枚举推式子

1 #include 
      
        2 using namespace std; 3 typedef long long LL; 4 LL gcd(LL a, LL b){ 5     return a % b ? gcd(b, a % b) : b; 6 } 7 int main(){ 8     int T; 9     scanf("%d", &T);10     while(T--) {11         LL K, M, six = 6;12         cin >> K >> M;13         LL a = K + 1, b = K + 2, c = K + 3;14         LL g = gcd(a, six);15         a /= g, six /= g;16         g = gcd(b, six);17         b /= g, six /= g;18         g = gcd(c, six);19         c /= g, six /= g;20         LL ans = a * b % M * c % M;21         cout << ans << endl;22     }23     return 0;24 }
      

 

子树修改子树询问转路径标记

1 #include 
      
        2 using namespace std; 3 const int maxn = 1e6 + 10; 4 typedef long long LL; 5   6 int node; 7 LL val[maxn], num[maxn], del[maxn]; 8 LL sum[maxn], tot[maxn]; 9 map
       
         G[maxn];10 void insert(string s, LL v){11     int p = 0;12     for(int i = 0; i < s.length(); ++i){13         if(G[p].find(s[i]) == G[p].end()) G[p][s[i]] = ++node;14         p = G[p][s[i]];15         v -= del[p];16         sum[p] += v;17         tot[p]++;18     }19     val[p] += v;20     num[p]++;21 }22 void modify(string s, LL v) {23     int p = 0;24     for (int i = 0; i < s.length(); ++i) {25         if (G[p].find(s[i]) == G[p].end()) G[p][s[i]] = ++node;26         p = G[p][s[i]];27     }28     del[p] += v;29     LL tmp = tot[p];30     p = 0;31     for (int i = 0; i < s.length(); ++i) {32         if (G[p].find(s[i]) == G[p].end()) G[p][s[i]] = ++node;33         p = G[p][s[i]];34         if(i != s.length() - 1) sum[p] += tmp * v;35     }36 }37 LL Q1(string s) {38     int p = 0;39     LL tmp = 0;40     for (int i = 0; i < s.length(); ++i) {41         if (G[p].find(s[i]) == G[p].end()) G[p][s[i]] = ++node;42         p = G[p][s[i]];43         tmp += del[p];44     }45     return val[p] + tmp * num[p];46 }47 LL Q2(string s) {48     int p = 0;49     LL tmp = 0;50     for (int i = 0; i < s.length(); ++i) {51         if (G[p].find(s[i]) == G[p].end()) G[p][s[i]] = ++node;52         p = G[p][s[i]];53         tmp += del[p];54     }55     return sum[p] + tmp * tot[p];56 }57  58 char s[maxn];59 int main(){60     int N;61     scanf("%d", &N);62     for(int i = 1; i <= N; ++i){63         int o, a, b;64         scanf("%d", &o);65         if(o == 1){66             scanf("%s %d", s, &a);67             insert(string(s), a);68         }69         else if(o == 2){70             scanf("%s %d", s, &a);71             modify(string(s), a);72         }73         else if(o == 3){74             scanf("%s", s);75             printf("%lld\n", Q1(string(s)));76         }77         else{78             scanf("%s", s);79             printf("%lld\n", Q2(string(s)));80         }81     }82     return 0;83 }
       
      

 

缩点

1 #include 
      
        2 using namespace std; 3 const int maxn = 1e5 + 10; 4  5 // BCC 6 set
       
         SE[maxn], ans; 7 set
        
          :: iterator it; 8 stack
         
           S; 9 vector
          
            G[maxn];10 int dfs_clock, dfn[maxn], low[maxn];11 int bcc_cnt, bccno[maxn];12 void dfs(int u, int fa)13 {14     dfn[u] = low[u] = ++dfs_clock;15     S.push(u);16     for(int i = 0; i < G[u].size(); ++i)17     {18         int v = G[u][i];19         if(!dfn[v])20         {21             dfs(v, u);22             low[u] = min(low[u], low[v]);23         }24         else if(!bccno[v]) low[u] = min(low[u], dfn[v]);25     }26 27     if(low[u] == dfn[u])28     {29         bcc_cnt++;30         while(1)31         {32             int x = S.top(); S.pop();33             bccno[x] = bcc_cnt;34             SE[bcc_cnt].insert(x);35             if(x == u) break;36         }37     }38 }39 40 void find_bcc(int n)41 {42     memset(dfn, 0, sizeof(dfn));43     memset(bccno, 0, sizeof(bccno));44     dfs_clock = bcc_cnt = 0;45     for(int i = 1; i <= n; i++) if(!dfn[i]) dfs(i, 0);46 }47 48 int deg[maxn];49 int main(){50     int n, m;51     scanf("%d %d", &n, &m);52     for(int i = 1; i <= m; ++i){53         int u, v;54         scanf("%d %d", &u, &v);55         G[u].push_back(v);56     }57     find_bcc(n);58     for(int i = 1; i <= n; ++i){59         for(int j = 0; j < G[i].size(); ++j)60             if(bccno[i] != bccno[G[i][j]]) deg[bccno[G[i][j]]]++;61     }62     for(int i = 1; i <= bcc_cnt; ++i){63         if(deg[i] == 0) ans.insert(*SE[i].begin());64     }65     printf("%d\n", ans.size());66     for(it = ans.begin(); it != ans.end(); it++){67         if(it != ans.begin()) putchar(' ');68         printf("%d", *it);69     }70     puts("");71     return 0;72 }
          
         
        
       
      

 

