A - Fairness

如果奇数次是b - a

否则是a - b

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

//#define ivorysi

using namespace std;

typedef long long int64;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int64 A,B,C,K;

void Solve() {

    read(A);read(B);read(C);read(K);

    if(K & 1) {out(B - A);enter;}

    else {out(A - B);enter;}

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

B - Backfront

找数值最长的连续的一段子序列，然后将剩下的数必须要移动了

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define MAXN 200005

//#define ivorysi

using namespace std;

typedef long long int64;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N,a[MAXN],pos[MAXN],dp[MAXN];

void Solve() {

    read(N);

    for(int i = 1 ; i <= N ; ++i) {

	read(a[i]);

	pos[a[i]] = i;

    }

    dp[1] = 1;

    for(int i = 2 ; i <= N ; ++i) {

	if(pos[i - 1] < pos[i]) dp[i] = dp[i - 1] + 1;

	else dp[i] = 1;

    }

    int res = N;

    for(int i = 1 ; i <= N ; ++i) {

	res = min(res,N - dp[i]);

    }

    out(res);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

C - Sequence Growing Easy

数列肯定是一段连续递增的好几段拼起来，都找到加上最大值就可以了

#include <iostream>

#include <cstdio>

#include <vector>

#include <algorithm>

#include <cmath>

#include <cstring>

//#define ivorysi

#define pb push_back

#define MAXN 200005

#define eps 1e-12

#define space putchar(' ')

#define enter putchar('\n')

#define mp make_pair

#define fi first

#define se second

#define mo 974711

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 - '0' + c;

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) putchar('-'),x = -x;

    while(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N,a[MAXN];

void Solve() {

    read(N);

    for(int i = 1 ; i <= N ; ++i) read(a[i]);

    a[0] = -1;

    for(int i = 1 ; i <= N ; ++i) {

	if(a[i - 1] < a[i] - 1) {

	    puts("-1");

	    return;

	}

    }

    int64 ans = 0;

    for(int i = N ; i >= 1 ; --i) {

	if(a[i] == a[i + 1] - 1) continue;

	ans += a[i];

    }

    printf("%lld\n",ans);

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

D - Isomorphism Freak

答案是直径的长度 / 2 + 1

我们对于直径长度为奇数，也就是有偶数个点，如果直径长度增加颜色也要增加，所以我们不增加直径

我们枚举作为直径中心的两个点，我们能达到这个要求仅当距离中心距离相同的点点度相同即可

对于直径长度为偶数，也就是有奇数个点，我们分两种情况，第一种是只有一个中心

第二种是有两个中心，我们枚举两个中心，然后要求这两个中心所在的树的深度最大的不超过中心的一半即可

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define MAXN 105

//#define ivorysi

using namespace std;

typedef long long int64;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

struct node {

    int to,next;

}E[MAXN * 2];

int N,sumE,head[MAXN],A[MAXN],B[MAXN],dep[MAXN],ch[MAXN],x[MAXN];

void add(int u,int v) {

    E[++sumE].to = v;E[sumE].next = head[u];head[u] = sumE;

}

int Calc(int u,int fa) {

    int res = dep[u];

    ch[u] = 0;

    for(int i = head[u] ; i ; i = E[i].next) {

	int v = E[i].to;

	if(v != fa) {

	    ch[u]++;

	    dep[v] = dep[u] + 1;

	    res = max(res,Calc(v,u));

	}

    }

    return res;

}

void Solve() {

    read(N);

    if(N == 1) {

	puts("1 2");return;

    }

    for(int i = 1 ; i < N ; ++i) {

	read(A[i]);read(B[i]);

	add(A[i],B[i]);add(B[i],A[i]);

    }

    int D = 0;

    for(int i = 1 ; i < N ; ++i) {

	dep[A[i]] = dep[B[i]] = 0;

	D = max(D,Calc(A[i],B[i]) + Calc(B[i],A[i]) + 1);

    }

    out(D / 2 + 1);space;

    if(D & 1) {

	int64 ans = 9e18;

	for(int i = 1 ; i < N ; ++i) {

	    dep[A[i]] = dep[B[i]] = 0;

	    int64 tmp = 2;

	    if(Calc(A[i],B[i]) == D / 2 && Calc(B[i],A[i]) == D / 2) {

		memset(x,0,sizeof(x));

		for(int j = 1 ; j <= N ; ++j) x[dep[j]] = max(x[dep[j]],ch[j]);

		for(int k = 0 ; k < D / 2 ; ++k) tmp = tmp * x[k];

		ans = min(ans,tmp);

	    }

	}

	out(ans);enter;

    }

    else {

	int64 ans = 9e18;

	for(int i = 1 ; i < N ; ++i) {

	    dep[A[i]] = dep[B[i]] = 0;

	    int64 tmp = 1;

	    int x0 = Calc(A[i],B[i]),x1 = Calc(B[i],A[i]);

	    if(x0 > x1) {swap(x0,x1),swap(A[i],B[i]);}

	    if(x0 == D / 2 - 1 && x1 == D / 2) {

		dep[B[i]] = 0;

		Calc(B[i],0);

		memset(x,0,sizeof(x));

		for(int j = 1 ; j <= N ; ++j) x[dep[j]] = max(x[dep[j]],ch[j]);

		for(int k = 0 ; k < D / 2 ; ++k) tmp = tmp * x[k];

		ans = min(ans,tmp);

	    }

	}

	for(int i = 1 ; i < N ; ++i) {

	    dep[A[i]] = dep[B[i]] = 0;

	    int x0 = Calc(A[i],B[i]),x1 = Calc(B[i],A[i]);

	    if(max(x0,x1) <= D / 2) {

		memset(x,0,sizeof(x));

		int64 tmp = 2;

		for(int j = 1 ; j <= N ; ++j) x[dep[j]] = max(x[dep[j]],ch[j]);

		for(int k = 0 ; k <= D ; ++k) {

		    if(x[k]) tmp *= x[k];

		}

		ans = min(ans,tmp);

	    }

	}

	out(ans);enter;

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

E - Sequence Growing Hard

Let's restate the problem = =

我们就相当于先有一个一个标号为0，值为0的点

然后每次新加一个标号为k的点在p点上，我们要新加的k点严格大于p点的值

这个可以用dp来完成

dp[u][x]表示用u个点，根节点值为x的方案数，标号就是0 - u - 1

答案就是dp[N + 1][0]

转移就是

\(dp[n] = \sum_{y > x} dp[n - k][x] * dp[k][y] \binom{n - 2}{k - 1}\)

我们每次把y当做1号点，x当做0号点可以不重不漏

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

//#define ivorysi

using namespace std;

typedef long long int64;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N,K,MOD;

int dp[305][305],sum[305][305],C[305][305];

int inc(int a,int b) {

    return a + b >= MOD ? a + b - MOD : a + b;

}

int mul(int a,int b) {

    return 1LL * a * b % MOD;

}

void update(int &x,int y) {

    x = inc(x,y);

}

void Solve() {

    read(N);read(K);read(MOD);

    C[0][0] = 1;

    for(int i = 1 ; i <= N ; ++i) {

	C[i][0] = 1;

	for(int j = 1 ; j <= i ; ++j) {

	    C[i][j] = inc(C[i - 1][j - 1],C[i - 1][j]);

	}

    }

    for(int j = 0 ; j <= K ; ++j) {sum[1][j] = (j + 1) % MOD;dp[1][j] = 1;}

    for(int i = 2 ; i <= N + 1; ++i) {

	for(int j = 1 ; j < i ; ++j) {

	    for(int k = 0 ; k <= K ; ++k) {

		update(dp[i][k],mul(mul(dp[j][k],inc(sum[i - j][K],MOD - sum[i - j][k])),C[i - 2][i - j - 1]));

	    }

	}

	sum[i][0] = dp[i][0];

	for(int k = 1 ; k <= K ; ++k) sum[i][k] = inc(sum[i][k - 1],dp[i][k]);

    }

    out(dp[N + 1][0]);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

F - Simple Subsequence Problem

我们只要构造出一张图

例如110[00011001]

这个点可以转移到

1100[0011001]和1101[1001]和110[]

我们若s在集合中[s] = 1

每个点t的值是t[]

如果t是s的子序列，转移的路径是唯一的，所以只要用dp求路径条数即可

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define space putchar(' ')

#define enter putchar('\n')

#define mp make_pair

#define pb push_back

#define MAXN 200005

//#define ivorysi

using namespace std;

typedef long long int64;

template<class T>

void read(T &res) {

	res = 0;T f = 1;char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') f = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		res = res * 10 + c - '0';

		c = getchar();

	}

	res *= f;

}

template<class T>

void out(T x) {

	if(x < 0){putchar('-');x = -x;}

	if(x >= 10) out(x / 10);

	putchar('0' + x % 10);

}

int N,K,cnt;

char s[25][(1 << 20) + 5];

vector<int> v[25];

int dp[42000005];

int p0[25],p1[25];

void Solve() {

	read(N);read(K);

	for(int i = 0 ; i <= N ; ++i) scanf("%s",s[i]);

	for(int i = 1 ; i <= N ; ++i) {

		v[i].resize((i + 1) * (1 << i));

		int s = v[i].size();

		for(int j = 0 ; j < s ; ++j) v[i][j] = ++cnt;

	}

	for(int i = 1 ; i <= N ; ++i) {

		for(int j = 0 ; j < (1 << i) ; ++j) {

			if(s[i][j] == '1') {

				dp[v[i][j * (i + 1) + i]]++;

			}

		}

	}

	for(int i = N ; i >= 1 ; --i) {

		for(int S = 0 ; S < (1 << i) ; ++S) {

			p0[0] = -1,p1[0] = -1;

			for(int j = 0 ; j <= i ; ++j) {

				p1[j + 1] = p1[j];p0[j + 1] = p0[j];

				if(S >> j & 1) p1[j + 1] = j;

				else p0[j + 1] = j;

			}

			for(int j = i ; j >= 0 ; --j) {

				int u = v[i][S * (i + 1) + j];

				int b = S & ((1 << j) - 1),f = S >> j;

				if(dp[u]) {

					if(p0[j] != -1) {

						int p = ((f << 1) << p0[j]) + (S & (1 << p0[j]) - 1);

						int l = p0[j] + 1 + i - j;

						dp[v[l][p * (l + 1) + p0[j]]] += dp[u];

					}

					if(p1[j] != -1) {

						int p = ((f << 1 | 1) << p1[j]) + (S & (1 << p1[j]) - 1);

						int l = p1[j] + 1 + i - j;

						dp[v[l][p * (l + 1) + p1[j]]] += dp[u];

					}

					if(j != 0 && j != i) {

						int l = i - j;

						dp[v[l][f * (l + 1)]] += dp[u];

					}

				}

			}

		}

	}

	for(int i = N ; i >= 1 ; --i) {

		for(int j = 0 ; j < (1 << i) ; ++j) {

			if(dp[v[i][j * (i + 1)]] >= K) {

				for(int k = i - 1; k >= 0 ; --k) {

					putchar('0' + ((j >> k) & 1));

				}

				enter;

				return;

			}

		}

	}

	puts("");

}

int main() {

#ifdef ivorysi

	freopen("f1.in","r",stdin);

#endif

	Solve();

}