A - STring

用一个栈模拟即可。

//waz#include 
     
       using namespace std; #define mp make_pair#define pb push_back#define fi first#define se second#define ALL(x) (x).begin(), (x).end()#define SZ(x) ((int)((x).size())) typedef pair
      
        PII;typedef vector
       
         VI;typedef long long int64;typedef unsigned int uint;typedef unsigned long long uint64; #define gi(x) ((x) = F())#define gii(x, y) (gi(x), gi(y))#define giii(x, y, z) (gii(x, y), gi(z)) int F(){	char ch;	int x, a;	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');	if (ch == '-') ch = getchar(), a = -1;	else a = 1;	x = ch - '0';	while (ch = getchar(), ch >= '0' && ch <= '9')		x = (x << 1) + (x << 3) + ch - '0';	return a * x;} const int N = 2e5 + 10; char str[N], stk[N]; int n, tp; int main(){	scanf("%s", str + 1);	n = strlen(str + 1);	for (int i = 1; i <= n; ++i)	{		if (tp > 0 && stk[tp] == 'S' && str[i] == 'T') --tp;		else stk[++tp] = str[i];	}	printf("%d\n", tp);	return 0;}
       
      
     

　　

B - Minimum Sum

分治一下，计算一个数作为最小值的贡献。

//waz#include 
     
       using namespace std; #define mp make_pair#define pb push_back#define fi first#define se second#define ALL(x) (x).begin(), (x).end()#define SZ(x) ((int)((x).size())) typedef pair
      
        PII;typedef vector
       
         VI;typedef long long int64;typedef unsigned int uint;typedef unsigned long long uint64; #define gi(x) ((x) = F())#define gii(x, y) (gi(x), gi(y))#define giii(x, y, z) (gii(x, y), gi(z)) int F(){	char ch;	int x, a;	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');	if (ch == '-') ch = getchar(), a = -1;	else a = 1;	x = ch - '0';	while (ch = getchar(), ch >= '0' && ch <= '9')		x = (x << 1) + (x << 3) + ch - '0';	return a * x;} const int N = 2e5 + 10; int a[N]; long long ans; void solve(int l, int r){	if (l == r)	{		ans += a[l];		return;	}	long long res = 0;	int mid = (l + r) >> 1;	vector
        
          L, R;	for (int i = mid; i >= l; --i)	{		if (!SZ(L) || a[L[SZ(L) - 1]] > a[i])			L.pb(i);	}	for (int i = mid + 1; i <= r; ++i)	{		if (!SZ(R) || a[R[SZ(R) - 1]] > a[i])			R.pb(i);	}	L.pb(l - 1);	R.pb(r + 1);	for (int i = 0, j = 0; i < SZ(L) - 1; ++i)	{		while (a[R[j]] > a[L[i]] && j < SZ(R) - 1) ++j;		res += 1LL * (R[j] - mid - 1) * (L[i] - L[i + 1]) * a[L[i]];	}	for (int i = 0, j = 0; i < SZ(R) - 1; ++i)	{		while (a[R[i]] < a[L[j]] && j < SZ(L) - 1) ++j;		res += 1LL * (mid - L[j]) * (R[i + 1] - R[i]) * a[R[i]];	}	ans += res;	solve(l, mid);	solve(mid + 1, r);} int n; int main(){	gi(n);	for (int i = 1; i <= n; ++i) gi(a[i]);	solve(1, n);	printf("%lld\n", ans);	return 0;}
        
       
      
     

　　

C - Tree Restoring

先把直径找出来，其它的挂在直径上就好了。

//waz#include 
     
       using namespace std; #define mp make_pair#define pb push_back#define fi first#define se second#define ALL(x) (x).begin(), (x).end()#define SZ(x) ((int)((x).size())) typedef pair
      
        PII;typedef vector
       
         VI;typedef long long int64;typedef unsigned int uint;typedef unsigned long long uint64; #define gi(x) ((x) = F())#define gii(x, y) (gi(x), gi(y))#define giii(x, y, z) (gii(x, y), gi(z)) int F(){	char ch;	int x, a;	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');	if (ch == '-') ch = getchar(), a = -1;	else a = 1;	x = ch - '0';	while (ch = getchar(), ch >= '0' && ch <= '9')		x = (x << 1) + (x << 3) + ch - '0';	return a * x;} int n, a[110]; int main(){	gi(n);	for (int i = n; i; --i) gi(a[i]);	sort(a + 1, a + n + 1);	reverse(a + 1, a + n + 1);	int len = a[1];	int mn = len / 2 + 1;	for (int i = len; i > len / 2; --i)	{		int cnt = 0;		for (int j = 1; j <= n; ++j)		{			if (a[j] == i) ++cnt, a[j] = 0;			if (cnt == 2) break;		}		if (cnt < 2)		{			puts("Impossible");			return 0;		}	}	if (!(len & 1))	{		mn = len / 2;		int cnt = 0;		for (int j = 1; j <= n; ++j)		{			if (a[j] == (len >> 1)) ++cnt, a[j] = 0;			if (cnt == 1) break;		}		if (cnt < 1)		{			puts("Impossible");			return 0;		}	}	for (int i = 1; i <= n; ++i)		if (a[i] && a[i] <= mn)		{			puts("Impossible");			return 0;		}	puts("Possible");	return 0;}
       
      
     

　　

