2018.2.12 省选模拟赛

题目大意

(题目很简洁了,不需要大意)

  其实显而易见地可以发现,当被卡一次后后面的路程都是固定了的。

  可以用类似动态规划的思想来进行预处理。现在的问题就是怎么知道在某个位置刚等完红灯然后出发会在哪个路口再次被卡。

  尝试画一画图:

  其中横轴表示位置,纵轴表示时间,长方体表示红灯时段。有用的部分长度只有$r + g$,所以在模意义下弄一下就可以减少很多重复和无用状态:

  但是这样仍然不好处理上面提到的问题,考虑让线段横着走,第一个撞着的长方形就是答案。为了实现这个目标,就每个长方形向下移动一段(移动的距离与它和它距起点的距离有关)

  比如可能修改后就成了这样。然后就可以从后向前区间覆盖来预处理每个路口刚等完红灯然后到终点的耗时。

Code

 1 // 2018-2-13 Test
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <ctime>
 6 #include <map>
 7 #ifndef WIN32
 8 #define Auto "%lld"
 9 #else
10 #define Auto "%I64d"
11 #endif
12 using namespace std;
13 typedef bool boolean;
14 #define ll long long
15 #define iter map<int, int>::iterator
16
17 int n, g, r, s;
18 int q;
19 ll *len;
20 ll *dis;
21 map<int, int> mp;
22
23 inline void init() {
24     scanf("%d%d%d", &n, &g, &r);
25     s = g + r;
26     len = new ll[(n + 2)];
27     dis = new ll[(n + 2)];
28     for (int i = 0; i <= n; i++)
29         scanf(Auto, len + i);
30 }
31
32 inline void cover(int l, int r, int x) {
33     iter il = mp.lower_bound(l), ir = mp.upper_bound(r);
34     int temp = -1;
35     if (ir == mp.end() || ir->first > r + 1) {
36         temp = (--ir)->second;
37         ir++;
38     }
39     mp.erase(il, ir);
40     mp[l] = x;
41     if (~temp)
42         mp[r + 1] = temp;
43 //    cerr << l << " " << r << endl;
44 }
45
46 inline void solve() {
47     mp[0] = n + 1;
48     dis[n + 1] = 0;
49     for (int i = 1; i <= n; i++)
50         len[i] += len[i - 1];
51     iter it;
52     for (int i = n; i; i--) {
53         int r = -len[i - 1] % s, l = r + g;
54         if (r < 0)    r += s;
55         if (l < 0)    l += s;
56         it = mp.upper_bound(r);
57         int j = (--it)->second;
58         int rest = (r + len[j - 1]) % s;
59         int wait = (j != n + 1 && rest >= g) ? (s - rest) : (0);
60         dis[i] = len[j - 1] - len[i - 1] + wait + dis[j];
61         r = (r) ? (r - 1) : (s - 1);
62         if (l <= r)
63             cover(l, r, i);
64         else
65             cover(0, r, i), cover(l, s - 1, i);
66 //        cerr << dis[i] << endl;
67     }
68     ll t;
69     scanf("%d", &q);
70     while (q--) {
71         scanf(Auto, &t);
72         it = mp.upper_bound(t % s);
73         int j = (--it)->second;
74         int r = (t + len[j - 1]) % s;
75         int wait = (j != n + 1 && r >= g) ? (s - r) : (0);
76         printf(Auto"\n", t + wait + len[j - 1] + dis[j]);
77     }
78 }
79
80 int main() {
81     freopen("brt.in", "r", stdin);
82     freopen("brt.out", "w", stdout);
83     init();
84     solve();
85     return 0;
86 }

题目大意

  给定$A$数组,每次可以选出$A$数组中没有选过的一个无序对$(A_{i},A_{j})$,然后得到的分数是$A_{i} xor A_{j}$,问选取$m$次得到的最大的分数和模$10^{9} + 7$

  想骂一句这道题,100%的数据不给$m$的范围,我一直以为$n, m$同阶,没见过这样坑题面的。。。

  显然需要把每个数放入Trie树中。然后二分一下得到第$m$大的值。

  然后考虑在Trie上搞点小计数来得到前$k$大和指定数的异或值的和。考虑每个节点记录一下它的子树中包含的数,每一位上的1的个数。

  然后就可以做了。

  真心怀疑这道题有毒,考试时用空间复杂度O(31(n + m))的算法,然后MLE。考完后改题,死活因为常数问题TLE。。为什么这道题这么不友好

