[关闭]
@RabbitHu 2017-09-02T14:16:05.000000Z 字数 77072 阅读 2591

胡小兔的 OI 日志 2 (2017.7.19 ~ 2017.8.31）

日记

查看最新

CodeVS 1553 互斥的数 ｜ 哈希

有这样的一个集合，集合中的元素个数由给定的N决定，集合的元素为N个不同的正整数，一旦集合中的两个数x,y满足y = P*x，那么就认为x,y这两个数是互斥的，现在想知道给定的一个集合的最大子集满足两两之间不互斥。

输入有多组数据，每组第一行给定两个数N和P（1<=N<=10^5, 1<=P<=10^9）。接下来一行包含N个不同正整数ai（1<=ai<=10^9）。

输出一行表示最大的满足要求的子集的元素个数。

可以多搞几个模数用来取模。

@ 逻辑或打成逻辑与……没想清楚就写。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. using namespace std;
  5. typedef long long ll;
  6. const ll HA = 19260817, ME = 20010313, MO = 97797977;
  7. bool ha[HA], me[ME], mo[MO];
  8. ll n, p, a[100005], ans;
  9. int main(){
  10.     scanf("%lld%lld", &n, &p);
  11.     for(int i = 0; i < n; i++)
  12.         scanf("%lld", &a[i]);
  13.     sort(a, a + n);
  14.     for(int i = 0; i < n; i++)
  15.         if(!ha[a[i]%HA] || !me[a[i]%ME] || !mo[a[i]%MO]){
  16.             ans++;
  17.             ha[a[i]*p%HA] = me[a[i]*p%ME] = mo[a[i]*p%MO] = 1;
  18.         }
  19.     printf("%lld\n", ans);
  20.     return 0;
  21. }

POJ 2226 Muddy Fields 泥泞牧场 | 二分图匹配

给出一个地图，其中'*'是泥地，'.'是草地，用一些宽度为1的木板覆盖所有泥地，不能覆盖草地，问最少需要多少木板。

题目很简单，在小行星那道题的基础上，将同一行中不连通的两部分拆成两行，列同理。

@ 又把int定义成了bool！！！

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <iostream>
  6. using namespace std;
  7. char mp[55][55];
  8. int x[55][55], y[55][55], xcnt, ycnt, user[1300];
  9. bool conn[1300][1300], used[1300];
  10. int r, c, ans;
  11. bool find(int i){
  12.     for(int j = 1; j <= ycnt; j++){
  13.         if(used[j] || !conn[i][j]) continue;
  14.         used[j] = 1;
  15.         if(!user[j] || find(user[j])){
  16.             user[j] = i;
  17.             return 1;
  18.         }
  19.     }
  20.     return 0;
  21. }
  22. void init(){
  23.     memset(user, 0, sizeof(user));
  24.     memset(conn, 0, sizeof(conn));
  25.     xcnt = ycnt = ans = 0;
  26. }
  27. int main(){
  28.     while(~scanf("%d%d", &r, &c)){
  29.         init();
  30.         for(int i = 1; i <= r; i++)
  31.             scanf("%s", mp[i] + 1);
  32.         //重新分配行列编号：x行y列 
  33.         for(int i = 1; i <= r; i++){
  34.             int connecting = 0;
  35.             for(int j = 1; j <= c; j++){
  36.                 if(mp[i][j] == '.') connecting = 0;
  37.                 else if(connecting) x[i][j] = xcnt;
  38.                 else connecting = 1, x[i][j] = ++xcnt;
  39.             }
  40.         }
  41.         for(int j = 1; j <= c; j++){
  42.             int connecting = 0;
  43.             for(int i = 1; i <= r; i++){
  44.                 if(mp[i][j] == '.') connecting = 0;
  45.                 else if(connecting) y[i][j] = ycnt;
  46.                 else connecting = 1, y[i][j] = ++ycnt;
  47.             }
  48.         }
  49.         //二分图连边 
  50.         for(int i = 1; i <= r; i++)
  51.             for(int j = 1; j <= c; j++)
  52.                 if(mp[i][j] == '*')
  53.                     conn[x[i][j]][y[i][j]] = 1;
  54.         //二分图匹配
  55.         for(int i = 1; i <= xcnt; i++){
  56.             memset(used, 0, sizeof(used));
  57.             ans += find(i); 
  58.         }
  59.         printf("%d\n", ans);
  60.     }
  61.     return 0;
  62. }

CodeVS 1163 访问艺术馆 | 树形DP

皮尔是一个出了名的盗画者，他经过数月的精心准备，打算到艺术馆盗画。艺术馆的结构，每条走廊要么分叉为二条走廊，要么通向一个展览室。皮尔知道每个展室里藏画的数量，并且他精确地测量了通过每条走廊的时间，由于经验老道，他拿下一副画需要5秒的时间。你的任务是设计一个程序，计算在警察赶来之前(警察到达时皮尔回到了入口也算)，他最多能偷到多少幅画。

由于这道题的神奇的输入方式，可以直接边DFS边计算，极大地缩短了代码。

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. const int MAXN = 105, MAXT = 605;
  5. int T, ncnt, dp[MAXN][MAXT];
  6. void dfs(int n){
  7.     int cost, value;
  8.     scanf("%d%d", &cost, &value);
  9.     cost <<= 1;
  10.     if(value)
  11.         for(int i = cost; i <= T; i++)
  12.             dp[n][i] = min(value, (i - cost) / 5);
  13.     else{
  14.         int ls, rs;
  15.         dfs(ls = ++ncnt);
  16.         dfs(rs = ++ncnt);
  17.         for(int i = cost; i <= T; i++)
  18.             for(int j = 0; j <= i - cost; j++)
  19.                 dp[n][i] = max(dp[n][i], dp[ls][j] + dp[rs][i - cost - j]);
  20.     }
  21. }
  22. int main(){
  23.     scanf("%d", &T);
  24.     dfs(++ncnt);
  25.     printf("%d\n", dp[1][T]);
  26.     return 0;
  27. }

随手记一下

上下界网络流教程
感人的 Tarjan LCA 插图教程

POJ 1144 网络 Network | Tarjan求割点

棵题：给出一个无向图，求割点[1]数量。

~ Tarjan 求割点的主要思路：对于一个u，枚举搜索树上的儿子v，如果其中一个low[v] >= dfn[u]（即v不能回溯到u以前的点），则去掉u后，u这棵子树就独立了，所以u是割点。

@ 注意：对于钦定的根节点，需要存在至少两个独立子树v，根节点才是割点。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  8. const int MAXN = 105, MAXE = 20005;
  9. int n, ans;
  10. int adj[MAXN], ecnt, go[MAXE], nxt[MAXE];
  11. int dfn[MAXN], low[MAXN], index;
  12. bool iscut[MAXN];
  13. void add(int u, int v){
  14.     go[++ecnt] = v;
  15.     nxt[ecnt] = adj[u];
  16.     adj[u] = ecnt;  
  17. }
  18. bool in(){ //辣鸡输入方式 
  19.     int u, v;
  20.     char c;
  21.     scanf("%d", &u);
  22.     if(u == 0) return 0;
  23.     do{
  24.         scanf("%d%c", &v, &c);
  25.         add(u, v);
  26.         add(v, u);
  27.     }while(c != '\n');
  28.     return 1;
  29. }
  30. void init(){
  31.     ecnt = ans = index = 0;
  32.     memset(adj, 0, sizeof(adj));
  33.     memset(iscut, 0, sizeof(iscut));
  34.     memset(dfn, 0, sizeof(dfn));
  35. }
  36. void tarjan(int u, int pre){
  37.     int v, child_cnt = 0;
  38.     dfn[u] = low[u] = ++index;
  39.     for(int e = adj[u]; e; e = nxt[e])
  40.         if(!dfn[v = go[e]]){
  41.             tarjan(v, u);
  42.             low[u] = min(low[u], low[v]);
  43.             if(low[v] >= dfn[u]){
  44.                 child_cnt++;
  45.                 iscut[u] = 1;
  46.             }
  47.         else if(v != pre)
  48.             low[u] = min(low[u], dfn[v]);
  49.     }
  50.     if(u == 1 && child_cnt == 1)
  51.         iscut[u] = 0;
  52. }
  53. int main(){
  54.     while(1){
  55.         scanf("%d", &n);
  56.         if(n == 0) break;
  57.         init();
  58.         while(in());
  59.         tarjan(1, 0);
  60.         for(int i = 1; i <= n; i++)
  61.             if(iscut[i]) ans++;
  62.         printf("%d\n", ans);
  63.     }
  64.     return 0;
  65. }

POJ 3177 多余的路 Redundant Paths | Tarjan求双联通分量/Tarjan求割边（桥）

无向图，求至少添加多少条边可使得任意两点间有至少两条路径？（不同路径的定义是两条路径上所有边都不同，但路径上可以有点相同。）

~ 这道题是求（边）双联通分量，即任意两点间有至少两条（没有重边的）路径的分量。可以利用Tarjan求割边的思路，像Tarjan求强联通分量一样求。求出双联通分量后，所有双联通分量构成了一棵树，只需加边使得树上每一个点都处于环中即可，所以将每对度为1的双联通分量连起来，共需要（度为1的双联通分量数 + 1）/2 条边。

@ 忘打一个"^1"

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int MAXE = 20005, MAXN = 5005;
  8. bool is_bridge[MAXE]; 
  9. int N, E, ans;
  10. int ecnt = 1, adj[MAXN], nxt[MAXE], go[MAXE];
  11. int dfn[MAXN], low[MAXN], index, cnt = 1, bel[MAXN], du[MAXN];
  12. int stk[MAXN], top;
  13. void add(int u, int v){
  14.     go[++ecnt] = v;
  15.     nxt[ecnt] = adj[u];
  16.     adj[u] = ecnt;  
  17. }
  18. void tarjan(int u, int pre){
  19.     int v;
  20.     stk[++top] = u;
  21.     dfn[u] = low[u] = ++index;
  22.     for(int e = adj[u]; e; e = nxt[e]){
  23.         if(!dfn[v = go[e]]){
  24.             tarjan(v, u);
  25.             low[u] = min(low[u], low[v]);
  26.             if(low[v] > dfn[u]){
  27.                 is_bridge[e] = is_bridge[e^1] = 1;
  28.                 cnt++;
  29.                 while(1){
  30.                     bel[stk[top]] = cnt;
  31.                     if(stk[top--] == v) break;
  32.                 }
  33.             }
  34.         }
  35.         else if(v != pre)
  36.             low[u] = min(low[u], dfn[v]);
  37.     }
  38. }
  39. int main(){
  40.     scanf("%d%d", &N, &E);
  41.     fill(bel, bel + N + 1, 1); //初始为1，作为根节点所在的双连通分量编号
  42.     for(int i = 1; i <= E; i++){
  43.         int u, v;
  44.         scanf("%d%d", &u, &v);
  45.         add(u, v);
  46.         add(v, u);
  47.     }
  48.     tarjan(1, 0);
  49.     for(int e = 2; e <= 2*E; e += 2){
  50.         if(is_bridge[e])
  51.             du[bel[go[e]]]++, du[bel[go[e^1]]]++;
  52.     for(int i = 1; i <= cnt; i++)
  53.         if(du[i] == 1) ans++;//求出只连着一条边的点的数目 
  54.     printf("%d\n", (ans + 1)/2);
  55.     return 0;
  56. }

CodeVS 3119 大整数开根 | 高精度

给出一个大整数()，求.

~ 昨天爆零了心情不好，写高精度自虐……

@
1. 要开到 , 是不够的……
2. 乘法的进位还是最后一起进的好。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <cctype>
  7. using namespace std;
  9. struct bigint {
  10.     int l, n[1005];
  11.     bigint():l(1){memset(n, 0, sizeof(n));}
  12.     bigint(int x):l(0){
  13.         memset(n, 0, sizeof(n));
  14.         while(x){
  15.             n[++l] = x % 10;
  16.             x /= 10;
  17.         }
  18.     }
  19.     void in(){
  20.         char s[1005];
  21.         scanf("%s", s);
  22.         l = strlen(s);
  23.         for(int i = 1; i <= l; i++)
  24.             n[i] = s[l - i] - '0';
  25.     }
  26.     void out(){
  27.         for(int i = l; i; i--)
  28.             printf("%d", n[i]);
  29.         cout << endl;   
  30.     }
  31.     bool operator < (bigint b) const {
  32.         if(l != b.l) return l < b.l;
  33.         for(int i = l; i; i--)
  34.             if(n[i] != b.n[i])
  35.                 return n[i] < b.n[i];
  36.         return 0;
  37.     }
  38.     bool operator > (bigint b) const{
  39.         if(l != b.l) return l > b.l;
  40.         for(int i = l; i; i--)
  41.             if(n[i] != b.n[i])
  42.                 return n[i] > b.n[i];
  43.         return 0;
  44.     }
  45.     bigint operator + (bigint b) {
  46.         bigint c;
  47.         c.l = max(l, b.l) + 1;
  48.         for(int i = 1; i <= c.l; i++){
  49.             c.n[i] += n[i] + b.n[i];
  50.             c.n[i + 1] += c.n[i] / 10;
  51.             c.n[i] %= 10;
  52.         }
  53.         if(!c.n[c.l]) c.l--;
  54.         return c;
  55.     }
  56.     bigint operator * (bigint b) {
  57.         bigint c;
  58.         c.l = l + b.l;
  59.         for(int i = 1; i <= l; i++)
  60.             for(int j = 1; j <= b.l; j++){
  61.                 c.n[i + j - 1] += n[i] * b.n[j];
  62.             }
  63.         int last = 0;
  64.         for(int i = 1; i <= c.l; i++){
  65.             c.n[i] += last;
  66.             last = c.n[i] / 10;
  67.             c.n[i] %= 10;
  68.         }
  69.         if(!c.n[c.l]) c.l--;
  70.         return c;
  71.     }
  72.     void haf(){
  73.         int last = 0;
  74.         for(int i = l; i; i--){
  75.             n[i] += last * 10;
  76.             last = n[i] & 1;
  77.             n[i] >>= 1;
  78.         }
  79.         while(!n[l]) l--;
  80.     }
  81.     void operator -- (int why_is_there_a_variable) {
  82.         n[1]--;
  83.         int x = 1;
  84.         while(n[x] < 0) n[x] += 10, n[++x]--;
  85.         while(!n[l]) l--;
  86.     }
  87. };
  89. bigint tar, l, r, mid, one(1);
  91. int main(){
  92.     tar.in();
  93.     r.l = 500;
  94.     r.n[500] = 1;
  95.     while(l < r){
  96.         mid = l + r + one;
  97.         mid.haf();
  98.         bigint tp = mid * mid;
  99.         if(tp > tar){
  100.             r = mid;
  101.             r--;
  102.         }
  103.         else l = mid;
  104.     }
  105.     l.out();
  106.     return 0;
  107. }

CodeVS 1001 舒适的路线 | 并查集

Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。
Z小镇附近共有N(1<N≤500)个景点（编号为1,2,3,…,N），这些景点被M（0<M≤5000）条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服，因此大家从一个景点前往另一个景点的时候，都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。

输入描述
第一行包含两个正整数，N和M。
接下来的M行每行包含三个正整数：x，y和v（1≤x,y≤N） 最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。

输出描述
如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。

数据范围
N(1<N≤500), M（0<M≤5000）, Vi在int范围内

~ 我好菜啊……这道题一开始理解错了……
实际上，只需要按边枚举，先把边按v从小到大排序，枚举v最小的边，往后的每一条边都取，一边取一边在并查集中合并边的两个端点，直到起点和终点在同一集合中。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. const int MAXN = 505, MAXM = 5005;
  8. int N, M, s, t, u[MAXM], v[MAXM], w[MAXM];
  9. int fa[MAXN], per[MAXM];
  10. int ansx = 0x3f3f3f3f, ansy = 1;
  11. bool ok = 0;
  12. int findfa(int x){ return x == fa[x] ? x : fa[x] = findfa(fa[x]); }
  13. bool cmp(int a, int b){ return w[a] < w[b];}
  14. int gcd(int a, int b){ return b ? gcd(b, a%b) : a; }
  15. int main(){
  16.     scanf("%d%d", &N, &M);
  17.     for(int i = 1; i <= M; i++)
  18.         scanf("%d%d%d", &u[i], &v[i], &w[i]), per[i] = i;
  19.     scanf("%d%d", &s, &t);
  20.     sort(per + 1, per + M + 1, cmp);
  21.     for(int i = 1; i <= M; i++){
  22.         for(int j = 1; j <= N; j++) fa[j] = j;
  23.         int x, y = w[per[i]];
  24.         for(int j = i; j <= M; j++){
  25.             fa[findfa(u[per[j]])] = findfa(v[per[j]]);
  26.             if(findfa(s) == findfa(t)){
  27.                 x = w[per[j]];
  28.                 if((double)x/y < (double) ansx/ansy)
  29.                     ok = 1, ansx = x, ansy = y;
  30.                 break;
  31.             }
  32.         }
  33.     }
  34.     int g = gcd(ansx, ansy);
  35.     ansx /= g, ansy /= g;
  36.     if(!ok) printf("IMPOSSIBLE\n");
  37.     else if(ansy == 1) printf("%d\n", ansx);
  38.     else printf("%d/%d\n", ansx, ansy);
  39.     return 0;
  40. }

CodeVS 1069 关押罪犯 | 并查集

n个罪犯中，有些罪犯两两之间有一定仇恨值，如果两个有仇恨值的罪犯关押在同一所监狱中，就会产生和仇恨值大小相等的矛盾。将罪犯分配到两所监狱中，使最大仇恨值最小，输出最小的最大仇恨值。

【数据范围】
对于30%的数据有N≤ 15。
对于70%的数据有N≤ 2000，M≤ 50000。
对于100%的数据有N≤ 20000，M≤ 100000。\

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. const int MAXN = 20005, MAXM = 100005;
  5. int n, m, ans;
  6. int fa[2*MAXN], u[MAXM], v[MAXM], w[MAXM], per[MAXM];
  7. bool cmp(int a, int b){
  8.     return w[a] > w[b];
  9. }
  10. int findfa(int x){
  11.     return fa[x] == x ? x : fa[x] = findfa(fa[x]);
  12. }
  13. int main(){
  14.     scanf("%d%d", &n, &m);
  15.     for(int i = 1; i <= m; i++)
  16.         scanf("%d%d%d", &u[i], &v[i], &w[i]), per[i] = i;
  17.     for(int i = 1; i <= 2*n; i++)
  18.         fa[i] = i;
  19.     sort(per + 1, per + m + 1, cmp);
  20.     for(int i = 1; i <= m; i++){
  21.         int uu = u[per[i]], vv = v[per[i]], ww = w[per[i]];
  22.         if(findfa(uu) == findfa(vv)){
  23.             printf("%d\n", ww);
  24.             return 0;
  25.         }
  26.         fa[findfa(uu + n)] = findfa(vv);
  27.         fa[findfa(vv + n)] = findfa(uu);
  28.     }
  29.     printf("0\n");
  30.     return 0;
  31. }

CodeVS 1052 地鼠游戏 | 堆

题面懒得粘……
（一眼秒23333）

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <queue>
  7. using namespace std;
  8. const int MAXN = 105;
  9. int n, maxt, pos = 1, ans;
  10. struct mouse{
  11.     int t, w;
  12.     bool operator < (mouse b) const{
  13.         return w < b.w;
  14.     }
  15. }m[MAXN];
  16. priority_queue <mouse> e;
  17. bool cmp (mouse a, mouse b) {
  18.     return a.t > b.t;
  19. }
  20. int main(){
  21.     scanf("%d", &n);
  22.     for(int i = 1; i <= n; i++)
  23.         scanf("%d", &m[i].t), maxt = max(maxt, m[i].t);
  24.     for(int i = 1; i <= n; i++)
  25.         scanf("%d", &m[i].w);
  26.     sort(m + 1, m + n + 1, cmp);
  27.     for(int i = maxt; i; i--){
  28.          while(pos <= n && m[pos].t >= i) e.push(m[pos++]);
  29.          if(e.empty()) continue;
  30.          ans += e.top().w;
  31.          e.pop();
  32.     }
  33.     printf("%d\n", ans);
  34.     return 0;
  35. }

CodeVS 1245 最小的N个和 | 二分（堆？）

有两个长度为 N 的序列 A 和 B，在 A 和 B 中各任取一个数可以得到 N^2 个和，求这N^2 个和中最小的 N个。

一眼秒（用二分，没用堆什么的），然而……

@ 二分查找检验的时候，达到答案(mid)就要退出循环了, 我居然忘了退出……

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. const int MAXN = 100005;
  8. typedef long long ll;
  9. ll n, a[MAXN], b[MAXN], amax, bmax, l, r, c[3*MAXN], cnt;
  10. int main(){
  11.     scanf("%lld", &n);
  12.     for(int i = 1; i <= n; i++)
  13.         scanf("%lld", &a[i]), amax = max(amax, a[i]);
  14.     for(int i = 1; i <= n; i++)
  15.         scanf("%lld", &b[i]), bmax = max(bmax, b[i]);
  16.     sort(a + 1, a + n + 1);
  17.     sort(b + 1, b + n + 1);
  18.     l = 0, r = amax + bmax;
  19.     while(l < r){
  20.         ll mid = (l + r) >> 1, ans = 0;
  21.         for(int i = 1; i <= n; i++){
  22.             for(int j = 1; j <= n; j++){
  23.                 if(a[i] + b[j] > mid || ans > n) break;
  24.                 ans++;
  25.             }
  26.             if(a[i] + b[1] > mid || ans > n) break;
  27.         }
  28.         if(ans >= n) r = mid;
  29.         else l = mid + 1;
  30.     }
  31.     for(int i = 1; i <= n; i++){
  32.         for(int j = 1; j <= n; j++){
  33.             if(a[i] + b[j] >= l) break;
  34.             c[++cnt] = a[i] + b[j];
  35.         }
  36.         if(a[i] + b[1] >= l) break;
  37.     }
  38.     sort(c + 1, c + cnt + 1);
  39.     for(int i = 1; i <= cnt; i++)
  40.         printf("%lld ", c[i]);
  41.     for(int i = cnt + 1; i <= n; i++)
  42.         printf("%lld ", l);
  43.     return 0;
  44. }

CodeVS 1079 回家 | Floyd 最短路

棵题，但是输入方式非常不人性化……

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <cctype>
  7. using namespace std;
  8. const int INF = 0x3f3f3f3f;
  9. int m, num[128], ncnt, dis[60][60], Z;
  10. bool cow[60];
  11. int main(){
  12.     for(int i = 1; i <= 52; i++)
  13.         for(int j = 1; j <= 52; j++)
  14.             dis[i][j] = i == j ? 0 : INF;
  15.     scanf("%d", &m);
  16.     for(int i = 1; i <= m; i++){
  17.         char uc[2], vc[2];
  18.         int u, v, w;
  19.         scanf("%s%s%d", uc, vc, &w);
  20.         u = num[uc[0]] ? num[uc[0]] : num[uc[0]] = ++ncnt;
  21.         if(uc[0] == 'Z') Z = u;
  22.         else if(isupper(uc[0])) cow[u] = 1;
  23.         v = num[vc[0]] ? num[vc[0]] : num[vc[0]] = ++ncnt;
  24.         if(vc[0] == 'Z') Z = v;
  25.         else if(isupper(vc[0])) cow[v] = 1;
  26.         dis[u][v] = dis[v][u] = min(dis[u][v], w);
  27.     }
  28.     for(int k = 1; k <= ncnt; k++)
  29.         for(int i = 1; i <= ncnt; i++)
  30.             for(int j = 1; j <= ncnt; j++)
  31.                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  32.     int minn = INF, ans;
  33.     for(int i = 1; i <= ncnt; i++)
  34.         if(cow[i] && dis[i][Z] < minn)
  35.             minn = dis[i][Z], ans = i;
  36.     char ansc;
  37.     for(char i = 'A'; i <= 'z'; i++)
  38.         if(num[i] == ans) ansc = i;
  39.     printf("%c %d\n", ansc, minn);
  40.     return 0;
  41. }

随手记一下（二）

十个矩阵乘法

BZOJ 1036 树的统计 | 树链剖分棵题

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作：
I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v:询问从点u到点v的路径上的节点的最大权值
III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身

输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

树链剖分详细笔记：传送门

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <cctype>
  7. using namespace std;
  8. int read(){
  9.     int sgn = 1;
  10.     char ch;
  11.     while(!isdigit(ch = getchar()))
  12.         if(ch == '-') sgn = -1;
  13.     int res = ch - '0';
  14.     while(isdigit(ch = getchar()))
  15.         res = res * 10 + ch - '0';
  16.     return sgn * res;
  17. }
  18. const int N = 30005, INF = 0x3f3f3f3f;
  19. int n, Q, val[N];
  20. int ecnt, adj[N], nxt[2*N], go[2*N];
  21. int tot, fa[N], dep[N], top[N], sze[N], son[N], pos[N], idx[N];
  22. int SUM[4*N], MAX[4*N];
  23. void add(int u, int v){
  24.     go[++ecnt] = v; nxt[ecnt] = adj[u]; adj[u] = ecnt;
  25.     go[++ecnt] = u; nxt[ecnt] = adj[v]; adj[v] = ecnt;
  26. }
  27. void seg_build(int k, int l, int r){
  28.     if(l == r) return (void)(SUM[k] = MAX[k] = val[idx[l]]);
  29.     int mid = (l + r) >> 1;
  30.     seg_build(k << 1, l, mid); seg_build(k << 1 | 1, mid + 1, r);
  31.     SUM[k] = SUM[k << 1] + SUM[k << 1 | 1];
  32.     MAX[k] = max(MAX[k << 1], MAX[k << 1 | 1]);
  33. }
  34. void seg_change(int k, int l, int r, int p, int x){
  35.     if(l == r) return (void)(SUM[k] = MAX[k] = x);
  36.     int mid = (l + r) >> 1;
  37.     if(p <= mid) seg_change(k << 1, l, mid, p, x);
  38.     else seg_change(k << 1 | 1, mid + 1, r, p, x);
  39.     SUM[k] = SUM[k << 1] + SUM[k << 1 | 1];
  40.     MAX[k] = max(MAX[k << 1], MAX[k << 1 | 1]); 
  41. }
  42. int seg_sum(int k, int l, int r, int ql, int qr){
  43.     if(l >= ql && r <= qr) return SUM[k];
  44.     int mid = (l + r) >> 1, res = 0;
  45.     if(ql <= mid) res += seg_sum(k << 1, l, mid, ql, qr);
  46.     if(qr > mid) res += seg_sum(k << 1 | 1, mid + 1, r, ql, qr);
  47.     return res;
  48. }
  49. int seg_max(int k, int l, int r, int ql, int qr){
  50.     if(l >= ql && r <= qr) return MAX[k];
  51.     int mid = (l + r) >> 1, res = -INF;
  52.     if(ql <= mid) res = max(res, seg_max(k << 1, l, mid, ql, qr));
  53.     if(qr > mid) res = max(res, seg_max(k << 1 | 1, mid + 1, r, ql, qr));
  54.     return res;
  55. }
  56. void init(){
  57.     int q[n], r, u, v;
  58.     dep[1] = 1, q[r = 0] = 1;
  59.     for(int l = 0; l <= r; l++){
  60.         sze[u = q[l]] = 1;
  61.         for(int e = adj[u]; e; e = nxt[e]){
  62.             if(dep[v = go[e]]) continue;
  63.             dep[v] = dep[u] + 1, fa[v] = u;
  64.             q[++r] = v;
  65.         }
  66.     }
  67.     for(int l = r; l >= 0; l--){
  68.         sze[u = fa[q[l]]] += sze[v = q[l]];
  69.         if(sze[v] > sze[son[u]]) son[u] = v;
  70.     }
  71.     for(int l = 0; l <= r; l++){
  72.         if(top[u = q[l]]) continue;
  73.         for(int v = u; v; v = son[v])
  74.             idx[pos[v] = ++tot] = v, top[v] = u; 
  75.     }
  76.     seg_build(1, 1, n);
  77. }
  78. int path_sum(int u, int v){
  79.     if(top[u] != top[v]){
  80.         if(dep[top[u]] > dep[top[v]]) swap(u, v);
  81.         return seg_sum(1, 1, n, pos[top[v]], pos[v]) + path_sum(u, fa[top[v]]);
  82.     }
  83.     if(dep[u] > dep[v]) swap(u, v);
  84.     return seg_sum(1, 1, n, pos[u], pos[v]);
  85. }
  86. int path_max(int u, int v){
  87.     if(top[u] != top[v]){
  88.         if(dep[top[u]] > dep[top[v]]) swap(u, v); 
  89.         return max(seg_max(1, 1, n, pos[top[v]], pos[v]), path_max(u, fa[top[v]]));
  90.     }
  91.     if(dep[u] > dep[v]) swap(u, v); 
  92.     return seg_max(1, 1, n, pos[u], pos[v]);
  93. }
  94. int main(){
  95.     n = read();
  96.     for(int i = 1; i < n; i++)
  97.         add(read(), read());
  98.     for(int i = 1; i <= n; i++)
  99.         val[i] = read();
  100.     init();
  101.     Q = read();
  102.     int u, v;
  103.     char op;
  104.     while(Q--){
  105.         while((op = getchar()) != 'C' && op != 'Q');
  106.         if(op == 'Q') op = getchar();
  107.         u = read(), v = read();
  108.         if(op == 'C') seg_change(1, 1, n, pos[u], v);
  109.         else if(op == 'S') printf("%d\n", path_sum(u, v));
  110.         else if(op == 'M') printf("%d\n", path_max(u, v));
  111.     }
  112.     return 0;
  113. }

Vijos 1049 送给圣诞夜的礼品 | 矩阵乘法

有一个编号为 1~n 的序列，提供 m 个操作，每个操作是一个序列a，表示将当前序列中的a[i]个数放在第i个位置上。从头至尾循环执行这m个操作，直到共执行了k个操作。求最后得到的序列。

~ 矩阵乘法。

0 0 1 0       1       3
1 0 0 0   *   2   =   1
0 0 0 1       3       4
0 1 0 0       4       2

首先把m个操作乘成一个矩阵，然后用快速幂求出它的 k/m 次方，再乘上剩下的前 k%m 个矩阵，得到的就是总的操作，最后再乘上 1~n 竖排排列的一个原始矩阵，得到的就是最终结果。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int MAXN = 105;
  8. int n, m, k;
  9. struct matrix {
  10.     int g[MAXN][MAXN];
  11.     matrix(){
  12.         memset(g, 0, sizeof(g));
  13.     }
  14.     matrix operator * (matrix b) {
  15.         matrix c;
  16.         for(int k = 1; k <= n; k++)
  17.             for(int i = 1; i <= n; i++)
  18.                 for(int j = 1; j <= n; j++)
  19.                     c.g[i][j] += g[i][k] * b.g[k][j];
  20.         return c;
  21.     }
  22. } one, op, tp, rest, ans;
  23. void init(){
  24.     for(int i = 1; i <= n; i++)
  25.         one.g[i][i] = 1;
  26.     op = rest = one;
  27.     for(int i = 1; i <= n; i++)
  28.         ans.g[i][1] = i;
  29. }
  30. matrix qpow(matrix a, int x){
  31.     if(x == 0) return one;
  32.     matrix t = qpow(a, x >> 1);
  33.     if(x & 1) return t * t * a;
  34.     return t * t;
  35. }
  36. int main(){
  37.     scanf("%d%d%d", &n, &m, &k);
  38.     init();
  39.     for(int i = 1; i <= m; i++){
  40.         memset(tp.g, 0, sizeof(tp.g));
  41.         int v;
  42.         for(int j = 1; j <= n; j++){
  43.             scanf("%d", &v);
  44.             tp.g[j][v] = 1;
  45.         }
  46.         op = tp * op;
  47.         if(i <= k % m)
  48.             rest = tp * rest;
  49.     }
  50.     op = qpow(op, k / m);
  51.     ans = rest * op * ans;
  52.     for(int i = 1; i <= n; i++){
  53.         if(i > 1) printf(" ");
  54.         printf("%d", ans.g[i][1]);
  55.     }
  56.     printf("\n");
  57.     return 0;
  58. }

@ 矩阵乘法注意顺序。

Vijos 1067 Warcraft III 守望者的烦恼 | 矩阵乘法

有一排格子，一开始在第 0 个格子，每次可以往右走 1~k 步，最后都要到达第 n 个格子。问有多少种方案？

~ 类似斐波那契！

首先我们知道状态转移方程：

构造一个这样的矩阵：

0 1 0 0 0       dp[i]       dp[i+1]
0 0 1 0 0       dp[i+1]     dp[i+2]
0 0 0 1 0   *   dp[i+2]  =  dp[i+3]
0 0 0 0 1       dp[i+3]     dp[i+4]
1 1 1 1 1       dp[i+4]     dp[i+5]

求出左边那个矩阵的 m 次方就好了！

事实上，许多递推式都可以写成矩阵乘法，例如:

……的矩阵可以写成：

0 1 0 0
0 0 1 0
0 0 0 1
1 3 5 -2

这些矩阵共同特点是右上角 (n-1)*(n-1) 的小矩阵的主对角线为 1，最后一行为递推式中对应的系数。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int MO = 7777777, MAXN = 12;
  9. int n, m; //n是技能等级, m是监狱个数 
  10. struct matrix {
  11.     ll g[MAXN][MAXN];
  12.     matrix(){
  13.         memset(g, 0, sizeof(g));
  14.     }
  15.     matrix operator * (matrix b) {
  16.         matrix c;
  17.         for(int k = 1; k <= n; k++)
  18.             for(int i = 1; i <= n; i++)
  19.                 for(int j = 1; j <= n; j++)
  20.                     c.g[i][j] = (c.g[i][j] + g[i][k] * b.g[k][j] % MO) % MO;
  21.         return c;
  22.     }
  23. } op, ans, one;
  24. matrix qpow(matrix a, int x){
  25.     if(x == 0) return one;
  26.     matrix t = qpow(a, x >> 1);
  27.     if(x & 1) return t * t * a;
  28.     return t * t;
  29. }
  30. void init(){
  31.     for(int i = 1; i <= n; i++)
  32.         one.g[i][i] = 1;
  33.     for(int i = 1; i < n; i++)
  34.         op.g[i][i + 1] = 1;
  35.     for(int i = 1; i <= n; i++)
  36.         op.g[n][i] = 1;
  37.     ans.g[n][1] = 1;
  38. }
  39. int main(){
  40.     scanf("%d%d", &n, &m);
  41.     init();
  42.     op = qpow(op, m);
  43.     ans = op * ans;
  44.     printf("%lld\n", ans.g[n][1]); 
  45.     return 0;
  46. }

Vijos 1603 迷宫 | 矩阵乘法

水题：有向图，求两点之间恰好走k条边能到达的路径数目。

~
一个结论：k条边路径数目 = 邻接矩阵的k次方中对应的路径数目

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int MAXN = 55;
  9. int n, s, f, m, p;
  10. struct matrix {
  11.     ll g[MAXN][MAXN];
  12.     matrix(){
  13.         memset(g, 0, sizeof(g));
  14.     }
  15.     matrix operator * (matrix b) {
  16.         matrix c;
  17.         for(int k = 1; k <= n; k++)
  18.             for(int i = 1; i <= n; i++)
  19.                 for(int j = 1; j <= n; j++)
  20.                     c.g[i][j] = (c.g[i][j] + g[i][k] * b.g[k][j] % p) % p;
  21.         return c;
  22.     }
  23. } one, ans;
  24. void init(){
  25.     for(int i = 1; i <= n; i++)
  26.         one.g[i][i] = 1;
  27. }
  28. matrix qpow(matrix a, int x){
  29.     matrix ans = one;
  30.     while(x){
  31.         if(x & 1) ans = ans * a;
  32.         a = a * a;
  33.         x >>= 1;
  34.     }
  35.     return ans;
  36. }
  37. int main(){
  38.     scanf("%d", &n);
  39.     init();
  40.     for(int i = 1; i <= n; i++)
  41.         for(int j = 1; j <= n; j++)
  42.             scanf("%lld", &ans.g[i][j]);
  43.     scanf("%d%d%d%d", &m, &s, &f, &p);
  44.     ans = qpow(ans, m);
  45.     printf("%lld\n", ans.g[s][f]);
  46.     return 0;
  47. }

Vijos 1194 多米诺 Domino | 矩阵乘法

一个长 高 棋盘 ()，用 的多米诺骨牌完全覆盖，问有多少种方案。

~
用二进制表示某一列每个方格被覆盖与否的情况，然后考虑用各种方式填满这一列时，下一列的情况是什么。注意：禁止在当前列竖放多米诺骨牌，因为会和这一列的另一种情况重复，但下一列可以竖放。

例如下图，中间那列是“当前列”，当前列以左已经全部填满，当前列参差不齐，当前列以右还没填。：

  1. 100           111      111
  2. 100     ->    111  or  111
  3. 110           110      111
  4. 110           110      111

将所有能转换的两种状态之间连上边（如上图 0011 可以转换为 1100 或1111），得到了一个有向图。

在这个有向图上从 1111 出发，到 1111 结束，走 n 步，方案数就是覆盖棋盘的方案数。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. typedef long long ll;
  8. int n, m, p, M;
  9. const int WIDTH = 34;
  10. struct matrix {
  11.     ll g[WIDTH][WIDTH];
  12.     matrix(){
  13.         memset(g, 0, sizeof(g));
  14.     }
  15.     matrix(int x){
  16.         memset(g, 0, sizeof(g));
  17.         for(int i = 0; i < M; i++)
  18.             g[i][i] = 1;
  19.     }
  20.     matrix operator * (matrix b){
  21.         matrix c;
  22.         for(int k = 0; k < M; k++)
  23.             for(int i = 0; i < M; i++)
  24.                 for(int j = 0; j < M; j++)
  25.                     c.g[i][j] = (c.g[i][j] + g[i][k] * b.g[k][j] % p) % p;
  26.         return c;
  27.     }
  28. } mp;
  29. matrix qpow(matrix a, int x){
  30.     matrix ans(1);
  31.     while(x){
  32.         if(x & 1) ans = ans * a;
  33.         a = a * a;
  34.         x >>= 1; 
  35.     }
  36.     return ans;
  37. }
  38. // Matrix67 的神奇位运算我找不到了 -_-|||
  39. //自己编了一个十分naive的暴力判断，也能用 
  40. bool getbit(int num, int x){
  41.     return num & (1 << x);
  42. }
  43. void init(){
  44.     for(int i = 0; i < M; i++)
  45.         for(int j = 0; j < M; j++){
  46.             int ok = 1, rem = j;
  47.             for(int k = 0; k < m; k++){
  48.                 if(!getbit(i, k)){//如果母串该位为0 
  49.                     if(!getbit(rem, k)) ok = 0;
  50.                     //则子串该位必为1 
  51.                     else rem -= (1 << k);
  52.                     //去掉这些横放造成的突起 
  53.                 }
  54.             }
  55.         //去掉横放突起后，剩下的都是竖放的 
  56.             int cnt = 0;
  57.             for(int k = 0; k < m; k++){
  58.                 if(getbit(rem, k)) cnt++;
  59.                 //数数竖放挨在一起的有多少 
  60.                 if(!getbit(rem, k)){
  61.                     if(cnt & 1) ok = 0;
  62.                     cnt = 0;
  63.                 }
  64.             }
  65.             if(cnt & 1) ok = 0;
  66.             if(ok) mp.g[i][j] = 1;
  67.         }
  68. }
  69. int main(){
  70.     scanf("%d%d%d", &n, &m, &p);
  71.     M = 1 << m ;
  72.     init();
  73.     mp = qpow(mp, n);
  74.     printf("%lld\n", mp.g[M - 1][M - 1]);
  75.     return 0;
  76. }

51nod 1582 n叉树 | DP 矩阵乘法

有一棵n叉树，深度是无限的，每个结点有n个儿子。从左到右编号为1到n号儿子，第i号儿子离该结点的距离是di。现在要统计一下距离根结点不超过x的结点有多少个。

首先状态转移方程是显然的/*然鹅我一开始写错了*/
dp[i]表示到根节点距离不超过x的节点个数，cnt[j]输入数据中的表示长度为j的边的个数：

然后可以构造一个类似下面这样的矩阵：

1 0 0 0 0     1         1
0 0 1 0 0     dp[i-4]   dp[i-3]
0 0 0 1 0  *  dp[i-3] = dp[i-2]
0 0 0 0 1     dp[i-2]   dp[i-1]
1 d c b a     dp[i-1]   dp[i]

其中 abcd 分别为 cnt[1], cnt[2], cnt[3], cnt[4]。
2~4行右侧3*3正方形是单位矩阵。
第一行第一列的1保证了所得结果的第一行永远是1。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  8. typedef long long ll;
  9. const int N = 101, P = 1000000007;
  10. int n, x;
  11. struct matrix {
  12.     ll g[N+2][N+2];
  13.     matrix(){
  14.         memset(g, 0, sizeof(g));
  15.     }
  16.     matrix(int k){
  17.         memset(g, 0, sizeof(g));
  18.         for(int i = 0; i <= N; i++)
  19.             g[i][i] = 1;
  20.     }
  21.     matrix operator * (matrix b){
  22.         matrix c;
  23.         for(int k = 0; k <= N; k++)
  24.             for(int i = 0; i <= N; i++)
  25.                 for(int j = 0; j <= N; j++)
  26.                     c.g[i][j] = (c.g[i][j] + g[i][k] * b.g[k][j] % P) % P;
  27.         return c;
  28.     }
  29. } op, ori;
  31. matrix qpow(matrix a, int x){
  32.     matrix ans(1);
  33.     while(x){
  34.         if(x & 1) ans = ans * a;
  35.         a = a * a;
  36.         x >>= 1;
  37.     }
  38.     return ans;
  39. }
  41. int main(){
  42.     scanf("%d%d", &n, &x);
  43.     for(int i = 1; i <= n; i++){
  44.         int t;
  45.         scanf("%d", &t);
  46.         op.g[N][N - t + 1]++;
  47.     }
  48.     op.g[0][0] = op.g[N][0] = 1;
  49.     for(int i = 1; i < N; i++)
  50.         op.g[i][i + 1] = 1;
  51.     ori.g[N][0] = ori.g[0][0] = 1;
  52.     op = qpow(op, x);
  53.     ori = op * ori;
  54.     printf("%lld\n", ori.g[N][0]);
  55.     return 0;
  56. }

51nod 1298基础题：圆与三角形 | 解析几何

给出平面内一个圆与一个三角形，问它们是否相交（“相交”指边相交）。

呜呼噫嘻……
首先可以发现，三角形的三个顶点都在圆内时必然不相交，有内有外时必然相交。
三个顶点都在圆外时要求圆心到线段的距离。
怎么求？
设圆心为C，线段两端点为A和B，那么∠CAB和∠CBA都是锐角时，AB边上的高（即点到直线距离）在线段AB上，用点到直线距离求，否则取两端点圆心距离较小者。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  8. const double eps = 0.000000001;
  9. int T;
  10. double xc, yc, r, xp[4], yp[4], k, b, dis;
  11. //x_circle; x_point; kx + y + b = 0
  12. double point_dis_square(double xa, double ya){
  13.     return (xa - xc)*(xa - xc) + (ya - yc)*(ya - yc);
  14. }
  15. bool calc_line(double xa, double ya, double xb, double yb){
  16.     //求一个形如 kx + y + b的解析式 
  17.     if(abs(xa - xb) <= eps) return 0;//没有k 
  18.     k = -(ya - yb)/(xa - xb);
  19.     b = (xb*ya - xa*yb)/(xa - xb);
  20.     return 1;//有k 
  21. }
  22. double calc_dis(double xa, double ya, double xb, double yb){
  23.     double xe = xc - xa, ye = yc - ya, xf = xb - xa, yf = yb - ya, xg = xb - xc, yg = yb - yc;
  24.     // 求点乘判断钝角（后悔自己怎么没写结构体……） 
  25.     if(xe*xf + ye*yf > 0 && xf*xg + yf*yg > 0){//如果∠CAB和∠CBA都为锐角 
  26.         if(calc_line(xa, ya, xb, yb))//如果斜率存在，可求解析式 
  27.             return abs(k*xc + yc + b) / sqrt(k*k + 1);
  28.         else
  29.             return abs(xa - xc);//斜率不存在，直接求x轴距离 
  30.     }
  31.     return min(sqrt(point_dis_square(xa, ya)), sqrt(point_dis_square(xb, yb)));
  32.     //如果发现了钝角，则取线段两端点与原点距离中更小的。 
  33. }
  35. int main(){
  36.     scanf("%d", &T);
  37.     while(T--){
  38.         scanf("%lf%lf%lf", &xc, &yc, &r);
  39.         for(int i = 1; i <= 3; i++)
  40.             scanf("%lf%lf", &xp[i], &yp[i]);
  41.         bool all_out = 1, all_in = 1;
  42.         for(int i = 1; i <= 3; i++){
  43.             if(abs(point_dis_square(xp[i], yp[i]) - r*r) <= eps)
  44.                 all_out = all_in = 0;
  45.             else if(point_dis_square(xp[i], yp[i]) > r*r) all_in = 0;
  46.             else all_out = 0;
  47.         }
  48.         if(!all_out){//如果点不都在外面 
  49.             if(all_in) printf("No\n");//都在里面 
  50.             else printf("Yes\n");//有里有外 
  51.             continue;
  52.         }
  53.         bool got_ans = 0;
  54.         for(int i = 1; i <= 3; i++){
  55.             dis = calc_dis(xp[i], yp[i], xp[i%3+1], yp[i%3+1]);
  56.             if(dis <= r){ //线段与圆相切或相交 
  57.                 printf("Yes\n");
  58.                 got_ans = 1;
  59.                 break;
  60.             }
  61.         }
  62.         if(!got_ans) printf("No\n");
  63.     }
  64.     return 0;
  65. }

51nod 1020 逆序排列 | DP 优化

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。

1-n的全排列中，逆序数最小为0（正序），最大为n*(n-1) / 2（倒序）
给出2个数n和k，求1-n的全排列中，逆序数为k的排列有多少种？
例如：n = 4 k = 3。

1 2 3 4的排列中逆序为3的共有6个，分别是：
1 4 3 2
2 3 4 1
2 4 1 3
3 1 4 2
3 2 1 4
4 1 2 3

由于逆序排列的数量非常大，因此只需计算并输出该数 Mod 10^9 + 7的结果就可以了。

Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行2个数n，k。中间用空格分隔。（2 <= n <= 1000, 0 <= k <= 20000)
Output
共T行，对应逆序排列的数量 Mod (10^9 + 7)
Input示例
1
4 3
Output示例
6

~
dp[i][j] 表示 1~i 的全排列中逆序对为 j 的数目。
考虑第 i 个数插在原先的排列中，可以插在 0~(i-1) 号后面，分别新形成 0~(i-1) 个逆序对，于是：

但是这个复杂度炒鸡高，于是我们可以求前缀和，也可以再求出 dp[i][j-1]:

两式相减：

移项： 

  1. #include <cstring>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int P = 1000000007, N = 1000, K = 20000;
  8. int dp[N+3][K+3], T, n, k;
  9. int main(){
  10.     dp[0][0] = 1;
  11.     for(int i = 1; i <= N; i++){
  12.         dp[i][0] = 1;
  13.         for(int j = 1; j < i; j++)
  14.             dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % P;
  15.         for(int j = i; j <= K; j++)
  16.             dp[i][j] = ((dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i]) % P + P) % P;
  17.     }
  18.     scanf("%d", &T);
  19.     while(T--){
  20.         scanf("%d%d", &n, &k);
  21.         printf("%d\n", dp[n][k]);
  22.     }
  23.     return 0;
  24. }

