【19级算法训练赛第九场】题解

题解在B站发布，请点击下面的链接进入。

B站视频讲解

比赛密码：HPUACM

A - Fantasy of a Summation

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int T;
ll n,k,mod;
ll ksm(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    cin>>T;
    int kase = 0;
    while(T--){
        scanf("%lld%lld%lld",&n,&k,&mod);
        ll ans = 0;
        for(int i = 1;i<=n;i++){
            ll cur;scanf("%lld",&cur);
            ans = (ans + k*cur%mod*ksm(n,k-1)%mod)%mod;
        }
        printf("Case %d: %lld\n",++kase,ans);
    }

    return 0;
}

B - 又见GCD

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int T;
ll a,b;
ll gcd(ll a,ll b){
    return !b? a:gcd(b,a%b);
}

int main(){
    ios;
    cin>>T;
    while(T--){
        cin>>a>>b;
        for(ll c = 2*b;c<1e6+10;c+=b){
            if(gcd(a,c) == b){
                cout<<c<<endl;
                break;
            }
        }
    }
    return 0;
}

C - Phoneme Palindromes

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0);
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int T,p,q;
string s;
char mp[300];

bool fun(){
    int l = 0,r = s.length()-1;
    while(l<=r){
        if(s[l] != s[r]) return false;
        l++,r--;
    }
    return true;
}

int main(){
    cin>>T;
    int kase = 0;
    while(T--){
        printf("Test case #%d:\n",++kase);
        cin>>p;
        memset(mp,0,sizeof mp);
        while(p--){
            char a,b;cin>>a>> b;
            mp[a] = b;
        }
        cin>>q;
        while(q--){
            cin>>s;cout<<s<<" ";
            for(int i = 0;i<s.length();i++){
                if(mp[s[i]]) s[i] = mp[s[i]];
            }
            if(fun()) cout<<"YES\n";
            else cout<<"NO\n";
        }
        cout<<endl;
    }
    return 0;
}

D - Maximum Square

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int T,N;
int arr[maxn];
int main(){
    ios;
    cin>>T;
    while(T--){
        int res = 0;
        cin>>N;
        for(int i = 1;i<=N;i++) cin>>arr[i];
        sort(arr+1,arr+N+1,greater<int>());
        for(int i = 1;i<=N;i++){
            res = max(res,min(i,arr[i]));
        }
        cout<<res<<endl;
    }
    return 0;
}

E - Walk on Matrix

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int main(){
    ios;
    int x = 1<<17,y;
    cin>>y;
    cout<<"2 3"<<endl;
    int ans[2][3] = {
            {x|y,y,0},
            {x,x|y,y},
    };
    for(int i = 0;i<2;i++){
        for(int j = 0;j<3;j++)
            cout<<ans[i][j]<<" ";
        cout<<endl;
    }


    return 0;
}

F - A计划

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int C,T,N,M;
int endx,endy;
char G[20][20][2];
bool vis[20][20][2];
int dir[4][2] = {-1,0,1,0,0,1,0,-1};
struct pos{
    int x,y,z,t;
};

