| Solved | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 8/11 | O | . | O | Ø | O | . | O | . | O | Ø | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A Gym 101790A - Pizza Universe
题目描述
有一些人，分别吃了不同价值的饭，付了不同价值的钱。问如何相互给钱使得总消费为自己吃的饭的价钱。
解题思路
可以先排个序，双指针每次保证一个人的账单被清空即可。
AC代码
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
typedef long long ll;
using namespace std;
int a[1000010];
struct A{
int i,d;
bool operator<(const struct A&P)const{
return d<P.d;
}
}e[100010];
int main(){
int b,i,n;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++){
scanf("%d",&b),a[i]-=b;
e[i].i=i;e[i].d=a[i];
}
sort(e+1,e+1+n);
int l=1,r=n;
while(!e[r].d&&r>=0)r--;
while(!e[l].d&&l<=n+1)l++;
while(l<=r){
if(e[r].d+e[l].d>0)printf("%d %d %d",e[r].i,e[l].i,-e[l].d),e[r].d+=e[l].d,l++;
else if(e[r].d+e[l].d<0)printf("%d %d %d",e[r].i,e[l].i,e[r].d),e[l].d+=e[r].d,r--;
else printf("%d %d %d",e[r].i,e[l].i,e[r].d),l++,r--;
while(!e[r].d&&r>=0)r--;
while(!e[l].d&&l<=n+1)l++;
puts("");
}
return 0;
}
B Gym 101790B - Forest protection
题目描述
解题思路
AC代码
2
C Gym 101790C - Keys assignment
题目描述
有$n$个$key$，$k$个槽，每次只能在一个槽里放一个数。对于第$i$个$key$，如果这个$key$的数字没有出现在槽，那需要使一个槽里的数字改变成这个$key$的数字，否则继续下一个$key$。问最多需要改变多少次槽里的数字（初始状态槽里没有放任何数字）。
解题思路
贪心，每次需要分配的时候取出下一个这个数出现最晚的那个数，可以用堆维护。
AC代码
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
typedef long long ll;
using namespace std;
int pos[N],a[N],nxt[N];
int key[N],in[N];
struct P{
int data,i;
bool operator<(const struct P&a)const{return data<a.data;}
};
priority_queue<P>Q;
int main(){
int i,n,m;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)scanf("%d",&a[i]);
memset(pos,0x3f,sizeof(pos));
for(i=n-1;i>=0;i--){
nxt[i]=pos[a[i]];
pos[a[i]]=i;
}
int ans=0;
for(i=0;i<n;i++){
if(in[a[i]]){
Q.push({nxt[i],i});
continue;
}
if(ans<m)in[a[i]]=1,Q.push({nxt[i],i}),ans++;
else{
int top=Q.top().data,topi=Q.top().i;
while(top<=i&&!Q.empty())Q.pop(),top=Q.top().data,topi=Q.top().i;
in[a[topi]]=0;
Q.pop();
Q.push({nxt[i],i});
in[a[i]]=1;
ans++;
}
}
printf("%d",ans);
return 0;
}
D Gym 101790D - Scotland Yard’s fail
题目描述
初始时有一个人际关系图（原图），图里有且只有一个凶手。有$T$次杀戮，每一次杀戮时凶手与被害者互相认识（即有连边），每次杀戮后所有认识被害者的人都会互相认识。
问在第几次杀戮后，能够唯一确定凶手，并输出凶手是谁。
解题思路
首先很容易想出的是，第一次杀戮的时候，受害者的朋友们成为嫌疑犯集合。在第一次杀戮之后的每次杀戮之后，嫌疑犯集合需要取所有认识受害者的人和嫌疑犯集合的交集。
分两类讨论：
- 如果受害者$p$没有当过前面的受害者的朋友，那么这个受害者在每一次杀戮之后都没有认识新的人，所以受害者在原图中的的朋友集合$P$与嫌疑犯集合取交集，成为新的嫌疑犯集合。
- 如果受害者$p$当过前面的受害者的朋友，那么这个受害者认识某一次杀戮之后的受害者的所有朋友，记为集合$S$，而这个集合已经与嫌疑犯集合$sus$取过并集，也就是$sus$是$S$的子集，故$p$所有认识的人与$sus$的交集仍为$sus$。
所以维护两个集合，一个代表嫌疑犯集合$suspect$，一个代表通过杀戮后受害者朋友的集合$irrelevant$即可。
注意，不手写$union$和$inetersection$会$T$掉。
AC代码
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
typedef long long ll;
using namespace std;
struct Edge{int e,n;}e[N<<2];
int hd[N],cnt;
void add(int a,int b){e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;}
set<int>suspect,irrelevant,temp;
void uni(set<int>*a,set<int>*b){
set<int>t;
for(auto it=(*b).begin();it!=(*b).end();)if(!(*a).count(*it))(*a).insert(*it++);else it++;
}
void cro(set<int>*a,set<int>*b){
for(auto it=(*a).begin();it!=(*a).end();)if(!(*b).count(*it))(*a).erase(it++);else it++;
}
int main(){
int i,j,n,m,u,v,num;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u);
scanf("%d",&num);
for(i=0;i<num;i++){
scanf("%d",&u);
temp.clear();
for(j=hd[u];j;j=e[j].n)temp.insert(e[j].e);
if(irrelevant.count(u)){
if(suspect.count(u))suspect.erase(u);
irrelevant.erase(u);
}else{
if(i)cro(&suspect,&temp);
else uni(&suspect,&temp);
}
uni(&irrelevant,&temp);
if(suspect.size()==1)return printf("%d %d",i+1,*suspect.begin()),0;
}
printf("-1");
return 0;
}
E Gym 101790E - Test variants
题目描述
向长度为$n$的数列中填充整数，要求相邻两个数不相同且相隔$k$整数倍的数两两不同，输出最大值最小的方案。
解题思路
首先特判能够由$12121212…$构造出来的情况。
然后填充前$k$项，根据需求用$21313….$或$23131…$填充；求出最大值为$max(3,\lceil\frac{n}{k}\rceil)$之后循环填充即可获得$WA$。
WA代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef long long ll;
using namespace std;
int ans[200010];
int main(){
int i,j,n,k,mx;
scanf("%d%d",&n,&k);
if(n<=k||(n<=k*2&&k%2))for(i=0;i<n;i++)ans[i]=i%2;
else{
ans[0]=1;
mx=(n+k-1)/k;
if(k%2)for(i=1;i<k;)ans[i++]=2,ans[i++]=0;
else for(i=1;i<k;)ans[i++]=0,ans[i++]=2;
for(i=k;i<n;i++)ans[i]=(ans[i-k]+1)%mx;
}
for(i=0;i<n;i++)printf("%d ",++ans[i]);
return 0;
}
然后改成$131313242424$填充就过了？？？
这是什么神秘$bug$，，，，如有高人看出其中问题请务必指点
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef long long ll;
using namespace std;
int ans[200010];
int main(){
int i,j,n,k,mx;
scanf("%d%d",&n,&k);
if(n<=k||(n<=k*2&&k%2))for(i=0;i<n;i++)ans[i]=i%2;
else{
mx=max((n+k-1)/k,3);
for(i=0;i<k;)ans[i++]=0,ans[i++]=2;
for(i=k;i<n;i++)ans[i]=(ans[i-k]+1)%mx;
}
for(i=0;i<n;i++)printf("%d ",++ans[i]);
return 0;
}
F Gym 101790F - MK Ultra
题目描述
解题思路
AC代码
2
G Gym 101790G - Task distributor
题目描述
每一秒有一个任务，能被$k$整除的时间点产生长度为$2T$的任务，其余时间点产生长度为$T$的任务。一台机器相同时刻只能处理一个任务，为了能够持续进行生产，至少需要多少机器？
解题思路
先考虑长度全都是$T$的情况，那么需要$T$台机器。再考虑长度为$2T$的，可以看成每隔时间$k$就多出来一个长度为$T$的任务，于是答案为$T+\frac Tk+(T%k!=0)$。
AC代码
2
3
4
5
6
7
8
9
typedef long long ll;
using namespace std;
ll t,k;
int main(){
scanf("%lld%lld",&t,&k);
printf("%lld",t+t/k+!!(t%k));
return 0;
}
H Gym 101790H - Time difference
题目描述
解题思路
AC代码
2
I Gym 101790I - Key brute forcing
题目描述
问手势密码经过某些边一共有多少种方法。
解题思路
暴力$dfs$判正确性，注意$0$的特判。
AC代码
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
typedef long long ll;
using namespace std;
int a[15][15]={{1,2,3,4,5,6,7,8,9},
{2,4,5,6,8},
{1,3,4,5,6,7,9},
{2,4,5,6,8},
{1,2,3,5,7,8,9},
{1,2,3,4,6,7,8,9},
{1,2,3,5,7,8,9},
{2,4,5,6,8},
{1,3,4,5,6,7,9},
{2,4,5,6,8}};
int vis[15];
int ans;
int mt[15][15],mt2[15][15];
int satisfy(){
int i,j;
for(i=0;i<15;i++)for(j=0;j<15;j++)if(mt[i][j]&&!mt2[i][j])return 0;
return 1;
}
void dfs(int x){
int i;
if(satisfy())ans++;
for(i=0;i<10;i++)if(a[x][i]&&!vis[a[x][i]]){
vis[a[x][i]]=1;
mt2[x][a[x][i]]=mt2[a[x][i]][x]=1;
dfs(a[x][i]);
vis[a[x][i]]=0;
mt2[x][a[x][i]]=mt2[a[x][i]][x]=0;
}
}
int main(){
int i,n;
scanf("%d",&n);
if(!n)dfs(0),printf("%d",ans-10);
else{
int u,v;
for(i=0;i<n;i++){
scanf("%d%d",&u,&v);
mt[u][v]=mt[v][u]=1;
}
dfs(0);
printf("%d",ans);
}
return 0;
}
J Gym 101790J - Distress signal
题目描述
有两棵树，每棵树上有一个人随机在任意一个点上。他们同时向最靠近自己的叶节点走，每一秒走一条边，当一个人到达叶节点时游戏结束，问游戏结束的时间期望。
解题思路
$dfs$找出到叶节点的距离，分别计算方案数即可。
AC代码
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
typedef long long ll;
using namespace std;
struct Edge{
int e,n;
}e[N<<1];
int hd[N],cnt;
void add(int a,int b){
e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;
}
queue<int>Q;
int dis[N],num[N],deg[N],vis[N],num2[N];
ll s1[N],s2[N];
int main(){
int i,n,m,u,v;
scanf("%d",&n);
for(i=1;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
deg[u]++,deg[v]++;
}
for(i=1;i<=n;i++)if(deg[i]==1)vis[i]=1,dis[i]=0,Q.push(i);
while(!Q.empty()){
int now=Q.front();Q.pop();
for(i=hd[now];i;i=e[i].n){
int q=e[i].e;
if(!vis[q])vis[q]=1,dis[q]=dis[now]+1,Q.push(q);
}
}
for(i=1;i<=n;i++)num[dis[i]]++;
memset(hd,0,sizeof(hd));cnt=0;
memset(deg,0,sizeof(deg));memset(vis,0,sizeof(vis));
scanf("%d",&m);
for(i=1;i<m;i++){
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
deg[u]++,deg[v]++;
}
for(i=1;i<=m;i++)if(deg[i]==1)vis[i]=1,dis[i]=0,Q.push(i);
while(!Q.empty()){
int now=Q.front();Q.pop();
for(i=hd[now];i;i=e[i].n){
int q=e[i].e;
if(!vis[q])vis[q]=1,dis[q]=dis[now]+1,Q.push(q);
}
}
for(i=1;i<=m;i++)num2[dis[i]]++;
for(i=max(n,m);i>=0;i--)s1[i]=s1[i+1]+num[i],s2[i]=s2[i+1]+num2[i];
ll ans=0;
for(i=1;i<=n;i++)ans+=(num[i]*s2[i+1]+num2[i]*s1[i+1]+num[i]*num2[i])*i;
printf("%.12f",ans*1.0/n/m);
return 0;
}
K Gym 101790K - Forbidden messenger
题目描述
有$X$个小时，每个邮件写需要时间$A$，发需要时间$B$，每次在路上的邮件只能有一封，问能接受到几封邮件。
解题思路
分类即可。
AC代码
2
3
4
5
6
7
8
int main(){
int x,a,b;
scanf("%d%d%d",&x,&a,&b);x*=60;
if(a>b)printf("%d",(x-b)/a);
else printf("%d",(x-a)/b);
return 0;
}