51nod 1134 最长上升子序列 | @记得初始化 -INF！

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. const int N = 50005;
  5. int s[N], cnt, n, tmp;
  6. int main(){
  7.     scanf("%d", &n);
  8.     s[0] = -0x3f3f3f3f;
  9.     for(int i = 1; i <= n; i++){
  10.         scanf("%d", &tmp);
  11.         if(tmp > s[cnt]) s[++cnt] = tmp;
  12.         else{
  13.             int pos = upper_bound(s + 1, s + cnt + 1, tmp) - s;
  14.             s[pos] = tmp;
  15.         }
  16.     }
  17.     printf("%d\n", cnt);
  18.     return 0;
  19. }

51nod 1055 最长等差数列

给出一些数，求用这些数组成的最长等差序列的长度。

（企鹅学长最喜欢的） SCaffrey 学长 分享的题解

题解主要内容是：

dp[i][j] 表示以 i、j 号元素开头的最长等差数列长度。
自右向左枚举每个数 j, 在左、右分别找到 i 和 k 使 {i, j, k} 为等差数列，若找到，则 dp[i][j] = dp[j][k] + 1。

@ 虽然迫于空间限制必须开short，但是输入的那些数必须开int啊……

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int N = 10003;
  8. short f[N][N];
  9. int n, ans = 2, a[N];
  10. int main(){
  11.     scanf("%d", &n);
  12.     for(int i = 1; i <= n; i++)
  13.         scanf("%d", &a[i]);
  14.     sort(a + 1, a + n + 1);
  15.     for(int i = 1; i <= n; i++)
  16.         for(int j = i + 1; j <= n; j++)
  17.             f[i][j] = 2;
  18.     for(int j = n; j; j--){
  19.         int i = j - 1, k = j + 1;
  20.         while(i && k <= n){
  21.             if(a[i] + a[k] > 2 * a[j]) i--;
  22.             else if(a[i] + a[k] < 2 * a[j]) k++;
  23.             else {
  24.                 f[i][j] = f[j][k] + 1;
  25.                 if(f[i][j] > ans) ans = f[i][j];
  26.                 i--, k++;
  27.             }
  28.         }
  29.     }
  30.     printf("%d\n", ans);
  31.     return 0;
  32. }

