周一
A. Luntik and Concerts（思维）
比赛的时候写的比较复杂，分类讨论
注意a, b, c >= 1
另S = a + b * 2 + c * 3
那么可以组成0~S的任何数
可以用贪心放，先放3，再放2，再放1，这样一定可以放完
可以讨论每次3有没有放完，2有没有放完
所以答案就看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;int main()
{ int T; scanf("%d", &T);while(T--){ll a, b, c;scanf("%lld%lld%lld", &a, &b, &c);ll sum = a + b * 2 + c * 3;printf("%d\n", sum % 2);}return 0;
}D. Vupsen, Pupsen and 0（构造）
很快想到了构造方法，处理奇数的部分出了点问题
我用的式子里有两个数相减，没有考虑可能为0，交上去WA了
于是我就干脆找两个不相同的数相减，特殊情况所有数都相同很好处理
但是我这样写绝对值会变大，就不知道该怎么处理
后来不管了先交，结果AC了
之后看题解发现，如果是奇数情况，最大值一定是1e5-1，也就是最大值-1
所以绝对值多一个数是没关系的。比赛时没想到
还有一点是，构造的时候可以选择两个数相减，也可以选择两个数相加
选两个数相加不为0会好点，因为三个数里面，都不为0，一定存在两个数相加不为0
#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 = 1e5 + 10;
int a[N], b[N], n;int main()
{ int T; scanf("%d", &T);while(T--){scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);if(n % 2 == 0){_for(i, 1, n){if(i <= n / 2) printf("%d ", -a[n - i + 1]);else printf("%d ", a[n - i + 1]);}puts("");}else{int p1 = 1, p2 = -1, p3;_for(i, 2, n)if(a[p1] != a[i]){p2 = i;break;}if(p2 == -1){printf("2 ");_for(i, 2, n / 2) printf("1 ");_for(i, n / 2 + 1, n) printf("-1 ");puts("");continue;}_for(i, 1, n)if(i != p1 && i != p2){p3 = i;break;}_for(i, 1, n) b[i] = 0;int A1 = a[p1], A2 = a[p2], A3 = a[p3];b[p1] = -A3;b[p2] = A3;b[p3] = A1 - A2;vector<int> ve;_for(i, 1, n)if(!b[i])ve.push_back(i);for(int i = 0; i < ve.size(); i += 2){int l = ve[i], r = ve[i + 1];b[l] = a[r];b[r] = -a[l];}_for(i, 1, n) printf("%d ", b[i]); puts("");}}return 0;
}F1. Korney Korneevich and XOR (easy version)（dp）
这是一道dp
看数据范围，可以n * v的 也就是两个循环
这里的关键是怎么保证a的值递增
也就是i < j 且ai < aj
i < j用循环1到n来保证
ai < aj的话，枚举所有异或值，记录每一个异或值对应的最小的a[i]
如果ai < aj就可以转移
最后注意a最大值为500，但异或可能变大，到最接近它的2 ^ n - 1 也就是511
枚举值域的时候注意
#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 = 1e5 + 10;
int dp[N], a[N], n;int main()
{ scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);memset(dp, 0x3f, sizeof dp);dp[0] = -1;_for(i, 1, n)_for(j, 0, 512)if(dp[j] < a[i])dp[j ^ a[i]] = min(dp[j ^ a[i]], a[i]);vector<int> ans;_for(i, 0, 512) if(dp[i] < 1e9)ans.push_back(i);printf("%d\n", ans.size());for(int x: ans) printf("%d ", x); puts(""); return 0;
}周二
Tree Constructer（构造 + 二分图）
完全没往二分图这个方向想
树也是二分图，因为可以分层染色，使得节点分成两份，同一份之间没有边相连
直接分层黑白染色分成两份
首先保证同一份之间没有连边，可以在左边的点最高位全部为0，右边的点最高位为1次高位为0
然后给左边分配id，id位为0其他都为1，然后与其相连的右边点都id为1，其他为0
这样构造就刚好符合题目条件
这里注意需要id+2位，n等于100 只有60位
所以选点数小的做为左边的点
#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 = 100 + 10;
int g[N][N], ans[N][N], n, cnt;
vector<int> v1, v2;void dfs(int u, int fa, int d)
{if(d % 2) v1.push_back(u);else v2.push_back(u);_for(v, 0, 100)if(g[u][v]){if(v == fa) continue;dfs(v, u, d + 1);}
}int main()
{ scanf("%d", &n);_for(i, 1, n - 1){int u, v;scanf("%d%d", &u, &v);g[u][v] = g[v][u] = 1;}dfs(1, 0, 0);if(v1.size() > v2.size()) swap(v1, v2);for(int u: v1){_for(i, 1, 59) ans[u][i] = 1;++cnt;ans[u][cnt] = 0;_for(v, 1, n)if(g[u][v])ans[v][cnt] = 1;}for(int v: v2) ans[v][60] = 1;_for(i, 1, n){ll x = 0;for(int j = 60; j >= 1; j--)x = x * 2 + ans[i][j];printf("%lld ", x);}return 0;
}E. Pchelyonok and Segments（dp）
其实不是特别难的dp
dp[i][j]表示后i个，最大长度为j的和的最大值
可以分i是不是成不成为一段来写转移方程
注意边界条件和细节
首先j=0时要赋成最大值，表示一定可以转移
j!=0时赋为最小值，表示不合法
注意是i = n + 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;typedef long long ll;
const int N = 2e5 + 10;
const int M = 450;
int dp[N][M], n;
ll a[N], s[N];int main()
{ int T; scanf("%d", &T);while(T--){scanf("%d", &n);_for(i, 1, n) {scanf("%lld", &a[i]);s[i] = s[i - 1] + a[i];}int k = 1;while((k + 1) * (k + 2) / 2 <= n) k++;_for(j, 1, k) dp[n + 1][j] = 0;dp[n + 1][0] = 2e9;for(int i = n; i >= 1; i--)_for(j, 0, k){dp[i][j] = dp[i + 1][j];if(j && i + j - 1 <= n && s[i + j - 1] - s[i - 1] < dp[i + j][j - 1])dp[i][j] = max((ll)dp[i][j], s[i + j - 1] - s[i - 1]);}for(int i = k; i >= 1; i--)if(dp[1][i] > 0){printf("%d\n", i);break;}}return 0;
}D. Red-Green Towers（dp统计方案数）
同一题在不同的题单遇到
背包统计方案数
然后根据上下界统计答案就好了
注意下界要大于等于0，因为可能算出负值
#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 = 2e5 + 10;
const int mod = 1e9 + 7;
int dp[N], r, g, h;int main()
{ scanf("%d%d", &r, &g);while((h + 1) * (h + 2) / 2 <= r + g) h++;dp[0] = 1;_for(i, 1, h)for(int j = r; j >= i; j--)dp[j] = (dp[j] + dp[j - i]) % mod;int ans = 0;_for(i, max(h * (h + 1) / 2 - g, 0), r)ans = (ans + dp[i]) % mod;printf("%d\n", ans);return 0;
}E. Number of Simple Paths（思维）
如果是树的话，两两之间只有一条路径，很容易统计
然后加了一条边，我想统计因为这条边而增加的路径，也就是经过这条边的路径，发现非常复杂，很难统计，就不知道了
看了题解，一颗树加一条边就是基环树
可以看成一个环，然后环上的一些节点挂着一颗树
这个时候发现很多两点之间都有两条路径
发现只有在一颗树上才是两两之间一条路径，所以统计树的节点个数减去就好了
实现上，无向图找环就用类似拓扑排序，度数为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;typedef long long ll;
const int N = 2e5 + 10;
vector<int> g[N];
int degree[N], vis[N], n, cnt;void dfs(int u, int fa)
{cnt++;for(int v: g[u]){if(v == fa || !vis[v]) continue;dfs(v, u);}
}int main()
{ int T; scanf("%d", &T);while(T--){scanf("%d", &n);_for(i, 1, n) g[i].clear(), vis[i] = 0, degree[i] = 0;_for(i, 1, n){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);degree[u]++; degree[v]++;}queue<int> q;_for(i, 1, n)if(degree[i] == 1)q.push(i);while(!q.empty()){int u = q.front(); q.pop();vis[u] = 1;for(int v: g[u])if(--degree[v] == 1)q.push(v);}ll res = 1LL * n * (n - 1);_for(i, 1, n)if(!vis[i]){cnt = 0;dfs(i, 0);res -= 1LL * cnt * (cnt - 1) / 2;}printf("%lld\n", res);}return 0;
}周三
E. Compress Words（kmp）
字符串匹配用kmp
每次用kmp匹配最长的后缀等于前缀就行了
#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 Next[N], lens, lena, n;
string s, ans;void get_next()
{Next[0] = -1;int i = 0, j = -1;lens = s.size();while(i < lens){if(j == -1 || s[i] == s[j]) {i++; j++;Next[i] = j;}else j = Next[j];}
}int kmp()
{int j = 0, i = max(lena - lens, 0);while(i < lena){if(j == -1 || ans[i] == s[j]) i++, j++;else j = Next[j];}return j;
}int main()
{ scanf("%d", &n);cin >> ans;lena = ans.size();_for(i, 2, n){cin >> s;get_next();int j = kmp();ans += string(s, j);lena += lens - j;}cout << ans << endl;return 0;
}D. Book of Evil（树的直径）
对树的直径不熟导致没做出来
有一个很重要的性质，离一个点距离最远的点一定是树的直径的端点之一
因此求树的直径可以随便找一个点，找最远点，那就是端点之一，然后再以那个端点为起点就可以找到另一个端点
这道题，其实就是求特殊点的直径
每一个点离它最远的特殊点一定是直径之一
#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 = 1e5 + 10;
int d1[N], d2[N], p[N], k[N], n, m, maxd, s1, s2, t;
vector<int> g[N];void dfs(int u, int fa, int& s, int* d)
{d[u] = d[fa] + 1;if(p[u] && d[u] > d[s]) s = u;for(int v: g[u]){if(v == fa) continue;dfs(v, u, s, d);}
}int main()
{ scanf("%d%d%d", &n, &m, &maxd);_for(i, 1, m){int x; scanf("%d", &x);p[x] = 1;}_for(i, 1, n - 1){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs(1, 0, s1, k); dfs(s1, 0, s2, d1);dfs(s2, 0, t, d2);int ans = 0;_for(i, 1, n)if(d1[i] - 1 <= maxd && d2[i] - 1 <= maxd)ans++;printf("%d\n", ans);return 0;
}周日
Simone and Graph Coloring（贪心 + 线段树）
首先是贪心，每次选能选的最小的
然后可以发现，与其相连的一定是比它大的，因此这些的颜色一定是连续的
所以用线段树维护区间最大值最小值就好了
写的时候有细节需要注意
1.查询操作的时候有时候会出现 R > L的情况，这种情况要考虑怎么处理
2.统计答案的时候，若第一个先赋值了，那么ans就要赋第一个对应的答案。
#include <bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#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 t[N << 4][2];
int a[N], c[N], ans, n;void up(int k)
{t[k][0] = max(t[l(k)][0], t[r(k)][0]);t[k][1] = min(t[l(k)][1], t[r(k)][1]);
}void build(int k, int l, int r)
{if(l == r){t[k][1] = 1e9;t[k][0] = 0;return;}int m = l + r >> 1;build(l(k), l, m);build(r(k), m + 1, r);up(k);
}void add(int k, int l, int r, int x, int p)
{if(l == r){t[k][0] = t[k][1] = p;return;}int m = l + r >> 1;if(x <= m) add(l(k), l, m, x, p);else add(r(k), m + 1, r, x, p);up(k);
}int query0(int k, int l, int r, int L, int R)
{if(L <= l && r <= R) return t[k][0];int m = l + r >> 1, res = 0;if(L <= m) res = max(res, query0(l(k), l, m, L, R));if(R > m) res = max(res, query0(r(k), m + 1, r, L, R));return res;
}int query1(int k, int l, int r, int L, int R)
{if(L <= l && r <= R) return t[k][1];int m = l + r >> 1, res = 1e9;if(L <= m) res = min(res, query1(l(k), l, m, L, R));if(R > m) res = min(res, query1(r(k), m + 1, r, L, R));return res;
}int main()
{ int T; scanf("%d", &T);while(T--){scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);build(1, 1, n);c[1] = 1; ans = 1; //ans = 1关键！！add(1, 1, n, a[1], c[1]);_for(i, 2, n){if(a[i] == n) c[i] = 1; // ！！else{int mx = query0(1, 1, n, a[i] + 1, n);int mi = query1(1, 1, n, a[i] + 1, n);if(mi > 1) c[i] = 1;else c[i] = mx + 1;}add(1, 1, n, a[i], c[i]);ans = max(ans, c[i]);}printf("%d\n", ans);_for(i, 1, n) printf("%d ", c[i]); puts(""); }return 0;
}Parallel Sort（思维）
首先，我们可以让一个数到它应该去的位置连一个有向边
这样就可以形成很多个不相交的环
一个位置有一条入边，一条出边，如果环相交就不满足这个条件
那么其实就是要看一个环怎么处理
这个挺巧妙的，是队友想到了
先一次对称变换，然后就可以两两交换了
画个图就知道了
#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 = 1e5 + 10;
int g[N], vis[N], cnt, n;
vector<int> c[N];void dfs(int u, int id)
{if(vis[u]) return;vis[u] = 1;c[id].push_back(u);dfs(g[u], id);
}int main()
{ scanf("%d", &n);_for(i, 1, n) {int x; scanf("%d", &x);g[x] = i;}int ok = 0;_for(i, 1, n){if(g[i] == i) continue;if(!vis[i]) dfs(i, ++cnt);ok = 1;}if(!ok){puts("0");return 0;}vector<int> pr[2];_for(i, 1, cnt){vector<int> t = c[i];int l = 0, r = t.size() - 1;while(l < r){pr[0].push_back(t[l]); pr[0].push_back(t[r]); l++; r--;}l = 0, r = t.size() - 2;while(l < r){pr[1].push_back(t[l]); pr[1].push_back(t[r]); l++; r--;}}if(pr[1].size()) printf("%d\n", 2);else printf("%d\n", 1);printf("%d", pr[0].size() / 2);for(int x: pr[0]) printf(" %d", x); puts("");if(pr[1].size()){printf("%d", pr[1].size() / 2);for(int x: pr[1]) printf(" %d", x); puts("");}return 0;
}