[关闭]
@01010101 2018-10-17T13:42:23.000000Z 字数 5246 阅读 760

1016

T1
这是个二维平面世界，平面上有n个特殊的果实，我从(0,0)点出发，希望得到尽量多的果实，但是出于某种特殊的原因，我的运动方式只有三种（假设当前我在(x,y)）：
1、我可以走到(x+1,y)
2、我可以走到(x,y+1)
3、我可以走到(x+1,y+1)
现在我需要你的帮助，帮我找出我最多能够得到多少个果实。
1<=n<=100000，-10^9<=x,y<=10^9

用带一点点扫描线的思想来想，如果按横坐标排序，那么数量就是纵坐标不断递增的。就是最长上升子序列了。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  7. int read(){
  8.     char ch;int op=1;
  9.     while((ch=getchar())<'0'||ch>'9') if(ch=='-') op=-1;
  10.     int ret=ch-'0';
  11.     while((ch=getchar())>='0'&&ch<='9') ret=ret*10+ch-'0';
  12.     return ret*op;
  13. }
  15. const int N=100000+10;
  17. int n,cnt;
  18. int t[N];
  20. struct node{
  21.     int xx,yy;
  22.     bool operator < (const node &b) const{
  23.         if(xx!=b.xx) return xx<b.xx;
  24.         return yy<b.yy;
  25.     }
  26. }a[N];
  28. int main(){
  29.     freopen("find.in","r",stdin);
  30.     freopen("find.out","w",stdout);
  31.     n=read();
  32.     for(int i=1;i<=n;++i){
  33.         a[i].xx=read();a[i].yy=read();
  34.     }
  35.     sort(a+1,a+n+1);
  36.     for(int i=1;i<=n;++i){
  37.         if(a[i].xx<0||a[i].yy<0) continue;
  38.         int b=a[i].yy;
  39.         if(b>=t[cnt]){
  40.             t[++cnt]=b;
  41.         }
  42.         else{
  43.             int l=1,r=cnt,mid,ans=-1;
  44.             while(l<=r){
  45.                 int mid=(l+r)>>1;
  46.                 if(t[mid]>b) {ans=mid;r=mid-1;}
  47.                 else l=mid+1;
  48.             }
  49.             if(ans!=-1) t[ans]=b;
  50.         }
  51.     }
  52.     printf("%d\n",cnt);
  53.     return 0;
  54. }

T2
这是个奇异的世界，世界上的n-1条路联结起来形成一棵树，每条路有一个对应的权值ci。
现在我会给出q组询问或操作。
每次询问我会从一个x点走到y点，初始在x点我会有一个数字v，然后每走过一条权值为c的边，我的v就会变成,问最后到y时v变成了什么。
每次修改我会修改一条边的权值，保证修改后的权值小于等于原来的权值且不会小于1。
每组询问或操作的格式如下：
询问：1 x y v表示从x走到y，一开始的数字为v。
操作：2 p c表示将第p条边的边权修改为c
n,q<=100000,c_i,v_i <= 10^{18}

