[关闭]
@happyforever 2018-11-03T08:53:37.000000Z 字数 17852 阅读 530

六校联考11.2~11.3解题报告

解题报告 六校联考

Day1

各题状况

期望得分：
实际得分：

T1

就。。。没培养出来看到二叉树立马反应遍历顺序。
（上次做二叉树相关题目应该是半年前）

T2

从CF搬运过来的
luogu也有原题，《无尽的生命》
之前做过这个题但是当时也没有去学正解做法（敲完暴力跑路了）

T3

写完前两个题之后还剩大概分钟，就直接上了暴力，没有考虑优化

题目及考场代码

T1

image.png

  1. /*
  2.  * 选某个节点x的话需要满足w[x] < min(min_left[x],min_right[x])
  3.  * 若某个节点的左子树中有点那么min_left > max_right
  4.  *
  5.  * 对树上每个节点维护其左子树的最小最大值以及右子树的最大最小值
  6.  *
  7.  * 一条链那个描述有问题吧。。。。。
  8.  */
  9. #include <cstdio>
  11. inline int read()
  12. {
  13.     int n=0,w=1;register char c=getchar();
  14.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  15.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  16.     return n*w;
  17. }
  18. inline int max(int x,int y)
  19. {return x>y?x:y;}
  20. inline int min(int x,int y)
  21. {return x<y?x:y;}
  23. const int N=1e5+1,inf=2147483647;
  24. int n,w[N],minn[N],maxn[N],son[2][N],siz[N],ans=1;
  25. int fa[N],f[N];
  26. /*
  27. void dfs(int now)
  28. {
  29.     int left=son[0][now],right=son[1][now];
  30.     minn[now]=maxn[now]=w[now],siz[now]=1;
  31.     if(!left && !right)return ;
  32.     dfs(left),dfs(right);
  33.     siz[now]+=siz[left]+siz[right];
  34.     minn[now]=min(min(minn[left],minn[right]),w[now]);
  35.     maxn[now]=max(max(maxn[left],maxn[right]),w[now]);
  36. }
  37. */
  38. void dfs()
  39. {
  40.     int now=1,cnt=0;
  41.     while(now)
  42.     {
  43.         fa[++cnt]=w[now];
  44.         if(son[0][now])now=son[0][now];
  45.         else    now=son[1][now];
  46.     }
  47. }
  48. inline void work2()
  49. {
  50.     for(int i=1;i<=9;++i)
  51.         f[i]=1;
  52.     for(int maxx,i=2;i<=n;++i)
  53.     {
  54.         maxx=0;
  55.         for(int j=1;j<i;++j)
  56.             if(fa[j]<fa[i] && f[j]>maxx)
  57.                 maxx=f[j];
  58.         if((f[i]=maxx+1)>ans)
  59.             ans=f[i];
  60.     }
  61. }
  63. bool vis[11];
  64. void work(int now)
  65. {
  66.     int left=son[0][now],right=son[1][now];
  67.     minn[now]= inf,maxn[now]=-inf,siz[now]=0;
  68.     if(vis[now])
  69.     {
  70.         minn[now]=maxn[now]=w[now];
  71.         siz[now]=1;
  72.     }
  73.     if( left)work(left);
  74.     if(right)work(right);
  75.     minn[now]=min(min(minn[left],minn[right]),minn[now]);
  76.     maxn[now]=max(max(maxn[left],maxn[right]),maxn[now]);
  77.     siz[now]+=siz[left]+siz[right];
  78. }
  80. inline bool check()
  81. {
  82.     work(1);
  83. /*
  84.     if(vis[1] && vis[3] && vis[5])
  85.     {
  86.         for(int i=1;i<=n;++i)
  87.             printf("%d ",vis[i]?1:0);
  88.         puts("");
  89.         for(int i=1;i<=n;++i)
  90.             printf("%d %d %d\n",siz[i],minn[i],maxn[i]);
  91.     }
  92. */
  93.     for(int i=1;i<=n;++i)
  94.         if(minn[son[0][i]]<=maxn[son[1][i]] || (vis[i] && w[i]>=minn[son[1][i]]))
  95.             return false;
  96. //  puts("GG");
  97.     return true;
  98. }
  100. void meiju(int now)
  101. {
  102.     if(now>n){if(check())ans=max(ans,siz[1]);return ;}
  103.     vis[now]=true;
  104.     meiju(now+1);
  105.     vis[now]=false;
  106.     meiju(now+1);
  107. }
  109. int main()
  110. {
  111.     freopen("point.in","r",stdin);
  112.     freopen("point.out","w",stdout);
  114.     n=read();minn[0]=inf,maxn[0]=-inf;
  115.     for(int i=1;i<=n;++i)w[i]=read();
  116.     for(int i=1;i<=n;++i)son[0][i]=read(),son[1][i]=read();
  117.     if(n<=100)meiju(1);
  118.     else    work2();
  119.     printf("%d",ans);
  121.     fclose(stdin);fclose(stdout);
  122.     return 0;
  123. }

