埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 解题报告(持续更新中)

前言

A.Wasserstein Distance

思路:贪心,从左到右扫一遍保证前i个都被填平了即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=100000+10;
int T,n,i,a[N],b[N];
ll res;
int main(){
    for (read(T);T--;){
        read(n);
        for (i=1;i<=n;i++) read(a[i]);
        for (i=1;i<=n;i++) read(b[i]);
        for (res=0,i=1;i<=n;i++){
            if (a[i]<b[i]){
                res+=b[i]-a[i];
                a[i+1]-=b[i]-a[i];
            }
            else if (a[i]>b[i]){
                res+=a[i]-b[i];
                a[i+1]+=a[i]-b[i];
            }
        }
        printf("%lld\n",res);
    } 
    return 0;
}

B.合约数

思路:考虑到val的范围很小,所以先预处理出[1,10000]内每个数的合约数,然后DsuOnTree,开个桶记录每个val出现的次数,每次子树递归完后暴力统计就好了,时间复杂度O(nlogn)

#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}               
const int N=20000+10;
const int M=10000+10;
const int P=1000000007;
int T,n,i,u,v,root,ans,skip,cnt[M],sz[N],son[N],val[N],primes[M];
bool isPrime[M];
vector<int>G[N],fac[M];
void init(){
    for (int i=2;i<=10000;i++){
        if (!isPrime[i]) primes[++primes[0]]=i;
        for (int j=1;j<=primes[0]&&i*primes[j]<=10000;j++){
            isPrime[i*primes[j]]=1;
            if (i%primes[j]==0) break;
        } 
    }
    for (int i=2;i<=10000;i++)if(isPrime[i]){
        for (int j=i;j<=10000;j+=i){
            fac[j].PB(i);
        }
    }
}
void dfs(int u,int f){
    sz[u]=1,son[u]=-1;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if (son[u]==-1||sz[v]>sz[son[u]]) son[u]=v;
    }
}
void Count(int u,int f,int add){
    cnt[val[u]]+=add;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f || v==skip) continue;
        Count(v,u,add);
    }
}
void up(int&a,int b){a+=b;if(a>=P)a-=P;}
void dfs(int u,int f,bool keep){
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f || v==son[u]) continue;
        dfs(v,u,0);
    }
    if (son[u]!=-1) dfs(son[u],u,1),skip=son[u];
    Count(u,f,1);
    int res=0;
    for (int i=0;i<(int)fac[val[u]].size();i++) up(res,cnt[fac[val[u]][i]]);
    up(ans,1LL*res*u%P);
    skip=-1;
    if (!keep) Count(u,f,-1);
}
int main(){
    init();
    for (read(T);T--;){
        read(n),read(root);
        memset(cnt,0,sizeof(cnt));
        for (ans=0,i=1;i<=n;i++) G[i].clear();
        for (i=1;i<n;i++){
            read(u),read(v);
            G[u].PB(v);
            G[v].PB(u);
        }
        for (i=1;i<=n;i++) read(val[i]);
        dfs(root,0);
        dfs(root,0,0);
        printf("%d\n",ans);
    }
    return 0;
}

D.数字游戏

思路:考虑到当[L2,R2]的区间长度大于模数的时候对手就获得了[0,mod-1]所有的选择,不管先手怎么选都可以选一个数使最后的结果为0,此时先手必败,否则先手必胜。

#include <bits/stdc++.h>
using namespace std;
int T,L1,R1,L2,R2,mod;
int main(){
    for (cin>>T;T--;){
        cin>>L1>>R1>>L2>>R2>>mod;
        if (R2-L2+1>=mod) puts("LOSE");
        else puts("WIN");
    }
    return 0;
}

E.小Y吃苹果

思路dfs爆搜

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
int n;
set<int>S;
void dfs(int index,int num){
    if (index==n){
        S.insert(num);
        return;
    }
    dfs(index+1,num*2-1);
    dfs(index+1,num*2);
}
int main(){
    read(n);
    dfs(0,1);
    printf("%d\n",S.size());
    return 0;
}

L.K序列

思路:感觉自己意识模糊...居然写了1小时..脑子里总有些奇奇怪怪的想法...开一个dp数组,dp[i][j]表示到i位置子序列和模kj的最长子序列数,转移比较显然,然后由于每次只和上一层的dp值有关,所以优化掉第一维,用一个数组存上一层的dp数组,每次从上一层的dp值转移过来就好了,时间复杂度O(nk)

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e7+10;
const int M=1e5+10;
int n,k,i,j,a[M],mx[N],mxtmp[N];
int main(){
    read(n),read(k);
    for (i=1;i<=n;i++) read(a[i]),a[i]%=k;
    for (mxtmp[a[1]]=1,i=2;i<=n;i++){
        mxtmp[a[i]]=max(mxtmp[a[i]],1);
        for (j=0;j<k;j++)if(mxtmp[j]){
            int tmp=j+a[i];
            if (tmp>=k) tmp-=k;
            mx[tmp]=max(mx[tmp],mxtmp[j]+1);
        }
        for (j=0;j<k;j++){
            mxtmp[j]=max(mxtmp[j],mx[j]);
            mx[j]=0;
        }
    }
    printf("%d\n",mxtmp[0]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注