CodeForces 727 解题报告

大致题意

Problem A

给定$A$,$B$,每次可以对$A$进行$\times 2或$$\times 10+1$操作,问最后能否变成B,要求能的话输出过程

Problem B

给定字符串,要求输出其中所有花费之和

Problem C

长度为$n$的序列,每次你可以询问两个下标不同的数之和,要求最多询问$n$次确定序列

Problem D

给出六种尺码的衣服数目,每人给出对衣服的要求(一个尺码,或两个相邻尺码要求其中之一),问是否有满足要求的分配方案并输出

Problem E

将光盘分为$n$个区,每个区长为$k$,给定若干长为$k$的字符串(代表游戏)和光盘自身字符串,问是否能将n个不同的游戏放进每个区,并输出方案

Problem F

给定长为$n$的序列,以及$m$个查询,对于每个查询$k$,输出最少需要去除原序列中多少个元素,使得新序列任意前缀和与$k$之和$\geq0$

思路

A

由于最多只有$logn$的操作,所以写DFS进行暴力搜索即可

B

字符串扫描,注意可能以数字结尾,同时会有”.”参与的多种不同情况

细节很多的模拟

C

先查询$a_1+a_2$,$a_1+a_3$,$a_2+a_3$,并解出$a_1$,$a_2$,$a_3$,然后对于$i \geq 4$ ,查询$a_1+a_i$,并做一次减法即可

D(By Const)

网络流做,输出稍微有点恶心
每种T-shirt一个点,每种需求一个点,$6+11$加上SourceSink两个点,图很小
Source向每个T-shirt连边,容量为供应量
每个需求向Sink连边,容量为需求人数
供需关系连容量为无穷的边
跑最大流,出来是总人数就有可行方案
为了输出方案,记录每个人的需求类型
在这个需求类型里面去找跑完最大流出现的反边得到供应的型号,输出一个减一个

E(By Zhang BH)

利用AC自动机,跑出对于光盘自身字符串中每个字符开头长为$k$的字符串会匹配到哪个游戏

显然这是唯一的,或者匹配不到

然后枚举k个起点,每个起点开始跑n个判断看是否都能匹配到游戏且不重复即可

对于循环的问题,在原串后接上一个自身字符串即可

复杂度$O(nk+gk+nk)$,均为百万级

F(By Zhang BH)

显然对于任意序列,查询值$k$越大,需要去掉的数字个数不递增,即其满足二分性质。

再者,对于单次查询,我们可以贪心地在每次前缀和不满足条件的情况下去掉当前组成前缀和的最小值

由此诞生了一个二分+贪心的算法

先卡一卡上界,然后对于$0-n$中的每个数$i$去二分对应的$k$,使得$k$为必须要删去$i$个数的时候的最小查询值,用数组保存下来

然后对于每个询问,二分去查找对应的答案即可。

时间复杂度预处理$O(n^2lognlogm)$,查询$O(mlogn)$

其实预处理计算量很大,约莫有两亿。。。大概在2s的时限内,也就CF不会T了。。。

AC代码

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
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

bool f;
int s[100];

void dfs(int x,int y)
{
if(y<x)return;
if(y==x)
{
f=true;
s[++s[0]]=y;
return;
}
if(y%2==0)dfs(x,y/2);
if(f)
{
s[++s[0]]=y;
return;
}
if(y>10 && y%10==1)dfs(x,y/10);
if(f)
{
s[++s[0]]=y;
return;
}
}

