Zory的暖心省选胡策题解

搬题思路:我是想尽可能挑比较有“教育感”的题(当然只是对我这小菜比而言,考虑到各位中人才辈出GM横行大概会觉得难度跟甜点差不多吧)

没有实力造足够好的原创题、原创部分,甚至改编都没有,只有在转OI题上面做了轻微的探索

题目的做法都非常丰富:A起码3个,C起码3个,由于本人才疏学浅,这里只给出其中部分做法的题解

每题代码都好写得离谱,希望大家喜欢

赛后总结

难度方面,我基本是按照我自己的水平造的(毫无科技含量),我感觉难度上还是很合适的:T2是比较基础且传统的计数,T3因为多种做法的存在也大大拉低了难度,现场赛高达500人通过。题型上T1、T3与传统OI题不同也正是我所希望尝试的(考虑到我们这一代CF战力普遍都比以往选手高,不过分)

如果考虑大家的max,就确实达到了我的预期,所以或许改为5h的话大家会有更好的表现(可惜我校的制度有点蛋疼)

另外yzh的T3做法就是Errichto的做法,可惜没能大局观地考虑到部分分的提示

本场许多题其实已经在被人切掉的边缘了,着实可惜(不考虑xgc很久前曾经看过A的做法的话就没人当场AC了……)

所以本场最失败的地方应该是识别率有点高,但大家做题量实在太恐怖了,而且我是觉得这三题这么好写,碰到过的人肯定不会口胡的吧,我好难啊

lemon测试包下载链接

CF1240F Football

思维难度较高的防AK担当

展开

算法一

当$k \ge m$时直接让每条边颜色不同,因此$k<m$时随便写个搜索即可($需要关注的点数 \le m/2$),期望得分15

算法二

随机大法,水平达到code1code2这种程度可以获得100分,因为好像还挺有意思的,没有开subtask

算法三

如果告诉你所有边都能保留是否会觉得很神奇,一个最优化问题其实是个构造问题……

事实上,如果你曾经做过CF212A Privatization(题解在最底下),这题就并不难了(所以希望没人做过)

建一个新图$G(V,E’),V=1..2n,E’=(x,y+n) \leftarrow (x,y) \in E$,然后跑CF212A,这样每个点的极差不超过1,将x和n+x合并起来,得到原图,极差不超过2,复杂度同那题,其实就是改两行代码,code


另外有兴趣的可在cf题解区研究下官方题解、yosupo题解

ARC089F ColoringBalls

传统计数题,糅合些小技巧,std代码实际长度只有1K

虽然std都能在0.3s内跑过(仅仅是优化了循环),但马队是1.5s,十分良心地开到了2s(数组甚至没滚动)

下文始终是红色对应块,蓝色对应段(块包含段,所以实际上可能最后里面没有红色)

可能是我OI生涯写过最长最认真的题解了,虽然如果只讲正解的话会短不少?

展开

做法一(得分50)

我只想到了$O(n^3m^4log)$的做法,常数不大跑得飞快,总之atc上跑过了106/112:完整code

很容易想到如何判断一个结果序列可达:将白色区域删除得到若干块,记每个块中蓝色段数为bi,对于B个[bi=0]的块要一个r,其他A个[bi>0]的块需要先rb,再然后$b_i-1$次任意颜色(只要有这么多,怎样都能构造出方案,我们称这为第二阶段)

枚举A和B(接下来说的都是这两层循环内的),相当于A对括号,处理出括号序分配方案

显然是用掉最左边的A个r并且使用A个每个都无法再前移的b以尽快进入第二阶段。同理,第k对括号一定先分配给bi第k大的块。设pi为第i个r对应的b的位置,$p_{A+1}=m$,另外再找B个r,共计预分配了2A+B个操作。

第二阶段与颜色无关,可以用个变量cnt记录,最后就是要求cnt=0:

$i=1 \sim A,cnt=max(0,cnt-[操作序列p_{i-1} \sim p_{i}中没有被预分配的个数])+(b_i-1)$

