題目連結：傳送門
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;
}