Code

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <queue>
  5 using namespace std;
  6 typedef bool boolean;
  7
  8 const int M = 1e9 + 7;
  9
 10 typedef class TrieNode {
 11     public:
 12         int cnt;
 13         int cnts[32];
 14         TrieNode *ch[2];
 15
 16         TrieNode()    {    }
 17         TrieNode(int cnt, TrieNode* ch1, TrieNode* ch2):cnt(cnt) {
 18             ch[0] = ch1, ch[1] = ch2;
 19             memset(cnts, 0, sizeof(cnts));
 20         }
 21 }TrieNode;
 22
 23 #define Limit 1700000
 24
 25 TrieNode pool[Limit];
 26 TrieNode* top = pool;
 27
 28 TrieNode* newnode() {
 29     if (top == pool + Limit)
 30         return new TrieNode(0, NULL, NULL);
 31     top->cnt = 0, top->ch[0] = top->ch[1] = NULL;
 32     memset(top->cnts, 0, sizeof(top->cnts));
 33     return top++;
 34 }
 35
 36 TrieNode* newnode(TrieNode* old) {
 37     TrieNode* rt = newnode();
 38     if (old == NULL)    return rt;
 39     *rt = *old;
 40     return rt;
 41 }
 42
 43 typedef class Trie {
 44     public:
 45         TrieNode* rt;
 46
 47         Trie():rt(NULL)    {    }
 48
 49         TrieNode* modify(TrieNode* p, int x, int temp, int cnt) {
 50             TrieNode* np = newnode(p);
 51             int d = ((x & temp) ? (1) : (0));
 52             np->cnt += cnt;
 53             if (!temp)    return np;
 54             for (int i = 0, j = 1; i <= 30; i++, j <<= 1)
 55                 np->cnts[i] += ((x & j) ? (1) : (0));
 56             np->ch[d] = modify(np->ch[d], x, temp >> 1, cnt);
 57             return np;
 58         }
 59
 60         void modify(int x, int cnt) {
 61             rt = modify(rt, x, 1 << 30, cnt);
 62         }
 63
 64         int rank(int x, int a) {
 65              TrieNode *p = rt;
 66             int ret = 0, temp = 1 << 30;
 67             while (temp && p) {
 68                 int dx = ((x & temp) ? (1) : (0)), da = ((a & temp) ? (1) : (0));
 69                 if (dx == 0)
 70                     ret += ((p->ch[da ^ 1]) ? (p->ch[da ^ 1]->cnt) : (0)), p = p->ch[da];
 71                 else
 72                     p = p->ch[da ^ 1];
 73                 temp >>= 1;
 74             }
 75             return ret;
 76         }
 77
 78         int ksums(int k, int a) {
 79             TrieNode* p = rt;
 80             int ret = 0, temp = 1 << 30;
 81             while (temp && p) {
 82                 int da = ((a & temp) ? (1) : (0));
 83                 int ls = (p->ch[da ^ 1]) ? (p->ch[da ^ 1]->cnt) : (0);
 84                 if (k >= ls) {
 85                     TrieNode* l = p->ch[da ^ 1];
 86                     if (l)
 87                         for (int i = 0, j = 1, dx; i <= 30; i++, j <<= 1) {
 88                             dx = ((a & j) ? (l->cnt - l->cnts[i]) : (l->cnts[i]));
 89                             ret = (ret + (dx * 1ll * j)) % M;
 90                         }
 91                     k -= ls;
 92                     p = p->ch[da];
 93                 } else
 94                     p = p->ch[da ^ 1];
 95                 temp >>= 1;
 96             }
 97             return ret;
 98         }
 99 }Trie;
