校内模拟-2024-4-28
前言
第一次 AK 校内比赛 qwq。
D 的 $\text{trick}$ 见过类似的才侥幸做出来。
简单题但是毒瘤题。
【题意】
给定矩阵，找值相等的八连通块，满足其八联通方向没有值更大/更小。
分别求这两种连通块的个数。要做到 $O(n^2)$。
【解析】
搜索即可。开两个标记，表示是山峰/山谷。
记得特判全相等的情况。
但不知道为什么，$\text{dfs}$ 在 LOJ 上会 MLE。
所以改成了 $\text{bfs}$ 卡空间，把所有能开在外面的开外面，卡了 $10$ 发才过。
幸亏没有罚时。
【代码】
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define F(i,x,y) for(int i=(x);i<=(y);++i)
#define Fo(i,x,y) for(int i=(x);i>=(y);--i)
const int N=1001;
int n,flag,tmp;
bitset<N> vis[N];
int a[N][N],ans1,ans2;
bool f1,f2;
struct node{int x,y;};
queue<node> q;
void bfs(int x,int y){
f1=1,f2=1;
node u;
int tx,ty;
q.push({x,y});
vis[x][y]=1;
while(!q.empty()){
u=q.front();
q.pop();
F(i,-1,1){
F(j,-1,1){
if(i==0&&j==0) continue;
tx=u.x+i,ty=u.y+j;
if(tx<1||tx>n||ty<1||ty>n) continue;
if(a[tx][ty]>a[u.x][u.y]) f1=0;
else if(a[tx][ty]<a[u.x][u.y]) f2=0;
else if(!vis[tx][ty]){
vis[tx][ty]=1;
q.push({tx,ty});
}
}
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
int i,j;
for(i=1;i<=n;++i){
for(j=1;j<=n;++j){
cin>>a[i][j];
if(i==1&&j==1) tmp=a[i][j];
else if(a[i][j]!=tmp) flag=1;
}
}
if(!flag){
cout<<1<<" "<<1<<endl;
return 0;
}
for(i=1;i<=n;++i){
for(j=1;j<=n;++j){
if(vis[i][j]) continue;
bfs(i,j);
ans1+=f1,ans2+=f2;
}
}
cout<<ans1<<" "<<ans2<<endl;
return 0;
}
|
【题意】
给定一个长度为 $n\le 1000$ 的字符串，再给定一个长度相等的目标串和非负整数 $k\le 10^5$，请问是否可以使用正好 $k$ 次操作，将原串变成目标串。
每一次操作选择一个位置 $p\in[1,n)$，然后将字符串变成 $[p+1,n]+[1,p]$。其中 $+$ 表示连接。
求操作方案数，取模。两个方案不同当且仅当至少有一步 $p$ 的选择不同。
【解析】
猜一个非常重要的结论：如果一次操作不行的话，那一定不行。
感性理解一下，字符之间的相对位置大体不变，一次不行的话多次也不行。
推广一下，也就是说做任意多次操作以后只需要做 $1$ 次操作就可以变成想要的样子。
所以我们可以先暴力求出一次操作能满足条件的方案数，记为 $\text{cnt}$。
则考虑 DP，设 $f_i$ 表示第 $i$ 步变成目标串的方案数，$g_i$ 表示第 $i$ 步没变成目标串的方案数。
推出转移方程 $f_i=cnt\times g_{i-1}+(cnt-1)\times f_{i-1}$。表示有 $\text{cnt}$ 种方式从上一个的任意非目标串状态变成目标串状态，$\text{cnt-1}$ 种方式从上一个的目标串再操作一次还是目标串。
类似地，$g_i=(n-cnt)\times f_{i-1}+(n-cnt-1)\times g_{i-1}$。
答案是 $f_k$，初始状态就是看看原串和目标串是否一样，是则 $f_0=1$，否则 $g_0=1$。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define F(i,x,y) for(int i=(x);i<=(y);++i)
#define Fo(i,x,y) for(int i=(x);i>=(y);--i)
const int N=1e5+10,mod=1e9+7;
string a,b,s,t;
int n,k;
ll f[N][2],cnt;
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>s>>t>>k;
n=s.size();
if(k==0){
if(s==t) cout<<1<<endl;
else cout<<0<<endl;
return 0;
}
if(s==t){
cnt=1;
f[0][0]=1;
}
else f[0][1]=1;
F(i,1,n-1){
a=s.substr(0,i);
b=s.substr(i,n-i);
a=b+a;
if(a==t) cnt++;
}
F(i,1,k){
f[i][0]=(cnt*f[i-1][1]+(cnt-1)*f[i-1][0])%mod;
f[i][1]=((n-cnt)*f[i-1][0]+(n-cnt-1)*f[i-1][1])%mod;
}
cout<<f[k][0]<<endl;
return 0;
}
|
【题意】
从 $[0,m]$ 中选择一个整数，使其经过 $n$ 次操作后的结果最大，求此最大值。
对于每一次操作，让原数执行与给定数按位与、按位或、按位异或中的一种（操作类型给定）。
【解析】
既然是位运算，考虑最后高位是 $1$ 则整体更大，启示我们从高往低考虑。贪心地想，这一位一开始要么是 $0$，要么是 $1$，那么我们分别枚举即可。
可以使用两个变量分别是 $0$ 和 $-1$，代表二进制的全 $0$ 和全 $1$，进行操作以后从高位向低位枚举，如果一开始是 $0$ 这一位是 $1$，那直接加答案，否则一开始是 $1$ 这一位是 $1$，加答案，同时判断没有超过 $m$ 的限制。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define F(i,x,y) for(int i=(x);i<=(y);++i)
#define Fo(i,x,y) for(int i=(x);i>=(y);--i)
const int N=1e5+10;
int n,m,t;
char op[5];
int ans,tmp1,tmp2;
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
tmp1=0,tmp2=-1;
F(i,1,n){
cin>>op>>t;
if(op[0]=='A') tmp1&=t,tmp2&=t;
if(op[0]=='O') tmp1|=t,tmp2|=t;
if(op[0]=='X') tmp1^=t,tmp2^=t;
}
Fo(i,29,0){
if((tmp1>>i)&1){
ans+=(1<<i);
continue;
}
if((tmp2>>i)&1&&m>=(1<<i)){
ans+=(1<<i);
m-=(1<<i);
}
}
cout<<ans<<endl;
return 0;
}
|
【题意】
给定一个 $01$ 方阵，操作可以交换任意行列，问最终是否可以让左上到右下对角线全为 $1$。
【解析】
经典建模。既然要把对角线全变成 $1$，那就是每个行上对应每个列都匹配了，由此想到二分图最大匹配。
考虑把行当作左部点，列当作右部点，然后原矩阵里的 $1$ 行向列连边，源点连行，列连汇点。
正确性在于，交换行列就是匹配过程，总边数不改变，最大流为 $n$ 时满流有解。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define F(i,x,y) for(int i=(x);i<=(y);++i)
#define Fo(i,x,y) for(int i=(x);i>=(y);--i)
const int N=1e5+10,INF=0x3f3f3f3f;
int n,s,t;
struct edge{
int v,next,w;
}e[N<<1];
int head[N],tot;
void add(int u,int v,int w){
e[++tot]={v,head[u],w};
head[u]=tot;
e[++tot]={u,head[v],0};
head[v]=tot;
}
int dis[N],now[N];
bool bfs(){
queue<int> q;
memset(dis,0,sizeof(dis));
dis[s]=1,now[s]=head[s],q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
if(!dis[v]&&e[i].w){
dis[v]=dis[u]+1;
now[v]=head[v];
q.push(v);
if(v==t) return 1;
}
}
}
return 0;
}
ll dfs(int u,int sum){
if(u==t) return sum;
ll res=0,tmp;
for(int &i=now[u];i&∑i=e[i].next){
int v=e[i].v,w=e[i].w;
if((dis[v]==dis[u]+1)&&e[i].w){
tmp=dfs(v,min(sum,w));
if(!tmp) dis[v]=0;
e[i].w-=tmp,e[i^1].w+=tmp;
sum-=tmp,res+=tmp;
}
}
return res;
}
ll ans;
void init(){
tot=1;
ans=0;
memset(head,0,sizeof(head));
memset(now,0,sizeof(now));
}
void solve(){
init();
cin>>n;
s=n*2+1,t=s+1;
F(i,1,n){
add(s,i,1);
add(i+n,t,1);
int x;
F(j,1,n){
cin>>x;
if(x==1) add(i,j+n,1);
}
}
while(bfs()) ans+=dfs(s,INF);
if(ans>=n) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--) solve();
return 0;
}
|
