第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛重现赛（A~K题）。
文章目录
A.大学期末现状（签到题）
题意：
给一个考试分数 n，
及格（n ≥ 60）输出 “jige,haoye!”；
否则输出 “laoshi,caicai,laolao”。
思路：
签到题，直接判断
代码：
#include <iostream>
using namespace std;
int main()
{
int n; cin >> n;
if(n >= 60) puts("jige,haoye!");
else puts("laoshi,caicai,laolao");
return 0;
}
B.G1024（签到题）
题意：
给出 n 个人 和 k 天某班车已购票数 x 和 总票数 m，
求所有人买到同一天火车票的最早天数。
思路：
签到题，直接判断。
注意一个for别break，会卡掉输入，或者开两个for循环。
代码：
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, k; cin >> n >> k;
bool f = false;
for(int i=1; i<=k; i++)
{
int x, m; cin >> x >> m;
if(m - x >= n && !f)
{
cout << i << "\n";
f = true;
}
}
if(!f) puts("G!");
return 0;
}
C.NEUQ（贪心）
题意：
给出一个仅由大写字母A~Z组成的字符串，
问最少删除几个字母能得到仅由若干个"NEUQ"组成的子串。
思路：
不知道这题算什么，贪心？
遍历字符串，严格按照"NEUQ"的顺序确定保留下来的字母，
结果即为：n - cnt × 4（cnt为已确定"NEUQ"的个数）。
代码：
#include <iostream>
#include <string>
using namespace std;
int main()
{
int n; cin >> n;
string s; cin >> s;
// 已有cnt个"NEUQ"
// 下一个需要保留的字母为op, 0,1,2,3分别对应N,E,U,Q
int cnt = 0, op = 0;
for(int i=0; i<s.size(); i++)
{
if(s[i]=='N' && op==0) op = 1;
else if(s[i]=='E' && op==1) op = 2;
else if(s[i]=='U' && op==2) op = 3;
else if(s[i]=='Q' && op==3) op = 0, cnt++;
}
cout << n - cnt*4 << "\n";
return 0;
}
D.小G的任务（暴力）
题意：
给出一个正整数 n，i 的范围为1~n ，sum为i 的各位数之和，现需求得sum的和。
思路：
直接暴力解，for遍历1 ~ n，while求得每一个 i 的各位数之和sum，再求和sum。
代码：
#include <iostream>
using namespace std;
int count(int x)
{
int cnt = 0;
while(x)
{
cnt += x%10;
x /= 10;
}
return cnt;
}
int main()
{
int n, res; cin >> n;
for(int i=1; i<=n; i++) res += count(i);
cout << res << "\n";
return 0;
}
E.nn与游戏（BFS）
题意：
给出一个n × n的地图和 m 个障碍物的坐标，再给出 t 对可控制单位和敌对单位，
障碍物、可控制单位和敌对单位均不可通过，即统一视为行走路线上的障碍物，
问：每一个可控制单位可否通过地图到达敌对单位的位置，如果可以，输出所需的最短步数；否则输出 -1。
思路：
障碍物标记为 -1，第 i 对可控制单位和敌对单位标记为 i，-1 和 i 均不可走过。
用 t 个可控制单位的坐标跑 t 遍广搜即可AC。
代码：
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m, t;
int g[N][N], st[N][N]; //g存地图，st标记某个坐标是否行走过
int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//地图中四个移动方向
struct node
{// 可控制单位的坐标(x, y)，走到对应敌对单位所需的步数
int x, y, cnt;
}ser[15];
int bfs(int x, int y)
{
// 初始化标记数组
memset(st, 0, sizeof(st));
queue <node> q;
q.push({x, y, 0});
st[x][y] = 1;// (x, y)已走过
while(q.size())
{
auto tt = q.front();
q.pop();
for(int i=0; i<4; i++)
{
int ix=tt.x+d[i][0], iy=tt.y+d[i][1];
// 出界 或 某点已经走过
if(ix<0 || ix>=n || iy<0 || iy>=n || st[ix][iy]) continue;
if(g[ix][iy] == 0)
{// 某点可以走， -1 和 1~t均不可走
q.push({ix, iy, tt.cnt+1});
st[ix][iy] = 1;
}// 找到敌对单位了
else if(g[ix][iy] == g[x][y]) return tt.cnt + 1;
}
}
return -1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i=1; i<=m; i++)
{
int x, y; cin >> x >> y;
g[x][y] = -1;//障碍物标记为-1
}
cin >> t;
for(int i=1; i<=t; i++)
{
int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
g[x1][y1] = g[x2][y2] = i;
ser[i] = {x1, y1, 0};
}
for(int i=1; i<=t; i++)
cout << bfs(ser[i].x, ser[i].y) << "\n";
return 0;
}
F.第二大数（滑动窗口）
滑动窗口这个说法是在别处看到的，利于理解解题思路，这里拿来主义一下。
题意：
给出一个正整数n 和 n 个数，求和区间 [L, R] 中的第二大值
其中 L 和 R 均为下标，且L ∈ [1, n-1]，R ∈ [L+1, n]
思路：
定义两个遍历记录当前区间的最大值(maxk)和第二大值(seck)，
两层for循环，第一层遍历L，第二层遍历R,
（1）当R = L + 1 时，区间仅有两个元素，初始maxk 和 seck
（2）当R > L + 1 时，进行最大值和第二大值维护，即更新maxk和seck
- 当新进入区间的一个数num > maxk时，maxk和seck都需更新
- 当 maxk > num > seck时，仅需更新seck
代码：
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e4 + 10;
int a[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
int res = 0;//结果
int maxk=0, seck=0;//当前第一大数maxk、第二大树seck
for(int i=1; i<n; i++)
{
for(int j=i+1; j<=n; j++)
{
if(j == i+1) maxk=max(a[i],a[j]), seck=min(a[i],a[j]);
else
{//更新当前区间的最大值和第二大值
if(a[j] > maxk) seck=maxk, maxk=a[j];
else if(a[j] > seck) seck = a[j];
}
res += seck;
}
}
cout << res << "\n";
return 0;
}
G.Num（数学+思维）
题意：
给出一个数 n ，判断其是否可以分解为 a ? b + a + b 的形式，Yes or No
(其中a>0，b>0)
思路：
a ? b + a + b = （a+1）×（b+1）- 1
可以转化为 判断是否存在 a、b 使得 n + 1 =（a+1）×（b+1）成立
- 当n + 1 为素数时，（a+1）×（b+1）= 1 ×（n+1），此时a=0，b=n，不符合题意；
- 当n + 1 不为素数时，存在a>0且b>0使得 a ? b + a + b = n，符合题意。
代码：
#include <iostream>
using namespace std;
bool check(int x)
{// x是否为素数
for(int i=2; i<=x/i; i++)
if(x % i == 0) return false;
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
if(check(n + 1)) puts("No");
else puts("Yes");
return 0;
}
H.特征值（前缀和+大数相加）
题意：
给一个贼大的数 x，其中 1 ≤ x ≤ pow(10, 500000)，求它的特征值，
即求：x + while(x) { int t = x/10; x += t; }
当然不能这么求结果，因为 x 贼大，超int 和 long long 只能用字符串输入，只是用上述代码阐述一下题意中的“特征值”。
思路：
看一个样例：1225 + 122 + 12 + 1 = 1360，观察可知：
- 个位 = 5 + 2 + 2 + 1 = 10（mod 10）= 0；
- 十位 = 2 + 2 + 1 + 个位满十进的 1 = 6
- 百位 = 2 + 1 = 3
- 千位 = 1
可得到，x 的特征值的每一位为该数位和该数位前面所有数位之和取余于十，然后满 10 向该数位的高数位进 1。
这里可以引出一个概念（瞎胡说）：数位前缀和。例：数字1225 个位的数位前缀和为1 + 2 + 2 + 5。
代码：
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string s; cin >> s;// 输入
vector <int> v; // 存每一个的数位前缀和
int sum = 0; // 记录数位前缀和
for(int i=0; i<s.size(); i++)
{
sum += s[i] - '0';
v.push_back(sum);
}
vector <int> ans;// 存每一位的结果
int t = 0; // 记录该数位是否进位
for(int i=v.size()-1; i>=0; i--)
{
ans.push_back((t + v[i]) % 10);
t = (t + v[i]) / 10;
}// 如果最后一位仍满十进位了
if(t) ans.push_back(t);
// 倒序输出结果
for(int i=ans.size()-1; i>=0; i--) cout << ans[i];
return 0;
}
I.玄神的字符串（思维）
题意：
给出一个01序列 s，序列 s 的长度为偶数，可以进行3种操作和所需花费代价，求得将 s 删空的最小代价。
- 任意删除序列中一个 0 和 1，代价为 a ；
- 任意删除序列中两个 0 或 两个 1 ，代价为 b ；
- 将任意一个 0 --> 1 或 1 --> 0，代价为 c 。
思路：
对比操作1 和 操作2 的代价大小，以确定哪种删除操作优先进行，
记录序列中 0 和 1 的个数，利用序列长度为偶数的特性，考虑01个数的所有情况。
另外：操作1 + 操作 3 = 操作 2，操作2 + 操作3 = 操作1
- 当a + c < b 时，我们可以用操作1 + 操作 3 替代 操作 2；
- 当b + c < a 时，我们可以用操作2 + 操作 3 替代 操作 1；
各种 a b 代价大小和 01 个数情况：
- 操作1 优先
cnt[0] = 5, cnt[1] = 5 , 进行 t 次操作1 后序列为空；
cnt[0] = 4, cnt[1] = 6 , 进行 t 次操作1 后cnt[0] = 0, cnt[1] = 2
cnt[0] = 2, cnt[1] = 8 , 进行 t 次操作1 后cnt[0] = 0, cnt[1] = 6
因此if(cnt[0] || cnt[1]) cost += max(cnt[0], cnt[1])/2 * min(a+c, b);
不能写成if(cnt[0] || cnt[1]) cost += max(cnt[0], cnt[1]) * min(a+c, b);- 操作1 优先
cnt[0] = 5, cnt[1] = 5 , 尽可能多地进行操作2 后序列仍不为空；
仅需进行一次操作1 或 操作2+3if(cnt[0] && cnt[1]) cost += min(a, b+c);
cnt[0] = 4, cnt[1] = 6 , 尽可能多地进行操作2 后序列为空；
cnt[0] = 2, cnt[1] = 8 , 尽可能多地进行操作2 后序列为空。
代码：
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string s; cin >> s;
int a, b, c; cin >> a >> b >> c;
int cnt[2]; // 存储序列中0 1的个数
for(int i=0; i<s.size(); i++)
{
if(s[i] == '0') cnt[0]++;
else cnt[1]++;
}
int cost = 0;// 所需代价
if(a <= b)
{// 操作1 优先
int t = min(cnt[0], cnt[1]);// 进行 t 次 操作1
cost += a * t;
cnt[0] -= t; cnt[1] -= t;
// 01序列长度为偶数，删掉 t 对 01 后仅有两种情况序列不为空：
// cnt[0] = 0 , cnt[1] = 偶 或 cnt[0] = 偶 , cnt[1] = 0
if(cnt[0] || cnt[1]) cost += max(cnt[0], cnt[1])/2 * min(a+c, b);
}
else
{// 操作2 优先
cost += (cnt[0]/2 + cnt[1]/2)* b; // 进行 cnt[0]/2 + cnt[1]/2 次操作2
cnt[0] -= cnt[0]/2*2; cnt[1] -= cnt[1]/2*2;
// 01序列长度为偶数，删掉 cnt[0]/2 对 0 和 cnt[1]/2 对 1 后仅有一种情况序列不为空：
// cnt[0] = 1 , cnt[1] = 1
if(cnt[0] && cnt[1]) cost += min(a, b+c);
}
cout << cost << "\n";
return 0;
}
J.金牌厨师（二分+差分）
一个二分题，但check()有两个条件，想不出来，没能AC。
下面是跟大佬学习的解题代码，大佬题解链接 。
题意：
给出一个数 n， 表示厨师做菜的辣度值范围为 [ 1，n ]
再给出 m 个学生可以接受的辣度值范围 [ Li，Ri ]
从 m 个学生中任选 k 个，k 个学生都能接受的辣度值范围长度为 x
问：max（k，x）最大值为多少？
思路：
尝试写思路的时候人裂开了，下面仅讲一个让我恍然大悟的点。
cnt[p[i].first + mid - 1]++; cnt[p[i].second + 1]--;
一般差分操作为cnt[p[i].first]++; cnt[p[i].second + 1]--;
而这里是cnt[p[i].first + mid - 1]++;表示所选 k 个学生在辣度值范围长度满足mid的前提下的可滑动的范围为[p[i].first+mid-1, p[i].second]。
代码：
#include <iostream>
#include <cstring>
#define pii pair <int, int>
using namespace std;
const int N = 300010;
int n, m;
pii p[N];
int cnt[N];
bool check(int mid)
{
memset(cnt, 0, sizeof(cnt));
for(int i=1; i<=m; i++)
{
int len = p[i].second - p[i].first + 1;
if(len >= x)
{
cnt[p[i].first + mid - 1]++;
cnt[p[i].second + 1]--;
}
}
for(int i=1; i<=n; i++)
{
cnt[i] += cnt[i-1];
if(cnt[i] >= mid) return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i=1; i<=m; i++)
{
int l, r; cin >> l >> r;
p[i] = {l, r};
}
int l=1, r=n;
while(l < r)
{
int mid = (l + r + 1) / 2;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << "\n";
return 0;
}
K.WireConnection（自建边的最小生成树）
题意：
给出 n 个接线器的三维空间坐标（x，y，z），用电线连接 n 个接线器。
问：所需的电线最短是多少？
思路：
自建边 + kruskal算法求最小生成树,
记得开long long。
代码：
#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
const int N = 2010;
int n;
int bcj[N];//并查集数组
struct point
{//存点的空间坐标(x, y, z)
int x, y, z;
}p[N];
struct edge
{// 存点a与点b之间的距离len
int a, b, len;
}e[N*N/2];//注意这里开N*N, N*N/2也可
int idx;//表示已建idx条边
// 边按权值从小到大排序
bool cmp(edge a, edge b) {return a.len < b.len;}
// 找根节点
int find(int x) {return x == bcj[x] ? bcj[x] : find(bcj[x]);}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i=1; i<=n; i++)
{
int x,y,z; cin>>x>>y>>z;
p[i] = {x, y, z};
}// 以上为输入
// 建边
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
e[++idx]={i, j, (int)ceil(sqrt(pow((p[i].x-p[j].x),2)*1.0+pow((p[i].y-p[j].y),2)*1.0+pow((p[i].z-p[j].z),2)*1.0))};
// 边按权值从小到大排序
sort(e+1, e+idx+1, cmp);
//初始化并查集
for(int i=1; i<=n; i++) bcj[i] = i;
// Kruskal求最小生成数
int res = 0, cnt = 0;//已接电线的总长度res, 已连接cnt条电线
for(int i=1; i<=idx; i++)
{
int a=e[i].a, b=e[i].b, len=e[i].len;
a = find(a); b = find(b);
if(a != b)
{
cnt++;
bcj[a] = b;
res += len;
}
if(cnt == n-1) break;
}
cout << res << "\n";
return 0;
}
