[关闭]
@Scarlet 2017-01-07T06:16:35.000000Z 字数 16404 阅读 3579

NOIP泛做

NOIP 解题报告

联赛前没心情做BZOJ跑来写联赛题解23333
点击题目名称前往题目页面查看题目
年份我选择倒序= =

2015年

神奇的幻方

二维数组模拟题，跟着题面模拟坐标移动，相信大家都会做

  1. #include<bits/stdc++.h>
  2. int a[50][50],n;
  3. int main()
  4. {
  5.     scanf("%d",&n);
  6.     int nx=1,ny=(n+1)/2;
  7.     a[nx][ny]=1;
  8.     for (int i=2;i<=n*n;a[nx][ny]=i,i++)
  9.         if (nx==1&&ny!=n)nx=n,ny++;3
  10.         else
  11.         if (ny==n&&nx!=1)ny=1,nx--;
  12.         else
  13.         if (nx==1&&ny==n)nx++;
  14.         else
  15.         if (nx!=1&&ny!=n)
  16.             if (a[nx-1][ny+1])nx++;
  17.             else nx--,ny++;
  18.     for (int i=1;i<=n;i++,puts(""))
  19.         for (int j=1;j<=n;j++)
  20.             printf("%d ",a[i][j]);
  21. }

考点：模拟

信息传递

题意是寻找有向图最小环，由于所有点出度为，所以可以直接非递归模拟dfs，同时记录时间戳用来计算环的长度。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define maxn 200010
  4. #define INF 2000000000
  5. int dep[maxn],vis[maxn],f[maxn],l=0,ans=INF,n;
  6. int main()
  7. {
  8.     scanf("%d",&n);
  9.     for (int i=1;i<=n;i++)
  10.         scanf("%d",&f[i]);
  11.     for (int i=1;i<=n;i++)
  12.         if (!vis[i])
  13.         {
  14.             int j=i,st=1;l++;
  15.             while (!vis[f[j]])
  16.             {
  17.                 dep[j]=st;
  18.                 vis[j]=l;
  19.                 st++;
  20.                 j=f[j];
  21.             }
  22.             dep[j]=st;
  23.             vis[j]=l;
  24.             if (vis[j]==vis[f[j]]) ans=min(ans,dep[j]-dep[f[j]]+1);
  25.         }
  26.     printf("%d",ans);
  27. }

考点：图的遍历，有向图环长计算。

斗地主

考场上在下是想不出dp了，所以考虑搜索。
容易发现纯粹的暴力搜索每轮出牌会卡住，原因是当所有牌都是单牌（没有顺子）时，搜索会枚举出单牌的顺序，这很明显是和答案无关的，所以只管剪掉就行了，然后认真读题不写错就能过CCF数据了。
考场代码又丑又长，大家还是不要学了= =

考点：搜索，读题能力，细心程度

跳石头

题中“最短跳跃距离的最大值”具有十分明显的可二分性。所以直接考虑二分，题目就转化成了判断可行性问题。即把小于一定间距的石头移除，比较最终移除石头的数目。

  1. #include<bits/stdc++.h>
  2. #define maxn 50010
  3. int l,n,k,p[maxn],L,R,mid,ans;
  4. int check(int x)
  5. {
  6.     int k1=0,l=0;
  7.     for (int i=1;i<=n;i++)
  8.         if (p[i]-p[l]<x) k1++;
  9.         else l=i;
  10.     if (p[n+1]-p[l]<x) k1++;
  11.     if (k1>k) return 0;
  12.     return 1;
  13. }
  14. int main()
  15. {
  16.     scanf("%d%d%d",&l,&n,&k);
  17.     for (int i=1;i<=n;i++)
  18.         scanf("%d",&p[i]);
  19.     p[0]=0;
  20.     p[n+1]=l;
  21.     L=1,R=l;
  22.     while (L<=R)
  23.     {
  24.         mid=L+R>>1;
  25.         if (!check(mid)) R=mid-1;
  26.         else ans=mid,L=mid+1;
  27.     }
  28.     printf("%d",ans);
  29.     return 0;
  30. }

考点：二分答案，建模（问题转化）

子串