T2

image.png
image.png

  1. /*
  2.  * luogu原题吧。。。
  3.  * 40分可以归并排序求
  4.  * 20分特判
  5.  * 40分离散化+树状数组逆序对
  6.  */
  7. #include <cstdio>
  8. #include <iostream>
  10. inline int read()
  11. {
  12.     int n=0,w=1;register char c=getchar();
  13.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  14.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  15.     return n*w;
  16. }
  18. const int N=1e5+1;
  19. int n,a[N],emp[N];
  20. long long ans;
  22. void mergesort(int l,int r)
  23. {
  24.     if(l==r)return ;
  25.     int mid=l+r>>1;
  26.     mergesort(l,mid);
  27.     mergesort(mid+1,r);
  28.     int i=l,j=mid+1,k=l;
  29.     while(i<=mid && j<=r)
  30.     {
  31.         if(a[i]<a[j])
  32.             emp[k++]=a[i++];
  33.         else    ans+=mid-i+1,emp[k++]=a[j++];
  34.     }
  35.     while(i<=mid)emp[k++]=a[i++];
  36.     while(j<=r)emp[k++]=a[j++];
  37.     for(int x=l;x<=r;++x)
  38.         a[x]=emp[x];
  39. }
  41. void work1()
  42. {
  43.     int x=read(),y=read();
  44.     if(x>y)std::swap(x,y);
  45.     printf("%d",(y-x+1)*2-3);
  46. }
  47. void work2()
  48. {
  49. /*
  50.  * 两种情况：互相包含，互相交叉
  51.  * 假设a<x<y<b
  52.  * 相互包含那么答案为(b-a)+(b-a-1)+(y-x)+(y-x-1)
  53.  * 化简得：(b-a+y-x-1)*2
  54.  *
  55.  * 假设a<x<b<y
  56.  * 相互交叉那么答案为(b-a)+(b-a-1)+(y-x-1)+(y-x-2)
  57.  * 化简得：(b-a+y-x-2)*2
  58. */
  59.     int a=read(),b=read(),x=read(),y=read();
  60.     if(a>b)std::swap(a,b);
  61.     if(x>y)std::swap(x,y);
  62.     long long ans=b-a+y-x-1;
  63.     if(y>b)--ans;
  64.     std::cout<<ans*2;
  65. }
  67. int main()
  68. {
  69.     freopen("a.in","r",stdin);
  70.     freopen("a.out","w",stdout);
  72.     n=read();int maxn=0;
  73.     if(n==1)return work1(),0;
  74.     if(n==2)return work2(),0;
  75.     for(int i=1;i<=N;++i)a[i]=i;
  76.     for(int x,y,i=1;i<=n;++i)
  77.     {
  78.         x=read(),y=read();
  79.         if(x>y)std::swap(x,y);
  80.         std::swap(a[x],a[y]);
  81.         if(y>maxn)maxn=y;
  82.     }
  83. /*
  84.     for(int i=1;i<=maxn;++i)
  85.         printf("%d ",a[i]);
  86.     puts("");
  87. */
  88.     mergesort(1,maxn);
  89. /*  
  90.     for(int i=1;i<=maxn;++i)
  91.         printf("%d ",a[i]);
  92.     puts("");
  93. */
  94. //  printf("%d",ans);
  95.     std::cout<<ans;
  97.     fclose(stdin);fclose(stdout);
  98.     return 0;
  99. }

T3

image.png
image.png

  1. /*
  2.  * 每次将一个编号变成另一个编号
  3.  * 考虑对整张图维护按照编号建图
  4.  * 当编号改变时从所有这个编号的点出发向四周bfs，重新建图
  5.  */
  6. #include <queue>
  7. #include <cstdio>
  8. #include <cstring>
  9. #include <algorithm>
  11. inline int read()
  12. {
  13.     int n=0,w=1;register char c=getchar();
  14.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  15.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  16.     return n*w;
  17. }
  19. const int N=200001;
  20. int n,head[N],tot,a[N];
  21. struct Edge{
  22.     int v,nxt;
  23. }edge[N<<1];
  24. /*
  25. struct Node{
  26.     int id,col;
  27.     bool operator<(const Node &gg)const
  28.     {return col<gg.col;}
  29.     bool operator<(const int &x)const
  30.     {return col<x;}
  31. }a[N];
  32. */
  33. inline void add(int v,int u)
  34. {
  35.     edge[++tot]=(Edge){v,head[u]};head[u]=tot;
  36.     edge[++tot]=(Edge){u,head[v]};head[v]=tot;
  37. }
  39. bool vis[N];
  40. int ans;
  41. void dfs(int now,int fa)
  42. {
  43.     vis[now]=true;
  44.     for(int v,i=head[now];i;i=edge[i].nxt)
  45.         if((v=edge[i].v)!=fa && a[v]==a[now])
  46.             dfs(v,now);
  47. }
  49. void bfs(int y,int x)
  50. {
  51. //  while(!q.empty())q.pop();
  52. //  int now=std::lower_bound(a+1,a+1+n,x)-a;
  53.     if(ans==1)goto E;
  54.     ans=0;
  55.     memset(vis,false,sizeof vis);
  56.     for(int i=1;i<=n;++i)
  57.         if(a[i]==x)
  58.             a[i]=y;
  59.     for(int i=1;i<=n;++i)
  60.         if(!vis[i])
  61.             ++ans,dfs(i,i);
  62. E:  printf("%d\n",ans);
  63. }
  65. int main()
  66. {
  67.     freopen("simulator.in","r",stdin);
  68.     freopen("simulator.out","w",stdout);
  70.     n=read();int q=read();
  71. //  for(int i=1;i<=n;++i)a[i]=(Node){i,read()};
  72.     for(int i=1;i<=n;++i)a[i]=read();
  73.     for(int i=1;i<n;++i)
  74.         add(read(),read());
  75. /*  std::sort(a+1,a+1+n);
  76.     for(int i=1;i<=n;++i)
  77.         if(a[i].col!=a[i-1].col)
  78.             ++ans;
  79. */
  80.     while(q--)
  81.         bfs(read(),read());
  83.     fclose(stdin);fclose(stdout);
  84.     return 0;
  85. }

