备战省赛组队训练赛第一场

怼烎@ 2022-02-22 01:15 344阅读 0赞

**目录**

问题 A: 篮球队选拔

问题 B: 黑暗意志

问题 C: 调酒壶里的酸奶

问题 D: 过分的谜题

问题 E: 不存在的泳池

问题 F: fps游戏

问题 G: 流连人间的苏苏

问题 H: 路哥从不低头

问题 I: 闪闪发光

问题 J: 小C的数学问题

问题 K: 周期串plus

问题 L: TCMPC进阶之路

--------------------

# 问题 A: 篮球队选拔 #

时间限制: 1 Sec 内存限制: 128 MB  
提交: 849 解决: 337  
\[[提交][Link 1]\] \[[状态][Link 2]\] \[命题人:外部导入\]

**题目描述**

云南中医学院坐落于风景秀丽、四季如春的——昆明，创建于1960年，是全国第二批成立的高等中医药本科院校，为云南省唯一一所中医药本科院校。学校设有11个二级学院及2个教学部。有呈贡、白塔两个校区，占地面积871.36亩。  
2016年7月2日，云南省人民政府与国家中医药管理局共建云南中医学院。  
截至2016年8月，学校拥有两个校区，占地面积763.20亩，其中呈贡校本部730.33亩，白塔校区32.87亩，总建筑面积27.3万㎡。学校现有11个二级学院、2个公共课教学部、1个实验中心、1个研究院。有教职工680人，其中，专任教师591人。图书馆藏书79万册，线装古籍图书1.8万册， 电子资源总量36TB.  
云南中医学院(筹)坐落于风景秀丽、四季如春的昆明，创建于1960年，是全国第二批成立的高等中医药本科院校，为云南省唯一一所中医药本科院校。学校设有11个二级学院及2个教学部。有呈贡、白塔两个校区，占地面积871.36亩，呈贡校区是全国高等中医药院校中环境最优美的校园之一，其建筑为云南省“最具艺术特色建筑”。  
现在云南中医学院准备成立一支篮球队，同学们都非常热情，报名人数也非常多，为了方便选拔，体育老师们准备了一个积分制度来进行选拔，这样的做法既公平又方便。特别的选拔方式也很容易吸引同学们的兴趣。  
每周体育老师们会准备许多次训练，并且通知大家时间  
组队：在规定时间到达场地并且有意向参与的同学，老师随机分配组队，队伍人数老师自行分配，至少一人一队，至多五人一队  
训练：两个队伍比赛结束后仍可以继续与其他结束比赛的队伍进行比赛  
奖励：胜利能获得135点积分值（每次训练中首胜获得270点积分），失败则获得45点积分。自行在训练时间组织比赛或自己组队，则可获得的所有积分减少到三分之一。  
技术值∈\[0,2000\]：技术值是对同学们篮球技术的数值化估计，会因为同学的训练而发生改变，但不会因为任何除技术外的因素影响  
发挥情况∈\[-1000,1000\]:老师对同学篮球技术的估计是理想化的，当然在正式进行比赛时，各种影响因素也被老师数值化为一个整数(当然运气也算作操作水平的一种)  
整体篮球技术：数值化后的发挥情况可以直接添加到技术值上，在同学们单独对战（斗牛）的胜利与否与双方的整体篮球技术有关，整体篮球技术高的可以获胜。（若整体篮球技术相等，则表示双方不论谁控球，都无法进球）  
比赛内可以提供积分的有：篮板，抢断，盖帽，扣篮，篮板和抢断每次提供21点积分，盖帽每次提供63点积分，扣篮每次提供79点积分。  
限制：每场比赛中获得积分总和不能超过300积分。  
一次训练时候，a老师给出了一个新的组队方案：将所有同学分成两队，一队由他带领，一队由另外一位体育老师b老师带领。  
组队的时候，a老师因为是发起者，所以他可以选择自己队的成员，也就是他选择一半的同学进入自己的队，剩下一半同学归b老师队。  
然后a老师每次派出己方一人进行单挑赛，由b老师从自己队伍中选择与之比赛的队员，进球数量多的一方获胜，败者出局。当然为了防止同学过度训练，每位同学只能进行一场单挑赛。每场比赛持续五分钟，若结束时双方都未进球，则两人同时出局。  
现在a老师希望自己的队伍没有人出局，请问a老师能否得到一个选人方案？

**输入**

第一行包含一个正整数T(1≤T≤10)表示多组输入数据，  
每组数据第一行包含一个正整数n(1≤n≤100000)表示有2n位同学参与训练  
第二行包含2n个正整数表示每位同学的技术值ai(0<=ai<=2000)  
第三行包含2n个正整数表示每位同学的发挥水平bi(-1000<=bi<=1000)

**输出**

每组数据包含一行，若能得到a老师想要的方案，则输出"Cheat",若不能得到，则输出"Fail"。

**样例输入**

复制样例数据

2
    2
    1 3 2 4
    1 1 1 1
    1
    1 2
    2 1