D - ~K Perm Counting

我们发现可以放置的可以画出一个二分图，然后容斥一下就好了。

//waz#include 
     
       using namespace std; #define mp make_pair#define pb push_back#define fi first#define se second#define ALL(x) (x).begin(), (x).end()#define SZ(x) ((int)((x).size())) typedef pair
      
        PII;typedef vector
       
         VI;typedef long long int64;typedef unsigned int uint;typedef unsigned long long uint64; #define gi(x) ((x) = F())#define gii(x, y) (gi(x), gi(y))#define giii(x, y, z) (gii(x, y), gi(z)) int F(){	char ch;	int x, a;	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');	if (ch == '-') ch = getchar(), a = -1;	else a = 1;	x = ch - '0';	while (ch = getchar(), ch >= '0' && ch <= '9')		x = (x << 1) + (x << 3) + ch - '0';	return a * x;} const int mod = 924844033; int f[2010][2010][2], g[2010], t[2010], ans; int main(){	int n, k;	gii(n, k);	f[0][0][0] = 1;	for (int i = 1; i <= n; ++i)	{		for (int j = 0; j <= n; ++j)		{			f[i][j][0] = (f[i][j][0] + f[i - 1][j][0]) % mod;			f[i][j][0] = (f[i][j][0] + f[i - 1][j][1]) % mod;			if (j) f[i][j][1] = f[i - 1][j - 1][0];		}	}	g[0] = 1;	for (int i = 1; i <= k; ++i)	{		int len = (n - i) / k;		for (int i = 0; i <= n; ++i)			t[i] = g[i], g[i] = 0;		for (int j = 0; j <= len; ++j)			for (int l = 0; l <= n - j; ++l)				g[j + l] = (g[j + l] + 1LL * t[l] * (f[len][j][0] + f[len][j][1])) % mod;		for (int i = 0; i <= n; ++i)			t[i] = g[i], g[i] = 0;		for (int j = 0; j <= len; ++j)			for (int l = 0; l <= n - j; ++l)				g[j + l] = (g[j + l] + 1LL * t[l] * (f[len][j][0] + f[len][j][1])) % mod;	}	for (int i = n, fac = 1, j = (n & 1) ^ 1; ~i; --i, fac = 1LL * fac * (n - i) % mod, j ^= 1)	{		if (j) ans = (ans + 1LL * g[i] * fac) % mod;		else ans = (ans - 1LL * g[i] * fac) % mod;	}	if (ans < 0) ans += mod;	printf("%d\n", ans);	return 0;}
       
      
     

　　

E - Sugigma: The Showdown

 如果有一条A中的边在B中长度大于2，只要A走到肯定赢，A能走到的点就是A要在B之前走到，算一下就好了。

//waz#include 
     
       using namespace std; #define mp make_pair#define pb push_back#define fi first#define se second#define ALL(x) (x).begin(), (x).end()#define SZ(x) ((int)((x).size())) typedef pair
      
        PII;typedef vector
       
         VI;typedef long long int64;typedef unsigned int uint;typedef unsigned long long uint64; #define gi(x) ((x) = F())#define gii(x, y) (gi(x), gi(y))#define giii(x, y, z) (gii(x, y), gi(z)) int F(){	char ch;	int x, a;	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');	if (ch == '-') ch = getchar(), a = -1;	else a = 1;	x = ch - '0';	while (ch = getchar(), ch >= '0' && ch <= '9')		x = (x << 1) + (x << 3) + ch - '0';	return a * x;} const int N = 2e5 + 10; int n; VI A[N], B[N]; int fa[N], in[N], out[N], dep[N], dfs_clock; void dfsB(int u){	in[u] = ++dfs_clock;	for (auto v : B[u])	{		if (v == fa[u]) continue;		fa[v] = u;		dep[v] = dep[u] + 1;		dfsB(v);	}	out[u] = dfs_clock;} bool check(int u, int v){	if (in[u] <= in[v] && in[v] <= out[u])	{		if (fa[v] == u) return 1;		if (fa[fa[v]] == u) return 1;		return 0; 	} 	if (in[v] <= in[u] && in[u] <= out[v])	{		if (fa[u] == v) return 1;		if (fa[fa[u]] == v) return 1;		return 0; 	} 	if (fa[u] == fa[v]) return 1; 	return 0;} bool vis[N]; int d[N]; void bfsA(int s){	static int q[N]; int l = 0, r = 0;	q[r++] = s; vis[s] = 1;	while (l < r)	{		int u = q[l++];		for (auto v : A[u])		{			if (vis[v]) continue;			d[v] = d[u] + 1;			if (d[v] < dep[v] && !vis[v])			{				vis[v] = 1;				q[r++] = v;			}		}	}} int rootA, rootB; bool win[N]; int main(){	giii(n, rootA, rootB);	for (int i = 1; i < n; ++i)	{		int u, v;		gii(u, v);		A[u].pb(v);		A[v].pb(u);	}	for (int i = 1; i < n; ++i)	{		int u, v;		gii(u, v);		B[u].pb(v);		B[v].pb(u);	}	dfsB(rootB);	for (int i = 1; i <= n; ++i)	{		for (auto j : A[i])			if (!check(i, j)) win[i] = win[j] = 1;	}	bfsA(rootA);	int ans = 0;	for (int i = 1; i <= n; ++i)	{		if (vis[i] && win[i]) 		{			puts("-1");			return 0;		}		if (vis[i]) ans = max(ans, dep[i] * 2);	}	printf("%d\n", ans);	return 0;}
       
      
     

　　

