CodeForces 746解题报告

写在最前

抱歉了= =写了相当水的题解,实在是有点累了,望谅解

思路

A

$a$,$b/2$,$c/4$搞一下结束

B

遵循规律,反向还原就好辣

C

The answer is minimum of the following values: the time during which Igor will reach the point x2 by foot and the time during which the tram will reach at first the point x1 and than the point x2.

D

先尽量放多的茶,中间每到不得不放另一个时再放,然后再回来间隔插入就好辣

E

扫三遍,用map。我们不妨假设偶数多

第一遍,用未被使用的奇数先对偶数进行去重

第二遍,用未被使用的奇数对依然多余的偶数进行覆盖

第三遍,用未被使用的奇数或偶数对相同奇偶性的数进行去重

F

考虑滑动窗口(学名叫尺取233333)进行贪心

考虑右端

若右端可加入partly,则将其加入partly

若右端因个数限制不可加入partly,则将partly里面最小的加入full,然后更新partly

考虑左端

如果左端在full里,把它舍弃掉腾出空间

如果左端在partly里面,将其舍弃掉腾出空间,同时选出full里面最大的放入partly

以上操作均可用multiset维护

G

我们考虑将节点一层层放置,并贪心地算出最多最少有多少叶子节点

若不符合,输出无解

然后每层进行叶子节点数目的调整(接在同一父亲或不同父亲上)

如果这样进行到最后叶子节点数目依然不符合要求,同样输出无解(这里有点迷,但是加了这个判断就过了2333)

代码

A

1
2
3
4
5
6
7
8
9
int x,y,z;

int main()
{
scanf("%d%d%d",&x,&y,&z);
y/=2;z/=4;
printf("%d",7*min(min(y,z),x));
return 0;
}

B

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
char s[2005];
char ans[2005];
int n,i,l,r;