启发式合并

1 #include 
      
        2 using namespace std; 3 const int maxn = 1e5 + 10; 4 typedef long long LL; 5 typedef pair
       
         pii; 6 vector
        
          G[maxn]; 7 int n, m; 8  9 int sz[maxn];10 LL bt[maxn];11 void dfs(int x, int f){12     bt[x] = 0;13     sz[x] = 1;14     for(int i = 0; i < G[x].size(); ++i){15         int to = G[x][i].first, d = G[x][i].second;16         if(to == f) continue;17         dfs(to, x);18         bt[x] += bt[to] + d * sz[to];19         sz[x] += sz[to];20     }21 }22 23 LL ans;24 int id[maxn];25 map
         
           S[maxn];26 map
          
            :: iterator it;27 void add(int x, int f, int y){28     S[y][bt[x]] = 1;29     for(int i = 0; i < G[x].size(); ++i){30         int to = G[x][i].first;31         if(to == f) continue;32         add(to, x, y);33     }34 }35 void dfs1(int x, int f){36     id[x] = x;37     int M = 0, ms = 0;38     for(int i = 0; i < G[x].size(); ++i){39         int to = G[x][i].first;40         if(to == f) continue;41         dfs1(to, x);42         if(sz[to] > M) M = sz[to], ms = to;43     }44     if(ms) id[x] = id[ms];45     for(int i = 0; i < G[x].size(); ++i){46         int to = G[x][i].first;47         if(to == f || to == ms) continue;48         add(to, x, id[x]);49     }50     it = S[id[x]].lower_bound(bt[x] - m);51     if(it != S[id[x]].end()) ans = max(ans, bt[x] - (*it).first);52     S[id[x]][bt[x]] = 1;53 }54 55 int main(){56     int T;57     scanf("%d", &T);58     while(T--){59         scanf("%d %d", &n, &m);60         for(int i = 1; i <= n; ++i) G[i].clear(), S[i].clear();61         for(int i = 1; i < n; ++i){62             int u, v, d;63             scanf("%d %d %d", &u, &v, &d);64             G[u].push_back(pii(v, d));65             G[v].push_back(pii(u, d));66         }67         ans = -1;68         dfs(1, 0);69         dfs1(1, 0);70         printf("%lld\n", ans);71     }72     return 0;73 }
          
         
        
       
      

 

倒着并茶几

1 #include 
      
        2 using namespace std; 3 const int maxn = 1e5 + 10; 4 int a[maxn], b[maxn], ans[maxn]; 5 int base[maxn][33], vis[maxn]; 6  7 int fa[maxn]; 8 int Find(int x){ 9     return fa[x] == x ? x : fa[x] = Find(fa[x]);10 }11 void Union(int x, int y){12     x = Find(x), y = Find(y);13     if(x == y) return;14     for(int i = 29; i >= 0; i--){15         if(!base[x][i]) continue;16         for(int j = 29; j >= 0; j--){17             if((1 << j) & base[x][i]){18                 if(base[y][j]) base[x][i] ^= base[y][j];19                 else {20                     base[y][j] = base[x][i];21                     break;22                 }23             }24         }25     }26     fa[x] = y;27 }28 29 int main(){30     int N, M = 0;31     scanf("%d", &N);32     for(int i = 1; i <= N; ++i) fa[i] = i;33     for(int i = 1; i <= N; ++i) scanf("%d", a + i);34     for(int i = 1; i <= N; ++i) scanf("%d", b + i);35     for(int i = N; i >= 1; --i){36         int x = a[b[i]], y = 0;37         for(int j = 29; j >= 0; --j){38             if((1 << j) & x){39                 base[b[i]][j] = x;40                 break;41             }42         }43         vis[b[i]] = 1;44         if(vis[b[i] - 1]) Union(b[i] - 1, b[i]);45         if(vis[b[i] + 1]) Union(b[i] + 1, b[i]);46         x = Find(b[i]);47         for(int j = 29; j >= 0; --j){48             if((1 << j) & y) continue;49             y ^= base[x][j];50         }51         M = max(M, y);52         ans[i] = M;53     }54     for(int i = 1; i <= N; ++i) printf("%d\n", ans[i]);55     return 0;56 }