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;
}
总结
- 还是要注意时间的把控，再分析问题时还不够深入
- 没有必要的循环一定不要加，如T3中char直接可以异或就不用转化成int
- 数位dp在能用循环写就不要用记忆化
- 对于网络流的题目还不够敏感，看到数据范围较小的图论问题就可以考虑网络流