首页 > > 程序设计 > C/C++ >

Day3上午解题报告

2018-06-17 21:38:35来源：未知阅读 ()

预计分数：100+40+50=190

实际分数：100+40+50=190

T1

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 }

View Code

T2

不会做，打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 }

40暴力

正解：

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 }

View Code

T3

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 }