题目链接：传送门
B-一级棒
（树-路径压缩）
题意：给出一个n，表示有n个节点0~n，0为根结点，随后给出n-1个数表示第i个节点连接的父节点
再给出一个q，随后q次操作：R u v 表示节点u~v之间的路径被访问的次数加1
Eg:5 0 1 1 3 W x 表示请你输出经过x及他的父节点之间这条路被访问的情况
5 若没有被访问过输出"Not yet",若被访问超过2次输出"Many times"
R 2 4 若只被访问过一次输出那次访问的路径端点（Eg：小端点 大端点）
W 3 (输出:2 4）注意：要求输出访问过一次的情况时是输出路径端点（不一定是他和其父节点，试试左边样例）
R 1 2
W 2 (输出:Many times)
W 1 (输出:Not yet)
解法：第一次访问路径u，v，直接对路径中的所有节点都进行访问+1的操作
若访问到被访问过一次的路径时进行对其pre值进行修改为其父节点
（目的：把被访问到第二次的路径都压缩起来，下次不在访问）
若访问到被访问过两次的路径时直接根据其pre的并查集得到压缩路径后的终点（节省时间）
代码如下：
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<iostream>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = 1e5 + 500;
struct node
{
int l, r; //记录第一次访问时的路径端点
int dept; //记录该节点所在层数
int fa; //记录其父节点
int cnt; //对节点的访问次数进行统计（路径压缩后中间节点num最大2）
}tre[maxn];
int pre[maxn];//并查集对树上操作超过2次的操作进行路径压缩处理
int find(int x)
{
if (pre[x] == x)
return x;
return pre[x] = find(pre[x]);
}
void operation(int x, int y)
{
int u = x, v = y;//保留u，v（因为恰好是“一级棒的边”时，要回答恰好经过这条边的路径端点）
while (u != v)
{
if (tre[u].dept < tre[v].dept)swap(u, v); //先对深度大的进行向上前进操作（保证它们能相遇）
tre[u].cnt++;
if (tre[u].cnt == 1)
tre[u].l = min(x, y), tre[u].r = max(x, y);
else
pre[u] = tre[u].fa;
u = find(tre[u].fa);
}
}
int main()
{
int n;
while (~scanf("%d", &n))
{
for (int i = 1; i < n; i++)
{
scanf("%d", &tre[i].fa);
tre[i].dept = tre[tre[i].fa].dept + 1;
tre[i].cnt = 0;
pre[i] = i;
}
int q, u, v;
scanf("%d", &q);
char s[2];
while (q--)
{
scanf("%s", &s);
if (s[0] == 'R')
{
scanf("%d%d", &u, &v);
operation(u, v);
}
else
{
scanf("%d", &u);
if (tre[u].cnt == 0) printf("Not yet\n");
else if (tre[u].cnt == 1)printf("%d %d\n", tre[u].l, tre[u].r);
else printf("Many times\n");
}
}
}
return 0;
}
E-Youhane Assemblerti
（KMP） 题意：给出一个n，随后给你n条字符串（1~n），再给出一个q，表示q次询问，每次询问给出一个u，v，要求返回第u条字符串的后缀字符串和第v条字符串的前缀字符串的最大匹配数（即最大相同个数） 解法：题目保证每个文件只有一组数据而且数据总的字符串长度不会超过3e5，因此每个子串都很短，实际上暴力就可以过（现场数据的确都被暴力过了，然而我用的是KMP）在这里的kmp模板直接返回题目要的答案，不懂可以学一手kmp。 代码如下：
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<stdio.h>
#include<iostream>
using namespace std;
#define ll long long
const int maxn = 3e5 + 500;
string s[maxn];
int nxt[maxn];
void get_next(int y)
{
int len = s[y].length();
int i = 0, j = -1;
nxt[0] = -1;
while (i<len)
{
if (j == -1 || s[y][i] == s[y][j])
{
i++;
j++;
nxt[i] = j;
}
else
j = nxt[j];
}
}
int kmp(int x, int y)
{
int len1 = s[x].length(), len2 = s[y].length();
int i = 0, j = 0;
get_next(y);
while (i<len1)
{
if (j == -1 || s[x][i] == s[y][j])
{
i++;
j++;
}
else
j = nxt[j];
}
if (i == len1)
return j;
return 0;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> s[i];
int q,x,y;
cin >> q;
while (q--)
{
scanf("%d%d", &x, &y);
if (x == y)cout << s[x].length() << endl;
else
cout << kmp(x, y) << endl;
}
return 0;
}
G-Youhane as "Bang Riot"
（暴力剪枝） 题意：给出一个n，随后有2行，第一行n个数表示a[i],第二行n个数表示b[i]，题目想要输出全部a[i]且付出的代价最小，代价公式如下
因此可以选择一次输出一个也可以连续输出几个，只要求最后的代价最小值即可。
解法：正解我觉得是斜率优化DP（本人不怎么会）因此在此的解法为根据题目的数据进行巧妙的剪纸方法，然后直接暴力过。
（因为题目的a[i],b[i]的数据大小为【0，1e3】,因此对cost分析，当a[i]选择单个输出时最大代价为1e6,（在此先定义：sum[i]=a[1]+...+a[i]) )然后当sum[i]-sum[j]>2000时，cost=(2e3-b[i])^2,最小值为1e6，这时候就和单个输出的最大值相同代价了，因此在此可以break。（当然仔细想想感觉，好像有有点出入，因为上面的是单个代价为1e6，下面可能是多个数输出的代价才为1e6，那么2000就只能算是卡出题人数据的最小值吧，不过所幸2000的临界点交上去就ac了，如果不行可以考虑放大些。
代码如下：
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<iostream>
#include<map>
#include<queue>
#include<functional>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
const int maxn = 1e6 + 500;
ll sum[maxn], b[maxn], dp[maxn];
int main() {
int n;
while (~scanf("%d", &n))
{
for (int i = 1; i <= n; i++)
{
scanf("%lld", &sum[i]);
sum[i] += sum[i - 1];
}
for (int i = 1; i <= n; i++)
scanf("%lld", &b[i]);
for (int i = 1; i <= n; i++)
dp[i] = inf;
for (int i = 1; i <= n; i++)
{
for (int j = i - 1; j >= 0; j--)
{
ll tmp = sum[i] - sum[j];
if (tmp > 2000)break;
dp[i] = min(dp[i], dp[j] + (tmp-b[i])*(tmp-b[i]));
}
}
printf("%lld\n", dp[n]);
}
return 0;
}
H-对称与反对称
（水题）
题意：
给出一个N*N的方阵A。构造方阵B,C:
使得A = B + C.其中 B为对称矩阵，C为反对称矩阵。
对于方阵S中的任意元素,若(S)ij = (S)ji,则称S为对称矩阵
对于方阵T中的任意元素,若(T)ij = -(T)ji,则称T为反对称矩阵
注意，所有运算在模M意义下。
对于每组数据，将反对称矩阵C在N行中输出；
若不存在解，则输出"Impossible"；
若存在多解，则输出任意解。
解法：比赛时没有留意M为奇数，故Impossible的情况是不存在的，而B，C方正又取值随意（满足条件下）因此，我们只需要在纸上画一个2*2的B，C方正加起来就可以看出A方正和B,C方正的联系，及C方正左对角线上值都是0，其它（Aij+Aji）/2=Bij=Bji，且Cij=Aij-Bij 或Cij=-（Aij-Bij），因此就可以通过A反正消去B方正得到C方正的值。由于题目说所有数据都要在模运算%M下进行，而我们过程中存在除2运算（所以比赛时我们傻傻的写了一波2的逆元ac过去，不过题不用求2的逆元，因为M为奇数，当（Aij+Aji）为奇数时加一个M就可以了）
//注意最终输出的C方正也要%M
代码如下：
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
#define ll long long
ll a[1500][1500];
int main()
{
ll n, mod;
while (~scanf("%lld%lld", &n, &mod))
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
scanf("%lld", &a[i][j]);
if (i == j)
a[i][j] = 0;
a[i][j] %= mod;
}
int flag = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
{
ll tmp = a[i][j] + a[j][i];
if (tmp % 2 != 0) tmp += mod;
tmp /= 2;
a[i][j] -= tmp + mod; a[i][j] %= mod; a[i][j] += mod; a[i][j] %= mod;
a[j][i] -= tmp + mod; a[j][i] %= mod; a[j][i] += mod; a[j][i] %= mod;
if ((a[i][j]+a[j][i]) % mod != 0)
flag = 1;
}
if (flag)
cout << "Impossible" << endl;
else
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
printf("%lld%c", a[i][j], j == n - 1 ? '\n' : ' ');
}
}
return 0;
}
K-小马哥的超级盐水
（折半枚举法）
题意：小马哥有
杯盐水，第
杯有
单位的盐和
单位的水。小马哥很无聊，于是他想知道有多少种这
杯盐水的非空子集，倒在一起之后盐和水的比是
解法：折半枚举法，因为是求能组合出的所有情况，因此对于每一杯盐水都只有2种状态，取和不取，但是n_max=35，2^35的运算肯定超时，因此需要进行一波折半操作，对于每n杯盐水，我们分为2份，每份最大的讨论情况为2^18<1e6，因此我们可以先分别处理出2部分的所有组合情况，然后选择小部分中的每个数据到另一份数据中进行二分查找，找到满足组合之后值为x/y的数量即可时间复杂度O（nlogn）（这里的n是枚举所有情况的n，不是题目的n了）
代码如下：
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<iostream>
using namespace std;
#define ll long long
const int maxn = 3e5+500;
int n, top1, top2;
ll ans, xx, yy;
struct node
{
ll x, y;
}a[maxn];
ll s1[maxn], s2[maxn];
void dfs1(int i,ll x, ll y)
{
if (i == n / 2) {
s1[top1++] = xx*y - yy*x;
return;
}
dfs1(i + 1, x, y);
dfs1(i + 1, x + a[i].x, y + a[i].y);
}
void dfs2(int i,ll x, ll y)
{
if (i == n) {
s2[top2++] = yy*x - xx*y;
return;
}
dfs2(i + 1, x, y);
dfs2(i + 1, x + a[i].x, y + a[i].y);
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d%lld%lld", &n, &xx, &yy);
for (int i = 0; i < n; i++)
scanf("%lld%lld", &a[i].x, &a[i].y);
top1 = 0; dfs1(0, 0, 0);
top2 = 0; dfs2(n / 2, 0, 0);
ans = 0;
// x s1.x+s2.x
//--- = ------------ => x*s1.y+x*s2.y=y*s1.x+y*s2.x=> x*s1.y-y*s1.x = y*s2.x-x*s2.y
// y s1.y+s2.y
sort(s2, s2 + top2);
for (int i = 0; i < top1; i++)
ans += (upper_bound(s2, s2 + top2, s1[i]) - s2) - (lower_bound(s2, s2 + top2, s1[i]) - s2);
cout << ans - 1 << endl;
}
return 0;
}