VP记录——The 2021 CCPC Weihai Onsite

网址

2021CCPC威海

赛时过题与罚时

A.Goodbye, Ziyin!

签到题，队友写的

#include<bits/stdc++.h>
using namespace std;
int cnt[10], de[1000010];
int main() {int n;cin >> n;for(int i = 1; i < n; ++i) {int u, v;scanf("%d %d", &u, &v);++de[u];++de[v];}for(int i = 1; i <= n; ++i) {if(de[i] > 3) {cout << "0";return 0;}cnt[de[i]]++;}cout << cnt[1] + cnt[2];return 0;
}

D.Period

队友写的KMP，签到题

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
char s[MAXN];
int nxt[MAXN];
int n;
int ans[MAXN];
int main()
{scanf("%s", s + 1);n = strlen(s + 1);int j = 0;for(int i = 2; i <= n; ++i){while(j && s[i] != s[j + 1]) j = nxt[j];if(s[i] == s[j + 1]) j++;nxt[i] = j;}/* for(int i = 1; i <= n; ++i)* {*     cout << nxt[i] << " ";* }* cout << "\n"; */j = nxt[n];while(j){int l = j;int r = n - l + 1;if(r > l){ans[r] --;ans[l + 1] ++;}j = nxt[j];}for(int i = 1; i <= n; ++i)ans[i] = ans[i] + ans[i-1];/* for(int i = 1; i <= n; ++i)* {*     cout << ans[i] << " ";* }* cout << "\n"; */int q;scanf("%d", &q);while(q--){int l;scanf("%d", &l);printf("%d\n", ans[l]);}return 0;
}

G. Shinyruo and KFC

简单组合计数
若$k<max(a_i)$，显然无解
有解时答案是${\prod }_{i=1}^{n}C(k,a_i)={\prod }_{i=1}^n\frac{k!}{a_i!\ast (k-a_i)!}$
这样显然有一个$O(mn)$的做法
观察数据性质${\sum }_{i=1}^n{a}_i<=1e5$
即$a_i$的种类数量级别为$sqrt(n)$
那么就可以把相同的$a_i$一起做，优化成$O(m\sqrt{n})$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const int MOD = 998244353;
int n, m, a[N];
ll b[N];
ll c[N];
ll cnt[N];
ll power(ll x, ll y) {if(y == 0) {return 1;}ll res = 1;while(y){if(y&1) res = res * x % MOD;x  = x * x % MOD; y >>= 1;}return res;
}
ll ni(ll x) {return power(x, MOD - 2);
}
int main() {scanf("%d %d", &n, &m);b[0] = 1;for(ll i = 1; i <= 1e5; ++i) {b[i] = b[i - 1] * i % MOD;c[i] = power(b[i], n);}int mx = 0;for(ll i = 1; i <= n; ++i ) {scanf("%d", &a[i]);++cnt[a[i]];mx = max(mx, a[i]);}sort(a + 1, a + 1 + n);n = unique(a + 1, a + 1 + n) - (a + 1);for(int k = 1; k <= m; ++k) {if(k < mx) {puts("0");continue;}ll ans = c[k];for(ll i = 1; i <= n; ++i) {ll t = b[a[i]] * b[k - a[i]] % MOD;t = power(t, cnt[a[i]]);ans = ans * ni(t) % MOD;}printf("%lld\n", ans);}return 0;
}

H. city safet

发现$n$的范围很像网络流，然后就往这方面想，后面发现每当多选择一个距离相当于是获得了$v_{i+1}-v_i$的贡献，每当修复了一个点，相当于是花费了$w_i$，我们要统一边权的性质，即我们可以想办法把问题变成最大贡献或者最小花费
那么我们可以假设初始时全部修复，
那么每个点建立$n$个代表点，$i{d}_{i,j}$表示以点$i$为中心，距离$<=j$的一类点，共$n\ast n$个代表点
然后建立$n$个具体点$1$到$n$
对于建图而言，
第$i$个点的代表点$j$向代表点$j-1$连边，$(i,j)->(i,j-1)$，边权为$v_j-v_{j-1}$，可理解成是反悔边，反悔这次距离的添加
每个代表点$(i,j)$连向所有跟$i$距离为$j$的具体点，$(i,j)->k当dis[i][k]=j$，边权为无穷
源点向所有代表点连边，边权为无穷，$S->(i,j)$
所有具体点向汇点连边，边权为对应的$w_i$，$i->T$，因为一个点最坏情况就是直接修了它
那么最小花费就是求最小割，直接网络流即可
那么答案就是$n\ast v_n-maxflow$

