CodeForces Gym 101149

写在最前

真的是蛮水的一套套题。。。竟然被我队AK了QAQ,然鹅Q神4小时AK,Qrz

思路

Problem A

题目看了好久。。。就是给你一堆球,每种颜色告诉你有几个

每次取出一个球不放回,让你猜球的颜色,问你最多能保证猜对几个

然后。。。扫一遍取max就好

Problem B

显然剩的士兵越多的龙越先杀,然后贪心一下就好

Problem C

从$0-{n-1}$暴力枚举算答案更新就行了

Problem D–By Const

简单的最大流

每个块拆成进出两个点中间连流量为费用的边

所有出点向上下左右的入点连流量为无穷的边

RC所在的点权值改成无穷,其出点作为汇点

从超级源向所有边界上的点连流量为无穷的边

最小割即为答案

Problem E

要保证是所有队伍的得分里最大的,又要尽可能小,显然取所有队伍得分区间左端点的最大值即可

Problem F

显然最后的答案最多只可能有一个。。。证明略,不难

然后排序乱搞一下就好了。

然鹅,我当初没看出来QAQ,于是用了首关键字排序+归并逆序对+维护后缀最小值的做法,噗~

我觉得写的还挺漂亮QAQ,至少挺有启发意义的嘛诶嘿嘿

Problem G

将所有的zorc和axe按第一关键字排序

然后倒着扫所有zorc,依次将满足$w_j>=a_i$的axe加入可选集,这样可选集里面的第一关键字均满足要求

然后考虑贪心做法,选取第二关键字$c_k$不小于$b_i$的最小的那个,分配给当前

这样能保证解最优,然后用set和upper_bound乱搞即可

P.S.有个大坑,即写struct的时候别偷懒,将所有特征都刻画清楚,不然set可能会将不同的东西当成同一个,被坑了好久QAQ,感谢Const大神提醒

Problem H

这题也把我写了好一会,我还是太菜了QAQ

就一个贪心策略,不到万不得已的情况下,尽量填左括号

不过蛮难写的,细节不少QAQ

Problem I

大水题,就把目标square和与其直接相邻的square不放police,其余放满就好了

Problem J

这题真的是个大腿题QAQ一拍大腿就想出来了

要是你觉得是DP啥的就想太多了

我们这样思考,如果前面一栋楼出现在某张照片中,那么为了照片最少,后面一栋楼显然也要被包含比较好

那后面一栋楼什么时候不被包含呢?当然是它的照片比前面的多!

所以其实线性扫一遍就结束了!详见代码~

Problem K–By ZBH大佬!

前方高能预警!!!

为了表示我神TM的心理波动,我决定解题报告用粗体写!!!

这题自己想一下发现坐标系可以变一变,把宫殿移到$(0,0)$即可

所以坐标啥的都没用,真正有用的是龙初始位置到宫殿的距离!

然后最神奇的地方出现了!听说你要列微分积分方程求解?亦可赛艇!

我们发现,如果距离变成了原来的$K$倍,那么相当于坐标系伸展了一下,所以面积是原来的$K^2$倍

然后又发现样例里面距离为1,所以最终求出输入的两点距离$X$

输出[$X^2$×样例答案]即可!!!What The Fuck!!!

真的是迷之题目。。。

Problem L

啊这个题比上一个正常多了,一开始想了一下拓扑啊DFS啊之类的,后来发现想多了

这题可以把原图的边全部反向存成一个新图

然后在原图上跑$0$号点的最短路,在新图上跑$a,b$号点的最短路

然后枚举一下三个最短路汇合的点,取min即可

Problem M

一个交互题,我就顺手一想,然后被ZBH大佬理解出了线段树求第K大的新高度,服气。。。

其实就是分治求最大值,具体如下

先将原序列均分为$A,B$两区,均分

然后分别求出$A,B$区的最大值,假设为$a,b$

然后假设$a>b$,我们用$b$替换$a$,再在$A$区跑一遍最大值即可

如果$b>a$,同理反过来就行啦

有个问题是最好记录一下已经询问过的答案,因为可能会有不少的重复询问

因为这个WA了好几发QAQ,加个数组减少询问次数就过了

呼。。。终于写完题姐了,希望能对大家有所帮助~