51nod 1128 正整数分组V2

给出一个长度为N的正整数数组，不改变数组元素的顺序，将这N个数分为K组。各组中元素的和分别为S1,S2....Sk。如何分组，使得S1至Sk中的最大值最小？
例如：1 2 3 4 5 6分为3组，{1 2 3} {4 5} {6}，元素和为6, 9, 6，最大值为9。也可以分为{1 2 3 4} {5} {6}。元素和为：10 5 6，最大值为10。因此第一种方案更优。并且第一种方案的最大值是所有方案中最小的。输出这个最小的最大值。

Input
第1行：2个数N, K，中间用空格分隔，N为数组的长度，K为要分为多少组。(2 <= K < N <= 50000)
第2 - N + 1行：数组元素(1 <= A[i] <= 10^9)
Output
输出这个最小的最大值。

其实特别水！
只是思维一直卡在DP里！
其实二分答案就好了！
唉！

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int N = 50005;
  8. typedef long long ll;
  9. ll n, k, a[N], l, r, mid;
  10. bool check(){
  11.     ll sum = 0, cnt = 1;
  12.     for(int i = 1; i <= n; i++){
  13.         sum += a[i];
  14.         if(sum > mid)
  15.             sum = a[i], cnt++;
  16.         if(cnt > k)
  17.             return 0;
  18.     }
  19.     return 1;
  20. }
  21. int main(){
  22.     scanf("%lld%lld", &n, &k);
  23.     for(int i = 1; i <= n; i++)
  24.         scanf("%lld", &a[i]), r += a[i];
  25.     while(l < r){
  26.         mid = (l + r) >> 1;
  27.         if(check()) r = mid;
  28.         else l = mid + 1;
  29.     }
  30.     printf("%lld\n", l);
  31.     return 0;
  32. }

51nod 1140 矩阵相乘结果的判断

给出三个N*N的矩阵A, B, C，问A * B是否等于C？

正解居然是随机乱搞……

随机“一条” 1*N 的矩阵 D，分别计算 C*D 和 A*B*D (就等于 A*(B*D))，判断结果是否相同。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <ctime>
  7. #include <cstdlib>
  8. #include <cctype>
  9. using namespace std;
  11. int sread(){
  12.     char c;
  13.     int sign = 1, ans = 0;
  14.     while(!isdigit(c = getchar()))
  15.         if(c == '-') sign = -1;
  16.     ans = c - '0';
  17.     while(isdigit(c = getchar()))
  18.         ans = ans * 10 + c - '0';
  19.     return ans * sign;
  20. }
  22. const int N = 501;
  23. int n, A[N][N], B[N][N], C[N][N], tp[N], ans1[N], ans2[N], ans3[N];
  25. void gener(){
  26.     for(int i = 1; i <= n; i++)
  27.         tp[i] = rand() % 233;
  28.     memset(ans1, 0, sizeof(ans1));
  29.     memset(ans2, 0, sizeof(ans2));
  30.     memset(ans3, 0, sizeof(ans3));
  31. }
  33. int main(){
  35.     srand((int)time(0));
  36.     n = sread();
  38.     for(int i = 1; i <= n; i++)
  39.         for(int j = 1; j <= n; j++)
  40.             A[i][j] = sread();
  41.     for(int i = 1; i <= n; i++)
  42.         for(int j = 1; j <= n; j++)
  43.             B[i][j] = sread();
  44.     for(int i = 1; i <= n; i++)
  45.         for(int j = 1; j <= n; j++)
  46.             C[i][j] = sread();
  47.     for(int CNT = 1; CNT <= 2; CNT++){
  48.         gener();
  49.         for(int i = 1; i <= n; i++)
  50.             for(int j = 1; j <= n; j++)
  51.                 ans1[i] += B[i][j] * tp[j];
  52.         for(int i = 1; i <= n; i++)
  53.             for(int j = 1; j <= n; j++)
  54.                 ans2[i] += A[i][j] * ans1[j];
  55.         for(int i = 1; i <= n; i++)
  56.             for(int j = 1; j <= n; j++)
  57.                 ans3[i] += C[i][j] * tp[j];
  58.         for(int i = 1; i <= n; i++)
  59.             if(ans3[i] != ans2[i]){
  60.                 printf("No\n");
  61.                 return 0;
  62.             }
  63.     }
  64.     printf("Yes\n");
  66.     return 0;
  67. }

51nod 1765 谷歌的恐龙 | 期望

被标题吸引进来……却发现跟Chrome的恐龙毫无关系……

相信网络不好的选手一定很熟悉Chrome里面那个恐龙的游戏，这个题目就是根据那个游戏简化得来的。
给出一个正整数n，把恐龙的跳跃简化成一个[0,n)的随机数，再给出一个正整数m，把障碍简化为[0,n)中m个不同的的整数，把分数简化成所有生成的随机数的和。
把整个游戏简化为，每次生成一个[0,n)的随机数，如果这个随机数和给出的m个数字中的其中一个数字相等，那么就停止生成随机数，否则继续生成，求出所有生成的数的和的期望。

在某个小破地方我曾经推过这样一个式子：

的解是

所以这道题的解就是 。

  1. #include <cstdio>
  2. long long n, m;
  3. int main(){
  4.     scanf("%lld%lld", &n, &m);
  5.     printf("%.6lf", (double) n*(n-1)/2/m);
  6.     return 0;
  7. }

随手记一下（三）

带权中位数？

51nod 1040 最大公约数之和 | 数论 欧拉函数

给出一个n，求1-n这n个数，同n的最大公约数的和。比如：n = 6
1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6，加在一起 = 15

唉，数论……又不会。

题解：

最大公约数的种数不多，所以我们采取枚举最大公约数的策略。
最大公约数一定是n的因数，所以枚举每个n的约数x，要求 1~n 中所有满足 gcd(y, n) == x 的y的个数，等价于 gcd(y/x, n/x) == 0 的y的个数，所以只要求 phi(n/x)。

  1. #include <cstdio>
  2. using namespace std;
  3. typedef long long ll;
  4. int n;
  5. ll ans;
  6. int euler(int x){
  7.     int res = x;
  8.     for(int i = 2; i * i <= x; i++){
  9.         if(x % i == 0) res = res / i * (i - 1);
  10.         while(x % i == 0) x /= i;
  11.     }
  12.     if(x > 1) res = res / x * (x - 1);
  13.     return res;
  14. }
  15. int main(){
  16.     scanf("%d", &n);
  17.     for(int i = 1; i * i <= n; i++)
  18.         if(n % i == 0){
  19.             ans += i * euler(n / i);
  20.             if(i * i < n)
  21.                 ans += n / i * euler(i);
  22.         }
  23.     printf("%lld\n", ans);
  24.     return 0;
  25. }

51nod 1161 Partial Sums | 矩阵乘法 打表找规律

给出一个数组A，经过一次处理，生成一个数组S，数组S中的每个值相当于数组A的累加，比如：A = {1 3 5 6} => S = {1 4 9 15}。如果对生成的数组S再进行一次累加操作，{1 4 9 15} => {1 5 14 29}，现在给出数组A，问进行K次操作后的结果。(每次累加后的结果 mod 10^9 + 7)

Input
第1行，2个数N和K，中间用空格分隔，N表示数组的长度，K表示处理的次数（2 <= n <= 5000, 0 <= k <= 10^9, 0 <= a[i] <= 10^9)

Output
共N行，每行一个数，对应经过K次处理后的结果。每次累加后mod 10^9 + 7。

看到这种操作，首先想到的就是矩阵乘法。
然而一个严峻的问题是，n <= 5000...会超时的。
但是由于这个矩阵（主对角线及其左下方都为1，其余为0）长得非常规律，我们可以试着找到它的m次方的规律。
最后发现是个组合数，可以快速求出。

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cstring>
  5. #include <cmath>
  6. using namespace std;
  7. typedef long long ll;
  8. const ll P = 1000000007;
  9. const int N = 5005;
  10. ll n, k, a[N], fake_matrix[N], inv[N];
  11. ll qpow(ll a, ll x){
  12.     ll ans = 1;
  13.     while(x){
  14.         if(x & 1) ans = ans * a % P;
  15.         a = a * a % P;
  16.         x >>= 1;
  17.     }
  18.     return ans;
  19. }
  20. int main(){
  21.     scanf("%lld%lld", &n, &k);
  22.     inv[0] = fake_matrix[1] = 1;
  23.     for(int i = 1; i <= n; i++)
  24.         inv[i] = inv[i - 1] * qpow(i, P - 2) % P;
  25.     k--;
  26.     ll last = 1;
  27.     for(int i = 1; i <= n; i++){
  28.         last = last * (k + i) % P;
  29.         fake_matrix[i + 1] = inv[i] * last % P;
  30.     }
  31.     for(int i = 1; i <= n; i++)
  32.         scanf("%lld", &a[i]);
  33.     ll ans = 0;
  34.     for(int i = 1; i <= n; i++){
  35.         ans = 0;
  36.         for(int j = 1; j <= i; j++)
  37.             ans = (ans + fake_matrix[i - j + 1] * a[j] % P) % P;
  38.         printf("%lld\n", ans);
  39.     }
  40.     return 0;
  41. }

51nod 1120 机器人走方格 V3 | 卡特兰数 Lucas定理

N * N的方格，从左上到右下画一条线。一个机器人从左上走到右下，只能向右或向下走。并要求只能在这条线的上面或下面走，不能穿越这条线，有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10007的结果。

Input
输入一个数N(2 <= N <= 10^9)。
Output
输出走法的数量 Mod 10007。

这个方案数就是卡特兰数………………

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const ll P = 10007;
  9. ll n, fac[P], inv[P];
  10. ll qpow(ll a, ll x){
  11.     ll res = 1;
  12.     while(x){
  13.         if(x & 1) res = res * a % P;
  14.         a = a * a % P;
  15.         x >>= 1;
  16.     }
  17.     return res;
  18. }
  19. void init(){
  20.     fac[0] = inv[0] = 1;
  21.     for(int i = 1; i < P; i++){
  22.         fac[i] = fac[i-1] * i % P;
  23.         inv[i] = qpow(fac[i], P - 2);
  24.     }
  25. }
  26. ll rawC(ll x, ll y){
  27.     return fac[x] * inv[y] * inv[x - y];
  28. }
  29. ll C(ll x, ll y){
  30.     ll res = 1;
  31.     while(x || y){
  32.         res = res * rawC(x % P, y % P) % P;
  33.         x /= P, y /= P;
  34.     }
  35.     return res;
  36. }
  37. int main(){
  38.     scanf("%lld", &n);
  39.     n--;
  40.     init();
  41.     printf("%lld\n", C(2 * n, n) * qpow(n + 1, P - 2) % P * 2 % P);
  42.     return 0;
  43. }

洛谷板子题 堆优Dij

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  8. const int N = 10005, M = 1000005, INF = 2147483647;
  10. int n, m, s, cnt, pos[N], dis[N];
  11. struct node {
  12.     int dis, id; //id: 堆上节点在图上的编号 
  13.     bool operator < (node b){
  14.         return dis < b.dis;
  15.     }
  16. } hp[N];
  17. void node_swap(node &a, node &b){
  18.     swap(pos[a.id], pos[b.id]);
  19.     node c;
  20.     c = a, a = b, b = c;
  21. }
  22. void checkup(int x){
  23.     while(x > 1 && hp[x] < hp[x >> 1]){
  24.         node_swap(hp[x], hp[x >> 1]);
  25.         x >>= 1;
  26.     }
  27. }
  28. void checkdown(int x){
  29.     while((x << 1) <= cnt){
  30.         int y = hp[x << 1 | 1] < hp[x << 1] ? (x << 1 | 1) : (x << 1);
  31.         if(y <= cnt && hp[y] < hp[x]) node_swap(hp[x], hp[y]), x = y;
  32.         else break;
  33.     }
  34. }
  35. void push(int id, int x){
  36.     hp[++cnt].id = id, hp[cnt].dis = x;
  37.     dis[id] = x;
  38.     pos[id] = cnt;
  39.     checkup(cnt);
  40. }
  41. void pop(){
  42.     hp[1] = hp[cnt--];
  43.     checkdown(1);
  44. }
  45. void decrease(int id, int x){
  46.     if(x >= dis[id]) return;
  47.     hp[pos[id]].dis = x;
  48.     dis[id] = x;
  49.     checkup(pos[id]);
  50. }
  51. node top(){ return hp[1]; }
  52. bool empty(){ return cnt == 0;}
  54. int ecnt, adj[N], go[M], w[M], nxt[M]; 
  55. bool vis[N];
  57. void add(int u, int v, int ww){
  58.     go[++ecnt] = v;
  59.     nxt[ecnt] = adj[u];
  60.     adj[u] = ecnt;
  61.     w[ecnt] = ww;
  62. }
  64. int main(){
  65.     scanf("%d%d%d", &n, &m, &s);
  66.     for(int i = 1; i <= m; i++){
  67.         int u, v, ww;
  68.         scanf("%d%d%d", &u, &v, &ww);
  69.         add(u, v, ww);
  70.     }
  71.     push(s, 0);
  72.     for(int i = 1; i <= n; i++) if(i != s) push(i, INF);
  73.     while(!empty()){
  74.         node u = top();
  75.         pop();
  76.         vis[u.id] = 1;
  77.         for(int e = adj[u.id]; e; e = nxt[e])
  78.             if(!vis[go[e]] && u.dis < INF)
  79.                 decrease(go[e], w[e] + u.dis); 
  80.     }
  81.     for(int i = 1; i <= n; i++)
  82.         printf("%d ", dis[i]);
  83.     return 0;
  84. }