bool BFS(){
    memset(vis,0,sizeof vis);
    queue<pos> q;
    q.push({0,0,0,0});
    vis[0][0][0] = true;

    while(q.size()){
        pos u = q.front();q.pop();
        if(u.t <= T && G[u.x][u.y][u.z] == 'P') return true;
        for(int i = 0;i<4;i++){
            int nx = u.x+dir[i][0];
            int ny = u.y+dir[i][1];
            int nz = u.z;
            if(nx<0 || ny<0 || nx>=N || ny>=M || G[nx][ny][nz] == '*' || vis[nx][ny][nz]) continue;
            if(G[nx][ny][nz] == '#'){
                if(G[nx][ny][nz^1] == '#' || G[nx][ny][nz^1] == '*' || vis[nx][ny][nz^1]) continue;
                else nz^=1;
            }
            if(u.t+1>T || u.t + abs(nx-endx) + abs(ny-endy) >T) continue;//剪枝
            q.push({nx,ny,nz,u.t+1});
            vis[nx][ny][nz] = true;
        }
    }
    return false;
}
int main(){
    ios;
    cin>>C;
    while(C--){
        cin>>N>>M>>T;
        for(int z = 0;z<=1;z++){
            for(int x = 0;x<N;x++){
                for(int y = 0;y<M;y++){
                    cin>>G[x][y][z];
                    if(G[x][y][z] == 'P') endx = x,endy = y;
                }
            }
        }
        if(BFS()) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

G - Pseudoprime numbers

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

ll p,a;
ll ksm(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res*a%p;
        a = a*a%p;
        b>>=1;
    }
    return res;
}
ll is_prime(ll x){
    if(x == 2) return true;
    for(int i = 2;i*i<=x;i++){
        if(x%i == 0) return false;
    }
    return true;
}

int main(){
    ios;
    while(cin>>p>>a){
        if(p == 0 && a == 0) break;
        if(ksm(a,p)  != a || is_prime(p)) cout<<"no\n";
        else cout<<"yes\n";
    }

    return 0;
}

H - Rightmost Digit

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int T;
ll ksm(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res*a%10;
        a = a*a%10;
        b>>=1;
    }
    return res;
}

int main(){
    ios;
    cin>>T;
    while(T--){
        ll n;cin>>n;
        cout<<ksm(n,n)<<"\n";
    }
    return 0;
}

I - Co-prime

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int T;
int yin[maxn],tail;

ll fun(ll x){
    ll res = 0;
    for(int i = 1;i<(1<<tail);i++){
        ll cur = 1,cnt = 0;
        for(int j = 0;j<tail;j++){
            if((i>>j) & 1){
                cnt++;
                cur *= yin[j+1];
            }
        }
        if(cnt&1) res += x/cur;
        else res -=x/cur;
    }
    return x-res;
}

int main(){
    cin>>T;
    int kase = 0;
    while(T--){
        tail = 0;
        ll a,b,c;cin>>a>>b>>c;
        for(int i = 2;i*i<=c;i++){
            if(c%i == 0){
                yin[++tail] = i;
                while(c%i == 0) c/=i;
            }
        }
        if(c>1) yin[++tail] = c;
        ll ans = fun(b)-fun(a-1);
        printf("Case #%d: %lld\n",++kase,ans);
    }
    return 0;
}

J - 摘花生

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int T,N,M;
int arr[111][111];
int dp[111][111];
int main(){
    ios;
    cin>>T;
    while(T--){
        cin>>N>>M;
        for(int i = 1;i<=N;i++){
            for(int j = 1;j<=M;j++){
                cin>>arr[i][j];
            }
        }
        memset(dp,0,sizeof dp);
        for(int i = 1;i<=N;i++){
            for(int j = 1;j<=M;j++){
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + arr[i][j];
            }
        }
        cout<<dp[N][M]<<"\n";
    }
    return 0;
}

K - 验证子串

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

string s1,s2;
int main(){
    ios;
    cin>>s1>>s2;
    if(s2.find(s1) != -1) cout<<s1<<" is substring of "<<s2<<"\n";
    else if(s1.find(s2) != -1) cout<<s2<<" is substring of "<<s1<<"\n";
    else cout<<"No substring\n";
    return 0;
}

L - 图像旋转

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int N,M;
int arr[111][111];
int ans[111][111];
int main(){
    ios;
    cin>>N>>M;
    for(int i = 1;i<=N;i++){
        for(int j = 1;j<=M;j++){
            cin>>arr[i][j];
        }
    }
    for(int j = 1;j<=M;j++){
        for(int i = N;i>=1;i--){
            cout<<arr[i][j]<<" ";
        }
        cout<<"\n";
    }

    return 0;
}

M - 整数去重

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int N;
bool st[111];
int main(){
    ios;
    cin>>N;
    while(N--){
        int cur;cin>>cur;
        if(st[cur]) continue;
        cout<<cur<<" ";
        st[cur] = true;
    }
    return 0;
}

N - 国王的魔镜

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

string s;
int main(){
    ios;
    cin>>s;
    while(true){
        int len = s.length();
        string l = s.substr(0,len/2),r = s.substr(len/2);
        reverse(r.begin(),r.end());
        if(len%2 || l != r) break;
        s = l;
    }
    cout<<s.length()<<"\n";
    return 0;
}

