CodeForces 734 解题报告

思路

Problem A

线性扫一遍,然后数一下A和D的个数就好

Problem B

显然只有2是矛盾的,通过观察发现256越多越好。

所以2优先给256,然后给32。

Problem C

已知$spell2$的$c_i,d_i$不下降,我们将$spell1$按$b_i$从小到大排列。

然后由后往前枚举使用哪一种$spell2$,由于这样的话所需的$d_i$会不上升,所以剩余的$manapoints$不下降

然后我们可以依次将$spell1$添加进可选集合,维护一下最小的$a_i$即可

时间复杂度$O(n_1logn_1+n1+n2)$

Problem D

$King$的周围一共有八个方向,维护一下八个方向上离$King$最近的棋子

判断一下能不能将死即可

Problem E

首先若对一个点染色,将其连通的所有相同颜色点均染色显然是坠吼的

如此我们可以先对图上已有的连通块进行缩点,得到新的树

然后显然新树上任意相邻结点不同色,我们需要将整棵树变成一种颜色

考虑树的直径即可,设直径上点数$x$,答案为$x/2$向下取整

Problem F

经过q神提醒,有此结论:x&y+x|y=x+y

因此,我们对于某一个$i$,可以看出:$b_i+c_i=\sum_{j=1}^na_j+n*a_i$

那么$\sum_{i=1}^n(b_i+c_i)=2n*\sum_{i=1}^na_i$此可以作为一个判据

由此我们可以求出$\sum_{i=1}^na_i$,继而求出$a_i$

但是考虑以下情况(没错是某组数据)

1
2
3
1
3
5

我们会得到$a_1=4$,显然不对,答案应该是无解($-1$)

因此我们需要对得到的$a_i$ 进行检验

假如一个一个算,复杂度为$O(n^2)$,会超时

我们考虑贡献的做法

对于每个数$a_i$,我们考虑它每个二进制位对于答案做的贡献

即第$i$个二进制位为$0$,贡献为$0$,否则贡献为$2^{i-1}$

然后我们可以通过累和$sum_k=\sum_{i=1}^n{a_i的第k位的贡献}$

那么假设最大有$m$位二进制数

$b_i=\sum_{k=1}^m \begin{cases} sum_k& \text{a_i二进制第k位为1}\0&\text{a_i二进制第k位为0}\end{cases}$

$c_i=\sum_{k=1}^m \begin{cases} n*2^{k-1}& \text{a_i二进制第k位为1}\sum_k&\text{a_i二进制第k位为0}\end{cases}$

检验的时空复杂度均为$O(nm)$

$m$最大为$log_2{10^9}$

代码(不写贼长的头文件啦~)

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
char s[100005];
int a,d,n,i;

int main()
{
scanf("%d\n",&n);
gets(s);
for(i=0;i<n;i++)
if(s[i]=='A')a++;else d++;
if(a>d){printf("Anton");return 0;}
if(a<d){printf("Danik");return 0;}
if(a==d)printf("Friendship");
return 0;
}

B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int a,b,c,d;

int main()
{

int ans=0;
scan2(a,b);scan2(c,d);
int a1=min(c,d);
a1=min(a1,a);
ans+=256*a1;
a-=a1;
a=min(a,b);
ans+=32*a;
printf("%d",ans);
return 0;
}

C

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
const int maxn=200005;

struct spell
{
LL x,y;
bool operator < (const struct spell p)const
{return y<p.y;}
}a[maxn],b[maxn];

LL x,s,n,l,k;
int i,j,m1,m2;

int main()
{
scanf("%lld %d %d %lld %lld",&n,&m1,&m2,&x,&s);
for(i=1;i<=m1;i++)scanf("%lld",&a[i].x);
for(i=1;i<=m1;i++)scanf("%lld",&a[i].y);
sort(a+1,a+m1+1);
for(i=1;i<=m2;i++)scanf("%lld",&b[i].x);
for(i=1;i<=m2;i++)scanf("%lld",&b[i].y);
j=1;k=n*x;l=x;
for(i=m2;i>=1;i--)
{
if(b[i].y>s)continue;
while(j<=m1 && a[j].y<=s-b[i].y){l=min(l,a[j].x);j++;}
k=min(k,(n-b[i].x)*l);
}
while(j<=m1 && a[j].y<=s){l=min(l,a[j].x);j++;}
k=min(k,n*l);
printf("%lld",k);
return 0;
}

D(太丑捂脸)

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
struct point
{
LL x,y;
bool operator == (const struct point p)const
{return x==p.x && y==p.y;}
}king,now,pos[20],ch[500005];

char c[500005];

int i,j,k,l,m,n;

/*
* 123
* 4k5
* 678
*/

bool pd(point t)
{
if(t.x==king.x || t.y==king.y)return true;
if(t.x+t.y==king.x+king.y)return true;
if(t.x-t.y==king.x-king.y)return true;
return false;
}