**样例输出**

Cheat
    Fail

> 注意严格大于。
> 
>     #include<iostream>
>     #include<cstdio>
>     #include<cmath>
>     #include<algorithm>
>     using namespace std;
>     const int maxn=2e5+10;
>     int a[maxn],b;
>      
>     int main(){
>         int t,n;
>         scanf("%d",&t);
>         while(t--){
>             scanf("%d",&n);
>             for(int i=0;i<2*n;i++){
>                 scanf("%d",&a[i]);
>             }
>             for(int i=0;i<2*n;i++){
>                 scanf("%d",&b);
>                 a[i]+=b;
>             }
>             sort(a,a+2*n);
>             if(a[n]>a[n-1]){
>                 printf("Cheat\n");
>             }else{
>                 printf("Fail\n");
>             }
>         }
>         return 0;
>     }

--------------------

# 问题 B: 黑暗意志 #

时间限制: 1 Sec 内存限制: 128 MB  
提交: 976 解决: 338  
\[[提交][Link 3]\] \[[状态][Link 4]\] \[命题人:外部导入\]

**题目描述**

在数千年前潘达利亚从卡利姆多分离之时，迷雾笼罩着这块新形成的大陆，使它不被外来者发现。迷雾同样遮蔽着这片大陆古老邪恶的要塞——雷神的雷电王座。在雷神统治时期，他的要塞就是雷电之王力量的保障。即使在他死后，强大而堕落的能量仍然在此萦绕不绝；而复活的雷电之王和赞达拉巨魔企图再次驾驭那股能量，重建昔日帝国。这就是魔兽世界5.2版本的大型团队副本"雷电王座"  
雷电王座中有一个神奇的BOSS是所有玩家都会记得的，直到现在当你的人物血量比BOSS血量都高的时候，在战斗的时候都要注意自己是不是会一不留神死在这个BOSS面前，它就是"黑暗意志"  
黑暗意志的整场战斗围绕着一种神秘、旋转的液体——心能；它们是在这侧厅室内魔古实验的核心。这些重要的液体有固定的量并能激活魔像。当最初储藏它们的容器被摧毁后，逃逸出的液体会不断流向越来越大的构造体；直至它们的量聚集到一定程度后，便会激活所有魔像中最大的一个——黑暗意志。  
击杀这个BOSS需要团队玩家一个人面向一个小魔像，在保证不击杀小魔像的情况下存活并且对BOSS进行输出，并且在需要时击杀小魔像以减轻治疗压力，提高对BOSS的输出  
但是在炼狱难度下，玩家不但要保证不击杀小魔像，更要保证任意一个小魔像本身的血量，有另一个小魔像的血量与它相同，那么这两个小魔像之间便会形成一条连线(每个小魔像只能连接一条线),同时小魔像上会出现一个debuff(减少小魔像50%的输出)，显然这个debuff在炼狱难度下的副本战斗中至关重要。  
所以在炼狱难度开荒的时候，队长会给两个DPS差不多的玩家组队，让这两个玩家保证自己的小魔像与另一个人的小魔像血量相同，但是在团灭五次之后，团长终于发现，不是治疗不够，而是有两个玩家的DPS与之前的DPS有了差别，所以总是不能保证他们这一组的小魔像血量相同，但是这个时候，每对玩家彼此都有了默契，重新分组显然是不明智的，那么团长准备自己去帮助那两个玩家，保证他们的小魔像血量相同，但是团长需要知道，他们两个的小魔像血量是多少，才可以去攻击那个血量较多的小魔像，来保证这两个小魔像血量相同，从而击杀BOSS。  
所以现在告诉你所有小魔像的血量，你能告诉团长，那两个玩家所对应的小魔像血量是多少吗？

**输入**

第一行一个整数T，代表数据的组数（1<=T<=10）,接下来T组数据，每组数据的第一行是一个整数n（2<=n<=1000000,保证n是偶数），第二行是n个整数ai（0 <= ai <= 1000000000）代表血量，每两个整数之间有一个空格，（输入保证有且只有两个小魔像无法连线）

**输出**

对于每组数据，输出两个整数，分别代表两个小魔像的血量，中间有一个空格，并且血量较大的先输出。

**样例输入**

复制样例数据

2
    6
    2 2 1 1 3 4
    4
    1 1 3 4

**样例输出**

4 3
    4 3

> 输入保证有且只有两个小魔像无法连线。妥妥地签到题。
> 
>     #include<iostream>
>     #include<cstdio>
>     #include<cmath>
>     #include<algorithm>
>     using namespace std;
>     const int maxn=2e5+10;
>     int a[maxn],b;
>      
>     int main(){
>         int t,n;
>         scanf("%d",&t);
>         while(t--){
>             scanf("%d",&n);
>             for(int i=0;i<2*n;i++){
>                 scanf("%d",&a[i]);
>             }
>             for(int i=0;i<2*n;i++){
>                 scanf("%d",&b);
>                 a[i]+=b;
>             }
>             sort(a,a+2*n);
>             if(a[n]>a[n-1]){
>                 printf("Cheat\n");
>             }else{
>                 printf("Fail\n");
>             }
>         }
>         return 0;
>     }

