Avito Cool Challenge 2018(div1+2)

A. Definite Game：

题意：输入N，输出最小的结果N-x，其中x不少N的因子。

思路：N=2时，输出2；其他情况输出1；因为N>2时，N-1不会是N的因子。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=2000010;
int a[maxn];
int main()
{
    int N; cin>>N;
    if(N==2) puts("2");
    else puts("1");
    return 0;
}

View Code

B. Farewell Party

题意：有N个人，有N中帽子，N个数，表示多少人与他的帽子不同。

思路：把问题转维有多少个人帽子和他相同，然后数字相同的分到同一组，而且人数是数字的倍数，因为同一组的还要均分。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=2000010;
int a[maxn],ans[maxn],vis[maxn],cnt,num[maxn];
int main()
{
    int N; cin>>N; bool F=true;
    rep(i,1,N) scanf("%d",&a[i]),a[i]=N-a[i];
    rep(i,1,N) num[a[i]]++;
    rep(i,1,N) if(num[i]%i!=0) {F=false; break;}
    rep(i,1,N){
        if(num[a[i]]%a[i]==0) vis[a[i]]=++cnt;
        ans[i]=vis[a[i]];
        num[a[i]]--;
    }
    if(!F) puts("Impossible");
    else {
        puts("Possible");
        rep(i,1,N) printf("%d ",ans[i]);
    }
    return 0;
}

View Code

C. Colorful Bricks

题意：有N个地板，有M种颜色，有K个地板与左边的不相同。

思路：数据量不难写出二维DP，方程为，dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(M-1)；（也可以用组合数来做，不过这个数据没必要想太多

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=2010;
const int Mod=998244353;
int dp[maxn][maxn];
int main()
{
    int N,M,K;
    scanf("%d%d%d",&N,&M,&K);
    dp[1][0]=M;
    rep(i,2,N) {
        rep(j,0,i-1){
            if(j==0) dp[i][j]=dp[i-1][j];
            else dp[i][j]=(dp[i-1][j]+1LL*dp[i-1][j-1]*(M-1)%Mod)%Mod;
        }
    }
    printf("%d
",dp[N][K]);
    return 0;
}

View Code

D. Maximum Distance

题意：题意很搅，这里的距离表示最小的路径最大值，就是让你求一个最小生成树（满足路径最大值最小），在生成树上有K个关键点，你的任务是对于每个关键点，找离他最远的关键点，输出距离。

思路：K个点的虚树，是所有两两路径经过的边集并，我们求这个边集并的最大值就是结果，因为我们可以保证他过这条边。其他写法容易挂，具体为什么暂时不知道。（虚树可以换成并查集？）

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=200010;
int a[maxn],Laxt[maxn],Next[maxn],To[maxn],Len[maxn],cnt,ans;
struct in{
    int u,v,len;
    friend bool operator <(in a,in b){ return a.len<b.len; }
}s[maxn];
int in[maxn],fa[maxn][19],dep[maxn],vis[maxn],times,fcy[maxn];
bool cmp(int x,int y) { return in[x]<in[y]; }
void add(int u,int v,int c) { Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v;Len[cnt]=c;}
void dfs(int u,int f)
{
    in[u]=++times; fa[u][0]=f; dep[u]=dep[f]+1;
    for(int i=Laxt[u];i;i=Next[i]){
        if(To[i]!=f) fcy[To[i]]=Len[i],dfs(To[i],u);
    }
}
int LCA(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=18;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=18;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
int ac[maxn];
int find(int x){
    if(ac[x]!=x) return ac[x]=find(ac[x]); return x;
}
int main()
{
    int N,M,K;
    scanf("%d%d%d",&N,&M,&K);
    rep(i,1,K) scanf("%d",&a[i]);
    rep(i,1,M){
        scanf("%d%d%d",&s[i].u,&s[i].v,&s[i].len);
    }
    sort(s+1,s+M+1);
    rep(i,1,N) ac[i]=i;
    rep(i,1,M){
        int fau=find(s[i].u);
        int fav=find(s[i].v);
        if(fau!=fav) {
            ac[fau]=fav;
            add(s[i].u,s[i].v,s[i].len);
            add(s[i].v,s[i].u,s[i].len);
        }
    }
    dfs(1,0);
    sort(a+1,a+K+1,cmp);
    int tot=K;
    rep(i,2,K) a[++tot]=LCA(a[i-1],a[i]);
    sort(a+1,a+tot+1,cmp);
    tot=unique(a+1,a+tot+1)-(a+1);
    rep(i,1,tot) vis[a[i]]=1; //得到关键点
    rep(i,1,tot){   //关键点之间连边得到新树
        int u=a[i];
        while(true){
            if(u==a[1]) break;
            ans=max(fcy[u],ans); u=fa[u][0];
            if(vis[u]||u==0) break;
        }
    }
    rep(i,1,K) printf("%d ",ans);
    return 0;
}

View Code

E. Missing Numbers

题意：一个偶数N的序列，我们给出了偶数位置的数，让你填补奇数位置的数，满足所有前缀和的完全平方数。

思路：因为都是完全平方数，注意到完全平方数的相邻差值递增，我们可以利用这个单调性来搜索，或者单调队列什么的。我是二分写的，好像有点丑。过了就行。。。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;i++)
using namespace std;
const int maxn=3300010;
const ll inf=1e13;
ll p[maxn],a[maxn],b[maxn],ans[maxn],cnt,N; //3162277
int main()
{
    for(ll i=1;;i++){
        if(i*i>inf) break;
        p[++cnt]=i*i;
    }
    bool F=true;
    scanf("%lld",&N);
    rep(i,1,N/2){
        scanf("%lld",&a[i]);
    }
    if(!F) return puts("No"),0;
    ll BG=-1LL;
    rep(i,0,cnt){
        ll pos=lower_bound(p+1,p+cnt+1,p[i]+a[1])-p;
        if(pos>=2&&p[pos]==p[i]+a[1]){
            ans[1]=p[pos]-a[1];
            ll kk=lower_bound(p+1,p+cnt+1,ans[1])-p;
            if(p[kk]==ans[1]){ BG=pos; break;}
        }
    }
    if(BG==-1LL) return puts("No"),0;
    ans[2]=a[1]; ll fcy=BG;
    for(ll i=2;i<=N/2&&fcy<=cnt;i++){
        while(fcy<=cnt){
            ll pos=lower_bound(p+1,p+cnt+1,p[fcy]+a[i])-p;
            if(pos>=BG+2&&p[pos]==p[fcy]+a[i]){
                ll tmp=p[pos]-a[i];
                ll hhh=lower_bound(p+1,p+cnt+1,tmp)-p;
                if(p[hhh]==tmp) {ans[i*2]=a[i]; ans[i*2-1]=p[pos]-p[BG]-a[i]; BG=pos; fcy=BG; break;}
                else fcy++;
            }
            else fcy++;
        }
    }
    rep(i,1,N) if(ans[i]<1LL||ans[i]>inf) return puts("No"),0;
    puts("Yes");
    rep(i,1,N) printf("%lld ",ans[i]);
    return 0;
}

View Code