Codeforces Round 469(Div.2)题解(950A~950F)

2018-03-15jzqjzq?

传送门:CF Round469
希望这是我最后一篇Div2题解……
说起来题目都不是很难,在1小时内可做出前5题
然后你就上紫了666

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#include <complex>
#define int long long
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
int a,b,c;
signed main()
{
a=read();b=read();c=read();
if(a>b)swap(a,b);
if(a+c<=b)writeln(2*(a+c));
else{
c-=(b-a);
writeln(2*b+c/2*2);
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#include <complex>
#define int long long
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
int n,m,a[100010],b[100010];
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=m;i++)b[i]=read();
int s1=0,s2=0,l=1,ans=0;
for(int i=1;i<=n;i++){
s1+=a[i];
while(s2+b[l]<=s1&&l<=m)s2+=b[l],l++;
if(s1==s2)ans++,s1=s2=0;
}
writeln(ans);
return 0;
}

C

因为可以输出任何解,我们考虑直接乱搞
设$f_i$表示以$i$为结尾的序列可以跟在$f_i$的后面
然后我们分别对$0$和$1$开个队列存下位置,考虑找最前面的可行位置接上
然后就可以跑出整个$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
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#include <complex>
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
char s[200010];
int q[2][200010],cnt=0,f[200010],jzq,ans;
bool b[200010];
vector<int>Ans[200010];
inline void dfs(int x){
if(f[x])dfs(f[x]);
b[x]=1;Ans[ans].push_back(x);
}
int main()
{
scanf("%s",s+1);int n=strlen(s+1);
if(s[1]=='1')return puts("-1")&0;
int l[2]={1,1},r[2]={0};
for(int i=1;i<=n;i++){
if(s[i]=='0'){
if(l[1]<=r[1])f[i]=q[1][l[1]],l[1]++;
}
if(s[i]=='1'){
if(l[0]>r[0])return puts("-1")&0;
f[i]=q[0][l[0]];l[0]++;
}
int p=s[i]-'0';
q[p][++r[p]]=i;
}
ans=0;
for(int i=n;i;i--)if(!b[i]){
if(s[i]=='1')return puts("-1")&0;
ans++;
dfs(i);
}
writeln(ans);
for(int i=1;i<=ans;i++){
write(Ans[i].size());putchar(' ');
for(int j=0;j<Ans[i].size();j++)write(Ans[i][j]),putchar(' ');
puts("");
}
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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#include <complex>
#define int long long
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
int n;
signed main()
{
n=read();
for(int q=read();q;q--){
int x=read();
for(;(x&1)==0;x+=n-x/2);
writeln((x+1)/2);
}
return 0;
}

E

首先输入的时候一定是合法的
考虑到一定要加至少一次(如果可以不加的话那答案一定为0)
我们可以对序列构造模型
考虑对某个数$u_i$加1后和另一个数$u_j$相同,那么我们从$i$到$j$连上一条有向边
这些边的意义是:对于某个点,如果加上1,那么对应的出边指向的点也要加1
要使答案最小,我们只需找到出边为0的点就行了,这种情况答案是1
那么问题来了,有些图没有出边为0的点怎么办?
我们发现这种情况下一定有环
于是我们tarjan缩下点之后重新建图,对于一个出边为0的新点,我们统计这个新点对应原图的强联通分量的大小
找最小的那个就可以了

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#include <complex>
#define int long long
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
bool vis[100010];
int s[100010],top=0,dist[100010],f[100010],H;
int n,m,a[100010],b[100010],dfn[100010],low[100010],l[100010],d[100010];
int nedge=0,p[200010],nex[200010],head[200010],dx[200010];
inline void addedge(int a,int b){
p[++nedge]=b;nex[nedge]=head[a];head[a]=nedge;
}
int cnt=0;
inline void dfs(int x){
dfn[x]=low[x]=++cnt;
s[++top]=x;vis[x]=1;
for(int k=head[x];k;k=nex[k])if(!dfn[p[k]]){
dfs(p[k]);low[x]=min(low[x],low[p[k]]);
}else if(vis[p[k]])low[x]=min(low[x],dfn[p[k]]);
if(dfn[x]==low[x]){
d[0]++;int k=0;
do{
k=s[top--];vis[k]=0;l[k]=d[0];d[d[0]]++;
}while(k!=x);
}
}
#define mp make_pair
map<pair<int,int>,bool>M;
signed main()
{
n=read();m=read();H=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
if(!M[mp(x,y)])M[mp(x,y)]=1;
else continue;
if((a[x]+1)%H==a[y])addedge(x,y);
if((a[y]+1)%H==a[x])addedge(y,x);
}
for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
for(int i=1;i<=n;i++)
for(int k=head[i];k;k=nex[k])if(l[i]!=l[p[k]])dx[l[i]]++;
int ans,minn=1e9;
for(int i=1;i<=d[0];i++)if(!dx[i]){
if(minn>d[i])minn=d[i],ans=i;
}
writeln(minn);
for(int i=1;i<=n;i++)if(l[i]==ans)write(i),putchar(' ');
return 0;
}


然后在1:07的时候我过了E之后,专心看榜……
于是……

F

我没有去做!!!!!
留坑待填
不存在的(当然是订正啊)
这东西……我题目看错一小时QAQ
我们先看只有一个老师的情况
我们对于一个位置,把所有可以到这个点的区间找到,判一下数量够不够即可
这个贪心很显然是不是
左右两边都有老师的话也是同理,我们一起做就可以了
时间复杂度是完美的$O(n)$

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#include <complex>
#define int long long
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
int n,d,b;
int a[100010],cntl=0,cntr=0;
signed main()
{
n=read();d=read();b=read();
for(int i=1;i<=n;i++)a[i]=read()+a[i-1];
int ansl=0,ansr=0;
for(int i=1;i<=(n+1)/2;i++){
int l=i*(d+1);
if(a[min(l,n)]>=(cntl+1)*b)cntl++;else ansl++;
if(a[n]-a[max(0ll,n-l)]>=(cntr+1)*b)cntr++;else ansr++;
}
writeln(max(ansl,ansr));
return 0;
}

总结

大多数Div2的题都是非常简单的
当然手速要快