--------------------

# 问题 C: 调酒壶里的酸奶 #

时间限制: 1 Sec 内存限制: 128 MB  
提交: 511 解决: 201  
\[[提交][Link 5]\] \[[状态][Link 6]\] \[命题人:外部导入\]

**题目描述**

最近小w学了一手调酒的技巧，这么帅的操作，说不定能靠这个俘获女神的芳心，为了在女神面前露一手，他想在学校里建一个"pub"，但是显然学校不可能让他真的建一个"pub"，那么他退而求次，想建一个"Yogurt shop"，不能用酒，那用酸奶也行啊！  
今天女神终于来光顾小w的酸奶店了！兴奋的小w拿出自己准备已久每天都仔细擦干净的装备——调酒壶、果汁机、隔冰器和计量杯、砧板、小刀....准备露一手给女神看看  
但是女神却没有那么多耐心，女神只是觉得，自己买一瓶大酸奶喝不完，小瓶酸奶不够喝，所以在小w的酸奶店，说不定她可以想买多少就买多少。  
于是女神告诉了小w她想要多少体积的酸奶，而小w却依旧想秀一下自己的操作，于是他决定用仅有的两个调酒壶为女神倒出女神想要的酸奶....  
小w的两个调酒壶体积是不同的(一开始都是空的)，小w每次可以选择一个调酒壶倒入另一个调酒壶（若A倒入B，A倒完或B倒满则停止），或者选择一个调酒壶倒光，或者选择一个调酒壶去接满酸奶.....  
满心失望的小w想找一朵花，一瓣一瓣的撕下来，问问花朵女神到底喜不喜欢他...虽然这个答案是显而易见的，但是他还是想找一朵花...然而找花未果，反正花瓣不是偶数就是奇数，那他索性就用自己的操作次数作为花瓣个数吧！（找不到花我还不能脑补一朵吗...）  
但是小w已经没有心情去想答案了...那么你能告诉他，需要多少步操作才能倒出女神想要的酸奶吗？

**输入**

输入包含多组数据，每行三个正整数a,b,c分别表示两个调酒壶的容量以及女神想要的酸奶体积,a,b的范围都在\[0,100\]，c<=max(a,b)

**输出**

一行包含一个整数表示完成要求的最少操作次数，若达不到则输出"impossible"（没有双引号）

**样例输入**

复制样例数据

10 15 11
    6 5 4

**样例输出**

impossible
    4

提示

我不知道为什么酸奶可以倒进调酒壶，我也不知道为什么女神不喜欢小w，我只知道凭小w的想象力，游泳池都行更别说一朵花了！

> 六种情况进行拓展。
> 
>     #include<iostream>
>     #include<cstdio>
>     #include<cstring>
>     #include<queue>
>     #include<cmath>
>     #include<set>
>     #include<algorithm>
>     using namespace std; 
>     typedef long long ll;
>     const int maxn=110;
>     int vis[maxn][maxn],A,B,C;
>       
>     struct Node{
>         int a,b,c;
>         Node(){
>             a=0;
>             b=0;
>             c=0;
>         }
>     };
>       
>     int bfs(){
>         memset(vis,0,sizeof(vis));
>         Node tmp,nxt;
>         queue<Node> q;
>         q.push(nxt);
>         vis[nxt.a][nxt.b]=1;
>         while(!q.empty()){
>             tmp=q.front();
>             q.pop();
>             for(int i=0;i<6;i++){
>                 nxt=tmp;
>                 nxt.c++;
>                 if(i==0){
>                     nxt.a=A;  //A倒满 
>                 }
>                 if(i==1){
>                     nxt.b=B;  //B倒满 
>                 }
>                 if(i==2){
>                     int t=min(nxt.b,A-nxt.a);
>                     nxt.a+=t;
>                     nxt.b-=t;  //B倒入A 
>                 }
>                 if(i==3){
>                     int t=min(nxt.a,B-nxt.b);
>                     nxt.b+=t;
>                     nxt.a-=t;  //A倒入B 
>                 }
>                 if(i==4){
>                     nxt.a=0;  //A倒光
>                     nxt.b=tmp.b;
>                 }
>                 if(i==5){
>                     nxt.a=tmp.a;
>                     nxt.b=0;  //B倒光 
>                 }
>                 //printf("a=%d,b=%d,c=%d\n",nxt.a,nxt.b,nxt.c);
>                 if(vis[nxt.a][nxt.b]) continue;
>                 if(nxt.a==C||nxt.b==C) return nxt.c;
>                 vis[nxt.a][nxt.b]=1;
>                 q.push(nxt);
>             }
>         }
>         return -1;
>     }
>       
>     int main(){
>         while(~scanf("%d%d%d",&A,&B,&C)){
>             int res=bfs();
>             if(res==-1) printf("impossible\n");
>             else printf("%d\n",res);
>         }
>         return 0;
>     }