int main()
{
int a,b;
f=false;
memset(s,0,sizeof(s));
scan2(a,b);
dfs(a,b);
if(!f){printf("NO");return 0;}
printf("YES\n");
printf("%d\n",s[0]);
for(int i=1;i<=s[0];i++)
{
if(i>1)printf(" ");
printf("%d",s[i]);
}
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
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
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

char s[1005];
int zs,xs;
int i,n,now,t1,t2,t;
bool f;

void pp(int t)
{
int o=100;
while(o>0)
{
printf("%d",t/o);
t%=o;
o/=10;
}
}

void pri(int x)
{
if(x>=1000000)
{
printf("%d",x/1000000);
x%=1000000;
printf(".");
pp(x/1000);
printf(".");
x%=1000;
pp(x);
return;
}
if(x>=1000)
{
printf("%d.",x/1000);
x%=1000;
pp(x);
return;
}
printf("%d",x);
}

int find(int t)
{
int ans=0;
t++;
while(s[t]>='0' && s[t]<='9'){ans++;t++;}
return ans;
}

int ww(int t)
{
if(t==0)return 1;
if(t==1)return 10;
if(t==2)return 100;
return 1000;
}

int main()
{
gets(s);
n=strlen(s);
s[n]='a';
for(i=0;i<=n;i++)
{
if(s[i]>='a' && s[i]<='z')
{
if(now<=2 && f)t2=t2*ww(now)+t;else t1=t1*1000+t;
xs+=t2;zs+=t1;
now=t1=t2=t=0;
f=false;
continue;
}
if(s[i]=='.')
{
t1=t1*ww(now)+t;
t=now=0;
f=true;
continue;
}
t=t*10+s[i]-48;
now++;
}
zs=zs+xs/100;
xs%=100;
pri(zs);
if(xs>=10)printf(".%d",xs);
if(xs>0 && xs<10)printf(".0%d",xs);
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

const int maxn=5005;

int num[maxn],ans[maxn];
int i,n;

int QA(int x,int y)
{
printf("? %d %d\n",x,y);
fflush(stdout);
int t;
scan(t);
return t;
}

int main()
{
scanf("%d",&n);
for(i=2;i<=n;i++)num[i]=QA(1,i);
num[1]=QA(2,3);
int tot=num[1]+num[2]+num[3];
tot/=2;
ans[1]=tot-num[1];
ans[3]=tot-num[2];
ans[2]=tot-num[3];
for(i=4;i<=n;i++)ans[i]=num[i]-ans[1];
printf("!");
for(i=1;i<=n;i++)printf(" %d",ans[i]);
return 0;
}

D(By Const)

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 205 //????????
#define maxm 205 //????????
#define rever(x) (mem+((x-mem)^1))
struct edge
{
int s,t,v;
edge* next;
}mem[maxm*2],*head[maxn];
int cnt=-1;
void add_edge(int s,int t,int v)
{
mem[++cnt].s=s;mem[cnt].t=t;mem[cnt].v=v;mem[cnt].next=head[s];head[s]=mem+cnt;
mem[++cnt].s=t;mem[cnt].t=s;mem[cnt].v=0;mem[cnt].next=head[t];head[t]=mem+cnt;
}
int n,m;

int S,T;
int numbs[maxn];
int d[maxn];
edge* cur[maxn],*revpath[maxn];

void bfs()
{
queue<int> q;
while(!q.empty()) q.pop();
for (int i=0;i<=n;i++) d[i]=maxn-1; //?ɳ?ʼ?±?????01
d[T]=0;q.push(T);
while(!q.empty())
{
int u=q.front();
q.pop();
for (edge* it=head[u];it;it=it->next)
{
edge *now=rever(it);
if (now->v==0||d[now->s]<n) continue;
d[now->s]=d[u]+1;
q.push(now->s);
}
}
memset(numbs,0,sizeof(numbs));
for (int i=0;i<=n;i++) numbs[d[i]]++; //?ɳ?ʼ?±?????01
}

int isap()
{
int flow=0;
for (int i=0;i<=n;i++) cur[i]=head[i]; //?ɳ?ʼ?±?????01
int u=S;
while(d[S]<n)
{
if (u==T)
{
int augflow=2147483647;
for (int i=S;i!=T;i=cur[i]->t)
augflow=min(augflow,cur[i]->v);
for (int i=S;i!=T;i=cur[i]->t)
{
cur[i]->v-=augflow;
rever(cur[i])->v+=augflow;
}
flow+=augflow;u=S;
}
edge *e;
for (e=cur[u];e;e=e->next)
if (e->v&&d[u]==(d[e->t]+1)) break;
if (e)
{
cur[u]=e;
revpath[e->t]=rever(e);
u=e->t;
}
else
{
numbs[d[u]]--;
if (numbs[d[u]]==0) break;
cur[u]=head[u];
int mindist=n;
for (edge* it=head[u];it;it=it->next)
if (it->v) mindist=min(mindist,d[it->t]);
d[u]=mindist+1;
numbs[d[u]]++;
if (u!=S) u=revpath[u]->t;
}
}
return flow;
}

int N;
char tmp[20];
int prov[10],need[20];
int tpe[100005];
char lst[6][5]={"S","M","L","XL","XXL","XXXL"};
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
for (int i=1;i<=6;i++) scanf("%d",&prov[i]);
scanf("%d",&N);
for (int i=1;i<=N;i++)
{
scanf("%s",tmp);
if (strcmp(tmp,"S")==0) tpe[i]=1;
else if (strcmp(tmp,"M")==0) tpe[i]=2;
else if (strcmp(tmp,"L")==0) tpe[i]=3;
else if (strcmp(tmp,"XL")==0) tpe[i]=4;
else if (strcmp(tmp,"XXL")==0) tpe[i]=5;
else if (strcmp(tmp,"XXXL")==0) tpe[i]=6;
else if (strcmp(tmp,"S,M")==0) tpe[i]=7;
else if (strcmp(tmp,"M,L")==0) tpe[i]=8;
else if (strcmp(tmp,"L,XL")==0) tpe[i]=9;
else if (strcmp(tmp,"XL,XXL")==0) tpe[i]=10;
else tpe[i]=11;
}
for (int i=1;i<=N;i++) need[tpe[i]]++;
cnt=-1;S=0;T=18;n=T;
for (int i=1;i<=6;i++) add_edge(S,i,prov[i]);
for (int i=1;i<=11;i++) add_edge(i+6,T,need[i]);
for (int i=1;i<=6;i++)
{
add_edge(i,i+6,100000);
if (i!=1) add_edge(i,i+11,100000);
if (i!=6) add_edge(i,i+12,100000);
}
bfs();
if (isap()!=N) {printf("NO\n");return 0;}
else printf("YES\n");
edge* it;
for (int i=1;i<=N;i++)
{
for (it=head[tpe[i]+6];it->t==T||it->v==0;it=it->next);
it->v--;
printf("%s\n",lst[it->t-1]);
}
return 0;
}

E(By Zhang BH)

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

char s[1000005];
char ss[2000005];
int i,j,k,g,n,ans,t,m;
int num[2000005];
int hh[100005];

#define LETTER 26
struct Trie{
int num, fail, match;
int next[LETTER];
}trie[2200005];
int cnt;
void init(){
cnt = 1;
memset(trie, 0, 2 * sizeof(Trie));
trie[0].fail = 1;
}
inline int convert(char ch){ return ch - 'a'; }
void insert(char *s,int bj)
{
int cur = 0;
for (int i = 0; s[i]; i++){
int &pos = trie[cur].next[convert(s[i])];
if (!pos){
pos = ++cnt;
memset(&trie[cnt], 0, sizeof(Trie));
}
cur = pos;
}
trie[cur].num=bj;
}
void makeFail()
{
queue<int> q; q.push(0);
while (!q.empty()){
int t = q.front(); q.pop();
for (int i = 0; i < LETTER; i++){
int &cur = trie[t].next[i];
if (cur){
q.push(cur);
trie[cur].fail = trie[trie[t].fail].next[i];
trie[cur].match = trie[cur].num ? cur : trie[trie[cur].fail].match;
}
else cur = trie[trie[t].fail].next[i];
}
}
}
void search(char *s)
{
int ret = 0, cur = 0;
for (int i = 0; i < t ; i++){
cur = trie[cur].next[convert(s[i])];
for (int temp = trie[cur].match; temp; temp = trie[trie[temp].fail].match)
//ret += trie[temp].num;
num[i-k+1]=trie[temp].num;
}
//return ret;
}

int main()
{
init();
scanf("%d %d\n",&g,&k);
gets(ss);
t=strlen(ss);
scanf("%d\n",&n);
for(i=0;i<k;i++)ss[i+t]=ss[i];
t+=k;ss[t]='\0';
for(i=1;i<=n;i++)
{
gets(s);
insert(s,i);
}
makeFail();
search(ss);
bool f=false;
for(i=1;i<=n;i++)hh[i]=-1;
for(i=0;i<k;i++)
{
f=true;
for(j=1;j<=g;j++)
{
int pos=(j-1)*k+i;
if(hh[num[pos]]==i || num[pos]==0){f=false;break;}
if(hh[num[pos]]!=i)hh[num[pos]]=i;
}
if(f)
{
printf("YES\n");
for(j=1;j<=g;j++)
{
if(j>1)printf(" ");
printf("%d",num[(j-1)*k+i]);
}
return 0;
}
}
printf("NO");
return 0;
}

F(By Zhang BH)

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
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

const int maxn=800;
const int maxm=200005;

LL a[maxn],b[maxn];
priority_queue< LL , vector<LL>, greater<LL> > q;
LL ord[maxm];
LL mm,mi,tot;
int i,j,k,m,n;

int find(LL t)
{
int ans=0;
LL sum=0;
while(!q.empty())q.pop();
for(int i=1;i<=n;i++)
{
q.push(a[i]);
sum+=a[i];
while(sum+t<0)
{
LL temp=q.top();q.pop();
if(temp>0)break;
sum-=temp;
ans++;
}
}
return ans;
}

int main()
{
scan2(n,m);
mm=mi=tot=0;
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
tot+=a[i];
mi=min(tot,mi);
}
for(i=1;i<=m;i++)
{
scanf("%lld",&ord[i]);
mm=max(mm,ord[i]);
}
if(mi<0)mm=min(mm,-mi);
else
{
for(i=1;i<=m;i++)printf("0\n");
return 0;
}
for(i=0;i<=n;i++)
{
LL l=0,r=mm+1;
while(r-l>1)
{
LL mid=(l+r)>>1;
if(find(mid)>i)l=mid;else r=mid;
}
if(find(l)>i)l++;
b[i]=l;
}
//for(i=0;i<=n;i++)printf("%d %lld\n",i,b[i]);
for(int i=1;i<=m;i++)
{
LL x=ord[i];
int l=0,r=n;
while(r-l>1)
{
int mid=(l+r)>>1;
if(b[mid]>x)l=mid;else r=mid;
}
if(b[l]>x)l++;
printf("%d\n",l);
}
return 0;
}