Codeforces Round #430 (Div. 2)

A. Kirill And The Game

题意:一个人去买药,药店有在$range[l,r]$经验值 $range[x,y]$花费的药,问给定一个经验值和花费的比例有没有药可以买到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int l,r,x,y;
double k;
const double eps=1e-6;
int main()
{
scanf("%d%d%d%d%lf",&l,&r,&x,&y,&k);
for(int i=l;i<=r;i++){
double tmp=(double)i/k;
if(fmod((double)i/k,(int)((double)i/k))<=eps && (int)tmp>=x && (int)tmp<=y) {
printf("YES\n");exit(0);
}
}
printf("NO\n");
return 0;
}

B. Gleb And Pizza

题意:有个披萨饼,有内圆为主要部分,其他部分是外壳,告诉内圆半径,披萨半径,火腿的位置和半径,问有多少完全在外壳上的火腿

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+5;
double r,d;
int n;
double x[maxn],y[maxn],R[maxn];
int main()
{
scanf("%lf%lf",&r,&d);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&x[i],&y[i],&R[i]);
int ans=0;
for(int i=1;i<=n;i++){
if(R[i]<=d){
double dis=sqrt((double)x[i]*x[i]+(double)y[i]*y[i]);
if(dis>=(double)r-d+R[i] && dis<=r-R[i]) ans++;
}
}
printf("%d\n",ans);
return 0;
}

C. Ilya And The Tree

题意:给定一棵树和它各个点的权值,对于一个结点它的美丽值是指他到根的路径上所有点权值的最大公约数,对于每个结点到根的路径,可以修改一个点的权值到0,问每个点的最大美丽值