代码,依然不写头文件啦

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LL sum,ma,x;
int i,n;

int main()
{
scan(n);
for(i=1;i<=n;i++)
{
scanf("%lld",&x);
sum+=x;
ma=max(ma,x);
}
printf("%lld",ma);
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
struct soldiers
{
LL x,y;
soldiers(LL x=0,LL y=0):x(x),y(y){};
bool operator < (const struct soldiers p)const
{return x-y<p.x-p.y;}
}s[200005];

priority_queue<soldiers> q;

LL sum,now;

int n;

int main()
{
scan(n);
while(n--)
{
LL a,b;
scanf("%lld %lld",&a,&b);
struct soldiers temp=soldiers(a,b);
q.push(temp);
}
sum=0;now=0;
while(!q.empty())
{
struct soldiers t=q.top();
q.pop();
if(t.x>now)sum+=t.x-now,now=t.x;
now-=t.y;
}
printf("%lld",sum);
return 0;
}

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int maxn=1000005;

LL a[maxn];
LL p,n,i;

int main()
{
scanf("%lld",&n);
for(i=0;i<=n-1;i++)a[i]=-1;
for(i=0;i<=n-1;i++)
{
p=i*i%n;
if(a[p]<0)a[p]=i;
}
for(i=0;i<=n-1;i++)
{
if(i>0)printf(" ");
printf("%lld",a[i]);
}
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
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,M,R,C,A;
inline int fi(int x,int y) {return ((x-1)*M+y)*2-1;}
inline int se(int x,int y) {return ((x-1)*M+y)*2;}

bool vis[50005];
void find()
{
queue<int> q;
q.push(S);vis[S]=1;
while(!q.empty())
{
int now=q.front();q.pop();
for (edge* it=head[now];it;it=it->next)
if (!vis[it->t]&&it->v) {q.push(it->t);vis[it->t]=1;}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d%d%d%d",&N,&M,&R,&C);
cnt=-1;S=0;T=se(R,C);n=N*M*2;
memset(head,0,sizeof(head));
for (int i=1;i<=N;i++)
for (int j=1;j<=M;j++)
{
scanf("%d",&A);
if (i==R&&j==C) {add_edge(fi(i,j),se(i,j),INF);continue;}
add_edge(fi(i,j),se(i,j),A);
if (i==1||i==N||j==1||j==M) add_edge(S,fi(i,j),INF);
if (i!=N) add_edge(se(i,j),fi(i+1,j),INF);
if (i!=1) add_edge(se(i,j),fi(i-1,j),INF);
if (j!=M) add_edge(se(i,j),fi(i,j+1),INF);
if (j!=1) add_edge(se(i,j),fi(i,j-1),INF);
}
bfs();
printf("%d\n",isap());

find();
for (int i=1;i<=N;i++)
{
for (int j=1;j<=M;j++)
printf("%c",vis[fi(i,j)]^vis[se(i,j)]?'X':'.');
printf("\n");
}
return 0;
}

E

1
2
3
4
5
6
7
8
9
10
11
12
13
const int maxn=200005;

LL a[maxn],b[maxn];
LL n,i,ma,tot;

int main()
{
scanf("%lld",&n);
for(i=1;i<=n;i++)scanf("%lld %lld",&a[i],&b[i]),ma=max(a[i],ma);
for(i=1;i<=n;i++)if(b[i]>=ma)tot++;
printf("%lld",tot);
return 0;
}

F(我觉得写的还蛮好QAQ)

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

struct people
{
LL x,y,z;
int num;
bool operator < (const struct people p)const
{return x>p.x;}
}a[maxn],temp[maxn];
bool b[maxn];

int i,n,tot;

LL m1[maxn],m2;

void solve(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
solve(l,mid);solve(mid+1,r);
int p=l,q=mid+1,sum=l-1;
m1[mid+1]=m2=1e9+7;
for(int i=mid;i>=l;i--)m1[i]=min(m1[i+1],a[i].z);
for(int i=r;i>=mid+1;i--)m2=min(m2,a[i].z);
while(sum<=r)
{
sum++;
if(p<=mid && q<=r && a[p].y>a[q].y)
{
b[a[p].num]=true;
temp[sum]=a[p];
p++;
continue;
}
if(p<=mid && q<=r && a[p].y<a[q].y)
{
if(a[q].z>m1[p])b[a[q].num]=true;
temp[sum]=a[q];
q++;continue;
}
if(p>mid){temp[sum]=a[q++];continue;}
if(a[p].z>m2)b[a[p].num]=true;
temp[sum]=a[p++];
}
for(int i=l;i<=r;i++)a[i]=temp[i];
}

int main()
{
scan(n);
for(i=1;i<=n;i++)
{
scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].z);
a[i].num=i;
}
sort(a+1,a+n+1);
memset(b,0,sizeof(b));
solve(1,n);
for(i=1;i<=n;i++)if(!b[i])tot++;
printf("%d\n",tot);
tot=0;
for(i=1;i<=n;i++)
{
if(b[i])continue;
if(tot>0)printf(" ");
printf("%d\n",i);
tot++;
}
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
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
const int maxn=200005;
const LL inf=1e9+1;

struct thing
{
int x,y,pos;
thing(int x=0,int y=0,int pos=0):x(x),y(y),pos(pos){}
bool operator < (const struct thing p)const
{
if(x<p.x)return true;
if(x>p.x)return false;
return y<p.y;
}
}axe[maxn],zorc[maxn];

struct us
{
int x,y,pos;
us(int x=0,int y=0,int pos=0):x(x),y(y),pos(pos){}
bool operator < (const struct us p)const
{
if(y<p.y)return true;
if(y>p.y)return false;
return pos<p.pos;
}
bool operator == (const struct us p)const
{return y==p.y;}
};

set<us> ms;
map< LL , int > cou;
map< LL , int > store;
vector<int> g[maxn];
int ans[maxn];

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

LL cnt(LL p,LL q)
{
return p*inf+q;
}

int main()
{
set<us>::iterator i1;
scan(n);
for(i=1;i<=n;i++)
{
scan2(j,k);
zorc[i]=thing(j,k,i);
}
scan(m);
for(i=1;i<=m;i++)
{
scan2(j,k);
axe[i]=thing(j,k,i);
}
sort(zorc+1,zorc+n+1);
sort(axe+1,axe+m+1);
l=m;k=0;
for(i=n;i>=1;i--)
{
while(axe[l].x>=zorc[i].x && l>0)
{
us temp=us(axe[l].x,axe[l].y,axe[l].pos);
LL t1=axe[l].x,t2=axe[l].y;
LL c=cnt(t1,t2);
if(cou.count(c)>0 && cou[c]>0)
{
cou[c]++;
g[store[c]].push_back(temp.pos);
}else
{
ms.insert(temp);cou[c]=1;
store[c]=++k;
g[k].push_back(temp.pos);
}
l--;
}
if(ms.empty()){printf("-1");return 0;}
us tt=us(zorc[i].x,zorc[i].y,0);
i1=ms.lower_bound(tt);
if(i1==ms.end()){printf("-1");return 0;}
if((*i1).y>=tt.y)
{
LL t1=(*i1).x,t2=(*i1).y;
LL c=cnt(t1,t2);
cou[c]--;
ans[zorc[i].pos]=g[store[c]][cou[c]];
if(cou[c]<=0)ms.erase(i1);
continue;
}
}
for(i=1;i<=n;i++)if(ans[i]==0){printf("-1");return 0;}
for(i=1;i<=n;i++)
{
if(i>1)printf(" ");
printf("%d",ans[i]);
}
return 0;
}

H

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

char s[maxn];
int l[maxn],r[maxn];
int n,i,j,k;

int main()
{
gets(s+1);
n=strlen(s+1);
if(n%2!=0){printf("Impossible");return 0;}
for(i=n;i>=1;i--)
{
l[i]=l[i+1];r[i]=r[i+1];
if(s[i]=='(')l[i]++;
if(s[i]==')')r[i]++;
}
for(i=1;i<=n;i++)
{
if(s[i]=='(')k++;
if(s[i]==')')k--;
if(k<0){printf("Impossible");return 0;}
if(s[i]!='?')continue;
if(k<=0){s[i]='(';k++;continue;}
j=n-i+1-l[i]-r[i];
if(k-j+l[i]-r[i]<0){s[i]='(';k++;}else {s[i]=')';k--;}
}
if(k!=0)printf("Impossible");else printf("%s",s+1);
return 0;
}

I

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

bool a[maxn];
int i,j,n,m,k;
vector<int> g[maxn];
int du[maxn];

int main()
{
scan2(n,m);
for(i=1;i<=m;i++)
{
scan2(j,k);
g[j].push_back(k);
g[k].push_back(j);
du[j]++;du[k]++;
}
k=200006;
for(i=1;i<=n;i++)if(du[i]<k){k=du[i];j=i;}
memset(a,0,sizeof(a));
for(unsigned int t=0;t<g[j].size();t++)
a[g[j][t]]=true;
a[j]=true;
for(i=1;i<=n;i++)
{
if(i>1)printf(" ");
if(a[i])printf("0");else printf("1");
}
return 0;
}

J

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int i,n;
LL x,y,sum;

int main()
{
scan(n);
for(i=1;i<=n;i++)
{
scanf("%lld",&x);
if(x>y)sum+=x-y;
y=x;
}
printf("%lld",sum);
return 0;
}

K(神TM!!!)

1
2
3
4
5
6
7
8
9
10
double a,b,x,y,xx,yy;

int main()
{
a=0.916297857297023;
scanf("%lf %lf %lf %lf",&x,&y,&xx,&yy);
b=sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
printf("%.10lf",b*b*a);
return 0;
}

L

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

struct node
{
int to,cost;
node(int to=0,int cost=0):to(to),cost(cost){}
bool operator < (const struct node p)const
{return cost>p.cost;}
};

vector<node> g1[maxn];
vector<node> g2[maxn];

int dis0[maxn],disa[maxn],disb[maxn];
bool vis[maxn];
int i,j,k,l,m,n,a,b;

priority_queue<node> q;

void Dijkstra(int st,int *dis,vector<node> *g)
{
while(!q.empty())q.pop();
memset(vis,0,sizeof(vis));vis[st]=true;
for(unsigned int i=0;i<g[st].size();i++)
{
node v=g[st][i];
dis[v.to]=v.cost;
q.push(v);
}
for(int l=1;l<=n;l++)
{
if(q.empty())break;
int t=q.top().to;
vis[t]=true;
for(unsigned int i=0;i<g[t].size();i++)
{
int v=g[t][i].to;
if(dis[v]>dis[t]+g[t][i].cost)
{
dis[v]=dis[t]+g[t][i].cost;
q.push(node(v,dis[v]));
}
}
while(!q.empty() && vis[q.top().to])q.pop();
}
}

int main()
{
scan2(n,m);scan2(a,b);
for(i=1;i<=m;i++)
{
scan2(j,k);
g1[j].push_back(node(k,1));
g2[k].push_back(node(j,1));
}
for(i=0;i<=n;i++)dis0[i]=disa[i]=disb[i]=inf;
dis0[0]=disa[a]=disb[b]=0;
Dijkstra(0,dis0,g1);
Dijkstra(a,disa,g2);
Dijkstra(b,disb,g2);
m=3*inf;
for(i=0;i<=n;i++)
{
k=dis0[i]+disa[i]+disb[i];
m=min(k,m);
}
printf("%d",m);
return 0;
}

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
int a[1005];

int cmp[1005][1005];

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

int QA(int x,int y)
{
if(cmp[x][y]!=0)return cmp[x][y];
printf("? %d %d\n",x,y);
fflush(stdout);
char c;
while(scanf("%c",&c)==1 && c!='>' && c!='=' && c!='<');
if(c=='>')cmp[x][y]=1;else cmp[x][y]=-1;
cmp[y][x]=-cmp[x][y];
return cmp[x][y];
}

int solve(int x,int y)
{
if(x==y)return x;
int mid=(x+y)>>1;
int p=solve(x,mid);
int q=solve(mid+1,y);
mid=QA(a[p],a[q]);
if(mid>0)return p;else return q;
}

int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)a[i]=i;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)cmp[i][j]=0;
m=(1+n)>>1;
i=solve(1,m);
j=solve(m+1,n);
k=QA(a[i],a[j]);
if(k>0)
{
a[i]=a[j];
printf("! %d\n",a[solve(1,m)]);
}else
{
a[j]=a[i];
printf("! %d\n",a[solve(m+1,n)]);
}
return 0;
}