绍大2022级ACM集训队新生选拔赛题解（更新中）
A.Honest
大致题意
在一个 n*n 的矩阵统计 “honest” 这个单词的个数。
基本思路
本题是签到题，只要用二维数组读入字符矩阵遍历统计即可。
代码
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
bool fg=0;
while(cin>>n) {
if (n==0) break;
if (fg) cout<<endl;
fg=1;//输出换行
char a[30][30];//字符数组
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) cin>>a[i][j];
}
int ans=0;
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
string s="";
string s1="";
for (int k=0; k<6; k++) {
if (j+k<=n) s=s+a[i][j+k]; //横向统计，超出矩阵范围不统计。
if (i+k<=n) s1=s1+a[i+k][j]; //纵向统计。
}
if (s=="honest") ans++;
if (s1=="honest") ans++;
}
}
cout<<ans;
}
return 0;
}
建议
尽早解决，避免罚时过高。
B.最短购物距离
大致题意
给定 n 个商店的坐标，选择一个商店作为起点，每次到达一个商店并放回，要求走完所有商店，求最少的总路程。
基本思路
由于 n 的数据范围非常小(只有\(100\))，所以只需要枚举每个商店作为起点，计算总路程并统计最短路程输出即可。
代码
#include<bits/stdc++.h>
using namespace std;
int main() {
int T;
cin>>T;
while(T--) {
int a[200]={0};
int n;
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n);
int ans=0x3f3f3f3f; // 开始假设最短路程为无穷大(超过题目最大路程的数即可视为无穷大)
for (int i=1;i<=n;i++){
int now=0;
for (int j=1;j<=n;j++){//枚举商店
now=now+abs(a[j]-a[i])*2;//计算路程之和，到达后目的地后要回到起点，所以要乘2
}
ans=min(ans,now);//取最短路程
}
cout<<ans<<endl;
}
return 0;
}
建议
题目数据范围过小时，可以选择用暴力枚举解决问题，以减少思考时间，降低罚时。
C.多少签多少钱
大致题意
有 n 种签子，给定每种签子的数量，价格和折扣，计算签子总数和总价格。
基本思路
直接求和即可，由于折扣会导致价格出现小数，所以要用 \(double\) 类型的变量表示价格。
代码
#include<bits/stdc++.h>
using namespace std;
int main() {
int T;
bool fg=0;
cin>>T;
int cnt=0;
while(T--) {
if (fg) cout<<endl;
fg=1;
cnt++;//记录case
int n;
cin>>n;
int ansn=0;//记录签子总数
double ans=0;//记录总价格
for (int i=1;i<=n;i++){
int x;
double y,z;
cin>>x>>y>>z;
ansn+=x;
ans=ans+(x*y*(z/10));
}
printf("Case #%d:%d %.1lf",cnt,ansn,ans);//价格保留1位小数
}
return 0;
}
建议
写程序前，应提前根据题目描述想好要用哪些类型的变量。
D.小学数学
大致题意
给定一个 n ,判断 n 的立方能否等于 n 个连续奇数之和，找到并输出这些连续奇数。
基本思路
这道题是一道找规律的题，从样例中不难看出， 1 的立方由 1 个奇数组成，2 的立方由俩个奇数组成，3 的立方由三个奇数组成，所以不难推出 n 的立方就是第 (1+2+...+n-1+1)个奇数后面连续的 n 个奇数之和。
当然，题目中还有 "-1" （即不存在）的情况1，事实上，当 n 为正数时都满足以上情况，只有 n<=0 时不存在。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int T;
bool fg=0;
cin>>T;
while(T--) {
if (fg) cout<<endl;
fg=1;
ll n;
cin>>n;
if (n<=0) {
cout<<"-1";
continue;
}//n<=0时不存在要求情况
ll now=(n-1+1)*(n-1)/2;
now++;
now=now*2-1; //计算连续奇数的第一个数
for (int i=1;i<=n;i++){
if (i!=1) cout<<" "; //末尾无空格
cout<<now;
now=now+2;
}
}
return 0;
}
建议
遇到和数学有关的题，可以尝试一下能否从样例或者自己拟造的例子中找出规律。（事实上，很多类型的题都能够找规律，这种题不涉及算法，只考察思维）
E.游戏
大致题意
俩个人玩游戏，有一堆总数为 n 的柚子，双方轮流进行操作（俩人都采用最优策略），每次操作可以拿走 一个质数的幂次个数 的柚子（即 \(p^k\) \(p为质数\)）, 最后拿走柚子的人获胜。给定一个 n ，询问先手操作的Wei能否获胜。
基本思路
这是一道博弈类型的题目，属于博弈题中最简单的一类。
对于此类追求胜负的博弈题，我们首先明确要一个概念，这个概念名为 必胜态 。
从字面上理解，必胜态就是必胜的状态，例如题中 n=1 或 n=2 时，Wei 都能直接把柚子取完，即 Wei 必胜，则我们称 n=1和 n=2 的状态为必胜态。
这样，其他不是必胜态的状态，就变成了必输的局面，称之为 必败态。
以上的所有概念与结论，都有一个很重要的前提，即 俩人都采用最优策略 ，因为俩人都想方设法地赢，所以不会有哪一次操作出现失误，这样就不会出现 可能输或可能赢 的情况，即所有状态不是必胜就是必败。
在了解了博弈的基础知识后，回来看这道题，我们能发现：当 n=1-5 时，都为必胜态，6 为第一个必败态。
我们先把所有的质数和他们的幂筛选出来，因为这些数明显是必胜态。
筛选完之后，20 以内的数还剩下 : 6 10 12 14 15 18
由于 6 已经确定为必败态，所以当哪一个人开始操作时如果还剩 6 个柚子，他一定会输。
所以当 n=10 时，如果 Wei 拿走 4 个柚子，使柚子总数变成 6 ，那么就是 Peng 陷入了必败态，Wei 必胜，所以 10 也是必胜态。
当 n=12 时，Wei 只能拿走 2 个柚子，不然剩下的柚子都会被 Peng 一次性拿完，这样使 Peng 开始操作时还剩下 10 个柚子，此时 Peng 进入了必胜态，也就是 Wei 陷入了必败态，所以 12 也是 必败态。
接下来，由于 14，15 这俩个数Wei 都能使他们变成 12 ，即让 Peng 陷入必败态，所以 14 15 也是必胜态，而对于 n=18 的情况，不管 Wei 如何取， Peng 都能让他 变为 12 或者 6 ，即让 Wei 陷入必败态，所以 18 也是必败态。
至此，我们已经能猜到规律：只要 n 为 6 的倍数，Wei 就一定陷入必败态，反之皆为必胜态。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll n;
bool fg=0;
while(cin>>n){
if (fg) cout<<endl;
fg=1;
if (n%6==0) {
cout<<"No";
}else cout<<"Yes";
}
return 0;
}
建议
在学习完c++基础语法后，可以尝试学习一下各种算法，扩充自己的算法知识库，这样更有利于面对比赛时的各种情况。
F.包子
大致题意
给定一个范围 w 和一个整数 n 以及 n 个 整数，要求找出一共有多少个整数 k （\(0\leq k \leq w\)），使得 k 在加上这 n 个整数时始终保持（\(0\leq k \leq w\)）。
基本思路
由于本题的 w 的数据范围为 （\(1 \leq w \leq 10^9\)），且有多组数据，所以不能采用暴力枚举的方法 (从 1 枚举到 w) 来求 k 的个数。
我们首先对每个整数 a[i] 求他的前缀和 (即\(\sum_{j = 1}^{i} a[j]\)) ，然后找出前缀和中的最大值和最小值。
如果前缀和的最大值或最小值的绝对值超过了 w ，则当 k 加到 最大值或最小值位置 时，一定会出现 k <0 或 k>w 的情况，则该 k 不满足要求。
之后的情况，我们用mx表示前缀和最大值，用mn表示最小值，分三种情况讨论:
1 ： 当 \(mn\geq 0\) 时，若用 \((l，r)\) 表示 k 的答案区间，则 \(l\) 可以取到 0 ，而 \(r\) 不能超过 \(w-mx\) ，所以一共有 \(r-l+1\) 个 k 可取。
2：当 \(mx\leq0\) 时， \(r\) 可以取到 w ，但 \(l\) 不能小于 (|\(mn\)|) 所以 \(l=|mn|\) , 一共有 \(r-l+1\) 个 k 可取。
3：当 \(mx\geq 0\) 但 \(mn\leq0\) 时，\(l\) 不能小于 (|\(mn\)|) 而 \(r\) 不能超过 \(w-mx\) ,所以 \(l=|mn|\) ， \(r=w-mx\) ，
一共有 \(r-l+1\) 个 k 可取。
至此，讨论结束。
代码
#include<bits/stdc++.h>
#include<map>
using namespace std;
typedef long long ll;
const int N=1005;
const ll INF=1e9+7;
int main() {
bool fg=0;
int n;
ll w;
while(cin>>n>>w) {
if (fg) cout<<endl;
fg=1;
ll a[1005]={0};
ll mx=-INF,mn=INF;//最大值和最小值
ll pre=0;
for (int i=1;i<=n;i++){
ll x;
cin>>x;
pre=pre+x;
mx=max(pre,mx);
mn=min(mn,pre);
}
if (abs(mn)>w || abs(mx)>w) {
cout<<"0";
}else {
ll l=0,r=w;
if (mn<0) {
if (mx<0) {
l=abs(mn);
}else {
l=abs(mn);
r=w-abs(mx);
}
}else {
r=w-mx;
}
cout<<r-l+1;
}
}
return 0;
}
建议
根据题目的数据范围，选择合适的做法。
标签：绍大,int,题解,Wei,mn,ACM,必胜,fg,必败 From： https://www.cnblogs.com/you-mu-jv-ruo/p/16821543.html