可以做一个$dp(ln,S,t,cnt)=正在考虑段数为ln的块,前面t个块总体积为S$,降序考虑蓝色段数=ln的块有多少个(因此块数是调和级数)

为了方便转移,预处理$go(cnt,ln,st,j)表示cnt被st+1到st+j的块$依次处理后的结果(当然是排序后,具体处理见上面)

转移的时候枚举有j个段数为ln的块,先把j个看做相同的(即多重集排列数);另外转移和统计答案用到的组合数就是
$$
\begin{aligned}
& 预处理卷积,g(ln,i,j)=j个段数为ln的块,总体积为i的方案数
\\
& 转移考虑大小为i’的块里放ln个蓝色段,系数是个稍作讨论的简单隔板法
\\
& g(ln,i+i’,j+1)+=g(ln,i,j)*( C_{i’-1}^{2ln-2}+ 2C_{i’-1}^{2ln-1}+ C_{i’-1}^{2ln} )
\\
& dp(ln,S+i,t+j,go(cnt,ln,t,j))+=dp(ln+1,S,t,cnt)*g(ln,i,j)*\frac{1}{j!}
\\
& 手动把ln=0处理完后,统计答案时就是n-S分A+B-1组非空和2组可空
\\
& ans=\sum_{cnt合法} dp(0,S,A,cnt)*(A+B)!*C_{(n-S)+2-1}^{(A+B-1)+2-1}
\end{aligned}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
g[0][0][0]=1;fo(i,1,n) fo(j,1,m) g[0][i][j]=C(i-1,j-1)*facinv[j]%MOD;
fo(cc,1,n)
{
g[cc][0][0]=1;
fo(i,0,n) fo(j,0,m-1) if(g[cc][i][j]) fo(ii,1,n-i)
add(g[cc][i+ii][j+1],g[cc][i][j]*( (C(ii-1,cc*2-2)+C(ii-1,cc*2-1)*2+C(ii-1,cc*2))%MOD )%MOD);
fo(i,0,n) fo(j,0,m) g[cc][i][j]=g[cc][i][j]*facinv[j]%MOD;
}
ll ans=0;dp[n+1][0][0][0]=1;
fo(A,0,m)
{
int R=0;mem(inB,0);
if(A) fo(i,1,m) if(str[i]=='r')
{
bool ok=0;fo(j,i+1,m) if(str[j]=='b' and !inB[j]) {inB[j]=1,pos[++R]=j,ok=1;break;}
if(!ok or R==A) break;//posi=被匹配的第i个蓝色
}if(R<A) break;
fo(B,0,m)
{
int cc=0;fo(i,1,m) if(str[i]=='r') cc++,blu[i]=blu[i-1]+(cc>A+B); else blu[i]=blu[i-1]+(!inB[i]);if(cc<A+B) break;
fo(cnt,0,blu[m]) fo(ln,1,n) fo(st,0,A)
{
go[cnt][ln][st][0]=cnt;
fo(j,1,A-st) go[cnt][ln][st][j]=max(0,go[cnt][ln][st][j-1]-(blu[pos[st+j]]-blu[pos[st+j-1]]))+(ln-1);
}
fd(ln,n,1) fo(S,0,n) fo(t,0,min(A,S/ln)) fo(cnt,0,m) dp[ln][S][t][cnt]=0;
fd(ln,n,1)
{
fo(S,0,n) fo(t,0,min(A,S/ln)) fo(cnt,0,blu[m]-blu[pos[t]]) if(dp[ln+1][S][t][cnt])
fo(j,0,A-t) if(go[cnt][ln][t][j]<=blu[m]-blu[pos[t+j]]) fo(i,0,n-S)
add(dp[ln][S+i][t+j][go[cnt][ln][t][j]],1ll*dp[ln+1][S][t][cnt]*g[ln][i][j]%MOD);
}
fo(S,0,n) fo(cnt,0,m) if(dp[1][S][A][cnt]) fo(S2,0,n-S) if(g[0][S2][B])
add(ans,1ll*dp[1][S][A][cnt]*g[0][S2][B]%MOD*fac[A+B]%MOD*C(n-S-S2+1,A+B)%MOD);
}
}

