CF1101

D:题意：树上每个顶点有个权值，求最长链，满足链上gcd > 1

解：对每个质数建虚树，每个点只会拆成log个点，所以是log²的。

 #include <bits/stdc++.h>

 const int N = ;

 struct Edge {

     int nex, v, len;

 }edge[N << ], EDGE[N << ]; int tp, TP;

 int p[N], top, e[N], pos2[N], num2, ST[N << ][], pw[N << ], n, ans, id[N], last[N];

 int vis[N];

 int imp[N], K, E[N], val[N], fa[N], d[N], stk[N], use[N], Time, RT, f[N];

 std::vector<int> v[N];

 inline void add(int x, int y) {

     tp++;

     edge[tp].v = y;

     edge[tp].nex = e[x];

     e[x] = tp;

     return;

 }

 inline void ADD(int x, int y) {

     TP++;

     EDGE[TP].v = y;

     EDGE[TP].len = d[y] - d[x];

     EDGE[TP].nex = E[x];

     E[x] = TP;

     return;

 }

 inline void getp(int n) {

     for(int i = ; i <= n; i++) {

         if(!vis[i]) {

             p[++top] = i;

             last[i] = i;

             id[i] = top;

         }

         for(int j = ; j <= top && i * p[j] <= n; j++) {

             vis[i * p[j]] = ;

             last[i * p[j]] = p[j];

             if(i % p[j] == ) break;

         }

     }

     return;

 }

 void DFS_1(int x, int f) {

     fa[x] = f;

     d[x] = d[f] + ;

     pos2[x] = ++num2;

     ST[num2][] = x;

     for(int i = e[x]; i; i = edge[i].nex) {

         int y = edge[i].v;

         if(y == f) {

             continue;

         }

         DFS_1(y, x);

         ST[++num2][] = x;

     }

     return;

 }

 inline void prework() {

     for(int i = ; i <= num2; i++) pw[i] = pw[i >> ] + ;

     for(int j = ; j <= pw[num2]; j++) {

         for(int i = ; i + ( << j) -  <= num2; i++) {

             if(d[ST[i][j - ]] < d[ST[i + ( << (j - ))][j - ]])

                 ST[i][j] = ST[i][j - ];

             else

                 ST[i][j] = ST[i + ( << (j - ))][j - ];

         }

     }

     return;

 }

 inline int lca(int x, int y) {

     x = pos2[x];

     y = pos2[y];

     if(x > y) std::swap(x, y);

     int t = pw[y - x + ];

     if(d[ST[x][t]] < d[ST[y - ( << t) + ][t]])

         return ST[x][t];

     else

         return ST[y - ( << t) + ][t];

 }

 inline bool cmp(const int &a, const int &b) {

     return pos2[a] < pos2[b];

 }

 inline void work(int x) {

     if(use[x] != Time) {

         use[x] = Time;

         f[x] = ;

         E[x] = ;

     }

     return;

 }

 inline void build_t() {

     std::sort(imp + , imp + K + , cmp);

     TP = top = ;

     work(imp[]);

     stk[++top] = imp[];

     for(int i = ; i <= K; i++) {

         int x = imp[i], y = lca(x, stk[top]);

         work(x); work(y);

         while(top >  && pos2[y] <= pos2[stk[top - ]]) {

             ADD(stk[top - ], stk[top]);

             top--;

         }

         if(y != stk[top]) {

             ADD(y, stk[top]);

             stk[top] = y;

         }

         stk[++top] = x;

     }

     while(top > ) {

         ADD(stk[top - ], stk[top]);

         top--;

     }

     RT = stk[top];

     return;

 }

 void DFS(int x) {

     int a = , b = ;

     for(int i = E[x]; i; i = EDGE[i].nex) {

         int y = EDGE[i].v;

         DFS(y);

         if(EDGE[i].len > ) continue;

         if(f[y] > a) {

             b = a;

             a = f[y];

         }

         else b = std::max(b, f[y]);

     }

     if(vis[x] == Time) {

         ans = std::max(ans, a + b + );

         f[x] = a + ;

     }

     return;

 }

 int main() {

     getp(N - );

     memset(vis, , sizeof(vis));

     int tot = top, flag = ;

     scanf("%d", &n);

     for(int i = ; i <= n; i++) {

         scanf("%d", &val[i]);

         int x = val[i];

         if(x > ) flag = ;

         while(x > ) {

             int y = last[x];

             while(x % y == ) {

                 x /= y;

             }

             v[id[y]].push_back(i);

         }

     }

     for(int i = , x, y; i < n; i++) {

         scanf("%d%d", &x, &y);

         add(x, y); add(y, x);

     }

     if(flag) {

         puts("");

         return ;

     }

     DFS_1(, );

     prework();

     for(int i = ; i <= tot; i++) {

         K = ;

         ++Time;

         for(int j = ; j < (int)v[i].size(); j++) {

             imp[++K] = v[i][j];

             vis[v[i][j]] = Time;

         }

         build_t();

         DFS(RT);

     }

     printf("%d \n", ans);

     return ;

 }

AC代码

G：题意：给定序列，你要把它分成尽可能多的几段，每段的权值是异或和。

要求没有哪些段的权值异或和为0。输出最大段数。无解-1。

解：考虑无解，肯定是总异或和为0。否则一定存在解。

发现这个东西，其实等价于选出一些前缀，因为异或可以抵消，所以这些前缀能表示出的和这些段能表示出的是相同的。

然后就把前缀插入线性基，看能插入多少个。

看到异或就要想线性基。

 #include <bits/stdc++.h>

 const int N = ;

 int b[], a[N];

 inline int insert(int x) {

     for(int i = ; i >=  && x; i--) {

         if(((x >> i) & ) == ) continue;

         if(b[i]) x ^= b[i];

         else {

             b[i] = x;

             return ;

         }

     }

     return ;

 }

 int main() {

     int n;

     scanf("%d", &n);

     for(int i = ; i <= n; i++) {

         scanf("%d", &a[i]);

         a[i] ^= a[i - ];

     }

     if(!a[n]) {

         printf("-1\n");

         return ;

     }

     int cnt = ;

     for(int i = n; i >= ; i--) {

         cnt += insert(a[i]);

     }

     printf("%d \n", cnt);

     return ;

 }

AC代码

巴特西

CF1101

最新文章

热门文章