2020.12.02 比赛总结题解合集_综合

最后一次 OI 模拟赛。
果然裂开了，~~说实话我还担心这次考好浪费 RP 呢~~。
总算是结束了这十次的 NOIP 赛前模拟赛体验。经过了这十场模拟赛的历练，感觉虽然学文化课很吃力，但还是比学竞赛轻松呢…

Part 1 总结

期望得分： $100 + 50 + 100 + 30 = 280$ 。
实际得分： $65 + 20 + 100 + 0 = 185$ 。
T1 猜错结论了，因为前几次考试的恐怖经历让我没有写对拍，结果就挂了。
T2 出题人偷懒直接搬运原题数据， $O(n^2)$ 本来就只能得 $20$ 。
T3 想不到又这么多人都会…
T4…真不想说了…NOIP 前把暴毙滚粗豪华套餐背100遍…真注意不到这东西…
今天两道计数题目都做得不好，说明组合计数是我的弱项，明天考虑加强一下。
~~反正马上就可以跟这东西说拜拜了。~~

Part 2 题解

T1-bricks

原题：CF1355E Restorer Distance
令 $f (x)$ 表示我们将高度统一为 $x$ 时花费的最小代价，显然这是一个单峰函数，我们可以选择直接三分。
~~然而我两年没写过了怕写挂。~~
当然，我们进一步仔细思考，容易发现当 $C$ 较小时，我们一定会尽量使 $C$ 的代价占比更多。
容易发现当我们的 $x$ 取到 $hˉ=∑i=1nhin\bar{h}=\frac{\sum^n_{i=1}h_i}{n}$ $C$ 的代价占比更多，由于要求 $x$ 为整数我们需要取 $f(?hˉ?)f(\lfloor \bar{h}\rfloor)$ 与 $f(?hˉ?)f(\lceil \bar{h}\rceil)$ 的最小值。
接下来考虑 $C$ 和 $A, B$ 中的一个极大时，~~由于样例的误导我直接取了 $min\{f(mn),f(mx)\}$~~ 。事实上我们不仅仅可能取 $m n, m x$ 两个值，由于本身这两个位置会使其他模板操作次数过大，因此可能还会微调，因此我们需要求 $min?i=1nf(hi)\min^n_{i=1}f(h_i)$ 。
以后写完了这种感觉很悬的题目一定要记得验证…
复杂度： $O(nlog?n)O(n\log n)$ 。

T2-rgbgraph

原题：LOJ6160「美团 CodeM 初赛 Round A」二分图染色
感觉这题挺难想的，为什么都切了呢…

算法1

本题计数的难点在于我们红边和蓝边的染色会互相影响，我们虽然可以分别计算红边和蓝边的匹配，但是却存在一条边被红色和蓝色同时染色的情况。
考虑容易，我们枚举我们重合的染色的边数为 $p$ ，显然这 $p$ 条边会是一个匹配，然后我们再删去这 $p$ 对匹配，那么问题就变成了求在 $n ? p$ 对点上无限制选择两组匹配的方案数。
我们设在 $n$ 对点上选择若干对（可以不选）匹配的方案数为 $f_i$ ，那么有：
$∑p=0n(?1)p(np)2p!×fn?p2\sum^n_{p=0}(-1)^{p}\binom{n}{p}^2p!\times f^2_{n-p}$
我们很容易得出一个 $O (n)$ 求单个 $f_n$ 的式子：
$fn=∑i=0n(ni)2i!f_n=\sum_{i=0}^n\binom{n}{i}^2i!$
于是我们得到一个 $O(n^2)$ 的做法。

算法2

由于题目的 $n$ 过于大，无法 NTT，显然我们需要考虑递推 $O (n)$ 求出 $f_n$ 。~~结果我失败了~~
在二分图上比较难想，我们可以考虑将二分图抽象成一个二维矩阵，我们需要求在上面任意摆若干个棋子，且两两不在同行同列的方案数。
其实我们很久很久之前也做过更复杂的题目，~~但是我还是不会~~。
我们考虑从 $(n?1)×(n?1)(n-1)\times (n-1)$ 的矩阵增加一行一列，现在我们可以在这新增的一行一列 $2 n ? 1$ 个空格上放置一个棋子，或者选择不放：
2020.12.02 比赛总结题解合集
但是，很有可能我们选择的位置和之前放好的棋子矛盾了，这时候我们考虑将这颗冲突的棋子也放在新增的某个位置：

