当前位置: 首页 > news >正文

卖汽车怎么做网站南宁网站seo优化公司

卖汽车怎么做网站,南宁网站seo优化公司,wordpress apache内存,嵌入式开发要学哪些D - Gomamayo Sequence 状态DP 题意:给定一个长度为n的01字符串,使得只存在一组s[i]s[i1] 其余都是不同的,若使0改变为1 会花相应的费用 a[i] 求最小值 思路:数据为2e5数据太大,贪心不可以想到dp--状态dp 构造01串…

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;}

http://www.dinnco.com/news/50304.html

相关文章:

  • 广东网站备案要多久建网站用什么软件
  • 广东网站设计招工.淘宝直通车推广怎么收费
  • 手工活300元一天双桥seo排名优化培训
  • 政务服务网站建设资金快速排名优化推广排名
  • 网站怎么做gps定位2345网址导航浏览器下载
  • 专业购物网站baidu百度首页官网
  • 网站建设可行性研究报告 baidu百度seo查询系统
  • 安阳市哪里做网站建设关键词什么意思
  • 东圃做网站的公司关键词首页排名优化
  • 阿里云服务器上传网站网络优化工程师工作内容
  • 制作简历的免费模板网站培训机构优化
  • 慈溪网站建设报价镇江网站
  • 织梦网站排版能调整吗北京seo网站推广
  • 任丘市做网站价格百度推广培训班
  • 中小型网站建设百度热搜榜排名昨日
  • 国防教育网站建设说明书一键制作网站
  • 郑州做网站推广电话网络推广接单平台
  • 做趣味图形的网站郑州seo优化哪家好
  • 怎么建设自己网站会计培训班哪个机构比较好
  • 网站提交链接入口培训班有哪些
  • 申请网站空间常见的网络营销手段
  • 做网站的哪家好学seo如何入门
  • 银行的网站做的真垃圾新网域名注册
  • 卖环保设备做哪个网站好免费网站模板网
  • 网站优化软件有哪些网站优化快速排名软件
  • 政府网站建设人员的组织雅虎搜索引擎首页
  • wordpress运行机制深圳关键词优化平台
  • 网站权重的重要性长沙优化网站推广
  • 拖拽式建站平台医院线上预约
  • wordpress归档页面泉州seo排名扣费