#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;const int N = 205;
const int M = 4e5+5;struct node {int to, next, w;
}e[M];
int n, m, k = 1, head[M], d[M];
int id[N][N], w[N], v[N];
int f[N][N];
int S, T, Maxflow, Num;void build(int u, int v, int w) {e[++k] = (node) {v, head[u], w};head[u] = k;e[++k] = (node) {u, head[v], 0};head[v] = k;
}queue<int> q;bool bfs() {while(!q.empty()) q.pop();for(int i = S; i <= T; ++i) d[i] = 0;d[S] = 1;q.push(S);while(!q.empty()) {int u = q.front();q.pop();for(int i = head[u]; i; i = e[i].next){int v = e[i].to;if(e[i].w && !d[v]) {d[v] = d[u] + 1;q.push(v);if(v == T) return 1;}}}return 0;
}
int dfs(int dep, int flow) {if(dep == T) {return flow;}int rest = flow, rp = 0;for(int i = head[dep]; i && rest; i = e[i].next) {int v = e[i].to;if(d[v] == d[dep] + 1 && e[i].w) {rp = dfs(v, min(e[i].w, rest));if(!rp) {d[v] = 0;}e[i].w -= rp;e[i ^ 1].w += rp;rest -= rp;}}return flow - rest;
}
void dinic() {int flow;while(bfs()) {while(flow = dfs(S, INF)) {Maxflow += flow;}}
}int main() {scanf("%d", &n);S = 0;T = n*n+n+1;for (int i = 1; i <= n; i++) scanf("%d", &w[i]);for (int i = 1; i <= n; i++) scanf("%d", &v[i]); int U, V;memset(f, 0x3f, sizeof(f));for (int i = 1; i < n; i++) {scanf("%d%d", &U, &V);if (U != V) f[U][V] = f[V][U] = 1;}for (int i = 1; i <= n; i++) build(i, T, w[i]);Num = n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) id[i][j] = ++Num;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {build(S, id[i][j], v[j]-v[j-1]);build(id[i][j], id[i][j-1], INF); }}    for (int i = 1; i <= n; i++) f[i][i] = 0;for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {build(id[i][f[i][j]+1], j, INF); }dinic();printf("%d\n", n*v[n]-Maxflow);return 0;
}

J.Circular Billiard Table

签到题，我写的，题意是给一个入射角，求在圆内最少弹射多少次能回到原点
入射角是$\frac{a}{b}$，那么假设有$x$个转角，要弹$y$圈
显然有$\frac{a}{b}\ast x\ast 2=360\ast y$
构造$x=180\ast b,y=a$然后除$gcd$就可以了

#include<bits/stdc++.h>using namespace std;typedef long long ll;ll gcd(ll a, ll b) {return (!b) ? a : gcd(b, a%b);
}
ll t, a, b;int main() {scanf("%lld", &t);while (t--) {scanf("%lld%lld", &a, &b);long long A = 180*b, B = a;ll c = gcd(A, B);ll ans = A/c-1;printf("%lld\n", ans);}return 0;
} 

M.810975

题意是构造一个长度为$n$的01串，其中有$m$个1，最长连续1 等于$k$，问总方案数
相当于是在0的$n-m+1$个空隙里面插入1
容斥一下，
答案即为
$n-m+1$个数中，满足$0<=x_i<=k$且$({\sum }_{i=1}^{n-m+1}{x}_i)=m$的方案数
减去
$n-m+1$个数，满足$0<=x_i<=k-1$且$({\sum }_{i=1}^{n-m+1}{x}_i)=m$的方案数

经典问题，队友直接秒了！