这样的方案数会是 $2n×fi?12n\times f_{i-1}$ 。
我们很容易发现这样是会算重复的，就如同下图这种情况本质上和上面这种情况是相同的：
2020.12.02 比赛总结题解合集
考虑算重的方案数就是我们再去掉这冲突的一行一列，余下的 $n ? 2$ 行摆放的方案数。也即是 $(n?1)2×fn?2(n-1)^2\times f_{n-2}$ 。
因此最终的递推式子是：
$fn=2n×fn?1?(n?1)2×fn?2f_n=2n\times f_{n-1}-(n-1)^2\times f_{n-2}$
如果你推导这个式子和我一样吃力的话，可能就只能找规律了…
复杂度： $O (n)$ 。

T3-cyclesort

原题弱化（不输出方案）：「eJOI2018」循环排序
~~样例/部分分观察题。~~
还是要感谢 eJOI 精心设计的部分分和样例，真的很有提示作用。
从部分分着手一步一步推到正解，这题也就逐渐变得容易起来了。（CF 上好像就是因为没什么提示就成了 3100 的题目）
结果考完之后发现一堆人都 AC 了这道题…

算法1：20%

$ai≤2a_i\leq 2$

考虑最终我们需要变为 1111....2222... 这样的样子，设我们 1 的个数为 $p$ ，那么在 $p$ 前面的 2 就必须移到 $p$ 位置后面，在 $p$ 后面的 1 就必须移到 $p$ 位置前面，这两者的数目显然相等。
我们可以将这两种数交替连起来，这样我们就只需要 1 次操作就能够完成。

算法2：30%

${a_i\}$ 为 $1 ? n$ 的排列。

提起排列，我们很容易联想到我们排列中本来就存在的“环”，那就是置换。
很容易发现，我们可以对一个排列中每一个大小大于 $1$ 的循环进行一次循环排序，这样做显然会花费最小的 $s$ ，但是不一定会消耗最小的次数。
例如我们样例 4,5 中呈现的情况：我们可以先将我们所有要循环排序的环连在一起做一次排序，这样我们最终会恰好剩下一个大小为循环个数的环，我们再对这个环做一次循环排序即可。
那么我们设循环个数为 $c n t$ ，我们环的大小总和为 $s i z$ ，当 $siz+cnt≤ssiz+cnt\leq s$ 时，我们一定能够 $2$ 步将这个排列进行排序。
再考虑我们减少我们连在一起排序的循环数目，每当我们减少一个环，我们会恰好使 $s ? 1$ ，那么我们就可以直接根据限制计算出我们现在能做到的最小操作步数为多少了（显然操作步数不会大于 $c n t$ ）。

算法3：100%

现在我们解决了排列的问题，我们再来考虑存在若干个数相同的情况时我们如何解决。
受到算法 1的启发，我们发现我们可以将最终我们每种数字停留的区间看成一个连通块，对于本身就在对应连通块中的数字，我们完全可以不去管它。对于不在对应连通块中的数字，我们模仿算法2将其当前所在的连通块和其最终属于的连通块连一条边。
现在我们只需要用最少的环来覆盖完这图中所有的边即可。
容易发现我们的图中有一个显著的性质：每个点的入度和出度相等。
这意味这对于每一个弱联通块，它一定存在一条能一次覆盖每条边的欧拉路径。
因此我们只需要求这个图中的连通块个数即可，随便用并查集做做就行了。
复杂度： $O (n)$ 。
对于输出方案，我们只需要找到每个图的欧拉回路方案然后模拟即可。

T4-parentrises