我又手写了个快排

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <cstdlib>
  7. #include <ctime>
  8. using namespace std;
  9. void mysort(int *a, int l, int r){
  10.     if(l >= r) return;
  11.     int i = l, j = r, k = l + rand() % (r - l + 1);
  12.     while(i < j){
  13.         while(i < k && a[i] <= a[k]) i++;
  14.         swap(a[i], a[k]), k = i;
  15.         while(j > k && a[j] >= a[k]) j--;
  16.         swap(a[j], a[k]), k = j;
  17.     }
  18.     mysort(a, l, k - 1);
  19.     mysort(a, k + 1, r);
  20. }
  21. int main(){
  22.     srand((int)time(0));
  23.     int n, a[100005];
  24.     scanf("%d", &n);
  25.     for(int i = 1; i <= n; i++)
  26.         scanf("%d", &a[i]);
  27.     mysort(a, 1, n);
  28.     for(int i = 1; i <= n; i++)
  29.         printf("%d ", a[i]);
  30.     puts("");
  31.     return 0;
  32. }

随机数初始化：srand((int)time(0))
随机数：rand()

随手记一下（四）

AI for 2048

51nod 1196 字符串的数量

用N个不同的字符（编号1 - N），组成一个字符串，有如下要求：
(1) 对于编号为i的字符，如果2 * i > n，则该字符可以作为结尾字符。如果不作为结尾字符而是中间的字符，则该字符后面可以接任意字符。
(2) 对于编号为i的字符，如果2 * i <= n，则该字符不可以作为结尾字符。作为中间字符，那么后面接的字符编号一定要 >= 2 * i。
问有多少长度为M且符合条件的字符串，由于数据很大，只需要输出该数Mod 10^9 + 7的结果。
例如：N = 2，M = 3。则abb, bab, bbb是符合条件的字符串，剩下的均为不符合条件的字符串。

Input
输入2个数，N, M中间用空格分割，N为不同字符的数量，M为字符串的长度。(2 <= N, M <= 10^6)
Output
输出符合条件的字符串的数量。由于数据很大，只需要输出该数Mod 10^9 + 7的结果。

可以把一个合法字符串划分成若干个合法的“链”，每条链的结尾都是一个编号大于n/2的字符。设f[i]为长度为i的合法字符串数量，g[i]为长度为i的链的数量，则：

由于“链”的长度不超过，处理f[i]需要。

那么怎么求g[i]呢？我们可以设一个h[i][j]表示长度为i，以j开头的链的个数。

可以一边求h[i][j]一边记录g[i]。h[i][j]可以滚动数组压缩成h[j]。处理h[j]需要。

总复杂度。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. typedef long long ll;
  8. const int INF = 0x3f3f3f3f, P = 1000000007;
  10. const int N = 1000005, L = 23;
  11. int n, m, l;
  12. ll f[N], h[N], g[L], sum[N];
  13. //f[i]: 长度为i的字符串个数；
  14. //h([i])[j]：长度为i以j开头的链数；
  15. //g[i]: 长度为i的链数 
  16. //sum[j]: 上一层的h的后缀和 
  18. int main(){
  19.     scanf("%d%d", &n, &m);
  20.     l = ceil(log2((double)n)) + 1;
  21. /******预处理******/ 
  22.     f[0] = g[0] = g[1] = sum[n] = 1;
  23.     for(int i = n - 1; i * 2 > n; i--)
  24.         sum[i] = sum[i + 1] + 1, g[1]++;
  25.         //i*2>n的i可以作为“链”的结尾 
  26.     for(int i = n/2; i; i--)
  27.         sum[i] = sum[i + 1];
  28.         //其他不可以作为“链”的结尾 
  29. /******处理g数组******/ 
  30.     for(int i = 2; i <= l; i++){
  31.         for(int j = n / 2; j; j--)
  32.             h[j] = sum[2 * j];//上一层[2*j, n]相加 
  33.         sum[n] = 0;
  34.         for(int j = n - 1; j; j--)
  35.             sum[j] = (sum[j + 1] + h[j]) % P;//这一层的sum 
  36.         g[i] = sum[1];
  37.     }
  38. /******处理f数组******/ 
  39.     for(int i = 1; i <= m; i++){
  40.         for(int j = 1; j <= min(i, l); j++)
  41.             f[i] = (f[i] + f[i - j] * g[j]) % P;
  42.     }
  43.     printf("%lld\n", f[m]);
  44.     return 0;
  45. }

51nod 1060 最复杂的数

把一个数的约数个数定义为该数的复杂程度，给出一个n，求1-n中复杂程度最高的那个数。
例如：12的约数为：1 2 3 4 6 12，共6个数，所以12的复杂程度是6。如果有多个数复杂度相等，输出最小的。

Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 100)
第2 - T + 1行：T个数，表示需要计算的n。（1 <= n <= 10^18)
Output
共T行，每行2个数用空格分开，第1个数是答案，第2个数是约数的数量。

正解是搜索……

优化：每一个素数的指数不能大于上一个素数的指数，否则这样生成的数一定更大

@ 注意：判断是否超出n的范围时，一定要用 nowans <= n / plst[x]，而不是乘好了再判断，否则会越界。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 60;
  9. int T, plst[N + 5], pcnt;
  10. ll n, val, ans;
  11. bool np[N + 5];
  12. void euler(){
  13.     np[0] = np[1] = 1;
  14.     for(int i = 2; i <= N; i++){
  15.         if(!np[i]) plst[++pcnt] = i;
  16.         for(int j = 1; j <= pcnt && plst[j] * i <= N; j++){
  17.             np[plst[j] * i] = 1;
  18.             if(i % plst[j] == 0)
  19.                 break;
  20.         }
  21.     }
  22. }
  23. void dfs(int x, int lastnum, ll nowval, ll nowans){
  24.     if(val < nowval || (val == nowval && ans > nowans)){
  25.         val = nowval;
  26.         ans = nowans;
  27.     }
  28.     if(x > pcnt) return;
  29.     for(int i = 1; i <= lastnum && nowans <= n / plst[x]; i++){
  30.         nowans *= plst[x];
  31.         dfs(x + 1, i, nowval * (i + 1), nowans);
  32.     }
  33. }
  34. int main(){
  35.     euler();
  36.     scanf("%d", &T);
  37.     while(T--){
  38.         scanf("%lld", &n);
  39.         val = ans = 0;
  40.         dfs(1, 70, 1, 1);
  41.         printf("%lld %lld\n", ans, val);
  42.     }
  43.     return 0;
  44. }

51nod 1215 数组的宽度

N个整数组成的数组，定义子数组a[i]..a[j]的宽度为：max(a[i]..a[j]) - min(a[i]..a[j])，求所有子数组的宽度和。

上次在某vijos蒟蒻比赛里就看见过这道题，没想出来……

首先，求所有子数组的宽度和就是所有子数组的最大值之和减去所有子数组的最小值之和。那么我们就要计算每个元素对多少个子数组有贡献。

我的做法是暴力的ST表(@ 记得强制转换 long long！）：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 50005;
  9. int n, a[N], mi[N][20], ma[N][20];
  10. ll sum_min, sum_max;
  11. void init(){
  12.     for(int i = 1; i <= n; i++)
  13.         mi[i][0] = ma[i][0] = i;
  14.     for(int j = 1; (1 << j) <= n; j++)
  15.         for(int i = 1; i + (1 << j) - 1 <= n; i++) {
  16.             mi[i][j] = a[mi[i][j - 1]] > a[mi[i + (1 << (j - 1))][j - 1]] ?  mi[i + (1 << (j - 1))][j - 1] : mi[i][j - 1];
  17.             ma[i][j] = a[ma[i][j - 1]] < a[ma[i + (1 << (j - 1))][j - 1]] ?  ma[i + (1 << (j - 1))][j - 1] : ma[i][j - 1];
  18.         }
  19. }
  20. int getmin(int l, int r){
  21.     int j = log2((double) r - l + 1);
  22.     return a[mi[l][j]] > a[mi[r - (1 << j) + 1][j]] ? mi[r - (1 << j) + 1][j] : mi[l][j];
  23. }
  24. int getmax(int l, int r){
  25.     int j = log2((double) r - l + 1);
  26.     return a[ma[l][j]] < a[ma[r - (1 << j) + 1][j]] ? ma[r - (1 << j) + 1][j] : ma[l][j];
  27. }
  28. int max_lim_left(int k, int l, int r){
  29.     if(l == r) return l;
  30.     int mid = (l + r) >> 1;
  31.     if(getmax(mid, k) != k) return max_lim_left(k, mid + 1, r);
  32.     return max_lim_left(k, l, mid);
  33. }
  34. int max_lim_right(int k, int l, int r){
  35.     if(l == r) return l;
  36.     int mid = (l + r + 1) >> 1;
  37.     if(getmax(k, mid) != k) return max_lim_right(k, l, mid - 1);
  38.     return max_lim_right(k, mid, r);
  39. }
  40. int min_lim_left(int k, int l, int r){
  41.     if(l == r) return l;
  42.     int mid = (l + r) >> 1;
  43.     if(getmin(mid, k) != k) return min_lim_left(k, mid + 1, r);
  44.     return min_lim_left(k, l, mid);
  45. }
  46. int min_lim_right(int k, int l, int r){
  47.     if(l == r) return l;
  48.     int mid = (l + r + 1) >> 1;
  49.     if(getmin(k, mid) != k) return min_lim_right(k, l, mid - 1);
  50.     return min_lim_right(k, mid, r);
  51. }
  52. int main(){
  53.     scanf("%d", &n);
  54.     for(int i = 1; i <= n; i++)
  55.         scanf("%d", &a[i]);
  56.     init();
  57.     for(int i = 1; i <= n; i++){
  58.         int l = max_lim_left(i, 1, i), r = max_lim_right(i, i, n);
  59.         sum_max += (ll)(i - l + 1) * (r - i + 1) * a[i];
  60.         l = min_lim_left(i, 1, i), r = min_lim_right(i, i, n);
  61.         sum_min += (ll)(i - l + 1) * (r - i + 1) * a[i];
  62.     }
  63.     printf("%lld\n", sum_max - sum_min);
  64.     return 0;
  65. }

然鹅网上有更妙的办法（单调栈）

TODO

51nod 1537 分解 | 打表找规律 矩阵乘法

问 能否分解成 的形式
如果可以 输出 m%(1e9+7) 否则 输出no

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const ll m = 1000000007;
  9. ll n;
  10. struct matrix {
  11.     ll g[2][2];
  12.     matrix(){
  13.         memset(g, 0, sizeof(g));    
  14.     }
  15.     matrix(int x){
  16.         g[0][1] = g[1][0] = 0, g[0][0] = g[1][1] = 1;
  17.     }
  18.     matrix operator * (matrix b){
  19.         matrix c;
  20.         for(int k = 0; k < 2; k++)
  21.             for(int i = 0; i < 2; i++)
  22.                 for(int j = 0; j < 2; j++)
  23.                     c.g[i][j] = (c.g[i][j] + g[i][k] * b.g[k][j] % m) % m;
  24.         return c;
  25.     }
  26. } op;
  27. matrix ksm(matrix a, ll x){
  28.     matrix ret(1);
  29.     while(x){
  30.         if(x & 1) ret = ret * a;
  31.         a = a * a;
  32.         x >>= 1;
  33.     }
  34.     return ret;
  35. }
  36. int main(){
  37.     op.g[0][0] = op.g[1][0] = op.g[1][1] = 1;
  38.     op.g[0][1] = 2;
  39.     scanf("%lld", &n);
  40.     if(n == 1){
  41.         printf("2\n");
  42.         return 0;
  43.     }
  44.     op = ksm(op, n - 1);
  45.     if(n & 1) 
  46.         printf("%lld\n", 2 * (op.g[1][0] + op.g[1][1]) % m * (op.g[1][0] + op.g[1][1]) % m);
  47.     else 
  48.         printf("%lld\n", (op.g[0][0] + op.g[0][1]) % m * (op.g[0][0] + op.g[0][1]) % m);
  49.     return 0;
  50. }

51nod 1274 最长递增路径

一个无向图，可能有自环，有重边，每条边有一个边权。你可以从任何点出发，任何点结束，可以经过同一个点任意次。但是不能经过同一条边2次，并且你走过的路必须满足所有边的权值严格单调递增，求最长能经过多少条边。

Input
第1行：2个数N, M，N为节点的数量，M为边的数量(1 <= N <= 50000, 0 <= M <= 50000)。节点编号为0 至 N - 1。
第2 - M + 1行：每行3个数S, E, W，表示从顶点S到顶点E，有一条权值为W的边(0 <= S, E <= N - 1, 0 <= W <= 10^9)。
Output
输出最长路径的长度。

把边排序后DP即可。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int INF = 0x3f3f3f3f;
  10. const int N = 50005, M = 100005;
  11. int n, m;
  12. int ecnt = 1, go[M], nxt[M], w[M], adj[N];
  13. int id[M], dp[M], ans;
  15. void add(int u, int v, int ww){
  16.     go[++ecnt] = v;
  17.     w[ecnt] = ww;
  18.     id[ecnt] = ecnt;
  19.     nxt[ecnt] = adj[u];
  20.     adj[u] = ecnt;
  21. }
  23. bool cmp(int a, int b){
  24.     return w[a] < w[b];
  25. }
  27. int main(){
  28.     scanf("%d%d", &n, &m);
  29.     for(int i = 1, u, v, ww; i <= m; i++)
  30.         scanf("%d%d%d", &u, &v, &ww), add(u, v, ww), add(v, u, ww);
  31.     sort(id + 2, id + ecnt + 1, cmp);
  32.     for(int i = 2; i <= ecnt; i++){
  33.         int x = id[i], u = go[x ^ 1];//u是x的起点 
  34.         dp[x] = 1;
  35.         for(int e = adj[u]; e; e = nxt[e]){//枚举起点出发的每条边 
  36.             if(x != e && w[e] < w[x])
  37.                 dp[x] = max(dp[x], dp[e ^ 1] + 1);
  38.         }
  39.         ans = max(ans, dp[x]);
  40.     }
  41.     printf("%d\n", ans);
  42.     return 0;
  43. }

51nod 1277 字符串中的最大值

一个字符串的前缀是指包含该字符第一个字母的连续子串，例如：abcd的所有前缀为a, ab, abc, abcd。
给出一个字符串S，求其所有前缀中，字符长度与出现次数的乘积的最大值。
例如：S = "abababa" 所有的前缀如下:

"a", 长度与出现次数的乘积 1 * 4 = 4,
"ab",长度与出现次数的乘积 2 * 3 = 6,
"aba", 长度与出现次数的乘积 3 * 3 = 9,
"abab", 长度与出现次数的乘积 4 * 2 = 8,
"ababa", 长度与出现次数的乘积 5 * 2 = 10,
"ababab", 长度与出现次数的乘积 6 * 1 = 6,
"abababa", 长度与出现次数的乘积 7 * 1 = 7.

其中"ababa"出现了2次，二者的乘积为10，是所有前缀中最大的。

Input
输入字符串S, (1 <= L <= 100000， L为字符串的长度)，S中的所有字符均为小写英文字母。
Output
输出所有前缀中字符长度与出现次数的乘积的最大值。

用KMP计算出每一位的nxt，然后从后往前，cnt[nxt[i]] += nxt[i]。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int INF = 0x3f3f3f3f;
  9. const int N = 100005;
  10. char s[N];
  11. int n, nxt[N], cnt[N];
  12. ll ans;
  13. int main(){
  14.     scanf("%s", s + 1);
  15.     n = strlen(s + 1);
  16.     for(int i = 2, j = 0; i <= n; i++){
  17.         while(j && s[i] != s[j + 1]) j = nxt[j];
  18.         if(s[i] == s[j + 1]) j++;
  19.         nxt[i] = j;
  20.     }
  21.     for(int i = n; i; i--){
  22.         cnt[i]++;
  23.         cnt[nxt[i]] += cnt[i];
  24.         ans = max(ans, (ll) i * cnt[i]);
  25.     }
  26.     printf("%lld\n", ans);
  27.     return 0;
  28. }

51nod 1296 有限制的排列

计算整数集合{1,2,3,4, .... N }满足下列条件的的排列个数:

在位置a1, a2, ..., aK小于其邻居（编号从0开始）。
在位置b1, b2, ..., bL大于其邻居。

输出符合条件的排列数量Mod 1000000007的结果。例如：N = 4，a = {1}, b = {2}，符合条件的排列为：

2 1 4 3
3 2 4 1
4 2 3 1
3 1 4 2
4 1 3 2

Input
第1行：3个数N, K, L，分别表示数组的长度，限制a的长度，限制b的长度(1 <= N <= 5000, 1 <= K, L <= N)。
第2 - K + 1行：每行一个数，对应限制a的位置(1 <= ai <= N - 2)
第K + 2 - K + L + 1行：每行一个数，对应限制b的位置(1 <= bi <= N - 2)
Output
输出符合条件的排列数量Mod 1000000007的结果。

其实还是很简单的，但之前“+1”那块一直没弄懂。

用 dp[i][j] 表示前i个元素组成的、第i位为j的序列个数（防元素重复）。用数组s[i]记录第i位是否有特殊要求：s[i] = 0 则无要求，s[i] = 1 表示第i个元素大于第i-1个，s[i] = 2 表示第i个元素小于第i-1个。

前两种情况的状态转移都好说，分别是:


第三种略难，因为涉及到把一个新元素放在一个连续数字组成的序列后面……大概是这样的：

原序列：4 2 3 5 1
现在要求dp[6][3]，即由1~6组成的，第6位为3的序列个数
求的就是形如 5 2 4 6 1 3 的序列个数
对比上下两个序列，下面序列就是上面序列中所有大于等于3的元素都加一
两种序列是一一对应的

所以对于第三种情况：

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int N = 5005, P = 1000000007;
  8. int n, a, b;
  9. int s[N], sum[N], dp[N];
  10. int main(){
  11.     scanf("%d%d%d", &n, &a, &b);
  12.     for(int i = 1, tmp; i <= a; i++)
  13.         scanf("%d", &tmp), s[tmp + 1] = 2, s[tmp + 2] = 1;
  14.     for(int i = 1, tmp; i <= b; i++)
  15.         scanf("%d", &tmp), s[tmp + 1] = 1, s[tmp + 2] = 2;
  16.     dp[1] = sum[1] = 1;
  17.     for(int i = 2; i <= n; i++){
  18.         for(int j = 1; j <= n; j++){
  19.             if(s[i] == 0) dp[j] = sum[i - 1];
  20.             else if(s[i] == 1) dp[j] = sum[j - 1];
  21.             else dp[j] = ((sum[i - 1] - sum[j - 1]) % P + P) % P;
  22.         }
  23.         for(int j = 1; j <= n; j++)
  24.             sum[j] = (sum[j - 1] + dp[j]) % P;
  25.     }
  26.     printf("%d\n", sum[n]);
  27.     return 0;
  28. }

51nod 1322 关于树的函数 | 树形DP

我也想出题的时候出出这么妙的树形DP……

有两颗无根树Tree1与Tree2，这两棵树各有N个节点（2<=N<=4000）。每棵树中，N个节点都被标为0,1,2，..,N-1，这N个序号，不保证两颗树是同构的。
定义一个关于这两棵树的函数S(e1,e2),其中e1为Tree1的一条边，e2为Tree2的一条边，定义如下：
（1）如果将边e1从Tree1中移除（即Tree1在e1处断开），那么Tree1将分裂为两棵小树A1与B1；
（2）如果将边e2从Tree2中移除（即Tree2在e2处断开），那么Tree2将分裂为两棵小树A2与B2；
（3）令Set(Tree)表示Tree中所有节点的序号构成的集合，且令Fun(S1，S2)为集合S1与S2交集的大小(交集元素个数，空集时为0)，即|S1 ∩ S2|，例如Fun({1,2,3,4},{7,3,2,8,6}) = 2；
（4）S(e1,e2) = max{ Fun(Set(A1),Set(A2)) , Fun(Set(A1),Set(B2)) , Fun(Set(B1),Set(A2)) ,
Fun(Set(B1),Set(B2)) }.其中 max{...} 为集合{...}中元素的最大值。
简单说，S(e1,e2)为Fun(X,Y)能取到的最大值，其中X=A1或B1，Y=A2或B2.
在这个问题中，你需要求对于所以边对(e1,e2)，共计(N-1)*(N-1)对情况下，S(e1,e2)平方的和。即求如下公式的值。

一开始看着这一大堆东西毫无头绪，后来看讨论区两位大神点拨，豁然开朗……

两棵树各被分成两部分（A1、B1、A2、B2），对于任何一个编号，在（A1、B1）中要么属于A1要么属于B1，在（A2、B2）中要么属于A2要么属于B2。那么可以列个表：

  A1 B1
A2 a b
B2 c d

a、b、c、d为交集的大小，则a + b = c + d = a + c = b + d = n, 这样求出abcd中的任意一个，其余三个皆可求。

那么我们可以在一棵树中枚举切断的边，然后随便选择它的一侧，作为A1，记录一下每个编号是否属于A1; 之后在另一棵树上进行DP，令一个点及其子树作为A2，求出A1、A2的交集大小，然后就能求出其余三个交集大小，取max即可。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 4005;
  9. int n;
  10. int ecnt[2] = {1, 1}, go[2][2 * N], nxt[2][2 * N], adj[2][N];
  11. int sze[N], rsze[N], ccnt;
  12. bool col[N];
  13. ll ans;
  14. void add(int u, int v, bool p){
  15.     go[p][++ecnt[p]] = v;
  16.     nxt[p][ecnt[p]] = adj[p][u];
  17.     adj[p][u] = ecnt[p];
  18. }
  19. void color(int u, int pre){
  20.     int v;
  21.     //printf("%d <- %d\n", u, pre);
  22.     col[u] = 1, ccnt++;
  23.     for(int e = adj[0][u]; e; e = nxt[0][e])
  24.         if((v = go[0][e]) != pre)
  25.             color(v, u);
  26. }
  27. void dfs(int u, int pre){
  28.     int v;
  29.     sze[u] = col[u];
  30.     rsze[u] = 1;
  31.     for(int e = adj[1][u]; e; e = nxt[1][e])
  32.         if((v = go[1][e]) != pre){
  33.             dfs(v, u);
  34.             sze[u] += sze[v];
  35.             rsze[u] += rsze[v];
  36.         }
  37.     if(pre){
  38.         int res = max(sze[u], rsze[u] - sze[u]);
  39.         res = max(res, ccnt - sze[u]);
  40.         res = max(res, n - ccnt - rsze[u] + sze[u]);
  41.         ans += (ll) res * res;
  42.     }
  43. }
  44. int main(){
  45.     scanf("%d", &n);
  46.     for(int i = 1, u, v; i < n; i++)
  47.         scanf("%d%d", &u, &v), add(u + 1, v + 1, 0), add(v + 1, u + 1, 0);
  48.     for(int i = 1, u, v; i < n; i++)
  49.         scanf("%d%d", &u, &v), add(u + 1, v + 1, 1), add(v + 1, u + 1, 1);
  51.     for(int i = 2; i <= ecnt[0]; i += 2){
  52.         memset(col, 0, sizeof(col));
  53.         ccnt = 0;
  54.         color(go[0][i], go[0][i ^ 1]);
  55.         //printf("tree1 cut %d %d, ccnt = %d\n", go[0][i], go[0][i ^ 1], ccnt);
  56.         dfs(1, 0);
  57.     }
  58.     printf("%lld\n", ans);
  59.     return 0;
  60. }

51nod 1330 雕像投影

有一个三维的雕像，这个雕像被一个N*N*N的立方网格包围。巧合的是该雕像恰好能被网格划分，即这个N^3的立方网格中，每一个1*1*1的小立方块要么恰好完全是雕塑的一部分（该立方网格与雕塑的交就是该立方大小），要么这个立方块是空的（与雕塑的交为空）。这个雕塑是一个整体，其每个单位立方块的拓扑结构是相互连通的。两个立方块A与B是连通的要么（1）A与B存在公共面，（2）A与C连通且C与B连通。不幸的是这个雕塑被不小心破坏了，现在需要还原它，但幸运的是我们拥有这个雕像的三视图投影XY，YZ与ZX。其中XY是一个二维数组，表示一个沿着Z轴方向的投影，XY[i][j]是XY平面上（i，j）坐标处网格的投影信息，如果XY[i][j] = ‘ Y’ 说明该处是有阴影的，即三维空间坐标(i,j,0),(i,j,1)...(i,j,z)...(i,j,N-1)这N个格子中至少有一个立方块是实心的；相反如果XY[i][j] = ‘ N’ 说明（i，j）处是透光的，即维空间坐标(i,j,0),(i,j,1)...(i,j,z)...(i,j,N-1)这N个格子全部是空心的。同理YZ[i][j]表达YZ平面信息，YZ[i][j]对应{(x,i,j)|x=0,1,..,N-1}处的网格；而ZX[i][j]同理，对应{(j,y,i)|y=0,1,...,N-1}这些网格。由于种种原因，复原者发现这个三视图信息似乎构造不出一个合理的三维雕塑，他们希望确定这个三视图是否有错误。现在给出XY,YZ,ZX的信息，你需要判断该三视图是否有可能是某个雕塑的三视图投影。

例如一个2x2x2的立方网格，其三视图如下：
XY： YZ： ZX：
YN YN YN
NN NN NN
该视图显然可以构造一个雕塑出来，即（0,0,0）处是实心，其他7个立方块都是空心。

而如果其三视图如下：
XY： YZ： ZX：
YN YN YN
NY NY NY
是不能构造一个雕塑出来，因为（0,0,0）处与（1,1,1）处都是实心，而它们不是连通的。

Input
多组测试数据，第一行一个整数T，表示测试数据个数，其中1<=T<=5。
之后有T组测试数据，每组数据第一行一个整数N，即立方网格大小，1<=N<=10.
之后有3*N行，每行N个字符，每个字符不是'Y'就是‘N’，且前N行代表XY[][],中间N行代表YZ[][],最后N行是ZX[][].
Output
每组数据一行输出，输出雕塑存在可能性，如果有至少一种构造方法输出"Possible"，否则"Impossible"。（都不含引号）

Input示例
2
2
YN
NN
YN
NN
YN
NN
2
YN
NY
YN
NY
YN
NY
Output示例
Possible
Impossible

一开始搞一个n*n*n的实心立方体，然后把每条透光的部分抠掉，之后检查这个立方体的每一个联通块能否把所有不透光的地方挡满。

注意：
（1） 啥都没有（全是"N"）是可行的
（2） 完全不存在的三视图（如只有一面有"Y"，其余两面都全是"N"）是不可行的

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <iostream>
  5. using namespace std;
  7. typedef long long ll;
  8. const int N = 15;
  9. //up, down, left, right, front, back
  10. int dx[] = {0, 0, -1, 1, 0, 0}, dy[] = {0, 0, 0, 0, 1, -1}, dz[] = {1, -1, 0, 0, 0, 0};
  11. int T, n;
  12. bool fil[N][N][N], vis[N][N][N];
  13. char s1[N][N], s2[N][N], s3[N][N];
  14. bool y1[N][N], y2[N][N], y3[N][N];
  16. void dfs(int x, int y, int z){
  17.     vis[x][y][z] = 1;
  18.     y1[x][y] = y2[y][z] = y3[z][x] = 1;
  19.     for(int i = 0; i < 6; i++){
  20.         if(fil[x + dx[i]][y + dy[i]][z + dz[i]] && !vis[x + dx[i]][y + dy[i]][z + dz[i]])
  21.             dfs(x + dx[i], y + dy[i], z + dz[i]);
  22.     }
  23. }
  25. bool check(){
  26.     for(int i = 1; i <= n; i++)
  27.         for(int j = 1; j <= n; j++){
  28.             if(s1[i][j] == 'Y' && !y1[i][j]) return 0;
  29.             if(s2[i][j] == 'Y' && !y2[i][j]) return 0;
  30.             if(s3[i][j] == 'Y' && !y3[i][j]) return 0;
  31.         }
  32.     return 1;
  33. }
  35. int main(){
  36.     scanf("%d", &T);
  37.     while(T--){
  38.         scanf("%d", &n);
  39.         bool ept = 1;
  40.         for(int i = 1; i <= n; i++)
  41.             for(int j = 1; j <= n; j++)
  42.                 for(int k = 1; k <= n; k++)
  43.                     fil[i][j][k] = 1, vis[i][j][k] = 0;
  44.         for(int i = 1; i <= n; i++){
  45.             scanf("%s", s1[i] + 1);
  46.             for(int j = 1; j <= n; j++)
  47.                 if(s1[i][j] == 'N'){
  48.                     for(int k = 1; k <= n; k++)
  49.                         fil[i][j][k] = 0;
  50.                 }
  51.                 else ept = 0;
  52.         }
  53.         for(int j = 1; j <= n; j++){
  54.             scanf("%s", s2[j] + 1);
  55.             for(int k = 1; k <= n; k++)
  56.                 if(s2[j][k] == 'N'){
  57.                     for(int i = 1; i <= n; i++)
  58.                         fil[i][j][k] = 0;
  59.                 }
  60.                 else ept = 0;
  61.         }
  62.         for(int k = 1; k <= n; k++){
  63.             scanf("%s", s3[k] + 1);
  64.             for(int i = 1; i <= n; i++)
  65.                 if(s3[k][i] == 'N'){
  66.                     for(int j = 1; j <= n; j++)
  67.                         fil[i][j][k] = 0;
  68.                 }
  69.                 else ept = 0;
  70.         }
  71.         bool ok = 0;
  72.         for(int i = 1; i <= n; i++)
  73.             for(int j = 1; j <= n; j++)
  74.                 for(int k = 1; k <= n; k++)
  75.                     if(fil[i][j][k] && !vis[i][j][k]){
  76.                         memset(y1, 0, sizeof(y1));
  77.                         memset(y2, 0, sizeof(y2));
  78.                         memset(y3, 0, sizeof(y3));
  79.                         dfs(i, j, k);
  80.                         ok = ok || check();
  81.                     }
  82.         if(ok || ept) printf("Possible\n");
  83.         else printf("Impossible\n");
  84.     }
  85.     return 0;
  86. }

51nod 1050 循环数组最大子段和

N个整数组成的循环序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值（循环序列是指n个数围成一个圈，因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列）。当所给的整数均为负数时和为0。
例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。
Input
第1行：整数序列的长度N（2 <= N <= 50000)
第2 - N+1行：N个整数 (-10^9 <= S[i] <= 10^9)
Output
输出循环数组的最大子段和。

