这场是Round (PI)314,突然发现已经两个月没打CF了,果然被虐成狗了…

A

大水题,因为是升序给出
所以最大值就是max(a[i]-a[0],a[n-1]-a[i])
最小值为min(a[i]-a[i-1],a[i+1]-a[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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;
const int maxn = 100010;
int a[maxn];
int mx[maxn],mn[maxn];

int main()
{
// freopen("test.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",a+i);
for(int i=0;i<n;++i)
{
mx[i] = max(a[n-1]-a[i],a[i]-a[0]);
if(i!=0 && i!=n-1) mn[i] = min(a[i]-a[i-1],a[i+1]-a[i]);
else if(i!=n-1) mn[i] = a[i+1] - a[i];
else mn[i] = a[i] - a[i-1];
printf("%d %d\n",mn[i],mx[i]);
}
return 0;
}

B

也是水题,我们假设馆中有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
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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;

const int maxn = 1000010;
int vis[maxn] ;
char s[102][2];
int id[102];
int n;

int solve()
{
for(int i=0;i<=2*n;++i)
{
memset(vis,0,sizeof vis);
bool flag = true;
int sz = i,now = 0;
int mx = i;
for(int j=1;j<=n;++j)
{
if(s[j][0]=='+')
{
vis[id[j]] = 1;
now++;
}
else
{
if(vis[id[j]]) now--;
else --sz;
vis[id[j]] = 0;
}
if(sz<0) { flag = false;break; }
mx = max(mx,now+sz);
}
if(flag) return mx;
}
return n;
}

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
int pos;
scanf("%s %d",s[i],id+i);
}
printf("%d\n",solve());
return 0;
}

C

DP…
d[i][j] 表示数列$bk^0,bk^1,bk^2…$中前i个,满足b为j的情况

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

typedef long long LL;

const int maxn = 200010;
map<LL,LL> d[2];

int main()
{
//freopen("test.txt","r",stdin);
int n;
LL k1;
scanf("%d %lld",&n,&k1);
LL k2 = k1*k1;
LL ns = 0;
d[0].clear();
d[1].clear();
for(int i=0;i<n;++i)
{
LL x;
scanf("%lld",&x);
if(x%k2==0) ans += d[1][x/k2];
if(x%k1==0) d[1][x/k1] += d[0][x/k1];
++d[0][x];
}
printf("%lld\n",ans);
return 0;
}

D

CF测评机太6了,各种STL乱搞都没事…
长度为n的区间最多可以放$(n+1)/(a+1)$个
然后用map来标记,每次只需要更新标记到的最小区间即可

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

typedef long long LL;
#define pb push_back
const int maxn = 200010;
int n,k,a,m;
int save[maxn];

map<int,int> range;
map<int,int>::iterator it;

int solve()
{
range.clear();
range[0] = 1;
range[n+1] = 1;
int ans = (n+1)/(a+1);
for(int i=1;i<=m;++i)
{
it = range.lower_bound(save[i]);
--it;
int low = it->first;
it = range.upper_bound(save[i]);
int high = it->first;
// printf("%d %d\n",low,high);
ans -= (high - low)/(a+1);
ans += (high - save[i])/(a+1);
ans += (save[i] - low)/(a+1);
if(ans < k)
{
return i;
}
range[save[i]] = 1;
}
return -1;
}

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %d %d %d",&n,&k,&a,&m);
for(int i=1;i<=m;++i)
scanf("%d",save+i);
printf("%d\n",solve());
return 0;
}