原题弱化（只有 $P 2$ ）：LOJ2713「BalkanOI 2018 Day2」Parentrises
其实我们可以首先考虑 P1。
很容易得到一个 $O(n^3)$ 判定一个括号串是否合法的 dp 方法，即 $f_{i,L,R}$ 现在处理了前 $i$ 个字符忽略蓝色之后 $\pm 1$ 的和为 $L$ ，忽略红色之后 $\pm 1$ 的和为 $R$ 。
我们只需要判断第 $n$ 步时我们能否停留在 $(0, 0)$ 即可。注意到以 $(0, 0)$ 为中心相同的曼哈顿距离的点可达性的情况是相同的。考虑我们每次只看每个位置与 $(0, 0)$ 的曼哈顿距离 $d$ ，我们加左括号可以使 $d + 1$ 或 $d + 2$ ，加右括号可以使 $d ? 1$ 或 $d ? 2$ 。我们可以求出这个距离最终能达到的区间范围 $[L, R]$ ，容易发现的是，我们可以通过改变一些位置的行走策略使得其距离每次递减 $1$ ，因此我们这个范围内所有的整数都是可达的。
验证了可达性之后，我们可以从最终距离为 $R$ 的策略开始，将字符串后方连续一部分染色策略改变，每次改变会使距离恰好减一，因此我们改变最后 $R$ 个即可。
复杂度： $O (n)$ 。
再来看 P2 ，问题就很简单了。
直接定义 $f_{i,L,R}$ 表示现在处理了前 $i$ 个字符使得括号串离 $(0, 0)$ 的距离的范围是 $[L, R]$ 的方案数总合。枚举每个位置选择左括号还是右括号即可。
复杂度： $O(n^3)$ 。

Part 3 实现

T1-bricks

贪心做法

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;#define LL long long
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 200000
#define INF 1000000000000000000LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}return x*F;
}int n;LL A,B,C;
LL sum,ans,h[MAXN+5],lsum[MAXN+5],rsum[MAXN+5];LL f(LL x){
    LL L=0,R=0;int p=lower_bound(h+1,h+n+1,x)-h;L=x*(p-1)-lsum[p-1],R=rsum[p]-x*(n-p+1);LL v=min(L,R);L-=v,R-=v;return min((L+v)*A+(R+v)*B,C*v+A*L+B*R);
}int main(){
    freopen("bricks.in","r",stdin);freopen("bricks.out","w",stdout);n=read(),A=read(),B=read(),C=read();for(int i=1;i<=n;i++){
    h[i]=read();sum+=h[i];}sort(h+1,h+n+1);for(int i=1;i<=n;i++)lsum[i]=lsum[i-1]+h[i];for(int i=n;i>=1;i--)rsum[i]=rsum[i+1]+h[i];ans=INF;for(int i=1;i<=n;i++)ans=min(ans,f(h[i]));printf("%lld\n",min(ans,min(f(sum/n),f((sum+n-1)/n))));
}

三分做法

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;#define LL long long
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 100000
#define INF 2000000000
#define MOD 1000000007
#define mem(x,v) memset(x,v,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}return x*F;
}int A,B,C,n,h[MAXN+5];LL f(LL x){
    LL L=0,R=0;for(int i=1;i<=n;i++)if(h[i]<=x)L+=x-h[i];else R+=h[i]-x;LL v=min(L,R);L-=v,R-=v;return min((v+L)*A+(v+R)*B,L*A+R*B+v*C);
}int main(){
    freopen("bricks.in","r",stdin);freopen("bricks.out","w",stdout);n=read(),A=read(),B=read(),C=read();for(int i=1;i<=n;i++)h[i]=read();LL l=0,r=INF;while(l+1<r){
    LL p1=l+(r-l+1)/3,p2=r-(r-l+1)/3;if(f(p1)<=f(p2))r=p2;else l=p1;}printf("%lld\n",min(f(l),f(l+1)));
}

