CFR371 div1

CFR371 div1

CF713C Sonya and Problem Wihtout a Legend

建议学习一下强化版:这里

CF713D Animals and Puzzle

可以直接二分+ST表,$O(n^2log^2n+qlogn)$,code

CF713E Sonya Partymaker

请先思考后再展开

我目前认为,把最长段转到n-1间是错误的做法,但不知为何得到AC且没能拍出错误,故只给出代码:

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
int m,n,st;pr mx;
int f[MAX_N][2],a[MAX_N];
void dp(int T,int op)
{
for(int i=st+1+op;i<=st+n-1;i++)
{
if(f[i-1][0]>=a[i]-T) chmax(f[i][0],a[i]+1);
if(f[i-1][1]>=a[i]-T) chmax(f[i][0],max(a[i-1]+T+1,a[i]+1) );
int tmp=max(f[i-1][0],f[i-1][1]);if(tmp>=a[i]) chmax(f[i][1],a[i]+T+1);
chmax(f[i][0],tmp);chmax(f[i][1],tmp);
}
}
bool check(int T)
{
int st=mx.SE;//printf("st=%d\n",st);
//left
{
memset(f,-0x3f,sizeof f);f[st][0]=a[st]+1;dp(T,0);
if( max(f[st+n-1][0],f[st+n-1][1])>=a[st]+m-T ) return 1;
}
//right
{
memset(f,-0x3f,sizeof f);f[st][1]=a[st]+T+1;dp(T,0);
if( max(f[st+n-1][0],f[st+n-1][1])>=a[st]+m ) return 1;
}
//right2
if(a[st]+T+1>=a[st+1])
{
memset(f,-0x3f,sizeof f);f[st+1][0]=max(a[st]+T+1,a[st+1]+1);dp(T,1);
if( max(f[st+n-1][0],f[st+n-1][1])>=a[st+1]+m-T ) return 1;
}
return 0;
}
void main()
{
m=qread(),n=qread();for(int i=1;i<=n;i++) a[i]=qread();
mx=MP(a[1]-1+m-a[n]+1,1);for(int i=2;i<=n;i++) mx=max(mx,MP(a[i]-a[i-1],i));st=mx.SE;
for(int i=1;i<=n;i++) a[n+i]=a[i]+m;
int l=0,r=mx.FR-1,ans=mx.FR;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
write(ans);
}

比较合理的做法应该是移动到1和2之间,从1开始dp,这样能避免很多奇怪的情况。

第一次dp,不考虑所有人在n-1段的贡献,得出还差长度ln,然后第二次dp,dp的初始值要求覆盖ln,然后判能否合上

不是很想再写一次了,所以口胡跑路了……

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/58b5aaea.html
转载请注明出处,谢谢!