Codeforces Round #631 div2 [萌新题解 只有三个题]
萌新的第一次cf ~打的巨烂无比 第二天来整理下
放一下原题和别人的题解!
原题目及作者答案
巨佬1的题解
巨佬2的题解
以下萌新的题解:
A. Dreamoon and Ranking Collection
题意:给出一个人参加n场比赛的所有排名,假设他再参加x场比赛可以取得v,v表示1~v的所有排名他都取得过,求最大的v。
话说读题读了好久qwqq
开一个桶排序 模拟就好啦!
#include<cstdio>
#include<cstring>
int n,x,t,rank,ans,book[505];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&x);
memset(book,0,sizeof(book));
for(int i = 1; i <= n; ++i){
scanf("%d",&rank);
book[rank]++;
}
for(ans = 1; ans <= 250; ++ans){
if(!book[ans]){
if(!x) break;
else x--;
}else continue;
}
printf("%d\n",ans - 1);
}
return 0;
}
P.S.第一遍写的时候抽风 book数组只开了105……导致错误。至少应该开到200+呀!
B. Dreamoon Likes Permutations
题意:给一个连续的序列,共n个数。求从中间某个位置划分,前面l1个数字是序列1-l1的排列;后面n - l1 = l2个数字是1-l2的排列。
P.S.做的时候想了好久……也没有发现哪里是错的。明明都过了QWQ
思路就是正向/反向的看,因为答案无非0 1 2. 用桶排序两次。
要注意一个细节! 如果是123123这种,正反向都会得到3,但是答案只算一次!
PP.S 答案的思路更简单~ 找最大的那个数字maxx,一定是两个划分:maxx与n - maxx
然后分别检查这两种即可!
#include<cstdio>
#include<vector>
#include<utility>
#include<cstring>
using namespace std;
const int maxn = 200005;
int book[maxn],t,n,maxx,box[maxn];
vector<pair<int, int> > ans;
bool check(int x){
for(int i = 1; i <= x; ++i) box[i] = 0;
for(int i = 1; i <= x; ++i) box[book[i]]++;
for(int i = 1; i <= x; ++i) if(!box[i]) return 0;
for(int i = 1; i <= n - x; ++i) box[i] = 0;
for(int i = x + 1; i <= n; ++i) box[book[i]]++;
for(int i = 1; i <= n - x; ++i) if(!box[i]) return 0;
return 1;
}
int main(){
scanf("%d",&t);
while(t--){
ans.clear();
scanf("%d",&n);
maxx = -1;
for(int i = 1; i <= n; ++i){
scanf("%d",&book[i]);
if(book[i] > maxx) maxx = book[i];
}
if(check(maxx)) ans.push_back(make_pair(maxx, n - maxx));
if(check(n - maxx) && maxx * 2 != n) ans.push_back(make_pair(n - maxx, maxx));
printf("%d\n",ans.size());
for(int i = 0; i < ans.size(); ++i)
printf("%d %d\n",ans[i].first, ans[i].second);
}
return 0;
}
O(n)的复杂度!
C. Dreamoon Likes Coloring这个题好秀的样子
题意:有m种颜色,涂一个长度为n的方块,每种颜色涂连续Li块(初始从1到n - li + 1选一个数,个数为li块),构造出使得所有方块都被涂色且每种颜色至少涂了一个方块的方法,方块上的颜色只记录最后一次涂的颜色(可以覆盖)。
感觉没思路好吧!
处理这两种情况后,就是可以的情况了。最后把后面的依次往后移就可以!
while(里要写>0),大于0必不可少哦!否则负数的bool值也是1.
#include<cstdio>
#define ll long long
const int maxn = 100005;
int n,m,x,book[maxn],ans[maxn];
ll sum;
void over(){puts("-1");}
void solve(){
int i = m,rn = n;
while(rn - i - book[i] + 1 > 0){
ans[i] = rn - book[i] + 1;
rn -= book[i];
i--;
}
for(int i = 1; i <= m; ++i)
printf("%d ",ans[i]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; ++i){
scanf("%d",&book[i]);
sum += book[i];
}
//check right
if(sum < n){
over();
return 0;
}
for(int i = 1; i <= m; ++i){
ans[i] = i;
if(i > n - book[i] + 1){
over();
return 0;
}
}
solve();
return 0;
}
下一篇: oscp——Hell: 1