正解及代码

T1

选根节点的话，在这棵子树内选的其他的点都要比根节点的值大
如果在左子树选了一个点，在右子树中选的其他点要比它小
有10%的特殊数据有性质是所有节点都没有右子树或者都没有左子树，也就是说只需要维护第一条限制
此时显然是一个。。。最长上升子序列

首先对整棵树先遍历根节点再遍历右子树再遍历左子树
而后对这个dfs序跑最长上升子序列

  1. #include <cstdio>
  2. #include <algorithm>
  4. inline int read()
  5. {
  6.     int n=0,w=1;register char c=getchar();
  7.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  8.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  9.     return n*w;
  10. }
  12. const int N=1e5+1,inf=2147483647;
  13. int n,cnt,ls[N],rs[N],a[N],w[N];
  15. void dfs(int now)
  16. {
  17.     if(!now)return ;
  18.     a[++cnt]=w[now];
  19.     dfs(rs[now]);
  20.     dfs(ls[now]);
  21. }
  23. int sta[N],len;
  24. int main()
  25. {
  26.     freopen("point.in","r",stdin);
  27.     freopen("point.out","w",stdout);
  29.     n=read();
  30.     for(int i=1;i<=n;++i)w[i]=read();
  31.     for(int i=1;i<=n;++i)
  32.         ls[i]=read(),rs[i]=read();
  33.     dfs(1);
  34. /*
  35.     for(int i=1;i<=n;++i)
  36.         printf("%d ",a[i]);
  37. */
  38.     sta[++len]=a[1];
  39.     for(int i=2;i<=n;++i)
  40.     {
  41.         if(a[i]>sta[len])
  42.             sta[++len]=a[i];
  43.         else
  44.         {
  45.             int j=std::lower_bound(sta+1,sta+1+len,a[i])-sta;
  46.             sta[j]=a[i];
  47.         }
  48.     }
  49.     printf("%d",len);
  51.     fclose(stdin);fclose(stdout);
  52.     return 0;
  53. }

T2

首先，将交换过的数离散化，这样值域就和个数同阶
总的答案可以成两部分算：
一部分是位置改变的。
我们可以用树状数组维护
另一部分是位置没有改变的
这样每个数都在原来的位置上，我们首先处理出哪些元素没有改变，用前缀和维护
表示小于 的元素中没有出现过的有几个
这样每次将 的前缀和 和 当前数的前缀和做差即可

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<iostream>
  4. #define LL long long 
  5. #define lb(x) (x & (-x))
  6. #define Pair pair<int, int> 
  7. #define fi first
  8. #define se second
  9. #define MP(x, y) make_pair(x, y)
  10. using namespace std;
  11. const int MAXN = 1e6 + 10;
  12. inline int read() {
  13.     char c = getchar(); int x = 0, f = 1;
  14.     while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
  15.     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); 
  16.     return x * f;
  17. }
  18. int N, T[MAXN],  date[MAXN], pos[MAXN];// pos[i] i位置的元素   date 离散化数组
  19. LL sum[MAXN];
  20. Pair P[MAXN];
  21. void add(int x) {
  22.     for(int i = x; i <= N * 2; i += lb(i)) T[i]++;
  23. }
  24. LL Query(int x) {
  25.     LL ans = 0;
  26.     for(int i = x; i; i -= lb(i)) ans += T[i];
  27.     return ans;
  28. }
  29. int main() {
  30.     freopen("a.in","r", stdin); freopen("a.out", "w", stdout);
  31.     N = read();
  32.     for(int i = 1; i <= N; i++) {
  33.         P[i].fi = read(), P[i].se = read();
  34.         date[i] = P[i].fi; date[i + N] = P[i].se;
  35.         pos[i] = i; pos[i + N] = i + N;
  36.     }
  37.     sort(date + 1, date + N * 2 + 1);
  38.     int num = unique(date + 1, date + N * 2 + 1) - date - 1;
  39.     for(int i = 1; i <= num; i++) sum[i] = sum[i - 1] + date[i] - date[i - 1] - 1;
  40.     for(int i = 1; i <= N; i++) {
  41.         P[i].fi = lower_bound(date + 1, date + num + 1, P[i].fi) - date;
  42.         P[i].se = lower_bound(date + 1, date + num + 1, P[i].se) - date;
  43.         swap(pos[P[i].fi], pos[P[i].se]);
  44.     }
  45.     LL ans = 0;
  46.     for(int i = num; i >= 1; i--) {
  47.         ans += Query(pos[i]);
  48.         ans += abs(sum[pos[i]] - sum[i]);
  49.         add(pos[i]);
  50.     }
  51.     cout << ans << "\n";
  52.     return 0;
  53. }