显然，走过一条非1边后边权至少减半。所以有两种维护方式：1边，或0边。
对于1边：可以用并查集进行路径压缩。
对于0边：可以用树链剖分维护从当前点到根的路径乘积，用double进行乘，超过1e18就置为0。
此题不需要维护精度：
有两个结论：
1.
向下取整只与数值有关，与数的先后无关。
2.
向下取整可以变连除为除一个。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #define ll long long
  5. using namespace std;
  7. ll read(){
  8.     char ch;ll op=1;
  9.     while((ch=getchar())<'0'||ch>'9') if(ch=='-') op=-1;
  10.     ll ret=ch-'0';
  11.     while((ch=getchar())>='0'&&ch<='9') ret=ret*10+ch-'0';
  12.     return ret*op;
  13. }
  14. void write(ll x){
  15.     if(x<0) putchar('-'),x=-x;
  16.     if(x>=10) write(x/10);
  17.     putchar('0'+x%10);
  18. }
  20. const ll N=100000+10;
  21. const ll D=20;
  23. ll n,m,k,q;
  24. ll head[N],cst[N],f[N],d[N],fa[N][D+2];
  26. struct edge{
  27.     ll v,w,nxt;
  28. }e[N<<1];
  29. void adde(ll u,ll v,ll w){
  30.     e[k].v=v;
  31.     e[k].w=w;
  32.     e[k].nxt=head[u];
  33.     head[u]=k++;
  34. }
  36. ll Find(ll x){
  37.     return (f[x]==x)?x:f[x]=Find(f[x]);
  38. }
  40. void dfs(ll u,ll fath){
  41.     d[u]=d[fath]+1;fa[u][0]=fath;
  42.     for(ll i=head[u];i!=-1;i=e[i].nxt){
  43.         ll v=e[i].v;
  44.         if(v!=fath){
  45.             if(e[i].w==1) f[v]=Find(u);
  46.             else f[v]=v;
  47.             dfs(v,u);
  48.             cst[v]=e[i].w;
  49.         }
  50.     }
  51. }
  53. ll Lca(ll u,ll v){
  54.     if(d[u]<d[v]) swap(u,v);
  55.     for(ll i=D;i>=0;--i){
  56.         if(d[fa[u][i]]>=d[v]) u=fa[u][i];
  57.     }
  58.     if(u==v) return u;
  59.     for(ll i=D;i>=0;--i){
  60.         if(fa[u][i]!=fa[v][i]){
  61.             u=fa[u][i];
  62.             v=fa[v][i];
  63.         }
  64.     }
  65.     return fa[u][0];
  66. }
  68. ll up_tree(ll u,ll t,ll cc){
  69.     while(d[u]>d[t]&&cc!=0){
  70.         cc/=cst[u];
  71.         if(f[u]!=u) u=f[u];
  72.         else u=fa[u][0];
  73.     }
  74.     return cc;
  75. }
  78. ll a,b,c,op;
  80. int main(){
  81. //  freopen("walk.in","r",stdin);
  82. //  freopen("walk.out","w",stdout);
  83.     memset(head,-1,sizeof(head));
  84.     scanf("%lld%lld",&n,&q);
  85.     for(ll i=1;i<n;++i){
  86.         a=read();b=read();c=read();
  87.         adde(a,b,c);adde(b,a,c);
  88.     }
  89.     f[1]=1;
  90.     dfs(1,0);
  91.     for(ll i=1;i<=D;++i){
  92.         for(ll j=1;j<=n;++j){
  93.             fa[j][i]=fa[fa[j][i-1]][i-1];
  94.         }
  95.     }
  96.     while(q--){
  97.         op=read();
  98.         if(op==1){
  99.             a=read();b=read();c=read();
  100.             ll l=Lca(a,b);
  101.             write(up_tree(b,l,up_tree(a,l,c)));
  102.             putchar('\n');
  103.         }
  104.         else{
  105.             a=read();b=read();
  106.             if(b==1) {
  107.                 f[e[2*a-2].v]=Find(e[2*a-1].v);
  108.             }
  109.             cst[e[2*a-2].v]=b;
  110.         }
  111.     }
  112.     return 0;
  113. }

T3
这是个有n个点的世界，有m条无向边连接着这n个点，但是不保证点之间能够互相到达。
“这个世界的夕阳，只在奇数长的简单路径的尽头。”一个神如是说。
于是我想知道对于一个点对(x,y)，x到y之间的所有简单路径中是否存在长度为奇数的路径，只有这样，我才能找到存在有夕阳的路。保证没有自环与重边。
1≤n,q,m≤100000

此题的考察知识较多。

题解：
假设我们现在对原图先得到一棵生成树（其实应该是森林，毕竟不保证联通）
那么我们对于询问(x,y)，我们要看的其实是在生成树上x到y的路径上是否存在在某个奇环内的边（“奇环”指长度为奇数的环）。
于是问题转化成看一条边是否在奇环中，一个很直观的想法是，对于一个强连通分量，如果在这个强连通分量中存在一条在奇环中的边，那么所有在强连通分量里的边都是存在于某一个奇环中的。
那么如何在一个强连通分量里找到是否有在奇环中的边呢？我们对这个图做tarjan，对于一条虚边(u,v)如果dep[u]与dep[v]的奇偶性相同（dep[u]表示u在树中的深度），那么u到v的路径上的边都是在奇环中的。
于是我们可以得到每条边是否存在于奇环中，问题就变得很简单了。
对于一个询问(x,y)如果dep[x]和dep[y]奇偶性不同，那么是yes的
否则如果在x到y的路径上存在有在奇环中的边，那么也是yes的，这个可以通过预处理出点到根节点的路径上的这种边的个数得到。
再否则就只有no了。

