20250822 组题总结
A - a
在一个8×8的点阵网格中，某个小写拉丁字母组成的单词被完整地垂直书写在单一列内，从上到下连续排列（无间断）。
由题目可得，字母都在同一列，并且不会间断，所以不用什么复杂的判断，遇到字母直接加进字符串就行了。
#include<bits/stdc++.h>
using namespace std;
int main(){int t;cin>>t;while(t--){string s="";for(int i=1;i<=64;i++){//八八六十四char x;cin>>x;if(x!='.'){//如果不是字符s+=x;}}cout<<s<<endl;}return 0;
}
B - b
一天，弗拉德突然好奇自己在地铁扶梯上能和哪些人交谈。扶梯上有n名乘客，共有m级台阶，编号从1到m，第i级台阶的高度为i*k厘米。
弗拉德的身高是H厘米。当两个人站在不同台阶上时，若他们的身高差等于所在台阶的高度差，就能进行对话。例如，身高170厘米和180厘米的两个人，当m=10，k=5时，可以分别站在第5和第7级台阶上（高度差为10厘米，等于身高差）。
现在给定包含n个身高的数组h，其中h[i]表示第i个人的身高。弗拉德想知道自己能和其中多少人分别进行对话。
这题暴力就能过，直接看每个人和弗拉德的身高差是否符合要求。
#include<bits/stdc++.h>
using namespace std;
int a[55];
int main(){int t;cin>>t;while(t--){int n,m,k,h,ans=0;cin>>n>>m>>k>>h;for(int i=1;i<=n;i++){cin>>a[i];if(abs(h-a[i])%k==0&&abs(h-a[i])/k+1<=m&&a[i]!=h){ans++;}}cout<<ans<<endl;}return 0;
}
C - c
给定一个长度为 n 的整数数组 a。你可以对该数组执行以下操作：
交换任意两个元素 a[i] 和 a[j]，需满足 i≠j 且 a[i] 与 a[j] 的奇偶性相同（同为奇数或同为偶数）。
问题要求判断：通过执行任意次数（包括零次）的上述操作，能否将数组按非递减顺序排序。
因为只有奇偶性相同的两个数才能交换，所以如果一个数排完序后的预期位置的值与这个数的奇偶性不相同，最终答案就是不能。
我们只要看一下每个数排完序后的预期位置的值与这个数的奇偶性是否相同就能够得出答案。
#include<bits/stdc++.h>
using namespace std;
int a[200005],b[200005];
int main(){int t;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i];//用于存储排完序后的预期位置}sort(b+1,b+1+n);bool cc=0;for(int i=1;i<=n;i++){if(a[i]%2!=b[i]%2){//奇偶性相同吗cc=1;break;}}if(!cc){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0;
}
D - d
Bmail公司最初仅配备了一台路由器。随着业务发展，公司逐步新增了多台路由器。每当引入新路由器时，都会将其连接到现有的某台设备上。题目给出数组 pip_ipi（其中pip_ipi < i），表示第i台路由器连接的目标路由器编号。
现公司共拥有n台路由器。请输出从第1台到第n台路由器的完整路径序列。
这题考验你对树的理解，因为每个节点的父亲是唯一的，所以只要从n下标开始while，每次找到父亲，直到1号点。
#include<bits/stdc++.h>
using namespace std;
int a[200005],n;
stack<int> s;
int main(){cin>>n;for(int i=2;i<=n;i++){//i从2开始的cin>>a[i];//a[i]代表i节点的父亲是a[i]}int x=n;//从n开始找父亲while(x!=1){s.push(x);//注意，不能直接输出，要用栈存着，我们是从1号节点出发的x=a[x];}s.push(1);//别漏了一号点while(!s.empty()){cout<<s.top()<<" ";//每次输出栈顶s.pop();}return 0;
}
E - e
波利卡普在圣诞树下发现了一个包含n个元素的数组a，以及游戏规则：
- 首先选择任意下标i（1 ≤ i ≤ n）作为起点
- 将棋子放在位置i（对应数值a[i]）
- 当i ≤ n时：
- 将a[i]计入得分
- 向右移动a[i]个位置（即i = i + a[i]）
- 当i > n时游戏结束
请帮助波利卡普计算，当选择最优起始下标时能获得的最大得分。
很显然是动态规划，但是要怎么设计呢？由于有多组数据，所以我们要时间复杂度尽量小的的方案。
我们设dp[i]表示走到i下标最多能得到dp[i]得分，那么我们可以枚举每一个点，看他能走到哪去，并更新那个点。
进行状态转移时我们暂时不加上该点的得分，最后找最大值时再加上。
#include<bits/stdc++.h>
using namespace std;
int a[200005],dp[200005];
int main(){int t;scanf("%d",&t);while(t--){memset(dp,0,sizeof dp);int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){if(i+a[i]<=n){//如果没有越界dp[i+a[i]]=max(dp[i+a[i]],dp[i]+a[i]);//目前累计积分加上这一格的得分}}int mx=0;for(int i=1;i<=n;i++){mx=max(mx,dp[i]+a[i]);//加上该格的得分}printf("%d\n",mx);}return 0;
}