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