--------------------

# 问题 D: 过分的谜题 #

时间限制: 1 Sec 内存限制: 128 MB  
提交: 576 解决: 238  
\[[提交][Link 7]\] \[[状态][Link 8]\] \[命题人:外部导入\]

**题目描述**

2060年是云南中医学院的百年校庆，于是学生会的同学们搞了一个连续猜谜活动：共有10个谜题，现在告诉所有人第一个谜题，每个谜题的答案就是下一个谜题的线索....成功破解最后一个谜题后，答案就是指向奖励的线索  
在所有同学们的努力下，全校同学们获得了最后一个谜题，这个谜题有几十张纸，上面全是密密麻麻的数字以及'.'  
第一页内容如下：  
1,2,3,4,5,6  
4,1,5,2,6,3  
2,4,6,1,3,5  
1,2,3,4,5,6  
———3

1,2,3,4....32  
.............  
.............  
———10

有细心的同学发现，这是对一组1-2n的序列进行如下移动：每次将前n个数字取出，按顺序依次插入到位于n+1,n+2...2n的数字后面，最后的数字表示多少次移动后会变回原来的序列  
第二页内容如下：  
1,2,3,4....64  
.............  
.............  
———?

1,2,3,4....140  
.............  
.............  
———?

同学们发现，越往后翻，这个序列的长度就越长，前面十几二十个数字的序列同学们还可以一步一步模拟做出来，但是到后来几千甚至上万的长度，就没有办法计算了，甚至中间一步做错，就步步都错。  
这个谜题真是太过分了！但是奖励就在眼前，只要计算出所有答案，所有答案就是指引同学们获得奖励的线索，那么现在问题来了，同学们除了发现上面的n=最后那个数字/2之外，没有办法给你任何帮助，而作为一个计算机科学与技术专业的大佬，你自然就成为了同学们心目中拯救他们的英雄，所以你能不能写一个程序，当你知道n是多少的时候，可以直接得出答案呢？

**输入**

多组测试数据.每组数据的第一行包含一个正整数n(1<= n<=10000).

**输出**

每组数据输出一行整数表示最少需要经过几次移动能变回原序列，若不能，则输出"-1"

**样例输入**

复制样例数据

3
    16

**样例输出**

3
    10

> 模拟题，只针对于一个数位置的变化即可，当这个数变到原来的位置时，整个序列也就变到了原序列；当这个数变到最后一个位置时，整个序列还有一半的工作需要做。
> 
>     #include<iostream>
>     #include<cstdio>
>     #include<cstring>
>     #include<cmath>
>     #include<set>
>     #include<algorithm>
>     using namespace std; 
>     typedef long long ll;
>     const int maxn=2e4+10;
>     int vis[maxn];
>      
>     int main(){
>         int n;
>         ll cnt;
>         while(~scanf("%d",&n)){
>             memset(vis,0,sizeof(vis));
>             cnt=1;
>             int tmp=2;
>             while(true){
>                 //printf("tmp=%d\n",tmp);
>                 if(vis[tmp]){
>                     cnt=-1;
>                     break;
>                 }
>                 if(tmp==1) break;
>                 if(tmp==2*n){
>                     cnt*=2;
>                     break;
>                 }else if(tmp<=n){
>                     vis[tmp]=1;
>                     tmp*=2;
>                     cnt++;
>                 }else{  //tmp>n
>                     vis[tmp]=1;
>                     tmp=2*(tmp-n)-1;
>                     cnt++;
>                 }
>             }
>             printf("%d\n",cnt);
>         }
>          
>         return 0;
>     }

--------------------

# 问题 E: 不存在的泳池 #

时间限制: 1 Sec 内存限制: 128 MB  
提交: 650 解决: 288  
\[[提交][Link 9]\] \[[状态][Link 10]\] \[命题人:外部导入\]

**题目描述**