非常NOIP的一道dp题！大力推荐
既然说要在字符串取出段取匹配字符串，记表示取出段后，字符串以结尾，字符串匹配到的方案数，表示取出段后，字符串在之前结尾，字符串匹配到的方案数，明显是的一个前缀和即。容易看出，对于每一个匹配对，我们可以选择接续上一段或者新起一段，这时接续的话要求是连续，所以从转移过来，新起一段不一定要连续，可以从之前任意位置转移过来，所以是。这样就可以大力转移了。注意滚动数组。

  1. #include<bits/stdc++.h>
  2. #define maxn 1005
  3. #define maxm 205
  4. #define mod 1000000007
  5. using namespace std;
  6. typedef long long LL;
  7. #define G c=getchar()
  8. inline int read()
  9. {
  10.     int x=0,f=1;char G;
  11.     while(c>57||c<48){if(c=='-')f=-1;G;}
  12.     while(c>47&&c<58)x=x*10+c-48,G;
  13.     return x*f;
  14. }
  15. int f[2][maxn][maxm],g[2][maxn][maxm],n,m,k;
  16. char a[maxn],b[maxm],ans;
  17. int main()
  18. {
  19.     scanf("%d%d%d%s%s",&n,&m,&k,a+1,b+1);
  20.     for(int i=0;i<=n;i++)g[0][i][0]=1;
  21.     int cr=1;
  22.     for(int K=1;K<=k;K++,cr^=1)
  23.     {
  24.         memset(f[cr],0,sizeof(f[cr]));
  25.         memset(g[cr],0,sizeof(g[cr]));
  26.         for(int i=1;i<=n;i++)
  27.             for(int j=1;j<=m;j++)
  28.             {
  29.                 if(a[i]==b[j])f[cr][i][j]=(f[cr][i-1][j-1]+g[cr^1][i-1][j-1])%mod;//接续上一段或者新起一段
  30.                 g[cr][i][j]=(g[cr][i-1][j]+f[cr][i][j])%mod;//维护前缀和
  31.             }
  32.     }
  33.     printf("%d\n",g[cr^1][n][m]);
  34.     return 0;
  35. }

考点：动态规划，内存计算。

运输计划

非常不NOIP的数据结构题！但是考虑到题目答案也是能二分的，所以我们不妨来试着二分一下。
判断答案能否为，先找出所有长度大于的树链，总数为，那么这些树链是一定要有交集的，即某些边被这条树链都覆盖过。然后我们只需要找到树链交上的最大边权，和最长树链长比较一下就好了。
这里寻找树链交上的最大边权采用了差分的思路，一条链上集体，就相当于差分后在链两端，在最近公共祖先处。当一条边被覆盖了次，就说明它在所有链交上，此时更新答案即可。差分后用dfs前缀可还原并更新答案。
记住基于边的树上操作，点权是维护它父边的信息就可以简单处理细节了。
整个算法的时间瓶颈在于lca的计算和二分答案并判断上，所以时间复杂度是。这里是最大链长，因为采用了记忆化求解所以不大可能到达上界，实际复杂度接近。

  1. #include<bits/stdc++.h>
  2. #define maxn 300010
  3. #define maxm 600010
  4. using namespace std;
  5. typedef long long LL;
  6. #define G c=getchar()
  7. inline int read()
  8. {
  9.     int x=0,f=1;char G;
  10.     while(c>57||c<48){if(c=='-')f=-1;G;}
  11.     while(c>47&&c<58)x=x*10+c-48,G;
  12.     return x*f;
  13. }
  14. #define AE(u,v,w) E[Si]=(Ed){u,v,w},nxt[Si]=idx[u],idx[u]=Si++
  15. struct Ed{int u,v,w;}E[maxm];
  16. int idx[maxn],nxt[maxm],Si=1;
  17. int n,m,v[maxn],fa[maxn],siz[maxn],top[maxn],id[maxn],son[maxn],dep[maxn],dis[maxn],cnt=0;
  18. int que[maxn];
  19. int dfs(int x,int f)
  20. {
  21.     int re=1,w=0,t;
  22.     for(int i=idx[x];i;i=nxt[i])
  23.         if(E[i].v!=f)
  24.         {
  25.             fa[E[i].v]=x;dep[E[i].v]=dep[x]+1;dis[E[i].v]=dis[x]+E[i].w;
  26.             re+=t=dfs(E[i].v,x);if(t>w)w=t,son[x]=E[i].v;
  27.         }
  28.     return re;
  29. }
  30. void dfs2(int x,int tp)
  31. {
  32.     top[x]=tp;id[x]=cnt++;
  33.     if(son[x])dfs2(son[x],tp);
  34.     for(int i=idx[x];i;i=nxt[i])
  35.         if(E[i].v!=son[x]&&E[i].v!=fa[x])dfs2(E[i].v,E[i].v);
  36. }
  37. struct poi{int u,v,lca,w;}Q[maxn];
  38. int lca(int x,int y)//这里采用了稍快的树剖求lca，改成倍增的话就不超过NOIP范围了。
  39. {
  40.     for(;top[x]^top[y];x=fa[top[x]])
  41.         if(dep[top[x]]<dep[top[y]])swap(x,y);
  42.     return dep[x]<dep[y]?x:y;
  43. }
  44. int f[maxn],L,ha[maxn],www,cc;
  45. int calc(int x,int f)
  46. {
  47.     int tmp=ha[x];
  48.     for(int i=idx[x];i;i=nxt[i])
  49.         if(E[i].v!=f)
  50.             tmp+=calc(E[i].v,x);//前缀和还原信息
  51.     tmp>=cc?www=max(www,dis[x]-dis[f]):0;
  52.     return tmp;
  53. }
  54. int check(int x)
  55. {
  56.     cc=0;
  57.     for(int i=1;i<=m;i++)
  58.         if(Q[i].w>x)cc++;
  59.     if(f[cc])return f[cc]>=L-x;//记录部分答案进行优化
  60.     memset(ha,0,sizeof(ha));
  61.     for(int i=1;i<=m;i++)
  62.         if(Q[i].w>x)ha[Q[i].u]++,ha[Q[i].v]++,ha[Q[i].lca]-=2;//差分记录信息
  63.     www=0;
  64.     calc(1,0);
  65.     f[cc]=www;
  66.     return www>=L-x;
  67. }
  68. int main()
  69. {
  70.     n=read(),m=read();
  71.     for(int i=1,a,b,w;i<n;i++)a=read(),b=read(),w=read(),AE(a,b,w),AE(b,a,w);
  72.     dfs(1,0);
  73.     dfs2(1,1);
  74.     int ans,l=0,r=0;
  75.     for(int i=1,a,b;i<=m;i++)a=read(),b=read(),Q[i]=(poi){a,b,lca(a,b),0},Q[i].w=dis[a]+dis[b]-dis[Q[i].lca]*2,r=max(r,Q[i].w);
  76.     L=r;
  77.     for(;l<r;)
  78.     {
  79.         int mid=l+r>>1;
  80.         if(check(mid))r=mid;
  81.         else l=mid+1;
  82.     }
  83.     printf("%d\n",l);
  84.     return 0;
  85. }

