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;
}