T3


我们发现给定我们树上的所有节点的颜色，我们可以求得军团个数，方法是进行dfs，如果一个结点和他父亲节点颜色不同，答案就
然后暴力更改暴力统计答案

我们可以优化一下上面那个暴力，用vector纪录下每种颜色存在的位置，然后枚举要更改的颜色位置，每个位置原来对于答案的贡献是和他相邻不同色的节点个数，我们减去原来的答案加上更改后的答案就得到了当前的答案。然后再暴力合并vector就行了

我们考虑优化合并操作，我们发现把变成和把变成得到的答案是相同的，所以我们在合并的时候以及更改颜色的时候都是把颜色少的改成颜色多的，并且维护每种颜色实际的vector是哪个，然后就相当于启发式合并。
每个点的复杂度就是其度数乘以它被统计答案的次数，最差情况下每个点也只会被统计次答案，那么复杂度就是
也就等于

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<queue>
  5. #include<iostream>
  6. #include<set>
  7. #include<map>
  8. #define ll long long
  9. #define M 200010
  10. using namespace std;
  11. int read() {
  12.     int nm = 0, f = 1;
  13.     char c = getchar();
  14.     for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
  15.     for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
  16.     return nm * f;
  17. }
  19. int note[M], sz[M], cor[M], id[M];
  20. vector<int>to[M], to1[M];
  21. int n, q, ans;
  22. void dfs(int now, int fa) {
  23.     if(cor[now] != 0 && cor[now] != cor[fa]) ans++;
  24.     for(int i = 0; i < to[now].size(); i++) {
  25.         int vj = to[now][i];
  26.         if(vj == fa) continue;
  27.         dfs(vj, now);
  28.     }
  29. }
  31. void del(int x) {
  32.     for(int i = 0; i < to[x].size(); i++) {
  33.         int vj = to[x][i];
  34.         if(cor[vj] != cor[x]) ans--;
  35.     }
  36. }
  37. void insert(int x) {
  38.     for(int i = 0; i < to[x].size(); i++) {
  39.         int vj = to[x][i];
  40.         if(cor[vj] != cor[x]) ans++;
  41.     }
  42. }
  43. int tot = 0, tot2 = 0;
  44. int main() {
  45.     freopen("simulator.in", "r", stdin), freopen("simulator.out", "w", stdout);
  46.     n = read(), q = read();
  47.     for(int i = 1; i <= n; i++) cor[i] = read(), sz[cor[i]]++, to1[cor[i]].push_back(i), id[i] = i, note[i] = i;
  48.     for(int i = 1; i < n; i++) {
  49.         int vi = read(), vj = read();
  50.         to[vi].push_back(vj), to[vj].push_back(vi);
  51.     }
  52.     to[1].push_back(0), cor[0] = 0x3e3e3e3e;
  53.     dfs(1, 0);
  54.     while(q--) {
  55.         int x = read(), y = read();
  56.         int xn = id[x], yn = id[y];
  57.         if(sz[xn] < sz[yn]) {
  58.             tot += sz[xn], tot2 += to1[xn].size();
  59.             for(int i = 0; i < to1[xn].size(); i++) {
  60.                 int op = to1[xn][i];
  61.                 del(op);
  62.                 to1[yn].push_back(op);
  63.             }
  64.             for(int i = 0; i < to1[xn].size(); i++) {
  65.                 int op = to1[xn][i];
  66.                 cor[op] = yn;
  67.             }
  68.             for(int i = 0; i < to1[xn].size(); i++) {
  69.                 int op = to1[xn][i];
  70.                 insert(op);
  71.             }
  72.             to1[xn].clear();
  73.             sz[yn] += sz[xn];
  74.             sz[xn] = 0;
  75.             id[x] = 0;
  76.         } else {
  77.             tot+=sz[yn], tot2 += to1[yn].size();
  78.             for(int i = 0; i < to1[yn].size(); i++) {
  79.                 int op = to1[yn][i];
  80.                 del(op);
  81.                 to1[xn].push_back(op);
  82.             }
  83.             for(int i = 0; i < to1[yn].size(); i++) {
  84.                 int op = to1[yn][i];
  85.                 cor[op] = xn;
  86.             }
  87.             for(int i = 0; i < to1[yn].size(); i++) {
  88.                 int op = to1[yn][i];
  89.                 insert(op);
  90.             }
  91.             to1[yn].clear();
  92.             sz[xn] += sz[yn];
  93.             sz[yn] = 0;
  94.             id[y] = xn;
  95.             id[x] = 0;
  96.         }
  97.         cout << ans << "\n";
  98.     }
  99.     return 0;
  100. }