考点：考场上敲对暴力，二分答案，差分、前缀互逆思想，lca

卖个萌，感觉还能再口胡一个做法：首先可以确定被删的边一定在最长链上（否则就不影响答案了）。
所以只需要对于最长链上每条边，求出不经过该边的最大链长（即删除这条边也不影响答案的部分），那么就转化成了一维的问题。
这一部分可以通过求出其他每条链和最长链的交来计算，大概可以dfs，乱搞。

如果采用的ST表技巧来求lca的话这题最终就变成了。

2014年

生活大爆炸版石头剪刀布

按照题目要求循环即可。

  1. #include<bits/stdc++.h>
  2. #define maxn 210
  3. using namespace std;
  4. int score[5][2]={{0,0,1,1,0},
  5.                  {1,0,0,1,0},
  6.                  {0,1,0,0,1},
  7.                  {0,0,1,0,1},
  8.                  {1,1,0,0,0}};
  9. int a[maxn],b[maxn];
  10. int main()
  11. {
  12.     int n,na,nb,sa=0,sb=0;
  13.     scanf("%d%d%d",&n,&na,&nb);
  14.     for (int i=1;i<=na;i++)
  15.         scanf("%d",&a[i]);
  16.     for (int i=1;i<=nb;i++)
  17.         scanf("%d",&b[i]);
  18.     for (int i=1;i<=n;i++)
  19.     {
  20.         int u=a[1+(i-1)%na],v=b[1+(i-1)%nb];
  21.         sa+=score[u][v];
  22.         sb+=score[v][u];
  23.     }
  24.     printf("%d %d",sa,sb);
  25.     return 0;
  26. }

考点：模拟

联合权值

考虑一个点的所有邻居对距离都为，就可以统计答案了。

第一问手动模拟每个点邻居的最大值和次大值。

第二问考虑


就好了。

（ 是对称求和）

  1. #include<bits/stdc++.h>
  2. #define maxn 200010
  3. #define mod 10007
  4. using namespace std;
  5. typedef long long LL;
  6. #define G c=getchar()
  7. inline int read()
  8. {
  9.     int x=0,f=1;char G;
  10.     while(c>57||c<48){if(c=='-')f=-1;G;}
  11.     while(c>47&&c<58)x=x*10+c-48,G;
  12.     return x*f;
  13. }
  14. int mx[maxn][3],s1[maxn],s2[maxn],ans1,ans2;
  15. int n,u[maxn],v[maxn],w[maxn];
  16. int main()
  17. {
  18.     n=read();
  19.     for(int i=1;i<n;i++)
  20.         u[i]=read(),v[i]=read();
  21.     for(int i=1;i<=n;i++)w[i]=read();
  22.     for(int i=1;i<n;i++)
  23.     {
  24.         s1[u[i]]+=w[v[i]],s1[v[i]]+=w[u[i]],
  25.         s2[u[i]]+=w[v[i]]*w[v[i]]%mod,s2[v[i]]+=w[u[i]]*w[u[i]]%mod;
  26.         if(w[v[i]]>mx[u[i]][0])mx[u[i]][4]=mx[u[i]][0],mx[u[i]][0]=w[v[i]];
  27.         else if(w[v[i]]>mx[u[i]][5])mx[u[i]][6]=w[v[i]];
  28.         if(w[u[i]]>mx[v[i]][0])mx[v[i]][7]=mx[v[i]][0],mx[v[i]][0]=w[u[i]];
  29.         else if(w[u[i]]>mx[v[i]][8])mx[v[i]][9]=w[u[i]];
  30.     }
  31.     for(int i=1;i<=n;i++)
  32.         ans1=max(ans1,mx[i][0]*mx[i][10]),s1[i]%=mod,ans2+=(s1[i]*s1[i]-s2[i])%mod;
  33.     printf("%d %d",ans1,(ans2%mod+mod)%mod);
  34. }

