AGC030 A~F 題解
題目連結
第一次嘗試做一整場AGC，結果做了一整天。。。還是開個部落格記錄一下吧。
A - Poisonous Cookies
一道難度評分高達90分的思博題。
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main(){
scanf("%d%d%d",&a,&b,&c);
printf("%d",b+min(c,a+b+1));
return 0;
}
B - Tree Burning
一開始以為可以直接順時針走一個，逆時針走一個，然後順時針再走一個，逆時針再走一個，以此類推。然後觀察樣例可以發現，還可能會先沿某一個方向走若幹個點，再開始上面的循環過程，這個貪心做法可以用數學歸納法證明是正确的。
于是接下來就枚舉走到哪個點時開始循環，循環後的部分可以通過預處理字首和與字尾和做到 \(\mathcal O(n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int L,n,x[N];
ll suf[N],pre[N];
int main(){
scanf("%d%d",&L,&n);
for(int i=1;i<=n;++i) scanf("%d",&x[i]);
ll ans=0;
for(int i=1;i<=n;++i) pre[i]=pre[i-1]+x[i];
for(int i=n;i>=1;--i) suf[i]=suf[i+1]+L-x[i];
for(int i=1;i<=n;++i){
ll now=0;
if((n-i+1)&1){
int t=n-(n-i)/2+1;
now+=2ll*suf[t]+2ll*(pre[t-1]-pre[i-1])-x[t-1];
}
else{
int t=n-(n-i+1)/2+1;
now+=2ll*suf[t]+2ll*(pre[t-1]-pre[i-1])-(L-x[t]);
}
if(i==n) now=x[n];
ans=max(ans,now);
}
for(int i=n;i>=1;--i){
ll now=0;
if(i&1){
int t=i/2;
now+=2ll*pre[t]+2ll*(suf[t+1]-suf[i+1])-(L-x[t+1]);
}
else{
int t=i/2;;
now+=2ll*pre[t]+2ll*(suf[t+1]-suf[i+1])-x[t];
}
if(i==1) now=L-x[1];
ans=max(ans,now);
}
printf("%lld\n",ans);
return 0;
}
C - Coloring Torus
神仙構造題。
如果 \(k\le 500\) 那麼一個容易想到的做法是對每一行/每一列填同一個顔色，這樣一定合法。考慮将這一個構造改裝到對角線上（對角線是指 \(i+j\bmod n\) 相同的點）。但這樣做依然隻能染 \(n\) 個顔色。
如何變成 \(2n\) 個顔色呢？考慮對于每個對角線，給它配置設定兩種顔色交替出現，比如下圖中的 \(2,5\) 兩種顔色，就可以通過此題。
1 2 3 4
2 3 5 1
3 4 1 2
5 1 2 3
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int k,n,a[N][N];
int main(){
scanf("%d",&k);
if(k<500){
n=k;
printf("%d\n",n);
for(int i=1;i<=k;puts(""),++i) for(int j=1;j<=k;++j) printf("%d ",i);
return 0;
}
else{
n=500;k-=n;
for(int i=1;i<=n;++i){
int ta=i,tb=i;
if(k) tb=n+i,k--;
for(int x=1,y=i;x<=n;++x,y=y%n+1)
a[x][y]=x&1?ta:tb;
}
printf("%d\n",n);
for(int i=1;i<=n;puts(""),++i) for(int j=1;j<=n;++j) printf("%d ",a[i][j]);
}
return 0;
}
D - Inversion Sum
由于 \(n\) 很小，考慮直接對于位置 \(a_i,a_j\) 計算有多少種方案使得它們最終對答案做出貢獻。
考慮倒着模拟整個過程，記 \(dp_{i,j}\) 表示所選擇的兩個數目前分别在位置 \(i\) 和 \(j\) 上時，有多少種方案使得最終位置滿足前一個數大于後一個數。初始 \(dp_{i,j}=[i>j]\)。然後倒着掃一遍所有交換操作 \((x,y)\)，可以發現我們隻用對包含 \(x,y\) 的 \(\mathcal O(n)\) 個狀态進行轉移，這樣一來複雜度就是 \(\mathcal O(nq)\) 的了。
最後再枚舉 \(a_i,a_j\) ，根據它們的大小關系計算對答案的貢獻即可。
#include<bits/stdc++.h>
using namespace std;
const int N=3010,mod=1e9+7,iv=(mod+1)/2;
int n,q,a[N],x[N],y[N],dp[N][N];
inline void inc(int &x,int y){x=(x+y>=mod)?x+y-mod:x+y;}
inline int add(int x,int y){return (x+y>=mod)?x+y-mod:x+y;}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=q;++i) scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;++i)
for(int j=1;j<i;++j)
dp[i][j]=1;
for(int i=q;i>=1;--i){
int xx=x[i],yy=y[i];
for(int j=1;j<=n;++j){
if(j!=xx&&j!=yy){
int a=dp[xx][j],b=dp[yy][j];inc(a,b);
dp[xx][j]=dp[yy][j]=1ll*a*iv%mod;
a=dp[j][xx],b=dp[j][yy];inc(a,b);
dp[j][xx]=dp[j][yy]=1ll*a*iv%mod;
}
}
int a=dp[xx][yy],b=dp[yy][xx];inc(a,b);
dp[xx][yy]=dp[yy][xx]=1ll*a*iv%mod;
}
int ans=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
if(i==j) continue;
if(a[i]<a[j]) ans=add(ans,dp[i][j]);
else if(a[i]>a[j]) ans=add(ans,(mod+1-dp[i][j])%mod);
}
for(int i=1;i<q;++i) ans=add(ans,ans);
printf("%d\n",ans);
return 0;
}
E - Less than 3
神仙題，E比F難系列。考慮在序列上的 \(0,1\) 之間連一條紅線，在 \(1,0\) 之間連一條藍線，在序列的最左側與最右側分别增加若幹條紅藍交替的線，那麼一次操作就相當于将一條線左移或者右移，移動過程中要求不能有相鄰的兩條線的距離 \(>2\)，下面是官方題解的圖檔：
于是我們隻需要找一個 \(s\) 中的線與 \(t\) 中線的對應關系。找到關系後隻需要固定位置不變的線，将其他線分成多個塊，每個塊内部向同一個方向移動即可完成構造。于是我們隻需要 \(\mathcal O(n)\) 的枚舉對應方案即可做到 \(\mathcal O(n^2)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=5010;
char s[N],t[N];
int n,a[N],b[N],c1,c2;
int ans=0x3f3f3f3f;
int main(){
scanf("%d",&n);
scanf("%s%s",s+1,t+1);
for(int i=1;i<n;++i) if(s[i]!=s[i+1]) a[++c1]=i;
for(int i=1;i<n;++i) if(t[i]!=t[i+1]) b[++c2]=i;
for(int i=-c2;i<=c1+1;++i){
if((i&1)&&s[1]!=t[1]) continue;
if(i%2==0&&s[1]==t[1]) continue;
int now=0;
for(int j=min(1,i),k=min(1-(i-1),1);j<=c1||k<=c2;++j,++k){
int x=(j<1)?0:(j>c1?n:a[j]);
int y=(k<1)?0:(k>c2?n:b[k]);
now+=abs(x-y);
}
ans=min(ans,now);
}
printf("%d\n",ans);
return 0;
}
F - Permutation and Minimum
考慮将原問題看成将 \(1\sim 2n\) 的排列分成 \(n\) 對數。兩個數已經确定的數對可以忽略，剩下還有确定了一個數以及一個都沒有确定的數對。考慮 \(dp\)，從小到大填入每一個數，設 \(dp_{i,j,k}\) 表示填了 \(\le i\) 的數，目前已确定最小值的有 \(j\) 對（設為 \(A\) 類數對）， 已填一個數但不确定大小的有 \(k\) 個（設為 \(B\) 類數對）。
轉移需要注意的是，如果将一個數放進 \(B\) 類數對，那我們無法确定是與哪一個數進行的比對，可以将操作延後至周遊到與它配對的數時進行。周遊到某個被欽定了位置的數 \(x\) 時，如果還有 \(suf\) 個欽定數沒有配對，那麼就意味着有 \(suf-k\) 個前面的數與這些欽定的數進行比對，是以可以讨論 \(x\) 是否與前面比對，有轉移：
\[dp_{i+1,j,k}\gets (suf-k)dp_{i,j,k}\\
dp_{i+1,j+1,k-1}\gets dp_{i,j,k}
\]
#include<bits/stdc++.h>
using namespace std;
const int N=610,mod=1e9+7;
int dp[N][310][310];//考慮到第i個數字，目前已确定最小值的有j個， 已填一個數但未确定大小的有j個
int n,a[N],d[N],tot,c1,c2,pd[N],vis[N],inv[N];
inline int dec(int x,int y){return (x-y<0)?x-y+mod:x-y;}
inline void inc(int &x,int y){x=(x+y>=mod)?x+y-mod:x+y;}
int main(){
scanf("%d",&n);n<<=1;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
if(a[i]>0) pd[a[i]]=1;
}
inv[0]=1;
for(int i=1;i<=n;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=n;i+=2){
if(a[i]>0&&a[i+1]>0){vis[a[i]]=vis[a[i+1]]=1;continue;}
else if(a[i]>0||a[i+1]>0) ++c2;
else ++c1;
}
for(int i=1;i<=n;++i) if(!vis[i]) d[++tot]=i;
dp[0][0][c2]=1;
int suf=c2;
for(int i=0;i<tot;++i){
for(int j=0;j<=c1+c2;++j)
for(int k=0,x;k<=c2;++k){
if(!(x=dp[i][j][k])) continue;
if(pd[d[i+1]]){
if(k!=suf) inc(dp[i+1][j][k],1ll*(suf-k)*x%mod);
if(k) inc(dp[i+1][j+1][k-1],x);
}
else{
if(j) inc(dp[i+1][j-1][k],x);
int tmp=(i-j)/2+j+k;
if(c1+c2-tmp)
inc(dp[i+1][j+1][k],x);
if(k) inc(dp[i+1][j][k-1],x);
}
}
if(pd[d[i+1]]) suf--;
}
int ans=dp[tot][0][0];
for(int i=1;i<=c1;++i) ans=1ll*ans*i%mod;
printf("%d\n",ans);
return 0;
}