Day2

各题状况

期望得分：
实际得分：

T1

开场分钟切掉，爽翻
然后直接忽略数据范围看去了
然后。。
image.png
有一部分数据是所有
那么这个循环就会一直跑到RE才停下来
那就。。。挂了

T2

暴力范围给错了，特殊性质看串了行，就。。。没做考虑

T3

图里面有环，我的解决办法是设置数组，但是dfs的时候忘了回溯就。。。了

题目及考场代码

T1

image.png
image.png

  1. /*
  2.  * 考前知道是gxb出的这道题。。
  3.  * 于是7:30的时候反复问了他两遍：你T1是个水题吧
  4.  * 是
  5.  * en
  6.  * 哇，瞬间心安
  7.  *
  8.  * 开始考试15分钟之后切掉
  9.  * 爽了
  10.  */
  11. #include <cstdio>
  12. #include <algorithm>
  14. inline int read()
  15. {
  16.     int n=0,w=1;register char c=getchar();
  17.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  18.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  19.     return n*w;
  20. }
  22. const int N=1e5+1;
  23. int n,s,a[N];
  25. int main()
  26. {
  27.     freopen("median.in","r",stdin);
  28.     freopen("median.out","w",stdout);
  30.     n=read(),s=read();
  31.     for(int i=1;i<=n;++i)
  32.         a[i]=read();
  33.     std::sort(a+1,a+1+n);
  34.     long long ans=0;
  35.     for(int i=n/2+1;a[i]<s;++i)
  36.         ans+=s-a[i];
  37.     printf("%I64d",ans);
  39.     fclose(stdin);fclose(stdout);
  40.     return 0;
  41. }

T2

image.png
image.png

  1. /*
  2.  * 他这暴力范围给错了吧。。。
  3.  *
  4.  * 题目实际相当于给你2n个位置，在其中挑n个位置放东西
  5.  * 若将没放东西的位置看做+1,放了东西的位置看做-1,要求对任意位置的前缀和小于k
  6.  *
  7.  * 若k>n,ans=C(2n,n)
  8.  * 设dp[i][j]表示第i天,前缀和为j,但是负数没法考虑
  9.  * dp[i][j]=dp[i-1][j-1]*2+dp[i-1][j+1]*2
  10.  *
  11.  * 若k==1那么就是括号序列的合法方案数，即Catalan数
  12.  */
  13. #include <cstdio>
  14. /*
  15. inline int read()
  16. {
  17.     int n=0,w=1;register char c=getchar();
  18.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  19.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  20.     return n*w;
  21. }
  22. inline int ksm(long long x,int b)
  23. {
  24.     long long res=1;
  25.     for(;b;b>>=1,x=x*x%p)
  26.         if(b&1)
  27.             res=res*x%p;
  28.     return res;
  29. }
  30. */
  31. const int N=1e3+1;
  32. int n,m,k,p,dp[N][N],ans;
  34. int exgcd(int a,int b,int &x,int &y)
  35. {
  36.     if(!b)
  37.     {
  38.         x=1,y=0;
  39.         return a;
  40.     }
  41.     int t=exgcd(b,a%b,y,x);
  42.     y-=(a/b)*x;
  43.     return t;
  44. }
  46. void work1()
  47. {
  48.     long long ans,emp=1,tmp=1;int i,x,y;
  49.     for(i=2;i<=n;++i)
  50.         emp=emp*i%p;
  51.     n<<=1;
  52.     for(;i<=n;++i)
  53.         tmp=tmp*i%p;
  54.     exgcd(tmp,p,x,y);
  55.     if(x<0)x+=p;
  56.     printf("%d",emp*x%p);
  57. }
  59. bool a[N];
  60. void dfs(int now,int sum,int last)
  61. {
  62.     if(now>m)
  63.     {
  64.         if(last==0)
  65.         {
  66.             ++ans;
  67. /*
  68.             for(int i=1;i<=m;++i)
  69.                 printf("%d ",a[i]?1:0);
  70.             puts("");
  71. */
  72.             if(ans==p)ans=0;
  73.         }
  74.         return ;
  75.     }
  76.     if(sum<k-1)//不写作业
  77.     {
  78.         a[now]=false;
  79.         dfs(now+1,sum+1,last);
  80.     }
  81.     if(last>0)//写作业
  82.     {
  83.         a[now]=true;
  84.         dfs(now+1,sum-1,last-1);
  85.     }
  86. }
  88. long long work2(int h)
  89. {
  90.     if(h==1)return 1;
  91.     if(h==2)return 2;
  92.     if(h==3)return 5;
  93.     return (work2(h-1)*(4*h-2)%(p*(h+1)))/(h+1)%p;
  94. }
  96. int main()
  97. {
  98.     freopen("term.in","r",stdin);
  99.     freopen("term.out","w",stdout);
  101.     scanf("%d%d%d",&n,&k,&p);
  102.     if(k>n)work1();
  103.     else
  104.         if(n<=15)
  105.         {
  106.             m=n<<1;dfs(1,0,n);
  107.             printf("%d\n",ans);
  108.         }
  109.         else
  110.             if(k==1)
  111.                 printf("%d",work2(n));
  112.             else    ;
  114. E:  fclose(stdin);fclose(stdout);
  115.     return 0;
  116. }