考点：树的性质，计算

飞扬的小鸟

一看就发现列是阶段，可以做相邻阶段的动态规划。
连续点击的叠加效果是明显可以记忆化的。处理管道的范围，滚动一下数组，这题就……没了？

  1. #include<bits/stdc++.h>
  2. #define maxn 10010
  3. using namespace std;
  4. int x[maxn],y[maxn],p,l[maxn],h[maxn];
  5. int f[maxn],g[maxn];
  6. int main()
  7. {
  8.     int n,m,k;
  9.     scanf("%d%d%d",&n,&m,&k);
  10.     for (int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]),l[i]=m+1;
  11.     for (int i=1;i<=k;i++)scanf("%d",&p),scanf("%d%d",&h[p],&l[p]);
  12.     int i;
  13.     for (i=1;i<=n;i++)
  14.     {
  15.         for (int j=1;j<=m;j++)g[j]=f[j],f[j]=1e9;
  16.         for (int j=1,k=0;j<=m;j++)f[k=min(j+x[i],m)]=min(f[k],min(g[j],f[j])+1);
  17.         for (int j=h[i]+1;j<l[i];j++)if (j+y[i]<=m) f[j]=min(f[j],g[j+y[i]]);
  18.         int k=0,j;
  19.         for (k=0,j=1;j<=m;k|=f[j++]<1e9) if (j<=h[i]||j>=l[i])f[j]=1e9;
  20.         if (!k) break;
  21.     }
  22.     int ans=0;
  23.     if (i<=n){for (int j=1;j<i;j++)if (l[j]<=m) ans++;return printf("0\n%d",ans),0;}
  24.     ans=1e9;
  25.     for (int i=1;i<=m;i++)ans=min(ans,f[i]);
  26.     printf("1\n%d",ans);
  27. }

考点：动态规划

无线网络发射器选址

小得浑身难受，大力模拟即可。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 600;
  4. int d, n,w[maxn][maxn],x,y,z;
  5. int cnt = 0, ans = 0;
  6. int get(int x, int y)
  7. {
  8.     int sum = 0;
  9.     for(int i = x-d; i <= x+d; ++i)
  10.         for(int j = y-d; j <= y+d; ++j)
  11.             if (i >=0 && j >=0)
  12.                sum += w[i][j];
  13.     return sum;
  14. }
  15. int main() {
  16.     scanf("%d%d", &d, &n);
  17.     for(int i = 1; i <= n; i++){
  18.         scanf("%d%d%d",&x,&y,&z);
  19.         w[x][y] = z;
  20.     }
  21.     for(int i = 0; i <= 128; i++)
  22.         for(int j = 0; j <= 128; j++) {
  23.             int x = get(i, j);
  24.             if(x > ans)ans = x,cnt = 1;
  25.             else if(x == ans)cnt++;
  26.     }
  27.     printf("%d %d\n", cnt, ans);
  28.     return 0;
  29. }

考点：模拟

寻找道路

因为要求路径上所有点出边都连像终点，所以正反两边bfs,反过来时记录哪些点是符合要求的，正过来就直接跑最短路，就能解决问题了。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define maxn 600000
  4. struct Edge {
  5.     int v,next;
  6. }e[maxn];
  7. int first[maxn],d[maxn],u1[maxn], u2[maxn],en;
  8. bool mark[maxn];
  9. int n, m;
  10. int s, t;
  11. void add(int u, int v) {
  12.     en++;
  13.     e[en].v = v;
  14.     e[en].next = first[u];
  15.     first[u] = en;
  16. }
  17. void bfs(int u, int flag) {
  18.     memset(d, -1, sizeof(d));
  19.     queue<int> q;
  20.     q.push(u);
  21.     d[u] = 0;
  22.     while(!q.empty()) {
  23.         int x = q.front();
  24.         q.pop();
  25.         for(int j = first[x]; j > 0; j = e[j].next)
  26.         if (j % 2 == flag && !mark[e[j].v]) {
  27.             int v = e[j].v;
  28.             if(d[v] == -1) {
  29.                 d[v] = d[x] + 1;
  30.                 q.push(v);
  31.             }
  32.         }
  33.     }
  34.     return ;
  35. }
  36. int main() {
  37.     memset(first, -1, sizeof(first));
  38.     scanf("%d%d", &n, &m);
  39.     en = 0; 
  40.     for(int i = 1; i <= m; i++) {
  41.         scanf("%d%d", &u1[i], &u2[i]);
  42.         add(u1[i],u2[i]);
  43.         add(u2[i],u1[i]);
  44.     }
  45.     scanf("%d%d", &s, &t);
  46.     bfs(t, 0);
  47.     for(int i = 1; i <= m; i++)
  48.         if(d[u2[i]] == -1)
  49.             mark[u1[i]] = true;
  50.     bfs(s, 1);
  51.     printf("%d\n", d[t]);
  52.     return 0;
  53. }