F - Many Easy Problems

分开算每个点贡献，可以用容斥做，最后发现这个式子是一个卷积。NTT一下就好了。

//waz#include 
     
       using namespace std; #define mp make_pair#define pb push_back#define fi first#define se second#define ALL(x) (x).begin(), (x).end()#define SZ(x) ((int)((x).size())) typedef pair
      
        PII;typedef vector
       
         VI;typedef long long int64;typedef unsigned int uint;typedef unsigned long long uint64; #define gi(x) ((x) = F())#define gii(x, y) (gi(x), gi(y))#define giii(x, y, z) (gii(x, y), gi(z)) int F(){	char ch;	int x, a;	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');	if (ch == '-') ch = getchar(), a = -1;	else a = 1;	x = ch - '0';	while (ch = getchar(), ch >= '0' && ch <= '9')		x = (x << 1) + (x << 3) + ch - '0';	return a * x;} const int N = 1 << 20; const int mod = 924844033; const int g = 5; int fpow(int a, int x){	int ret = 1;	for (; x; x >>= 1)	{		if (x & 1) ret = 1LL * ret * a % mod;		a = 1LL * a * a % mod;	}	return ret;} int n; vector
        
          edge[N]; int cnt[N], siz[N], fac[N], ifac[N]; int C(int n, int m){	if (n < m || m < 0) return 0;	return 1LL * fac[n] * ifac[n - m] % mod * ifac[m] % mod;} void dfs(int u, int fa){	siz[u] = 1;	for (auto v : edge[u])	{		if (v == fa) continue;		dfs(v, u);		siz[u] += siz[v];	}	for (auto v : edge[u])	{		if (v == fa)		{			++cnt[n - siz[u]];			continue;		}		++cnt[siz[v]];	}} void dft(int *a, int n, int sig){	for (int i = 0, j = 0; i < n; ++i)	{		if (i > j) swap(a[i], a[j]);		for (int l = n >> 1; (j ^= l) < l; l >>= 1);	}	for (int i = 1; i < n; i <<= 1)	{		int m = i << 1;		int w = fpow(g, (mod - 1) / m);		if (sig == -1) w = fpow(w, mod - 2);		for (int j = 0; j < n; j += m)		{			int v = 1;			for (int k = j; k < j + i; ++k, v = 1LL * v * w % mod)			{				int x = a[k], y = 1LL * a[k + i] * v % mod;				a[k] = (x + y) % mod;				a[k + i] = (x - y + mod) % mod;			}		}	}	if (sig == -1)	{		int invn = fpow(n, mod - 2);		for (int i = 0; i < n; ++i) a[i] = 1LL * a[i] * invn % mod;	}} int main(){	gi(n);	for (int i = 1; i < n; ++i)	{		int u, v;		gii(u, v);		edge[u].pb(v);		edge[v].pb(u);	}	dfs(1, 0);	fac[0] = 1;	for (int i = 1; i <= n; ++i) fac[i] = 1LL * fac[i - 1] * i % mod;	ifac[n] = fpow(fac[n], mod - 2);	for (int i = n; i; --i) ifac[i - 1] = 1LL * ifac[i] * i % mod;	static int f[N], g[N];	for (int i = 0; i <= n; ++i) g[i] = ifac[n - i];	for (int i = 0; i <= n; ++i) f[i] = 1LL * cnt[i] * fac[i] % mod;	int m = 1;	for (; m <= (n << 1); m <<= 1);	dft(f, m, 1), dft(g, m, 1);	for (int i = 0; i < m; ++i) f[i] = 1LL * f[i] * g[i] % mod;	dft(f, m, -1);	for (int k = 1; k <= n; ++k)	{		int ans = n;		ans = 1LL * ans * C(n, k) % mod;		ans = (ans - 1LL * ifac[k] * f[n + k]) % mod;		if (ans < 0) ans += mod;		printf("%d\n", ans);	}	return 0;}