T3

image.png
image.png

  1. /*
  2.  */
  3. #include <cstdio>
  4. #include <cstring>
  6. inline int read()
  7. {
  8.     int n=0,w=1;register char c=getchar();
  9.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  10.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  11.     return n*w;
  12. }
  14. const int N=200001,inf=2147483647;
  15. int tot,n,m,s,t,ans=-1,val[N],head[N],fa[N],fa_dis[N];
  16. bool vis[N];
  17. struct Edge{
  18.     int v,w,nxt;
  19. }edge[N];
  20. void add(int w,int v,int u)
  21. {
  22.     edge[++tot]=(Edge){v,w,head[u]};head[u]=tot;
  23.     fa[v]=u,fa_dis[v]=w;
  24. }
  26. void dfs(int now,int w)
  27. {
  28. //  printf("%d %d\n",now,w);
  29.     w&=val[now];
  30.     vis[now]=true;
  31.     if(now==t)
  32.     {
  33.         if(w<ans || ans==-1)
  34.             ans=w;
  35.         return ;
  36.     }
  37.     for(int v,i=head[now];i;i=edge[i].nxt)
  38.         if(!vis[v=edge[i].v])
  39.             dfs(v,w&edge[i].w);
  40. }
  42. inline void work()
  43. {
  44.     int x=inf;
  45.     while(s!=t && t)
  46.     {
  47.         x&=fa_dis[t]&val[t];
  48.         t=fa[t];
  49.     }
  50.     if(s==t)ans=val[s]&x;
  51. }
  53. int main()
  54. {
  55.     freopen("rabbit.in","r",stdin);
  56.     freopen("rabbit.out","w",stdout);
  58.     n=read(),m=read(),s=read(),t=read();
  59.     for(int i=1;i<=n;++i)val[i]=read();
  60.     for(int i=1;i<=m;++i)
  61.         add(read(),read(),read());
  62.     if(n<=10)
  63.         dfs(s,inf);
  64.     else    work();
  65.     printf("%d",ans);
  67.     fclose(stdin);fclose(stdout);
  68.     return 0;
  69. }

正解及代码

T1

首先排序
考虑从的位置开始往后统计有多少位置的数，我们只需要修改这些位置的数字就可以了
所以 

  1. #include <cstdio>
  2. #include <algorithm>
  4. inline int read()
  5. {
  6.     int n=0,w=1;register char c=getchar();
  7.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  8.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  9.     return n*w;
  10. }
  12. const int N=1e5+1;
  13. int n,s,a[N];
  15. int main()
  16. {
  17.     freopen("median.in","r",stdin);
  18.     freopen("median.out","w",stdout);
  20.     n=read(),s=read();
  21.     for(int i=1;i<=n;++i)
  22.         a[i]=read();
  23.     std::sort(a+1,a+1+n);
  24.     long long ans=0;
  25.     for(int i=n/2+1;a[i]<s && i<=n;++i)
  26.         ans+=s-a[i];
  27.     printf("%I64d",ans);
  29.     fclose(stdin);fclose(stdout);
  30.     return 0;
  31. }

T2

题目实际相当于给你个和个,要求对任意位置的前缀和的方案数有多少
的时候答案显然为卡特兰数，所以我们考虑卡特兰数的证明过程
若数列不合法，那么一定存在一个位置，假设在位置前面有个，有个
我们考虑将位置之后的个变成，个变成
那么该序列一共含有个和个
所以不合法的方案数就是
用总方案数减去不合法方案数就是合法方案数了
这样可以拿到分