考点：最短路

解方程

有一个简易判断高精度数是否相等的办法就是对多种质数取模看余数。这道题也采用了这种做法：

选取几个较大素数（例如之间的），
对于每个，算出，是的必要条件，多选几个素数，就可以在一定范围大小内判断成功。

还有一个大力优化的方法是对于整系数多项式来说，。也就是说，当不是方程的解时，也不是方程的解。结合hash就完成了大力优化。

  1. #include<bits/stdc++.h>
  2. #define maxn 110
  3. #define R 4
  4. #define G getchar()
  5. using namespace std;
  6. int a[10010],A[110],P[4]={10007,11003,12007,13001},N,H[110][11],L,ans=0,V,p,X,sum,x,n,m,W;
  7. bool C[1000010];
  8. char ch;
  9. int main()
  10. {
  11.     scanf("%d%d\n",&n,&m);
  12.     for (int i=0;i<=n;i++)
  13.     {
  14.         L=0,ch=G;
  15.         if (ch=='-') N=-1;
  16.         else a[L++]=ch-48,N=1;
  17.         ch=G;
  18.         while (ch<=57&&ch>=48)
  19.             a[L++]=ch-48,ch=G;
  20.         scanf("\n");
  21.         for (int p=0;p<R;p++)
  22.         {
  23.             W=0;
  24.             for (int w=0;w<L;w++)W=(W*10+a[w])%P[p];
  25.             H[i][p]=(P[p]+W*N)%P[p];
  26.         } 
  27.     }
  28.     for (int i=1;i<=m;i++)
  29.     {
  30.         V=1;
  31.         if (C[i]) continue;
  32.         for (int j=0;j<R;j++)
  33.         {
  34.             p=P[j],x=i%p,sum=0,X=1;
  35.             for (int k=0;k<=n;k++) sum=(sum+X*H[k][j])%p,X=(X*x)%p; 
  36.             if (sum)
  37.             {
  38.                 for (int k=i;k<=m;k+=P[j])C[k]=1;
  39.                 V=0;break;
  40.             }
  41.         }
  42.         if (V) A[++ans]=i;
  43.     }
  44.     printf("%d\n",ans);
  45.     for (int i=1;i<=ans;i++)
  46.         printf("%d\n",A[i]);
  47.     return 0;
  48. }

考点：同余，打对高精度暴力

2013年

转圈游戏

看题意就是让你计算对mod取模的值

  1. #include<bits/stdc++.h>
  2. #define maxn 1000
  3. using namespace std;
  4. typedef long long LL;
  5. LL mod,r;
  6. LL Pow(LL x,LL y)
  7. {
  8.     LL r=1;
  9.     for(;y;y>>=1,x=x*x%mod)if(y&1)r=r*x%mod;
  10.     return r;
  11. }
  12. int main()
  13. {
  14.     LL m,k,x;
  15.     scanf("%lld%lld%lld%lld",&mod,&m,&k,&x);
  16.     LL p=(Pow(10,k)*(m%mod))%mod;
  17.     printf("%lld",(p+(x%mod))%mod); 
  18.     return 0;
  19. }

考点：快速幂、倍增

火柴排队


只要最大化就好了
由排序不等式知，同序和最大。也就是要花最少的代价交换使得在中的排名和在中的排名相同。

分别求出在中和在中的的排名再求一个相对逆序对就好了

  1. #include<bits/stdc++.h>
  2. #define maxn 100010
  3. using namespace std;
  4. int a[maxn],b[maxn],c[maxn];
  5. int u[maxn],s[maxn],t[maxn],n,w;
  6. long long sum=0;
  7. #define G c=getchar()
  8. inline int read()
  9. {
  10.     int x=0,f=1;char G;
  11.     while(c>57||c<48){if(c=='-')f=-1;G;}
  12.     while(c>47&&c<58)x=x*10+c-48,G;
  13.     return x*f;
  14. }
  15. int cmp(int a,int b){return u[a]<u[b];}
  16. struct poi{int s,t;}A[maxn];
  17. inline bool cmpp(const poi &a,const poi &b){return a.s<b.s;}
  18. void add(int x){for(;x<=n;x+=x&-x)c[x]++;}
  19. int ask(int x){for(w=0;x;x-=x&-x)w+=c[x];return w;}
  20. int main()
  21. {
  22.     n=read();
  23.     for(int i=0;i<n;i++)s[i]=t[i]=i;
  24.     for(int i=0;i<n;i++)u[i]=read();sort(s,s+n,cmp);
  25.     for(int i=0;i<n;i++)u[i]=read();sort(t,t+n,cmp);
  26.     for(int i=0;i<n;i++)A[i]=(poi){s[i],t[i]};
  27.     sort(A,A+n,cmpp);
  28.     sum=1ll*n*(n-1)>>1;
  29.     for(int i=0;i<n;i++)sum=sum-ask(A[i].t+1),add(A[i].t+1);
  30.     printf("%lld",sum%99999997);
  31.     return 0;
  32. }