考虑每个节点,它的美丽值应该是根的一个约数或者除根以外所有数的最大公约数,因为如果不修改根,那么美丽值一定能整除根的权值。考虑枚举根的权值的约数,更新不修改根时的美丽值;至于修改根时的答案也可以一次dfs实现,时间复杂度总体应该是$O(n+log(w_{1}))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
const int maxn=200000+5;
vector<int> g[maxn];
void addedge(int from,int to){
g[from].push_back(to);
g[to].push_back(from);
}
int n;
int a[maxn];
int ans[maxn],ans2[maxn];
int getgcd(int x,int y){
return y==0?x:getgcd(y,x%y);
}
void dfs(int v,int fa,int gcd,bool remov)
{
if(a[v]%gcd!=0){
if(!remov){
remov=true;
ans[v]=max(ans[v],gcd);
}else return;
}else ans[v]=max(ans[v],gcd);
for(int i=0;i<(int)g[v].size();++i){
int u=g[v][i];
if(u!=fa){
dfs(u,v,gcd,remov);
}
}
return;
}
void dfs2(int v,int fa,int gcd)
{
if(v!=1) ans2[v]=gcd=getgcd(a[v],gcd);
for(int i=0;i<(int)g[v].size();++i){
int u=g[v][i];
if(u!=fa){
dfs2(u,v,gcd);
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=0;i<n-1;++i){
int from,to;
scanf("%d%d",&from,&to);
addedge(from,to);
}
vector<int > ys;
for(int i=1;i*i<=a[1];++i){
if(a[1]%i==0){
ys.push_back(i);
if(a[1]/i!=i) ys.push_back(a[1]/i);
}
}
sort(ys.begin(),ys.end());
for(int i=(int)ys.size()-1;i>=0;i--){
dfs(1,-1,ys[i],false);
}
dfs2(1,-1,0);
ans2[1]=a[1];
for(int i=1;i<=n;i++){
printf("%d ",max(ans[i],ans2[i]));
}puts("");
return 0;
}

D. Vitya and Strange Lesson

题意:给定一个$n$个元素的序列,和$m$个询问($n,m\leq 3\times 10^{5}$),每次询问是给定一个数,将序列所有数都异或上这个数,然后输出异或以后整个序列的$mex$值

这个我们考虑维护一个$trie$(存每个数的二进制),如果我们每次异或上一个数都交换01叉的话,会发现我们必须得倒着每个数的$bitset$建树,这样的话不仅复杂度没有保证(异或对应位上的那个深度的所有01叉都要交换一遍),而且不能很快求出序列的$mex$值。于是我们考虑不修改这个$trie$,由于异或操作是具有右结合性质的,我们考虑把每一位上异或过的结果记下来为inv数组,然后我们求$mex$的时候每一位我们只需要考虑和$inv$数组的这一位尽量相同即可(即尽可能地为0)。什么时候不能为0呢?当这个叉的结点已经满了的时候,即子树大小为$2^{i+1}-1$的时候,我们只能选与这一位不同的那个叉继续搜寻下去。复杂度$O(mlog(a))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
const int maxn=3*100000+5;
const int max_log_n=20;
const int siz=2;
struct node{
int id,book,size;
int ch[2];
}pool[maxn*max_log_n];
int n,m,poi=0;
int inv[max_log_n];
void Insert(int x,int id){
int u=0;
for(int i=max_log_n-1;i>=0;--i){
int bt=(x>>i)&1;
if(pool[u].ch[bt]==0){
pool[u].ch[bt]=++poi;
}
u=pool[u].ch[bt];
}
pool[u].book=id;
}
int fac[max_log_n];
void pre()
{
fac[0]=1;
for(int i=1;i<20;i++) fac[i]=fac[i-1]*2;
}
int Getmex()
{
int ret=0,to=0;
int u=0;
for(int i=max_log_n-1;i>=0;--i){
to=inv[i];
if(pool[pool[u].ch[to]].size==fac[i+1]-1){
to^=1;
ret|=(1<<i);
}
u=pool[u].ch[to];
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
pre();
int x;
for(int i=1;i<=n;++i){
scanf("%d",&x);
Insert(x,i);
}
for(int i=poi;i>=0;--i){
pool[i].size=1;
if(pool[i].ch[0]!=0) pool[i].size+=pool[pool[i].ch[0]].size;
if(pool[i].ch[1]!=0) pool[i].size+=pool[pool[i].ch[1]].size;
}
for(int i=0;i<m;++i){
scanf("%d",&x);
for(int j=max_log_n-1;j>=0;j--){
inv[j]^=(x>>j)&1;
}
printf("%d\n",Getmex());
}
return 0;
}

E. Nikita and game

题意:给你一棵树,每次加一条边,要求每次输出所有直径两端的点的个数($m\leq 3\times 10^5$)

这个暴力其实就可以了…用两个set维护一下两个端点的结点集合,然后加完边后根据直径变化不断改变集合,复杂度的话其实发现每个点如果被set弹出,那么自然不会有再加入的机会,也就是每个点最多被加入和弹出一次,那么其实是接近$O(m)$的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
int readint()
{
char c;int tmp=0,x=1;c=getchar();
while(!isdigit(c)){if(c=='-') x=-1;c=getchar();}
while(isdigit(c)){tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
const int maxn=3*100000+5;
const int max_log_n=20;
int pa[max_log_n][maxn],dep[maxn];
int m;
int getdis(int u,int v){
if(dep[u]>dep[v]) swap(u,v);
int ret=0;
for(int k=max_log_n-1;k>=0;k--){
if((dep[v]-dep[u])&(1<<k)) ret+=(1<<k),v=pa[k][v];
}
if(u==v) return ret;
else{
for(int k=max_log_n-1;k>=0;k--){
if(pa[k][v]!=pa[k][u] && pa[k][v]!=-1 && pa[k][u]!=-1)
v=pa[k][v],u=pa[k][u],ret+=(1<<(k+1));
}
return ret+2;
}
}
void out(int lim)
{
puts("");
for(int i=1;i<=lim;i++){
printf("point %d:\n",i);
for(int j=0;j<max_log_n;j++){
printf("pa[%d][%d]=%d\n",j,i,pa[j][i]);
}puts("");
}
puts("");
}
int main()
{
m=readint();
set<int > s1,s2;
s1.insert(1);dep[1]=1;
memset(pa,-1,sizeof(pa));
int dia=0;
for(int v=2;v<=m+1;++v){
int u;u=readint();
pa[0][v]=u;dep[v]=dep[u]+1;
int k=1;
while(pa[k-1][v]!=-1)
{
pa[k][v]=pa[k-1][pa[k-1][v]];
k++;
}
int dis1=0,dis2=0;
if(!s1.empty()) dis1=getdis(v,*(s1.begin()));
if(!s2.empty()) dis2=getdis(v,*(s2.begin()));
int dismx=max(dis1,dis2);
if(dismx>dia){
dia=dismx;
if(dismx==dis1){
for(set<int >::iterator ite=s2.begin();ite!=s2.end();++ite){
if(getdis(*ite,v)==dismx) s1.insert(*ite);
}
s2.clear();s2.insert(v);
}else if(dismx==dis2){
for(set<int >::iterator ite=s1.begin();ite!=s1.end();++ite){
if(getdis(*ite,v)==dismx) s2.insert(*ite);
}
s1.clear();s1.insert(v);
}
}else if(dismx==dia){
if(dis1>=dis2) s2.insert(v);
else s1.insert(v);
}
printf("%d\n",(int)s1.size()+(int)s2.size());
}
return 0;
}