对于最后的分，注意到模数不一定是质数
考虑对阶乘进行质因数分解，对模数也进行质因数分解，那么就可以通过先把质因数同时除掉之后再进行
或者也可以用扩展卢卡斯定理

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #define int long long 
  5. #define LL int
  6. using namespace std;
  7. const int MAXN = 2 * 1e6 + 10;
  8. inline int read() {
  9.     char c = getchar(); int x = 0, f = 1;
  10.     while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
  11.     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  12.     return x * f;
  13. }
  14. int N, mod, prime[MAXN], vis[MAXN], tot, mn[MAXN], num[MAXN], K;
  15. void GetPhi(int N) {
  16.     vis[1] = 1;
  17.     for(int i = 2; i <= N; i++) {
  18.         if(!vis[i]) prime[++tot] = i, mn[i] = tot;
  19.         for(int j = 1; j <= tot && (i * prime[j] <= N); j++) {
  20.             vis[i * prime[j]] = 1; mn[i * prime[j]] = j;
  21.             if(!(i % prime[j])) break;
  22.         }
  23.     }
  24. }
  25. void insert(int x, int opt) {
  26.     while(x != 1) num[mn[x]] += opt, x = x / prime[mn[x]];
  27. }
  28. int fastpow(int a, int p) {
  29.     int base = 1;
  30.     while(p) {
  31.         if(p & 1) base = (1ll * base * a) % mod;
  32.         a = (1ll * a * a) % mod; p >>= 1;
  33.     }
  34.     return base;
  35. }
  36. int FindAns() {
  37.     LL ans = 1;
  38.     for(int i = 1; i <= tot; i++) 
  39.         if(num[i]) 
  40.             ans = (1ll * ans * fastpow(prime[i], num[i])) % mod;    
  41.     return ans;
  42. }
  43. main() {
  44.     freopen("term.in", "r", stdin);
  45.     freopen("term.out", "w", stdout);
  46.     N = read();  K = read(); mod = read();
  47.     GetPhi(2 * N);
  48.     for(int i = N + 1; i <= 2 * N; i++) insert(i, 1);
  49.     for(int i = 1; i <= N; i++) insert(i, -1);
  50.     LL ans1 = FindAns();
  51.     memset(num, 0, sizeof(num));
  53.     for(int i = N + K + 1; i <= 2 * N; i++) insert(i, 1);
  54.     for(int i = 1; i <= N - K; i++) insert(i, -1);
  56.     LL ans2 = FindAns();
  57.     cout << (ans1 - ans2 + mod) % mod;
  59.     return 0;
  60. }

T3

缩点然后反着跑SPFA有分
注意的部分分并不是保证给定的是一棵树，可能是很多个联通块并且每个联通块里面可能有环