小w是云南中医学院的同学，有一天他看到了学校的百度百科介绍：  
截止到2014年5月，云南中医学院图书馆纸本藏书74.8457万册，纸质期刊388种，馆藏线装古籍图书1.8万册，电子资源总量35TB，拥有中、外文数据库25个，电子图书29.5万册（镜像）、包库130万册。古籍线装图书1.8万余册，有39种列为本馆珍善本，如《彻滕八编》、《赵氏医贯》等明清版本、台湾文渊阁版本《四库全书》，按《全国古籍善本书总目》分类表（即：经·史·子·集四部分类）部编列、上架、供读者使用。  
显然学校图书馆的占地面积非常大，于是他开始想象.....如果他有一个跟图书馆一样大的游泳池？！  
如果有一个那么大的游泳池，他就可以邀请女神一起去游泳...  
如果有一个那么大的游泳池，他还可以划开一半出租，收取门票费赚钱...这样等赚了一些钱之后，就招一些游泳教练来，然后对外招生，招收学生继续赚更多的钱！  
如果有一个那么大的游泳池，他还能把泳池里的水全部放光...开一个吕子乔心目中最大最棒的泳池派对！  
.......  
等有了更多的钱，就可以在第一个泳池旁边再建一个一样大的泳池......  
小w一边流口水一边想自己的未来，一想到女神看到自己事业有成，靠一个游泳池白手起家发家致富，对自己投怀送抱，高兴的根本合不拢嘴。  
这时候旁边的小q作为小w的室友，随口提了一句：“这么大的泳池，你怎么换水？”  
显然小w是个有原则的人，他不会让自己的泳池像不法商家一样不换水，用不干净的水给别人使用或者给自己使用。  
小w百度了之后发现...淘宝里有一家店卖一种一次性抽水机，这种一次性抽水机很神奇，它有两个按钮：  
1.如果泳池里的水（立方米）是3的倍数，那么可以按第一个按钮让它抽走泳池里三分之二的水  
2.如果泳池里的水（立方米）是2的倍数，那么可以按第二个按钮让它抽走泳池里二分之一的水  
小w虽然是个有原则的人，但是作为一个商人，他需要节省钱...而且他现在有两个泳池....但是显然这种抽水机不能把水抽光，水越少，性价比就越低。  
但是两个泳池建在一起，如果两个泳池的水面不一样高，那么小w会很不开心，所以他想用这种抽水机，把两个泳池里的水抽成一样多。然后再考虑别的....当然在保证能把两个泳池里的水抽成一样多的情况下..他希望花的钱最少...  
（不管了！好看最重要，好看才能吸引顾客啊！先好看！再考虑怎么换水吧）

**输入**

多组测试数据，给出A,B表示两个泳池当前的水量(立方米)

（1<=A,B<=10^9）

**输出**

每组测试数据输出一个整数表示至少需要买多少个一次性抽水机，若买多少个都不能让泳池的水相等，则输出"-1"

**样例输入**

复制样例数据

5 20
    14 8
    6 6

**样例输出**

2
    -1
    0

提示

显然这一切都是他的YY，他怎么可能会有游泳池？？？

> gcd.
> 
>     #include<iostream>
>     #include<cstdio>
>     #include<cmath>
>     #include<set>
>     #include<algorithm>
>     using namespace std;
>     const int maxn=2e5+10;
>      
>     int gcd(int x,int y){
>         if(y==0) return x;
>         return gcd(y,x%y);
>     } 
>      
>     int main(){
>         int a,b;
>         while(~scanf("%d%d",&a,&b)){
>             if(a==b){
>                 printf("0\n");
>                 continue;
>             }
>             int g=gcd(a,b);
>             int ca=a/g,cb=b/g,cnt=0;
>             while(ca%2==0){
>                 ca/=2;
>                 cnt++;
>             }
>             while(ca%3==0){
>                 ca/=3;
>                 cnt++;
>             }
>             while(cb%2==0){
>                 cb/=2;
>                 cnt++;
>             }
>             while(cb%3==0){
>                 cb/=3;
>                 cnt++;
>             }
>             if(ca==1&&cb==1){
>                 printf("%d\n",cnt);
>             }else{
>                 printf("-1\n");
>             }
>         }
>         return 0;
>     }

#  #

--------------------

# 问题 F: fps游戏 #

时间限制: 1 Sec 内存限制: 128 MB  
提交: 1350 解决: 109  
\[[提交][Link 11]\] \[[状态][Link 12]\] \[命题人:外部导入\]

**题目描述**

fps游戏是第一人称射击游戏。这类游戏有一个很重要的技巧也是基本功之一的，是压枪。  
为了模拟真实环境，在游戏里你每开一枪，枪口都会往上和左右浮动。  
如果你想使枪口在某个范围内，为了提高精准度，你就必须压枪。  
而且每把枪的后坐力不同和有效打击距离不同，就需要对每把枪都很熟悉，能很快的计算出在多远距离外开枪枪口会往上和左右浮动多少。  
现在只考虑枪的垂直浮动。  
假设在d米外有一个靶子，初始枪口正对靶心的圆心，靶心是个半径为r米的圆,现在你要射击c次。(你可以把枪看成一个点)。  
为了省力，要使压枪次数最少。  
只有当在靶上的射击位置在靶心之外时才需要压枪。  
每次压枪，枪口都会回到上次的射击位置。  
每次开枪最多只能压一次枪，不能连续压枪。

**输入**

每个输入文件只包含一组数据。  
包含3个正整数d,r，c和1个实数a(d,r,c意义如上文所述，a是每次开枪，枪口向上浮动的角度)。  
(1 <= d,r <= 100,0 <= c <= 1000000,0 <= a < 90)

**输出**

一个整数，表示压枪的最少次数。

**样例输入**

复制样例数据

10 1 10 3

**样例输出**

