ECfinal2021部分題解
把賽中卡住的題爭取補一下
題目鏈接：https://codeforces.com/gym/103861
H. Check Pattern is Good
網絡流
先把各自按奇偶反色，然后就變成要最多的全黑或全白
建立一個兩側各是n*n的二分圖
左邊表示將這個小矩形，右邊表示將這個小矩形染成黑色
相交的黑白小矩形之間連接inf
如果還有希望變白的小矩形，就讓s連到它，流量為1
如果還有希望變白的小矩形，就讓它連到t，流量為1
跑最小割就可以了
不難感受到這種建圖的正確性
這題代碼就先咕咕咕了
G.Check Pattern is Bad
做法其實很簡單
先把一定要填的？，即填某種字符會出現不合法的？，先填了
如果不存在，就隨便指定一個？為隨便一種字符，然后重復上述過程即可
最后跑出來有解就是有解，沒解就是沒解
目前沒有嚴格證明
當時再考場上可以大概感受到隨便填一下基本上也是有解的
當時因為想了一個假填法，所以已經寫完了bfs的過程，但后面卡在了填未知？的位置
賽中覺得是隨機個幾次，應該就能過
事實證明隨機一次就是一定有解的。
但當時手里卡著別的題，榜上過的人也不多，我也沒有嚴格證明就沒敢沖了。還是有點可惜
點擊查看代碼
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PI;
const int N=105;
char ss[N][N];
int n,m;
queue<PI> q;
int tx[4]={0,0,1,1};
int ty[4]={0,1,0,1};
bool check1 (int x,int y)
{
if (x<=0||x>=n||y<=0||y>=m) return false;
if (ss[x][y]=='B'&&ss[x+1][y]=='W'&&ss[x][y+1]=='W'&&ss[x+1][y+1]=='B') return false;
if (ss[x][y]=='W'&&ss[x+1][y]=='B'&&ss[x][y+1]=='B'&&ss[x+1][y+1]=='W') return false;
return true;
}
void check (int x,int y)
{
if (x<=0||x>=n||y<=0||y>=m) return ;
int xx=-1,yy=-1;
for (int u=0;u<4;u++)
{
int nx=x+tx[u],ny=y+ty[u];
if (ss[nx][ny]=='?')
{
if (xx!=-1) return ;
xx=nx;yy=ny;
}
}
if (xx==-1) return ;
ss[xx][yy]='B';
if (check1(x,y)==false) {ss[xx][yy]='W';q.push({xx,yy});return ;}
ss[xx][yy]='W';
if (check1(x,y)==false) {ss[xx][yy]='B';q.push({xx,yy});return ;}
ss[xx][yy]='?';
}
void solve ()
{
while (!q.empty())
{
int x=q.front().first,y=q.front().second;q.pop();
for (int u=-1;u<=1;u++)
for (int i=-1;i<=1;i++)
check(x+u,y+i);
}
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&n,&m);
for (int u=1;u<=n;u++) scanf("%s",ss[u]+1);
for (int u=1;u<n;u++)
for (int i=1;i<m;i++)
check(u,i);
solve();
for (int u=1;u<=n;u++)
for (int i=1;i<=m;i++)
if (ss[u][i]=='?')
{
ss[u][i]='B';
q.push({u,i});
solve();
}
bool tf=true;
for (int u=1;u<n;u++)
for (int i=1;i<m;i++)
if (check1(u,i)==false)
tf=false;
if (!tf) {printf("NO\n");continue;}
printf("YES\n");
for (int u=1;u<=n;u++)
{
for (int i=1;i<=m;i++) printf("%c",ss[u][i]);
printf("\n");
}
}
return 0;
}
C.String-dle Count：
其實，最后每一種字符只有兩種狀態：
1.出現了x，此時就已經知道該字符有多少個了
2.沒有出現x，那么相當于知道了這個字符至少有多少個記為\(L_I\)
同時，我們可以維護出每一個位置不可以填某個字符
考慮從左往右填，記錄一個狀態為填了前i個字符
由于有下界的限制，因此還需要每種字符已經出現了多少次
由于\(\sum L_i\le k\)，因此可以簡單地壓成一個二進制數
至于具體出現了多少次的字符，只需要保證再出現夠\(L_i\)個字符后不再轉移即可
目前的寫法是O(\(262^kk\))的，但其實可以寫成\(O(2^kk)\)
點擊查看代碼
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD=1e9+7;
const int N=10005;
const int K=20;
int add (int x,int y){x=x+y;return x>=MOD?x-MOD:x;}
int mul (int x,int y){return (LL)x*y%MOD;}
int dec (int x,int y){x=x-y;return x<0?x+MOD:x;}
int Pow (int x,int y)
{
int t=1;
while (y)
{
if (y&1) t=mul(t,x);
y>>=1;x=mul(x,x);
}
return t;
}
int L[30],R[30];
char s[K],t[K];
int n,m;
int cnt[30];
bool ban[K][30];
bool p[N];
void Init()
{
scanf("%s%s",s,t);
for (int u=0;u<26;u++) cnt[u]=0;
for (int u=0;u<m;u++) if (t[u]=='O')
{
int x=s[u]-'A';
cnt[x]++;
for (int i=0;i<26;i++) if (i!=x) ban[u][i]=1;
}
for (int u=0;u<m;u++) if (t[u]!='O')
{
int x=s[u]-'A';
ban[u][x]=1;
if (t[u]=='-') cnt[x]++;
else {p[x]=false;R[x]=min(R[x],cnt[x]);}
}
for (int u=0;u<26;u++) L[u]=max(L[u],cnt[u]);
}
int mask[30];
int bel[30];
int f[K][1<<K];
int inv[30];
int main()
{
inv[0]=1;for (int u=1;u<=20;u++) inv[u]=mul(inv[u-1],Pow(u,MOD-2));
memset(ban,false,sizeof(ban));
for (int u=0;u<26;u++) p[u]=true;
scanf("%d%d",&n,&m);
for (int u=0;u<26;u++) {L[u]=0;R[u]=m;}
while (n--) Init();
for (int u=0;u<26;u++) if (L[u]>R[u]) {printf("0\n");return 0;}
n=0;
for (int u=0;u<26;u++)
{
mask[u]=0;
for (int i=0;i<L[u];i++)
{
mask[u]|=(1<<n);bel[n]=u;n++;
if (n>m) {printf("0\n");return 0;}
}
}
f[0][0]=1;
for (int u=0;u<m;u++)
for (int i=0;i<(1<<n);i++)
{
if (!f[u][i]) continue;
for (int k=0;k<n;k++) if (!ban[u][bel[k]]&&!((i>>k)&1))
{
f[u+1][i|(1<<k)]=add(f[u+1][i|(1<<k)],f[u][i]);
}
for (int k=0;k<26;k++) if (p[k]&&(mask[k]==(mask[k]&i))&&!ban[u][k])
{
f[u+1][i]=add(f[u+1][i],f[u][i]);
}
}
int ans=f[m][(1<<n)-1];
for (int u=0;u<26;u++) ans=mul(ans,inv[L[u]]);
printf("%d\n",ans);
return 0;
}
浙公網安備 33010602011771號