考点：不等式、排序、逆序对

货车运输

即是求最大生成树上的链上最小值，构树后倍增即可。

  1. #include<bits/stdc++.h>
  2. #define maxm 70010
  3. #define maxn 10010
  4. #define INF 2000000000
  5. using namespace std;
  6. #define G c=getchar()
  7. inline int read()
  8. {
  9.     int x=0,f=1;char G;
  10.     while(c>57||c<48){if(c=='-')f=-1;G;}
  11.     while(c>47&&c<58)x=x*10+c-48,G;
  12.     return x*f;
  13. }
  14. struct Ed{int u,v,w;}E[maxm];
  15. int r[maxm],n,m,f[maxn];
  16. int GF(int x){return f[x]==x?x:f[x]=GF(f[x]);}
  17. int cmp(int a,int b){return E[a].w>E[b].w;}
  18. int nxt[maxm],idx[maxn],Si;
  19. #define AE(u,v,w) E[Si]=(Ed){u,v,w},nxt[Si]=idx[u],idx[u]=Si++
  20. int p[maxn][14];//以i跳2^j格的点
  21. int w[maxn][14];//跳的范围内最小边权
  22. int h[maxn];//每点深度
  23. int dfs(int u)
  24. {
  25.     for(int j=1;j<14;j++)
  26.         p[u][j]=p[p[u][j-1]][j-1],w[u][j]=min(w[u][j-1],w[p[u][j-1]][j-1]);
  27.     for(int i=idx[u];i+1;i=nxt[i])
  28.         if(!h[E[i].v])
  29.             h[E[i].v]=h[u]+1,p[E[i].v][0]=u,w[E[i].v][0]=E[i].w,dfs(E[i].v);
  30. }
  31. int LCA(int a,int b)
  32. {
  33.     int ans=INF;
  34.     if(GF(a)!=GF(b))return-1;
  35.     if(h[a]<h[b])swap(a,b);
  36.     for(int t=h[a]-h[b],j=0;t;t>>=1,j++)
  37.         if(t&1)ans=min(ans,w[a][j]),a=p[a][j];
  38.     if(a==b)return ans;
  39.     for(int j=13;j>=0;j--)
  40.         if(p[a][j]^p[b][j])
  41.             ans=min(ans,w[a][j]),a=p[a][j],ans=min(ans,w[b][j]),b=p[b][j];
  42.     ans=min(ans,w[a][0]);
  43.     return min(ans,w[b][0]);
  44. }
  45. int main()
  46. {
  47.     n=read(),m=read();
  48.     for(int i=1;i<=n;i++)f[i]=i;
  49.     for(int i=0;i<m;i++)r[i]=i;
  50.     for(int i=0,u,v,w;i<m;i++)u=read(),v=read(),w=read(),E[i]=(Ed){u,v,w};
  51.     sort(r,r+m,cmp);
  52.     memset(idx,-1,sizeof(idx));Si=m;
  53.     for(int i=0;i<m;i++)
  54.     {
  55.         Ed&e=E[r[i]];
  56.         int x=GF(e.u),y=GF(e.v);
  57.         if(x!=y)f[x]=y,AE(e.u,e.v,e.w),AE(e.v,e.u,e.w);
  58.     }
  59.     h[1]=1;dfs(1);
  60.     int q=read();
  61.     for(int i=1;i<=q;i++)
  62.         printf("%d\n",LCA(read(),read()));
  63.     return 0;
  64. }

积木大赛

经过思考可以发现，一座“山峰”建造长度只和山高、山谷高度差有关，利用这一点可以线性统计。

  1. #include<bits/stdc++.h>
  2. int n,l,r,s;
  3. int main()
  4. {
  5.     scanf("%d",&n);
  6.     for(;n--;l=r)
  7.         scanf("%d",&r),r>l?s+=r-l:0;
  8.     printf("%d",s);
  9. }

考点：观察样例

花匠