> 注意第一次指哪里就射到哪里，另外角度不与偏移量成正比。
> 
>     #include<iostream>
>     #include<cstdio>
>     #include<cmath>
>     using namespace std;
>     const int maxn=2e5+10;
>     const double PI=acos(-1);
>       
>     int main(){
>         int d,r,c;
>         double a,b;
>         while(~scanf("%d%d%d%lf",&d,&r,&c,&a)){
>             int i;
>             double h=0;
>             b=a;
>             for(i=1;i<=c;i++){
>                 h=tan(PI/180*b)*d;
>                 //printf("h=%llf\n",h);
>                 if(h>r) break;
>                 b+=a;
>             }
>             //printf("%d\n",i);
>             if(i>c) i=0;
>             else i=c-i;
>             printf("%d\n",i);
>         }
>           
>         return 0;
>     }

--------------------

# 问题 G: 流连人间的苏苏 #

时间限制: 1 Sec 内存限制: 128 MB  
提交: 574 解决: 289  
\[[提交][Link 13]\] \[[状态][Link 14]\] \[命题人:外部导入\]

**题目描述**

苏苏在做红尘仙的任务时，发现坐落于风景秀丽、四季如春的昆明市的云南中医学院。

没过多久，苏苏就喜欢上了这个学校。以致于苏苏忘了回涂山的时间，现在她只剩下d天的时间待在云南中医学院。由于时间紧迫，苏苏想方设法为建设更好的云南中医学院。

假设学校里某条街道有n个房子。

每天选择两个门牌号l、r,给这两个门牌号之间的所有房子的门前都栽一棵树，已经有树的不需要再种。

苏苏想知道在某天，有哪些房子前有树。

**输入**

每个输入文件只有一组数据  
第一行包含n,d。(1 <= n,d <= 1000)  
接下来d行，每行包含两个整数l,r(1 <= l <= r <= n)

**输出**

输出d行。  
每行输出门牌号的区间。每个区间以逗号分隔。  
具体看样例。

**样例输入**

复制样例数据

10 4
    1 3
    2 4
    5 6
    8 10

**样例输出**

[1,3]
    [1,4]
    [1,6]
    [1,6],[8,10]

> 简单模拟。
> 
>     #include<iostream>
>     #include<cstdio>
>     #include<cmath>
>     #include<set>
>     #include<algorithm>
>     using namespace std;
>     const int maxn=1e3+10;
>     int vis[maxn];
>      
>     int main(){
>         int n,d,a,b;
>         scanf("%d%d",&n,&d);
>         while(d--){
>             scanf("%d%d",&a,&b);
>             for(int i=a;i<=b;i++){
>                 vis[i]=1;
>             }
>             bool flag=false,cnt=0;
>             for(int i=1;i<=n+1;i++){
>                 if(!flag&&vis[i]){
>                     if(cnt==0){
>                         printf("[%d,",i);
>                         cnt++;
>                     }else{
>                         printf(",[%d,",i);
>                     }
>                     flag=true;
>                 }else if(flag&&vis[i]==0){
>                     printf("%d]",i-1);
>                     flag=false;
>                 }
>             }
>             printf("\n");
>         }
>         return 0;
>     }

--------------------

# 问题 H: 路哥从不低头 #

时间限制: 1 Sec 内存限制: 128 MB  
提交: 441 解决: 57  
\[[提交][Link 15]\] \[[状态][Link 16]\] \[命题人:外部导入\]

**题目描述**

路哥是云南中医学院大一新生，对路哥来说任何人任何物都只是他的道具而已。  
过程不重要，只要最后胜利是属于路哥的。  
路哥每次出完手就把这锅扔给别人。  
而他自己，深藏功与名，事了拂衣去。  
毕竟，深藏不露是一种卓越的才能。  
某天，路哥被班主任叫去清理海报。  
这里有一块宽为W，高为H的海报栏。以左下角为原点建立直角坐标系。  
第i张贴上去的海报左下角为(x1\_i,y1\_i),右上角为(x2\_i,y2\_i)。  
撕去一张海报会导致所有覆盖在其上的海报被同时撕掉(这个过程具有传递性，即如果A覆盖B，B覆盖C，那么撕掉C会导致A和B均被撕掉)  
一张海报如果可以被撕掉需要至少存在一个角没有被其他海报覆盖。  
海报A被海报B覆盖当且仅当存在A和B的交面积大于0，并且A在B之前贴出。  
由于路哥嫌麻烦，为了提高效率，路哥会一次性的撕掉尽可能多的海报。  
现在请你帮路哥计算路哥一次最多可以撕掉多少张海报。  
在张数相同的情况下，路哥会选择更早贴出的海报。

**输入**

多组数据。  
第一行三个整数W,H,N,分别为海报栏的宽和高，贴出的海报数量。  
接下来N行，每行四个整数x1\_i,y1\_i,x2\_i,y2\_i。  
(1 <= W,H <= 10000000, 1 <= N <= 1000, 0 <= x1\_i,x2\_i <= W, 0 <= y1\_i,y2\_i <= H)

**输出**

输出两个整数，分别是海报数量和撕去的是第几张。

**样例输入**

复制样例数据