做法二(得分100)

发现我们需要放弃$a’=max(a+X-Y,0)$,换一种判断合法性的方法

注意到我们的这个过程是整体已知的,所以有条件倒过来做

具体地,其实就是过程中有个上界,如果达到了上界,这个时间段内再多增量也是没用的。那我们枚举每一个顶了上界的位置,要求依然满足,即把条件转化为$\forall 后缀i,\sum_{t=i}^A b_t \le up_i$

这个up可以倒推求,$up_i=up_{i+1}+blu(pos_i \sim pos_{i+1})+1$(blu为未分配的数量和),因此升序考虑ln做dp

当然此时复杂度还没有优化,但注意到之前记录的总长度S和这个b的和,这两个信息只需要一个就能计算出方案数了。

具体地,有$(2S-A)+B+(A+B-1)$个非空段,$2A+2$个可空段,隔板法即可

成功省掉了卷积S的那两次循环且不再与n有关,变成了$O(m^5log)$,完整code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
fo(i,1,m) if(str[i]=='r')
{
if(R==A) break;
bool ok=0;fo(j,i+1,m) if(str[j]=='b' and !inB[j]) {inB[j]=1,pos[++R]=j,ok=1;break;}
if(!ok) break;
}if(R<A) break;
fo(B,0,m)
{
int cc=0;fo(i,1,m) if(str[i]=='r') cc++,blu[i]=blu[i-1]+(cc>A+B); else blu[i]=blu[i-1]+(!inB[i]);if(cc<A+B) break;
up[A+1]=0,pos[A+1]=m;fd(i,A,1) up[i]=up[i+1]+(blu[pos[i+1]]-blu[pos[i]])+1;reverse(up+1,up+A+1);
dp[0][0][0]=1;fo(ln,1,m) fo(i,0,A) fo(S,0,up[i]) dp[ln][i][S]=0;
fo(ln,1,m) fo(i,0,A) fo(S,0,min(up[i],up[A]-ln*(A-i))) if(dp[ln-1][i][S])
for(int ad=0;i+ad<=A and S+ad*ln<=up[i+ad];ad++)
add(dp[ln][i+ad][S+ad*ln],dp[ln-1][i][S]*facinv[ad]%MOD);
fo(S,0,up[A]) if(dp[m][A][S])
{
ll feikong=2*S+2*B-1,kekong=A*2+2;
add(ans, dp[m][A][S]*C(n+kekong-1, feikong+kekong-1 )%MOD*fac[A+B]%MOD*facinv[B]%MOD );
}
}

做法三(得分60~70)

整数分拆做法,xht

总结

做法一并不能因此也得到优化,因为就算不记录S,也还要记录bi的和

可见做法二优越的关键在于它需要的信息,和原本就需要的东西,有一定的重叠

$a’=max(a+X-Y,0)$这种东西,能够转化成现在的「某个变量在变化过程中处处受某个范围的限制」,主要条件就是整个过程已知,所以也算是题目性质的妙用

另外这题好像恰好是2020集训队作业里面的(难受),希望不会被各位爆破

下面三位都是dp,我是跟马队学习的,有幸跑得比三位都快,另两位做法不太清楚xyxmyhzyy

codejam Qualification Round 2020 E Indicium

这个Latin Square的性质还是挺优美的,但并不是一道科技题,应该是平均分最高的题目

部分分有启发性,不会的话不建议直接跳过

另外CF上的相关讨论可能可以发现别的做法

展开

算法一(得分10~30)

对于$K=n+2、n^2-2$,偶数的情况可以构造,奇数的话据说可以随机通过

例如,奇数列1 2 3 4 5 6...n,偶数列n n-1,n-2...1,最后交换第n-1和n列,具体见文件夹:工具人-c_(n+2)

算法二(得分20)

对于$K=n+3、n^2-3$,以n+3为例,一定是n-2个1、1个2、1个3,随便构造

