2019 年百度之星·程序设计大赛 - 初赛三[1-3]

题目链接:http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=863

A.

#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 10;
const int mod = 1e9+7;
typedef long long ll;

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        printf("%d\n",n^1);
    }
    return 0;
}

B.

跑个最短路，然后剪剪枝就OK了。

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int mx = 1e3 + 10;
const int mod = 998244353;
typedef long long ll;
typedef pair <int,int> pa;
vector <int> r;
vector <pa> g[mx];
ll d[mx][mx],dis[mx];
int c[mx][mx];
int n,m;
bool vis[mx];
void spfa(int beg){
    queue <int> q;
    for(int i=1;i<=n;i++)
        dis[i] = 1e16;
    dis[beg] = 0;
    q.push(beg);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        vis[now] = 0;
        for(pa po:g[now]){
            int v = po.x,w = po.y;
            if(dis[v]>dis[now]+po.y){
                dis[v] = dis[now] + po.y;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                c[i][j] = 0,d[i][j] = 1e16;
                if(i==j) d[i][j] = 0;
            }
            g[i].clear();
        }
        r.clear();
        for(int i=1;i<=m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            d[u][v] = min(1ll*w,d[u][v]);
            d[v][u] = min(1ll*w,d[v][u]);
            g[v].push_back(pa(u,w));
            g[u].push_back(pa(v,w));
        }
        for(int k=1;k<=n;k++){
            spfa(k);
            r.clear();
            for(int i=1;i<=n;i++){
                if(dis[i]==d[k][i])
                    r.push_back(i);
                if(d[k][i]!=d[i][k]) cout << 1/0 << endl;
            }
            for(int i:r){
                for(int j:r){
                    ll tmp = d[i][k] + d[k][j];
                    if(tmp<d[i][j]){
                        d[i][j] = tmp;
                        c[i][j] = k;
                    }
                }
            }
        }
        ll ans = 0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                ans += c[i][j];
                //cout << dis[i][j] << endl;
            }
        }
        printf("%I64d\n",ans%mod);
    }
    return 0;
}

C.

利用莫比乌斯函数的性质和u(lcm(i,j)） = u(i)*u(j)*u(gcd(i,j))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef complex<double> comp;
const double pi = acos(-1);
const int mx = 1e6+10;
const int mod = 1e9 + 7;
int mu[mx],pri[mx/10],pre[mx];
bool vis[mx];
vector <int> g[mx];
void init(){
    int top = 0;
    mu[1] = 1;
    for(int i=2;i<mx;i++){
        if(!vis[i]){
            pri[top++] = i;
            mu[i] = -1;
        }
        for(int j=0;j<top&&pri[j]*i<mx;j++){
            int val = i*pri[j];
            vis[val] = 1;
            if(i%pri[j]==0){
                mu[val] = 0;
                break;
            }
            mu[val] = -mu[i];
        }
    }
    for(int i=1;i<mx;i++){
        g[i].push_back(0);
        int sum = 0;
        for(int j=i;j<mx;j+=i){
            sum += mu[j];
            g[i].push_back(sum);
            pre[j] += mu[i]*mu[j/i];
        }
    }
}
int main()
{     
    init();
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        int mi = min(n,m);
        ll ans = 0;
        for(int i=1;i<=mi;i++){
            ans += 1ll*pre[i]*g[i][n/i]*g[i][m/i];
        }
        printf("%lld\n",ans);
    }
    return 0;
}