Educational Codeforces Round 121 (Rated for Div. 2) 简训

文档中心

Educational Codeforces Round 121 （Rated for Div. 2）简训

导语
涉及的知识点
题目
- - A Equidistant Letters
  - B Minor Reduction
  - C Monsters And Spells
  - D Martial Arts Tournament
参考文献

导语

日常训练

涉及的知识点

二分，思维，贪心

链接：Educational Codeforces Round 121 (Rated for Div. 2)

题目

A Equidistant Letters

题目大意：给定一个只有小写字母的字符串s，每个字母出现不超过2次，现在需要重新排列字符串使得每两个相同字母间的距离相等，例如abcdcba，a和a间距6，b和b间距4，c和c间距2，改成ababcdc后，间距都为2

思路：直接把一样的堆在一起就行了

代码

#include #define int long longusing namespace std;int t,n,alpha[30];signed main() {    scanf("%lld",&t);    while(t--) { string s; cin >>s; memset(alpha,0,sizeof(alpha)); int len=s.size(); for(int i=0; i<len; i++)     alpha[s[i]-'a']++; for(int i=0; i<30; i++)     while(alpha[i]--)printf("%c",i+'a'); cout <<endl;    }    return 0;}

B Minor Reduction

题目大意：给出一个最多200000位的十进制非负整数x，没有前导0，定义一种操作：对x选取相邻的两位进行十进制相加然后替换原来的两位，例如10057，选取末两位得到10012，现在只能进行一次操作，求出操作之后能够得到的最大的数字是多少

思路：从低位向高位遍历，如果存在两位加起来超过10，则直接操作即可，否则操作最高位

代码

#include #define int long longusing namespace std;int t,n;char s[200005];signed main() {    scanf("%lld",&t);    while(t--) { scanf("%s",s); int len=strlen(s); bool flag=0; for(int i=len-1; i>0; i--) {     int x=s[i]-'0',y=s[i-1]-'0';     if(x+y>=10) {  x=x+y;  s[i]=x%10+'0';  s[i-1]=x/10+'0';  flag=1;  break;     } } if(flag) {     printf("%s\n",s);     continue; } s[1]=s[0]+s[1]-'0'; printf("%s\n",s+1);    }    return 0;}

C Monsters And Spells

题目大意：n个怪兽，第i个怪兽在开始之后只连续出现 $k_i$ 秒，有 $h_i$ 血，保证 $h_i\le k_i$ 且 $k_i$ 都不同，每一秒造成的伤害取决于上一秒以及自己的选择，如果上一秒没有蓄力，那么伤害/蓄力值默认为1，否则伤害/蓄力值为上一秒的值+1或者是1，每一点蓄力/伤害的花费都是对应值，每个怪物只能被攻击一次，求出能够消灭所有怪物的最小花费

思路：见参考文献和代码

代码

#include #define int long longconst int inf=0x3f3f3f3f;using namespace std;const int maxn=2e5+5;int t,n,k[maxn],h[maxn];signed main() {    ios::sync_with_stdio(0);    cin.tie(0);    cin >>t;    while(t--) { cin >>n; for(int i=1; i<=n; i++)cin >>k[i]; for(int i=1; i<=n; i++)cin >>h[i]; int kn=k[n],hn=h[n],sum=0; for(int i=n-1; i>=1; i--) {     if(kn-hn<=k[i]-h[i])continue;     //如果使n怪物消灭的起始点比i的起始点小，代表不需要更改     if(kn-hn<k[i])  hn+=kn-hn-(k[i]-h[i]);//否则就要增加伤害，起始点还需要前移     else {  sum+=(1+hn)*hn/2;//代表已经超出hn能够管理的范围了  hn=h[i],kn=k[i];//开始一个新的区域     } } sum+=(1+hn)*hn/2; cout <<sum<<endl;    }    return 0;}

D Martial Arts Tournament

题目大意：一场比赛分成三个等级：轻量级，中量级，重量级，每个等级内部进行锦标赛赛制，现在知道每个人的值，需要将所有人根据值划分成三个等级，并且每个等级必须有人，最后要让每个等级的人数都是2的整数次幂（锦标赛赛制），现在要决定两个边界来分出三个等级，不够的人数需要增加，现在需要使得增加的人数最少，求出加的最少人数

思路：由于给定的范围不大，可以直接暴力尝试区间，预处理各个值的人数以及人数前缀和，在尝试区间的时候直接二分即可，时间复杂度为 $O(n+(\log_2n)^3)$

代码

#include #define int long longconst int inf=0x3f3f3f3f;using namespace std;const int maxn=2e5+5;int t,n,mp[maxn],pre[maxn];int place(int l,int r) {    int ans=0;    int posl=upper_bound(pre+1,pre+1+n,l)-pre;//找到首个大于边界长度的位置    posl--;//减1将posl及之前的全部划分给L    ans+=l-pre[posl];    int posr=upper_bound(pre+1,pre+1+n,r+pre[posl])-pre;    posr--;    ans+=r-pre[posr]+pre[posl];    int p=1;    while(pre[n]-pre[posr]>p)p<<=1;//为剩余长度填人    ans=ans+p-pre[n]+pre[posr];    return ans;}signed main() {    ios::sync_with_stdio(0);    cin.tie(0);    cin >>t;    while(t--) { cin >>n; int res=inf,x; memset(mp,0,sizeof(mp)); for(int i=1; i<=n; i++)cin >>x,mp[x]++;//开桶记录 for(int i=1; i<=n; i++)pre[i]=pre[i-1]+mp[i];//记录前缀和，出现次数 for(int i=1; i<=n; i<<=1)     for(int j=1; j<=n; j<<=1)//尝试不同边界  res=min(res,place(i,j)); cout <<res<<endl;    }    return 0;}

参考文献

Martial Arts Tournament
Educational Codeforces Round 121 1626C Monsters And Spells

Educational Codeforces Round 121 (Rated for Div. 2) 简训