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

19级算法训练赛第十场

比赛地址：https://vjudge.net/contest/367058#overview 密码：IWantToACC
内容涉及：A数学定理 B贪心入门 C枚举or数位dp D枚举or唯一分解定理 E离散化+差分 F唯一分解定理 G计算机常识+二进制 H签到

直播讲解高清录像放在B站上，点击下面链接进入

视频链接：https://www.bilibili.com/video/bv1ak4y197pm

A-[NOIP2017]小凯的疑惑

#include<bits/stdc++.h>
#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);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int main(){
    ios;
    ll a,b;cin>>a>>b;
    cout<<a*b-(a+b)<<endl;
    return 0;
}

B-合并果子

#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;
priority_queue<int,vector<int>,greater<int>> q;
int main(){
    ios;
    cin>>T;
    while(T--){
        while (q.size()) q.pop();
        cin>>N;
        for(int i = 1;i<=N;i++){
            int cur;cin>>cur;
            q.push(cur);
        }
        ll res = 0;
        while(q.size()>=2){
            int t1 = q.top();q.pop();
            int t2 = q.top();q.pop();
            res += t1 + t2;
            q.push(t1+t2);
        }
        cout<<res<<endl;
    }

    return 0;
}

C - 不要62

#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 dp[maxn][2];
int nums[10];

int dfs(int pos,bool limit,bool pre_is6){
    if(!limit && dp[pos][pre_is6] != -1) return dp[pos][pre_is6];
    if(pos == 0) return 1;
    int up = limit? nums[pos]:9;
    int sum = 0;
    for(int i = 0;i<=up;i++){
        if(i == 4) continue;
        if(i == 2 && pre_is6) continue;
        sum += dfs(pos-1,limit && i == nums[pos],i == 6);
    }
    if(!limit) dp[pos][pre_is6] = sum;
    return sum;
}

int solve(int x){
    int pos = 0;
    while(x){
        nums[++pos] = x%10;
        x/=10;
    }
    return dfs(pos,1,0);
}

int main(){
    memset(dp,-1, sizeof(dp));
    while(scanf("%d %d",&N,&M)){
        if(N == 0 && M == 0) break;
        printf("%d\n",solve(M)-solve(N-1));
    }
    return 0;
}

D - [NOIP2009]Hankson的趣味题

