codeforces411div.2

每日CF:

411div2

Solved		A	CodeForces 805A	Fake NP
Solved		B	CodeForces 805B	3-palindrome
Solved		C	CodeForces 805C	Find Amir
Solved		D	CodeForces 805D	Minimum number of steps
Attempted		E	CodeForces 805E	Ice cream coloring
		F	CodeForces 805F	Expected diameter of a tree

点题号阅读题面

---------

A

题意:

给a,b,求[a,b]中所有整数的所有除数中,最多的一个

分析:

水题,直接看代码

/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime: 
***********************/
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;
int n,m,k;
int main(){
//#define test
#ifdef test
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    
    cin>>n>>m;
    if(m==n) cout<<m;
    else cout<<2;
    
    
#ifdef test
    fclose(stdin);
  fclose(stdout);
    system("out.txt");
#endif
    return 0;
}

---------

B

题意:

求一个长度为n的字符串,由a,b,c三个字符组成

要求不能出现长度为3的回文串,且c的出现次数最低

分析:

是不出现长度''恰好''好为3的回文串

经过简单的思考和实验,

显然aabb的无限重复,只会出现长度为偶数的回文串,符合题意

/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:20min
*@DateTime:2018-02-02 16:16:38
***********************/
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;
int n,m,k;

int main(){
//#define test
#ifdef test
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    cin>>n;
    for(int i=1;i<=n;i++){
        if(i%4==1||i%4==2)printf("a");
        else printf("b");
    }
#ifdef test
    fclose(stdin);
  fclose(stdout);
    system("out.txt");
#endif
    return 0;
}

-----

C

题意:

1-n一共n个节点,两个节点之间的距离等于两个节点编号之和对n+1取模,每次访问完两个节点,两个节点的距离花费为0

求遍历所有点的最小花费

分析:

显然,i+j==n+1时最优,次优为i+j==n+2

具体看代码

/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime:2018-02-02 16:16:38
***********************/
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;
int n,m,k;

int main(){
//#define test
#ifdef test
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    cin>>n;
    if(!(n&1)) cout<<n/2-1;
    else cout<<n/2;
#ifdef test
    fclose(stdin);
  fclose(stdout);
    system("out.txt");
#endif
    return 0;
}

-----

D

题意:

给一个由a,b组成的字符串,进行如下操作:

　　把所有"ab"子串,换为"bba"

求最少的操作次数,答案对1e9+7取余

分析:

递推题

如果是简单的"ab"换为"ba",很明显答案就是整个字符串进行冒泡排序的次数

但这里换成的"bba",显然,本质上依然是冒泡排序

但是每次交换会多出来一个b,也就是简单的递推

预打表操作n次后的冒泡次数

再预处理每个位置之前a的个数

求和即可

/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime:2018-02-02 16:16:38
***********************/
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
int n,m,k;
char s[maxn];
int numa[maxn];
int ans[maxn];
int main(){
//#define test
#ifdef test
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    ans[1]=1;
    for(int i=2;i<=maxn;i++){
        ans[i]=(((ans[i-1]<<1)%mod)+1)%mod;
    }
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++){
        numa[i]=numa[i-1];
        if(s[i]=='a')numa[i]++;
    }
    long long time=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='b')time=(time+ans[numa[i]])%mod;
    }
    cout<<time<<endl;
#ifdef test
    fclose(stdin);
  fclose(stdout);
    system("out.txt");
#endif
    return 0;
}

-----

E

没写完E...题意比较麻烦,读错了

题意:

给一个树,每个节点包含一个数字集合,其中有相同元素的节点一定组成一个连通子图

然后建立一个新图,把树上所有有相同元素的连边,组成一个完全子图

接下来进行图上的染色,最终保证所有相邻点没有一样的颜色

求所有颜色和一种染色方式

分析:

(出来看了题解,写出来的)

图论思维题,树上的dfs

所有相邻点一定构成一个连通子图,就意味着所有一样颜色的点一定在同样一个子树上

然后新图中连边,显然所有有一样元素的节点一定是相邻的

具体过程采用dfs,由于原图中颜色一样就在一个子树上,所以直接dfs不会出现问题

注意,可能会出现节点是空集合,注意避免

/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime: 2018-02-02 17:15:12
***********************/
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int maxm=1e6+10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
typedef set<int>::iterator sit;
int n,m,k;
set<int>s[maxn];
vector<int>g[maxn];
int ans[maxn];
int head[maxn],nume;
int cnt;
struct node{
    int to,next;
}e[maxm];
void add(int a,int b){
    e[nume]=(node){b,head[a]};
    head[a]=nume++;
}
void dfs(int now,int pre){
    vector<int>vis;
    sit end=s[now].end();
    if(pre==-1){
        for(sit i=s[now].begin();i!=end;i++){
            ans[(*i)]=++cnt;
        }
    }else {
        for(sit i=s[now].begin();i!=end;i++){
            if(ans[(*i)]){
                vis.push_back(ans[(*i)]);
            }
        }
        sort(vis.begin(),vis.end());
        int num=vis.size();
        int j=0,son=1;
        for(sit i=s[now].begin();i!=end;i++){
            if(!ans[(*i)]){
                while(j<num){
                    if(son==vis[j]){
                        j++,son++;
                    }
                    else break;
                }
                ans[(*i)]=son++;
            }
            cnt=max(cnt,son-1);
        }
    }
    for(int i=head[now];~i;i=e[i].next){
        int to=e[i].to;
        if(to!=pre){
            dfs(to,now);
        }
    }
}


int main(){
//#define test
#ifdef test
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int n,m;
    memset(head,-1,sizeof head);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int a;
        scanf("%d",&a);
        for(int j=0;j<a;j++){
            int b; 
            scanf("%d",&b);
            s[i].insert(b);
        }
    }
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    memset(ans,0,sizeof ans);
    cnt=0;
    dfs(1,-1);
    printf("%d
",max(1,cnt));
    for(int i=1;i<=m;i++){
        if(ans[i])printf("%d ",ans[i]);
        else printf("1 ");
    }
#ifdef test
    fclose(stdin);
  fclose(stdout);
    system("out.txt");
#endif
    return 0;
}