循环数组最大子段和有且只有两种可能：

  1. 正常的（不循环的）最大子段和
  2. 总和减去最小字段和

后者相当于把这个循环数组中间最小的那段剪去。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int N = 50005;
  8. typedef long long ll;
  9. int n;
  10. ll a[N], sum, lastmin, minn, lastmax, maxn;
  11. int main(){
  12.     scanf("%d", &n);
  13.     for(int i = 1; i <= n; i++)
  14.         scanf("%lld", &a[i]), sum += a[i];
  15.     for(int i = 1; i <= n; i++){
  16.         lastmin = min(lastmin + a[i], a[i]);
  17.         minn = min(lastmin, minn);
  18.         lastmax = max(lastmax + a[i], a[i]);
  19.         maxn = max(lastmax, maxn);
  20.     }
  21.     printf("%lld\n", max(maxn, sum - minn));
  22.     return 0;
  23. }

@ 不开 long long 见那啥

51nod 1103 N的倍数 | 抽屉原理

一个长度为N的数组A，从A中选出若干个数，使得这些数的和是N的倍数。
例如：N = 8，数组A包括：2 5 6 3 18 7 11 19，可以选2 6，因为2 + 6 = 8，是8的倍数。
Input
第1行：1个数N，N为数组的长度，同时也是要求的倍数。(2 <= N <= 50000)
第2 - N + 1行：数组A的元素。(0 < A[i] <= 10^9)
Output
如果没有符合条件的组合，输出No Solution。
第1行：1个数S表示你所选择的数的数量。
第2 - S + 1行：每行1个数，对应你所选择的数。

对于每一位求前缀和（模n），一共求了n个；如果其中有一个为0，则输出这一位前面所有的数即可，否则前缀和模n一共有(n - 1)种可能，则根据抽屉原理必有两个前缀和相等，输出相等的两位之间的数即可。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 50005;
  9. int n, cnt[N];
  10. ll a[N], sum;
  11. int main(){
  12.     scanf("%d", &n);
  13.     for(int i = 1; i <= n; i++)
  14.         cnt[i] = -1;
  15.     for(int i = 1; i <= n; i++){
  16.         scanf("%lld", &a[i]);
  17.         sum = (sum + a[i]) % n;
  18.         if(cnt[sum] == -1) cnt[sum] = i;
  19.         else {
  20.             printf("%d\n", i - cnt[sum]);
  21.             for(int j = cnt[sum] + 1; j <= i; j++)
  22.                 printf("%lld\n", a[j]);
  23.             return 0;
  24.         }
  25.     }
  26.     return 0;
  27. }

@ sum一开始用的是数组，然后写成了sum[i] = sum[i] + a[i]……
……为了这点问题还买了数据！我的盾啊！

51nod 1254 最大M子段和 | ST表

N个整数组成的序列a[1],a[2],a[3],…,a[n]，你可以对数组中的一对元素进行交换，并且交换后求a[1]至a[n]的最大子段和，所能得到的结果是所有交换中最大的。当所给的整数均为负数时和为0。
例如：{-2,11,-4,13,-5,-2, 4}将 -4 和 4 交换，{-2,11,4,13,-5,-2, -4}，最大子段和为11 + 4 + 13 = 28。

Input
第1行：整数序列的长度N（2 <= N <= 50000)
第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）
Output
输出交换一次后的最大子段和。

O(nlogn)：枚举要被替换的数，经预处理可以得到它向左右延伸的L、R，然后在[L, R]以外的部分找最大值来替换它即可。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 50005, INF = 0x3f3f3f3f;
  9. int n, lp[N], rp[N];
  10. ll a[N], ma[N][20], ln[N], rn[N], ans;
  11. ll getma(int l, int r){
  12.     if(r < l) return -INF;
  13.     int j = log2((double) r - l + 1);
  14.     return max(ma[l][j], ma[r - (1 << j) + 1][j]);
  15. }
  16. int main(){
  17.     scanf("%d", &n);
  18.     for(int i = 1; i <= n; i++)
  19.         scanf("%lld", &a[i]), ma[i][0] = a[i];
  20.     for(int i = 1; i <= n; i++)
  21.         if(ln[i - 1] + a[i] > a[i])
  22.             lp[i] = lp[i - 1], ln[i] = ln[i - 1] + a[i];
  23.         else lp[i] = i, ln[i] = a[i];
  24.     for(int i = n; i; i--)
  25.         if(rn[i + 1] + a[i] > a[i])
  26.             rp[i] = rp[i + 1], rn[i] = rn[i + 1] + a[i];
  27.         else rp[i] = i, rn[i] = a[i];
  28.     for(int j = 1; (1 << j) <= n; j++)
  29.         for(int i = 1; i + (1 << j) - 1 <= n; i++)
  30.             ma[i][j] = max(ma[i][j - 1], ma[i + (1 << (j - 1))][j - 1]);
  32.     for(int i = 1; i <= n; i++){
  33.         ll rpl = max(getma(1, lp[i] - 1), getma(rp[i] + 1, n));
  34.         rpl = max(rpl, a[i]);
  35.         ans = max(ans, ln[i] + rn[i] - 2 * a[i] + rpl);
  36.     }
  37.     printf("%lld\n", ans);
  38.     return 0;
  39. }

51nod 1065 最小正子段和 | set

N个整数组成的序列a[1],a[2],a[3],…,a[n]，从中选出一个子序列（a[i],a[i+1],…a[j]），使这个子序列的和>0，并且这个和是所有和>0的子序列中最小的。
例如：4，-1，5，-2，-1，2，6，-2。-1，5，-2，-1，序列和为1，是最小的。

在之前所有前缀和里找当前前缀和的前驱。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <cmath>
  6. #include <set>
  7. using namespace std;
  8. typedef long long ll;
  9. const int N = 50005;
  10. int n;
  11. ll a[N], sum, ans = 0x3f3f3f3f3f3f3f3f;
  12. set <ll> s;
  13. int main(){
  14.     scanf("%d", &n);
  15.     s.insert(0);
  16.     for(int i = 1; i <= n; i++){
  17.         scanf("%lld", &a[i]);
  18.         sum += a[i];
  19.         set <ll> :: iterator p = s.lower_bound(sum);
  20.         if(p != s.begin())
  21.             --p, ans = min(ans, sum - *p);
  22.         s.insert(sum);
  23.     }
  24.     printf("%lld\n", ans);
  25.     return 0;
  26. }

@ 一开始没把0扔进去导致无法处理答案包含第一个数的情况，错了前两个点。

CodeForces 703D 区间出现偶数次的数的异或和

来自豪神的推荐。

给出一个长为n的序列，有m个询问，每次询问区间[l, r]中所有出现偶数次的数的异或和。()

所有出现偶数次的数的异或和就是所有数的异或和^所有不同的数的异或和。（因为所有数的异或和就是所有出现奇数次的数的异或和，再异或上不同的数的异或和，就把“不同的数的异或和”中出现奇数次的数“去掉了”。）

问题转化为询问一个区间中所有不同的数的异或和。

对于“不同的数”一类问题，可以离线处理：

将询问按照r排序，用线段树维护区间异或和，然后从1到n扫一遍这个序列，如果a[i]出现过，就把之前出现的a[i]从线段树种删去（改成0即可），没出现则不管，然后把新的a[i]放进线段树（把第i位由0改成a[i]）。

如果此时的i是要处理的询问的r，则此时线段树中的[l, r]异或和就是要求的“不同的数异或和”。

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cmath>
  5. #include <cstring>
  6. #include <map>
  7. using namespace std;
  8. const int N = 1000005;
  9. int n, m;
  10. int data[4 * N], a[N], ans[N], sum[N];
  11. void change(int k, int l, int r, int p, int x){
  12.     if(l == r) return (void) (data[k] = x);
  13.     int mid = (l + r) >> 1;
  14.     if(p <= mid) change(k << 1, l, mid, p, x);
  15.     else change(k << 1 | 1, mid + 1, r, p, x);
  16.     data[k] = data[k << 1] ^ data[k << 1 | 1];
  17. }
  18. int query(int k, int l, int r, int ql, int qr){
  19.     if(ql <= l && qr >= r) return data[k];
  20.     int mid = (l + r) >> 1, ret = 0;
  21.     if(ql <= mid) ret ^= query(k << 1, l, mid, ql, qr);
  22.     if(qr > mid) ret ^= query(k << 1 | 1, mid + 1, r, ql, qr);
  23.     return ret;
  24. }
  25. struct question{
  26.     int id, l, r;
  27.     bool operator < (question b) const{
  28.         return r < b.r;
  29.     }
  30. } q[N];
  31. map <int, int> pos;
  33. int main(){
  35.     scanf("%d", &n);
  36.     for(int i = 1; i <= n; i++)
  37.         scanf("%d", &a[i]), sum[i] = sum[i - 1] ^ a[i];
  38.     scanf("%d", &m);
  39.     for(int i = 1; i <= m; i++)
  40.         scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
  41.     sort(q + 1, q + m + 1);
  42.     for(int i = 1, qnum = 1; i <= n && qnum <= m; i++){
  43.         if(pos.find(a[i]) != pos.end()) change(1, 1, n, pos[a[i]], 0);
  44.         change(1, 1, n, i, a[i]);
  45.         pos[a[i]] = i;
  46.         while(i == q[qnum].r){
  47.             ans[q[qnum].id] = query(1, 1, n, q[qnum].l, q[qnum].r);
  48.             ans[q[qnum].id] ^= sum[q[qnum].r] ^ sum[q[qnum].l - 1];
  49.             qnum++;
  50.         }
  51.     }
  52.     for(int i = 1; i <= m; i++)
  53.         printf("%d\n", ans[i]);
  54.     return 0;
  55. }

51nod 1105 第K大的数 | 二分

水题！
居然！
T了！

  1. #include <cstring>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 50005;
  9. ll n, k, a[N], b[N];
  10. bool check(ll x){
  11.     ll cnt = 0;
  12.     int j = 0;
  13.     for(int i = n; i; i--){
  14.         while(j <= n && a[i] * b[j] < x) j++;
  15.         cnt += n - j + 1;
  16.     }
  17.     return cnt >= k;
  18. }
  19. int main(){
  20.     scanf("%lld%lld", &n, &k);
  21.     for(int i = 1; i <= n; i++)
  22.         scanf("%lld%lld", &a[i], &b[i]);
  23.     sort(a + 1, a + n + 1);
  24.     sort(b + 1, b + n + 1);
  25.     ll l = a[1] * b[1], r = a[n] * b[n], mid;
  26.     while(l < r){
  27.         mid = (l + r + 1) >> 1;
  28.         if(check(mid)) l = mid;
  29.         else r = mid - 1;
  30.     }
  31.     printf("%lld\n", l);
  32.     return 0;
  33. }

@ 数数完全不用一个一个数啊！！！

51nod 1107 斜率小于0的连线数量 | 逆序对

二维平面上N个点之间共有C(n,2)条连线。求这C(n,2)条线中斜率小于0的线的数量。
二维平面上的一个点，根据对应的X Y坐标可以表示为(X,Y)。例如：(2,3) (3,4) (1,5) (4,6)，其中(1,5)同(2,3)(3,4)的连线斜率 < 0，因此斜率小于0的连线数量为2。
Input
第1行：1个数N，N为点的数量(0 <= N <= 50000)
第2 - N + 1行：N个点的坐标，坐标为整数。(0 <= X[i], Y[i] <= 10^9)
Output
输出斜率小于0的连线的数量。(2,3) (2,4)以及(2,3) (3,3)这2种情况不统计在内。