100
101 int n, m;
102 int* ar;
103 Trie* ts;
104
105 inline void init() {
106     scanf("%d%d", &n, &m);
107     ar = new int[(n + 1)];
108     ts = new Trie[(n + 1)];
109     for (int i = 1; i <= n; i++)
110         scanf("%d", ar + i);
111 }
112
113 inline int check(int mid) {
114     long long rt = 0;
115     for (int i = 2; i <= n && rt < m; i++)
116         rt += ts[i].rank(mid, ar[i]);
117     return rt;
118 }
119
120 int res = 0;
121 inline void solve() {
122     for (int i = 2; i <= n; i++) {
123         ts[i].rt = ts[i - 1].rt;
124         ts[i].modify(ar[i - 1], 1);
125     }
126
127     int l = 0, r = (signed) (~0u >> 1);
128     while (l <= r) {
129         int mid = l + ((r - l) >> 1);
130         if (check(mid) < m)
131             r = mid - 1;
132         else
133             l = mid + 1;
134     }
135
136     int sk = 0, k;
137     for (int i = 2; i <= n; i++) {
138         k = ts[i].rank(r + 1, ar[i]);
139         res = (res + ts[i].ksums(k, ar[i])) % M;
140         sk += k;
141     }
142
143     res = (res + (m - sk) * 1ll * (r + 1)) % M;
144
145     printf("%d\n", res);
146 }
147
148 int main() {
149     freopen("xor.in", "r", stdin);
150     freopen("xor.out", "w", stdout);
151     init();
152     solve();
153     return 0;
154 }

题目大意

  请维护一个数据结构,使得它能支持:

  1. 区间加上$k$
  2. 区间询问从1开始的前缀和的最大值

  记得去年省选后,自己yy出了这么一道题,然而并不会做,就跑去问学长,学长告诉我分块加斜率等等,然而我并没有懂,觉得这么"独流"的题应该没人考吧。现在觉得脸好疼啊。

  但是我觉得最毒的是,我写的纯暴力在氧气优化下拿了80分.全班开始都以为我是正解写挂了。

  考虑区间加上$k$对前缀和的影响,画个图比较直观:

  其中一段加的是等差数列,后一段就是普通的区间加法。

  若将每个位置看成一个点,横坐标为下标,纵坐标为前缀和,那么对询问区间维护一个上凸壳,答案就是斜率为0的直线和凸壳的切点。

  对于区间加上一个公差为k的等差数列,相当于任意两点之间斜率增加$k$。修改后凸壳的点集显然不会改变。另外标记显然可加。

  但是难以快速合并两个凸壳,为了避免合并凸壳,所以采用分块。

  每个块维护一个凸壳,斜率标记,区间加法标记。

  考虑修改操作,区间两端暴力重构块,中间的打tag,后边把tag也打上。

  考虑查询操作,区间两端暴力找,中间在凸壳上二分(只是注意一下tag的存在),最后把答案一起取个max。

  中间取值的时候不要忘记tag的存在。

  (由于这道题和bzoj 2388除了题目描述不一样,我就直接贴bzoj 2388的代码了)

