智算之道2020复赛参考代码

╰半夏微凉° 2022-12-01 15:43 14阅读 0赞

# T1 #

#include <cstdio>
    #define LL long long
    
    LL pow10(LL m)
    { 
        return m == 0 ? 1 : 10 * pow10(m - 1);
    }
    
    int main()
    { 
        LL aa, b;
        scanf("%lld%lld", &aa, &b);
        LL len = 0;
        LL tmp = aa;
        while(tmp)
        { 
            len++;
            tmp /= 10;
        }
        LL result = 0;
        for(LL i = 100; i < 1000; i++)
        { 
            LL a = i * pow10(len) + aa;
            if(a % b == 0)
            { 
                result++;
            }
        }
        printf("%lld",result);
        return 0;
    }

# T2 #

#include<cstdio>
    #include <algorithm>
    using namespace std;
    
    #define x first
    #define y second
    
    typedef long long LL;
    const int N = 2020;
    
    int n, k, w1, w2;
    pair<int, int> p[N];
    int f[N];
    
    int main()
    { 
        //freopen("T2.in", "r", stdin);
    
        scanf("%d%d%d%d", &n, &k, &w1, &w2);
        int m = n << 1;
        if(w1 * 2 <= w2)
        { 
            return 0 * printf("%lld\n", (LL)m * w1);
        }
    
        for(int i = 0; i < k; i ++)
        { 
            scanf("%d%d", &p[i].x, &p[i].y);
        }
    
        sort(p, p + k);
    
        int cnt = 0;
        for(int i = 0; i < k; i ++)
        { 
            f[i] = 1;
            for(int j = 0; j < i; j ++)
            { 
                if(p[j].x < p[i].x and p[j].y < p[i].y and f[j] + 1 > f[i])  f[i] = f[j] + 1;
            }
    
            if(f[i] > cnt)
            { 
                cnt = f[i];
            }
        }
    
        m -= cnt * 2;
    
        printf("%lld\n", (LL)m * w1 + (LL)cnt * w2);
    
        return 0;
    }

# T3 #

#include<iostream>
    #include<vector>
    using namespace std;
    
    typedef unsigned long long LL;
    
    vector<pair<int,int> >vec;
    
    int main()
    { 
        //freopen("T3.in", "r", stdin);
    
        LL n,k;
        scanf("%llu%llu",&k,&n);
    
        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;
        }
    
        LL tmp = k;
        int cnt = 0;
        while(tmp) //k有几位二进制位
        { 
            cnt++;
            tmp /= 2;
        }
    
        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;
    }

# T4 #

#include<iostream>
    using namespace std;
    
    typedef long long LL;
    
    const int maxn = 8e7 + 7;
    const LL mod = 1ll << 32;
    
    int prime[5000000], cnt;
    int primePos[maxn];
    
    //线性筛选法求质数
    void getprime()
    { 
        for(int num = 2; num < maxn; num++)
        { 
            if(primePos[num] == 0)//为0时才是质数
            { 
                primePos[num] = num;
                prime[++cnt] = num;
            }
    
            for(int j = 1; j <= cnt && num * prime[j] < maxn; j++)
            { 
                primePos[num * prime[j]] = 1;
                if(num % prime[j] == 0)
                { 
                    break;
                }
            }
        }
    }
    
    int main()
    { 
        //freopen("T4.in", "r", stdin);
    
        getprime();
    
        LL n, A, B;
        scanf("%lld%lld%lld", &n, &A, &B);
    
        for(int num = 2; num <= n; num++)
        { 
            primePos[num] = 0;
        }
    
        for(int i = 1; i <= cnt; i++)
        { 
            LL now = prime[i];
            while(now <= n)
            { 
                primePos[now] = i;
                now = now * prime[i];
            }
        }
    
        for(int num = 2; num <= n; num++)
        { 
            if(primePos[num])
            { 
                A = (A * prime[primePos[num]] % mod + B) % mod;
            }
        }
    
        printf("%lld\n", A);
    
        return 0;
    }

> 长按识别二维码加好友邀请进中小学信息学竞赛群 ![在这里插入图片描述][2020082722411464.png_pic_center]

[2020082722411464.png_pic_center]: /images/20221123/110d51c862cf4b0c806bcadb595ea02b.png