第一次当房间第一,然并卵…

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
int T,S,q;

int main()
{
//freopen("test.txt","r",stdin);
while(scanf("%d %d %d",&T,&S,&q)==3)
{
int pre = 0;
int cnt = 1;
for(int t=S+1;t<=T;++t)
{
int now = t*(q-1);
pre +=q;
if(pre>=now)
{
if(pre==now && t==T) continue;
++cnt;
pre = 0;
}
}
printf("%d\n",cnt);
}
return 0;
}

然而题解的方法是列方程了,假设每次相遇的时间为$x$则可知,$\frac{x}{q} = \frac{x-S}{q-1}$
解得$x=qS$,这里$S$可以理解为多走的一段时间,因为每次相遇都走了$qS$,因此每次更新$S=qS$,直到$S\geq T$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>

int main()
{
int T,S,q;
scanf("%d %d %d",&T,&S,&q);
int cnt = 0;
while(S<T)
{
S*=q;
++cnt;
}
printf("%d\n",cnt);
return 0;
}

B

用vis记录下排列中哪些数多了,哪些数大了,哪些数还没有,然后扫一遍,如果多了或者大了就拿没有的数替换。

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn =100010;
int a[maxn];
int vis[maxn];
vector<int> un;

int main()
{
//freopen("test.txt","r",stdin);
int n;
while(scanf("%d",&n)==1)
{
un.clear();
for(int i=1;i<=n;++i) scanf("%d",a+i),++vis[a[i]];
for(int i=1;i<=n;++i) if(!vis[i]) un.push_back(i);
vecotr<int>::iterator it = un.begin();
for(int i=1;i<=n;++i)
{
if((a[i]<=n && vis[a[i]]>1) || a[i]>n)
{
--vis[a[i]];
printf("%d%c",*it,i==n?'\n':' ');
it++;
continue;
}
printf("%d%c",a[i],i==n?'\n':' ');
}
}
return 0;
}

C

将$\pi(n)$和$rub(n)$处理出来发现n大约在120W的时候$\frac{\pi(n)}{rub(n)} > 42$
因此将$\pi(n)$和$rub(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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1300000;
int pi[maxn],n,p,q;
int rub[maxn];
double res[maxn];

inline bool yes(int n)
{
int m=n,t=0;
while(m)
{
t=t*10+m%10;
m/=10;
}
return t==n;
}

void init()
{
memset(pi,0,sizeof pi);
for(int i=2;i<maxn;++i)
{
if(pi[i]==-1)
{
pi[i]=pi[i-1];
continue;
}
for(int j=i+i;j<maxn;j+=i) pi[j] = -1;
pi[i]=pi[i-1]+1;
}
rub[0] = 0;
int i;
for(i=1;i<maxn;++i)
{
rub[i]=rub[i-1];
if(yes(i)) ++rub[i];
res[i] = (double)pi[i]/rub[i];
if(res[i]>=43) break;
}
n = i;
}

int main()
{
int p,q;
init();
while(scanf("%d %d",&p,&q)==2)
{
double A = (double)p/q;
bool flag = false;
for(int i=n-1;i>0;--i)
{
if(A>=res[i])
{
printf("%d\n",i);
flag = true;
break;
}
}
if(flag) continue;
puts("Palindromic tree is better than splay tree");
}
return 0;
}