int main()
{
scanf("%d\n",&n);
gets(s+1);
if(n%2==1)
{
ans[(n+1)/2]=s[1];
l=(n+1)/2-1;r=(n+1)/2+1;
i=2;
}else
{
l=n/2;r=n/2+1;i=1;
}
while(i<=n)
{
ans[l--]=s[i++];
ans[r++]=s[i++];
}
for(i=1;i<=n;i++)printf("%c",ans[i]);
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
33
34
35
36
37
38
39
40
41
42
43
44
45
const int maxn = 1010;
int s,x1,x2,t1,t2,p,d;
int man,train;
void shuru(){
scanf("%d%d%d",&s,&x1,&x2);
scanf("%d%d",&t1,&t2);
scanf("%d%d",&p,&d);
}

void gogogo(){
int t = 0;
man = t2*max((x1-x2),(x2-x1));
if(d == 1){
if(x1<x2){
if(p<=x1){
t = x2-p;
}
else{
t = 2*s+x2-p;
}
}
else{
t = 2*s-p-x2;
}
}
if(d == -1){
if(x1<x2){
t = p+x2;
}
else if(p>=x1){
t = p-x2;
}
else{
t = 2*s+p-x2;
}
}
t = t*t1;
printf("%d\n",min(man,t));
}

int main(){
shuru();
gogogo();
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
int n,k,p,q;
int a[100005],b[100005];
int i,j,l,m;
char ca,cb;

int main()
{
scanf("%d%d%d%d",&n,&m,&p,&q);
if(p>q){ca='G';cb='B';}else {k=p;p=q;q=k;ca='B';cb='G';}
l=j=0;i=1;
while(l<p)
{
j++;
if(j==m+1){a[i++]=0;q--;j=0;}else {a[i++]=1;l++;}
}
if(q<0){printf("NO");return 0;}
l=i-1;i=1;
while(q>0 && i<=l)
{
if(a[i]==1 && a[i+1]==1)
{
b[i]=1;i++;q--;
}else i++;
}
if(q>0)while(q--)b[i++]=1;
int tt=i-1,t=i-1;i=0;
while(b[t]==1){t--;i++;}
t=tt;
if(i>m){printf("NO");return 0;}
for(i=1;i<=max(t,l);i++)
{
if(i<=l)
{
if(a[i]==1)printf("%c",ca);
else printf("%c",cb);
}
if(b[i]==1)printf("%c",cb);
}
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
map<int,int> mp;
int i,j,k,l,m,n;
int a[200005];
int x,y,ans;//x-偶,y-奇
int ne,b;
int u[2];

void out(int t)
{
printf("%d\n",t);
for(i=1;i<=n;i++)
{
if(i>1)printf(" ");
printf("%d",a[i]);
};
}

bool judge()
{
for(int i=1;i<=n;i++)if(mp[a[i]]>1)return false;
return ne<=0;
}

int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
(a[i]%2==0)?x++:y++;
mp[a[i]]++;
}
ne=abs(x-n/2);
i=0;b=x>y?1:0;
u[0]=2;u[1]=1;
if(judge()){out(0);return 0;}
while(u[b]<=m && ne>0 && i<n)
{
i++;
if(a[i]%2==b || mp[a[i]]<=1)continue;
while(mp[u[b]]>=1 && u[b]<=m)u[b]+=2;
if(u[b]>m)break;
mp[a[i]]--;a[i]=u[b];ne--;ans++;mp[u[b]]++;
}
if(judge()){out(ans);return 0;}
if(u[b]>m){printf("-1");return 0;}
i=0;
while(u[b]<=m && ne>0 && i<n)
{
i++;
if(a[i]%2==b)continue;
while(mp[u[b]]>=1 && u[b]<=m)u[b]+=2;
if(u[b]>m)break;
mp[a[i]]--;a[i]=u[b];ne--;ans++;mp[u[b]]++;
}
if(judge()){out(ans);return 0;}
if(u[b]>m || ne>0){printf("-1");return 0;}
for(i=1;i<=n;i++)
{
if(mp[a[i]]==1)continue;
j=a[i]%2;
while(mp[u[j]]>=1 && u[j]<=m)u[j]+=2;
if(u[j]>m){printf("-1");return 0;}
mp[a[i]]--;a[i]=u[j];mp[u[j]]++;ans++;
}
out(ans);
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
56
57
const int maxn=200005;

int t[maxn],a[maxn];

multiset<int> ha,fu;
multiset<int>::iterator it;
int i,j,k,l,m,n,r,tot,ans,sum;

int main()
{
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)scanf("%d",&t[i]);
a[0]=0;
for(i=1;i<=n;i++)a[i]+=a[i-1];
tot=ans=sum=0;
for(l=1,j=0;l<=n;l++)
{
while(tot-sum<=k && r<=n)
{
ans=max(ans,a[r]-a[l-1]);
r++;
if(r>n)break;
ha.insert(t[r]);
tot+=t[r];sum+=t[r]/2;
if(ha.size()>m)
{
it=ha.begin();
sum-=(*it)/2;
fu.insert((*it));
ha.erase(it);
}
}
it=fu.find(t[l]);
if(it!=fu.end())
{
tot-=(*it);
fu.erase(it);
}else
{
it=ha.find(t[l]);
tot-=(*it);
sum-=(*it)/2;
ha.erase(it);
it=fu.end();
if(it!=fu.begin())
{
it--;
ha.insert((*it));
sum+=(*it)/2;
fu.erase(it);
}
}
}
printf("%d",ans);
return 0;
}

G

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
int n,m,k;
int i,j,l;
int p,q,ma;
int a[200005];
int ans[200005][2];
int f;
vector<int> g,gg;

int main()
{
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=m;i++)
{
scanf("%d",&a[i]);
ma=max(ma,a[i]);
}
if(k>n-m || k<ma)
{
printf("-1");
return 0;
}
g.clear();
for(i=2;i<=a[1]+1;i++)
{
ans[++f][0]=1;
ans[f][1]=i;
g.push_back(i);
}
l=n-m;j=a[1]+1;
for(i=2;i<=m;i++)
{
int p=0;gg.clear();q=1;
while(p<a[i])
{
p++;j++;
gg.push_back(j);
if(p==1)
{
ans[++f][0]=g[0];
ans[f][1]=j;
continue;
}
if(l>k && q<g.size())
{
ans[++f][0]=g[q++];
ans[f][1]=j;
l--;
}else
{
ans[++f][0]=g[0];
ans[f][1]=j;
}
}
g=gg;
}
if(l>k){printf("-1");return 0;}
printf("%d\n",n);
for(i=1;i<=f;i++)printf("%d %d\n",ans[i][0],ans[i][1]);
return 0;
}