2022NEUQ-ACM招新赛

本蒟蒻第一次发文章，有不对的地方望大佬轻喷QWQ

1.WIN

为了实现建设世界一流大学和建设世界一流学科的目标，不少大学都用各种方式提升排名：发表论文、 申请基金、提升多样性. . . 不过看起来这些并不容易，而且 US News 和 Times 这样的机构并不一定会 公正评判你的工作。因此，一些大学更聪明——自己发布排行榜，这可以使得自己的名次间接变好。比如，通过上海某大学发布的软科排名（ARWU）作为桥梁，咖波甚至可以论证他的小汤河职业技术学院要好于清华大学：

现在，给定三个大写字母，你需要判断：

如果这三个大写字母分别为：NEU，则输出：Win

如果这三个大写字母分别为：THU，则输出：Lose

否则输出：?

输入格式:

一行三个大写字母，如题意所示

输出格式:

一行一个字符串，如题意所示

输入样例1:

NEU

输出样例1:

Win

输入样例2:

THU

输出样例2:

Lose

输入样例3:

KFC

输出样例3:

?

 这个题就比较水了，直接上AC代码

#include<iostream>
using namespace std;
int main()
{string str;while (cin >> str){if (str == "NEU") cout << "Win";else if (str == "THU") cout << "Lose";else cout << "?";}return 0;
}

2.比大小

知名数学家田所浩二先生证明了：

9>10

证明：写下两个数的十进制表示：

9​.

1​0

观察这两个数字从前到后第一个不相同的数字，由于9>1，因此9>10。

用同样的方法，我们可以很容易地证明1919>114514：

19​19..

11​4514

或者是999>99：

99.​

999​

现在，请你给田所浩二先生写一个程序，用来比较两个输入的数字。

输入格式:

第一行一个整数T(1≤T≤106) ，表示有T组数据

接下来T行，每行两个整数a,b(1≤a,b≤109)

输出格式:

输出总共T行，对于第i行：

如果"a>b"，则输出：>

如果"a=b"，则输出：=

如果"a<b"，则输出：<

输入样例:

5
9 10
114514 1919
999 99
131 131
1314 520

输出样例:

>
<
>
=
<

 把题目给的两个数据当成数组存起来那这道题就相当于是从数组的第一个字符开始一个个比较大小，而我们的cstring头文件正好有一个函数可以帮我们做这个事情，方法有了，AC代码就出来惹

#include<iostream>
#include<cstring>
using namespace std;int main()
{char a[12],b[12];int T;cin >> T;for(int i = 0;i < T;i++){cin >> a;cin >> b;if(strcmp(a,b) > 0) cout << '>' <<endl;else if(strcmp(a,b) < 0) cout << '<' <<endl;else cout << '=' <<endl;}return 0;
}

 3.矩阵乘法

Alice在学线性代数。她觉得线代的计算特别麻烦，于是就来找你，希望你可以给她写一个程序计算两个矩阵的乘积。

矩阵乘法介绍：
矩阵A是一个N行P列的矩阵。
矩阵B是一个K行M列的矩阵。
当P=K时,A和B可以相乘(仅限于AB, BA不一定可行)
假设矩阵C=AB，那么Ci,j​=∑t=1P(或K)​Ai,t​∗Bt,j​

举个例子，假设A是一个2×3的矩阵，B是一个3×2的矩阵,最终结果C是一个2×2的矩阵，如下图所示

输入格式:

输入共一行，有三个整数N,P,M(N,P,M≤100)。表示矩阵A是一个N×P的矩阵，矩阵B是一个P×M的矩阵。

接下来N行，每行P个整数，读入矩阵A。

再接下来P行，每行M个整数，读入矩阵B。

数据保证在输入输出数据可以用int类型存储。

输出格式:

输出N行M列的矩阵C。每行最后一个数后面有一个空格。

输入样例:

在这里给出一组输入。例如：

3 3 3
1 3 2
1 0 0
1 2 2
0 0 2
7 5 0
2 1 1

输出样例:

在这里给出相应的输出。例如：

25 17 4 
0 0 2 
18 12 4 

哇这个题理解为重，看懂题目问题就不大，也还比较简单，直接上代码

#include<iostream>
using namespace std;
int main()
{int a[100][100];int b[100][100];int c[100][100];int N,P,M;cin >> N >> P >> M;//读入矩阵afor(int i = 0;i<N;i++){for(int j = 0;j < P;j++){cin >> a[i][j];}}//读入矩阵bfor(int i = 0;i<P;i++){for(int j = 0;j < M;j++){cin >> b[i][j];}}//计算矩阵c，要多注意这里的条件，很容易写错for(int i = 0;i < N;i++){for(int j = 0;j < M;j++){c[i][j] = 0;for(int k = 0;k < P;k++){c[i][j] += a[i][k]*b[k][j];}}}//输出矩阵cfor(int i = 0;i < N;i++){for(int j = 0;j < M;j++){cout << c[i][j] << " ";}if(i!= N-1) cout << "\n";}return 0;
}

