20230429 模拟赛（jnxxhzz）

hewanying0622 / 2023-05-03 / 原文

T1.神奇零食柜

略，oj上交要加快读

T2.防御工事

数据范围：\(1 \le n,m \le 100\)
不难想到是网络流（虽然我没想到……）
这是一个挺基础的网络流
对于每个\(V\)，我们将它们连到一个超级源点上
在往它的四个方向分别建边
最后把所有的\(M\)连到一个汇点上
而在建边时注意其实\(E->E\)的边是没有用的，就可以不用建
最后在跑一个最大流求最小割即可

#include <bits/stdc++.h>
using namespace std;
#define int long long 

const int maxn=1e5+10,INF=0x3f3f3f3f;
const int fx[4]={0,1,0,-1};
const int fy[4]={-1,0,1,0};
int n,m,head[maxn],tot=-1,cur[maxn],lv[maxn],st,ed;
char mp[105][105];
struct edge{
  int v,val,nxt;
}e[maxn*2];

void add(int u,int v,int w){
  e[++tot]=(edge){v,w,head[u]};
  head[u]=tot;
  e[++tot]=(edge){u,0,head[v]};
  head[v]=tot;
}

bool bfs(){
  memset(lv,-1,sizeof(lv));
  cur[st]=head[st];
  lv[st]=0;
  queue<int> q;
  q.push(st);
  while(!q.empty()){
  	int nw=q.front();q.pop();
  	for(int i=head[nw];i!=-1;i=e[i].nxt){
  	  int v=e[i].v,val=e[i].val;
	  if(val>0&&lv[v]==-1){
	  	lv[v]=lv[nw]+1;
	  	cur[v]=head[v];
	  	q.push(v);
	  }	
	}
  }
  return lv[ed]!=-1;
}

int dfs(int nw,int flow){
  if(nw==ed) return flow;
  int res=flow;
  for(int i=cur[nw];i!=-1&&res;i=e[i].nxt){
  	cur[nw]=i;
  	int v=e[i].v,val=e[i].val;
  	if(val>0&&lv[v]==lv[nw]+1){
  	  int c=dfs(v,min(val,res));
	  e[i].val-=c;
	  e[i^1].val+=c;
	  res-=c;	
	}
  }
  return flow-res;
}

int dinic(){
  int ans=0;
  while(bfs())
  	ans+=dfs(st,INF);
  return ans;
}

signed main(){
  scanf("%lld%lld",&n,&m);
  memset(head,-1,sizeof(head));
  for(int i=1;i<=n;i++){
  	scanf("\n");
  	for(int j=1;j<=m;j++) scanf("%c",&mp[i][j]);
  }
  st=0,ed=n*m+1;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
      if(mp[i][j]=='V') add(st,(i-1)*m+j,INF);//注意行列式的计算啊
      if(mp[i][j]=='M') add((i-1)*m+j,ed,INF);
      for(int k=0;k<4;k++){
      	int x=i+fx[k],y=j+fy[k];
      	if(x>=1&&y>=1&&x<=n&&y<=m) add((i-1)*m+j,(x-1)*m+y,1);
	  }
	}
  printf("%lld\n",dinic());
  return 0;
}

T3.异或三角形

这道题和我之前在洛谷上做的那道同名题挺像的
感觉我的思路也挺像的
就顺着那道题想下去就写出来了
虽然挺冗长的，但终究还是A了
可是在oj上交就只有27分，RE，挺离谱的

源代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=2e5+10;
const ll mod=998244353;
int len=0,a[maxn];
char ch[maxn];
ll dp[maxn][8][8];

//当前枚举到第id位，a,b,c是否满足条件limit，X是否满足flag
//limit _,_,_ a,b,c是否达到上界
//flag _,_,_ aXc>aXb aXc>bXc aXc<aXb+bXc 
ll dfs(int id,int limit,int flag){
  //1.出口
  if(id==0) return flag==7;
  if(dp[id][limit][flag]!=-1) return dp[id][limit][flag];
  //2.能做的事情 
  ll res=0;
  int bounda=((limit>>2)&1)==1 ? a[id] : 1;
  int boundb=((limit>>1)&1)==1 ? a[id] : 1;
  int boundc=((limit)&1)==1 ? a[id] : 1;
  for(int ia=0;ia<=bounda;ia++)
    for(int ib=0;ib<=boundb;ib++)
	  for(int ic=0;ic<=boundc;ic++){
	  	int m=((ia==bounda)<<2)+((ib==boundb)<<1)+(ic==boundc);
	  	if(ib==ic&&ia!=ib){
	  	  res+=dfs(id-1,limit&m,flag|2);res%=mod;
	  	  continue;
		}
		if(ia==ib&&ic!=ia){
		  res+=dfs(id-1,limit&m,flag|4);res%=mod; 
		  continue;
		}
		if(ia==ib&&ia==ic){
		  res+=dfs(id-1,limit&m,flag);res%=mod;
		  continue;
		}
		if(((flag>>2)&1) && ((flag>>1)&1)){
		  res+=dfs(id-1,limit&m,flag|1);res%=mod;
		}
	  } 
  return dp[id][limit][flag]=res%mod;
} 

int main(){
  memset(dp,-1,sizeof(dp));
  scanf("%s",ch);
  len=strlen(ch);
  for(int i=len-1;i>=0;i--) a[len-i]=(int)(ch[i]-'0');
  printf("%lld\n",(dfs(len,7,0)*3)%mod);
  return 0;
}

题解中的做法比我想得更深入一些
我是钦定了大小关系，而题解中并没有
看起来也要简单得多
也就是说当\(a,b,c\)中每一个数字都与另外两个数有一位不同
这样就不用用递归实现了
时间复杂度就会变小

#include <bits/stdc++.h>
using namespace std;
#define ll long long 

const int maxn=2e5+10;
const int f[8]={0,1,2,4,4,2,1,0};
const ll mod=998244353;
int len;
char ch[maxn];
ll dp[maxn][8][8],ans=0; 

int main(){
  scanf("%s",ch);
  len=strlen(ch);
  dp[0][0][0]=1;
  for(int i=0;i<len;i++)
    for(int j=0;j<8;j++)//枚举limit 
      for(int k=0,F=ch[i]&1?7:j;k<8;k++)
        for(int l=0;l<8;l++)//枚举每一位真实的值
		  if((l&F)==l) //没有越界
		    (dp[i+1][j|(l^F)][k|f[l]]+=dp[i][j][k])%=mod; 
  for(int i=0;i<8;i++) (ans+=dp[len][i][7])%=mod;
  printf("%lld\n",ans%mod);
  return 0;
}