T2-rgbgraph

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;#define LL long long
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 10000000
#define INF 1000000000
#define MOD 1000000007LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}return x*F;
}int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return a-b<0?a-b+MOD:a-b;}
int mul(int a,int b){
    return (1LL*a*b)%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a),b>>=1;}return res;
}int n,fac[MAXN+5],ifac[MAXN+5];
int f[MAXN+5],ans;void prepare(){
    fac[0]=1;for(int i=1;i<=MAXN;i++)fac[i]=mul(fac[i-1],i);ifac[MAXN]=fst_pow(fac[MAXN],MOD-2);for(int i=MAXN;i>=1;i--)ifac[i-1]=mul(ifac[i],i);
}
int Comb(int a,int b){
    return mul(fac[a],mul(ifac[a-b],ifac[b]));
}int main(){
    freopen("rgbgraph.in","r",stdin);freopen("rgbgraph.out","w",stdout);prepare();n=read();f[0]=1,f[1]=2;for(int i=2;i<=n;i++)f[i]=dec(mul(2*i,f[i-1]),mul(mul(i-1,i-1),f[i-2]));for(int p=0;p<=n;p++){
    int tot=mul(fac[p],mul(Comb(n,p),Comb(n,p)));if(p&1)ans=dec(ans,mul(tot,mul(f[n-p],f[n-p])));else ans=add(ans,mul(tot,mul(f[n-p],f[n-p])));}printf("%d\n",ans);
}

T3-cyclesort

考试版本

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;#define LL long long
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 500000
#define INF 1000000000
#define MOD 1000000007LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}return x*F;
}int n,tn,cnt,s,a[MAXN+5],b[MAXN+5],val[MAXN+5];
int fa[MAXN+5],siz[MAXN+5];int xfind(int x){
    return (fa[x]==x)?x:fa[x]=xfind(fa[x]);}
void bin(int u,int v){
    int a=xfind(u),b=xfind(v);if(a==b)return ;fa[b]=a,siz[a]+=siz[b];
}int main(){
    freopen("cyclesort.in","r",stdin);freopen("cyclesort.out","w",stdout);tn=n=read(),s=read();for(int i=1;i<=n;i++)val[i]=a[i]=read();sort(val+1,val+n+1);int pn=unique(val+1,val+n+1)-val-1;for(int i=1;i<=n;i++)b[i]=a[i]=lower_bound(val+1,val+pn+1,a[i])-val;sort(b+1,b+n+1);for(int i=1;i<=pn;i++)fa[i]=i,siz[i]=1;for(int i=1;i<=n;i++)if(b[i]!=a[i])bin(b[i],a[i]);else tn--;for(int i=1;i<=pn;i++)if(xfind(i)==i)if(siz[i]>1)cnt++;if(tn==0)puts("0");else if(s<tn)puts("-1");else printf("%d\n",min(cnt,max(tn+cnt-s+2,2)));
}

原题实现

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;#define LL long long
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 500000
#define INF 1000000000
#define MOD 1000000007LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}return x*F;
}int n,cnt,s,F,tmp;
int a[MAXN+5],b[MAXN+5],val[MAXN+5];
int head[MAXN+5],ecnt;
struct edge{
    int to,nxt,vis;
}e[MAXN+5];
vector<int> P[MAXN+5];void link(int u,int v){
    e[++ecnt]=(edge){
    v,head[u]},head[u]=ecnt;
}void dfs(int x){
    for(int &i=head[x];i;){
    int v=e[i].to;i=e[i].nxt;dfs(a[v]);P[cnt].push_back(v);}
}void Print(int id){
    printf("%d\n",P[id].size());for(int i=P[id].size()-1;i>=0;i--)printf("%d ",P[id][i]);puts("");
}int main(){
    freopen("cyclesort.in","r",stdin);freopen("cyclesort.out","w",stdout);n=read(),s=read();for(int i=1;i<=n;i++)val[i]=a[i]=read();sort(val+1,val+n+1);int pn=unique(val+1,val+n+1)-val-1;for(int i=1;i<=n;i++)b[i]=a[i]=lower_bound(val+1,val+pn+1,a[i])-val;sort(b+1,b+n+1);for(int i=1;i<=n;i++)if(b[i]!=a[i])link(b[i],i),s--,F=1;if(!F){
    puts("0");return 0;}else if(s<0){
    puts("-1");return 0;}for(int i=1;i<=pn;i++)if(head[i])cnt++,dfs(i);if(cnt==1){
    puts("1");Print(1);return 0;}s=min(s,cnt);if(s>1)printf("%d\n",cnt-s+2);else printf("%d\n",cnt);for(int i=cnt;i>s;i--)Print(i);if(s){
    int tot=0;for(int i=1;i<=s;i++)tot+=P[i].size();printf("%d\n",tot);for(int i=s;i>=1;i--)for(int j=P[i].size()-1;j>=0;j--)printf("%d ",P[i][j]);puts("");if(s>1){
    printf("%d\n",s);for(int i=1;i<=s;i++)printf("%d ",P[i][P[i].size()-1]);}}
}