去掉重复相邻元素后数拐点个数。

  1. #include<bits/stdc++.h>
  2. #define maxn 100010
  3. int a[maxn],n,ans=2;
  4. int sqn(int a){return a>0?a:-1;}
  5. int main()
  6. {
  7.     scanf("%d%d",&n,&a[1]);
  8.     for(int i=2;i<=n;i++)
  9.     {
  10.         scanf("%d",&a[i]);
  11.         if (a[i]==a[i-1])i--,n--;
  12.     }
  13.     for(int i=2;i<=n-1;i++)
  14.         if (sqn(a[i]-a[i-1])*sqn(a[i+1]-a[i])<0)ans++;
  15.     printf("%d",min(ans,n));
  16.     return 0;
  17. }

考点：观察样例

华容道

因为可移动棋子一定要空格在边上才能动，所以肯定先要做一个最短路从空格到棋子，然后空格滚到棋子的另一边才能移动。
以空格与可移动棋子的位置关系作为状态，以空格的移动或是空格与可移动棋子交换作为转移，可以构造出一张图。
关键是q次询问都在同一个图里！
预处理出图后每次在图上跑最短路即可。

以空格靠在棋子某个方向为状态点，构图。算出每个点相邻四格互相移动的步数，连边。空格和棋子交换（即棋子挪动）也连边，权为1。

以超级起点（初始空格）跑到棋子四周的距离连边，目标终点四周与超级终点连边，边权为0，跑最短路。

代码

考点：建模，构图，最短路

2012年

Vigenère密码

注意到题目给出的表格是具有循环规律的，就意味着可以取模计算。

  1. #include<bits/stdc++.h>
  2. #define maxn 1010
  3. using namespace std;
  4. char s1[maxn],s2[maxn];
  5. int main()
  6. {
  7.     scanf("%s%s",s1,s2);
  8.     int n=strlen(s1),m=strlen(s2);
  9.     for(int i=0,j=0;i<m;i++,j++,j==n?j=0:0)
  10.     {
  11.         int a=s1[j]<97?s1[j]-65:s1[j]-97,b=s2[i]<97?s2[i]-65:s2[i]-97,c=(b-a+26)%26;
  12.         printf("%c",s2[i]<97?65+c:97+c);
  13.     }
  14.     return 0;
  15. }

考点：字符串模拟

国王游戏

按照排序后高精度计算。
证明可以参考其他题解。
大致思路是考虑交换两人以后，对拿钱最多大臣的影响，利用向下取整的性质可以讨论出结果。

代码被吃掉了QAQ

开车旅行

看上去两个人轮流操作，但是说白了就是在一棵固定的树上跑罢了。
所以可以倍增处理天内的路程
预处理应该是要用初赛的链表技巧，但是map乱搞过去了233。

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<cstdlib>
  4. #include<set>
  5. #include<map>
  6. #include<vector>
  7. #include<algorithm>
  8. #define INF 5000000000LL
  9. #define maxn 100010
  10. using namespace std;
  11. typedef long long LL;
  12. LL H[maxn];
  13. int n,TO[maxn][14],m;
  14. int pre[maxn][19];
  15. LL SA[maxn][19],SB[maxn][19];
  16. map <int,LL>mp;
  17. set <LL> S;
  18. typedef set <LL> ::iterator ITER;
  19. LL K[4];
  20. LL Abs(LL a){return a<0?-a:a;}
  21. int cmp(int a,int b){return abs(a)<abs(b);}
  22. double GG(int s,LL x,LL &sa,LL &sb)
  23. {
  24.     sa=sb=0;
  25.     for (int j=18;j>=0;j--)
  26.         if (pre[s][j]&&sa+sb+SA[s][j]+SB[s][j]<=x) sa+=SA[s][j],sb+=SB[s][j],s=pre[s][j];
  27.     if (sb==0) return INF;
  28.     return (double)sa/(double)sb;
  29. }
  30. int main()
  31. {
  32.     scanf("%d",&n);
  33.     for (int i=1;i<=n;i++)
  34.         scanf("%lld",&H[i]),mp[H[i]]=i;
  35.     S.insert(H[n]);
  36.     for (int i=n-1;i>=1;i--)
  37.     {
  38.         int l=0;
  39.         ITER a=S.lower_bound(H[i]),b=S.upper_bound(H[i]);
  40.         if (a!=S.begin()) a--,K[l++]=H[i]-(*a);
  41.         if (a!=S.begin()) a--,K[l++]=H[i]-(*a);
  42.         if (b!=S.end()) K[l++]=H[i]-(*b),b++;
  43.         if (b!=S.end()) K[l++]=H[i]-(*b),b++;
  44.         stable_sort(K,K+l,cmp);
  45.         TO[i][15]=mp[H[i]-K[0]];
  46.         if (l>1) TO[i][0]=mp[H[i]-K[1]];
  47.         S.insert(H[i]);
  48.     }
  49.     for (int i=1;i<=n;i++) 
  50.         pre[i][0]=TO[i][0],SA[i][0]=Abs(H[i]-H[TO[i][0]]);
  51.     for (int i=1;i<=n;i++) 
  52.         pre[i][16]=TO[pre[i][0]][17],SA[i][18]=SA[i][0],SB[i][19]=Abs(H[pre[i][0]]-H[pre[i][20]]);
  53.     for (int j=2;j<=18;j++)
  54.         for (int i=1;i<=n;i++)
  55.             if (pre[pre[i][j-1]][j-1]) 
  56.                 pre[i][j]=pre[pre[i][j-1]][j-1],
  57.                 SA[i][j]=SA[i][j-1]+SA[pre[i][j-1]][j-1],
  58.                 SB[i][j]=SB[i][j-1]+SB[pre[i][j-1]][j-1];
  59.     LL x0,sa,sb,ans;
  60.     double mn=1e60;
  61.     scanf("%lld",&x0);
  62.     for (int i=1;i<=n;i++)
  63.     {
  64.         double t=GG(i,x0,sa,sb);
  65.         if (t<mn||(t==mn&&H[i]>H[ans]))mn=t,ans=i;
  66.     }
  67.     printf("%lld\n",ans);
  68.     scanf("%d",&m);
  69.     for (int i=1;i<=m;i++)
  70.     {
  71.         int s;LL x;
  72.         scanf("%d%lld",&s,&x);
  73.         GG(s,x,sa,sb);
  74.         printf("%lld %lld\n",sa,sb);
  75.     }
  76.     return 0;
  77. }

