https://www.luogu.org/problem/show?pid=T15365
表示从来没做过博弈论的题,
不过在推了40多分钟之后发现有几个结论是肯定对的。。。。
n,m都是奇数,后手胜
否则先手胜
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 const int MAXN=1e6;
7 const int INF=0x7ffff;
8 inline int read()
9 {
10 char c=getchar();int flag=1,x=0;
11 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
12 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
13 }
14 int main()
15 {
16 // freopen("star.in","r",stdin);
17 // freopen("star.out","w",stdout);
18 int n,m;
19 while(scanf("%d%d",&n,&m))
20 {
21 if(n==0&&m==0) break;
22 int nowx=n,nowy=1;
23 if(n%2==0)//A不利
24 {
25 printf("Yuri\n");
26 }
27 else
28 {
29 if(m%2==0) printf("Yuri\n");
30 else printf("Chito\n");
31 }
32 }
33 return 0;
34 }
不会做,打40分暴力走人
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 #include<ctime>
8 using namespace std;
9 const int MAXN=1e6;
10 const int INF=0x7ffff;
11 inline int read()
12 {
13 char c=getchar();int flag=1,x=0;
14 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
15 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
16 }
17 const int mod=1e9+7;
18 int a[MAXN];
19 int ans[MAXN];
20 int anstot=0;
21 int comp(const int &a,const int &b)
22 {
23 return a>b;
24 }
25 int main()
26 {
27 //freopen("war.in","r",stdin);
28 //freopen("war.out","w",stdout);
29 int n=read(),k=read();
30 if(n<=3000)
31 {
32 for(int i=1;i<=n;i++) a[i]=read();
33 for(int i=1;i<=n;i++)
34 for(int j=i+1;j<=n;j++)
35 if(i!=j)
36 ans[++anstot]=a[i]^a[j];
37 sort(ans+1,ans+anstot+1,comp);
38 int out=0;
39 for(int i=1;i<=k;i++)
40 out=(out+ans[i])%mod;
41 printf("%d",out);
42 }
43 else if(k==1)
44 {
45 for(int i=1;i<=n;i++) a[i]=read();
46 int t=clock();
47 sort(a+1,a+n+1,comp);
48 int ans=0;
49 for(int i=1;i<=n;i++)
50 {
51 for(int j=i+1;j<=n;j++)
52 {
53 ans=max(ans,(a[i]^a[j])%mod)%mod;
54 if(clock()-t>=900)
55 {
56 printf("%d",ans);
57 exit(0);
58 }
59 }
60 }
61 printf("%d",ans);
62 }
63 else
64 {
65 int t=clock();
66 for(int i=1;i<=n;i++) a[i]=read();
67 for(int i=1;i<=n;i++)
68 for(int j=i+1;j<=n;j++)
69 if(i!=j)
70 {
71 ans[++anstot]=a[i]^a[j];
72 if(clock()-t>=800)
73 {
74 sort(ans+1,ans+anstot+1,comp);
75 int out=0;
76 for(int i=1;i<=k;i++)
77 out=(out+ans[i])%mod;
78 printf("%d",out);
79 }
80 }
81 sort(ans+1,ans+anstot+1,comp);
82 int out=0;
83 for(int i=1;i<=k;i++)
84 out=(out+ans[i])%mod;
85 printf("%d",out);
86 }
87 return 0;
88 }
正解:
20分k==1
最高位异或==1
假设最大的数只有4位
把所有数遍历一边,看一下第四位是0还是1
考虑分治,对于已经确定的高位,在能选择的区间中观察低一位的能否成为1
最长区间为n
复杂度$O(31*n)$
20分不超过1023
记录0-1023的每个数有多少个
每次暴力枚举
$cnt[a^b]+=cnt[a]*cnt[b]$
正解:
01 trie树
先算第k大是啥,再把比他大的加起来
考虑如何求k->二分
如何求比k大的数:
枚举一个i,那么问题就转化为求有多少个j使得a[i]^a[j]>v(二分的值)
用trie树,从最高位开始枚举
看tire树的右儿子(1)有多少个节点
1 #define PROC "shana"
2 #include <cstdio>
3 #include <cctype>
4 #include <memory.h>
5 #include <algorithm>
6 #include<cctype>
7
8 using namespace std;
9
10 typedef long long qw;
11
12 #define _l (qw)
13 const int BUF_SIZE = 30;
14 char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1;
15
16 #define PTR_NEXT() \
17 { \
18 buf_s ++; \
19 if (buf_s == buf_t) \
20 { \
21 buf_s = buf; \
22 buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); \
23 } \
24 }
25
26 #define readInt(_n_) \
27 { \
28 while (*buf_s != '-' && !isdigit(*buf_s)) \
29 PTR_NEXT(); \
30 bool register _nega_ = false; \
31 if (*buf_s == '-') \
32 { \
33 _nega_ = true; \
34 PTR_NEXT(); \
35 } \
36 int register _x_ = 0; \
37 while (isdigit(*buf_s)) \
38 { \
39 _x_ = _x_ * 10 + *buf_s - '0'; \
40 PTR_NEXT(); \
41 } \
42 if (_nega_) \
43 _x_ = -_x_; \
44 (_n_) = (_x_); \
45 }
46
47 const int maxn = 50010;
48 const int maxl = 31;
49 const int maxnd = maxn * maxl;
50 const int mod = 1e9 + 7;
51 const int inv = 500000004;
52
53 int v0, n, rt, tn, a[maxn];
54 int tr[maxnd][2], rb[maxnd][maxl], c[maxnd];
55 qw k;
56
57 void trieIns(int v) {
58 int p = rt;
59 for (int i = maxl - 1; i >= 0; -- i) {
60 int v0 = (v >> i) & 1;
61 if (!tr[p][v0])
62 tr[p][v0] = ++ tn;
63 p = tr[p][v0];
64 ++ c[p];
65 for (int j = maxl - 1; j >= 0; -- j)
66 if ((v >> j) & 1)
67 ++ rb[p][j];
68 }
69 }
70
71 int cntUpper(int v, int vu) {
72 int p = rt, s = 0;
73 for (int i = maxl - 1; i >= 0; -- i) {
74 int v0 = (v >> i) & 1;
75 if ((vu >> i) & 1) {
76 p = tr[p][v0 ^ 1];
77 }
78 else {
79 s += c[tr[p][v0 ^ 1]];
80 p = tr[p][v0];
81 }
82 }
83 return s;
84 }
85
86 qw check(int v) {
87 qw s = 0;
88 for (int i = 0; i < n; ++ i)
89 s += cntUpper(a[i], v);
90 return s >> 1;
91 }
92
93 int sumUpper(int v, int vu) {
94 int s = 0, p = rt;
95 for (int i = maxl - 1; i >= 0; -- i) {
96 int v0 = (v >> i) & 1;
97 if ((vu >> i) & 1)
98 p = tr[p][v0 ^ 1];
99 else {
100 for (int j = 0; j < maxl; ++ j)
101 if ((v >> j) & 1)
102 s = (_l s + (1LL << j) * (_l c[tr[p][v0 ^ 1]] - _l rb[tr[p][v0 ^ 1]][j])) % mod;
103 else
104 s = (_l s + (1LL << j) * _l rb[tr[p][v0 ^ 1]][j]) % mod;
105 p = tr[p][v0];
106 }
107 }
108 return s;
109 }
110
111 int main() {
112 freopen("war.in", "r", stdin);
113 freopen("war.out", "w", stdout);
114
115 readInt(n);
116 readInt(k);
117 rt = 1;
118 tn = 1;
119 for (int i = 0; i < n; ++ i) {
120 readInt(a[i]);
121 trieIns(a[i]);
122 }
123 {
124 int l = 0, r = 2147483647;
125 while (l < r) {
126 int mid = (_l l + r + 1) >> 1;
127 if (check(mid - 1) < k)
128 r = mid - 1;
129 else
130 l = mid;
131 }
132 v0 = l;
133 }
134 if (v0) {
135 //printf("%d %lld\n", v0, check(v0));
136 int ans = 0;
137 for (int i = 0; i < n; ++ i)
138 ans = (_l ans + sumUpper(a[i], v0 - 1)) % mod;
139 ans = (_l ans * inv % mod + ((k - check(v0 - 1)) % mod + mod) * _l v0) % mod;
140 printf("%d\n", ans);
141 }
142 else {
143 int ans = 0;
144 for (int i = 0; i < n; ++ i)
145 ans = (_l ans + sumUpper(a[i], 0)) % mod;
146 ans = _l ans * inv % mod;
147 printf("%d\n", ans);
148 }
149 }
https://www.luogu.org/record/lists?uid=36984&pid=T15368
给了40分的暴力分,另外20分是线段树
但是线段树莫名其妙T掉一个点。。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #define ls k<<1
7 #define rs k<<1|1
8 using namespace std;
9 const int MAXN=4e6;
10 const int INF=0x7ffff;
11 inline int read()
12 {
13 char c=getchar();int flag=1,x=0;
14 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
15 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
16 }
17 int a[MAXN];
18 struct Q
19 {
20 int opt,l,r,x,f;
21 }qs[MAXN];
22 int flagxd=1;
23 struct node
24 {
25 int l,r,w,f;
26 }tree[MAXN];
27 int buildnow=0;
28 inline void update(int k)
29 {
30 tree[k].w=max(tree[ls].w,tree[rs].w);
31 }
32 int down(int k)
33 {
34 tree[ls].w+=tree[k].f;
35 tree[rs].w+=tree[k].f;
36 tree[ls].f+=tree[k].f;
37 tree[rs].f+=tree[k].f;
38 tree[k].f=0;
39 }
40 inline void Build_Tree(int ll,int rr,int k)
41 {
42 tree[k].l=ll;tree[k].r=rr;
43 if(ll==rr)
44 {
45 tree[k].w=a[++buildnow];
46 return ;
47 }
48 int mid=tree[k].l+tree[k].r>>1;
49 Build_Tree(ll,mid,ls);
50 Build_Tree(mid+1,rr,rs);
51 update(k);
52 }
53 int ans=0;
54 inline void Interval_Max(int ll,int rr,int k)
55 {
56 if(ll<=tree[k].l&&tree[k].r<=rr)
57 {
58 ans=max(ans,tree[k].w);
59 return ;
60 }
61 if(tree[k].f) down(k);
62 int mid=tree[k].l+tree[k].r>>1;
63 if(ll<=mid) Interval_Max(ll,rr,ls);
64 if(rr>mid) Interval_Max(ll,rr,rs);
65 update(k);
66 }
67 inline void Interval_Add(int ll,int rr,int val,int k)
68 {
69 if(ll<=tree[k].l&&tree[k].r<=rr)
70 {
71 tree[k].w+=val;
72 tree[k].f+=val;
73 return ;
74 }
75 if(tree[k].f) down(k);
76 int mid=tree[k].l+tree[k].r>>1;
77 if(ll<=mid) Interval_Add(ll,rr,val,ls);
78 if(rr>mid) Interval_Add(ll,rr,val,rs);
79 update(k);
80 }
81 int main()
82 {
83 //freopen("noname.in","r",stdin);
84 // freopen("noname.out","w",stdout);
85 int n=read(),m=read();
86 for(int i=1;i<=n;i++) a[i]=read();
87 for(int i=1;i<=m;i++)
88 {
89 qs[i].opt=read(),qs[i].l=read(),qs[i].r=read(),qs[i].x=read();
90 if(qs[i].opt==0&&qs[i].x>1) flagxd=0;
91 }
92 if(flagxd)
93 {
94 Build_Tree(1,n,1);
95 for(int i=1;i<=m;i++)
96 {
97 if(qs[i].opt==0)
98 {
99 ans=0;
100 Interval_Max(qs[i].l,qs[i].r,1);
101 printf("%d\n",ans);
102 }
103 else
104 Interval_Add(qs[i].l,qs[i].r,qs[i].x,1);
105 }
106 }
107 else
108 {
109 for(int i=1;i<=m;i++)
110 {
111 int l=qs[i].l,r=qs[i].r,x=qs[i].x;
112 if(qs[i].opt==0)
113 {
114 priority_queue<int>q;
115 for(int i=l;i<=r;i++) q.push(a[i]);
116 if(x>(r-l+1)||x==0)
117 {
118 printf("-1\n");
119 }
120 else
121 {
122 int now=1;
123 while(now!=x)
124 q.pop(),now++;
125 printf("%d\n",q.top());
126 }
127
128 }
129 else
130 {
131 for(int i=l;i<=r;i++)
132 a[i]+=x;
133 }
134 }
135 }
136 return 0;
137 }
正解:
30分:暴力
另外20分:线段树
再另外20分:主席树||莫队+堆
100分:
线段树
k<=10
维护区间前10大的数
每一个区间的前十大是ls的前十大+rs的前10大
类似于归并排序,双指针法
修改:前十大都加val
一个比较方便的写法:重载运算符
总结
这一场考的还算不错 ,起码该拿的分都拿到了。
希望自己调整好心态,稳稳当当的走下去,直到11.12
---恢复内容结束---
n,m都是奇数,后手胜
否则先手胜
20分k==1
最高位异或==1
假设最大的数只有4位
把所有数遍历一边,看一下第四位是0还是1
考虑分治,对于已经确定的高位,在能选择的区间中观察低一位的能否成为1
最长区间为n
复杂度O(31*n)
20分不超过1023
记录0-1023的每个数有多少个
每次暴力枚举
cnt[a^b]+=cnt[a]*cnt[b]
正解:
01 trie树
先算第k大是啥,再把比他大的加起来
考虑如何求k->二分
如何求比k大的数:
枚举一个i,那么问题就转化为求有多少个j使得a[i]^a[j]>v(二分的值)
用trie树,从最高位开始枚举
看tire树的右儿子(1)有多少个节点
30分:暴力
另外20分:线段树
再另外20分:主席树||莫队+堆
100分:
线段树
k<=10
维护区间前10大的数
每一个区间的前十大是ls的前十大+rs的前10大
类似于归并排序,双指针法
修改:前十大都加val
一个比较方便的写法:重载运算符