6 7 4
    0 0 4 4
    1 0 3 4
    1 4 4 6
    0 0 3 5

**样例输出**

3 1

--------------------

# 问题 I: 闪闪发光 #

时间限制: 1 Sec 内存限制: 128 MB  
提交: 954 解决: 244  
\[[提交][Link 17]\] \[[状态][Link 18]\] \[命题人:外部导入\]

**题目描述**

一所位于云南昆明的中医药本科院校--云南中医学院。

因为报考某专业的人数骤减，正面临着停招的危机。

其中有九名少女想到一条妙计——成为偶像，

只要她们成为偶像，学校的名气便会增加，而报考的人数亦会上升。

就这样，九位个性鲜明的少女决定一起努力成为偶像。

希望可以凭借偶像的名气增加生源来挽救自己所喜爱的专业，让自己的学校闪闪发光。

她们为了成为偶像，第一步对于她们来说是减肥！

这里有n个重物，第i个重物的重量是2^\{w\_i\}。她们每天任务要完成的重量是n个重物的重量和。

每次举重的重量和必须是2的幂，重物数量不要求。

但是为了方便，要使举重的次数最少。

**输入**

多组数据。  
每组数据第一行一个整数n。(1 <= n <= 10^6)  
第二行有n个整数w\_1,w\_2,...,w\_n。(0 <= w\_i <= 1000000)

**输出**

输出最少的举重次数。

**样例输入**

复制样例数据

5
    1 1 2 3 3

**样例输出**

提示

1,1,2一组;  
3,3一组。

> 1 1合并为2, 2 2合并为3.
> 
> 知道这个规律后，模拟。
> 
>     #include<iostream>
>     #include<cstdio>
>     #include<cmath>
>     #include<set>
>     #include<algorithm>
>     using namespace std;
>     const int maxn=2e5+10;
>      
>     int main(){
>         int n,a;
>         while(~scanf("%d",&n)){
>             set<int> s;
>             while(n--){
>                 scanf("%d",&a);
>                 if(s.find(a)==s.end()){
>                     s.insert(a);
>                 }else{
>                     while(s.find(a)!=s.end()){
>                         s.erase(a);
>                         a++;
>                     }
>                     s.insert(a);
>                 }
>             }
>             printf("%d\n",s.size());
>         }
>          
>         return 0;
>     }

#  #

--------------------

# 问题 J: 小C的数学问题 #

时间限制: 1 Sec 内存限制: 128 MB  
提交: 602 解决: 153  
\[[提交][Link 19]\] \[[状态][Link 20]\] \[命题人:外部导入\]

**题目描述**

小C是个云南中医学院的大一新生，在某个星期二，他的高数老师扔给了他一个问题。

让他在1天的时间内给出答案。

但是小C不会这问题，现在他来请教你。

请你帮他解决这个问题。

有n个数，每个数有权值。

数学老师定义了区间价值为区间和乘上区间内的最小值。

现在要你找出有最大区间价值的区间是什么，并输出区间价值。

**输入**

每个输入文件只包含单组数据。  
第一行一个整数n。(1 <= n <= 100000)  
第二行n个整数a\_1,a\_2,...,a\_n。(0 <= a\_i <= 1000000)

**输出**

第一行输出一个整数，表示最大的区间价值。  
第二行输出两个整数，表示区间的起点和终点。  
保证答案唯一。

**样例输入**

复制样例数据

6
    10 1 9 4 5 9

**样例输出**

108
    3 6

#  #

--------------------

# 问题 K: 周期串plus #

时间限制: 1 Sec 内存限制: 128 MB  
提交: 860 解决: 307  
\[[提交][Link 21]\] \[[状态][Link 22]\] \[命题人:外部导入\]

**题目描述**

如果一个字符串可以由某个长度为k的字符串重复多次得到，我们说该串以k为周期。例如abcabcabcabc以3为周期（当然他也以6，12为周期）。输入一个长度不超过100000的串，输出他的最小周期。

**输入**

多组测试数据,每组仅一行为一个仅有大写字母组成的字符串。

**输出**

对于每组数据输出该字符串的最小周期。

**样例输入**

复制样例数据

HOHO

**样例输出**

> 开始还以为是KMP，其实只是一个简单模拟，直接暴力即可。
> 
>     #include<iostream>
>     #include<cstdio>
>     #include<cmath>
>     #include<set>
>     #include<algorithm>
>     using namespace std;
>     const int maxn=1e3+10;
>     string t;
>      
>     int main(){
>         while(cin>>t){
>             int len=t.length();
>             bool flag;
>             for(int i=1;i<len;i++){
>                 if(len%i==0){
>                     flag=true;
>                     for(int j=i;j<len;j++){
>                         if(t[j]!=t[j%i]){
>                             flag=false;
>                             break;
>                         }
>                     }
>                     if(flag){
>                         printf("%d\n",i);
>                         break;
>                     }   
>                 }
>             }
>             if(!flag)
>                 printf("%d\n",len);
>         }
>          
>         return 0;
>     }