例如以3 1 2 4 5 6...n为置换,最后交换第n-1和n列,具体见文件夹:工具人-c_(n+3)

算法三(人工控制为40~80)

经过上面虽然不太完美但都比较简单(连我都会)的分析,感受出了一点大致思路,就是$B、C、(n-2) \cdot A$,然后交换最后两列,等价于对角线都是A,且最后两列的上下分别是B和C

那么只要不是$K=n+2、n^2-2$,枚举下发现$n \le 100$除了$n=4,K=10$,都能分解为$B \ne C$,特判一下,剩下同算法二,没写

算法四(结合以上做法,得分100)

问题集中在算法一奇数的情况(抛开随机不谈)

Errichto的构造法,稍微补充一句,就是最后那里应该是从左往右每次填两个,填法唯一

这个我觉得算是水法,主要得益于性质比较优美,所以能够有个比较具规律性的方法

算法五(一般性优美做法,得分100)

先看几道简单题感受一下:


2018 ICPC North American Qualifier Contest L Superdoku有数据和英文题解

题意:给定前k行,构造

核心结论:前k行合法时一定有合法解

证明:如果每次直接二分图匹配(n个数和n列求完美匹配),那我们只需要证明接下来每行做的时候都有解。考虑hall定理,每个数和每列的度数都是n-k,对于列的一个子集C,连向数字那一侧的边数是$(n-k)|C|$,因此连过去的点集大小一定不小于|C|(否则到不了这个边数)


2019 ICPC Asia Danang Regional Contest Latin Square

每次匹配是n-k列和n-k个颜色,还是设列子集C,$|C|*(n-k-i) \le |n(C)|*(n-k-i \sim n-k),|n(C)| \ge |C|$


特殊之处在于对角线上的数。首先很快知道的是,$k=n+1或n^2-1$都是无解的,因为我们能直接得知其组成是${(n-1) \cdot A,1 \cdot B}$,这是不可能发生的(同理,n=3时,k=5和7是无解的,下文忽略这些简单无解情况)。经过上面两题,我们知道应该使固定的条件尽可能简单且具有一点点性质便于hall。

如果k是n倍数就所有相等,否则的话因为不能选n-1个相同我们尝试考虑$B、C、(n-2) \cdot A$($A \ne B,A \ne C$),下面将证明一定有解,所以我们可以直接枚举得到任意一组$(A,B,C)$去做(一定有分解方案)

如果把B和C放最底下会发现非常麻烦,如果放在前面两行,可以直接构造出前两行的合法解(A位置已经唯一了,所以A可以当做不存在),然后当上面有k行时,下面的行就是n-1列匹配n-1种数。对于数,考虑第k+1列,上面的k种数度数都是n-k,其他的(n-1)-k种数的数是n-k-1;对于列,前k列度数是(n-1)-(k-1),后面n-1-k列度数是(n-1)-k。和上面两题做类似推导,枚举任意侧子集,此时看起来分数会比|C|小,但其实没法$ \le |C|-1$,因此这需要n-k个额外-1,而现在最多提供n-k-1个

UPD:修复证明后,另一种实现上五五开的做法就显现出了它在证明上的优美,就是简单构造出对角线上出现的数的一组解,然后枚举每个数一次性填完,这样二分图就是匹配行和列,这是个正则图,一定满足hall定理