原来就是求逆序对啊！

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 50005;
  9. int n;
  10. int ans;
  11. struct point{
  12.     int x, y;
  13.     bool operator < (point b) const{
  14.         return x < b.x;
  15.     }
  16. } p[N], tmp[N];
  17. bool cmp(point a, point b){
  18.     return a.y == b.y ? a.x < b.x : a.y < b.y;
  19. }
  20. void merge_sort(int l, int r){
  21.     if(l == r) return;
  22.     int mid = (l + r) >> 1;
  23.     merge_sort(l, mid);
  24.     merge_sort(mid + 1, r);
  25.     int pa = l, pb = mid + 1, pt = l;
  26.     while(pa <= mid && pb <= r){
  27.         if(p[pb] < p[pa]) {
  28.             tmp[pt++] = p[pb++];
  29.             ans += mid - pa + 1;
  30.         }
  31.         else
  32.             tmp[pt++] = p[pa++];
  33.     }
  34.     while(pb <= r) tmp[pt++] = p[pb++];
  35.     while(pa <= mid) tmp[pt++] = p[pa++];
  36.     for(int i = l; i <= r; i++)
  37.         p[i] = tmp[i];
  38. }
  39. int main(){
  40.     scanf("%d", &n);
  41.     for(int i = 1; i <= n; i++)
  42.         scanf("%d%d", &p[i].x, &p[i].y);
  43.     sort(p + 1, p + n + 1, cmp);
  44.     merge_sort(1, n);
  45.     printf("%d\n", ans);
  46.     return 0;
  47. }

51nod 1096 距离和最小 | 中位数

X轴上有N个点，求X轴上一点使它到这N个点的距离之和最小，输出这个最小的距离之和。

TODO: 证明它

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 10005;
  9. int n;
  10. ll a[N];
  11. double x, ans;
  12. int main(){
  13.     scanf("%d", &n);
  14.     for(int i = 1; i <= n; i++)
  15.         scanf("%lld", &a[i]);
  16.     sort(a + 1, a + n + 1);
  17.     if(n & 1)
  18.         x = a[n / 2 + 1];
  19.     else
  20.         x = (double) (a[n / 2] + a[n / 2 + 1]) / 2;
  21.     for(int i = 1; i <= n; i++)
  22.         ans += fabs(x - a[i]);
  23.     printf("%.0lf\n", ans);
  24.     return 0;
  25. }

51nod 1204 Parity 奇偶 | 并查集

你的朋友写下一串包含1和0的串让你猜，你可以从中选择一个连续的子串（例如其中的第3到第5个数字）问他，该子串中包含了奇数个还是偶数个1，他会回答你的问题，然后你可以继续提问......你怀疑朋友的答案可能有错，或说同他之前的答案相互矛盾，例如：1 - 2 奇数，3 - 4 奇数，那么可以确定1 - 4 一定是偶数，如果你的朋友回答是奇数，就产生了矛盾。给出所有你朋友的答案，请你找出第一个出现矛盾的答案。

Input
第1行：2个数N, Q，N为串的长度，Q为询问的数量。（2 <= N <= 100000, 2 <= Q <= 50000)
第2 - Q + 1行：每行包括两个数以及一个字符串来描述朋友的回答，2个数中间用空格分隔，分别表示区间的起点和终点，后面的字符为"even"或"odd"，表示朋友的答案。
Output
输出1个数，表示朋友的答案中第一个错误答案的位置，如果所有答案均不矛盾，则输出-1。

可以把闭区间变成左开右闭区间，用带权并查集维护与父亲的关系即可。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  8. const int N = 100005;
  9. int n, m, fa[N];
  10. bool w[N];
  11. char tmp[5];
  12. int findfa(int x){
  13.     if(x == fa[x]) return x;
  14.     int anc = findfa(fa[x]);
  15.     w[x] ^= w[fa[x]];
  16.     fa[x] = anc;
  17.     return anc;
  18. }
  19. void join(int u, int v, bool op){
  20.     int fau = findfa(u), fav = findfa(v);
  21.     fa[fav] = fau;
  22.     w[fav] = op ^ w[u] ^ w[v];
  23. }
  24. int main(){
  25.     scanf("%d%d", &n, &m);
  26.     for(int i = 1; i <= n + 1; i++)
  27.         fa[i] = i;
  28.     for(int i = 1, l, r, fal, far; i <= m; i++){
  29.         scanf("%d%d%s", &l, &r, tmp);
  30.         r++;
  31.         fal = findfa(l), far = findfa(r);
  32.         if(tmp[0] == 'e'){
  33.             if(fal != far) join(l, r, 0);
  34.             else if (w[l] != w[r]) {
  35.                 printf("%d\n", i);
  36.                 return 0;
  37.             }
  38.         }
  39.         else{
  40.             if(fal != far) join(l, r, 1);
  41.             else if(w[l] == w[r]){
  42.                 printf("%d\n", i);
  43.                 return 0;
  44.             }
  45.         }
  46.     }
  47.     printf("-1\n");
  48.     return 0;
  49. }

51nod 1275 连续子段的差异 | 单调队列

给出一个包括N个元素的整数数组A，包括A本身在内，共有 (N+1)*N / 2个非空子段。例如：1 3 2的子段为{1} {3} {2} {1 3} {3 2} {1 3 2}。在这些子段中，如果最大值同最小值的差异不超过K，则认为这是一个合格的子段。给出数组A和K，求有多少符合条件的子段。例如：3 5 7 6 3，K = 2，符合条件的子段包括：{3} {5} {7} {6} {3} {3 5} {5 7} {7 6} {5 7 6}，共9个。
Input
第1行：2个数N, K（1 <= N <= 50000, 0 <= K <= 10^9)
第2 - N + 1行：每行1个数，对应数组的元素Ai(0 <= A[i] <= 10^9)
Output
输出符合条件的子段数量。

扫一遍，把每个元素丢进一个能求最大值最小值的队列里，如果最大值减最小值大于K了就从队列左边弹出元素。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  8. const int N = 50005;
  9. int n, k, ans, a[N], qmin[N], qmax[N], l, r, lmin, rmin, lmax, rmax;
  11. int main(){
  12.     scanf("%d%d", &n, &k);
  13.     for(int i = 1; i <= n; i++)
  14.         scanf("%d", &a[i]);
  15.     lmin = lmax = l = 1, rmin = rmax = 0;
  16.     for(r = 1; r <= n; r++){
  17.         while(lmin <= rmin && a[qmin[rmin]] >= a[r]) rmin--;
  18.         qmin[++rmin] = r;
  19.         while(lmax <= rmax && a[qmax[rmax]] <= a[r]) rmax--;
  20.         qmax[++rmax] = r;
  21.         while(a[qmax[lmax]] - a[qmin[lmin]] > k && lmin <= rmin && lmax <= rmax){
  22.             if(qmin[lmin] == l) lmin++;
  23.             if(qmax[lmax] == l) lmax++;
  24.             l++;
  25.         }
  26.         ans += r - l + 1;
  27.     }
  28.     printf("%d\n", ans);
  29.     return 0;
  30. }

51nod 1179 最大的最大公约数 | 数论 思维题

给出N个正整数，找出N个数两两之间最大公约数的最大值。例如：N = 4，4个数为：9 15 25 16，两两之间最大公约数的最大值是15同25的最大公约数5。
Input
第1行：一个数N，表示输入正整数的数量。(2 <= N <= 50000)
第2 - N + 1行：每行1个数，对应输入的正整数.(1 <= S[i] <= 1000000)
Output
输出两两之间最大公约数的最大值。

哎……数论……还是看到题就不会……看了题解倒是会……可是有啥用呢……

答案范围小，由大到小枚举答案，再对于答案枚举它的1倍、2倍、3倍，数出来有多少数是它的倍数，如果数出来大于等于2，这个答案就是最终答案。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int N = 50005, S = 1000005;
  8. int n, cnt[S], maxs;
  9. int main(){
  10.     scanf("%d", &n);
  11.     for(int i = 1, tmp; i <= n; i++)
  12.         scanf("%d", &tmp), cnt[tmp]++, maxs = max(maxs, tmp);
  13.     for(int i = maxs; i; i--){
  14.         int tot = 0;
  15.         for(int j = i; j <= maxs; j += i)
  16.             tot += cnt[j];
  17.         if(tot >= 2){
  18.             printf("%d\n", i);
  19.             return 0;
  20.         }
  21.     }
  22.     return 0;
  23. }

51nod 1191 消灭兔子 | 堆

我是抱着怎样的心情做这样一道题……

题面是腾讯打兔子……………………企鹅消灭兔子？！

有N只兔子，每只有一个血量B[i]，需要用箭杀死免子。有M种不同类型的箭可以选择，每种箭对兔子的伤害值分别为D[i]，价格为P[i](1 <= i <= M)。假设每种箭只能使用一次，每只免子也只能被射一次，计算要消灭地图上的所有兔子最少需要多少Q币。如不能杀死所有兔子，请输出No Solution。
特别说明：1、当箭的伤害值大于等于兔子的血量时，能将兔子杀死；2、血量B[i]，箭的伤害值D[i]，箭的价格P[i]，均小于等于100000。
Input
第1行：两个整数N，M，中间用空格分隔（1 <= N, M <= 50000），分别表示兔子的个数和箭的种类。
第2 - N + 1行：每行1个正整数(共N行)，表示兔子的血量B[i]（1 <= B[i] <= 100000）。
第N + 2 - N + M + 1行：每行2个正整数(共M行)，中间用空格分隔，表示箭所能造成的伤害值D[i]，和需要花费的Q币P[i]（1 <= D[i], P[i] <= 100000）。
Output
输出最少需要多少Q币才能消灭所有的兔子。如果不能杀死所有兔子，请输出"No Solution"。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <queue>
  7. using namespace std;
  9. const int N = 50005;
  10. int n, m, ans;
  11. struct rabbit {
  12.     int b;
  13.     bool operator < (rabbit obj) const {
  14.         return b > obj.b;
  15.     }
  16. } rabbits[N];
  17. struct arrow {
  18.     int d, p;
  19.     bool operator < (arrow obj) const {
  20.         return p > obj.p;
  21.     }
  22. } arrows[N];
  23. bool cmp_d (arrow a, arrow b){ 
  24.     return a.d > b.d; 
  25. }
  26. priority_queue <arrow> q;
  27. int main(){
  28.     scanf("%d%d", &n, &m);
  29.     for(int i = 1; i <= n; i++)
  30.         scanf("%d", &rabbits[i].b);
  31.     for(int i = 1; i <= m; i++)
  32.         scanf("%d%d", &arrows[i].d, &arrows[i].p);
  33.     sort(rabbits + 1, rabbits + n + 1);
  34.     sort(arrows + 1, arrows + m + 1, cmp_d);
  35.     for(int i = 1, j = 1; i <= n; i++){
  36.         while(j <= m && arrows[j].d >= rabbits[i].b){
  37.             q.push(arrows[j]);
  38.             j++;
  39.         }
  40.         if(q.empty()){
  41.             printf("No Solution\n");
  42.             return 0;
  43.         }
  44.         ans += q.top().p;
  45.         q.pop();
  46.     }
  47.     printf("%d\n", ans);
  48.     return 0;
  49. }

51nod 1158 全是1的最大子矩阵 | 单调栈

给出1个M*N的矩阵M1，里面的元素只有0或1，找出M1的一个子矩阵M2，M2中的元素只有1，并且M2的面积是最大的。输出M2的面积。
Input
第1行:2个数m,n中间用空格分隔(2 <= m,n <= 500)
第2 - N + 1行：每行m个数，中间用空格分隔，均为0或1。
Output
输出最大全是1的子矩阵的面积。

枚举子矩阵的最下面一行，对每一位求向上的前缀和，枚举前缀和最小位，向左右延伸得到最大的以它为最小值的区间，区间宽度*这个最小值来更新答案。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int N = 502;
  8. int m, n, mp[N][N], sum[N], stk[N], top, toleft[N], toright[N], ans;
  9. int main(){
  10.     scanf("%d%d", &m, &n);
  11.     for(int i = 1; i <= n; i++)
  12.         for(int j = 1; j <= m; j++)
  13.             scanf("%d", &mp[i][j]);
  14.     for(int i = 1; i <= n; i++){
  15.         for(int j = 1; j <= m; j++)
  16.             sum[j] = mp[i][j] ? sum[j] + 1 : 0;
  17.         top = 0, stk[0] = 0;
  18.         for(int j = 1; j <= m; j++){
  19.             while(top && sum[stk[top]] >= sum[j]) top--;
  20.             toleft[j] = stk[top];
  21.             stk[++top] = j;
  22.         }
  23.         top = 0, stk[0] = m + 1;
  24.         for(int j = m; j; j--){
  25.             while(top && sum[stk[top]] >= sum[j]) top--;
  26.             toright[j] = stk[top];
  27.             stk[++top] = j;
  28.         }
  29.         for(int j = 1; j <= m; j++)
  30.             ans = max(ans, sum[j] * (toright[j] - toleft[j] - 1));
  31.     }
  32.     printf("%d\n", ans);
  33.     return 0;
  34. }

51nod 1241 特殊的排序 | 思维题

一个数组的元素为1至N的整数，现在要对这个数组进行排序，在排序时只能将元素放在数组的头部或尾部，问至少需要移动多少个数字，才能完成整个排序过程？
例如：
2 5 3 4 1 将1移到头部 =>
1 2 5 3 4 将5移到尾部 =>
1 2 3 4 5 这样就排好了，移动了2个元素。
给出一个1-N的排列，输出完成排序所需的最少移动次数。
Input
第1行：1个数N(2 <= N <= 50000)。
第2 - N + 1行：每行1个数，对应排列中的元素。
Output
输出1个数，对应所需的最少移动次数。

只有最长的连续数字组成的序列不用动，所以把它求出来即可。

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. const int N = 50005;
  5. int n, pos[N], ans;
  6. int main(){
  7.     scanf("%d", &n);
  8.     for(int i = 1, tmp; i <= n; i++)
  9.         scanf("%d", &tmp), pos[tmp] = i;
  10.     for(int i = 1, last = 0; i <= n; i++)
  11.         ans = max(ans, last = (pos[i] > pos[i - 1]) ? last + 1 : 1);
  12.     printf("%d\n", n - ans);
  13.     return 0;
  14. }

51nod 1189 阶乘分数 | 数论

难死我了……数论只会GCD……

1/N! = 1/X + 1/Y（0 < x<=y），给出N，求满足条件的整数解的数量。例如：N = 2，1/2 = 1/3 + 1/6，1/2 = 1/4 + 1/4。由于数量可能很大，输出Mod 10^9 + 7。
Input
输入一个数N（1 <= N <= 1000000)。
Output
输出解的数量Mod 10^9 + 7。




所以把分解质因数然后乘法原理即可。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 1000005, P = 1000000007;
  9. ll n, cnt[N], ans = 1, prime[N], pcnt;
  10. bool np[N];
  11. void euler(){
  12.     np[1] = np[0] = 1;
  13.     for(int i = 2; i <= n; i++){
  14.         if(!np[i]) prime[++pcnt] = i;
  15.         for(int j = 1; j <= pcnt && i * prime[j] <= n; j++){
  16.             np[i * prime[j]] = 1;
  17.             if(i % prime[j] == 0) break;
  18.         }
  19.     }
  20. }
  21. void factorize(int x){
  22.     for(int i = 1; prime[i] * prime[i] <= x; i++)
  23.         while(x % prime[i] == 0){
  24.             cnt[prime[i]] += 2;
  25.             x /= prime[i];
  26.         }
  27.     if(x > 1) cnt[x] += 2;
  28. }
  29. int main(){
  30.     scanf("%lld", &n);
  31.     euler();
  33.     for(int i = 2; i <= n; i++)
  34.         factorize(i);
  35.     for(int i = 2; i <= n; i++)
  36.         ans = ans * (cnt[i] + 1) % P;
  37.     ans = (1 + ans) * 500000004 % P;
  38.     printf("%lld\n", ans);
  39.     return 0;
  40. }

51nod 1052 最大M子段和 | DP

今天啥都难……数论难完DP难……

N个整数组成的序列a[1],a[2],a[3],…,a[n]，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。如果M >= N个数中正数的个数，那么输出所有正数的和。
例如：-2 11 -4 13 -5 6 -2，分为2段，11 -4 13一段，6一段，和为26。
Input
第1行：2个数N和M，中间用空格分隔。N为整数的个数，M为划分为多少段。（2 <= N , M <= 5000)
第2 - N+1行：N个整数 (-10^9 <= a[i] <= 10^9)
Output
输出这个最大和

题解链接

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 5005, INF = 0x3f3f3f3f;
  9. int n, m;
  10. ll a[N], dp[N], pre[N]; 
  11. int main(){
  12.     scanf("%d%d", &n, &m);
  13.     for(int i = 1; i <= n; i++)
  14.         scanf("%lld", &a[i]);
  15.     for(int j = 1; j <= m; j++){
  16.         dp[1] = a[1];
  17.         for(int i = 2; i <= n; i++){
  18.             dp[i] = max(dp[i - 1], pre[i - 1]) + a[i];
  19.             if(i > 1) pre[i - 1] = max(pre[i - 2], dp[i - 1]);
  20.         }
  21.         pre[n] = max(pre[n - 1], dp[n]);
  22.     }
  23.     printf("%lld\n", pre[n]);
  24.     return 0;
  25. }

51nod 1199 Money out of Thin Air | 线段树

啊！时隔多天！又写线段树找虐了！

一棵有N个节点的树，每个节点对应1个编号及1个权值，有2种不同的操作。
操作1：S x y z，表示如果编号为x的节点的权值 < y，则将节点x的权值加上z。(Single)
操作2：A x y z，表示如果编号为x的节点以及其所有子节点的权值平均值 < y，则将节点x及其所有子节点的权值加上z。(All)
给出树节点之间的关系，进行M次操作，问所有操作完成后，各个节点的权值为多少？
节点的编号为0 - N - 1，根节点的编号为0，并且初始情况下，根节点的权值也是0。
Input
第1行：2个数N, M，N为节点的数量，M为操作的数量(1 <= N, M <= 50000)。
第2 - N行：每行描述一个节点N[i]的信息，第2行对应编号为1的节点，第N行对应编号为N - 1的节点。具体内容为：每行2个数P[i], W[i]。P[i]为当前节点的父节点的编号，W[i]为当前节点的权值。(0 <= W[i] <= 10^5, P[i] < i)
第N + 1 - N + M行：每行表示一个操作，S x y z或A x y z，（0 <= y, z <= 10^5)。
Output
输出共N行，每行1个数W[i]，表示经过M次后，编号为0 - N - 1的节点的权值。

“前序遍历”一下，给每个点一个序列里的位置，然后正常线段树即可。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 50005;
  10. int n, m, adj[N], nxt[N], ncnt, pos[N], sze[N];
  11. ll w[N], a[N], data[4*N], lazy[4*N];
  13. void add(int fa, int son){
  14.     nxt[son] = adj[fa];
  15.     adj[fa] = son;
  16. }
  17. void dfs(int u){
  18.     pos[u] = ++ncnt;
  19.     a[ncnt] = w[u];
  20.     sze[u] = 1;
  21.     for(int v = adj[u]; v; v = nxt[v])
  22.         dfs(v), sze[u] += sze[v];
  23. }
  24. void build(int k, int l, int r){
  25.     if(l == r) return (void) (data[k] = a[l]);
  26.     int mid = (l + r) >> 1;
  27.     build(k << 1, l, mid);
  28.     build(k << 1 | 1, mid + 1, r);
  29.     data[k] = data[k << 1] + data[k << 1 | 1];
  30. }
  31. void pushdown(int k, int l, int r){
  32.     if(l == r || !lazy[k]) return;
  33.     int mid = (l + r) >> 1;
  34.     lazy[k << 1] += lazy[k];
  35.     lazy[k << 1 | 1] += lazy[k];
  36.     data[k << 1] += lazy[k] * (mid - l + 1);
  37.     data[k << 1 | 1] += lazy[k] * (r - mid);
  38.     lazy[k] = 0;
  39. }
  40. void change(int k, int l, int r, int ql, int qr, ll x){
  41.     if(ql <= l && qr >= r)
  42.         return (void) (data[k] += (r - l + 1) * x, lazy[k] += x);
  43.     pushdown(k, l, r);
  44.     int mid = (l + r) >> 1;
  45.     if(ql <= mid) change(k << 1, l, mid, ql, qr, x);
  46.     if(qr > mid) change(k << 1 | 1, mid + 1, r, ql, qr, x);
  47.     data[k] = data[k << 1] + data[k << 1 | 1];
  48. }
  49. ll query(int k, int l, int r, int ql, int qr){
  50.     if(ql <= l && qr >= r) return data[k];
  51.     pushdown(k, l, r);
  52.     int mid = (l + r) >> 1;
  53.     ll ret = 0;
  54.     if(ql <= mid) ret += query(k << 1, l, mid, ql, qr);
  55.     if(qr > mid) ret += query(k << 1 | 1, mid + 1, r, ql, qr);
  56.     return ret;
  57. }
  59. int main(){
  60.     scanf("%d%d", &n, &m);
  61.     for(int i = 2, fa; i <= n; i++)
  62.         scanf("%d%lld", &fa, &w[i]), add(fa + 1, i);
  63.     dfs(1);
  64.     build(1, 1, n);
  65.     char s[3];
  66.     ll x, y, z;
  67.     while(m--){
  68.         scanf("%s%lld%lld%lld", s, &x, &y, &z);
  69.         x++;
  70.         if(s[0] == 'S'){
  71.             if(query(1, 1, n, pos[x], pos[x]) < y)
  72.                 change(1, 1, n, pos[x], pos[x], z);
  73.         }
  74.         else{
  75.             if(query(1, 1, n, pos[x], pos[x] + sze[x] - 1) < y * sze[x])
  76.                 change(1, 1, n, pos[x], pos[x] + sze[x] - 1, z);
  77.         }
  78.     }
  79.     for(int i = 1; i <= n; i++)
  80.         printf("%lld\n", query(1, 1, n, pos[i], pos[i]));
  81.     return 0;
  82. }

