# T1

https://www.luogu.org/problem/show?pid=T15365

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;
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 }```

# T2

``` 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;
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);
30     if(n<=3000)
31     {
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     {
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();
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

20分不超过1023

\$cnt[a^b]+=cnt[a]*cnt[b]\$

01 trie树

```  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
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
117     rt = 1;
118     tn = 1;
119     for (int i = 0; i < n; ++ 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 }```

# T3

https://www.luogu.org/record/lists?uid=36984&pid=T15368

```  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;
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;
79     update(k);
80 }
81 int main()
82 {
83     //freopen("noname.in","r",stdin);
84 //    freopen("noname.out","w",stdout);
87     for(int i=1;i<=m;i++)
88     {
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
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分：暴力

100分：

k<=10

一个比较方便的写法：重载运算符

---恢复内容结束---

n,m都是奇数，后手胜

# T2

20分k==1

20分不超过1023

cnt[a^b]+=cnt[a]*cnt[b]

01 trie树

# T3

30分：暴力

100分：

k<=10

一个比较方便的写法：重载运算符

1811 篇文章120 人订阅

0 条评论

## 相关文章

### 1934: [Shoi2007]Vote 善意的投票

1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 1174  ...

2917

### 2017.10.1解题报告

---- 预计分数：60+50+0=110 实际分数：60+81+0=144 全场rank13？全校rank1？貌似题很难啊23333 ---- T1...

3699

### string 之 strlen函数

Author: bakari  Date: 2012/8/9 近两年好多的IT公司喜欢拿一些库函数来考，string函数库当然是首选，除此之外，像qsort，S...

2017

### 1112: [POI2008]砖块Klo

1112: [POI2008]砖块Klo Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1245  Solv...

3296

3146

35011

### 面试——经典问题1

1、阶梯问题 问题描述：一个阶梯有n个级，一个人要走完这个阶梯，一步可以走一级或两级，问：共有多少个方案? 解决思路：当n=1时候，只有一种走法，当n=2时候有...

2221

3624

### 1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路 Time Limit: 5 Sec  Memory L...

3346

### 1010. 邮寄包裹

1010. 邮寄包裹 (Standard IO) 时间限制: 1000 ms  空间限制: 262144 KB  具体限制  题目描述 某邮局对邮寄包裹有如下...

41911