AtCoder Beginner Contest 419(ABCDEF)
前言
这次的D感觉还好，但E一涉及到dp就跟不上了……
一、A - AtCoder Language
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;void solve()
{string s;cin>>s;if(s=="red"){cout<<"SSS";}else if(s=="blue"){cout<<"FFF";}else if(s=="green"){cout<<"MMM";}else{cout<<"Unknown";}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve(); }return 0;
}这个题没啥好说的，特判就行了。
二、B - Get Min
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;void solve()
{int q;cin>>q;multiset<int>s;int type;while(q--){cin>>type;if(type==1){int x;cin>>x;s.insert(x);}else{cout<<*s.begin()<<endl;s.erase(s.begin());}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve(); }return 0;
}这个题直接模拟着做就行了。方法就是开一个multiset，然后要求插入就插入，要求输出就输出并删除即可。
三、C - King's Summit
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;void solve()
{int n;cin>>n;ll maxx=0,minx=1e9+5;ll maxy=0,miny=1e9+5;for(int i=0;i<n;i++){ll x,y;cin>>x>>y;maxx=max(maxx,x);minx=min(minx,x);maxy=max(maxy,y);miny=min(miny,y);}ll mid=(maxx+minx)/2;ll mx=max(maxx-mid,mid-minx);mid=(maxy+miny)/2;ll my=max(maxy-mid,mid-miny);cout<<max(mx,my);
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve(); }return 0;
}这题就需要贪心一下了。
因为要求所有人走到同一个格子的最小时间，所以肯定就是让所有人都往中间走。那么依赖的就是最上方，最下方，最左侧和最右侧的人的位置，所以可以考虑每次读入时把x的最大最小值和y的最大最小值抓出来。之后，那么最终所有人汇合的点就是最大最小值的平均值，即中点坐标。又因为有可能中间距离是奇数，所以最终走的最远距离就是最大最小值分别到中点的距离的最大值，最后输出横坐标上和纵坐标上耗时的最大值即可。
四、D - Substr Swap
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;void solve()
{int n,m;cin>>n>>m;string s,t;cin>>s>>t;vector<int>cnts(n+1);for(int i=0,x,y;i<m;i++){cin>>x>>y;x--,y--;cnts[x]++;cnts[y+1]--;}for(int i=1;i<n;i++){cnts[i]+=cnts[i-1];}for(int i=0;i<n;i++){if(cnts[i]%2==0){cout<<s[i];}else{cout<<t[i];}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve(); }return 0;
}这次的D倒是挺简单的。
观察可以发现，假如一个区间上翻转的操作数为偶数，最后会转回来，就相当于没反转。所以只需要看一下每个位置经历了几次翻转即可，如果是奇数那就输出t串，偶数就输出s串即可。那么这就是一个差分题了，只需要读入每个区间求一下一维差分，再求一遍前缀和输出即可。
五、E - Subarray Sum Divisibility
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;void solve()
{int n,m,l;cin>>n>>m>>l;vector<int>a(n+1);for(int i=1;i<=n;i++){cin>>a[i];}//若sum1=a[1]+a[2]+……+a[l]模m等于0//在下一次窗口滑动时，窗口内的累加和sum2=sum1-a[1]+a[l+1]//如果要保证sum2模m等于0//那么必须保证(a[1]-a[l+1])%m==0//所以就必须有a[1]和a[l+1]模m同余//所以就可以推广出a[i]和a[l+i]模m同余//只需要先确定好第一个窗口//之后a[l+1]~a[n]的所有数都唯一确定//所以a[i],a[i+l]……a[i+kl]均模m同余//定义g[i][j]为将a[i]调为模m等于j时整体的最小操作数//因为将a[i]改成模m等于j的最小操作数为(j-a[i]+m)%m//所以g[i][j]=sum[k>=0]( (j-a[i+kl]+m)%m )//定义dp[i][j]为当前来到a[i]，使得a[1]+……+a[i]模m等于j的最小操作数//所以dp[i][j]=min[k=0~m-1](g[i][k]+dp[i-1][(j-k+m)%m])//含义为先让a[i]变为模m等于k，再让前i-1个数变为和a[i]能凑出模m等于jvector<vector<int>>g(l+1,vector<int>(m));for(int i=1;i<=l;i++){for(int j=0;j<m;j++){for(int p=i;p<=n;p+=l){//将a[p]变为j的代价g[i][j]+=(j-a[p]+m)%m;}}}vector<vector<int>>dp(l+1,vector<int>(m));dp[0][0]=0;for(int j=1;j<m;j++){dp[0][j]=1e9;}for(int i=1;i<=l;i++){for(int j=0;j<m;j++){dp[i][j]=1e9;for(int k=0;k<m;k++){dp[i][j]=min(dp[i][j],g[i][k]+dp[i-1][(j-k+m)%m]);}}}cout<<dp[l][0]<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve(); }return 0;
}这题是真的难……
首先，若第一个窗口中a[1]+a[2]+……+a[l]模上m等于0，那么在窗口往后滑时，窗口内累加和需要加上a[l+1]再减去a[1]。而如果要现在的累加和也模m等于0，那么就有a[1]-a[l+1]模m等于0，所以可以得出a[1]和a[l+1]模m同余。所以可以总结出，a[i]和a[l+i]模m同余。所以，只需要确定了第一个窗口内的数，之后的数必然唯一确定，所以可以推出a[i]和后续所有的a[i+kl]的数均同余。所以可以定义g[i][j]为将第一个窗口内的a[i]，连带着后续所有要求和a[i]同余的数，一起调整为模m余j的最小操作数。又因为观察可以得到，将a[i]调整到模m余j的最小操作数就是(j-a[i]+m)%m，所以g[i][j]就是从a[i]开始每次往后跳l个位置，所有数的最小操作数的累加和。
预处理好g数组后，就可以定义dp[i][j]为当前来到a[i]，使得从头到a[i]所有数的累加和模m等于j的最小操作数。所以dp[i][j]就等于k从0到m-1，g[i][k]+dp[i-1][(j-k+m)%m]，含义为先让a[i]及后面相关的数均模m等于k，再将前i-1个数调整为和k能凑出余数为j的最小操作数，再从所有情况中取最小值即可。那么初始化时dp[0][0]就等于0，含义为没有数时累加和为0模m等于0，不需要操作。再把第一行剩下的数都初始化为无穷大，表示不可能达成。之后因为每个格子都依赖自己上一行的某个位置的格子，所以就是从上往下从左往右填格子。最后输出dp[l][0]，表示第一个窗口的数都确定了，模m等于0的最小操作数。
六、F - All Included
这玩意儿居然真会考……
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;const int MOD=998244353;const int MAXN=8*10+5;//总字符数//动态规划
//定义dp[i][u][s]为
//当前来到字符串的第i位，在AC自动机的节点u，已包含的串的集合s的情况数
//第一维大小为2 -> 滚动更新
vector<vector<vector<int>>>dp(2,vector<vector<int>>(MAXN,vector<int>((1<<9))));//AC自动机
vector<vector<int>>tree(MAXN,vector<int>(26));
vector<int>fail(MAXN);
int cnt=0;//id[u]:节点u在fail树上的祖先有哪些是终止节点 -> 状态压缩
vector<int>id(MAXN);//第i号目标串建前缀树
void insert(int i,string s)
{//当前所在的节点int u=0;for(int j=0;j<s.length();j++){int c=s[j]-'a';//没路if(tree[u][c]==0){tree[u][c]=++cnt;}u=tree[u][c];}id[u]|=(1<<i);
}//设置fail和直通表 -> bfs
void setFail()
{queue<int>q;//0号节点下一层入队for(int i=0;i<=25;i++){//有路if(tree[0][i]>0){q.push(tree[0][i]);}}//bfswhile(!q.empty()){int u=q.front();q.pop();id[u]|=id[fail[u]];for(int i=0;i<=25;i++){if(tree[u][i]==0)//没路 -> 改直通表{tree[u][i]=tree[fail[u]][i];}else//有路 -> 设置fail{fail[tree[u][i]]=tree[fail[u]][i];q.push(tree[u][i]);}}}
}void solve()
{int n,l;cin>>n>>l;vector<string>a(n+1);for(int i=1;i<=n;i++){cin>>a[i];insert(i-1,a[i]);}setFail();int now=0;//初始在根节点，没有任何串dp[now][0][0]=1;for(int i=1;i<=l;i++){//上一层清空for(int u=0;u<=cnt;u++){for(int s=0;s<(1<<n);s++){dp[now^1][u][s]=0;}}for(int u=0;u<=cnt;u++){for(int status=0;status<(1<<n);status++){//到不了if(dp[now][u][status]==0){continue;}//枚举每种字符for(int c=0;c<=25;c++){//AC自动机上要去的节点int v=tree[u][c];dp[now^1][v][status|id[v]]=(dp[now^1][v][status|id[v]]+dp[now][u][status])%MOD;}}}now^=1;}int ans=0;for(int u=0;u<=cnt;u++){//全包含的情况数ans=(ans+dp[now][u][(1<<n)-1])%MOD;}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve(); }return 0;
}因为涉及到多个字符串的子串匹配，那么就是AC自动机对口的问题了。
在构建AC自动机时，需要定义id[u]为AC自动机上节点u匹配了哪些字符串。因为字符串的数量不大，所以考虑使用状态压缩记录。那么在构建AC自动机时，最后的节点u就是一个字符串的终止节点，所以把当前字符串的位修改为1，表示匹配了该字符串。之后在setFail设置fail指针时，每次都将当前节点u的fail指针指向的节点的id或进当前节点的id。举个例子，假如字符串有“abc”和“bc”，那么因为在遍历完“abc”后两个字符串都匹配到了，就把“bc”串终止节点的id或进“abc”串的终止节点。
之后就是一个dp了，定义dp[i][u][s]为当前来到枚举的字符串的第i位，位于AC自动机的节点u，所有字符串的匹配状态s，所以每次都枚举所有字符数，求出在AC自动机上要去的节点v，所以当前的匹配状态s就是之前的s或上节点v的id值，dp值就是加上上一步的种类数即可。又因为每个位置的dp值只依赖上一层的dp值，所以可以考虑进行空间压缩。所以初始化就是dp[now][0][0]为1，表示初始在根节点，一个匹配的都没有，此时就有空串一种情况。之后就是枚举每个位置，再枚举所有AC自动机上的节点和所有可能的状态。注意如果dp值为0，说明到不了这种状态，直接continue即可。否则就枚举每种字符填格子即可，注意每次需要把上一层的dp值清空。最后，只需要遍历最后一层的所有节点，统计全匹配的种类数之和即可。
总结
菜就多练吧，加油！！