对于的数据可以考虑在每个联通块中维护当前联通块所有边权和点权的是多少，那么问题转化成DAG上的问题
考虑从高位向低位枚举二进制位，贪心策略是希望高位上能够为，那么我们考虑在整个DAG中的那些路径是能够使这一位为的，显然，在所有从到的道路中，若存在某个点或者边，那么他所有的后继路径和前驱路径都是可行的，那么我们可以正反拓扑两次找到所有可行的点边集合作为当前答案。
然后考虑下一位，下一位中因为要保证上一位是，所以能够走的点和边肯定是上次得到的点边集合里的，我们在这个得到的集合中在尽行同样的拓扑看看当前位是否可行，如果可行的话就用新得到的点边集合去更新原图的点边集合。
如此做三十次考虑所有的位就能得到答案了。

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<queue>
  5. #include<iostream>
  6. #include<ctime>
  7. #include<cmath>
  8. #include<set>
  9. #include<map>
  10. #define ll long long
  11. #define M 700010
  12. struct Edge {
  13.     int vi, vj, v;
  14. } edge[M];
  15. struct Note {
  16.     int vj, v, id;
  17. } be;
  18. using namespace std;
  19. int read() {
  20.     int nm = 0, f = 1;
  21.     char c = getchar();
  22.     for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
  23.     for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
  24.     return nm * f;
  25. }
  26. vector<int>to[M];
  27. vector<Note> to1[M], to2[M];
  28. int belong[M], st[M], dfn[M], low[M], dft, n, m, s, t, note[M], noww[M], tp, tot, sz[M], ans = 2147483647, rudu1[M], rudu2[M];
  29. bool vis[M];
  30. void tarjan(int now) {
  31.     vis[now] = true;
  32.     st[++tp] = now;
  33.     dfn[now] = low[now] = ++dft;
  34.     for(int i = 0; i < to[now].size(); i++) {
  35.         int vj = to[now][i];
  36.         if(!dfn[vj]) {
  37.             tarjan(vj);
  38.             low[now] = min(low[now], low[vj]);
  39.         } else if(vis[vj]) low[now] = min(low[now], dfn[vj]);
  40.     }
  41.     if(dfn[now] == low[now]) {
  42.         tot++;
  43.         while(st[tp] != now) {
  44.             int x = st[tp];
  45.             vis[x] = false;
  46.             noww[tot] &= note[x];
  47.             belong[x] = tot;
  48.             tp--;
  49.         }
  50.         int x = st[tp];
  51.         vis[x] = false;
  52.         noww[tot] &= note[x];
  53.         belong[x] = tot;
  54.         tp--;
  55.     }
  56. }
  57. bool can[M], tmp1[M], tmp2[M];
  58. int note1[M], note2[M], tp1, tp2;
  60. void tuopu() {
  61.     queue<int>q;
  62.     q.push(belong[t]);
  63.     while(!q.empty()) {
  64.         int op = q.front();
  65.         q.pop();
  66.         for(int i = 0; i < to2[op].size(); i++) {
  67.             int vj = to2[op][i].vj;
  68.             rudu2[vj]++;
  69.             if(!vis[vj]) q.push(vj), vis[vj] = true;
  70.         }
  71.     }
  72.     while(!q.empty()) q.pop();
  73.     q.push(belong[s]);
  74.     while(!q.empty()) {
  75.         int op = q.front();
  76.         note1[++tp1] = op;
  77.         q.pop();
  78.         for(int i = 0; i < to1[op].size(); i++) {
  79.             int vj = to1[op][i].vj;
  80.             rudu1[vj]--;
  81.             if(rudu1[vj] == 0) q.push(vj);
  82.         }
  83.     }
  84.     q.push(belong[t]);
  85.     while(!q.empty()) {
  86.         int op = q.front();
  87.         q.pop();
  88.         note2[++tp2] = op;
  89.         for(int i = 0; i < to2[op].size(); i++) {
  90.             int vj = to2[op][i].vj;
  91.             rudu2[vj]--;
  92.             if(rudu2[vj] == 0) q.push(vj);
  93.         }
  94.     }
  95. }
  97. void work(int x) {
  98.     for(int i = 1; i <= tot; i++) tmp1[i] = tmp2[i] = false;
  99.     if((noww[belong[s]] & x) == 0) tmp1[belong[s]] = true;
  100.     for(int i = 1; i <= tp1; i++) {
  101.         int op = note1[i];
  102.         for(int j = 0; j < to1[op].size(); j++) {
  103.             be = to1[op][j];
  104.             if((tmp1[op] == true) || (can[be.id] && ((be.v & x) == 0))) {
  105.                 tmp1[be.vj] = true;
  106.                 tmp1[be.id] = true;
  107.             } else if((noww[be.vj] & x) == 0 && (can[be.vj])) tmp1[be.vj] = true;
  108.         }
  109.     }
  110.     if((noww[belong[t]] &x) == 0) tmp2[belong[t]] = true;
  111.     for(int i = 1; i <= tp2; i++) {
  112.         int op = note2[i];
  113.         for(int j = 0; j < to2[op].size(); j++) {
  114.             be = to2[op][j];
  115.             if((tmp2[op] == true) || (can[be.id] && ((be.v & x) == 0))) {
  116.                 tmp2[be.vj] = true;
  117.                 tmp2[be.id] = true;
  118.             } else if((noww[be.vj] & x) == 0 && (can[be.vj])) tmp2[be.vj] = true;
  119.         }
  120.     }
  121.     for(int i = 1; i <= tot; i++) tmp1[i] = (tmp1[i] | tmp2[i]);
  122.     if(tmp1[belong[s]] && tmp1[belong[t]]) ans -= x;
  123.     else return;
  124.     for(int i = 1; i <= tot; i++) can[i] = (can[i] & tmp1[i]);
  125. }
  126. int main() {
  127.     freopen("rabbit.in", "r", stdin);
  128.     freopen("rabbit.out", "w", stdout);
  129.     cin >> n >> m >> s >> t;
  130.     for(int i = 1; i <= n; i++) note[i] = read(), noww[i] = 2147483647;
  131.     for(int i = 1; i <= m; i++) {
  132.         int vi = read(), vj = read(), v = read();
  133.         edge[i].vi = vi, edge[i].vj = vj, edge[i].v = v;
  134.         to[vi].push_back(vj);
  135.     }
  136.     tarjan(s);
  137.     if(!dfn[t]) {
  138.         puts("-1");
  139.         return 0;
  140.     }
  141.     for(int i = 1; i <= m; i++) {
  142.         int vi = edge[i].vi, vj = edge[i].vj, v = edge[i].v;
  143.         vi = belong[vi], vj = belong[vj];
  144.         if(vi == 0 || vj == 0) continue;
  145.         if(vi == vj) noww[vi] &= v;
  146.         else {
  147.             be.id = ++tot;
  148.             be.vj = vj;
  149.             be.v = v;
  150.             to1[vi].push_back(be);
  151.             rudu1[vj]++;
  152.             be.vj = vi;
  153.             to2[vj].push_back(be);
  154.         }
  155.     }
  156.     if(belong[s] == belong[t]) {
  157.         cout << noww[belong[s]] << "\n";
  158.         return 0;
  159.     }
  160.     tuopu();
  161.     for(int i = 1; i <= tot; i++) can[i] = true;
  162.     for(int i = 30; i >= 0; i--) work(1 << i);
  163.     cout << ans << "\n";
  164.     return 0;
  165. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注