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 方便最开始相减为0
for(int i=1;i<t.size();i++)
{
ll x=t[i]-'a'+1;
if(cnt[x][len]==0) return false;//代表t中某个字符在s中从来没有出现过 不可能会有结果 返回false
ll 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-1
else 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;
}