--------------------

# 问题 L: TCMPC进阶之路 #

时间限制: 1 Sec 内存限制: 128 MB  
提交: 385 解决: 347  
\[[提交][Link 23]\] \[[状态][Link 24]\] \[命题人:外部导入\]

**题目描述**

小w是云南中医学院计算机专业的一名学生，最近决心开始好好学习（当然是因为太菜被女神嫌弃了..）

作为一个超级菜的菜鸟，进步的最好方式就是奋发图强努力刷题！于是小w开始在ZCMUOJ中做题。ZCMUOJ新开了一个叫<C语言练习>的专题，引进了一个新模式——积分系统，积分越多，账号称号就越高级：

\[0-50\]：菜鸟

(50-500\]:入门

(500-2000\]:黑铁级入门选手

(2000-8000\]:青铜级入门选手

(8000-20000\]:白银级入门选手

(20000-80000\]:黄金级入门选手

(80000-200000\]:钻石级入门选手

(200000-500000\]:专业级入门选手

(500000-1000000\]:TCMPC热身赛选手

(1000000-2000000\]:TCMPC正赛选手

(2000000-5000000\]:TCMPC铜牌选手

.........

当然，每道题目都有它相应的积分，ID为1的题目AC后会获得1分，ID为2的题目AC后获得2分...ID为i的题目AC后会获得i分，那么现在小w为了成为女神心目中的大神，决定从第一题开始做，绝不跳过任何题目，严格按顺序往下做。

那么现在小w已经做到第n题了，但是积分系统却没有显示个人积分，所以他想知道他现在的积分是多少，以便计算还需要多少题才能进阶，以此给自己动力,你能帮他吗？

**输入**

多组数据，第一行输入一个整数T（1≤T≤10000）表示数据组数  
以下T行，每行输入一个正整数n(1≤n≤10000）表示小w当前做到第n题(第n题也已AC)，且题目编号是有序的。

**输出**

每行输出一个整数表示小w当前的积分

**样例输入**

复制样例数据

2
    5
    10

**样例输出**

15
    55

> 啊哈~直接上代码。
> 
>     #include<iostream>
>     #include<cstdio>
>     #include<cmath>
>     #include<set>
>     #include<algorithm>
>     using namespace std;
>     const int maxn=2e5+10;
>      
>     int main(){
>         int t,n;
>         scanf("%d",&t);
>         while(t--){
>             scanf("%d",&n);
>             n=n*(n+1)/2;
>             printf("%d\n",n);
>         }
>         return 0;
>     }

[Link 1]: http://icpc.upc.edu.cn/submitpage.php?cid=1721&pid=0&langmask=262133
[Link 2]: http://icpc.upc.edu.cn/problemstatus.php?id=4881
[Link 3]: http://icpc.upc.edu.cn/submitpage.php?cid=1721&pid=1&langmask=262133
[Link 4]: http://icpc.upc.edu.cn/problemstatus.php?id=4882
[Link 5]: http://icpc.upc.edu.cn/submitpage.php?cid=1721&pid=2&langmask=262133
[Link 6]: http://icpc.upc.edu.cn/problemstatus.php?id=4883
[Link 7]: http://icpc.upc.edu.cn/submitpage.php?cid=1721&pid=3&langmask=262133
[Link 8]: http://icpc.upc.edu.cn/problemstatus.php?id=4884
[Link 9]: http://icpc.upc.edu.cn/submitpage.php?cid=1721&pid=4&langmask=262133
[Link 10]: http://icpc.upc.edu.cn/problemstatus.php?id=4885
[Link 11]: http://icpc.upc.edu.cn/submitpage.php?cid=1721&pid=5&langmask=262133
[Link 12]: http://icpc.upc.edu.cn/problemstatus.php?id=4886
[Link 13]: http://icpc.upc.edu.cn/submitpage.php?cid=1721&pid=6&langmask=262133
[Link 14]: http://icpc.upc.edu.cn/problemstatus.php?id=4887
[Link 15]: http://icpc.upc.edu.cn/submitpage.php?cid=1721&pid=7&langmask=262133
[Link 16]: http://icpc.upc.edu.cn/problemstatus.php?id=4888
[Link 17]: http://icpc.upc.edu.cn/submitpage.php?cid=1721&pid=8&langmask=262133
[Link 18]: http://icpc.upc.edu.cn/problemstatus.php?id=4889
[Link 19]: http://icpc.upc.edu.cn/submitpage.php?cid=1721&pid=9&langmask=262133
[Link 20]: http://icpc.upc.edu.cn/problemstatus.php?id=4890
[Link 21]: http://icpc.upc.edu.cn/submitpage.php?cid=1721&pid=10&langmask=262133
[Link 22]: http://icpc.upc.edu.cn/problemstatus.php?id=4891
[Link 23]: http://icpc.upc.edu.cn/submitpage.php?cid=1721&pid=11&langmask=262133
[Link 24]: http://icpc.upc.edu.cn/problemstatus.php?id=4892