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

2018.2.12 省选模拟赛的相关文章

2018.3.10 省选模拟赛

从这里开始 概况 Problem A 三元组 Problem B 攻略 Problem C 迂回 概况 这是省选T1合集?还是欢乐AK赛? 全班一半以上的人三道题都会做qwq. Doggu还剩一小时时以为自己AK了,然后玩了一小时.虽然最终被卡了20分的常数. ZJC 1个半小时AK?Excuse me? 我这条大咸鱼到最后10分钟才敲完了T1,然后发现线段树要T掉. 发自内心鄙视垃圾出题人卡常数,本来的欢乐AK变成280. 教练给我们考4个小时的试,题面上也这么写的,看题解,woc,考试时间3

2018/3/9 省选模拟赛 0分

第二题模拟扫一遍就可以过,不能更划算了.q=1的30分写的比100分还麻烦,有趣哦. 破暴力40分也没什么可写了,日常辣鸡吃枣药丸. 原文地址:https://www.cnblogs.com/137shoebills/p/8533870.html

2018/3/27 省选模拟赛 140分

T1 树归 100 T2 写的快速幂卷积 40,超时了,正解是矩阵乘法之类的. 正解 1 暴力(m<=5):将x的所有约数提出来矩阵乘法 2 3 定义乘法同构: 4 A=p[1]^a[1] * p[2]^a[2] * ... * p[n]^a[n] 5 B=q[1]^b[1] * q[2]^b[2] * ... * q[n]^b[n] 6 其中p[i]与q[i]皆为质数 7 将数组a与b降序排序后如果是完全相同的,那么称A与B是乘法同构的 8 如 2*2*2*2*3*3*5 与 7*11*11*

2018/3/29 省选模拟赛 80

我真是太菜了... T1 10分纯暴力没写,20分容斥也没写(人就是懒死的).还有30分矩乘不会 正解 <IOI2018 中国国家集训队第一阶段作业题解部分 - 杭州第二中学 吴瑾昭.pdf>最后一题 T2  以为自己能拿到50分,但是其实那个暴力算法只能过10分的点,n=2000的20分数据用n^3带剪枝过不了,所以拿了30分. 正解 <计数与期望问题选讲 CLJ.pdf>最后一题 我记得我以前好像看到过这个文档但是没读过..今天读一下 T3 依然是分情况50分,30分树归20分

2018.6.29 省选模拟赛

*注意:这套题目应版权方要求,不得公示题面. 从这里开始 Problem A 小D与电梯 Problem B 小D与田野 Problem C 小D与函数 Problem A 小D与电梯 题目大意 假设电梯在0层,容量无限大.给定$n$个人的到达时间和要去的楼层.电梯上下一层楼花费的时间为1,电梯开关门.乘客上下的耗时不计,电梯可以停留在某一层楼.问将所有人送达到目的地,并让电梯回到0层的最少耗时. 先按到达时间将所有人排序.显然,每次电梯运输的人是一段连续的区间中的人. 用$f[i]$表示将前$

2018.2.23 省选模拟赛

从这里开始 Problem A cycle Problem B meal Problem C naive Problem A cycle 判断是否有经过一个点的负环,我们可以跑最短路.判断这个点到自己的最短路是否是负数. 于是可以二分环大小跑dfs版spfa. 于是可以分层图做时间复杂度四方的dp. (YYR给的数据水得吓人,这两个做法居然都跑过了.然后都被我和jmr卡掉了) 注意到如果一个点走不超过$k$条边回到自己的最短路的长度是负数,那么走不超过$k + 1$条边也是. 因此我们可以二分答

@省选模拟赛03/16 - T3@ 超级树

目录 @description@ @solution@ @accepted code@ @details@ @description@ 一棵 k-超级树(k-SuperTree) 可按如下方法得到:取一棵深度为 k 的满二叉树,对每个节点向它的所有祖先连边(如果这条边不存在的话). 例如,下面是一个 4-超级树: 请统计一棵 k-超级树 中有多少条不同的简单有向路径,对 mod 取模. input 一行两整数 k, mod. output 一行一整数表示答案. example input1: 2

xjoi省选模拟赛_14

T1 发现 对于当前 投出 奇数次向上的概率为 p 那么 若加入一个 pi=0.5 的骰子 发现  p奇 +1=p奇 * 0.5+p偶 * 0.5 = p偶+1  也就是说 只要方案中存在一个 p=0.5 的骰子 这个方案必然合法  : 1 #include <bits/stdc++.h> 2 #define N 100 3 #define eps 1e-7 4 using namespace std; 5 typedef long double ldb; 6 int t,n; 7 ldb A

2018/3/1 省选模拟考试 50分

T1 30分模拟暴力,40分树的直径.拿了0分.(空间开小了爆了,因为缩点之后是又建了一次图,两个边的编号tot没分开,mdzz) 只写了后40分,而这40分中有20分不需要边双连通分量.写了一个类似于强连通分量(标记双向边)的缩点,应该实现哪里出了偏差,因为就算空间开大改正tot的bug也还是20分. T2 写了50分纯暴力 会bsgs可以得80分好像,但是我只会快速幂和暴力,所以50. T3 看了题目,没写,感觉是lca和一些神奇的操作.题解看上去是一个挺裸的lca,亏了. 原文地址:htt