QAQorz的训练记录

感觉还是该从今天开始记下来

5.8日查询 870(查询系统) + 100(洛谷) + 100(牛客) = 1070题, 去重按1000题算

5.8

牛客寒训营 3F 双向搜索+处理前后缀积

牛客寒训营 5G 唯一分解, 埃氏筛法的理解

牛客寒训营 5D 二进制, 关于建图的一个有意思的思维题

还是牛客寒训5 E题, 线段树维护区间RMQ, 还有一个神奇的树状数组姿势

5.9

牛客寒训营 5 B, H, F 一些姿势题

5.10

牛客寒训营 6E, G, J思维

5.11

Gym101875 ABCDEFJIL

CF Round#558 B2

5.12

牛客寒训营 6H 单调队列

CF Round#558 C1 C2计算几何

CF Round#552 E 线段树+链表

CF Round#553 C, D

5.13

ICPC 2018 南京 ADGIJ

5.14

CF 559B 搜索

CF 161D 树型dp

CF 225C dp

CF 459D 树状数组+离散化求贡献

5.15

病假

5.16

鸽

5.21

CF 573B 单调队列搞一搞

5.27

camp day1 F 爬山最短路搞搞

----------------------------------------------------暑训的分割线------------------------------------------------------------

7.9

今天开始暑训，废了一个多月开始刷手感，目前的任务是补10场cf，希望暑训下来省赛能整个银，不要再给我破铜烂铁了

（胡适之日记警告

CF Round #572 ABCD1E 知道RMQ不会手写×1，初中数竞技巧不会×1

CF edu 57 ABC wa好多，读错好多

7.10

CF edu 57 DE 线段树和树上乱搞，偏思维但没想出来或者想假了QAQ

CF Round #570 CDG H dp+去重

CF Round #297 BCD E 用的折半搜索

7.11

CF Round #298 CD E哈希

7.12

CF Round #298 F 哈希搜索剪枝 set记忆化

搞了一整天orz

 1 #include <bits/stdc++.h>
 2 #include <unordered_map>
 3 #define INF 0x3f3f3f3f
 4 #define debug(x) cout << #x << " = " << x << endl;
 5 #define lid id << 1
 6 #define rid id << 1 | 1
 7 using namespace std;
 8 typedef long long LL;
 9 typedef unsigned long long uLL;
