Preface
久违地训练，因为昨天 ICPC 网络赛打的太唐不得不上点强度了
回到这场本身，由于中途发现了两个题被搬到去年暑假前集训队内赛了，导致经典提前没事干
2h15min 过了六个题后（有两个是原）就开始对着 L,M 发呆，虽然最后 4h45min 的时候把 M 开出来了，但还是说明做难题的水平不够（评价是霓虹场是这样的，好多 Counting 没办法发力）
由于这场题很多因此就只写过了的题/计划补的题了
A. XOR Tree Path
签到，读完题就发现可以设状态 \(f_{x,0/1}\) 表示在点 \(x\) 的子树内，修改的叶子数量为偶数/奇数时最多有几个黑点，转移显然
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,a[N],x,y,f[N][2]; vector <int> v[N];
inline void DFS(CI now=1,CI fa=0)
{
bool flag=1;
for (auto to:v[now]) if (to!=fa)
{
DFS(to,now);
if (flag)
{
for (RI i=0;i<2;++i) f[now][i]=f[to][i]; flag=0;
} else
{
int g[2]={0,0};
for (RI p=0;p<2;++p) for (RI q=0;q<2;++q)
g[p^q]=max(g[p^q],f[now][p]+f[to][q]);
for (RI i=0;i<2;++i) f[now][i]=g[i];
}
}
++f[now][a[now]^1];
}
int main()
{
scanf("%d",&n);
for (RI i=1;i<=n;++i) scanf("%d",&a[i]);
for (RI i=1;i<n;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
DFS(),printf("%d",max(f[1][0],f[1][1]));
//for (RI i=1;i<=n;++i) printf("f[%d][0] = %d; f[%d][1] = %d\n",i,f[i][0],i,f[i][1]);
return 0;
}
B. Magical Wallet
祁神开场写的神秘模拟+ DP，我题目都没看
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9+5;
const int N = 1e4+5;
int n, x, A[105];
int dp[105][N];
void chmax(int &x, int a) {
x = max(x, a);
}
int strToInt(const string &str) {
int sz = str.size();
int res = 0, bas=1;
for (int i=0; i<sz; ++i, bas*=10) {
res += (str[i]-'0')*bas;
}
return res;
}
string intToStr(int x) {
string res;
while (x>0) res += (char)('0'+x%10), x/=10;
return res;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> x;
for (int i=1; i<=n; ++i) cin >> A[i];
auto makeSet = [&](int val) {
vector<int> res;
string X = intToStr(val);
sort(X.begin(), X.end());
do {
res.push_back(strToInt(X));
} while (next_permutation(X.begin(), X.end()));
return res;
};
vector<int> vec = makeSet(x);
// printf("vec:"); for (int u : vec) printf("%d ", u); puts("");
for (int i=0; i<=n; ++i) for (int j=0; j<10000; ++j) dp[i][j] = -INF;
for (int u : vec) dp[0][u]=0;
for (int i=1; i<=n; ++i) {
for (int j=0; j<10000; ++j) {
chmax(dp[i][j], dp[i-1][j]);
int val = j-A[i];
if (val < 0) continue;
vec = makeSet(val);
// if (dp[i-1][j]>=0) {printf("val=%d vec:", val); for (int u : vec) printf("%d ", u); puts("");}
for (int u : vec) chmax(dp[i][u], dp[i-1][j]+1);
}
}
int ans = 0;
for (int j=0; j<10000; ++j) chmax(ans, dp[n][j]);
cout << ans << '\n';
return 0;
}
E. Five Med Sum
就是 这个题，做法直接看当时写的吧
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=998244353;
int n,a[5][N],id[5],ans;
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,k,s; for (scanf("%lld",&n),i=0;i<5;++i)
for (j=1;j<=n;++j) scanf("%lld",&a[i][j]),a[i][j]=5LL*a[i][j]+i;
for (i=0;i<5;++i) sort(a[i]+1,a[i]+n+1);
for (i=0;i<5;++i) for (s=0;s<(1<<4);++s)
{
int cur=0; for (j=0;j<4;++j) if ((s>>j)&1) ++cur;
if (cur!=2) continue; cur=0;
for (j=0;j<5;++j) if (i!=j) id[j]=(s>>cur)&1,++cur;
for (j=1;j<=n;++j)
{
int ret=1; for (k=0;k<5;++k) if (i!=k)
{
int coef=lower_bound(a[k]+1,a[k]+n+1,a[i][j])-a[k]-1;
if (id[k]) coef=n-coef; ret=1LL*ret*coef%mod;
}
inc(ans,1LL*ret*((a[i][j]-i)/5LL)%mod);
}
}
return printf("%lld",ans),0;
}
G. Range NEQ
虽然算是 Counting，但恰好是牢闪勉强会一点的简单容斥和简单多项式，推了会也就会了
有禁区的排列计数直接上棋盘多项式，不难发现就是在一个边长为 \(n\times m\) 的棋盘上放 \(n\times m\) 个棋子，其中禁区为按主对角线排布的 \(n\) 个单元，每个单元为 \(m\times m\) 的矩形
考虑容斥计数，枚举有 \(i\) 个棋子放在禁区中，同时令 \(f(i)\) 表示放 \(i\) 个棋子在禁区中的方案数，则答案为：
\[\sum_{i=0}^{n\times m} (-1)^i\times f(i)\times (n\times m-i)! \]现在考虑计算 \(f(i)\)，不难想到一个朴素的 DP，令 \(g_{i,j}\) 表示处理了前 \(i\) 个单元，此时一共放了 \(j\) 个棋子的方案数
考虑在一个单元里放 \(k\in[0,m]\) 个棋子的方案数为 \((C_m^k)^2\times k!\) ，以此为系数进行转移，即得到复杂度为 \(O(n^2\times m^2)\) 的 DP
但这样做显然太劣了，考虑生成函数，对于一个单元格的生成函数 \(G(x)=\sum_{k=0}^m (C_m^k)^2\times k!\times x^k\)，不难发现 \(G^n(x)\) 就是我们想要的 \(f(i)\)
由于 \(G(x)\) 的次数为 \(n\times m\)，因此可以大力转化为点值后快速幂后转回去，只用写 NTT 即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1<<21,mod=998244353;
int n,m,f[N],fact[N],ifac[N];
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
inline void dec(int& x,CI y)
{
if ((x-=y)<0) x+=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
fact[0]=1; for (RI i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
ifac[n]=quick_pow(fact[n]); for (RI i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
if (n<0||m<0||n<m) return 0;
return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
namespace Poly
{
int rev[N],lim,p;
inline void init(CI n)
{
for (lim=1,p=0;lim<=n;lim<<=1,++p);
for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);
}
inline void NTT(int *f,CI opt)
{
for (RI i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);
for (RI i=1;i<lim;i<<=1)
{
int m=i<<1,D=quick_pow(3,opt==1?(mod-1)/m:mod-1-(mod-1)/m);
for (RI j=0;j<lim;j+=m)
{
int W=1; for (RI k=0;k<i;++k,W=1LL*W*D%mod)
{
int x=f[j+k],y=1LL*f[i+j+k]*W%mod;
f[j+k]=f[i+j+k]=x; inc(f[j+k],y); dec(f[i+j+k],y);
}
}
}
if (!~opt)
{
int Inv=quick_pow(lim);
for (RI i=0;i<lim;++i) f[i]=1LL*f[i]*Inv%mod;
}
}
}
int main()
{
scanf("%d%d",&n,&m); init(n*m);
for (RI i=0;i<=m;++i) f[i]=1LL*C(m,i)*C(m,i)%mod*fact[i]%mod;
Poly::init(n*m); Poly::NTT(f,1);
for (RI i=0;i<Poly::lim;++i) f[i]=quick_pow(f[i],n);
Poly::NTT(f,-1); int ans=0;
//for (RI i=0;i<=n*m;++i) printf("%d%c",f[i]," \n"[i==n*m]);
for (RI i=0;i<=n*m;++i)
{
int tmp=1LL*f[i]*fact[n*m-i]%mod;
if (i&1) dec(ans,tmp); else inc(ans,tmp);
}
return printf("%d",ans),0;
}
J. Make Convex Sequence
直接把做法写在题目名里了
首先不难发现题目中给的限制等价于找到的所有点 \((i,A_i)\) 形成一个下凸壳
手玩发现我们对所有 \((i,R_i)\) 求下凸壳后，检验它是否和每一个线段有交即可，这样一定是最优的
#include<bits/stdc++.h>
using namespace std;
#define int long long
using pii = pair<int, int>;
const int N = 3e5+5;
int n, L[N], R[N];
int stk[N], tp=-1;
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i=1; i<=n; ++i) cin >> L[i];
for (int i=1; i<=n; ++i) cin >> R[i];
auto check = [&](int p, int a, int b) {return (R[a]-R[p])*(b-p) < (R[b]-R[p])*(a-p);};
auto check2 = [&](int p, int a, int b) {return (L[a]-R[p])*(b-p) < (R[b]-R[p])*(a-p);};
for (int i=1; i<=n; ++i) {
while (tp>0 && !check(stk[tp-1], stk[tp], i)) --tp;
stk[++tp] = i;
}
bool ok=true;
int cur=1;
for (int i=1; i<=n; ++i) {
while (cur<=tp && stk[cur]<i) ++cur;
if (!check2(stk[cur-1], i, stk[cur])) {ok=false; break;}
}
cout << (ok ? "Yes\n" : "No\n");
return 0;
}
L. Many Products
看过题人数是个应该要会的 Counting，等过两天有时间再补吧
M. Colorful Graph
只能说这题上来就发现是个经典的 DAG 最小可重复路径覆盖，然后偷懒了想去网上找标准的做法，结果发现会连出 \(O(n^2)\) 条边被卡空间
后面只能自己想结果发现是个很 trivial 的建图，首先还是把原 DAG 用拆分二分图的模型来建，具体地：
- \(S\) 向 \(i\) 连容量为 \(1\) 的边，且 \(n+i\) 向 \(T\) 连容量为 \(1\) 的边；
- 若原图中存在 \(x\to y\) 的边，则 \(x\) 向 \(n+y\) 连容量为 \(\infty\) 的边；
- \(n+i\) 向 \(i\) 连容量为 \(\infty\) 的边；
这样建图后跑出的最大流上的边一定在原 DAG 的路径覆盖上，求方案数的话就沿着选中的边 DFS 一下，用并查集把同色的点合并一下即可
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=7005,INF=1e9;
int n,m,x,y,dfn[N],low[N],idx,stk[N],top,vis[N],bel[N],tot,fa[N],col[N]; vector <int> v[N];
inline void Tarjan(CI now)
{
dfn[now]=low[now]=++idx; stk[++top]=now; vis[now]=1;
for (auto to:v[now]) if (!dfn[to]) Tarjan(to),low[now]=min(low[now],low[to]);
else if (vis[to]) low[now]=min(low[now],dfn[to]);
if (low[now]==dfn[now])
{
bel[now]=++tot; vis[now]=0;
while (stk[top]!=now) bel[stk[top]]=tot,vis[stk[top--]]=0; --top;
}
}
namespace Network_Flow
{
const int NN=15005,MM=30005;
struct edge
{
int to,nxt,v,tp;
}e[MM<<1]; int cnt=1,head[NN],cur[NN],dep[NN],s,t;
inline void addedge(CI x,CI y,CI z)
{
//printf("%d -> %d (%d)\n",x,y,z);
e[++cnt]=(edge){y,head[x],z,z}; head[x]=cnt;
e[++cnt]=(edge){x,head[y],0,-z}; head[y]=cnt;
}
#define to e[i].to
inline bool BFS(void)
{
memset(dep,0,(t+1)*sizeof(int));
dep[s]=1; queue <int> q; q.push(s);
while (!q.empty())
{
int now=q.front(); q.pop();
for (RI i=head[now];i;i=e[i].nxt)
if (e[i].v&&!dep[to]) dep[to]=dep[now]+1,q.push(to);
}
return dep[t];
}
inline int DFS(CI now,CI tar,int dis)
{
if (now==tar) return dis; int ret=0;
for (RI& i=cur[now];i&&dis;i=e[i].nxt)
if (e[i].v&&dep[to]==dep[now]+1)
{
int dist=DFS(to,tar,min(dis,e[i].v));
if (!dist) dep[to]=INF;
dis-=dist; ret+=dist; e[i].v-=dist; e[i^1].v+=dist;
if (!dis) return ret;
}
if (!ret) dep[now]=INF; return ret;
}
inline bool travel(CI now,int& tar)
{
//printf("%d\n",now);
if (now>tot)
{
for (RI i=head[now];i;i=e[i].nxt)
if (to==t&&e[i].tp>0&&e[i].v!=e[i].tp)
{
++e[i].v; tar=now; return 1;
}
}
for (RI i=head[now];i;i=e[i].nxt)
{
//printf("to = %d; v = %d; tp = %d\n",to,e[i].v,e[i].tp);
if (e[i].tp>0&&e[i].v!=e[i].tp)
{
++e[i].v;
if (travel(to,tar)) return 1;
}
}
return 0;
}
#undef to
inline int Dinic(int ret=0)
{
while (BFS()) memcpy(cur,head,(t+1)*sizeof(int)),ret+=DFS(s,t,INF); return ret;
}
};
using namespace Network_Flow;
inline int getfa(CI x)
{
return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
int main()
{
scanf("%d%d",&n,&m);
for (RI i=1;i<=m;++i) scanf("%d%d",&x,&y),v[x].push_back(y);
for (RI i=1;i<=n;++i) if (!dfn[i]) Tarjan(i);
for (RI x=1;x<=n;++x) for (auto y:v[x])
if (bel[x]!=bel[y]) addedge(bel[x],tot+bel[y],INF);
//for (RI i=1;i<=n;++i) printf("%d%c",bel[i]," \n"[i==n]);
s=0; t=2*tot+1; for (RI i=1;i<=tot;++i)
addedge(s,i,1),addedge(tot+i,t,1),addedge(tot+i,i,INF);
for (RI i=1;i<=tot;++i) fa[i]=i;
Dinic(); int num=0;
for (RI i=head[s];i;i=e[i].nxt)
if (e[i].tp>0&&e[i].v!=e[i].tp)
{
int st=e[i].to,tar;
++e[i].v; travel(st,tar);
//printf("%d %d\n",st,tar);
fa[getfa(st)]=getfa(tar-tot);
}
for (RI i=1;i<=tot;++i) if (getfa(i)==i) col[i]=++num;
for (RI i=1;i<=n;++i) printf("%d ",col[getfa(bel[i])]);
return 0;
}
N. XOR Reachable
就是 这个题，做法直接看当时写的吧
Postscript
犹记得去年这个时候一周 VP 四场还外加 CF/ATC 的补题，现在我一周啥也不干每天就是白兰
只能说该进入备战状态了，不出意外的话今年应该是个人算竞生涯的最后一舞了，希望能不留遗憾吧
标签：CI,12,return,Cup,int,Universal,include,const,now From： https://www.cnblogs.com/cjjsb/p/18416735