Code

  1 /**
  2  * bzoj
  3  * Problem#2388
  4  * Accepted
  5  * Time: 39696ms
  6  * Memory: 3520k
  7  */
  8 #include <bits/stdc++.h>
  9 #ifndef WIN32
 10 #define Auto "%lld"
 11 #else
 12 #define Auto "%I64d"
 13 #endif
 14 using namespace std;
 15 typedef bool boolean;
 16 #define ll long long
 17
 18 const int cs = 350;
 19 const double eps = 1e-8;
 20
 21 typedef class Chunk {
 22     public:
 23         int s, ed;
 24         ll lazyk;
 25         ll lazys;
 26         ll ar[cs];
 27         int con[cs];
 28
 29         Chunk():s(0), ed(-1), lazyk(0), lazys(0) {        }
 30
 31         double slope(int x1, int x2) {
 32             return (ar[x2] - ar[x1]) * 1.0 / (x2 - x1);
 33         }
 34
 35         void update() {
 36             if (!lazyk && !lazys)    return;
 37             for (int i = 0; i < s; i++)
 38                 ar[i] += lazyk * (i + 1);
 39             for (int i = 0; i < s; i++)
 40                 ar[i] += lazys;
 41             lazyk = lazys = 0;
 42         }
 43
 44         void rebuild() {
 45             ed = -1;
 46             for (int i = 0; i < s; i++) {
 47                 while (ed >= 1 && slope(con[ed - 1], con[ed]) + eps < slope(con[ed], i))
 48                     ed--;
 49                 con[++ed] = i;
 50             }
 51         }
 52
 53         int query() {
 54             int l = 0, r = ed;
 55             while (l <= r) {
 56                 int mid = (l + r) >> 1;
 57                 if (!mid || slope(con[mid - 1], con[mid]) + lazyk > eps)
 58                     l = mid + 1;
 59                 else
 60                     r = mid - 1;
 61             }
 62             return con[l - 1];
 63         }
 64
 65         ll getRealValue(int p) {
 66             return ar[p] + (p + 1) * lazyk + lazys;
 67         }
 68 }Chunk;
 69
 70 int n, m;
 71 ll *ar;
 72 Chunk ch[350];
 73
 74 inline void init() {
 75     scanf("%d", &n);
 76     ar = new ll[(n + 1)];
 77     Chunk* p = ch;
 78     for (int i = 0; i < n; i++)
 79         scanf(Auto, ar + i);
 80     for (int i = 1; i < n; i++)
 81         ar[i] += ar[i - 1];
 82     for (int i = 0; i < n; i++) {
 83         p->ar[p->s++] = ar[i];
 84         if (p->s == cs)
 85             p->rebuild(), p++;
 86     }
 87 }
 88
 89 inline void bmodify(Chunk* p, int l, int r, ll k, ll s) {
 90     p->update();
 91     for (int i = 0; i <= r - l; i++)
 92         p->ar[l + i] += s + k * (i + 1);
 93     p->rebuild();
 94 }
 95
 96 inline ll bquery(Chunk* p, int l, int r) {
 97     p->update();
 98     ll rt = p->ar[l];
 99     for (int i = l + 1; i <= r; i++)
100         if (rt < p->ar[i])
101             rt = p->ar[i];
102     return rt;
103 }
104
105 inline void solve() {
106     int opt, l, r;
107     ll k, base;
108     scanf("%d", &m);
109     while (m--) {
110         scanf("%d%d%d", &opt, &l, &r);
111         l--, r--;
112         if (!opt) {
113             scanf(Auto, &k);
114             base = 0;
115             for (int i = l, ni; i <= r; i = ni) {
116                 ni = (i / cs + 1) * cs;
117                 Chunk* p = ch + (i / cs);
118                 if ((i % cs) || ni > r)
119                     bmodify(p, i % cs, (ni > r) ? (r % cs) : (cs - 1), k, base);
120                 else
121                     p->lazyk += k, p->lazys += base;
122                 base += (ni - i) * k;
123             }
124             base = k * (r - l + 1);
125             for (int i = r + 1, ni; i < n; i = ni) {
126                 ni = (i / cs + 1) * cs;
127                 Chunk* p = ch + (i / cs);
128                 if ((i % cs) || ni >= n)
129                     bmodify(p, i % cs, (ni >= n) ? ((n - 1) % cs) : (cs - 1), 0, base);
130                 else
131                     p->lazys += base;
132             }
133         } else {
134             ll res = 1ll << 63, cmp;
135             for (int i = l, ni; i <= r; i = ni) {
136                 ni = (i / cs + 1) * cs;
137                 Chunk *p = ch + (i / cs);
138                 if ((i % cs) || ni > r)
139                     cmp = bquery(p, i % cs, (ni > r) ? (r % cs) : (cs - 1));
140                 else
141                     cmp = p->getRealValue(p->query());
142                 if (cmp > res)
143                     res = cmp;
144             }
145             printf(Auto"\n", res);
146         }
147     }
148 }
149
150 int main() {
151     init();
152     solve();
153     return 0;
154 }

原文地址:https://www.cnblogs.com/yyf0309/p/8447600.html

时间: 02-11