2022长沙学院ACM实验室选拔赛-题解
2022长沙学院ACM实验室选拔赛-题解
A.几十里水路到湘江
模拟输出题，可以看到题目给定的约束有一片图像的长宽，河流宽度。
注意到
1.相邻的两片图像会有公共的一行。 2.如果河流宽度超出了图像，那么会适当缩短河流。
实现有很多种方法，可以逐字符输出
#include <bits/stdc++.h>
using namespace std;
char ans[110][110];
int main()
{
int n, m, p, q;
cin >> n >> m >> p >> q;
int dir = 1, y = 1;
for (int i = 1; i <= n * q; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
if (j >= y && j < y + p) cout << '@';
else cout << '#';
}
puts("");
if (i%n == 0) i ++, dir = -dir;
y += dir;
}
return 0;
} 也可以用存每一行，用
存整张图。在蓝桥杯基础技能树题解（一）中，提到过用
的方式实现类似二维数组的字符存储。也可以通过样例观察到，令两片图像公共边为第k条边，那么第
条和第
条是一样的。这时候再循环输出就简单多了。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,p,q,k=0;
cin>>n>>m>>p>>q;
vector<string> v;
for(int i=0;i<n;i++)
{
int cnt=0;
string s="";
for(int j=0;j<i;j++)
if(cnt<m)
cnt++,s+='#';
for(int j=0;j<p;j++)
if(cnt<m)
cnt++,s+='@';
for(int j=i+p;j<m;j++)
if(cnt<m)
cnt++,s+='#';
s+='\n';
v.push_back(s);
}
cout<<v[0];
while(q--)
{
if(k&1)
for(int i=v.size()-2;i>=0;i--)
cout<<v[i];
else
for(int i=1;i<v.size();i++)
cout<<v[i];
k++;
}
} B.帮帮小戴
题目说了一堆废话，其实就是求n个数的最大公约数(greatest common divisor)。
一般手写求GCD用欧几里得算法，也叫辗转相除法。在HDU-LCY算法入门班第2讲《数学基础》中有讲到，可以自己去学一下。
这里给出常用的一个板子：
int gcd(int a,int b){return b?a:gcd(b,a%b);}; 在C++的algorithm头文件中，封装了一个GCD函数： ，可以直接得到两个同类型
数字的最大公约数。
:同类型指a和b同为
等整型，但是不包括
等浮点型。
本题直接三个for：第一个for输入n个数，第二个for得到n个数的最大公约数t，第三个for计算
#include<bits/stdc++.h>
using namespace std;
int n,a[1000006],t;
long long ans=0;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
t=a[0];
for(int i=1;i<n;i++)
t=__gcd(t,a[i]);
for(int i=0;i<n;i++)
ans+=a[i]/t;
cout<<ans;
} C.7的意志
题目对“7的意志”的定义为：
1.正整数 2.是7的倍数
由于，所以n的位数不大于18位，对于所有要删除的可能进行二进制枚举即可。最大需要枚举
种可能，即为262144种，评测机可以在1s内完成数据规模2e6的运算~
二进制枚举
对于一个二进制数比如说的二进制是
，我们逐位提取二进制位，
的视为取，
则视为不取。这样就很容易将一个数的各个数位提取出来。
二进制枚举是一个很常用的知识点，在涉及到大型枚举，状压的时候非常好用。相关的知识点还：状态压缩（搜索/dp），bitset
假如给定，当枚举参数是
时，取出的数k=135，我们再对135去判断是否满足7的意志即可。
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin>>s;
int len=s.size();
int n=1<<len;
for(int i=1;i<=n;i++)
{
int r=i;
__int128 tmp=0;
for(int j=0;j<len;j++)
{
if(r&1)
tmp=tmp*10+s[j]-'0';
r/=10;
}
if(tmp%7==0)
{
puts("yes");
return 0;
}
}
puts("no");
return 0;
} 搜索枚举
对于每一个数位，都有取或者不取两种情况。采用一个dfs去遍历每一个数位考虑取or不取的情况即可。效率与上面的二进制枚举近似一样。只会在数据规模极大或极小的时候有一些内存上的差距，一般不用考虑这方面问题。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int g[25], cnt, ans;
void dfs(int pos, ll x)
{
if (!pos)
{
if (x % 7 == 0 && x) ans ++;
return;
}
dfs(pos - 1, x * 10 + g[pos]);
dfs(pos - 1, x);
}
int main()
{
ll n;
cin >> n;
while (n) g[++cnt] = n % 10, n /= 10;
dfs(cnt, 0);
cout << ans << endl;
return 0;
} 相关：逐位进行DFS这只是最基础的一个版本，题目还可以变成给定一个整数范围，让你找范围内有多少个数满足要求。那时候就对每个数位进行0~9的枚举，再进行一些其他操作。就会涉及到数位DP，还有一些大型搜索了。
D.qq的考试
晴晴学长说他不写题解，不会的看代码注释，还不会的线下单杀晴晴学长就好。
#include<bits/stdc++.h>
typedef long long ll;
const ll mod = 1e9 + 7;
using namespace std;
int c[10010];
int main() {
int n, m;
cin >> n >> m;
string a, b;
cin >> a >> b; //C++的字符串，不会的同学可以用C的char
int k = 0;
ll sum = 0; // 注意开long long
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (a[i] != b[i]) { //如果答案错误，则把他的分值放入数组c中
c[++k] = x;
}
else { //如果答案正确，则直接加上他的分值。
sum += x;
}
}
sort(c + 1, c + 1 + k); // 快排，没学的同学使用自己会的排序方法
if (k < m) { // 如果错误答案数小于最大修改数，则说明所有的错误题目的分值均可加上去
for (int i = k; i >= 1; i--) {
sum += c[i];
}
}
else { // 如果错误答案大于等于最大修改数，则把前m大的分值加上去
for (int i = k; m > 0; m--, i--) {
sum += c[i];
}
}
cout << sum;
return 0;
} P.S 这题还有优先队列解法，不做补充了。
E.RMQ模板
板中板，自己去洛谷学线段树啥的。
这题数据弱了，被一堆O(N*Q)的暴力卡过去了，出题人背锅，很抱歉qwq
静态RMQ问题可以用st表维护效率更高。带修RMQ通常只能用线段树来写，本题STD就是线段树。
冷知识：1e5八仙过海，1e6线段树就随运气了，大概率被卡。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node
{
int l,r,max;
}t[N<<2];
void build(int k,int l,int r)
{
t[k].l=l;t[k].r=r;
if(l==r)
{
cin>>t[k].max;
return ;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
t[k].max=max(t[k<<1].max,t[k<<1|1].max);
}
int query(int k,int l,int r)
{
if(l<=t[k].l&&t[k].r<=r)
return t[k].max;
int ans=-0x3f3f3f3f;
int mid=(t[k].l+t[k].r)>>1;
if(l<=mid)ans=max(ans,query(k<<1,l,r));
if(r>mid)ans=max(ans,query(k<<1|1,l,r));
return ans;
}
int main()
{
int n,q,l,r;
cin>>n>>q;
build(1,1,n);
while(q--)
{
cin>>l>>r;
cout<<query(1,l,r)<<endl;
}
} #include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int n,q,M[N][20],lo[N];
void ST()
{
for(int i=2;i<=n;i++)
lo[i] = lo[i>>1] + 1;
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
M[i][j] = max(M[i][j-1],M[i+(1<<(j-1))][j-1]);
}
}
}
void quer_x(int l,int r)
{
int len = r-l+1;
int k = lo[len];
int ans = max(M[l][k],M[r-(1<<k)+1][k]);
printf("%d\n",ans);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&M[i][0]);
ST();
for(int i=1;i<=q;i++)
{
int l,r;
scanf("%d%d",&l,&r);
quer_x(l,r);
}
return 0;
} F.哼！想逃？
排序，优先队列，贪心。
给这些人按照啥时候离开排个序就行。能走的就早点走别逗留~
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,n,x;
cin>>t;
while(t--)
{
cin>>n;
priority_queue<int>q;
while(n--)
{
cin>>x;
q.push(x);
}
while(q.size()&&q.top()>=q.size())
q.pop();
cout<<q.size()<<endl;
}
return 0;
} G.马猴烧酒
本题是玉神出的超大型诈骗题，1e1000的数据看上去真的很哈人，但是细心的小朋友就会发现：
我们同时对和
乘上
，得到
如果观察仔细的话就可以发现这里有一个完全平方公式，当且仅当时满足
，否则其他时候都是
的，所以直接判就行了。
C/C++由于int128的范围也不够放10^1000^，所以用字符串去模拟数字即可。
PYTHON可以直接存进去嗯算，也是无脑过题~
#include<bits/stdc++.h>
#define int long long
using namespace std;
string a,b,c;
signed main()
{
cin>>a>>b>>c;
if(a==b&&b==c)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
} a,b,c = input().split()
a = int(a)
b = int(b)
c = int(c)
A = a*b//c+b*c//a+c*a//b
B = a+b+c
if(A>B):
print("YES")
else:
print("NO") H.卷王之间的决斗
很不巧，H也是大型诈骗题~
这题如果认真写过上上上周蓝桥训练题欧拉函数的同学，应该问题不大。题面说了一大堆其实就是先计算之间与
互质的数的个数
，这里
的个数就是代表了反对出模板题的人数，则可以得到如果
，输出
，否则输出
。（关于怎么求
的个数可以去某度了解一下欧拉函数的定义）
#include<bits/stdc++.h>
using namespace std;
const int N = 30010;
void solve(){
int arr[N] = {0};
int n; cin >> n;
int N = n, ans = n, idx = 0;
for(int i = 2; i * i <= N; i ++){
if(n % i == 0) arr[idx++] = i;
while(n % i == 0) n /= i;
}
if(n > 1) arr[idx++] = n;
for (int i = 0; i < idx; i++){
ans = ans - ans / arr[i];
}
if(ans <= N / 2) cout << "yes" << endl;
else cout << "no" << endl;
}
int main()
{
int t; cin >> t;
for (int i = 0; i < t; i++) solve();
return 0;
} 
，接着当手孝子