计算机学院2022级新生周赛（一）题解

A. Hello , HAUE

原题链接

描述

欢迎大家参加河南工程学院2022级第一次新生周赛，LYS代表计算机ACM协会在此祝愿大家的大学生涯一帆风顺，自信满满；友情爱情，两全其美；三阳开泰，学业大展；魅力四射，朋友万千；五福临门，幸福美满；六六大顺，学识博渊；七步之才，知识无边；八仙过海，才华呈现；九霄云外，烦恼抛开；十全十美，大学前途熠熠生辉！！！

输入格式

第一行，输入一个整数 N。

输出格式

输出占一行，不含引号。

若 N = 1，输出 "One Sail Wind Go"。

若 N = 6，输出 "Six Six Big Go"。

若 N = 10，输出 "Ten OK Ten OK"。

若 N = 2022，输出 "Hello , HAUE"。

样例输入

代码语言：javascript

复制

样例输出

代码语言：javascript

复制

Hello , HAUE

思想：

签到题，考察选择结构。
注意 "Hello , HAUE" 的符号是中文，直接复制粘贴。

C代码：

代码语言：javascript

复制

#include <stdio.h>
int main(){
int n;

scanf(&#34;%d&#34;, &amp;n);

if(n == 1) printf(&#34;One Sail Wind Go\n&#34;);
else if(n == 6) printf(&#34;Six Six Big Go\n&#34;);
else if(n == 10) printf(&#34;Ten OK Ten OK\n&#34;);
else printf(&#34;Hello , HAUE\n&#34;);

return 0;

}

B. 我必须立刻签到，因为它有手就行

原题链接

描述

在算法竞赛的题目当中，有很多难度逆天的题，然鹅，也有个别的题肥肠煎蛋，像这种HFCJ一看就是"有手就行"的题目就被称之为签到题。

例如这道题目：

f(x)=

\begin{aligned}

\begin{cases}

x^2 &,0\le x\le 10\\

x\times f(x - 5) &,10\lt x\le 50\\

x + f(x - 10) &,50\lt x\le 100

\end{cases}

\end{aligned}

输入格式

第一行，输入一个整数 X。

输出格式

一行，输出按照上述公式计算所得 X 的结果。

数据范围

0\le X \le 100

样例输入1

代码语言：javascript

复制

样例输出1

代码语言：javascript

复制

样例输入2

代码语言：javascript

复制

样例输出2

代码语言：javascript

复制

思想：

签到题，考察递归函数。
计算后面的数较大，注意开long long。

C代码：

代码语言：javascript

复制

#include <stdio.h>

#define LL long long
LL f(LL x){
if(x &gt;=0 &amp;&amp; x &lt;= 10) return x * x;
else if(x &gt; 10 &amp;&amp; x &lt;= 50) return x * f(x - 5);
else return x + f(x - 10);

}
int main(){
LL x;

scanf(&#34;%lld&#34;,&amp;x);

printf(&#34;%lld\n&#34;,f(x));

return 0;

}

C. OrzOrzOrz

原题链接

描述

河工院21级计算机学院和软件学院存在着许许多多的大佬，这些大佬都是LYS所膜拜的对象，他们分别是：陈佬(C) ，郭佬(G)，皇甫爷(H)，金佬(J)，李佬(L)，魏佬(W)，邢佬(X)，毅佬(Y)，朱佬(Z) 等等诸多大佬（以上排名不分先后，未列出亦视为大佬），由于这些大佬经常水群，所以大家对这些大佬耳熟能详。

每次见到这些大佬在群里出现，LYS就会膜拜一番，发出“OrzOrzOrz”的消息，对于未列出的大佬出现，LYS见到了只敢在心中膜拜，不敢发消息。

一天结束，LYS想要统计今天见到的大佬的次数，可统计实在是个大工程，令LYS肥肠困扰，你能帮助他进行统计吗？

输入格式

第一行输入两个整数 N 和 M，代表大佬出现 N 次和 M 次询问。

第二行输入 N 个大写字母 (A\sim Z)，代表出现的大佬的编号。

接下来 M 行，每行输入一个大写字母 (A\sim Z)，代表询问的大佬编号。

输出格式

对于每次询问：

第一行输出询问编号的大佬出现的次数，若该编号的大佬是上述列出的大佬且出现过，则输出一个空格后输出"OrzOrzOrz"（不加引号）。

数据范围

0\le N\le 10^4

1\le M\le 26

样例输入

代码语言：javascript

复制

12 6

D N F H L H W Z A W H J

C

Z

W

A

J

H

样例输出

代码语言：javascript

复制

0

1 OrzOrzOrz

2 OrzOrzOrz

1

1 OrzOrzOrz

3 OrzOrzOrz

思想：

只有询问的大佬编号是列出的大佬才会发出 "OrzOrzOrz"。
利用int vis[N]初始化标记，vis[i]表示i是否是列出的大佬。
利用int st[N]记录大佬出现的次数。
询问时通过vis[op[0]]的状态来判断是否是列出的大佬。
注意C语言scanf()读入。

C代码：

代码语言：javascript

复制

#include <stdio.h>
const int N = 1e3 + 10;
int main(){
int st[N];  //记录大佬出现次数
int vis[N];  //标记大佬

for(int i = &#39;A&#39;; i &lt;= &#39;Z&#39;; i ++){
    if(i == &#39;C&#39; || i == &#39;G&#39; || i == &#39;H&#39; || i == &#39;J&#39; || i == &#39;L&#39; || i == &#39;W&#39; || i == &#39;X&#39; || i == &#39;Y&#39; || i == &#39;Z&#39;) vis[i] = 1;
    else vis[i] = 0;
    st[i] = 0;
}

int n, m;

scanf(&#34;%d %d&#34;, &amp;n, &amp;m);

for(int i = 1; i &lt;= n; i ++){
    char op[10];
    scanf(&#34;%s&#34;, op);  //这里读入把空格过滤掉，防止读入奇奇怪怪的东西
    st[*op] ++;
}

for(int i = 1; i &lt;= m; i ++){
    char op[10];
    scanf(&#34;%s&#34;, op);

    if(vis[*op] &amp;&amp; st[*op]) printf(&#34;%d OrzOrzOrz\n&#34;, st[*op]);  //*op 等价于 op[0]
    else printf(&#34;%d\n&#34;, st[*op]);
}

return 0;

}

C++代码：

代码语言：javascript

复制

#include <bits/stdc++.h>

using namespace std;
const int N = 1e3 + 10;
int st[N];

bool vis[N];
void solve(){
for(int i = &#39;A&#39;; i &lt;= &#39;Z&#39;; i ++){
    if(i == &#39;C&#39; || i == &#39;G&#39; || i == &#39;H&#39; || i == &#39;J&#39; || i == &#39;L&#39; || i == &#39;W&#39; || i == &#39;X&#39; || i == &#39;Y&#39; || i == &#39;Z&#39;) vis[i] = 1;
    else vis[i] = 0;
}

int n, m;

cin &gt;&gt; n &gt;&gt; m;

for(int i = 1; i &lt;= n; i ++){
    char op;
    cin &gt;&gt; op;
    st[op] ++;
}

for(int i = 1; i &lt;= m; i ++){
    char op;
    cin &gt;&gt; op;
    if(vis[op] &amp;&amp; st[op]) cout &lt;&lt; st[op] &lt;&lt; &#34; OrzOrzOrz&#34; &lt;&lt; endl;
    else cout &lt;&lt; st[op] &lt;&lt; endl; 
}

}
int main(){
solve();

return 0;

}

D. 红心诡计

原题链接

描述

Vainglory（虚荣）是由Super Evil Megacorp开发的魔幻风格MOBA类手游，曾依靠超高质量的游戏画质和独特的“点触”操控，在全球收割了千万玩家的喜爱，借助独家的游戏渲染引擎，这款风靡全球的游戏亦曾两度被Apple公司选作Iphone的性能演示宣传片，由该团队首席环境艺术设计师EvilOnTheInside绘制的地图令人着迷。除此之外，独具特色的操控和精心设计的英雄角色，也令Vainglory在MOBA竞技史上给所有人留下了深刻的印象。

可惜的是，由于Vainglory独特的操控模式上手难度极大，以及种种运营不善等原因，导致这款曾经的现象级的游戏在2020年停止了运营，但停服之后，仍有大量热爱Vainglory的玩家活跃在社区服，LYS也不例外。

LYS肥肠喜欢使用剑客黑羽这名角色，因为他不但有爆发性的刺客输出，也有一定的拉扯和扛伤能力，同时还兼具免控与位移为一体的高机动性技能，使得他在单体和团战都能发挥强大的作用。

其中，该英雄的一技能"红心诡计"描述如图：

例如：对于某一次正在发生的团战，LYS的黑羽已经将”红心诡计“升至了 5 级，满级的黑羽基础物理普通攻击的伤害是 160，且身上的装备为其提供了 50 点物理强度和 300 点法术强度。

此时LYS遇到了一名敌人，该敌人当前生命值为 500，生命值上限为 2800，他在敌人到达技能释放范围内时，发动了”红心诡计“，迅速位移至敌人位置对其施加了满层的“震颤红心”并造成伤害，击杀了敌人并刷新了“红心诡计”的冷却时间，其伤害计算如下：

\begin{aligned}

敌人受到的伤害 &= 240（5级技能基础伤害）\\

&+ 300 × 50%（法术强度×法术比率的额外伤害）\\

& + 160（该技能触发普通攻击效果，满级黑羽基础物理普通攻击的伤害是160）\\

& + 50 × 100%（物理强度×物理比率的额外伤害）\\

&+ 2300 × 25%（已损失的生命值×5级技能造成的百分比额外伤害）\\

&= 1175点！

\end{aligned}

已知：

当前LYS已经将”红心诡计“升至了 5 级，且黑羽的等级已达到最大，其基础物理普通攻击的伤害是 160。

求：敌人原地挂机不动，LYS是否可以操作黑羽，在 (X,Y) 处选择任意一个在技能范围 D 之内的敌人开始，使用“红心诡计”位移到其身边击杀敌人并刷新技能，然后选择下一个敌人，如此重复，直到击杀所有的 5 名敌人。若"红心诡计"的范围内不存在敌人或使用一次”红心诡计“无法击杀敌人，LYS将停止后续的操作。

输入格式

第一行 5 个数，分别为黑羽装备的物理强度 AD，法术强度 AP，黑羽目前的位置横坐标 X 和纵坐标 Y，以及以 (X,Y) 为中心的”红心诡计“释放范围半径 D。

接下来 5 行，每行四个数，分别为敌人当前所剩的生命值 L，生命上限 R，以及其位置的横坐标 x 和纵坐标 y.

输出格式

第一行，若可以击杀全部敌人，输出”YES“，否则输出”NO“。

若为"NO"，第二行额外输出一个整数，表示最大击杀数。

数据范围

0\le AD,AP,D\le1000

-1000\le X,Y,x,y\le 1000

1\le L\le R\le5000

样例输入1

代码语言：javascript

复制

50 200 0 0 3

200 1500 0 3

800 4000 2 2

100 1200 1 1

500 3900 3 0

600 4400 4 3

样例输出1

代码语言：javascript

复制

YES

样例输入2

代码语言：javascript

复制

100 30 -1 1 4.2

1500 1900 1.2 0.8

140.9 892.6 3.1 2.2

230 556.9 4.4 -1

530 2799.2 -2.5 -2

462.6 3784 2.9 -1.1

样例输出

代码语言：javascript

复制

NO

1

提示

对于样例 1，可行的情况为从 (0,0) 开始，先击杀 (0,3) 刷新了技能，然后击杀 (1,1) 再次刷新技能，接着击杀 (3,0)，(2,2)，(4,3) 或者从 (0,0) 开始，先击杀 (3,0) 刷新了技能，然后击杀 (1,1) 再次刷新技能，接着击杀 (0,3)，(2,2)，(4,3)。

思想1：

由题意可知，要求从(X,Y)开始，在D范围内，可以任意选择一个(x,y)位置的敌人，如果可以将其击杀，则可以将(X,Y)更新为(x,y)，继续寻找在其D范围内的敌人击杀，直至D范围内没有敌人，或下一次无法击杀敌人。
对于本题，敌人数量只有5，可以暴力枚举：第一层循环枚举敌人i，判断(X,Y)是否与(x[i],y[i])距离小于d，且若可以将其击杀，则进入下一层循环。在下一层循环开始前，我们利用int vis[N]，vis[i]来标记i号敌人已经被击杀，以后不再枚举i，用cnt记录击杀数。第二层循环枚举敌人j，判断(x[i],y[i])是否与(x[j],y[j])距离小于d，且若可以将其击杀，则进入下一层循环。在下一层循环开始前，标记vis[j]，且cnt ++。第三层循环枚举敌人q，判断(x[j],y[j])是否与(x[q],y[q])距离小于d，且若可以将其击杀，则进入下一层循环。在下一层循环开始前，标记vis[q]，且cnt ++。 \dots 直到枚举到最后一个敌人，在每一层循环退出之后更新 res，还要将敌人和击杀数恢复为上一层的进入状态。

C语言代码：

代码语言：javascript

复制

#include <stdio.h>
//check函数判断是否满足继续的条件

int check(double x1, double y1, double x2, double y2, double d, double l, double r, double ap,double ad){

if((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= d * d){

if(l <= (r - l) * 0.25 + ap * 0.5 + 240 + 160 + ad) return 1;

else return -1;

}

else return -1;

}
int main(){
int check(double x1, double y1, double x2, double y2, double d, double l, double r, double ap,double ad);

double ap, ad, X, Y, d;

scanf(&#34;%lf %lf %lf %lf %lf&#34;, &amp;ad, &amp;ap, &amp;X, &amp;Y, &amp;d);

double l[10], r[10], x[10], y[10];

for(int i = 1; i &lt;= 5; i ++) scanf(&#34;%lf %lf %lf %lf&#34;, &amp;l[i], &amp;r[i], &amp;x[i], &amp;y[i]);

int res = 0;  //res存储可以击杀的最大敌人数量

for(int i = 1; i &lt;= 5; i ++){  //第一层循环，判断从(X,Y)开始能否击杀 i 号敌人
    int cnt = 0; //表示当前击杀数
    if(check(X, Y, x[i], y[i], d, l[i], r[i], ap, ad) &lt; 0) continue;  //不能击杀则跳过
     //能击杀 i
    int vis[10];  //vis[*]存储第 * 号敌人是否已经击杀
    for(int k = 1; k &lt;= 5; k ++) vis[k] = 0; //初始化全部敌人未击杀
    vis[i] = 1;  //标记 i 已经被击杀 
    cnt ++;  //击杀数加一
    for(int j = 1; j &lt;= 5; j ++){  //第二层循环，判断击杀 i 后，剩下的敌人 j 是否可以击杀
        if(vis[j] || check(x[i], y[i], x[j], y[j], d, l[j], r[j], ap, ad) &lt; 0) continue;
         //能击杀 j
        vis[j] = 1;  //标记 j 已经被击杀 
        cnt ++;
        for(int q = 1; q &lt;= 5; q ++){  //第三层循环，判断击杀 j 后，剩下的敌人 q 是否可以击杀
            if(vis[q] || check(x[j], y[j], x[q], y[q], d, l[q], r[q], ap, ad) &lt; 0) continue;
            vis[q] = 1;
            cnt ++;
            for(int w = 1; w &lt;= 5; w ++){
                if(vis[w] || check(x[q], y[q], x[w], y[w], d, l[w], r[w], ap, ad) &lt; 0) continue;
                vis[w] = 1;
                cnt ++;
                for(int e = 1; e &lt;= 5; e ++){  //最后一个循环，判断第五个敌人是否可以击杀
                    if(vis[e] || check(x[w], y[w], x[e], y[e], d, l[e], r[e], ap, ad) &lt; 0) continue;
                    vis[e] = 1;
                    cnt ++;
                    break;
                }
                  //结束每一层的循环后
                res = res &gt; cnt ? res : cnt;  //更新最大击杀数
                vis[w] = 0;  //恢复原有的敌人状态（变为未击杀）
                cnt --;  //恢复击杀数
            }
            res = res &gt; cnt ? res : cnt;
            vis[q] = 0;
            cnt --;
        }
        res = res &gt; cnt ? res : cnt;
        vis[j] = 0;
        cnt --;
    }

    res = res &gt; cnt ? res : cnt;  //最后的更新

}

if(res == 5) printf(&#34;YES\n&#34;);
else printf(&#34;NO\n%d\n&#34;,res);

return 0;

}

思想2：

DFS搜索。
利用递归的每一层代替暴力循环嵌套。

另一种暴力搜索的思路：

对所有的敌人击杀顺序的组合进行全排列，依次判断每一种排列组合的最大击杀数。

C++代码：

代码语言：javascript

复制

#include <bits/stdc++.h>

using namespace std;
bool check(double x1, double y1, double x2, double y2, double d, double l, double r, double ap,double ad){

if((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= d * d){

if(l <= (r - l) * 0.25 + ap * 0.5 + 240 + 160 + ad) return true;

else return false;

}

else return false;

}
struct point{

double l, r, x, y;

}p[10];
int res;
bool vis[10];
void dfs(double xx, double yy, double d, double ap,double ad, int u){

for(int i = 1; i <= 5; i ++){

if(!vis[i] && check(xx, yy, p[i].x, p[i].y, d, p[i].l, p[i].r, ap, ad)){

vis[i] = 1;

dfs(p[i].x, p[i].y, d, ap, ad, u + 1);

vis[i] = 0;  //恢复状态

}

}

res = max(res, u);  //更新击杀数

return ;
}
int main(){
double ad, ap, X, Y, d;

cin &gt;&gt; ad &gt;&gt; ap &gt;&gt; X &gt;&gt; Y &gt;&gt; d;

for(int i = 1; i &lt;= 5; i ++){
    double l, r, x, y;
    cin &gt;&gt; l &gt;&gt; r &gt;&gt; x &gt;&gt; y;
    p[i] = {l, r, x, y};
}

for(int i = 1; i &lt;= 5; i ++){
    memset(vis, 0, sizeof vis);  //初始化标记
    dfs(X, Y, d, ap, ad, 0);
}

if(res == 5) cout &lt;&lt; &#34;YES&#34; &lt;&lt; endl;
else cout &lt;&lt; &#34;NO&#34; &lt;&lt; endl &lt;&lt; res &lt;&lt; endl;

return 0;

}

E. 不要停下来啊！！！

原题链接

描述

新的学期开始了，我们的奥尔加团长又一次嘱托我们，无论以后学习遇到什么困难，都请记住：“不要停下来啊！！！”

输入格式

同样例输入

第一行输入三个整数 N,M,K，代表一个 N 行 M 列的二维数组和 K 行坐标信息

接下来共 K 行，每行输入两个整数 x,y，对于二维数组 (x,y) 位置的点标记为"#"，未被标记的点记为"."

输出格式

同样例输出（注意每个字符间隔一个空格）

样例输入

代码语言：javascript

复制

样例输出

代码语言：javascript

复制

. . # . . . . . .

. # . . . . . . .

. # . . . . . . .

. # . # # . . . .

. # . # # . . . .

. # # # # # # . .

. . # # # # # . .

. . # # # # # . .

. . # # # # # . .

. . . # # . # . .

. . . # . # . # .

. . . # . . # . .

. . . # . . # . .

. . . # . . # . .

. . . # . . # . .

注意：

该二维数组下标从 (0,0) 开始。

思想1：

签到题，考察二维数组。

C代码1：

代码语言：javascript

复制

#include <stdio.h>
int main(){
char mp[100][100];

int n, m, k;

scanf(&#34;%d %d %d&#34;, &amp;n, &amp;m, &amp;k);

for(int i = 0; i &lt; n; i ++){
    for(int j = 0; j &lt; m; j ++){
        mp[i][j] = &#39;.&#39;;
    }
}

for(int i = 1; i &lt;= k; i ++){
    int x, y;
    scanf(&#34;%d %d&#34;, &amp;x, &amp;y);
    mp[x][y] = &#39;#&#39;;
}

for(int i = 0; i &lt; n; i ++){
    for(int j = 0; j &lt; m; j ++){
        printf(&#34;%c &#34;,mp[i][j]);
    }
    printf(&#34;\n&#34;);
}

return 0;

}

思想2：

样例输出即为答案，直接打表也可以。

C代码2：

代码语言：javascript

复制

#include <stdio.h>
int main(){
printf(&#34;. . # . . . . . .\n&#34;);
printf(&#34;. # . . . . . . .\n&#34;);
printf(&#34;. # . . . . . . .\n&#34;);
printf(&#34;. # . # # . . . .\n&#34;);
printf(&#34;. # . # # . . . .\n&#34;);
printf(&#34;. # # # # # # . .\n&#34;);
printf(&#34;. . # # # # # . .\n&#34;);
printf(&#34;. . # # # # # . .\n&#34;);
printf(&#34;. . # # # # # . .\n&#34;);
printf(&#34;. . . # # . # . .\n&#34;);
printf(&#34;. . . # . # . # .\n&#34;);
printf(&#34;. . . # . . # . .\n&#34;);
printf(&#34;. . . # . . # . .\n&#34;);
printf(&#34;. . . # . . # . .\n&#34;);
printf(&#34;. . . # . . # . .\n&#34;);

return 0;

}

F. 反卷行动

原题链接

描述

众所周知，河工院的计算机学院和软件学院存在着许多大佬，这些大佬们每天最喜欢做的事情就是口口声声的称："今天又是摆烂的一天，啥也没干"，其实背地里却是名副其实的"卷王"，私底下学了不少东西

LYS心中大惊Σ(っ °Д °;)っ！他说：“这样好吗？这不好！”

LYS深知卷王的可怕，靠近卷王的人迟早也会被卷王传染，进而也会变成卷王，如此下去，所有人都将被卷，这太可怕了！

可惜的是，变成卷王的人再也变不会原来的样子了，所以LYS只能尽可能的想办法守护还没有变成卷王的人。

为了顺利开展反卷行动，LYS以每一个寝室为单位进行守护，他发现寝室的排列整好是按照 1\sim N 的编号围成了一圈，并且他将有卷王存在的 M 个宿舍都打上了标记。

已知有卷王存在的宿舍 Mi 经过一个夜晚的奋战，会将其相邻的两个宿舍（M{i-1}和M_{i+1}）的人全部变成卷王（编号为 M_N 的宿舍相邻宿舍是 M1 和 M{N-1}），LYS可以在夜晚降临之前据守在任意一个没有卷王存在的宿舍 M_j，使其宿舍内的所有人获得“反卷之力”，获得“反卷之力”的宿舍在今晚不会被变成卷王，且以后也不会被变成卷王。

由于LYS太弱小了，他一天只能保护一个宿舍，但是LYS想要保护尽可能多的宿舍，因此他需要精心策划每一次的据点，由于LYS孤军奋战，他需要一个人帮他谋划据点宿舍的选择，你能帮帮他吗？

输入格式

第一行输入两个整数 N,M，分别代表寝室最大编号和卷王宿舍的数量。

第二行 M 个数，表示卷王宿舍的编号 m_i。

输出格式

输出一个整数，输出最终没有被变成卷王的宿舍数量。

数据范围

5\le N \le 10^9

1\le M\le min(N,2\times 10^5)

1\le m_i\le N

样例输入1

代码语言：javascript

复制

6 2

3 5

样例输出1

代码语言：javascript

复制

样例输入2

代码语言：javascript

复制

12 2

8 2

样例输入2

代码语言：javascript

复制

思想：

贪心。
每次选择未被变成卷王（未被感染）宿舍的最长区间进行保护。
对于被保护的区间[l,r]：
- 经过第一天：
- 保护[l,r]的一个端点，设保护a[l]。
- a[l]不会感染，a[r]会被感染。
- 其他所有未受到保护的区间[l',r']里，a[l']和a[r']被感染。
- 经过第二天：
- 保护[l,r]的另一个端点a[r]，由于第一天a[r]被感染，故只能保护a[r - 1]。
- 其他所有未受到保护的区间[l',r']里，a[l' + 1]和a[r' - 1]被感染。
- 即对于选择保护的区间[l,r]，a[r]被感染，我们只能保护到[l,r - 1]这一段，且其余所有未受到保护的区间[l',r']里a[l'],a[r'],a[l' + 1],a[r' - 1]受到感染，感染后的区间变为[l' + 2, r' - 2]。
综上可知，我们优先保护最长的未被变成卷王的区间，即可实现最优策略。
由于选择保护的区间端点可以任选，故只需要考虑区间长度，不需要维护额外的信息。
注意不要忽略首尾相连的区间。

注意：

本题的数据卡掉了冒泡排序的可能性，选手可选择任意一种时间复杂度优于冒泡排序的方法进行处理。
以 C++ 的 sort() 排序函数为例，给出如下代码1，以优先队列维护最长区间为例，给出如下代码2。
sort() 用法参考：std::sort。

C++代码1：

代码语言：javascript

复制

#include <bits/stdc++.h>

using namespace std;
const int N = 1e7 + 10;
int a[N], b[N];
int main(){
int n, m;

scanf(&#34;%d %d&#34;, &amp;n, &amp;m);

for(int i = 0; i &lt; m; i ++) scanf(&#34;%d&#34;, &amp;a[i]);  //读入所有卷王的房间编号

sort(a, a + m);  //将卷王房间的编号从小到大排序

int idx = 0;  //idx作为被保护的区间数组b的下标

b[idx ++] = n - a[m - 1] + a[0] - 1;  //将首尾相连的区间加入

for(int i = 0; i &lt; m - 1; i ++) b[idx ++] = a[i + 1] - a[i] - 1;

sort(b, b + idx, greater&lt;int&gt;()); //将区间长度从大到小排序

int res = 0;

for(int i = 0; i &lt; idx; i ++){
    int k = 0;
    if(b[i] - i * 4 &gt; 0){  //完全保护好当前区间需要两天，则未被保护的区间由于两端均会被感染，故两天会损失4个宿舍
        k = b[i] - i * 4;  //经过i天后未被保护的区间在受到保护时剩下的还未变成卷王的区间长度
        if(k &gt; 1) k --;  //两天里一天只能保护一端，另一端会被感染
        res += k;
    }
    else break;
}

printf(&#34;%d\n&#34;,res);

return 0;

}

C++代码2：

代码语言：javascript

复制

#include <bits/stdc++.h>

using namespace std;
void solve(){
int n, m;

cin &gt;&gt; n &gt;&gt; m;

vector&lt;int&gt; vis;  //vis存储最先被感染的房屋编号 

for(int i = 0; i &lt; m; i ++){
    int x;
    cin &gt;&gt; x;
    vis.push_back(x);
}

sort(vis.begin(),vis.end());  //将编号从小到大排序 

priority_queue&lt;int&gt; st;  //优先队列维护当前最大长度的区间 

st.push(n - vis.back() + vis[0] - 1);  //将首尾相连的区间长度加入 

for(int i = 0; i + 1 &lt; vis.size(); i ++){
    st.push(vis[i + 1] - vis[i] - 1);  //将未感染的区间的长度加入 
}

int cnt = 0;  //存储未感染的区间长度 

for(int i = 0; i + 1 &gt; 0; i ++){  //i代表天数 
    if(!st.empty() &amp;&amp; st.top() - i * 4 &gt; 0){  //经过一天，下一个区间长度 -4 
        int k = st.top() - i * 4;  //设k为当前区间经过i天后未感染的区间长度 
        if(k &gt; 1) k --;  //对于一个端点的保护，会使另一个端点被感染(长度-1)，若区间长度仅为1，则只能保护1长度 
        cnt += k;  //累计保护到的区间长度 
        st.pop();
    }
    else break;
}

cout &lt;&lt; cnt &lt;&lt; endl;

}
int main(){
solve();

return 0;

}

G. 机器人OR寄器人

原题链接

描述

随着新学期的开始，HFCJ学长准备开发一个可以接收指令从而行动的机器人，现在硬件部分的设计已经解决，只剩下编辑指令和处理的部分。可是这种小事对他来说太简单了，用他的原话说就是："有手就行"，于是他就懒得继续做下去了。

HFCJ把这个做了一半的机器人丢给了LYS，如果他能完成剩余的工作，并且成品能够通过测试，那么这个机器人就归LYS辣。

以下是待完成的任务要求：

要求能够存储多个指令，在测试时执行对应编号的指令
添加指令：输入一个整数 P，表示添加的指令编号，然后输入两个整数 x,y，作为执行信息存储。
执行指令：输入一个整数 Q，表示执行的指令编号，然后执行该指令的信息 x_q,y_q，使得机器人从原位置 (X,Y) 移动到 (X+x_q,Y+y_q)。

LYS肥肠想要这个机器人，可是他啥也不会，现在他来找你帮忙了，你能帮帮他吗？

输入格式

第一行输入四个整数 N,M,X,Y，分别表示添加 N 个指令和 M 次执行，以及机器人的起始坐标 (X,Y)。

接下来 N 行，第 i(1\sim N) 行输入两个整数 x_i,y_i，表示 i 号指令的执行信息。

然后一行，输入 M 个整数，M_i 为执行的指令编号。

输出格式

一行，输出两个整数，表示执行完所有指令后机器人的坐标。

数据范围

1\le N,M\le 1000

-1000\le X,Y,x,y\le 1000

样例输入

代码语言：javascript

复制

样例输出

代码语言：javascript

复制

1 1

思想：

构造偏移量数组dx[N],dy[N]，存储编号的信息。
执行指令编号为q，则使X和Y加上对应编号的偏移量，即X += dx[q], Y += dy[q]。

C代码

代码语言：javascript

复制

#include <stdio.h>
int main(){
int dx[1010], dy[1010];

int n, m, X, Y;

scanf(&#34;%d %d %d %d&#34;, &amp;n, &amp;m, &amp;X, &amp;Y);

for(int i = 1; i &lt;= n; i ++) scanf(&#34;%d %d&#34;, &amp;dx[i], &amp;dy[i]);

for(int i = 1; i &lt;= m; i ++){
    int q;
    scanf(&#34;%d&#34;, &amp;q);
    X += dx[q];
    Y += dy[q];
}

printf(&#34;%d %d\n&#34;, X, Y);

return 0;

}

H. 帕秋莉GO！！！

原题链接

描述

众嗦♂粥汁，帕秋莉·诺蕾姬是《东方Project》系列弹幕游戏及其衍生作品的登场角色之一。

她是大小姐蕾米莉亚的好朋友，是个大概有100岁的魔女。她居住在幻想乡中藏书最多的大图书馆——红魔馆地下图书馆中。喜欢读书，并且会使用七曜魔法。

贤者（Philosopher）的另一个意思是哲学家，因此也可称她为七曜的哲♂学家。平常总待在大图书馆里的她，患有哮喘、贫血，体质虚弱，因此在肉搏♂战中非常劣势。

在比利王客串的兄贵本篇TalesFromTheFoxhole里，作为军官的比利对于下属的小兵在休息时间感到不满而发出的“Attention on”因为音质问题常被空耳成“帕秋莉♂GO”。

由于某种不可知的异变，姆Q穿越到了知名演员野兽♂仙贝的家中，这名不谙世事的马猴烧酒头一次从红魔馆的地下走出，没想到居然会收获颇丰，她在野兽♂仙贝的激情指导下学习到了她从未见识过的膜法，只不过由于哮喘的原因，导致她无法将这强大的咒语一次性咏唱完毕。

我们的姆Q非常困扰，她决定将这条强大的咒语告诉你，想借助科学的力量完成咏唱，你能帮帮她吗？

咒语：持续进行咏唱“114514”直到达到“1919“次。

输入格式

无。

输出格式

每行输出"114514"（不包含引号），共输出1919行。

思想：

签到题，考察循环结构。

C代码：

代码语言：javascript

复制

#include <stdio.h>
int main(){
for(int i = 1; i &lt;= 1919; i ++) printf(&#34;114514\n&#34;);

return 0;

}

题解下载

点此下载PDF版