void upd(point t)
{
if(t.x==king.x)
{
if(t.y>king.y)
{
if(pos[2].y==king.y || pos[2].y>t.y)pos[2].y=t.y;
return;
}
if(t.y<king.y)
{
if(pos[7].y==king.y || pos[7].y<t.y)pos[7].y=t.y;
return;
}
}
if(t.x>king.x)
{
if(t.y==king.y)
{
if(pos[5].x==king.x || pos[5].x>t.x)pos[5].x=t.x;
return;
}
if(t.y<king.y)
{
if(pos[8]==king || t.y>pos[8].y)pos[8]=t;
return;
}
if(t.y>king.y)
{
if(pos[3]==king || t.y<pos[3].y)pos[3]=t;
return;
}
}
if(t.x<king.x)
{
if(t.y==king.y)
{
if(pos[4].x==king.x || pos[4].x<t.x)pos[4].x=t.x;
return;
}
if(t.y<king.y)
{
if(pos[6]==king || t.y>pos[6].y)pos[6]=t;
return;
}
if(t.y>king.y)
{
if(pos[1]==king || t.y<pos[1].y)pos[1]=t;
return;
}
}
}

int main()
{
scanf("%d %lld %lld\n",&n,&king.x,&king.y);
for(i=1;i<=8;i++)pos[i]=king;
for(i=1;i<=n;i++)
{
scanf("%c %lld %lld\n",&c[i],&now.x,&now.y);
if(pd(now))upd(now);
ch[i]=now;
}
for(i=1;i<=n;i++)
{
if(!pd(ch[i]))continue;
if(c[i]=='B')
{
if(ch[i]==pos[1] || ch[i]==pos[3] || ch[i]==pos[6] || ch[i]==pos[8]){printf("YES");return 0;}
continue;
}
if(c[i]=='R')
{
if(ch[i]==pos[2] || ch[i]==pos[4] || ch[i]==pos[5] || ch[i]==pos[7]){printf("YES");return 0;}
continue;
}
if(c[i]=='Q')
{
if(ch[i]==pos[1] || ch[i]==pos[3] || ch[i]==pos[6] || ch[i]==pos[8]){printf("YES");return 0;}
if(ch[i]==pos[2] || ch[i]==pos[4] || ch[i]==pos[5] || ch[i]==pos[7]){printf("YES");return 0;}
continue;
}
}
printf("NO");
return 0;
}

E

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
const int maxn=200005;

vector<int> g1[maxn],g2[maxn];

int belong[maxn],color[maxn],c[maxn];
int i,j,k,l,m,n;
int edg[maxn][2];

void dfs(int x)
{
belong[x]=m;
for(unsigned int i=0;i<g1[x].size();i++)
{
int v=g1[x][i];
if(belong[v]>0)continue;
if(color[v]!=color[x])continue;
dfs(v);
}
}

void ss(int now,int sum)
{
color[now]=1;
if(sum>n){n=sum;k=now;}
for(unsigned int i=0;i<g2[now].size();i++)
{
int v=g2[now][i];
if(color[v]==0)ss(v,sum+1);
}
}

int main()
{
scan(n);
for(i=1;i<=n;i++)scan(color[i]);
for(i=1;i<n;i++)
{
scan2(j,k);
g1[j].push_back(k);
g1[k].push_back(j);
edg[i][0]=j;edg[i][1]=k;
}
m=0;
for(i=1;i<=n;i++)
{
if(belong[i]==0)
{
m++;
dfs(i);
}
}
for(i=1;i<n;i++)
{
if(belong[edg[i][0]]==belong[edg[i][1]])continue;
int u=belong[edg[i][0]];
int v=belong[edg[i][1]];
g2[u].push_back(v);
g2[v].push_back(u);
c[u]=c[edg[i][0]];
c[v]=c[edg[i][1]];
}
n=0;
memset(color,0,sizeof(color));n=1;
ss(1,1);
memset(color,0,sizeof(color));
ss(k,1);
printf("%d",n/2);
return 0;
}

F

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
struct point
{
LL x,y;
}a[200005];

LL ans[200005];
LL check[200005][30];
LL c[30];
LL sum,tot;
LL i,j,k,l,n,m;

int main()//x&y+x|y==x+y x&y+x^y==x|y
{
scanf("%lld",&n);
for(i=1;i<=n;i++)scanf("%lld",&a[i].x);
for(i=1;i<=n;i++)scanf("%lld",&a[i].y);
for(i=1;i<=n;i++)ans[i]=a[i].x+a[i].y,sum+=ans[i];
if(sum%(n*2)!=0){printf("-1");return 0;}
sum/=2*n;
for(i=1;i<=n;i++)
{
ans[i]-=sum;
if(ans[i]%n!=0){printf("-1");return 0;}
ans[i]/=n;
}
memset(check,0,sizeof(check));
for(i=1;i<=n;i++)
{
LL t=ans[i];
j=0;tot=1;
while(t>0)
{
if(t%2==0)check[i][j]=0;else check[i][j]=tot;
j++;tot*=2;t>>=1;
}
}
for(i=0;i<30;i++)
for(j=1;j<=n;j++)c[i]+=check[j][i];
for(i=1;i<=n;i++)
{
sum=0;tot=0;
for(j=0;j<30;j++)
{
if(ans[i]&((1LL)<<j)){sum+=c[j];tot+=((1LL)<<j)*n;continue;}
tot+=c[j];
}
if(sum!=a[i].x || tot!=a[i].y){printf("-1");return 0;}
}
for(i=1;i<=n;i++)
{
if(i>1)printf(" ");
printf("%lld",ans[i]);
}
return 0;
}