Codeforces Round 446 (Div. 1) 题解

施工中QwQ

A. Pride

首先如果原序列中已经有11 ,答案是nn减去11的个数。

否则一定是先构造出一个11,然后再用n1n-1步全部变成11

设最短的gcd\gcd11的区间长度为ll,那么答案为n+l2n+l-2

时间复杂度O(n2logai)O(n^2 \log a_i),维护不同的gcd\gcd可以做到O(nlog2ai)O(n \log^2 a_i)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("891A.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
int a[2003];
int main(){
    init();
    int n=readint(),ans=n+1;
    // puts("WTF");
    for(int i=1;i<=n;i++){
        a[i]=readint();
        int now=0;
        for(int j=i;j;j--){
            now=__gcd(now,a[j]);
            if (now==1){
                ans=min(ans,i-j+1);
                break;
            }
        }
    }
    // puts("WTF");
    if (ans>n)
        return puts("-1"),0;
    if (ans==1){
        int qwq=n;
        for(int i=1;i<=n;i++)
            qwq-=(a[i]==1);
        printf("%d\n",qwq);
        return 0;
    }
    printf("%d",ans-1+n-1);
}

B. Gluttony

一直在想状压DP,看了题解才发现n22n \leq 22只是因为spj需要O(2n)O(2^n)而已。

将每个数变成第一个比它大的数(如果不存在则变成最小的数)即可。

证明:

对于每个不包含原排列中最大数的下标集合显然成立,否则考虑取补集可以发现仍然成立。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("891B.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
pair<int,int> a[233];
int ans[233];
int main(){
    init();
    int n=readint();
    for(int i=1;i<=n;i++)
        a[i].first=readint(),a[i].second=i;
    sort(a+1,a+n+1);
    for(int i=1;i<n;i++)
        ans[a[i].second]=a[i+1].first;
    ans[a[n].second]=a[1].first;
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
}
//1 2 3 4
//2 3 4 1

C. Envy

算法导论上有这样一个结论:一张图的任何一个最小生成树均可以通过在Kruskal中改变相同权值的边的排列顺序得到。

于是考虑把每个询问中的边按权值分组,离线,然后在Kruskal的过程中判断一组中的边同时加入会不会产生环即可。需要带撤销的并查集,注意只需要按秩合并,路径压缩的复杂度是均摊的。

时间复杂度O((m+k)logn)O((m+\sum k) \log n)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=100000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("891C.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
const int maxn=500002;
struct dsu{
    int fa[maxn],rk[maxn];
    pair<int,int> stk[maxn*20];
    int tp;
    void init(int n){
        for(int i=1;i<=n;i++)
            fa[i]=i,rk[i]=0;
        tp=0;
    }
    void revert(int ver){
        while(tp!=ver){
            int x=stk[tp].first,y=stk[tp].second;
            if (x>0)
                fa[x]=y;
            else rk[-x]=y;
            tp--;
        }
    }
    int getf(int x){
        while(fa[x]!=x)
            x=fa[x];
        return x;
    }
    bool mer(int x,int y){
        x=getf(x),y=getf(y);
        if (x==y)
            return false;
        if (rk[x]>rk[y])
            swap(x,y);
        stk[++tp]=make_pair(x,fa[x]);
        stk[++tp]=make_pair(-y,rk[y]);
        fa[x]=y;
        rk[y]=max(rk[y],rk[x]+1);
        return true;
    }
}d;
struct edge{
    int u,v,w,id;
    bool operator <(const edge& rhs)const{
        return w<rhs.w;
    }
}e[maxn];
int to[maxn],lst[maxn];
struct query{
    int id;
    vector<int> a;
};
vector<query> q[maxn];
bool ans[maxn];
int main(){
    init();
    int n=readint(),m=readint();
    for(int i=1;i<=m;i++)
        e[i].id=i,e[i].u=readint(),e[i].v=readint(),e[i].w=readint();
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++){
        to[e[i].id]=i;
        lst[i]=e[i].w==e[i-1].w?lst[i-1]:i;
    }
    int cnt=readint();
    for(int i=1;i<=cnt;i++){
        ans[i]=1;
        int k=readint();
        while(k--){
            int p=to[readint()];
            if (q[lst[p]].empty() || q[lst[p]].back().id!=i)
                q[lst[p]].push_back((query){i});
            q[lst[p]].back().a.push_back(p);
        }
    }
    d.init(n);
    for(int i=1;i<=m;i++){
        if (q[i].size()){
            for(const auto& u:q[i]){
                int ver=d.tp;
                for(const auto& v:u.a){
                    if (!d.mer(e[v].u,e[v].v)){
                        ans[u.id]=0;
                        break;
                    }
                }
                d.revert(ver);
            }
        }
        d.mer(e[i].u,e[i].v);
    }
    for(int i=1;i<=cnt;i++)
        puts(ans[i]?"YES":"NO");
}

D. Sloth

留坑

E. Lust

设第ii个数被减了bib_i次。

首先归纳可证res=iaii(aibi)res=\prod_{i}a_i-\prod_{i}(a_i-b_i)

那么

Eres=i=1naik!nkb1+b2++bn=ki=1naibibi! \mathbb{E}_{res}=\prod_{i=1}^na_i-\frac{k!}{n^k}\sum_{b_1+b_2+\cdots+b_n=k}\prod_{i=1}^n\frac{a_i-b_i}{b_i!}

注意到

b1+b2++bn=ki=1n(aibi)=[xk]i=1nj=0kaijj!xj=[xk]i=1n(aiexxex)=[xk]enxi=1n(aix) \begin{aligned} \sum_{b_1+b_2+\cdots+b_n=k}\prod_{i=1}^n(a_i-b_i)&=[x^k]\prod_{i=1}^n\sum_{j=0}^k\frac{a_i-j}{j!}x^j \\ &=[x^k]\prod_{i=1}^n(a_ie^x-xe^x)\\ &=[x^k]e^{nx}\prod_{i=1}^n(a_i-x) \end{aligned}

i=1n(aix)=i=0ncixi\prod_{i=1}^n(a_i-x)=\sum_{i=0}^nc_ix^i,我们O(n2)O(n^2)暴力求出cc

于是

[xk]enxi=1n(aix)=i=0ncinki(ki)! [x^k]e^{nx}\prod_{i=1}^n(a_i-x)=\sum_{i=0}^nc_i\frac{n^{k-i}}{(k-i)!}

那么

时间复杂度O(n2)O(n^2)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("891E.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
const int mod=1000000007;
ll a[5003];
ll power(ll x,ll y){
    ll ans=1;
    while(y){
        if (y&1)
            ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
int main(){
    init();
    int n=readint();
    ll k=readint(),ans=1;
    a[0]=1;
    for(int i=1;i<=n;i++){
        ll x=readint();
        ans=ans*x%mod;
        for(int j=i-1;j>=0;j--){
            a[j+1]=(a[j+1]-a[j])%mod;
            a[j]=a[j]*x%mod;
        }
    }
    ll now=1,pw=1;
    ll inv=power(n,mod-2);
    for(int i=0;i<=n;i++){
        ans=(ans-now*pw%mod*a[i])%mod;
        now=now*(k-i)%mod;
        pw=pw*inv%mod;
    }
    printf("%lld",(ans%mod+mod)%mod);
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

本文链接:https://q234rty.top/2018/07/12/cf891/

隐藏