#include <bits/stdc++.h>
using namespace std;
#define mo 998244353
#define maxn 1000005
#define MAXN 1000005
#define ll long long
namespace Poly
{inline void Add(int &x,int y){x+=y;x-=(x>=mo?mo:0);}inline int add(int x,int y){x+=y;return x>=mo?x-mo:x;}int A[maxn],B[maxn],C[maxn],D[maxn],E[maxn],inv[maxn],R[maxn],len,sz,ny;inline int ksm(int x,int y=mo-2){int a=1;if(y<0)y+=mo-1;while(y){if(y&1)a=1ll*a*x%mo;x=1ll*x*x%mo;y>>=1;}return a;}inline void init(int n){int i;inv[1]=1;for(i=2;i<=n;++i)inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;}inline void Inte(int *a,int n){for(int i=n-1;i>=1;--i)a[i]=1ll*a[i-1]*inv[i]%mo;a[0]=0;}inline void Deri(int *a,int n){for(int i=1;i<n;++i)a[i-1]=1ll*a[i]*i%mo;a[n-1]=0;}inline void pre(int n){len=1,sz=-1;while(len<n)len<<=1,++sz;ny=ksm(len);for(int i=1;i<len;++i)R[i]=(R[i>>1]>>1)|((i&1)<<sz);}inline void NTT(int *a,int fl)//fl==1?3:332748118;{int i,j,k,t,y,p,w,wn;for(i=1;i<len;++i)if(i<R[i])swap(a[i],a[R[i]]);for(i=2,p=1;i<=len;p=i,i<<=1)for(wn=ksm(fl,(mo-1)/i),j=0;j<len;j+=i)for(w=1,k=0;k<p;++k,w=1ll*w*wn%mo){t=a[j|k],y=1ll*w*a[j|k|p]%mo;a[j|k]=add(t,y),a[j|k|p]=add(t,mo-y);}}inline void Mul(int *a,int *b,int *c,int nm,int n,int m)//a is the ans;{if(!n||!m){fill(a,a+nm,0);return ;}pre(n+m-1);for(int i=0;i<n;++i)A[i]=b[i];fill(A+n,A+len,0);for(int i=0;i<m;++i)B[i]=c[i];fill(B+m,B+len,0);NTT(A,3);NTT(B,3);for(int i=0;i<len;++i)A[i]=1ll*A[i]*B[i]%mo;NTT(A,332748118);for(int i=0;i<nm;++i)a[i]=1ll*A[i]*ny%mo;}inline void Inv(int *a,int *b,int n)//this n include zero position;{if(n==1)return a[0]=ksm(b[0]),void();int m=(n+1)>>1,i;Inv(a,b,m);pre(n<<1);for(i=0;i<m;++i)A[i]=a[i];fill(A+m,A+len,0);for(i=0;i<n;++i)B[i]=b[i];fill(B+n,B+len,0);NTT(A,3);NTT(B,3);for(i=0;i<len;++i)A[i]=1ll*A[i]*add(2,mo-1ll*A[i]*B[i]%mo)%mo;NTT(A,332748118);for(i=0;i<n;++i)a[i]=1ll*A[i]*ny%mo;}inline void Ln(int *a,int *b,int n)//a is the ans;b[0]need equal 1;{Inv(a,b,n);int i;pre(n<<1);for(i=0;i<n;++i)C[i]=b[i];Deri(C,n);for(i=0;i<n;++i)A[i]=a[i];fill(A+n,A+len,0);for(i=0;i<n;++i)B[i]=C[i];fill(B+n,B+len,0);NTT(A,3);NTT(B,3);for(i=0;i<len;++i)A[i]=1ll*A[i]*B[i]%mo;NTT(A,332748118);for(i=0;i<n;++i)a[i]=1ll*A[i]*ny%mo;Inte(a,n);}inline void Exp(int *a,int *b,int n)//a is the ans;{if(n==1)return a[0]=1,void();int m=(n+1)>>1,i;Exp(a,b,m);Ln(D,a,n);pre(n<<1);for(i=0;i<m;++i)A[i]=a[i];fill(A+m,A+len,0);for(i=0;i<n;++i)B[i]=add(b[i],mo-D[i]);++B[0];fill(B+n,B+len,0);NTT(A,3);NTT(B,3);for(i=0;i<len;++i)A[i]=1ll*A[i]*B[i]%mo;NTT(A,332748118);for(i=0;i<n;++i)a[i]=1ll*A[i]*ny%mo;}inline void Ksm(int *a,int *b,int n, ll k)//a b should be differented;a is the ans;b[0] need equal 1;{Ln(E,b,n);k%=mo;for(int i=0;i<n;++i)E[i]=1ll*E[i]*k%mo;Exp(a,E,n);}
}
int n, m, k;
int a[MAXN];
int b[MAXN];
int main()
{cin >> n >> m >> k;if(n == 0){if(m == 0 && k == 0) { cout << 1 << "\n"; return 0; }else { cout << 0 << "\n"; return 0; }}if(n < m) { cout << 0 << "\n"; return 0;}if(m < k) { cout << 0 << "\n"; return 0; }if(m == 0){if(k == 0) { cout << 1 << "\n"; return 0;}else { cout << 0 << "\n"; return 0;}}if(k == 0){if(m == 0) { cout << 1 << "\n"; return 0;}else { cout << 0 << "\n"; return 0; }}n = n - m + 1;Poly::init(800000);memset(a, 0, sizeof a);for(int i = 0; i <= k; ++i) a[i] = 1;Poly::Ksm(b, a, m + 1, n);int ans = b[m];memset(a, 0, sizeof a);for(int i = 0; i < k; ++i) a[i] = 1;memset(b, 0, sizeof b);Poly::Ksm(b, a, m + 1, n);ans = (ans - b[m] + mo) % mo;cout << ans << "\n";return 0;
}