T4-parentrises

考试版本

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;#define LL long long
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 300
#define INF 1000000000
#define MOD 1000000007
#define mem(x,v) memset(x,v,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}return x*F;
}int T,f[MAXN+5][MAXN+5][MAXN*2+5],ans[MAXN+5];
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
void upd(int &a,int b){
    a=add(a,b);}int main(){
    freopen("parentrises.in","r",stdin);freopen("parentrises.out","w",stdout);f[0][0][0]=1;for(int i=1;i<=MAXN;i++){
    for(int j=0;j<=i;j++)for(int k=0;k<=2*i;k++){
    upd(f[i][j+1][k+2],f[i-1][j][k]);if(k)upd(f[i][max(j-2,0)][k-1],f[i-1][j][k]);}for(int j=0;j<=2*i;j++)upd(ans[i],f[i][0][j]);}T=read();while(T--){
    int n=read();printf("%d\n",ans[n]);}
}

原题实现

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;#define LL long long
#define Pr pair<int,int>
#define X first
#define Y second
#define INF 1000000000
#define MOD 1000000007
#define mem(x,v) memset(x,v,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}return x*F;
}int P,T;
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
void upd(int &a,int b){
    a=add(a,b);}struct subtask1{
    #define MAXN 1000000int n,ans[MAXN+5];char s[MAXN+5];int check(){
    int mx=0,mn=0;for(int i=1;i<=n;i++)if(s[i]=='(')mn+=1,mx+=2;else{
    mn=max(0,mn-2),mx-=1;if(mx<0)return -1;}return (mn>0)?-1:mx;}void solve(){
    T=read();while(T--){
    scanf("%s",s+1);n=strlen(s+1);int cnt=check();if(cnt==-1)puts("impossible");else{
    for(int i=1;i<=n;i++)ans[i]=0;int F=-1,p=n+1;if(cnt){
    for(int i=n;i>=1;i--){
    //从后往前改变策略if(s[i]=='(')ans[i]=F,F*=-1;cnt--;if(!cnt){
    p=i;break;}}}F=-1;for(int i=1;i<p;i++)if(s[i]==')')ans[i]=F,F*=-1;for(int i=1;i<=n;i++)if(ans[i]==1)putchar('R');else if(ans[i]==-1)putchar('B');else putchar('G');puts("");}}}#undef MAXN
}P1;
struct subtask2{
    #define MAXN 300int f[MAXN+5][MAXN+5][MAXN*2+5],ans[MAXN+5];void solve(){
    f[0][0][0]=1;for(int i=1;i<=MAXN;i++){
    for(int j=0;j<=i;j++)for(int k=0;k<=2*i;k++){
    upd(f[i][j+1][k+2],f[i-1][j][k]);if(k)upd(f[i][max(j-2,0)][k-1],f[i-1][j][k]);}for(int j=0;j<=2*i;j++)upd(ans[i],f[i][0][j]);}T=read();while(T--){
    int n=read();printf("%d\n",ans[n]);}}#undef MAXN
}P2;int main(){
    freopen("parentrises.in","r",stdin);freopen("parentrises.out","w",stdout);P=read();if(P==1)P1.solve();else P2.solve();
}

Part 4 resource

T1

2020.12.02 比赛总结题解合集

T2

2020.12.02 比赛总结题解合集

T3

2020.12.02 比赛总结题解合集

T4

2020.12.02 比赛总结题解合集

END

感谢大家耐心的阅读，可能是最后一次写 OI 题解了。
虽然平时总是抱怨写题解是一个很麻烦很浪费时间的事，但总还是会一字一句的认真的写下去。
感谢你们的一路陪伴，再见！