注意：弹栈要在退栈的时候弹。

  1. const int N=100000+10;
  2. const int D=20;
  4. int n,m,k,tp,idx;
  5. int head[N],d[N],fa[N][D+2],dfn[N],low[N],sta[N],odd[N],s[N],vis[N];
  7. struct edge{
  8.     int v,nxt;
  9. }e[N<<1];
  10. void adde(int u,int v){
  11.     e[k].v=v;
  12.     e[k].nxt=head[u];
  13.     head[u]=k++;
  14. }
  16. void tarjan(int u,int fath){
  17.     d[u]=d[fath]+1;fa[u][0]=fath;
  18.     dfn[u]=low[u]=++idx;sta[++tp]=u;
  19.     for(int i=head[u];i!=-1;i=e[i].nxt){
  20.         int v=e[i].v;
  21.         if(!dfn[v]){
  22.             tarjan(v,u);
  23.             low[u]=min(low[u],low[v]);
  24.         }
  25.         else if(v!=fath){
  26.             if((d[u]&1)==(d[v]&1))  odd[u]=1;
  27.             low[u]=min(low[u],dfn[v]);
  28.         }
  29.     }
  30.     if(dfn[u]==low[u]){
  31.         int pos=tp,w=0;
  32.         while(sta[pos]!=u) w|=(odd[sta[pos--]]);
  33.         if(w==1) {
  34.             while(sta[tp]!=u) s[sta[tp--]]++;
  35.         }
  36.         else tp=pos-1;//!!不能再忘else了！！！！
  37.     }
  38. }
  40. int Lca(int u,int v){
  41.     if(d[u]<d[v]) swap(u,v);
  42.     for(int i=D;i>=0;--i){
  43.         if(d[fa[u][i]]>=d[v]) u=fa[u][i];
  44.     }
  45.     if(u==v) return u;
  46.     for(int i=D;i>=0;--i){
  47.         if(fa[u][i]!=fa[v][i]){
  48.             u=fa[u][i];
  49.             v=fa[v][i];
  50.         }
  51.     }
  52.     if(fa[u][0]==fa[v][0]) return fa[u][0];
  53.     return -1;  
  54. }
  56. void dfs(int u,int fath){
  57.     for(int i=head[u];i!=-1;i=e[i].nxt){
  58.         int v=e[i].v;
  59.         if(fa[v][0]==u){
  60.             vis[v]=1;
  61.             s[v]+=s[u]; 
  62.             dfs(v,u);
  63.         }
  64.     }
  65. }
  67. int a,b,q;
  69. int main(){
  70. //  freopen("a.txt","r",stdin);
  71.     memset(head,-1,sizeof(head));
  73.     n=read();m=read();
  74.     for(int i=1;i<=m;++i){
  75.         a=read();b=read();
  76.         adde(a,b);adde(b,a);
  77.     }
  78.     for(int i=1;i<=n;++i){
  79.         if(!dfn[i]){
  80.             tarjan(i,i);
  81.         }
  82.     }
  83.     for(int i=1;i<=D;++i){
  84.         for(int j=1;j<=n;++j){
  85.             fa[j][i]=fa[fa[j][i-1]][i-1];
  86.         }
  87.     }
  88.     for(int i=1;i<=n;++i){
  89.         if(fa[i][0]==i){
  90.             dfs(i,i);
  91.         }
  92.     }
  94.     q=read();
  96.     while(q--){
  97.         a=read();b=read();
  98.         int l=Lca(a,b);
  99.         if(l==-1) {puts("No");continue;}
  100.         if(((d[a]+d[b]-2*d[l])&1)==1) {puts("Yes");continue;}
  101.         if(s[a]+s[b]>2*s[l]) {puts("Yes");continue;}
  102.         puts("No");     
  103.     }
  104. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注