4.疯狂星期四

已知2022年10月11日是星期二

现在给定你一个日期，你需要计算当天是星期几。

输入格式:

一行三个整数M,D,Y，表示所求日期为：M月D日，Y年

1600≤Y≤2400，保证输入日期均为合法日期。

输出格式:

输出一个数字，表示当前是星期几。

如果星期天，则输出0。

输入样例1:

8 17 1926

输出样例1:

2

输入样例2:

2 29 1904

输出样例2:

1

 计算星期这东西用什么方法都hin麻烦(至少对我这个蒟蒻来说)，所以我们直接上蔡勒公式来便捷的计算星期

#include<iostream>
using namespace std;int main()
{int d,M,D,Y;cin >> M >> D >> Y;if(M<3){Y--;M+=12;}d = (((Y/400-2*(Y/100)+Y%100+(Y%100)/4+13*(M+1)/5+D-1)%7)+7)%7;//蔡勒公式cout << d ;return 0;
}

 5.排列

给你一个长度为n的排列p1​,p2​,p3​,...,pn​（1≤pi​≤n，且对于任意i=j，都有pi​=pj​）

再给你一个整数k，每次操作的定义如下：

选定一个下标j(1≤j≤n−k+1)，记m=max{pj​,pj+1​,...,pj+k−1​}，然后令pj​,pj+1​,...,pj+k−1​的值都等于m。

你需要使用最少的操作次数，使得p中所有元素的值都等于n。

输入格式:

第一行两个整数n,k (2≤n≤106,2≤k≤n)

接下来一行n个整数，用空格隔开，分别表示p1​,p2​,...,pn​

输出格式:

一行一个整数，表示最小的操作次数。

输入样例:

6 3
1 6 4 2 3 5

输出样例:

3

样例解释：

第一次操作选择：j=1，操作后p为：6 6 6 2 3 5

第二次操作选择：j=3，操作后p为：6 6 6 6 6 5

第三次操作选择：j=4，操作后p为：6 6 6 6 6 6

 这个题刚开始一看可能完全没有思路，但其实可以跳出数列的局限，从外面想，总共n个数，除去一个最大值还剩n-1个数，也就是我们要把n-1个数变成那个最大值，而我们每次能操作的数是k个，包括一个最大值也就是把最多k-1个数变成最大值，那答案就是（n-1）/（k-1）向上取整了

#include<iostream>
#include<cmath>
using namespace std;
int main()
{int n,k;cin >> n >> k;cout << ceil((n-1.0)/(k-1));return 0;
}

 eg.代码意外的简单呢

6.小不点

现在是跑步时间。

咖波需要依次经过地图上的五个点位才能完成任务，为了节省体力，他希望以最短的距离跑完这五个点位。

现在给出这五个点位的坐标，你需要帮咖波求出最短距离。（咖波可以从任意一个坐标开始跑步）

输入格式:

总共五行

第i行有两个整数xi​,yi​(−103≤xi​,yi​≤103)，表示第i个点位的坐标值。

数据保证不存在坐标相同的点。

输出格式:

输出一个实数，表示最短的跑步距离（保留三位小数）

输入样例:

0 0
0 2
2 2
2 0
1 1

输出样例:

6.828

样例解释：

可选择从(0,0)点开始，依次经过(0,2),(1,1),(2,0),(2,2)

此时距离为：2+sqrt(2)​+​sqrt(2)​+2=6.828，可以证明这是最短的路径。

1. 这个题的数量不多，本蒟蒻用了五个for循环过了，没什么聪明的，直接上代码吧

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;int a[2][5];double dis(int i, int j)
{return sqrt(pow((a[0][i] - a[0][j]), 2) + pow((a[1][i] - a[1][j]), 2));
}int main()
{double d, min = 99999999999;for (int i = 0; i <= 4; i++)cin >> a[0][i] >> a[1][i];for (int i = 0; i < 5; i++){for (int j = 0; j < 5; j++){if (j == i)continue;for (int k = 0; k < 5; k++){if (k == j || k == i)continue;for (int l = 0; l < 5; l++){if (l == i || l == j || l == k)continue;for (int n = 0; n < 5; n++){if (n == i || n == j || n == k || n == l)continue;d = dis(i, j) + dis(j, k) + dis(k, l) + dis(l, n);min = (d > min) ? min : d;d = 0;}}}}}cout << fixed << setprecision(3) << min;return 0;
}

7.原神生日会

注：空、荧、派蒙均为游戏原神里的人名。

有a个空（男旅行者）和b个荧（女旅行者）在会场外排队参加原神生日会。不幸的是，会场里只有N个座位，而且已经有若干个派蒙（可以是0个）已经坐在会场里面了。

• 每个男旅行者都希望坐在他边上的是女旅行者或者派蒙。
• 每个女旅行者都希望坐在她边上的是男旅行者或者派蒙。

