综合网站开发实训总结,小江网站建设,设计软件coreldraw,网站存在风险什么意思D - Gomamayo Sequence
状态DP
题意#xff1a;给定一个长度为n的01字符串#xff0c;使得只存在一组s[i]s[i1] 其余都是不同的#xff0c;若使0改变为1 会花相应的费用 a[i] 求最小值
思路#xff1a;数据为2e5数据太大#xff0c;贪心不可以想到dp--状态dp 构造01串…D - Gomamayo Sequence
状态DP
题意给定一个长度为n的01字符串使得只存在一组s[i]s[i1] 其余都是不同的若使0改变为1 会花相应的费用 a[i] 求最小值
思路数据为2e5数据太大贪心不可以想到dp--状态dp 构造01串 花费最小 --难点在于 要考虑两个状态dp去存储 若s[i]s[i1] 则s[1...i]之间都是不同的 s[i1..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的花费
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N2e510;
const ll INF1e18;
ll dp[2][N],rdp[2][N];
ll a[N];
int main()
{int n;cinn;string s;cins;s0s;for(int i1;in;i) cina[i];for(int i1;is.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 is.size()-1;i1;i--){if(s[i]0){rdp[0][i]rdp[1][i1];rdp[1][i]rdp[0][i1]a[i];}else{rdp[1][i]rdp[0][i1];rdp[0][i]rdp[1][i1]a[i];}}ll ansINF;for(int i1;in;i){ansmin(ans,dp[0][i]rdp[0][i1]);ansmin(ans,dp[1][i]rdp[1][i1]);}coutansendl;return 0;
}E - Paint
模拟
H行W列一开始都是颜色 0你需要进行M次操作
每次操作
若Ti1把Ai行全部改成 Xi 颜色
若Ti2把Ai列全部改成 Xi 颜色
操作全部执行完了之后按升序输出所有颜色有几个。
思路:从后往前遍历
考虑到重复操作前面会后面的覆盖所以逆序遍历操作如果对重复行列操作就不执行。
并且每刷一行之后如果下一次刷列显然就会有一个数不能再刷了。
#includeiostream
#includealgorithm
#includemap
using namespace std;
typedef long long ll;
const int N2e510;
mapint,llmp;
bool st1[N],st2[N];
int h[N],l[N];
int a[N],b[N],c[N];
int main()
{int h,w,m;cinhwm;ll res(ll)h*w;for(int i1;im;i) cina[i]b[i]c[i];//从后往前遍历 若已经遍历过的行和列便不在遍历for(int im;i1;i--){if(a[i]1){//若行没有遍历过if(!st1[b[i]]){if(w0) { //相当于加上列的个数减去已经遍历过的行的个数mp[c[i]]w;h--;st1[b[i]]1; } }}else{//若列没有遍历过if(!st2[b[i]]){if(h0){//相当于加上行的个数减去已经遍历过的列的个数mp[c[i]]h;w--;st2[b[i]]1;}}}}for(auto it:mp){if(it.second0) res-it.second;}if(res0) mp[0]res;coutmp.size()endl;for(auto it:mp){coutit.first it.secondendl;}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)的子序列(可以是不连续的)。
#includeiostream
#includealgorithm
#includevector
using namespace std;
typedef long long ll;
const int N2e510;
vectorllv[N];//存每个字母在s中对应的下标
ll cnt[30][N];//二维前缀和 记录 当前cnt[i][j] 记录当前长度为j时的i的个数
string s,t;
ll n;
//判断的标准是个数
bool check(ll mid)
{ll lens.size()-1;ll num0;ll idlen;//记录每一个字母遍历 最终停留的位置 开始初始化为len 方便最开始相减为0for(int i1;it.size();i){ll xt[i]-a1;if(cnt[x][len]0) return false;//代表t中某个字符在s中从来没有出现过 不可能会有结果 返回falsell ansmid-(cnt[x][len]-cnt[x][id]);//这说明当前的字符串就够了 不需要在开一条if(ans0){//为了找此时满足条件应该到谁了ansmidcnt[x][id];if(ans0) idv[x][ans-1];//因为vector的下标是从0开始的continue;}ll num1ans/cnt[x][len];ll num2ans%cnt[x][len];numnum1;if(num2!0){num;//更新当前id的位置idv[x][num2-1];}//yyv[x].size()共有几个 v[x]中存的下标就是与之对应的第几个 最后一个就是与之相对应的下标yy-1else idv[x][v[x].size()-1];if(numn) return false;}return true;
}
int main()
{cinn;cinst;s s;t t;for(int i1;is.size();i){int nums[i]-a1;v[num].push_back(i);for(int j1;j26;j){cnt[j][i]cnt[j][i-1];if(jnum) cnt[j][i]cnt[j][i-1]1;}}ll l0,r1e18;//找最小值的最大化while(lr){ll mid(lr1)1;if(check(mid)) lmid;else rmid-1;}coutlendl;return 0;}
