• 周一. 7 月 15th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[hdu7035]Game

admin

11 月 28, 2021

称区间$[i,j]$为普通区间,当且仅当$j-ige 3$​​​且其操作两次内不会变为给定区间

结论:若$[i,j]$为普通区间,则$[i,j]$和$[i+1,j-1]$​​​​​​​​​​的状态(是否先手必胜)相同

(关于这个结论的正确性,不难分类讨论得到)

由此,对于普通区间不断缩小使其变为非普通区间,而非普通区间暴力枚举其变化,直至其长度为1或变为普通区间,显然这类区间至多只有$o(n)$个,因此记忆化后总复杂度也为$o(n)$

综上,只需要能快速实现缩小的过程即可,注意到和是相同的,以和为第一关键字,左端点为第二关键字在所有第2类的非普通区间中二分即可

(暴力的过程中判定区间是否为特殊区间也可以二分)

最终,总复杂度为$o((n+q)log n)$​,可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 600005
 4 int t,n,m,q,l,r,ans[N];
 5 struct Data{
 6     int l,r,p;
 7     bool operator < (const Data &k)const{
 8         return (l+r<k.l+k.r)||(l+r==k.l+k.r)&&(l<k.l); 
 9     }
10     bool operator == (const Data &k)const{
11         return (l==k.l)&&(r==k.r);
12     }
13     bool operator != (const Data &k)const{
14         return (l!=k.l)||(r!=k.r);
15     }
16 }a[N],b[N];
17 int find(int l,int r){
18     Data o=Data{l,r,0};
19     int p=lower_bound(b+1,b+m+1,o)-b;
20     if ((p>m)||(b[p]!=o))return -1;
21     return p;
22 }
23 int get_nex(int l,int r){
24     Data o=Data{l,r,0};
25     int p=lower_bound(b+1,b+m+1,o)-b;
26     if ((p<=m)&&(o.l+o.r==b[p].l+b[p].r))return b[p].l-o.l;
27     return (r-l-1>>1);
28 }
29 bool calc(int l,int r){
30     int p=find(l,r);
31     if (p>0){
32         if (b[p].p>=0)return b[p].p;
33         if (ans[p]>=0)return ans[p];
34     }
35     if (l==r)return 0;
36     if ((r-l>=3)&&(p<0)){
37         p=get_nex(l,r);
38         return calc(l+p,r-p);
39     }
40     int s=((calc(l,r-1)&calc(l+1,r))^1);
41     if (p>0)ans[p]=s;
42     return s;
43 }
44 int main(){
45     scanf("%d",&t);
46     while (t--){
47         scanf("%d%d",&n,&q);
48         for(int i=1;i<=n;i++){
49             scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].p);
50             a[i+n]=Data{a[i].l-1,a[i].r,-1};
51             a[i+n*2]=Data{a[i].l-2,a[i].r,-1};
52             a[i+n*3]=Data{a[i].l,a[i].r+1,-1};
53             a[i+n*4]=Data{a[i].l,a[i].r+2,-1};
54             a[i+n*5]=Data{a[i].l-1,a[i].r+1,-1};
55         }
56         sort(a+1,a+n*6+1);
57         m=0;
58         for(int i=1;i<=n*6;i++){
59             if ((a[i].l<=0)||(a[i].r>1e9))continue;
60             if ((!m)||(b[m]!=a[i]))b[++m]=a[i];
61             else{
62                 if (b[m].p<0)b[m].p=a[i].p;
63             }
64         }
65         for(int i=1;i<=m;i++)ans[i]=-1;
66         for(int i=1;i<=q;i++){
67             scanf("%d%d",&l,&r);
68             printf("%d",calc(l,r));
69         }
70         printf("
");
71     }
72     return 0;
73 }

View Code

发表回复