$O(n*二分图匹配(n,n^2))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
bool asked[N];int gf[N];set<int> can[N];
int A,B,C;
bool FD(int bf[],int x,int ban)//shorter than flow
{
if(x==ban){ bf[x]=A;return 1;}
for(auto y:can[x]) if(!asked[y] and y!=A)
{
asked[y]=1;
if(!gf[y] or FD(bf,gf[y],ban)) {gf[y]=x,bf[x]=y;return 1;}
}return 0;
}
int ans[N][N];
void main()
{
fo(T,1,qread())
{
printf("Case #%d: ",T);
int n=qread(),K=qread();if(n==3 and (K==5 or K==7)){puts("IMPOSSIBLE");continue;}
if(K==n*n-1 or K==n+1){puts("IMPOSSIBLE");continue;} puts("POSSIBLE");
if(K%n==0)
{
fo(i,0,n-1){ fo(j,0,n-1) write1((K/n-1+j+n-i)%n+1);puts(""); }
continue;
}
A=0;fo(a,1,n) fo(b,1,n) fo(c,1,n) if(a!=b and a!=c and a*(n-2)+b+c==K) A=a,B=b,C=c; assert(A>0);
if(B!=C)
{
ans[1][1]=B,ans[1][2]=A,ans[1][3]=C;int now=3;fo(i,1,n) if(i!=A and i!=B and i!=C) ans[1][++now]=i;
fo(i,1,n-1) ans[2][i]=ans[1][i+1];ans[2][n]=ans[1][1];
}
else
{
ans[1][1]=B,ans[1][2]=A;int now=2;fo(i,1,n) if(i!=A and i!=B) ans[1][++now]=i;
fo(i,1,n-1) ans[2][i]=ans[1][i+1];ans[2][n]=ans[1][1];swap(ans[2][2],ans[2][n]);
}//构造前两行
fo(j,1,n) {can[j].clear();fo(i,1,n) if(i!=ans[1][j] and i!=ans[2][j]) can[j].insert(i);}
fo(i,3,n){ mem(gf,0);fo(j,1,n) mem(asked,0),FD(ans[i],j,i);fo(j,1,n) can[j].erase(ans[i][j]); }
fo(i,1,n){ fo(j,1,n) write1(ans[i][j]);puts(""); }
}
}

可参考资料:VK Cup 2012 Finals CF212A Privatization

题意:给出一张二分图,两侧点数分别是n1和n2(原n,m),有m条边(原t),给每条边染色$[1,k]$,要求最小化$\sum_x [x相邻的边中,每种颜色所占个数的极差]$且输出方案,$n1,n2,m \le 200,k \le 5e3$

请先思考后再展开

好像大部分人都是网络流,给出一个$O(m^2/K+m(K+n))$的做法

首先一个明显的下界是$\sum [deg_x\%k>0]$,而我们可以达到这个下界,构造方法即为证明

将每个点拆开使得每个点的点度不超过k,前面若干个点都是K最后为$deg_x\%K$,每个点周围颜色都不同,与原问题等价

依次加入每条边$(x,y)$,如果存在一个颜色能用就直接加上,否则找到两点各自可用的一个颜色c1和c2,然后从y开始找一条$c1,c2,c1,c2…$的增广路径。具体地,第一次时令边为c1,那么找到原本y上c1那条边,将其变为c2,如果合法了就结束,否则继续执行这个过程。注意到如果想成环必须是奇环,所以二分图上走出来的一定是简单路径,也因此一定存在这样的路径

感觉这个做法比较厉害的地方在于,有冲突能利用冲突继续走

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vc<pii> to[N];int col[N];
void solve(int x,int c1,int c2)
{
col[to[x][c1].SE]=c2;swap(to[x][c1],to[x][c2]);
if(to[x][c2].FR) solve(to[x][c2].FR,c2,c1);
}
void main()
{
int n1=qread(),n2=qread(),m=qread(),K=qread();
fo(i,1,m)
{
int x=qread(),y=n1+qread();
if(deg[x]%K==0) to[cur[x]=++id].resize(K);deg[x]++;x=cur[x];
if(deg[y]%K==0) to[cur[y]=++id].resize(K);deg[y]++;y=cur[y];
int c1;fo(t,0,K-1) if(!to[x][t].FR) c1=t;
if(to[y][c1].FR){ int c2;fo(t,0,K-1) if(!to[y][t].FR) c2=t;solve(y,c1,c2); }
to[x][c1]={y,i},to[y][c1]={x,i},col[i]=c1;
}int ans=0;fo(i,1,n1+n2) ans+=(deg[i]%K>0);write2(ans);fo(i,1,m) write1(1+col[i]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/2ba3d240.html
转载请注明出处,谢谢!