请选择 进入手机版 | 继续访问电脑版

Educational Codeforces Round 101 (Rated for Div. 2)

[复制链接]
太阳神鹰 发表于 2021-1-1 10:29:10 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
A. Regular Bracket Sequence

题目链接:点击查看
题目大意:
给定一个由()?三种字符组成的序列,该序列中符号(和)各有一个且只有一个。此中?字符可以替换成(和)任意一个,问是否能将整个序列通过替换?使整个序列的括号匹配(一个(对应一个))。
思路:
首先判断序列长度是否与2同余,因为只有这样才气包管(和)的个数相等。若满足,将原序列中前一半的?看成(,后一半看成),再判断括号是否匹配即可。
Code:
  1. #include#define N 101using namespace std;char s[N];int main(){        int T;        scanf("%d ",&T);        while(T--){                gets(s);                int len = strlen(s);                if(len % 2 != 0){                        puts("NO");                        continue;                }                int sum = (len - 2) / 2;                bool flag = false;                int top = 0;                for(int i = 0; i < len; i++){                        if(s[i] == &#39;(&#39;) top++;                        else if(s[i] == &#39;?&#39; && sum) top++, sum--;                        else{                                if(top == 0){                                        flag = 1;                                        break;                                }                                top--;                        }                }                if(flag) puts("NO");                else puts("YES");         }        return 0;}
复制代码
B. Red and Blue

题目链接:点击查看
题目大意:
给定两个序列,有n个元素的ri和有m个元素的bi。让这两个序列拼到一起构成一个新序列ai,需包管ri中的元素在ai中的位置顺序和在ri中的顺序相同,bi也是如此。
令f(a)=max(0,a1,(a1+a2),(a1+a2+a3),…,(a1+a2+a3+⋯+an+m)),求f(a)的值。
思路:
分别求ri和bi前i项元素和的最大值ans1和ans2,二者相加即答案。
Code:
  1. #includeusing namespace std;int n, m, ans;int r, b;int sum1, sum2, ans1, ans2;int main(){        int T;        scanf("%d", &T);        while(T--){                ans1 = ans2 = 0;                sum1 = sum2 = 0;                scanf("%d", &n);                for(int i = 1; i  r) puts("NO");                else puts("YES");        }        return 0;}
复制代码
D. Ceil Divisions

题目链接:点击查看
题目大意:
给定一个序列ai,此中ai = i。
在一步操作中, 可以选择1到n范围内的两个数x,y(x != y),将ax的值改变为[ax/ay] (向上取整),目的将ai序列改变为由n-1个1和1个2组成的序列。输出操作次数以及操作方案。 要求操作次数不凌驾n + 5次。
思路:
显然,对于数x,y:
操作1.若x  y且x  y * y,则需操作2次以上才可将ax改变为1。
用贪心的思维来想,若想操作次数尽可能的少,则x应尽可能小于等于y * y。
想要得到1很简朴,只需要使y等于n,任何不能与n的x举行一次操作后都可以变成1。但是这样一来an就无法改变。
所以现在的问题是如何改变an
我们首先思量如何得到序列最终的一个2:
如果2是由第2种方式得到,那么一定会使得序列中存在多个2或存在除1,2以外的数,故最终的2应该是原来就存在的a2,得到2需要0次操作。
下面思量如安在n + 5次操作内得到n - 1个1。
既然a2生存到了最后,那么我们不妨从它延伸:


  • 通过a2将a4改变成1需要2次操作
  • 通过a4将a16改变成1需要2次操作
  • 通过a16将a256改变成1需要两次操作
  • 通过a256将a65536改变成1需要两次操作
这样a4,a16,a256,a65536在两次操作内可以变成1,同时an可以通过这四个数以及a2中小于n且距n最近的一个数改变成1,最多只需2次操作。
这样,在最坏的情况下,a4,a16,a256,a65536,an这五个数最多只需要两次操作可以改变成1,除2外其他数可以通过1次操作改变成1,2不需要改变,总共n + 4次操作,满足条件!
Code
[code]#include#define N 200001using namespace std;bool vis[N];int tmp[N], ans1[N] , ans2[N];int n, t, num, numt;int main(){        int T;        long long t = 2;        while(t
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )