欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

智算之道2020复赛题解

程序员文章站 2022-07-08 10:14:35
A数字思路: 直接暴力枚举就好了#include#include#include #include#include #include #include#include using namespace std;typedef long long ll;int...

A数字
智算之道2020复赛题解

思路: 直接暴力枚举就好了

#include<iostream>
#include<cstdio>
#include <map>
#include<cstring>
#include <map>
#include <math.h>
#include<queue>
#include <algorithm>

using namespace std;

typedef long long ll;

int get(ll x) {
    if(x == 0) return 1;
    int cnt = 0;
    while(x) {
        cnt++;
        x /= 10;
    }
    return cnt;
}

int main() {
    ll a,b;scanf("%lld%lld",&a,&b);
    ll ans = 0;
    int cnt = get(a);
    ll num = 1;
    for(int i = 1;i <= cnt;i++) {
        num = num * 10;
    }
    for(ll i = 1;i <= 9;i++) {
        for(ll j = 0;j <= 9;j++) {
            for(ll k = 0;k <= 9;k++) {
                ll now = (i * 100 + j * 10 + k) * num + a;
                if(now % b == 0) {
                    ans++;
                }
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

B网格(DP)
智算之道2020复赛题解

思路:
选择1走一步,花费为w1。选择2走两步,花费为w2。
先考虑只走选择1,则到(x,y)的花费为(x+y)w1(x+y)*w1

再考虑可以有选择2,我们要用魔法个点来优化之前的选择,则可以将魔法节点排序,那么就可以保证后面的魔法节点无法走到前面,这就无后效性了。再找子问题:

定义f[i]f[i]为到达第ii个魔法节点的距离,则有
num=a[i].x+a[i].ya[j].xa[j].y2num = a[i].x + a[i].y - a[j].x - a[j].y - 2
f[i]=min(f[i],f[j]+numw1+w2)f[i] = min(f[i],f[j] + num * w1 + w2)

#pragma GCC optimize(2)

#include<iostream>
#include<cstdio>
#include <map>
#include<cstring>
#include <map>
#include <math.h>
#include<queue>
#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 2005;
ll f[maxn];

struct Node {
    int x,y;
}a[maxn];

int cmp(Node a,Node b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

int main() {
    int n,k,w1,w2;scanf("%d%d%d%d",&n,&k,&w1,&w2);
    for(int i = 1;i <= k;i++) {
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    sort(a + 1,a + 1 + k,cmp);
    a[k + 1].x = n;a[k + 1].y = n;
    k++;
    for(int i = 1;i <= k;i++) {
        f[i] = 1ll * w1 * (a[i].x + a[i].y);
    }
    
    for(int i = 2;i <= k;i++) {
        for(int j = 1;j < i;j++) {
            if(a[j].x < a[i].x && a[j].y < a[i].y) {
                int num = a[i].x + a[i].y - a[j].x - a[j].y - 2;
                f[i] = min(f[i],f[j] + 1ll * num * w1 + w2);
            }
        }
    }
    
    printf("%lld\n",f[k]);
    return 0;
}



C 有向无环图(二进制拆解)
智算之道2020复赛题解
思路:
一开始只想到了
1->2
1->3
3->4
2->4
这种的建图模式。

但实际上你直接先建成一条链(假设是n个点),然后第i个点向后面所有点连边。这时候就有神奇的事情:第i个点到点n的方案数为2ni2^{n-i}
则再加一个源点0,0向第ii个点连边,方案数就会增加2ni2^{n-i}个, 这不就是二进制拆解吗?

而且刚好66个点,64个点表征二进制,两个点为原点,而且边数也就n^2级别,不会特别多。直接搞就好了

#pragma GCC optimize(2)

#include<iostream>
#include<cstdio>
#include <map>
#include<cstring>
#include <map>
#include <math.h>
#include<queue>
#include <algorithm>

using namespace std;

typedef unsigned long long ll;

vector<pair<int,int> >vec;

int main() {
    ll n,k;scanf("%llu%llu",&k,&n);
    
    ll tmp = k;
    int cnt = 0;
    while(tmp) {
        cnt++;
        tmp /= 2;
    }
    
    if(n == 2 && k == 1) {
        printf("2 1\n");
        printf("1 2\n");
        return 0;
    } else if(n == 4 && k == 3) {
        printf("4 5\n");
        printf("1 2\n2 3\n3 4\n1 3\n2 4\n");
        return 0;
    }
    
    int N = cnt + 2;
    for(int i = 2;i <= cnt + 1;i++) {
        for(int j = i + 1;j <= cnt + 2;j++) {
            vec.push_back({i,j});
        }
    }
    
    for(int i = 0;i < cnt;i++) {
        if((k >> i) & 1) {
            int nex = cnt - i + 1;
            vec.push_back({1,nex});
        }
    }
    
    printf("%d %d\n",N,(int)vec.size());
    for(int i = 0;i < vec.size();i++) {
        printf("%d %d\n",vec[i].first,vec[i].second);
    }
    return 0;
}

D 分数

智算之道2020复赛题解
思路:
打个表可以发现(事后也可以证明),对于第ii个分数的贡献,就是ii中质因子比LCM(n1)LCM(n-1)多的部分。


当n为单个质数幂次时
LCM(n)=LCM(n1)prime[i]LCM(n)=LCM(n-1)*prime[i]
否则
LCM(n)=LCM(n1)LCM(n)=LCM(n-1)

所以只需要求出所有位单个质数幂次的数就行了。

#pragma GCC optimize(2)

#include<iostream>
#include<cstdio>
#include <map>
#include<cstring>
#include <map>
#include <math.h>
#include<queue>
#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 8e7 + 7;
const ll mod = 1ll << 32;

int a[5000000],cnt;
int v[maxn];

void getprime() {
    for(int i = 2;i < maxn;i++) {
        if(v[i] == 0) {
            v[i] = i;a[++cnt] = i;
        }
        for(int j = 1;j <= cnt && i * a[j] < maxn;j++) {
            v[i * a[j]] = 1;
            if(i % a[j] == 0)break;
        }
    }
}

ll qpow(ll x,ll n) {
    ll res = 1;
    while(n) {
        if(n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

ll gcd(ll n,ll m) {
    return m == 0 ? n : gcd(m,n % m);
}

int main() {
    getprime();
//    printf("debug %d\n",cnt);
    ll n,A,B;scanf("%lld%lld%lld",&n,&A,&B);
    for(int i = 2;i <= n;i++) {
        v[i] = 0;
    }
    
    for(int i = 1;i <= cnt;i++) {
        ll now = a[i];
        while(now <= n) {
            v[now] = i;
            now = now * a[i];
        }
    }
    
    for(int i = 2;i <= n;i++) {
        if(v[i]) {
            A = (A * a[v[i]] % mod + B) % mod;
        }
    }
    printf("%lld\n",A);
    return 0;
}



E 树数数
智算之道2020复赛题解
思路:
被拉去吃兰州拉面,写个暴力就跑了,有时间补补吧。

#pragma GCC optimize(2)

#include<iostream>
#include<cstdio>
#include <map>
#include<cstring>
#include <map>
#include <math.h>
#include<queue>
#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 2e3 + 7;

int a[maxn],color[maxn];
int fa[maxn],vis[maxn];
vector<int>G[maxn];

void dfs1(int x) { //染色
    vis[x] = 1;
    if(x == 1) return;
    dfs1(fa[x]);
}

int dfs2(int x) { //寻找
    if(vis[x] && color[x] == 1) {
        return a[x];
    }
    if(x == 1) return 0;
    return dfs2(fa[x]);
}

vector<int>point;

void dfs3(int x,int fa) { //找u子树
    point.push_back(x);
    for(int i = 0;i < G[x].size();i++) {
        int v = G[x][i];
        if(v == fa) continue;
        dfs3(v,x);
    }
}

ll LCBA(int u) {
    point.clear();
    dfs3(u,fa[u]);
    int len = point.size();
    ll ans = 0;
    for(int i = 0;i < len;i++) {
        for(int j = 0;j < len;j++) {
            if(i == j) continue;
            memset(vis,0,sizeof(vis));
            dfs1(point[i]);
            ans += dfs2(point[j]);
        }
    }
    return ans / 2;
}

int main() {
    int n,m;scanf("%d%d",&n,&m);
    for(int i = 2;i <= n;i++) {
        int x;scanf("%d",&x);
        fa[i] = x;
        G[i].push_back(x);G[x].push_back(i);
    }
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
    }
    for(int i = 1;i <= m;i++) {
        char op[10];scanf("%s",op);
        if(op[0] == 'Q') {
            int u;scanf("%d",&u);
            printf("%lld\n",LCBA(u));
        } else if(op[0] == 'F') {
            int x;scanf("%d",&x);
            color[x] ^= 1;
        } else if(op[0] == 'M') {
            int x,y;scanf("%d%d",&x,&y);
            a[x] = y;
        }
    }
    return 0;
}

本文地址:https://blog.csdn.net/tomjobs/article/details/107898022