@ 不开longlong见祖宗……开了longlong中间写了个int仍然见祖宗……

51nod 1307 绳子与重物 | 二分答案

据说可以用某种神奇的并查集过，然鹅我太蒻了，用二分答案，也能过……

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int N = 50005, INF = 0x3f3f3f3f;
  8. int n, fa[N], adj[N], nxt[N], cap[N], w[N], sze[N];
  9. void add(int u, int v){
  10.     nxt[v] = adj[u];
  11.     adj[u] = v;
  12. }
  13. bool check(int u){
  14.     sze[u] = w[u];
  15.     for(int v = adj[u]; v != -1; v = nxt[v]){
  16.         if(check(v)) return 1; //下面的断了
  17.         sze[u] += sze[v];
  18.     }
  19.     if(sze[u] > cap[u]) return 1; //断了
  20.     return 0;
  21. }
  22. int main(){
  23.     scanf("%d", &n);
  24.     cap[0] = INF;
  25.     for(int i = 1; i <= n; i++)//绳子编号改为1~n，根节点为0
  26.         scanf("%d%d%d", &cap[i], &w[i], &fa[i]), fa[i]++;
  27.     int l = 1, r = n, mid;
  28.     while(l < r){
  29.         mid = (l + r + 1) >> 1;
  30.         memset(adj, -1, sizeof(adj));
  31.         memset(sze, 0, sizeof(sze));
  32.         for(int i = 1; i <= mid; i++)
  33.             add(fa[i], i);
  34.         if(check(0)) r = mid - 1;//断了
  35.         else l = mid;//没断
  36.     }
  37.     printf("%d\n", l);
  38.     return 0;
  39. }

51nod 1282 时钟 | 字符串最小表示法

排序后（每个指针居然是等价的！）用最小表示法表示这个时钟每两个相邻指针之间的距离，然后暴力判断是否相同就可以了。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  9. const int N = 503;
  10. int n, m, p, a[N][N], st[N];
  11. ll ans;
  13. int mini_rep(int *s){
  14.     int i = 0, j = 1, k = 0;
  15.     while(i < m && j < m && k < m){
  16.         k = 0;
  17.         while(s[i + k] == s[j + k] && k < m) k++;
  18.         if(k == m) return i;
  19.         if(s[i+k]>s[j+k])   
  20.             if(i+k+1>j) i=i+k+1;  
  21.             else i=j+1;  
  22.         else if(j+k+1>i) j=j+k+1;  
  23.         else  j=i+1;   
  24.     }
  25.     return i < m ? i : j;
  26. }
  28. bool cmp(int i, int j){
  29.     for(int k = 0; k < m; k++)
  30.         if(a[i][(st[i] + k) % m] != a[j][(st[j] + k) % m])
  31.             return 0;
  32.     return 1;
  33. }
  34. int main(){
  35.     scanf("%d%d%d", &n, &m, &p);
  36.     for(int i = 1; i <= n; i++){
  37.         for(int j = 0; j < m; j++)
  38.             scanf("%d", &a[i][j]);
  39.         sort(a[i], a[i] + m);
  40.         int tmp = a[i][m - 1];
  41.         for(int j = m - 1; j >= 0; j--)
  42.             a[i][j] -= a[i][j - 1];
  43.         a[i][0] = a[i][0] - tmp + p;
  44.         st[i] = mini_rep(a[i]);
  45.     }
  46.     for(int i = 1; i <= n; i++)
  47.         for(int j = 1; j < i; j++)
  48.             if(cmp(i, j)) ans++;
  49.     printf("%lld\n", ans);
  50.     return 0;
  51. }

51nod 1205 流水线调度 | 贪心

因为1号流水线随时都能用，只要使2号尽量紧凑即可，所以……
将所有物品分成两组，1号时间小于2号一组，1号时间大于2号一组，先搞前者，按1号时间升序排序，然后搞后者，按2号时间降序排序。

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. const int N = 50005;
  5. struct node {
  6.     int a, b;
  7. } s1[N], s2[N];
  8. int n, cnt1, cnt2;
  9. long long ans1, ans2;
  10. bool cmp1(node x, node y){ return x.a < y.a; }
  11. bool cmp2(node x, node y){ return x.b > y.b; }
  12. int main(){
  13.     scanf("%d", &n);
  14.     for(int i = 1, a, b; i <= n; i++){
  15.         scanf("%d%d", &a, &b);
  16.         if(a <= b) s1[++cnt1].a = a, s1[cnt1].b = b;
  17.         else s2[++cnt2].a = a, s2[cnt2].b = b;
  18.     }
  19.     sort(s1 + 1, s1 + cnt1 + 1, cmp1);
  20.     sort(s2 + 1, s2 + cnt2 + 1, cmp2);
  21.     for(int i = 1; i <= cnt1; i++){
  22.         ans1 += s1[i].a;
  23.         ans2 = max(ans2, ans1) + s1[i].b;
  24.     }
  25.     for(int i = 1; i <= cnt2; i++){
  26.         ans1 += s2[i].a;
  27.         ans2 = max(ans2, ans1) + s2[i].b;
  28.     }
  29.     printf("%lld\n", ans2);
  30.     return 0;
  31. }

51nod 1281 山峰和旗子 | 二分

很简单的二分，注意可能答案为0！！！

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int N = 50005, INF = 0x3f3f3f3f;
  8. int n, a[N], p[N], cnt;
  9. bool check(int k){
  10.     int tot = 0, last = -INF;
  11.     for(int i = 1; i <= cnt; i++){
  12.         if(p[i] - last >= k)
  13.             tot++, last = p[i];
  14.         if(tot >= k) return 1;
  15.     }
  16.     return 0;
  17. }
  18. int main(){
  19.     scanf("%d", &n);
  20.     for(int i = 1; i <= n; i++)
  21.         scanf("%d", &a[i]);
  22.     for(int i = 2; i < n; i++)
  23.         if(a[i] > a[i - 1] && a[i] > a[i + 1])
  24.             p[++cnt] = i;
  25.     int l = 0, r = n, mid;
  26.     while(l < r){
  27.         mid = (l + r + 1) >> 1;
  28.         if(check(mid))//可以放得下
  29.             l = mid;
  30.         else
  31.             r = mid - 1;
  32.     }
  33.     printf("%d\n", l);
  34.     return 0;
  35. }

51nod 1255 字典序最小的序列 | 贪心 单调栈

维护一个栈，从左往右，如果栈顶元素比当前元素大，且以后还会出现，则弹出。

注意栈中元素不能重复，且根本不打算放进去的元素是不能用来把别的元素弹出去的。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int N = 100005;
  8. char s[N], stk[28];
  9. int n, last[128], top;
  10. bool vis[128];
  11. int main(){
  12.     scanf("%s", s + 1);
  13.     n = strlen(s + 1);
  14.     for(int i = n; i; i--)
  15.         if(!last[s[i]]) last[s[i]] = i;
  16.     for(int i = 1; i <= n; i++){
  17.         if(vis[s[i]]) continue;
  18.         while(top && stk[top] > s[i] && last[stk[top]] > i)
  19.             vis[stk[top--]] = 0;
  20.         vis[stk[++top] = s[i]] = 1;
  21.     }
  22.     for(int i = 1; i <= top; i++)
  23.         printf("%c", stk[i]);
  24.     puts("");
  25.     return 0;
  26. }

51nod 1542 羊圈偷袭 | 暴力？！

@ 读入优化里面没初始化，遂跪……

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. int qread(){
  9.     char c; bool minus = 0; int ret = 0;
  10.     while((c = getchar()) > '9' || c < '0')
  11.         if(c == '-') minus = 1;
  12.     ret = c - '0';
  13.     while((c = getchar()) <= '9' && c >= '0')
  14.         ret = ret * 10 + c - '0';
  15.     return minus ? -ret : ret;
  16. }
  17. const int N = 300005;
  18. int n, w[N], p;
  19. ll ans;
  20. int main(){
  21.     n = qread();
  22.     for(int i = 1; i <= n; i++)
  23.         w[i] = qread();
  24.     p = qread();
  25.     for(int i = 1, a, b; i <= p; i++){
  26.         a = qread(), b = qread();
  27.         ans = 0;
  28.         for(int j = a; j <= n; j += b)
  29.             ans += w[j];
  30.         printf("%lld\n", ans);
  31.     }
  32.     return 0;
  33. }

51nod 1319 跳跃游戏 | 计算几何？

心态崩了……

有一个可以在二维平面上做跳跃的机器人，该机器人有独特的跳跃程序。该程序的跳跃距离是由一个循环序列S决定的。序列S有无穷多项，但其有一个最小周期序列，令其为A，A中有N个元素(N<=50)，S[i]=A[i mod N],i从0取到正无穷。例如，A={2,5,1,1}那么S={2,5,1,1,2,5,1,1,2,5,1,1.....}。机器人的跳跃规则如下：第k次跳跃时，机器人可以跳出离原来位置S[k]的距离外，方向随意，其中k=0,1,2,3,...。这个方向是由机器人的控制玩家自己决定的，它可以是0~360度内的任意一个方向，角度未必是整数，落点也未必是整点。注意，控制玩家不能控制跳跃的距离，这个距离是机器人的自身属性即A序列决定的；玩家只能决定每一次跳跃的方向。现在，你需要让机器人从平面的(0,0)处跳跃到(x,0)处，求出最少需要控制机器人跳跃几次。其中，初始（第0次）跳跃距离恰为S[0]。
例如：x=5，A={3,4},(0,0)->(9/5,12/5)->(5,0)。
Input
第一行一个整数T，表示测试数据的数量，1<=T<=10。
接下来有T组相同格式的数据。
每组数据的第一行包含两个整数x、N，其中 -1,000,000,000<=x<=1,000,000,000 , 1<=N<=50。
接下来N行，每行一个整数A[i],其中1<=A[i]<=1,000,000,000。
Output
每组测试数据输出一行一个整数，即能使机器人完成任务最少跳跃的次数。

如果跳过两轮以上，则如果跳过的总路程 >= x 则一定可行：把两轮分别走成直线，摆成等腰三角形的腰，x作为底，能摆出[0, 2*L]之间的所有距离，那么只要总路程 >= x 且跳过两轮以上，把最后两轮摆成等腰三角形即可。

如果不到两轮，则如果跳过总路程 >= x 且跳过总路程+x大于跳过的最长边的二倍即可（这样至少能构成三角形）。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 53;
  9. int T, x, n;
  10. ll a[N];
  11. int main(){
  12.     scanf("%d", &T);
  13.     while(T--){
  14.         bool done = 0;
  15.         scanf("%d%d", &x, &n);
  16.         if(x < 0) x = -x;
  17.         for(int i = 1; i <= n; i++)
  18.             scanf("%lld", &a[i]);
  19.         if(!x){
  20.             printf("0\n");
  21.             continue;
  22.         }
  23.         ll sum = 0, maxn = 0;
  24.         for(int i = 1; i <= 2 * n; i++){
  25.             sum += a[(i - 1) % n + 1];
  26.             maxn = max(maxn, a[(i - 1) % n + 1]);
  27.             if(sum >= x && sum + x >= 2 * maxn){
  28.                 printf("%d\n", i);
  29.                 done = 1;
  30.                 break;
  31.             }
  32.         }
  33.         if(done) continue;
  34.         sum /= 2;
  35.         ll ans = x / sum, tot = 0;
  36.         x %= sum;
  37.         if(!x) printf("%lld\n", ans * n);
  38.         else
  39.             for(int i = 1; i <= n; i++){
  40.                 tot += a[i];
  41.                 if(tot >= x){
  42.                     printf("%lld\n", ans * n + i);
  43.                     break;
  44.                 }
  45.             }
  46.     }
  47.     return 0;
  48. }

51nod 1358 浮波那契 | 矩阵乘法

这题跟个智障一样
可惜我也跟个智障一样
zzetza

  1. #include <cstdio>
  2. #include <cstring>
  3. using namespace std;
  4. typedef long long ll;
  5. const int N = 35, P = 1000000007;
  6. ll n;
  7. struct matrix {
  8.     ll g[N][N];
  9.     matrix(){
  10.         memset(g, 0, sizeof(g));
  11.     }
  12.     matrix operator * (matrix b){
  13.         matrix c;
  14.         for(int k = 1; k < N; k++)
  15.             for(int i = 1; i < N; i++)
  16.                 for(int j = 1; j < N; j++)
  17.                     c.g[i][j] = (c.g[i][j] + g[i][k] * b.g[k][j] % P) % P;
  18.         return c;
  19.     }
  20. } ans, op;
  21. matrix qpow(matrix a, ll x){
  22.     matrix ret;
  23.     for(int i = 1; i < N; i++)
  24.         ret.g[i][i] = 1;
  25.     while(x){
  26.         if(x & 1) ret = ret * a;
  27.         a = a * a;
  28.         x >>= 1;
  29.     }
  30.     return ret;
  31. }
  32. int main(){
  33.     scanf("%lld", &n);
  34.     n *= 10;
  35.     if(n <= (ll) 40){
  36.         printf("1\n");
  37.         return 0;
  38.     }
  39.     for(int i = 1; i < N; i++)
  40.         ans.g[i][1] = 1;
  41.     for(int i = 1; i < N - 1; i++)
  42.         op.g[i][i + 1] = 1;
  43.     op.g[N - 1][1] = op.g[N - 1][N - 10] = 1;
  44.     ans = qpow(op, n - 40) * ans;
  45.     printf("%lld\n", ans.g[N - 1][1]);
  46.     return 0;
  47. }

随手记一下（五）

数独算法

51nod 1391 01串 | 瞎找规律

给定一个01串S,求出它的一个尽可能长的子串S[i..j]，满足存在一个位置i<=x Input
一行包含一个只由0和1构成的字符串S。 S的长度不超过1000000。
Output
一行包含一个整数，表示满足要求的最长子串的长度。

看了一眼讨论区，感觉有些地方讲得不是很清楚？

可以这样考虑：

设g[x]为[1, x]中0的个数，h[x]为[1, x]中1的个数。

题目要求的可以描述为：一个区间(l, r]中有一个元素x (l < x < r), 满足(l, x]中0的个数大于1的个数，(x, r]中0的个数小于1的个数。

由“(l, x]中0的个数大于1的个数”可以写出：
g[x] - g[l] > h[x] - h[l]
移项得：
h[x] - g[x] < h[l] - g[l]

由“(x, r]中0的个数小于1的个数”可以写出：
g[r] - g[x] < h[r] - h[x]
移项得：
h[x] - g[x] < h[r] - g[r]

我们设f[x] = h[x] - g[x]，则可得：
f[x] < f[l], f[x] < f[r]

那么我们把整个f[x]数组求出来（这个数组中的每个元素要么比前一个多1要么比前一个少1），对于每个x，向左找到最靠左的、f[l] > f[x] 的 l，向右找到最靠右的、f[r] > f[x] 的 r，则 r - l 为区间的长度。

那么需要满足x左右都能找到f比它大的元素，并且只要满足这一条，x越小越好。

那么在序列左侧找到第一个f[i] > f[i + 1]的元素，在右侧找到第一个f[j] > f[j - 1]的元素，如果(i, j]存在，在[i, j]中找最小值x，找到后在整个序列的左、右侧分别找第一个f 大于 f[x]的元素，就是题目所求区间。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  8. const int N = 1000005, INF = 0x3f3f3f3f;
  9. int n, f[N];
  11. int main(){
  13.     char c;
  14.     while(1){
  15.         c = getchar();
  16.         if(c == '0') n++, f[n] = f[n - 1] - 1;
  17.         else if(c == '1') n++, f[n] = f[n - 1] + 1;
  18.         else break;
  19.     }
  20.     int l = 0, r = n;
  21.     while(l < n && f[l] < f[l + 1]) l++;
  22.     while(r && f[r] < f[r - 1]) r--;
  23.     if(r <= l){
  24.         printf("0\n");
  25.         return 0;
  26.     }
  27.     int minn = INF;
  28.     for(int i = l + 1; i <= r; i++)
  29.         minn = min(minn, f[i]);
  30.     for(l = 0; f[l] <= minn; l++);
  31.     for(r = n; f[r] <= minn; r--);
  32.     printf("%d\n", r - l);
  34.     return 0;
  35. }

51nod 1423 最大二“货” | 单调栈

白克喜欢找一个序列中的次大值。对于一个所有数字都不同的序列 ，他的次大值是最大的 xj ,并且满足
对于一个所有数字都不同的序列 ，他的幸运数字是最大值和次大值的异或值(Xor)。
现在有一个序列 。 表示子段 。你的任务是找出所有子段的最大幸运数字。
注意，序列s中的所有数字都是不同的。

从左到右扫一遍，维护单调递减栈，要把一个新元素放进去的时候，它在栈中的前一个元素可以作为区间最大值，新元素作为区间次大值；但是从左到右扫一遍只能求最大值在左、次大值在右的情况，从右到左再扫一遍，就能求出所有情况了。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  9. int read(){
  10.     char c; 
  11.     while((c = getchar()) < '0' || c > '9');
  12.     int ret = c - '0';
  13.     while((c = getchar()) >= '0' && c <= '9')
  14.         ret = ret * 10 + c - '0';
  15.     return ret;
  16. }
  18. const int N = 100005;
  19. int n, a[N], stk[N], top, ans;
  21. int main(){
  22.     while(~scanf("%d", &n)){
  23.         for(int i = 1; i <= n; i++)
  24.             a[i] = read();
  25.         top = 0;
  26.         for(int i = 1; i <= n; i++){
  27.             while(top && stk[top] < a[i]) top--;
  28.             ans = max(ans, stk[top] ^ a[i]);
  29.             stk[++top] = a[i];
  30.         }
  31.         top = 0;
  32.         for(int i = n; i; i--){
  33.             while(top && stk[top] < a[i]) top--;
  34.             ans = max(ans, stk[top] ^ a[i]);
  35.             stk[++top] = a[i];
  36.         }
  37.         printf("%d\n", ans);
  38.     }
  39.     return 0;
  40. }

51nod 1388 六边形平面

取三个颜色a、b、c，只要每行错开着循环涂这三个颜色，即使图全都是X也可以涂完，答案不大于3。

在此基础上，如果没有奇环，两种颜色即可。

如果点都是独立的，一种颜色即可。

搜一搜就好了。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int N = 55;
  8. int T, n;
  9. char tmp[N];
  10. bool X[N][N], vis[N][N], col[N][N];
  11. const int dx[] = {0, -1, -1, 0, 1, 1, 0};
  12. const int dy[] = {0, 0, 1, 1, 0, -1, -1};
  13. bool legal(int i, int j){
  14.     return X[i][j] && i && j && i <= n && j <= n;
  15. }
  16. bool dfs(int x, int y, bool color){
  17.     vis[x][y] = 1, col[x][y] = color;
  18.     int vx, vy;
  19.     for(int d = 1; d <= 6; d++){
  20.         vx = x + dx[d], vy = y + dy[d];
  21.         if(!legal(vx, vy)) continue;
  22.         if(!vis[vx][vy]) {
  23.             if(dfs(vx, vy, !color))
  24.                 return 1;
  25.         }
  26.         else{
  27.             if(col[vx][vy] == color)
  28.                 return 1;
  29.         }
  30.     }
  31.     return 0;
  32. }
  33. int main(){
  34.     scanf("%d", &T);
  35.     while(T--){
  36.         memset(vis, 0, sizeof(vis));
  37.         memset(col, 0, sizeof(col));
  38.         //memset(X, 0, sizeof(X));
  39.         bool empty = 1;
  40.         scanf("%d", &n);
  41.         for(int i = 1; i <= n; i++){
  42.             scanf("%s", tmp + 1);
  43.             for(int j = 1; j <= n; j++)
  44.                 if(tmp[j] == 'X') X[i][j] = 1, empty = 0;
  45.                 else X[i][j] = 0;
  46.         }
  47.         if(empty){
  48.             printf("0\n");
  49.             goto LOOP;
  50.         }
  51.         for(int i = 1; i <= n; i++)
  52.             for(int j = 1; j <= n; j++)
  53.                 if(X[i][j] && !vis[i][j] && dfs(i, j, 0)){
  54.                     printf("3\n");
  55.                     goto LOOP;
  56.                 }
  57.         for(int i = 1; i <= n; i++)
  58.             for(int j = 1; j <= n; j++)
  59.                 if(col[i][j]){
  60.                     printf("2\n");
  61.                     goto LOOP;
  62.                 }
  63.         printf("1\n");
  64.       LOOP: continue;
  65.     }
  66.     return 0;
  67. }