O - DIY Wooden Ladder

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int T,N;
int arr[maxn];
int main(){

    ios;
    cin>>T;
    while(T--){
        cin>>N;
        for(int i = 1;i<=N;i++){
            cin>>arr[i];
        }
        sort(arr+1,arr+N+1,greater<int>());
        int mi = min(arr[1],arr[2]);
        if(N <= 2 || mi <=1) cout<<0<<endl;
        else cout<<min(N-2,mi-1)<<endl;
    }
    return 0;
}

P - Dawid and Bags of Candies

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int arr[5];
int main(){
    ios;
    for(int i = 1;i<=4;i++) cin>>arr[i];
    sort(arr+1,arr+5);
    if(arr[1] + arr[4] == arr[2]+arr[3] || arr[1]+arr[2]+arr[3] == arr[4]) cout<<"YES\n";
    else cout<<"NO\n";
    return 0;
}
Ryuichi的算法分享 文章被收录于专栏

分享我的一些算法题解，致力于把题解做好，部分题解可能会采用视频的形式来讲解。

全部评论

相关推荐

10-21 09:35
厦门大学 驱动开发
狗都不干单休， 真的不要选单休的工作！
前言除非是真的没办法，或者是工资真的非常非常高，我劝各位真的不要选单休的工作。我毕业第一份工作就是单休的，当时因为转行，再加上疫情工作确实不好找，没办法就选了个单休的公司。单休工作的感受大体如下：单休等于没休，一到周末就不想出去，休息那一天睡个懒觉，起床就到中午了，有精力下午就出去逛一逛。因为第二天又要上班，晚上基本得早点休息，一天就这样子过去了。刚毕业的时候精力好，还能折腾，过了3-4个月就真心不想出门了。而双休，甚至是大小周，起码有个两天的周末你可以兼顾游玩和休息。单休跟双休，或者是大小周对比，一个月分别少休4天、2天；一年下来就是48天，24天；两年就是96天，48天……单休是干6天休一...
点赞 评论 收藏
分享
10-19 11:08
哈尔滨工业大学 C++
点赞 评论 收藏
分享
10-13 13:49
南京大学 财务
不想谈方便面
饿魔：笑死我了，你简直是个天才
点赞 评论 收藏
分享
头像
09-01 15:54
桂林电子科技大学 安卓
点赞 评论 收藏
分享
10-17 11:58
FUNPLUS_服务端开发工程师(准入职员工)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 怎么给家人解释你的工作？ #
10614次浏览 74人参与
# 应届生被毁约被毁意向了怎么办 #
45725次浏览 279人参与
# 快手技术岗信息交流阵地 #
2615次浏览 26人参与
# 你的mentor是什么样的人？ #
15564次浏览 110人参与
# 牛客周边新品开箱 #
10116次浏览 89人参与
# 帮我看看，领导说这话什么意思？ #
20218次浏览 98人参与
# 求职中的尴尬瞬间 #
3476次浏览 41人参与
# 牛友的志愿填报指南 #
34592次浏览 185人参与
# 国企还是互联网，你怎么选？ #
169588次浏览 1271人参与
# 牛客树洞，我想对你说 #
8230次浏览 93人参与
# 机械人集合！你是什么工程师？ #
19603次浏览 91人参与
# 如何KTV领导 #
72389次浏览 502人参与
# 大疆工作体验 #
18520次浏览 85人参与
# 今年形式下双非本找得到工作吗 #
237232次浏览 1433人参与
# 三一集团提前批进度交流 #
38145次浏览 225人参与
# 求职低谷期你是怎么度过的 #
12336次浏览 246人参与
# 26届秋招公司红黑榜 #
27640次浏览 113人参与
# 校招泡的最久的公司是哪家？ #
12427次浏览 80人参与
# 从哪些方向判断这个offer值不值得去？ #
16218次浏览 188人参与
# 得物app工作体验 #
28010次浏览 64人参与
# 大厂无回复，继续等待还是奔赴小厂 #
247679次浏览 1633人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务