A. Morning Sandwich
题意:有面包片和火腿和芝士 问最多能组成几层三明治
题解:直接输出单考虑面包片和单考虑火腿和芝士的数量 取min
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod = 1e9+7; const ll inf = 0x3f3f3f3f; #define int ll void solve(){ int a,b,c;cin>>a>>b>>c; cout<<min({(a-1)*2+1,(b+c)*2+1})<<"\n"; } signed main(){ int t;cin>>t; while(t--) solve(); }
B. Monsters
题意:有很多怪物,每次砍m血,优先血多的,血一样多就优先序号小的,问死亡顺序
题解:想象一下过程,每个怪物最后都会被砍到1-m血,然后砍一刀就死了 就对血量取模,特判整除,然后sort排序即可
用优先队列模拟会tle
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 1e6+7; const ll mod = 1e9+7; const ll inf = 0x3f3f3f3f; #define int ll struct node{ int k,id; }N[MAXN]; bool bj(node a,node b){ if(a.k!=b.k) return a.k>b.k; else return a.id<b.id; } void solve(){ int n,m;cin>>n>>m; for(int i=1;i<=n;i++){ cin>>N[i].k; if(N[i].k%m!=0) N[i].k%=m; else N[i].k=m; N[i].id=i; } sort(N+1,N+1+n,bj); for(int i=1;i<=n;i++){ cout<<N[i].id<<" "; } cout<<"\n"; } signed main(){ close; int t;cin>>t; while(t--) solve(); }
C. Binary String Copying
题意:给一个长度为n的01字符串,m个操作,给l,r,对字符串lr进行排序,问最后的结果有多少不同的字符串
题解:对于一次排序 如果排序为0010111 很明显,只有(3,4)的区间的被排序了的,其他区间都是无效,那么l=1,r=6和l=2,r=5其实是一样的。
那么我们考虑记录所有的有效排序区间,即会变化的区间,有效区间的左端点就是l开始从左往右边数的第一个1 右端点就是r开始从右往左数的第一个0。
如何快速查找这个0和1,我记录了所有0和1的pos 对这些位置进行lower_bound即可,1是要找大于等于l的第一个数,0是找小于等于r的第一个数 这个实现应该比较方便。
如果找到的pos1和pos0不满足pos1<pos0 就往set里面塞一个(-1,-1),否则塞两个pos
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod = 1e9+7; const ll inf = 0x3f3f3f3f; //查找左往右第一个0 和右往左第一个1 vector<int> v[2]; set<pair<int,int> > sz; void solve(){ int n,m;cin>>n>>m; sz.clear(); v[0].clear(); v[1].clear(); string s;cin>>s; s=" "+s; for(int i=1;i<=n;i++){ if(s[i]=='1') v[1].push_back(i); else v[0].push_back(i*-1); } v[0].push_back(0); v[1].push_back(inf); sort(v[0].begin(),v[0].end()); sort(v[1].begin(),v[1].end()); for(int i=1;i<=m;i++){ int l,r;cin>>l>>r; int pos1=*(lower_bound(v[1].begin(),v[1].end(),l)); int pos0=*(lower_bound(v[0].begin(),v[0].end(),r*-1)); pos0*=-1; if(pos1>=pos0||pos1>=r||pos0<=l){ sz.insert({-1,-1}); } else sz.insert({pos1,pos0}); } cout<<sz.size()<<'\n'; } signed main(){ int t;cin>>t; while(t--) solve(); }
D. Array Painting
题意:可以消耗1个cost把染色,已经染色的块如果值>0 可以-1,让周围的一个未染色块染色
题解:考虑对这些数字分块,记录成只有0的块和没有0的块,对于每个没有0的块,染色费用为1,如果里面至少有1个2,就可以对左右两边的全0块都染一个,否则选一个染。
我们枚举所有块,遇到全0块就看看左右的非0块能不能提供贡献,注意一下别算多了
wa23:考虑下0块的消耗是不是变成负的了
wa28:考虑下是不是多占用了一个1块 比如 4 1 0 1 0 这组数据 我当时出的3
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod = 1e9+7; const ll inf = 0x3f3f3f3f; //查找左往右第一个0 和右往左第一个1 vector<int> v[2]; set<pair<int,int> > sz; void solve(){ int n,m;cin>>n>>m; sz.clear(); v[0].clear(); v[1].clear(); string s;cin>>s; s=" "+s; for(int i=1;i<=n;i++){ if(s[i]=='1') v[1].push_back(i); else v[0].push_back(i*-1); } v[0].push_back(0); v[1].push_back(inf); sort(v[0].begin(),v[0].end()); sort(v[1].begin(),v[1].end()); for(int i=1;i<=m;i++){ int l,r;cin>>l>>r; int pos1=*(lower_bound(v[1].begin(),v[1].end(),l)); int pos0=*(lower_bound(v[0].begin(),v[0].end(),r*-1)); pos0*=-1; if(pos1>=pos0||pos1>=r||pos0<=l){ sz.insert({-1,-1}); } else sz.insert({pos1,pos0}); } cout<<sz.size()<<'\n'; } signed main(){ int t;cin>>t; while(t--) solve(); }
这场A-D都是签到 有空补补后面的再补全(还有好多帐欠着呢
- cf-Educational Educational Codeforces Round Ratedcf-educational educational codeforces round educational codeforces round rated round codeforces rated based educational codeforces round 151 construction educational codeforces round educational codeforces round 147 educational codeforces round 158 educational codeforces monsters round educational codeforces contest round cf-educational