51nod 1349 最大值 | 单调栈 输出优化！

@ 输出优化没有特判0，遂GG……

以后一定要每天写一遍输入输出优化……

有一天，小a给了小b一些数字，让小b帮忙找到其中最大的数，由于小b是一个程序猿，当然写了一个代码很快的解决了这个问题。
这时，邪恶的小c又出现了，他问小b，假如我只需要知道这些数字中的某个区间的最大值，你还能做嘛？
小b经过七七四十九天的思考，终于完美的解决了这道题目，这次，他想也让小c尝尝苦头，于是他问小c，我现在想知道存在多少不同的区间的最大值大于等于k，你还能做吗？
这次，小c犯了难，他来请教身为程序猿的你。
Hint:一个区间指al,al+1,…,ar这一段的数且l<=r，一个区间的最大值指max{al,al+1,…,ar}，两个区间不同当且仅当[l1,r1],[l2,r2]中l1不等于l2或r1不等于r2

Input
第一行读入一个正整数n(1<=n<=100000)，表示有n个数字。
接下来一行读入n个正整数ai(1<=ai<=100000)
接下来一行一个正整数Q(1<=Q<=100000)，表示有Q组询问。
接下来Q行，每行一个正整数k(1<=k<=100000)
Output
Q行，每行一个正整数，表示存在多少区间大于等于k。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. int read(){
  9.     char c;
  10.     while((c = getchar()) < '0' || c > '9');
  11.     int ret = c - '0';
  12.     while((c = getchar()) >= '0' && c <= '9')
  13.         ret = ret * 10 + c - '0';
  14.     return ret;
  15. }
  16. void write(ll x){
  17.     if(x == 0) {
  18.         putchar('0');
  19.         putchar('\n');
  20.         return;
  21.     }
  22.     char c[20];
  23.     int p = 0;
  24.     while(x) c[p++] = x % 10 + '0', x /= 10;
  25.     while(p--) putchar(c[p]);
  26.     putchar('\n');
  27. }
  28. const int N = 100005, INF = 0x3f3f3f3f;
  29. int n, q, a[N], stk[N], top, l[N], r[N], k;
  30. ll cnt[N];
  31. int main(){
  32.     n = read();
  33.     for(int i = 1; i <= n; i++)
  34.         a[i] = read(), r[i] = n + 1;
  35.     a[0] = a[n + 1] = INF;
  36.     for(int i = 1; i <= n; i++){
  37.         while(top && a[stk[top]] <= a[i]) r[stk[top--]] = i;
  38.         l[i] = stk[top];
  39.         stk[++top] = i;
  40.     }
  41.     for(int i = 1; i <= n; i++)
  42.         cnt[a[i]] += (ll) (i - l[i]) * (r[i] - i);
  43.     for(int i = 99999; i; i--)
  44.         cnt[i] += cnt[i + 1];
  45.     q = read();
  46.     while(q--){
  47.         k = read();
  48.         write(cnt[k]);
  49.     }
  50.     return 0;
  51. }

51nod 1405 树的距离之和 | 树形DP

给定一棵无根树，假设它有n个节点，节点编号从1到n, 求任意两点之间的距离（最短路径）之和。
Input
第一行包含一个正整数n (n <= 100000)，表示节点个数。
后面(n - 1)行，每行两个整数表示树的边。
Output
每行一个整数，第i(i = 1,2,...n)行表示所有节点到第i个点的距离之和。

居然卡着时限过了……

先求出每个点到根节点距离之和，然后对每个点O(1)从父节点转移答案即可。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 100005;
  9. int read(){
  10.     char c;
  11.     while((c = getchar()) < '0' && c > '9');
  12.     int ret = c - '0';
  13.     while((c = getchar()) >= '0' && c <= '9')
  14.         ret = ret * 10 + c - '0';
  15.     return ret;
  16. }
  17. int n;
  18. int ecnt, go[2*N], nxt[2*N], adj[N];
  19. int sze[N], dep[N];
  20. ll ans[N];
  21. void add(int u, int v){
  22.     go[++ecnt] = v;
  23.     nxt[ecnt] = adj[u];
  24.     adj[u] = ecnt;
  25. }
  26. void dfs(int u, int pre){
  27.     sze[u] = 1;
  28.     ans[1] += dep[u];
  29.     for(int e = adj[u]; e; e = nxt[e])
  30.         if(go[e] != pre){
  31.             dep[go[e]] = dep[u] + 1;
  32.             dfs(go[e], u);
  33.             sze[u] += sze[go[e]];
  34.         }
  35. }
  36. void change(int u, int pre){
  37.     if(u != 1) ans[u] = ans[pre] + n - 2 * sze[u];
  38.     for(int e = adj[u]; e; e = nxt[e])
  39.         if(go[e] != pre)
  40.             change(go[e], u);
  41. }
  42. int main(){
  43.     n = read();
  44.     for(int i = 1, u, v; i < n; i++)
  45.         scanf("%d%d", &u, &v), add(u, v), add(v, u);
  46.     dfs(1, 0);
  47.     change(1, 0);
  48.     for(int i = 1; i <= n; i++)
  49.         printf("%lld\n", ans[i]);
  50.     return 0;
  51. }

51nod 1419 最小公倍数挑战 | 数论

我们的目的是在[1, n]中找到最大的三个互质的数。

首先，显然 n 和 n - 1 一定互质。
如果 n 是奇数，那么显然 n 和 n - 2 一定互质，直接输出 n * (n - 1) * (n - 2)。
否则 n 是偶数，n、n - 1、n - 2 的最小公倍数是 n * (n - 1) * (n - 2) / 2，是否有比这个数更大的呢？有：如果 n 和 n - 3 互质的话，n * (n - 1) * (n - 3)是一个可行解；如果 n 和 n - 3 不互质的话，(n - 1) * (n - 2) * (n - 3) 是一个可行解。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. ll n;
  9. ll gcd(ll a, ll b){
  10.     return b ? gcd(b, a % b) : a;
  11. }
  12. int main(){
  13.     while(~scanf("%lld", &n)){
  14.         if(n < 3) printf("%lld\n", n);
  15.         else if(n & 1) printf("%lld\n", n * (n - 1) * (n - 2));
  16.         else if(gcd(n, n - 3) == 1) printf("%lld\n", n * (n - 1) * (n - 3));
  17.         else printf("%lld\n", (n - 1) * (n - 2) * (n - 3));
  18.     }
  19.     return 0;
  20. }

51nod 1412 AVL树的种类 | DP

dp[i][j]表示节点数为i、深度为j

dp[i][j] = dp[k][j - 1] * dp[i - 1 - k][j - 1] + 2 * dp[k][j - 2] * dp[i - 1 - k][j - 1]

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N = 2005, J = 16, P = 1000000007;
  9. int n = 2000;
  10. ll dp[N][J], ans;
  11. int main(){
  12.     dp[0][0] = dp[1][1] = 1;
  13.     for(int i = 2; i <= n; i++)
  14.         for(int j = 2; j <= 15; j++)
  15.             for(int k = 0; k < i; k++){
  16.                 dp[i][j] = (dp[i][j] + dp[k][j - 1] * dp[i - k - 1][j - 1] % P) % P;
  17.                 dp[i][j] = (dp[i][j] + 2 * dp[k][j - 2] * dp[i - k - 1][j - 1] % P) % P;
  18.             }
  19.     while(~scanf("%d", &n)){
  20.         ans = 0;
  21.         for(int j = 1; j <= 15; j++)
  22.             ans = (ans + dp[n][j]) % P;
  23.         printf("%lld\n", ans);
  24.     }
  25.     return 0;
  26. }

51nod 1435 位数阶乘

X是一个n位数的正整数 (x=a0a1...an−1)
现在定义 F(x) 比如F(135)=1!*3!*5!=720.
我们给定一个n位数的整数X(至少有一位数大于1，X中可能有前导0)，
然后我们去找一个正整数(s)符合以下条件：
1.这个数尽可能大，
2.这个数中不能含有数字0或1。
3.F(s)=F(x)

每个数分解德越长越好。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <cstdlib>
  7. #include <ctime>
  8. #define INF 0x3f3f3f3f
  9. using namespace std;
  10. typedef long long ll;
  12. const int N = 105;
  13. const int tb[10][10] = {
  14.     {0},
  15.     {0},
  16.     {1, 2},
  17.     {1, 3},
  18.     {3, 3, 2, 2},
  19.     {1, 5},
  20.     {2, 5, 3},
  21.     {1, 7},
  22.     {4, 7, 2, 2, 2},
  23.     {4, 7, 3, 3, 2}
  24. };
  25. ll n;
  26. int cnt, s[N];
  28. int main(){
  29.     scanf("%lld%lld", &n, &n);
  30.     while(n){
  31.         int t = n % 10;
  32.         for(int i = 1; i <= tb[t][0]; i++)
  33.             s[++cnt] = tb[t][i];
  34.         n /= 10;
  35.     }
  36.     sort(s + 1, s + cnt + 1);
  37.     for(int i = cnt; i; i--)
  38.         putchar(s[i] + '0');
  39.     putchar('\n');
  40.     return 0;
  41. }

51nod 1403 有趣的堆栈 | 输入输出优化……

大家都熟悉堆栈操作。一个堆栈一般有两种操作，push和pop。假设所有操作都是合法的并且最终堆栈为空。我们可以有很多方法记录堆栈的操作，
（1） 对每个pop操作，我们记录它之前一共有多少个push操作。
（2） 对每个pop操作，我们记录这个被Pop的元素曾经被压上了几个。
例如：操作push, push, pop, push, push, pop, push, pop, pop, pop
用第一种方法 记录为 2, 4, 5, 5, 5
用第二种方法 记录为 0, 0, 0, 2, 4
这两种记录方法可以互相转化，我们的问题是，给定第二种记录方法的序列，请求出第一种记录方法的序列。

对于每个pop，根据它被压了几个，可以知道它是什么时候push的（是在哪个pop之前push的），然后求前缀和即可。

  1. #include <stdio.h>
  3. int read(){
  4.     bool op = 0;
  5.     char c;
  6.     while((c = getchar()) < '0' || c > '9')
  7.         if(c == '-') op = 1;
  8.     int ret = c - '0';
  9.     while((c = getchar()) >= '0' && c <= '9')
  10.         ret = ret * 10 + c - '0';
  11.     return ret;
  12. }
  13. void write(int x){
  14.     if(x < 0) putchar('-'), x = -x;
  15.     if(x > 10) write(x / 10);
  16.     putchar('0' + x % 10);
  17. }
  18. const int N = 1000005;
  19. int n, cnt[N];
  20. int main(){
  21.     n = read();
  22.     for(int i = 1; i <= n; i++)
  23.         cnt[i - read()]++;
  24.     for(int i = 1; i <= n; i++){
  25.         cnt[i] += cnt[i - 1];
  26.         printf("%d ", cnt[i]);
  27.     }
  28.     putchar('\n');
  29.     return 0;
  30. }

51nod 1354 选数字 | dp 离散化

当给定一个序列a[0],a[1],a[2],...,a[n-1] 和一个整数K时，我们想找出,有多少子序列满足这么一个条件：把当前子序列里面的所有元素乘起来恰好等于K。
样例解释：
对于第一个数据，我们可以选择[3]或者[1(第一个1), 3]或者[1(第二个1), 3]或者[1,1,3]。所以答案是4。

K虽然很大，但是根据超强的学姐的估计上界和随机，K的约数一般不超过700个！

那么我们把约数求出来，放在lst数组中，然后dp[i][j]表示前i个数组成的乘积为lst[j]的子序列数目。

那么：
dp[i][j] = dp[i - 1][j];
if(lst[j] % a[i] == 0) dp[i][j] += dp[i - 1][lst[j] / a[i]];

  1. #include <stdio.h>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. typedef long long ll;
  6. int read(){
  7.     bool op = 0;
  8.     char c;
  9.     while((c = getchar()) < '0' || c > '9')
  10.         if(c == '-') op = 1;
  11.     int ret = c - '0';
  12.     while((c = getchar()) >= '0' && c <= '9')
  13.         ret = ret * 10 + c - '0';
  14.     return ret;
  15. }
  16. void write(int x){
  17.     if(x < 0) putchar('-'), x = -x;
  18.     if(x > 10) write(x / 10);
  19.     putchar('0' + x % 10);
  20. }
  21. const int N = 1005, M = 20005, P = 1000000007;
  22. int T, n, k, a[N], lst[M], dp[M];
  23. int main(){
  24.     T = read();
  25.     while(T--){
  26.         memset(dp, 0, sizeof(dp));
  27.         n = read(), k = read();
  28.         //printf("%d %d\n", n, k);
  29.         int cnt = 0;
  30.         for(int i = 1; (ll) i*i <= (ll) k; i++){
  31.             if(k % i == 0){
  32.                 lst[++cnt] = i;
  33.                 if(i*i < k) lst[++cnt] = k / i;
  34.             }
  35.         }
  36.         sort(lst + 1, lst + cnt + 1);
  37.         for(int i = 1; i <= n; i++)
  38.             a[i] = read();
  39.         dp[1] = 1;
  40.         for(int i = 1; i <= n; i++)
  41.             for(int j = cnt; j; j--){
  42.                 if(lst[j] % a[i] == 0)
  43.                     dp[j] = (dp[j] + dp[lower_bound(lst + 1, lst + cnt + 1, lst[j] / a[i]) - lst]) % P;
  44.             }
  45.         printf("%d\n", dp[cnt]);
  47.     }
  48.     return 0;
  49. }

@ 滚动数组……忘了把j反过来了………………GG………………

51nod 1364 最大字典序排列 | 线段树

给出一个1至N的排列，允许你做不超过K次操作，每次操作可以将相邻的两个数交换，问能够得到的字典序最大的排列是什么？
例如：N = 5， {1 2 3 4 5}，k = 6，在6次交换后，能够得到的字典序最大的排列为{5 3 1 2 4}。
Input
第1行：2个数N, K中间用空格分隔（1 <= N <= 100000, 0 <= K <= 10^9)。
第2至N + 1行：每行一个数i（1 <= i <= N)。
Output
输出共N行，每行1个数，对应字典序最大的排列的元素。

我好菜啊……写了两个线段树……

每次把能移到最左侧的数中最大的移到最左侧即可。

  1. #include <stdio.h>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. typedef long long ll;
  6. int read(){
  7.     bool op = 0;
  8.     char c;
  9.     while((c = getchar()) < '0' || c > '9')
  10.         if(c == '-') op = 1;
  11.     int ret = c - '0';
  12.     while((c = getchar()) >= '0' && c <= '9')
  13.         ret = ret * 10 + c - '0';
  14.     return ret;
  15. }
  16. void write(int x){
  17.     if(x < 0) putchar('-'), x = -x;
  18.     if(x > 10) write(x / 10);
  19.     putchar('0' + x % 10);
  20. }
  21. const int N = 100005;
  22. int n, m;
  23. int a[N], pos[N], data[4 * N], ans[N];
  24. int sum[4*N];
  25. //pos[i]: i在原序列中的位置
  26. void build(int k, int l, int r){
  27.     if(l == r) return (void)(data[k] = a[l]);
  28.     int mid = (l + r) >> 1;
  29.     build(k << 1, l, mid);
  30.     build(k << 1 | 1, mid + 1, r);
  31.     data[k] = max(data[k << 1], data[k << 1 | 1]);
  32. }
  33. int query(int k, int l, int r, int ql, int qr){
  34.     if(ql <= l && qr >= r) return data[k];
  35.     int mid = (l + r) >> 1, ret = 0;
  36.     if(ql <= mid) ret = max(ret, query(k << 1, l, mid, ql, qr));
  37.     if(qr > mid) ret = max(ret, query(k << 1 | 1, mid + 1, r, ql, qr));
  38.     return ret;
  39. }
  40. void remove(int k, int l, int r, int p){
  41.     if(l == r) return (void)(data[k] = 0);
  42.     int mid = (l + r) >> 1;
  43.     if(p <= mid) remove(k << 1, l, mid, p);
  44.     else remove(k << 1 | 1, mid + 1, r, p);
  45.     data[k] = max(data[k << 1], data[k << 1 | 1]);
  46. }
  47. void build2(int k, int l, int r){
  48.     if(l == r) return (void)(sum[k] = 1);
  49.     int mid = (l + r) >> 1;
  50.     build2(k << 1, l, mid);
  51.     build2(k << 1 | 1, mid + 1, r);
  52.     sum[k] = sum[k << 1] + sum[k << 1 | 1];
  53. }
  54. void remove2(int k, int l, int r, int p){
  55.     if(l == r) return (void)(sum[k] = 0);
  56.     int mid = (l + r) >> 1;
  57.     if(p <= mid) remove2(k << 1, l, mid, p);
  58.     else remove2(k << 1 | 1, mid + 1, r, p);
  59.     sum[k] = sum[k << 1] + sum[k << 1 | 1];
  60. }
  61. int findxth(int k, int l, int r, int x){ //找到现存的第x个数
  62.     if(l == r) return l;
  63.     int mid = (l + r) >> 1;
  64.     if(sum[k << 1] >= x) return findxth(k << 1, l, mid, x);
  65.     return findxth(k << 1 | 1, mid + 1, r, x - sum[k << 1]);
  66. }
  67. int count(int k, int l, int r, int ql, int qr){ //找到序列中[ql, qr]还有多少剩的
  68.     if(ql <= l && qr >= r) return sum[k];
  69.     int mid = (l + r) >> 1, ret = 0;
  70.     if(ql <= mid) ret += count(k << 1, l, mid, ql, qr);
  71.     if(qr > mid) ret += count(k << 1 | 1, mid + 1, r, ql, qr);
  72.     return ret;
  73. }
  74. int main(){
  75.     n = read(), m = read();
  76.     for(int i = 1; i <= n; i++)
  77.         a[i] = read(), pos[a[i]] = i;
  78.     build(1, 1, n);
  79.     build2(1, 1, n);
  80.     for(int t = 1; t <= n; t++){
  81.         ans[t] = query(1, 1, n, 1, findxth(1, 1, n, min(sum[1], m + 1)));
  82.         int p = pos[ans[t]];
  83.         remove(1, 1, n, p);
  84.         remove2(1, 1, n, p);
  85.         m -= count(1, 1, n, 1, p);
  86.     }
  87.     for(int i = 1; i <= n; i++)
  88.         printf("%d\n", ans[i]);
  89.     return 0;
  90. }

51nod 1406 与查询 | 位运算

有n个整数。输出他之中和x相与之后结果为x的有多少个。x从0到1，000，000
Input
第一行输入一个整数n。(1<=n<=1,000,000).
第二行有n个整数a[0],a[1],a[2],...a[n-1]，以空格分开.(0<=a[i]<=1,000,000)
Output
对于每一组数据，输出1000001行，第i行对应和i相与结果是i的有多少个数字。

一开始想先枚举i（数）再枚举j（位），然后重复了……
其实先枚举j后枚举i就可以了。

  1. #include <cstdio>
  2. using namespace std;
  3. int read(){
  4.     char c; bool op = 0;
  5.     while((c = getchar()) < '0' || c > '9')
  6.         if(c == '-') op = 1;
  7.     int ret = c - '0';
  8.     while((c = getchar()) >= '0' && c <= '9')
  9.         ret = ret * 10 + c - '0';
  10.     return ret;
  11. }
  12. void write(int x){
  13.     if(x < 0) x = -x, putchar('-');
  14.     if(x >= 10) write(x / 10);
  15.     putchar('0' + x % 10);
  16. }
  17. const int N = 1000000;
  18. int n, cnt[N + 3];
  19. int main(){
  20.     n = read();
  21.     for(int i = 1; i <= n; i++)
  22.         cnt[read()]++;
  23.     for(int j = 19; j >= 0; j--)
  24.         for(int i = N; i; i--)
  25.             if(i >> j & 1)
  26.                 cnt[i ^ (1 << j)] += cnt[i];
  27.     for(int i = 0; i <= N; i++)
  28.         write(cnt[i]), putchar('\n');
  29.     return 0;
  30. }

51nod 1383 整数分解为2的幂 | DP

任何正整数都能分解成2的幂，给定整数N，求N的此类划分方法的数量！由于方案数量较大，输出Mod 1000000007的结果。
比如N = 7时，共有6种划分方法。

7=1+1+1+1+1+1+1
=1+1+1+1+1+2
=1+1+1+2+2
=1+2+2+2
=1+1+1+4
=1+2+4

dp[1] = 1;
if(i & 1) dp[i] = dp[i - 1]; //奇数，必有单独的1
else dp[i] = dp[i - 1] + dp[i / 2]; //偶数，前一种情况有单独的1，后一种情况没有单独的1

  1. #include <cstdio>
  2. using namespace std;
  3. const int N = 1000005, P = 1000000007;
  4. int n, f[N];
  5. int main(){
  6.     scanf("%d", &n);
  7.     f[1] = 1;
  8.     for(int i = 2; i <= n; i += 2)
  9.         f[i + 1] = f[i] = (f[i - 1] + f[i/2]) % P;
  10.     printf("%d\n", f[n]);
  11.     return 0;
  12. }

返回顶部

[1] 割点：去掉一个点后，图中存在不连通的点，则这个点是割点。 ↩
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注