每日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+;
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<<; #ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}
---------
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+;
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=;i<=n;i++){
if(i%==||i%==)printf("a");
else printf("b");
}
#ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}
-----
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+;
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&)) cout<<n/-;
else cout<<n/;
#ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}
-----
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+;
const int mod=1e9+;
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[]=;
for(int i=;i<=maxn;i++){
ans[i]=(((ans[i-]<<)%mod)+)%mod;
}
scanf("%s",s+);
n=strlen(s+);
for(int i=;i<=n;i++){
numa[i]=numa[i-];
if(s[i]=='a')numa[i]++;
}
long long time=;
for(int i=;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 ;
}
-----
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+;
const int maxm=1e6+;
const int mod=1e9+;
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==-){
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=,son=;
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-);
}
}
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,-,sizeof head);
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
int a;
scanf("%d",&a);
for(int j=;j<a;j++){
int b;
scanf("%d",&b);
s[i].insert(b);
}
}
for(int i=;i<n-;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
memset(ans,,sizeof ans);
cnt=;
dfs(,-);
printf("%d\n",max(,cnt));
for(int i=;i<=m;i++){
if(ans[i])printf("%d ",ans[i]);
else printf("1 ");
}
#ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}