#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 a0,a1,b0,b1;
bool vis[maxn];
int P[maxn],tail;
struct node{
    int a,b,c,d;
};
map<int,node> mp;
inline void read(int &x){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
inline void write(int X)
{
    if(X<0) {putchar('-'); X=~(X-1);}
    int s[20],top=0;
    while(X) {s[++top]=X%10; X/=10;}
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
}
void initP(int N){
    for(int i = 2;i<=N;i++){
        if(!vis[i]) P[tail++] = i;
        for(int j = 0;P[j]<=N/i;j++){
            vis[P[j]*i] = true;
            if(i%P[j] == 0) break;
        }
    }
}
void divP(){
    int idx = 0;
    for(int t:{a0,a1,b0,b1}){
        ++idx;
        for(int j = 0;j<tail && P[j]*P[j] <=t;j++){
            if(t%P[j] == 0){
                int cnt = 0;
                while(t%P[j] == 0){
                    cnt++;
                    t/=P[j];
                }
                if(idx == 1) mp[P[j]].a = cnt;
                if(idx == 2) mp[P[j]].b = cnt;
                if(idx == 3) mp[P[j]].c = cnt;
                if(idx == 4) mp[P[j]].d = cnt;
            }
        }
        if(t>1){
            if(idx == 1) mp[t].a = 1;
            if(idx == 2) mp[t].b = 1;
            if(idx == 3) mp[t].c = 1;
            if(idx == 4) mp[t].d = 1;
        }
    }
}
ll fun(){
    ll res = 1;
    for(auto p:mp){
        node cur = p.second;
        int a = cur.a,b = cur.b,c = cur.c,d = cur.d;
        int cnt = 0;
        for(int i = 0;i<=31;i++){
            if(min(i,a) == b && max(i,c) == d) cnt++;
        }
        res *= cnt;
    }
    return res;
}
int main(){
    initP(1<<16);
    cin>>T;
    while(T--){
        read(a0),read(a1),read(b0),read(b1);
        mp.clear();
        divP();
        printf("%d\n",fun());
    }
    return 0;
}

E - Covered Points Count

#include<bits/stdc++.h>
#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<ll,ll> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
pii lr[maxn];
ll arr[maxn],tail;
ll ca[maxn],idx;
ll ans[maxn];
map<ll,ll> pos,rpos;
void Lisa(){
    arr[0] = -1;
    sort(arr+1,arr+tail+1);
    for(int i = 1;i<=tail;i++){
        if(arr[i] != arr[i-1]) pos[arr[i]] = ++idx,rpos[idx] = arr[i];
    }
}

int main(){
    ios;
    cin>>N;
    for(int i = 1;i<=N;i++){
        ll l,r;cin>>l>>r;
        arr[++tail] = l,arr[++tail] = r+1;
        lr[i] = {l,r};
    }
    Lisa();
    for(int i = 1;i<=N;i++){
        ll l = lr[i].fs,r = lr[i].sc;
        ca[pos[l]] += 1;
        ca[pos[r+1]] -=1;
    }
    for(int i = 1;i<=idx;i++) ca[i] += ca[i-1];
    for(int i = 1;i<=idx-1;i++){
        ans[ca[i]] += rpos[i+1] - rpos[i];
    }
    for(int i = 1;i<=N;i++) cout<<ans[i]<<" ";cout<<endl;
    return 0;
}

F - [NOIP2009]细胞分裂

#include<bits/stdc++.h>
#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 int maxn = 1e6+10;
const int inf = 2e9;
using namespace std;

int N,M1,M2;
bool vis[maxn];
int P[maxn/10],tail;
struct node
{
    int a,b;
};
map<int,node> mp;
int ans = inf;
void initP(int N){
    for(int i = 2;i<=N;i++){
        if(!vis[i]) P[tail++] = i;
        for(int j = 0;P[j]<=N/i;j++){
            vis[P[j] * i] = true;
            if(i % P[j] == 0) break;
        }
    }
}

void divM(int x = M1){
    for(int i = 0;i<tail && P[i]*P[i] <= x;i++){
        if(x%P[i] == 0){
            int cnt = 0;
            while(x%P[i] == 0){
                cnt++;
                x/=P[i];
            }
            mp[P[i]].b = cnt * M2;
        }
    }
    if(x>1) mp[x].b = M2;
}
void divP(int x){
    mp.clear();
    divM();
    for(int i = 0;i<tail && P[i]*P[i] <= x;i++){
        if(x%P[i] == 0){
            int cnt = 0;
            while(x%P[i] == 0){
                cnt++;
                x/=P[i];
            }
            mp[P[i]].a = cnt;
        }
    }
    if(x>1) mp[x].a = 1;
}

int sovle(){
    int mx = 0;
    for(auto p:mp){
        auto cur = p.second;
        int a = cur.a,b = cur.b;
        if(b > 0 && a == 0) return inf;
        if(b > 0) mx = max(mx,(b-1)/a + 1);
    }
    return mx;
}
int main(){
    ios;
    initP(1<<16);
    cin>>N>>M1>>M2;
    while(N--){
        int x;cin>>x;
        divP(x);
        ans = min(ans,sovle());
    }
    if(ans == inf) cout<<-1<<endl;
    else cout<<ans<<endl;


    return 0;
}

G - 输出二进制补码

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

vector<bool> ans;
int main(){
    ios;
    int N;cin>>N;
    for(int j = 31;j>=0;j--){
        if((N>>j)&1) ans.push_back(1);
        else ans.push_back(0);
    }
    for(int i = 0;i<32;i++) cout<<ans[i];

    return 0;
}

H - 矩阵加法

#include<bits/stdc++.h>
#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);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N,M;
int ans[111][111];
int main(){
    ios;
    cin>>N>>M;
    for(int k:{1,2}){
        for(int i = 1;i<=N;i++){
            for(int j = 1;j<=M;j++){
                int cur;cin>>cur;
                ans[i][j] += cur;
            }
        }
    }

    for(int i = 1;i<=N;i++){
        for(int j = 1;j<=M;j++){
            cout<<ans[i][j];
            if(j<M) cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}
Ryuichi的算法分享 文章被收录于专栏

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

全部评论

相关推荐

头像
勇敢的山羊拒绝pua
06-25 16:52
长安大学 客户代表
点赞 评论 收藏
分享
头像
神枪手666
06-27 14:24
算法工程师
华为OD机试：寻找最优的路测线路
题目描述评估一个网络的信号质量，其中一个做法是将网络划分为栅格，然后对每个栅格的信号质量计算。路测的时候，希望选择一条信号最好的路线（彼此相连的栅格集合）进行演示。现给出&nbsp;R&nbsp;行&nbsp;C&nbsp;列的整数数组&nbsp;Cov，每个单元格的数值&nbsp;S&nbsp;即为该栅格的信号质量（已归一化，无单位，值越大信号越好）。要求从&nbsp;[0,&nbsp;0]&nbsp;到&nbsp;[R-1,&nbsp;C-1]设计一条最优路测路线。返回该路线得分。规则：1.路测路线可以上下左右四个方向，不能对角2.路线的评分是以路线上信号最差的栅格为准的，例如路径&nbsp;8→4→5→9&nbsp;的值为4，该线路评分为4。线路最优表示该条线路的评分最高输入描述第一行表示栅格的行数&nbsp;R第二行表示栅格的列数&nbsp;...
查看1道真题和解析 投递华为等公司10个岗位 >
点赞 评论 收藏
分享
头像
安静的coder在吃瓜
05-31 00:37
营销
点赞 评论 收藏
分享
头像
cicospui
06-25 14:09
暨南大学番禺校区 Java
美团后端开发实习心得，附苍穹外卖项目包装攻略
不知不觉来开水团实习两个月了，忽然想起来还有个项目包装的坑还没有填，这篇笔记就分享下团子的实习生活，并随后附上苍穹外卖的项目包装攻略。📍园区：&nbsp;笔主在恒电大厦实习。租房子在附近，十分钟的通勤时间真的大大提升幸福感，有时候中午还能回去睡一会儿。园区内的环境非常好，就是人有点多，不过大多都是年轻人，很有活力。⌚️工作时间：&nbsp;最少打卡9小时，通常是早上10点到晚上7点，但一般都呆到8点拿个补贴。加班也不严重，只要能干完活儿，呆够时间直接走也可以。🎁实习薪资/待遇：&nbsp;团子实习薪资没得说，同行业中处于中上水平，还为实习生提供免费的健身房和医务室。📄实习体验：&nbsp;作为后端开发实习生，我的主要工作是参与...
美团公司氛围 509人发布 投递美团等公司10个岗位 >
点赞 评论 收藏
分享
1 收藏 评论
分享

全站热榜

正在热议
# 打工人的辛酸 #
11862次浏览 195人参与
# 投递实习岗位前的准备 #
809692次浏览 13945人参与
# 极具前瞻性，现代汽车编程题 #
28791次浏览 512人参与
# 机械制造投递记录 #
159658次浏览 2732人参与
# 机械人怎么评价今年的华为 #
98194次浏览 757人参与
# 应届生应该先就业还是先择业 #
16980次浏览 149人参与
# 不去互联网可以去金融科技 #
65642次浏览 622人参与
# 晒一晒我的offer #
4368413次浏览 63322人参与
# 25届如何提前做秋招准备？ #
43943次浏览 1011人参与
# 想辞职但是不敢的原因 #
4196次浏览 65人参与
# 如何一边实习一边秋招 #
433578次浏览 6563人参与
# 实习生如何通过转正 #
33636次浏览 417人参与
# 我的简历长这样 #
46961次浏览 934人参与
# 摸鱼打卡站 #
10873次浏览 549人参与
# 你后悔选择现在的专业吗 #
12181次浏览 175人参与
# 你的秋招进行到哪一步了 #
470075次浏览 7356人参与
# 没有实习经历，还有机会进大厂吗 #
493453次浏览 9644人参与
# 我的上岸简历长这样 #
253333次浏览 4862人参与
# 如果校招重来我最想改变的是 #
107337次浏览 1699人参与
# 机械制造笔面经 #
65517次浏览 1321人参与
# 许愿池 #
106187次浏览 1825人参与
# 我的成功项目解析 #
111132次浏览 3009人参与
牛客网
牛客企业服务