10 typedef pair<int,int> pii;
11 typedef pair<LL, LL> pll;
12 
13 const int base = 131;
14 int a[6], b[22], vis[22];
15 int n, m;
16 vector<int> v[5];
17 char s[6][22];
18 unordered_set<uLL> dp[22][35];
19 
20 uLL ans = 0;
21 bool ok = 0;
22 
23 void print_ans(){
24     for (int i = 1; i <= m; i++){
25         int x = vis[i];
26         for (int j = 1; j <= n; j++) {
27             s[j][i] = x&(1<<(j-1)) ? '*' : '.';
28         }
29     }
30     for (int i = 1; i <= n; i++){
31         for (int j = 1; j <= m; j++) putchar(s[i][j]);
32         putchar('
');
33     }
34 }
35 
36 void dfs(int u, int pre){
37     uLL hs = 0;
38     for (int i = 1; i <= n; i++)
39         hs = hs*base+a[i];
40     if (u == m+1){
41         if (!hs) {
42             ok = 1;
43             print_ans();
44         }
45         return;
46     }
47     if (dp[u][pre].count(hs)) return;
48     for (int i = 0; i < v[b[u]].size(); i++){
49         bool f = 1;
50         for (int j = 0; j < n; j++){
51             if ((v[b[u]][i] & (1<<j)) && !(pre & (1<<j))) a[j+1]--;
52             if (a[j+1] < 0 || (m-u)/2+1 < a[j+1]) {
53                 f = 0;
54             }
55         }
56         //printf("%d %d %d
", u, v[b[u]][i], f);
57         if (f) {
58             vis[u] = v[b[u]][i];
59             dfs(u + 1, v[b[u]][i]);
60             if (ok) return;
61         }
62         for (int j = 0; j < n; j++){
63             if ((v[b[u]][i] & (1<<j)) && !(pre & (1<<j)))
64                 a[j+1]++;
65         }
66     }
67     dp[u][pre].insert(hs);
68 }
69 
70 int main() {
71     scanf("%d%d", &n, &m);
72     for (int i = 1; i <= n; i++) {
73         scanf("%d", &a[i]);
74         ans = ans*base+a[i];
75     }
76     for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
77     for (int i = 0; i < (1<<n); i++){
78         int x = i, num = 0, pre = 0;
79         while (x){
80             if (x & 1 && !pre) num++;
81             pre = x & 1;
82             x >>= 1;
83         }
84         v[num].push_back(i);
85     }
86     dfs(1, 0);
87     return 0;
88 }

View Code

7.13

几道很水的1k8 dp

7.17

咕了好几天

主要是学了一下SG函数打表补了补状压dp

BZOJ 4197 BUG了很多次

设f[i][j][k]表示前i个,两个人状态为j和k时的方案,为了表示重复的大质数还要设dp[0/1][i][j][k]表示对应的第一个人拿和第二个人拿的方案

i可以完全和01背包那样滚动掉然后我滚动忘记倒序了(

然后是"完全没拿大质数"的去重,在处理完这个大质数的时候才执行

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 #define INF 0x3f3f3f3f
 6 #define INFLL 0x3f3f3f3f3f3f3f3f
 7 #define debug(x) cout << #x << " = " << x << endl;
 8 #define lid id << 1
 9 #define rid id << 1 | 1
10 using namespace std;
11 typedef long long LL;
12 
13 int prime[] = {2, 3, 5, 7, 11, 13, 17, 19};
14 const int mx = 510;
15 struct node{
16     int s, p;
17     bool operator < (const node& a) const {
18         return p < a.p;
19     }
20 }sta[mx];
21 LL f[1<<8][1<<8];
22 LL dp[2][1<<8][1<<8];
23 
24 int main() {
25     int n, mod;
26     scanf("%d%d", &n, &mod);
27     for (int i = 2; i <= n; i++){
28         int x = i;
29         for (int j = 0; j < 8; j++){
30             while (x % prime[j] == 0){
31                 x /= prime[j];
32                 sta[i].s |= (1<<j);
33             }
34         }
35         sta[i].p = x;
36     }
37     sort(sta+2, sta+n+1);
38     f[0][0] = 1;
39     for (int i = 2; i <= n; i++) {
40         if (sta[i].p == 1 || sta[i].p != sta[i - 1].p) {
41             memcpy(dp[0], f, sizeof f);
42             memcpy(dp[1], f, sizeof f);
43         }
44         for (int j = (1<<8)-1; j >= 0; j--) {
45             for (int k = (1<<8)-1; k >= 0; k--) {
46                 if (j & k) continue;
47                 if (!(sta[i].s & k)) {
48                     dp[0][j | sta[i].s][k] += dp[0][j][k];
49                     dp[0][j | sta[i].s][k] %= mod;
50                 }
51                 if (!(sta[i].s & j)) {
52                     dp[1][j][k | sta[i].s] += dp[1][j][k];
53                     dp[1][j][k | sta[i].s] %= mod;
54                 }
55             }
56         }
57         if (sta[i].p == 1 || sta[i].p != sta[i + 1].p) {
58             for (int j = (1<<8)-1; j >= 0; j--) {
59                 for (int k = (1<<8)-1; k >= 0; k--) {
60                     if (j & k) continue;
61                     f[j][k] = (dp[0][j][k] + dp[1][j][k] - f[j][k] + mod) % mod;
62                 }
63             }
64         }
65     }
66     LL ans = 0;
67     for (int j = 0; j < (1<<8); j++){
68         for (int k = 0; k < (1<<8); k++){
69             if (j & k) continue;
70             ans += f[j][k];
71             ans %= mod;
72         }
73     }
74     printf("%lld
", ans);
75     return 0;
76 }

View Code

7.18

codeforces Round #574 D2 E

7.23

咕咕咕了好多天。。。

菜爆了。。。

camp day1图论专题：CF 449B 585B 489D

7.25

HDU 6581 二分 / O(n)做法

CF 1100F / HDU6579 / 牛客多校1H 各种线性基

hdu多校1-1004代码：

 1 #include <bits/stdc++.h>
 2 #include <unordered_map>
 3 #define INF 0x3f3f3f3f
 4 #define debug(x) cout << #x << " = " << x << endl;
 5 using namespace std;
 6 typedef long long LL;
 7 typedef pair<int, int> pii;
 8 
 9 const int mx = 1e6+7;
10 int b[mx][31], pos[mx][31];
11 
12 void add(int x, int i){
13     memcpy(b[i], b[i-1], sizeof b[i]);
14     memcpy(pos[i], pos[i-1], sizeof pos[i]);
15     int p = i;
16     for (int j = 30; j >= 0; j--){
17         if (x & (1<<j)){
18             if (!b[i][j]) {
19                 b[i][j] = x;
20                 pos[i][j] = p;
21                 break;
22             }
23             if (pos[i][j] < p){
24                 swap(pos[i][j], p);
25                 swap(b[i][j], x);
26             }
27             x ^= b[i][j];
28         }
29     }
30 }
31 
32 int main() {
33     int n, q, t, x;
34     scanf("%d", &t);
35     while (t--){
36         scanf("%d%d", &n, &q);
37         for (int i = 1; i <= n; i++){
38             scanf("%d", &x);
39             add(x, i);
40         }
41         int op, l, r, v = 0;
42         while (q--){
43             scanf("%d%d", &op, &l);
44             l ^= v;
45             if (!op){
46                 scanf("%d", &r);
47                 l %= n, l++;
48                 (r ^= v) %= n, r++;
49                 if (l > r) swap(l, r);
50                 int ans = 0;
51                 for (int j = 30; j >= 0; j--){
52                     if (b[r][j] && pos[r][j] >= l)
53                         ans = max(ans, ans^b[r][j]);
54                 }
55                 printf("%d
", ans);
56                 v = ans;
57             } else {
58                 n++;
59                 add(l, n);
60             }
61         }
62     }
63     return 0;
64 }

View Code

7.26

牛客多校1E 想明白前n个A和前m个B很水的一dp

洛咕提高场的一些dp

7.29

居然放了两天假，丢人捂脸逃（

dp优化专题，出奇的简单（x

BZOJ 1264 2131 树状数组优化

7.30

带修主席树（树状数组套主席树）

BZOJ 1901 洛谷3157（一个省空间一些的动态开点方法，修改不用保存历史版本）

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 #define debug(x) cout << #x << " = " << x << endl;
 4 using namespace std;
 5 typedef long long LL;
 6 typedef pair<int, int> pii;
 7 
 8 const int mx = 2e5+10;
 9 int a[mx], pos[mx];
10 int root[mx];
11 int n, tot = 1;
12 int ls[mx*50], rs[mx*50], sum[mx*50];
13 int L[mx], R[mx];
14 
15 inline int lowbit(int x){
16     return x & (-x);
17 }
18 
19 void upd(int& rt, int l, int r, int k, int v){
20     //这样写比原来省空间
21     if (!rt) rt = tot++;
22     sum[rt] += v;
23     if (l == r) return;
24     int mid = (l+r)>>1;
25     if (k <= mid) upd(ls[rt], l, mid, k, v);
26     else upd(rs[rt], mid+1, r, k, v);
27 }
28 
29 //l..r中有多少个比k要f(0大,1小)的
30 int query(int l, int r, int k, bool f){
31     int cntl = 0, cntr = 0;
32     for (int i = l-1; i > 0; i -= lowbit(i)) L[++cntl] = root[i];
33     for (int i = r; i > 0; i -= lowbit(i)) R[++cntr] = root[i];
34     int suml = 0, sumr = 0;
35     l = 1, r = n;
36     while (l != r){
37         int mid = (l+r)>>1;
38         if (k <= mid){
39             if (!f){
40                 for (int i = 1; i <= cntl; i++) suml += sum[rs[L[i]]];
41                 for (int i = 1; i <= cntr; i++) sumr += sum[rs[R[i]]];
42             }
43             for (int i = 1; i <= cntl; i++) L[i] = ls[L[i]];
44             for (int i = 1; i <= cntr; i++) R[i] = ls[R[i]];
45             r = mid;
46         } else {
47             if (f){
48                 for (int i = 1; i <= cntl; i++) suml += sum[ls[L[i]]];
49                 for (int i = 1; i <= cntr; i++) sumr += sum[ls[R[i]]];
50             }
51             for (int i = 1; i <= cntl; i++) L[i] = rs[L[i]];
52             for (int i = 1; i <= cntr; i++) R[i] = rs[R[i]];
53             l = mid+1;
54         }
55     }
56     return sumr-suml;
57 }
58 
59 int main() {
60     int m, x;
61     scanf("%d%d", &n, &m);
62     LL ans = 0;
63     for (int i = 1; i <= n; i++) {
64         scanf("%d", &a[i]);
65         pos[a[i]] = i;
66         ans += query(1, i-1, a[i], 0);
67         for (int j = i; j <= n; j += lowbit(j))
68             upd(root[j], 1, n, a[i], 1);
69     }
70     printf("%lld
", ans);
71     for (int i = 1; i < m; i++){
72         scanf("%d", &x);
73         ans -= query(1, pos[x]-1, x, 0);
74         ans -= query(pos[x]+1, n, x, 1);
75         printf("%lld
", ans);
76         for (int j = pos[x]; j <= n; j += lowbit(j))
77             upd(root[j], 1, n, x, -1);
78     }
79     return 0;
80 }

View Code

7.31

重新理解了一下主席树

学回文树

8.1

洛谷 P3649 P4287 P1435 回文树的各种姿势

8.4

初学cdq 刚会用cdq写树状数组裸题'

8.6

点分治明天再来写博客

8.7

斜率优化。。开一题又是斜率优化，开一题又是。。。

自闭了。。

8.8

连续数天的打牌打牌打牌.jpg。。。

（太怠惰了

BZOJ 1597 4518 都是斜率优化水题

早点切到线段树优化那几题我就不写专题了去补多校真香

8.9

线段树优化dp HDU 3698 4719 CF834D

牛客多校day1-I

8.21

优秀的博客 https://blog.csdn.net/huangjingyuan107/article/details/82829040

终于让我明白了矩阵转移

------------------------------------------------------------------------开学的分割线----------------------------------------------------------------------

9.2

最近搞了点分治概率矩阵，接下来搞扫描线，CDQ，杜教筛，串串吧

今日发现：线性推逆元记得mod开LL

9.5

整体二分orzorzorzorz，其实跟CDQ几乎一样

然而，对CDQ的感觉还是很迷