XJ疫情邀请赛

· · 个人记录

传送门

中文题面

虽然没有参加比赛(其实是报名的时候遇到小问题最后因为懒所以就没参加

但还是打算把题补补上

<!-- more -->

A.核酸检测

看看时间差不多就该心领神会了。

考虑构造线路，DNA形排列。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<cstdlib>//rand()
#define rep(i,a,b) for(register int i = (a);i <= (b);++i)
#define per(i,a,b) for(register int i = (a);i >= (b);--i)
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;

int n,t,now;

int main(){
    cin >> n;
    if(n & 1){ // 奇数行
        t = (n - 1) / 2 , now = n;   
        cout << (n * n + n) - 1 << "\n";     
        while(t--){
            rep(i,1,n + 1) cout << now + (i & 1) - 1 << " " << i << "\n";
            per(i,n + 1,1) cout << now + (!(i & 1)) - 1 << " " << i << "\n";
            now -= 2;
        }
        rep(i,1,n + 1) cout << 1 << " " << i << "\n";
    } else { // 偶数行
        t = n / 2 , now = 1;
        cout << (n * n + n) - 1 << "\n";
        while(t--){
            rep(i,1,n) cout << i << " " << now + (!(i & 1)) << "\n";
            per(i,n,1) cout << i << " " << now + (i & 1) << "\n";
            now += 2;
        }
        rep(i,1,n) cout << i << " " << n + 1 << "\n"; 
    }
    return 0;
}

B.齐心抗疫

ans = max(max(a_x,a_y) * dis(x,y))

寻找树的直径端点，答案存在于端点到任意点的连线中。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<cstdlib>//rand()
#define rep(i,a,b) for(register long long i = (a);i <= (b);++i)
#define per(i,a,b) for(register long long i = (a);i >= (b);--i)
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;
ll n,a[55555],u,v,dis,ans;
ll next[111111],ver[111111],head[111111],tot;
inline void link(ll x,ll y){
    ver[++tot] = y , next[tot] = head[x] , head[x] = tot;
}
inline void dfs(ll now,ll father,ll depth){
    if(depth > dis) dis = depth , u = now;
    for(register int i = head[now];i;i = next[i]){
        if(ver[i] != father) dfs(ver[i],now,depth+1);
    }
}
inline void find(){
    dfs(1,0,0);
    dis = 0 , v = u;
    dfs(v,0,0);
}
inline void update(ll now,ll father,ll depth){
    ll sum = depth * std::max(a[u],a[now]);
    ans = std::max(sum,ans);
    for(register int i = head[now];i;i = next[i]){
        if(ver[i] != father) update(ver[i],now,depth+1);
    }
}
int main(){
    cin >> n;
    rep(i,1,n) cin >> a[i];
    rep(i,1,n-1){
        cin >> u >> v;
        link(u,v) , link(v,u);
    }
    find();
    update(u,0,0);
    std::swap(u,v);
    update(u,0,0);
    cout << ans << "\n";
    return 0;
}