考点：倍增，STL

同余方程

全裸的扩展欧几里得，套上板子求最小非负值即可。

  1. #include<bits/stdc++.h>
  2. void gcd(int a,int b,int& d,int& x,int &y)
  3. {
  4.     if (b)gcd(b,a%b,d,y,x),y-=x*(a/b);
  5.     else d=a,x=1,y=0;
  6. }
  7. int main()
  8. {
  9.     int a,b,x,y,d;
  10.     scanf("%d %d",&a,&b);
  11.     gcd(a,b,d,x,y);
  12.     int aa=b/d;
  13.     printf("%d",(x%aa+aa)%aa);
  14.     return 0;
  15. }

考点：数论，扩展欧几里得

借教室

这里参考的是草酸君的做法
先把订单全部用上，那么必定有很多天教室数是小于0的。那么我们可以从后往前删除订单。
然后就是差分模拟，当这天教室数小于0，就依次删除订单，直到这天教室数合法。
因为是删除订单，所以以前的教室一定合法。
删除订单的时候注意是维护差分数组还是前缀和的值。

  1. #include<bits/stdc++.h>
  2. #define maxn 1000010
  3. using namespace std;
  4. typedef long long LL;
  5. #define G c=getchar()
  6. inline LL read()
  7. {
  8.     LL x=0,f=1;char G;
  9.     while(c>57||c<48){if(c=='-')f=-1;G;}
  10.     while(c>47&&c<58)x=x*10+c-48,G;
  11.     return x*f;
  12. }
  13. LL w[maxn],dt[maxn],c[maxn],l[maxn],r[maxn],cur=0;
  14. int main()
  15. {
  16.     int n=read(),m=read(),M=m;
  17.     for(int i=1;i<=n;i++)dt[i]=(w[i]=read())-w[i-1];
  18.     for(int i=1;i<=m;i++)
  19.         c[i]=read(),l[i]=read(),r[i]=read()+1,dt[l[i]]-=c[i],dt[r[i]]+=c[i];
  20.     for(int i=1;i<=n;i++)
  21.         for(cur+=dt[i];cur<0;m--)
  22.             if(l[m]>i)dt[l[m]]+=c[m],dt[r[m]]-=c[m];
  23.             else if(r[m]>i)cur+=c[m],dt[r[m]]-=c[m];
  24.     if(m==M)puts("0");
  25.     else printf("-1\n%d",m+1);
  26.     return 0;
  27. }

考点：差分、前缀

疫情控制

考虑到每个军队一定是往根的方向走（能控制更多的城市），那么只需计算往上走的方式。
考虑二分答案，转为判定性问题：时间为，能否守住所有路。
倍增计算所有军队都往上走到的最远处（或是根），记录驻扎处（或是到根的军队以后剩下的可移动长度，按剩余长度排序*）。
dfs处理没能守住的、与顶点直接相邻的边，并按边长排序。
这时在根的军队有两个决策
1. 挑一个边过去守
2. （无代价）退回上来的边。

这时*处排序就有用了：对于可移动长度最短的边，一定让它退回原边（因为它是最没用的），除非原边已守。将不能退的军队从小到大和剩余的没有守住的边用恰当方式守住（仿），发现守不住即可退出。

近4K毒瘤丑Code：（三个DFS我也不知道我在想啥）

考点：二分答案、贪心、倍增

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注