我是靠谱客的博主 害羞红牛，最近开发中收集的这篇文章主要介绍第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 补题题解C题 NEUQF题 第二大数E题 nn与游戏H题 特征值I题 最大公约数J题 玄神的字符串K题 金牌厨师L题 WireConnectionM题 NuclearReactor总结，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
目录
- C题 NEUQ
- F题 第二大数
- E题 nn与游戏
- H题 特征值
- I题 最大公约数
- J题 玄神的字符串
- K题 金牌厨师
- L题 WireConnection
- M题 NuclearReactor
- 总结
记录第一次比赛的题解
这次比赛让自己认识到了差距，一味的刷网课不太行，以后也要多打比赛，多锻炼锻炼思维
比赛传送门
C题 NEUQ
原题传送门
这是一道暴力就能过的题，自己想的方法会段错误（以后记得考虑小数组会不会遇到数组越界访问的情况）
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int main()
{
int n = 0;
char s[N] = {0};
int res = 0;
char z[4] = {'N', 'E', 'U', 'Q'};
int e = 0;
int t = 0;
cin>>n;
cin>>s;
for(int i = 0; i < n; i ++ ){
if(s[i] != 'N'){
res ++ ;
}
else{
t = 1;
for(int j = 1; j < 4; ){
if(s[i + t] != z[j]){
res ++ ;
}
else{
j ++ ;
}
t ++ ;
if(i + t == n && j < 3){
e = j;
break;
}
}
i = i + t - 1;
}
}
cout<<res + e<<endl;
return 0;
}
F题 第二大数
原题传送门
这也是一道暴力可以过的题，自己想的哪个思路在内部if.else过多会超时
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
typedef long long ll;
int n;
int a[N];
ll ans;
int main()
{
cin>>n;
for(int i = 1; i <= n; i ++ ) cin>>a[i];
for(int i = 1; i <= n; i ++ ){
int mx = max(a[i], a[i + 1]);
int x = min(a[i], a[i + 1]);
ans += x;
for(int j = i + 2; j <= n; j ++ ){
if(a[j] < x){
}
else if(a[j] > mx){
x = mx;
mx = a[j];
}
else{
x = a[j];
}
ans += x;
}
}
cout<<ans<<endl;
return 0;
}
E题 nn与游戏
原题传送门
solution:考察广度优先搜索算法，题意给出了一个大小为 且有障碍的矩阵，然后给出了m对起点
与终点，利用队列这种数据结构对每一个起点进行广度优先搜索即可得到起点到终点的最短距离，算法
流程如下：
①将起点加入队列。
②弹出队首元素u。
③将u上下左右四个方向且满足条件（不是障碍，不是其他的起点或终点，之前没有访问过）的点加入队
列，并更新距离。
④如果队列为空则退出，否则返回②
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m, t;
int Map[N][N];//记录障碍
int w[N][N];//记录步数
bool z[N][N];//记录这个格子是否已经被走过
int a[15], b[15];//记录己方单位
int c[15], d[15];//记录敌方单位
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main()
{
cin>>n>>m;
for(int i = 1; i <= m; i ++ ){
int a, b;
cin>>a>>b;
Map[a][b] = -1;
}
cin>>t;
for(int i = 1; i <= t; i ++ ){
cin>>a[i]>>b[i]>>c[i]>>d[i];
Map[a[i]][b[i]] = -1;
Map[c[i]][d[i]] = -1;
}
for(int i = 1; i <= t; i ++ ){
/*初始化地图，清理以前留下的*/
for(int j = 0; j < n; j ++ ){
for(int k = 0; k < n; k ++ ){
w[j][k] = 0;//清理步数
z[j][k] = 0;//清理脚印
}
}
queue<pair<int, int>>Q;
Q.push({a[i], b[i]});
int q = -1;//记录是否已经走完
while(Q.size()){
auto [x, y] = Q.front();
Q.pop();
for(int j = 0; j < 4; j ++ ){
int xx = x + dx[j];
int yy = y + dy[j];
if(xx == c[i] && yy == d[i]) q = w[x][y] + 1;//如果到达目标位置，就记录步数，然后退出
if(z[xx][yy] || xx == n || yy == n ||xx > n || yy > n || xx < 0 || yy < 0 || Map[xx][yy] == -1) continue;//如果这个格子不能走或者已出界，直接进入下次循环
w[xx][yy] = w[x][y] + 1;//记录到达这个格子的步数
Q.push({xx, yy});//新节点入队
z[xx][yy] = 1;//标记这个格子已经被走过
}
if(q != -1) break;
}
cout<<q<<endl;
}
return 0;
}
H题 特征值
原题传送门
官方题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
string s1;//记录输入的字符串
string s2;//记录输出的字符串
ll a;//记录每一位之和
int main()
{
cin>>s1;
int len = s1.length();
for(int i = 0; i < len; i ++ ){
a += (s1[i] - '0');
}
int c = 0;//记录进位
for(int i = len - 1; ;i -- ){
c += a;
s2.push_back('0' + c % 10);//将计算出的结果从后假如字符串中，这样最终的结果字符串s2的高位就是实际数的低位
c /= 10;
if(i >= 0)//当a应该减去的数字还没有达到字符串长度，就继续减去
a -= (s1[i] - '0');
if(i <= 0 && !c ) break;
}
//逆序
reverse(s2.begin(), s2.end());
cout<<s2;
return 0;
}
I题 最大公约数
原题传送门
官方题解：
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n, sum;
int a[N];
int s;
int main()
{
cin>>n;
for(int i = 0; i < n; i ++ ){
cin>>a[i];
sum += a[i];
}
for(int i = 1; i * i <= sum; i ++ ){
if(sum % i == 0){
if(i * i == sum) s += 1;
else s += 2;
}
}
cout<<s<<endl;
return 0;
}
J题 玄神的字符串
原题传送门
官方题解：
#include<bits/stdc++.h>
using namespace std;
const int N = 50010;
int sum0, sum1;
string s;
int ans;
int a, b, c;
int main()
{
cin>>s;
cin>>a>>b>>c;
int n = s.length();
for(int i = 0; i < s.length(); i ++ ){
if(s[i] == '0') sum0 ++ ;
else sum1 ++ ;
}
if(a >= b + c){
ans = (sum0 % 2) * c + n / 2 * b;
}
else if(b >= a + c){
ans = (n / 2 - min(sum0, sum1)) * c + n / 2 * a;
}
else if(b > a){
ans = min(sum0, sum1) * a + (n / 2 - min(sum1, sum0)) * b;
}
else{
ans = (sum1 / 2 + sum0 / 2) * b;
if(sum1 & 1){
ans += a;
}
}
cout<<ans<<endl;
return 0;
}
K题 金牌厨师
原题传送门
官方题解：
#include<bits/stdc++.h>
using namespace std;
const int N = 3000010;
int n, m;
vector<int>Q[N];
int r[N];//r[i]记录符合条件的区间右端点为i的个数
bool check(int mid){//mid是要找的区间长度 ,这个函数的作用是检查是否存在区间长度大于mid且区间数量也大于mid的区间，如果存在返回1，否则返回0
int cnt = 0;//记录符合条件的区间个数
for(int i = 1; i <= n; i ++ ){
r[i] = 0;
}
for(int i = 1; i + mid - 1 <= n; i ++ ){
for(auto j : Q[i]){//遍历区间左端点为i的所有区间
if(j >= i + mid - 1){//如果这个区间长度为大于所求的区间，即符合条件
r[j] ++ ;//区间右端是j的数量++
cnt ++ ;//记录区间数量
}
}
if(cnt >= mid) return 1;//如果区间数量cnt已经大于mid，就代表答案应该大于mid，返回1使答案右移
cnt -= r[i + mid - 1];//将区间长度刚好是mid的减去，这样剩下的cnt记录的就是大于mid的区间数量
}
return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i = 1; i <= m; i ++ ){
int a, b;
cin>>a>>b;
Q[a].push_back(b); //队列下标为区间左端点，值为区间右端点
}
int l = 1, r = n;
while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;//找到符合条件的mid
else r = mid - 1;
}
cout<<l<<endl;
return 0;
}
L题 WireConnection
原题传送门
官方题解：
借一位大佬的理解：并查集+结构体排序也可以解这道题
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2010;
struct Node{
int a, b, w;
bool operator < (Node x) const {//结构体排序
return w < x.w;
}
}J[N * N];
int ans;
int n, cnt;
int h[N];
double x[N], y[N], z[N];
int w[N];
int find(int a){
if(a != h[a]) h[a] = find(h[a]);
return h[a];
}
int get(int a, int b){
double l = sqrt(pow(x[a] - x[b], 2) + pow(y[a] - y[b], 2) + pow(z[a] - z[b], 2));
return ceil(l);
}
signed main()
{
cin>>n;
for(int i = 1; i <= n; i ++ ){
cin>>x[i]>>y[i]>>z[i];
}
for(int i = 1; i < n; i ++ ){
for(int j = i + 1; j <= n; j ++ ){
J[ ++ cnt] = {i, j, get(i, j)};//计算出每两个点之间的距离
}
}
sort(J + 1, J + 1 + cnt);//对cnt个储存了节点之间链接关系的结构体距离排序
for(int i = 1; i <= n; i ++ ){
h[i] = i;
}
for(int i = 1; i <= cnt; i ++ ){
int a = J[i].a, b = J[i].b, w = J[i].w;
a = find(a);
b = find(b);
if(a != b) h[a] = b, ans += w;//利用并查集将不在一个集合内的两个节点加入到一个集合并累计记录距离
}
cout<<ans<<endl;
return 0;
}
M题 NuclearReactor
原题传送门
难度太大，目前水平先不管了，先把官方题解和标程挂在这里
官方题解：
标程：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <iomanip>
using namespace std;
const int MAXX = 6 + 2;
const int MAXY = 9 + 2;
const int MAXTemp = 10000;
const int MAXTime = 20000;
const int MAXVentTemp = 1000;
const int dx[4] {0, -1, 0, 1};
const int dy[4] {-1, 0, 1, 0};
char map[MAXX][MAXY];
long long mapRodHeat[MAXX][MAXY];
double mapVentHeat[MAXX][MAXY];
long long mapVentANum[MAXX][MAXY];
long long ventBNum, ventbNum;
long long mapVentCNum[MAXX][MAXY];
int main() {
memset(map, 0, sizeof(map));
for (int i = 1; i < MAXX - 1; ++i) {
for (int j = 1; j < MAXY - 1; ++j) {
map[i][j] = getchar();
}
getchar();
}
long long answ = 0;
memset(mapRodHeat, 0, sizeof(mapRodHeat));
memset(mapVentANum, 0, sizeof(mapVentANum));
memset(mapVentCNum, 0, sizeof(mapVentCNum));
for (int i = 1; i < MAXX - 1; ++i) {
for (int j = 1; j < MAXY - 1; ++j) {
if (map[i][j] == 'U' || map[i][j] == 'D' || map[i][j] == 'Q') {
int n = 0, m = 1, eta = 1;
if (map[i][j] == 'D') {
m = 2;
eta = 2;
} else if (map[i][j] == 'Q') {
m = 4;
eta = 3;
}
for (int di = 0; di < 4; ++di) {
if (map[i + dx[di]][j + dy[di]] == 'U') {
n += 1;
} else if (map[i + dx[di]][j + dy[di]] == 'D') {
n += 2;
} else if (map[i + dx[di]][j + dy[di]] == 'Q') {
n += 4;
} else if (map[i + dx[di]][j + dy[di]] == 'N') {
n += m;
}
}
answ += 5 * m * (eta + n);
mapRodHeat[i][j] = 2 * m * (eta + n) * (eta + n + 1);
} else if (map[i][j] == 'A' || map[i][j] == 'a') {
for (int di = 0; di < 4; ++di) {
++mapVentANum[i + dx[di]][j + dy[di]];
}
} else if (map[i][j] == 'B') {
++ventBNum;
} else if (map[i][j] == 'b') {
++ventbNum;
} else if (map[i][j] == 'C') {
for (int di = 0; di < 4; ++di) {
++mapVentCNum[i + dx[di]][j + dy[di]];
}
}
}
}
long long ansW = 0;
double ansQ = 0;
bool isBoom = 0;
memset(mapVentHeat, 0, sizeof(mapVentHeat));
for (int k = 0; k < MAXTime; ++k) {
ansW += answ;
ansQ = max((double)0, ansQ - (5 * ventbNum));
double heatToVentB = ansQ;
if (ventBNum != 0)
ansQ = 0;
for (int i = 1; i < MAXX - 1; ++i) {
for (int j = 1; j < MAXY - 1; ++j) {
if (mapRodHeat[i][j] != 0 && mapVentANum[i][j] == 0) {
ansQ += mapRodHeat[i][j];
} else if (mapVentHeat[i][j] > MAXVentTemp)
continue;
else if (map[i][j] == 'A') {
for (int di = 0; di < 4; ++di) {
if (mapRodHeat[i + dx[di]][j + dy[di]] != 0) {
mapVentHeat[i][j] += min((double)12, (double)mapRodHeat[i + dx[di]][j + dy[di]] / mapVentANum[i + dx[di]][j + dy[di]]);
ansQ += max((double)0, (double)mapRodHeat[i + dx[di]][j + dy[di]] / mapVentANum[i + dx[di]][j + dy[di]] - 12);
}
}
} else if (map[i][j] == 'a') {
for (int di = 0; di < 4; ++di) {
if (mapRodHeat[i + dx[di]][j + dy[di]] != 0) {
mapVentHeat[i][j] += min((double)6, (double)mapRodHeat[i + dx[di]][j + dy[di]] / mapVentANum[i + dx[di]][j + dy[di]]);
ansQ += max((double)0, (double)mapRodHeat[i + dx[di]][j + dy[di]] / mapVentANum[i + dx[di]][j + dy[di]] - 6);
}
}
} else if (map[i][j] == 'B') {
mapVentHeat[i][j] += min((double)32, (double)heatToVentB / ventBNum);
ansQ += max((double)0, (double)heatToVentB / ventBNum - 32);
}
}
}
for (int i = 1; i < MAXX - 1; ++i) {
for (int j = 1; j < MAXY - 1; ++j) {
if (mapVentHeat[i][j] > MAXVentTemp + 10000)
continue;
else if (map[i][j] == 'A') {
mapVentHeat[i][j] = max((double)0, mapVentHeat[i][j] - 12 - 4 * mapVentCNum[i][j]);
if (mapVentHeat[i][j] > MAXVentTemp) {
mapVentHeat[i][j] += 10000;
for (int di = 0; di < 4; ++di) {
--mapVentANum[i + dx[di]][j + dy[di]];
}
}
} else if (map[i][j] == 'a') {
mapVentHeat[i][j] = max((double)0, mapVentHeat[i][j] - 6 - 4 * mapVentCNum[i][j]);
if (mapVentHeat[i][j] > MAXVentTemp) {
mapVentHeat[i][j] += 10000;
for (int di = 0; di < 4; ++di) {
--mapVentANum[i + dx[di]][j + dy[di]];
}
}
} else if (map[i][j] == 'B') {
mapVentHeat[i][j] = max((double)0, mapVentHeat[i][j] - 20 - 4 * mapVentCNum[i][j]);
if (mapVentHeat[i][j] > MAXVentTemp) {
mapVentHeat[i][j] += 10000;
--ventBNum;
}
}
}
}
if (ansQ > MAXTemp) {
isBoom = 1;
break;
}
}
if (isBoom)
cout << "Boom!";
else
printf("%.2lf", ansQ);
cout << endl << ansW << endl;
return 0;
}
总结
这次比赛整理完之后觉得难度不是特别大，至少临场写出五题是不应该的，后面有几道题其实可以做，只是当时摆烂心态没有看后面的题，以后要克制自己，至少每道题的题面都应该看一看。其次就是，这次比赛反映出我比赛经历太少，思维锻炼不够，可笑我前几天还跑去找教练说比赛太多，小丑竟是我自己，以后要多打CF和牛客比赛，和网课一起双管齐下。
一次比赛失败不算什么，被打击了又不是第一二三四五六七八九…次了，既然选择热爱就要坚持到底，来冲冲冲！
最后
以上就是害羞红牛为你收集整理的第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 补题题解C题 NEUQF题 第二大数E题 nn与游戏H题 特征值I题 最大公约数J题 玄神的字符串K题 金牌厨师L题 WireConnectionM题 NuclearReactor总结的全部内容，希望文章能够帮你解决第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 补题题解C题 NEUQF题 第二大数E题 nn与游戏H题 特征值I题 最大公约数J题 玄神的字符串K题 金牌厨师L题 WireConnectionM题 NuclearReactor总结所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复