智算之道复赛题解

注：有些题解借鉴于其他博客的大佬

1.数字

题意：
给定两个数字 aa,b 求在 aa 前面加连接上一个三位数之后是 b 的倍数有多少种方案
算出aa的位数，然后直接直接枚举即可
代码：

#include<bits/stdc++.h>
using namespace std;
#define NOT_TLE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
const int maxn=1e5+5;

int main()
{
    ll a,b;cin>>a>>b;
    ll c=a;
    ll p=1;
    while(c){
        p*=10;
        c/=10;
    }
    int count=0;
    for(int i=100;i<=999;++i){
        if((p*i+a)%b==0) count++;
    }
    cout<<count<<endl;
    return 0;
}

2.网格

题意：
给出一个 n×n 的网格图，求从(0,0)走到 (n,n) 的最小花费为多少
向右或向上走的花费为w1，有 k 个特殊的点可以向右下走，花费为w2
1≤n,w1,w2≤10 ^9 ,0≤k≤2000
题解：当2w1<=w2时，最小花费为2nw1。
否则就看最多能走多少个特殊点,当且仅当x[i]>x[j]&&y[i]>y[j]时这两个特殊点才都能走到，同时为了排除像x取很大y取很小的情况，我们不能直接基数排序之后直接算出最多有多少个特殊点，而应该dp特殊点算出最多能走多少个特殊点ans,最终答案为：w12*(n-ans)+w2*ans，时间复杂度：O(k^2)
代码:

#include<bits/stdc++.h>
using namespace std;
#define NOT_TLE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define x first
#define y second
const int maxn=2020;
int dp[maxn],n,k,w1,w2,ans;
pair<int,int> p[maxn];
int main()
{
    cin>>n>>k>>w1>>w2;
    if(2*w1<=w2){
        cout<<(ll)2*w1*n<<endl;
        return 0;
    }
    for(int i=0;i<k;++i){
    cin>>p[i].x>>p[i].y;
    }
    sort(p,p+k);
    for(int i=0;i<k;++i){
        dp[i]=1;
        for(int j=0;j<i;++j){
            if(p[j].x<p[i].x && p[j].y<p[i].y && dp[j]+1>dp[i]) dp[i]=dp[j]+1;
        }
        if(ans<dp[i]) ans=dp[i];
    }
    cout<<(ll)w1*2*(n-ans)+(ll)w2*ans<<endl;
    return 0;
}

3.有向无环图

题意:给定 k ，你需要生成一个没有重边的有向无环图（点编号 1…n ），使得从 11 到 n 的路径数恰好为 k 。
输入格式
一行两个正整数 k,N ，表示要求的路径数和该测试点允许的最大点数（即你生成的图点数不得超过 N ）。
输出格式
第一行两个正整数 n,m ，表示你生成的图的点数和边数。
接下来 m 行，每行两个正整数 u,v ，表示有一条从 u 到 v 的有向边。
如有多个满足条件的图，输出任意一个。

题解:起点1，终点2，则有 1->2 一条路径，起点1，终点3，有 1->3,1->2->3 两条路径，。。。起点2，终点5，有2->5,2->3->5,2->4->5,2->3->4->5 四条路径，所以可以推出从点i到点n有2^(n-i-1)
条路径，所以先将起点分离，如果起点与i点连接，则就会增加2^(n-i-1),所以后面二进制拆解就行了，注意要开unsigned long long，k的值很大（这里补题的时候被坑惨了，菜鸡流下了卑微的流水）

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define NOT_TLE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
vector<pair<int,int> > all;
ll n,k;

int main()
{
    cin>>k>>n;
    if(k<n){
        n=k+1;
        cout<<n<<" "<<2*(n-2)+1<<endl;
        cout<<1<<" "<<n<<endl;
        for(int i=2;i<n;++i){
            cout<<1<<" "<<i<<endl;
            cout<<i<<" "<<n<<endl;
        }
    }
    else{
        ll cn=k;
        int cnt=0;
        while(cn){
        	cnt++;
        	cn=cn/2;
        }
        for(int i=2;i<=cnt+1;++i){
        	for(int j=i+1;j<=cnt+2;++j){
        		all.push_back(pair<int,int>(i,j));
        	}
        }
        for(int i=0;i<cnt;++i){
        	if((k>>i) & 1){
        		int index=cnt-i+1;
        		all.push_back(pair<int,int>(1,index));
        	}
        }
        ll len=all.size();
        cout<<cnt+2<<" "<<len<<endl;
        for(ll i=0;i<len;++i) cout<<all[i].first<<" "<<all[i].second<<endl;
    }
    return 0;
}

4.分数（菜鸡的补题）

**：给出三个数n,a,b;最初第i个数是1/i,每次选出下标最小的分母不为1的分数的分母q，令所有分数都乘上 q 并化简，重复这个过程直到所有数分母均为 1。
为了减少输出量，采用如下输出方式：给定两个整数 a,b ，对于每次操作的 q ，执行 a=a*q+b ，最后输出 a 对 2^32取模的值。
数据: 0<n<= 8×10^7，0< a,b< 2^32

题解:欧拉筛解题，首先直接O(n)复杂度求出题目给定范围内的所有素数
之后从1到n再筛一次最小质因子即可,关键是欧拉筛

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define NOT_TLE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn=8e7+5;
const ll mod=pow(2,32);
bool num[maxn];
int prime[maxn],countnum=1,f[maxn];
void oula(){
    for(int i=2;i<=maxn;++i){
        if(!num[i]) prime[countnum++]=i;
        for(int j=1;j<countnum;++j){
            if(i*prime[j]>maxn) break;
            num[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}
int main()
{
	ll n,a,b;
    cin>>n>>a>>b;
    oula();
    for(int i=1;i<countnum&&prime[i]<=n;++i){
        ll p=prime[i];
        while(p<=n){
            p*=prime[i];
            //这里直接连乘而不连加的原因是由于前面的欧拉筛已经筛掉了不是素数且不是乘方的所有数，比如6，已经被筛掉了,如果n=7,6已经不存在了，所以不能用连加
            if(p<=n) f[p]=prime[i];
        }
    }
    for(int i=2;i<=n;++i){
        if(!num[i]){
            a=a*i+b;
//            cout<<i<<endl;
            a=a%mod;
        }
        else if(f[i]){
            a=a*f[i]+b;
//            cout<<f[i]<<endl;
            a=a%mod;
        }
    }
    cout<<a<<endl;
    return 0;
}

5题后面补，先补补知识还是（$-_-）