2018-04-04Codeforces Round #473

A
水题
B

这里我用了并查集，因为我以为 分组 1个单词可以在不同组，但是这个题目好像不用考虑在不同组。

#include<bits/stdc++.h>
using namespace std;
#define N 100005
typedef long long ll;
int n,k,m;
map<string,int>ma;
ll mh[N];
int pre[N];
int fun(int x){

if(x!=pre[x])
{

    pre[x]=fun(pre[x]);
}
return  pre[x];
}
int main()
{
    int m;
   scanf("%d%d%d",&n,&k,&m);
   string s;

   for(int i=1;i<=n;i++){
    cin>>s;
    ma[s]=i;
    pre[i]=i;
   }

    for(int i=1;i<=n;i++){
        scanf("%lld",&mh[i]);
    }
    int t;int a,b;
    for(int i=0;i<k;i++){

        scanf("%d",&t);
        scanf("%d",&a);
        for(int j=1;j<t;j++){
          scanf("%d",&b);
          int fa,fb;
          fa=fun(a);
          fb=fun(b);
          if(mh[fa]>mh[fb]){
            pre[fa]=fb;
          }else pre[fb]=fa;
          a=b;
        }
    }
    ll ans=0;
    for(int i=0;i<m;i++){
        cin>>s;
        int p=ma[s];
      //  cout<<p<<endl;
        p=fun(p);
        ans+=mh[p];
    }
    printf("%lld\n",ans);
    return 0;
}

C
找规律吧，我还是找复杂了，正确的情况可以全部跟1相连，不正确两层的情况，可以第二层直接跟2相连

#include<bits/stdc++.h>
using namespace std;
#define N 100005
typedef long long ll;

map<string,int>ma;
ll mh[N];
int pre[N];
int n;
void fun2(){
for(int i=2;i<=n;i++){
    printf("%d  %d\n",i-1,i);
}

}

void fun1(){
    int i;
for(i=1;i<=n/2;i++){
    printf("%d  %d\n",1,i+1);
}
for(i;i<n;i++){
    printf("%d  %d\n",n/2+1,i+1);
}
}
int main()
{

   scanf("%d",&n);
    if(n<6){
        printf("-1\n");
        fun2();
    }else{
    fun1();fun2();

    }
    return 0;
}

D
参考的别人的代码，当时 是从 总体出发，就不知道怎么做了T - T,还是要逐个击破

好坑啊， ai 小于10万 但是 产生的序列可能超过 100万，数组开小了

#include<bits/stdc++.h>
using namespace std;
#define N 500005

int n;
bool vis[N];
int main(){
    scanf("%d",&n);
    int a;
    int ans=0;
    int l=2;
    int flag=0;
    for(int i=0;i<n;i++){
        scanf("%d",&a);
        while(vis[l]==true)l++;
        ans=l;
        if(!flag)
            ans=max(l,a);
        while(vis[ans])ans++;
        printf("%d%c",ans,i==n-1?'\n':' ');
        if(ans>a)
            flag=1;
        if(ans>a)
            flag=1;
        for(int d=l;d*d<=ans;d++){

            if(ans%d==0)
            {

               while(ans%d==0&&ans)
                ans/=d;
                for(int x=d;x<=N;x+=d){
                    vis[x]=1;
                }
            }
        }
        if(ans>1){
            for(int x=ans;x<=N;x+=ans){
                    vis[x]=1;
                }
        }
    }
return 0;}

E
规律其实找出来了，就是 （i&-i）求和，看了别人的代码，长知识了，以后会求和了 开心
注意 1LL 不然会出错 ！！！！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n=0,k=0,ans=0;
    cin>>n;
    while(n>1){
        ans+=(n>>1)*(1ll<<k);
        n-=(n>>1);
        k++;
    }
    cout<<ans<<endl;
  
return 0;}

F