周三
P3586 [POI2015]LOG（猜结论 + 动态开点线段树）
首先猜一个结论
大于等于s的肯定可以选
小于s的和只要大于剩下要选的数乘以s就行了
用动态开点线段树维护
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e6 + 10;
int ls[N << 6], rs[N << 6], a[N], cnt, n, m, root; //注意root一定一开始设为0
ll t1[N << 6], t2[N << 6];void up(int k)
{ t1[k] = t1[ls[k]] + t1[rs[k]];t2[k] = t2[ls[k]] + t2[rs[k]];
}void modify(int& k, int l, int r, int x, int p)
{if(!k) k = ++cnt; //动态开点if(l == r){t2[k] += p;t1[k] = t2[k] * x;return;}int m = l + r >> 1;if(x <= m) modify(ls[k], l, m, x, p);else modify(rs[k], m + 1, r, x, p);up(k);
}ll query1(int k, int l, int r, int L, int R)
{if(!k) return 0; //询问时询问到空节点返回0if(L <= l && r <= R) return t1[k];int m = l + r >> 1; ll res = 0;if(L <= m) res += query1(ls[k], l, m, L, R);if(R > m) res += query1(rs[k], m + 1, r, L, R);return res;
}int query2(int k, int l, int r, int L, int R)
{if(!k) return 0;if(L <= l && r <= R) return t2[k];int m = l + r >> 1, res = 0;if(L <= m) res += query2(ls[k], l, m, L, R);if(R > m) res += query2(rs[k], m + 1, r, L, R);return res;
}int main()
{scanf("%d%d", &n, &m);modify(root, 0, 1e9, 0, n); while(m--){char op[5]; int x, y;scanf("%s%d%d", op, &x, &y);if(op[0] == 'U'){modify(root, 0, 1e9, a[x], -1); modify(root, 0, 1e9, a[x] = y, 1);}else{int t = query2(root, 0, 1e9, y, 1e9);ll sum = query1(root, 0, 1e9, 0, y - 1); if(sum >= 1LL * (x - t) * y) puts("TAK");else puts("NIE");}}return 0;
}P3809 【模板】后缀排序
后缀数组模板
/*sa[i] 排名为i的后缀的位置height lcp(sa[i], sa[i - 1]) 即排名为i的后缀与排名为i?1的后缀的最长公共前缀H[i]：height[rak[i]]，即i号后缀与它前一名的后缀的最长公共前缀最长公共子串（可重叠） height数组最大值 因为最长公共前缀的两个子串的排名一定相邻本质不同的字串数目 枚举每一个后缀i 对答案的贡献为 len ? sa[i] + 1 ? height[i]两个后缀的最大公共前缀 令x=rank[i],y=rank[j]，x < y,那么lcp(i,j)=min(height[x+1],height[x+2]…height[y])。lcp(i,i)=n-sa[i]。 用ST表或线段树
*/#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e6 + 10;
int x[N], y[N], c[N], sa[N], rk[N], height[N], wt[30];
int n, m;
char s[N];void get_SA()
{_for(i, 1, n) ++c[x[i] = s[i]];_for(i, 2, m) c[i] += c[i - 1];for(int i = n; i >= 1; i--) sa[c[x[i]]--] = i;for(int k = 1; k <= n; k <<= 1){int num = 0;_for(i, n - k + 1, n) y[++num] = i;_for(i, 1, n) if(sa[i] > k) y[++num] = sa[i] - k;_for(i, 1, m) c[i] = 0;_for(i, 1, n) ++c[x[i]];_for(i, 2, m) c[i] += c[i - 1];for(int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;swap(x, y);x[sa[1]] = 1; num = 1;_for(i, 2, n) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;if(num == n) break;m = num;}
}void get_height()
{int k = 0;_for(i, 1, n) rk[sa[i]] = i;_for(i, 1, n){if(rk[i] == 1) continue;if(k) k--;int j = sa[rk[i] - 1];while(j + k <= n && i + k <= n && s[i + k] == s[j + k]) k++;height[rk[i]] = k;}
}int main()
{scanf("%s", s + 1);n = strlen(s + 1);m = 122; //m表示字符个数 ascll('z')=122 //桶的范围是1~mget_SA();_for(i, 1, n) printf("%d ", sa[i]);return 0;
}周日
最近做了一些题，一直没整理，现在整理一下
之后的比赛心态一定要好，冷静而有压力
不要太紧张，太想比好
bzoj 1406（因数）
可以推出n | (x + 1)(x - 1)
令n = a * b
a | (x + 1) 且 b | (x - 1)
或
b | (x + 1) 且 a | (x - 1)
因此根号枚举因子，然后枚举因子的倍数即可
枚举后半段因子的倍数显然更优秀
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;set<int> ans;int main()
{int n; scanf("%d", &n);for(int a = 1; a * a <= n; a++)if(n % a == 0){int b = n / a;for(int i = 0; i < n - 1; i += b) if((i + 2) % a == 0) ans.insert(i + 1);for(int i = b; i < n + 1; i += b) if((i - 2) % a == 0) ans.insert(i - 1);}if(ans.empty()) puts("None");else for(int x: ans) printf("%d\n", x);return 0;
}
CF877D Olya and Energy Drinks（bfs + 剪枝）
这题关键是剪枝
我写的时候，剪少了就T，剪多了就WA
关键是拓展的时候
如果f[x][y] + 1> f[xx][yy]
这时候直接break了因为之后的点都可以通过f[xx][yy]去拓展，时间一样
如果f[x][y] + 1 == f[xx][yy] 这个时候不加入队列，但要继续拓展
接下来可能可以拓展到更加优秀的点
其实并不难，只是太紧张了没想到
今晚比赛一定沉下心，冷静，以平常心去对待
今晚的对手是我自己，不是别人。是对自己的心态
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int f[N][N], n, m, k;
char s[N][N];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
struct node
{int x, y, step;
};int main()
{scanf("%d%d%d", &n, &m, &k);_for(i, 1, n) scanf("%s", s[i] + 1);int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);queue<node> q;q.push(node{x1, y1, 0});memset(f, 0x3f, sizeof f);f[x1][y1] = 0;while(!q.empty()){node u = q.front(); q.pop();int x = u.x, y = u.y;if(u.step != f[x][y]) continue;rep(j, 0, 4)_for(i, 1, k){int xx = x + dir[j][0] * i, yy = y + dir[j][1] * i;if(xx < 1 || xx > n || yy < 1 || yy > m || s[xx][yy] == '#' || f[xx][yy] <= f[x][y]) break;if(f[x][y] + 1 < f[xx][yy]){f[xx][yy] = f[x][y] + 1;q.push(node{xx, yy, f[xx][yy]});}}}if(f[x2][y2] > 1e9) puts("-1");else printf("%d\n", f[x2][y2]);return 0;
}T199660 tree（递推）
考察了两个递推
首先可以发现，对于n，可以分成几棵相同的树
所以可以先求出一颗树有多少种构造方式
然后再求n个节点有多少构造方式
对于一颗树，可以这么理解
去掉根节点，就剩下n-1个节点，这n-1个节点可以为1颗子树，也就是dp[n - 1]
可以被2整除的话就两颗子树，就dp[(n - 1) / 2]
所以枚举因子就可以了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int mod = 998244353;
const int N = 1e5 + 10;
int dp[N], ans[N], n;int main()
{scanf("%d", &n);dp[1] = dp[2] = 1;_for(i, 3, n)for(int j = 1; j * j <= i - 1; j++)if((i - 1) % j == 0){dp[i] = (dp[i] + dp[j]) % mod;if(j * j != i - 1) dp[i] = (dp[i] + dp[(i - 1) / j]) % mod;}int ans = 0;for(int i = 1; i * i <= n; i++)if(n % i == 0){ans = (ans + dp[i]) % mod;if(i * i != n) ans = (ans + dp[n / i]) % mod;}printf("%d\n", ans);return 0;
}