AtCoder Beginner Contest 346

D - Gomamayo Sequence 

状态DP

题意：给定一个长度为n的01字符串，使得只存在一组s[i]=s[i+1] 其余都是不同的，若使0改变为1 会花相应的费用 a[i] 求最小值

思路：数据为2e5数据太大，贪心不可以想到dp--状态dp 构造01串 花费最小 --难点在于 要考虑两个状态dp去存储 若s[i]==s[i+1] 则s[1...i]之间都是不同的 s[i+1..n]之间都是不同的 若只采用一个状态dp是无法存储后面的是什么样的--由此想到两个状态dp--一个存储前面是01或10串 一个从后面往前遍历去存储01或10串

dp[2][i] -- dp[0][i]表示前[1...i]之间都是不同的字符串 ，且当前i的字符为0的花费

             --  dp[1][i]表示前[1...i]之间都是不同的字符串，且当前i的字符为1的花费

rdp[2][i]-- rdp[0][i]表示前[i...n]之间都是不同的字符串 ，且当前i的字符为0的花费

              --  rdp[1][i]表示前[i...n]之间都是不同的字符串，且当前i的字符为1的花费

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const ll INF=1e18;
ll dp[2][N],rdp[2][N];
ll a[N];
int main()
{int n;cin>>n;string s;cin>>s;s='0'+s;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<s.size();i++){if(s[i]=='0'){dp[0][i]=dp[1][i-1];dp[1][i]=dp[0][i-1]+a[i];}else{dp[1][i]=dp[0][i-1];dp[0][i]=dp[1][i-1]+a[i];}}for(int i=s.size()-1;i>=1;i--){if(s[i]=='0'){rdp[0][i]=rdp[1][i+1];rdp[1][i]=rdp[0][i+1]+a[i];}else{rdp[1][i]=rdp[0][i+1];rdp[0][i]=rdp[1][i+1]+a[i];}}ll ans=INF;for(int i=1;i<n;i++){ans=min(ans,dp[0][i]+rdp[0][i+1]);ans=min(ans,dp[1][i]+rdp[1][i+1]);}cout<<ans<<endl;return 0;
}

E - Paint

模拟 

H行W列，一开始都是颜色 0，你需要进行M次操作

每次操作：

若Ti=1，把Ai行全部改成 Xi 颜色

若Ti=2，把Ai列全部改成 Xi 颜色

操作全部执行完了之后，按升序输出所有颜色有几个。

思路:从后往前遍历

考虑到重复操作，前面会后面的覆盖，所以逆序遍历操作，如果对重复行列操作就不执行。

并且每刷一行之后，如果下一次刷列，显然就会有一个数不能再刷了。

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int N=2e5+10;
map<int,ll>mp;
bool st1[N],st2[N];
int h[N],l[N];
int a[N],b[N],c[N];
int main()
{int h,w,m;cin>>h>>w>>m;ll res=(ll)h*w;for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>c[i];//从后往前遍历 若已经遍历过的行和列便不在遍历for(int i=m;i>=1;i--){if(a[i]==1){//若行没有遍历过if(!st1[b[i]]){if(w>0) {  //相当于加上列的个数减去已经遍历过的行的个数mp[c[i]]+=w;h--;st1[b[i]]=1;		}  }}else{//若列没有遍历过if(!st2[b[i]]){if(h>0){//相当于加上行的个数减去已经遍历过的列的个数mp[c[i]]+=h;w--;st2[b[i]]=1;}}}}for(auto it:mp){if(it.second>0) res-=it.second;}if(res>0) mp[0]+=res;cout<<mp.size()<<endl;for(auto it:mp){cout<<it.first<<" "<<it.second<<endl;}return 0;
}

F - SSttrriinngg in StringString

二分+找边界点

 题目大意​​​​​​​

给定两个字符串s,t,定义 f(s,n)表示将字符串 s重复拼接 n次。 g(t,k)表示将 t的每个字符重复 k次得到。

给定 n，问最大的 k，使得 g(t,k)是 f(s,n)的子序列(可以是不连续的)。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=2e5+10;
vector<ll>v[N];//存每个字母在s中对应的下标
ll cnt[30][N];//二维前缀和 记录 当前cnt[i][j] 记录当前长度为j时的i的个数
string s,t;
ll n;
//判断的标准是个数
bool check(ll mid)
{ll len=s.size()-1;ll num=0;ll id=len;//记录每一个字母遍历 最终停留的位置 开始初始化为len 方便最开始相减为0for(int i=1;i<t.size();i++){ll x=t[i]-'a'+1;if(cnt[x][len]==0) return false;//代表t中某个字符在s中从来没有出现过 不可能会有结果 返回falsell ans=mid-(cnt[x][len]-cnt[x][id]);//这说明当前的字符串就够了 不需要在开一条if(ans<0){//为了找此时满足条件应该到谁了ans=mid+cnt[x][id];if(ans>0) id=v[x][ans-1];//因为vector的下标是从0开始的continue;}ll num1=ans/cnt[x][len];ll num2=ans%cnt[x][len];num+=num1;if(num2!=0){num++;//更新当前id的位置id=v[x][num2-1];}//yy=v[x].size()共有几个 v[x]中存的下标就是与之对应的第几个 最后一个就是与之相对应的下标yy-1else id=v[x][v[x].size()-1];if(num>n) return false;}return true;
}
int main()
{cin>>n;cin>>s>>t;s=' '+s;t=' '+t;for(int i=1;i<s.size();i++){int num=s[i]-'a'+1;v[num].push_back(i);for(int j=1;j<=26;j++){cnt[j][i]=cnt[j][i-1];if(j==num) cnt[j][i]=cnt[j][i-1]+1;}}ll l=0,r=1e18;//找最小值的最大化while(l<r){ll mid=(l+r+1)>>1;if(check(mid)) l=mid;else r=mid-1;}cout<<l<<endl;return 0;}