换句话说，男旅行者不希望和其他男旅行者坐一起，女旅行者不希望和其他女旅行者坐一起。

如果会场内没有符合旅行者心意的位置，那么旅行者会选择不参加原神生日会。

作为活动组织者的你，希望能参加生日会的旅行者尽可能的多，现在给出会场内每个派蒙的位置，请你求出最多有几个旅行者会来参加生日会。

输入格式:

输入共两行。
第一行有三数，分别为N,a,b(1≤n≤2∗105,0≤a,b≤2∗105,a+b>0)。表示会场内有N个位子，会场外有a个男旅行者，有b个女旅行者。

第二行是一个由字符"."和字符"P"组成的字符串。

"."表示空位,"P"表示这个位置被派蒙占了。

输出格式:

输出一个整数，表示最多可以有几个旅行者参加生日会。

输入样例:

在这里给出一组输入。例如：

11 3 10
.P....PP.P.

输出样例:

在这里给出相应的输出。例如：

7

样例解释

我们用P来表示派蒙,A来表示男旅行者，B来表示女旅行者，最终会场内的座位情况是这样的：BPABABPPAPB

（原来你也玩原神）划掉

这个题需要给空和荧安排座位，而相同性别的旅行者是不会坐在一起的，我们先把派蒙占下的位置去掉，剩下的位置就被分成了多段，例如

 .P....PP...P.

 就被分成了一，四，三，一四段座位，分奇偶讨论一下，偶数段的座位只能是空和荧对半分了，被固定好了，而奇数段的座位是可以有一个座位灵活分配的，例如连续的三个座位可以是空，荧，空，也可以是荧，空，荧。设总共为n个座位，有(n-1)/2个座位分别给空和荧以及一个自由分配的座位，那么我们就统计一下座位中的固定座位和自由座位，其中把自由座位给固定座位不够的旅行者，如果连自由座位都不够那么就不能使所有的旅行者坐下了

代码如下

#include <iostream>
#include <cstring>
using namespace std;int main()
{int N, a, b, n = 0, sum = 0, free = 0, m = 0;char ch[200001], c;cin >> N >> a >> b;cin >> ch;for (int i = 0; c = ch[i]; i++){if (c == '.'){n++;}else if (c == 'P' && n != 0){free += n % 2;sum += n / 2;n = 0;}}if (n != 0){free += n % 2;sum += n / 2;n = 0;}m = (((a - sum) > 0) ? (a - sum) : 0) + (((b - sum) > 0) ? (b - sum) : 0);if (free >= m)cout << a + b;elsecout << a + b - m + free;return 0;
}

 8.漏子文

有意避免使用某个或某几个特定字母的写成的文章称漏字文（英语lipogram，希腊语lipagrammatos，意为“失踪的字母”），漏字文可能在写作或文字游戏中出现。公元前5世纪希腊诗人里斐奥多鲁斯（Tryphiodorus）写的24卷史诗中，每一卷都省略希腊字母中的一个不同字母。

现在给你一段仅由空格和小写字母组成的字符串，请你找出其中最长的一段连续的漏字文，并输出漏字文的长度（即该段文字中字母的个数）。

输入格式:

输入共两行。
第一行一个数N(1≤N≤105),表示有N个由小写字母组成的单词。
第二行是一个字符串，有N个长度不超过10的单词，每个单词间用一个空格隔开。

输出格式:

一个整数，表示漏字文的长度。

输入样例:

在这里给出一组输入。例如：

9
the quick brown fox jumps over the lazy dog

输出样例:

在这里给出相应的输出。例如：

32

样例解释

“the quick brown fox jumps over the lazy dog”包含了所有的字母。
其中最长的漏字文是“the quick brown fox jumps over the lazy”，长度是32（即里面有32个字母）。这段文字没有字母d和g，符合漏字文的条件。

这个题漏了点条件，最长的漏字文应该是连续的，不是整个输入去掉漏字的单词，比如

the quick brown fox jumps over the lazy

 这段话漏掉t答案应该是22（quick brown fox jumps over）而不是26（quick brown fox jumps over lazy）

那么基本思路就是从a到z遍历然后一个个漏掉取最大值，代码实现如下

#include <iostream>
#include <cstring>
using namespace std;struct o
{int len;char a[15];
};bool is(o ob, char z)
{int n = 0;for (int i = 0; i <= ob.len-1; i++){if (ob.a[i] == z)n++;}return n;
}int main()
{int n, ma = 0, le = 0;o arr[100000];cin >> n;for (int i = 0; i <= n-1; i++){cin >> arr[i].a;arr[i].len = strlen(arr[i].a);}for (int i = 'a'; i <= 'z'; i++){for (int j = 0; j <= n-1; j++){if (is(arr[j], i)){ma = (ma > le) ? ma : le;le = 0;continue;}elsele += arr[j].len;}ma = (ma > le) ? ma : le;le = 0;}cout << ma;
}