文档章节

QAQorz的训练记录

o
 osc_k0q149k0
发布于 2019/05/08 19:27
字数 2576
阅读 7
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

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

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('\n');
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\n", 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\n", 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\n", 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\n", 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\n", 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的感觉还是很迷

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
iOS 语音识别

OpenEars是一个开源的iOS类库,用于在iPhone和iPad实现语音识别功能。本demo利用此开源类库实现了简单的语音识别。可以识别:CHANGE、LEFT、RIGHT、FORWARD、BACKWARD、GO等英文,其他语素需...

匿名
2013/03/15
6.3K
0
神经网络库--GoNN

GoNN是一个用GO语言写的神经网络库 GoNN目前实现了BP网络,RBF网络和感知机 在著名的手写体字符识别数据库MNIST上,GoNN达到了98.2%的正确率。 此外,项目中还包含简单的例子:sin曲线拟合、鸾...

fxsjy
2012/11/01
4.2K
0
卷积神经网络初探

前言 目前为止我已经完整地学完了三个机器学习教程:包括“Stanford CS229”,"Machine Learning on Coursrea" 和 "Stanford UFLDL",卷积神经网络是其中最抽象的概念。 维基百科对卷积的数学...

Lee的白板报
2015/12/24
8.4K
14
innodb 5.7.11 版本 所有变量记录

innodbadaptive_flushing 在线可以调整 数据类型 默认值 合法值 Yes boolean on on/off 是否启用innodb根据负载动态刷出脏页的功能。 一般情况下,5.7.5开始,innodb会在实例脏页比例到达inn...

刘伟
2016/04/03
1.3K
1
怎么查询我老婆删除的微信聊天记录?如何查询

以前删除的QQ聊天记录还可以恢复吗?技术QQ:599466688怎么查微信历史聊天记录,删除后的微信好友记录恢复--如果不会,认准官网:QQ【他是QQ:《他是:▲Q:5994/666-88▲》 你找专业这行的人帮你,...

myname666
2016/06/05
14
0

没有更多内容

加载失败,请刷新页面

加载更多

数据获取的小技巧

在大数据如此火的时代,我们要获取更多数据,就要进行数据采集,过滤,然后再进行使用。比如当我们在进行一个项目并且需要大量真实数据时,就需要通过爬虫去获得,有些爬取额数据还不能直接使用,...

xiaotaomi7
37分钟前
21
0
docker cp 容器和虚拟机间的数据拷贝

容器复制到主机 docker cp {container_name}:{source_path} {target_path}#例子: docker cp php:www/php.ini /home/alex/php.ini 主机复制到容器 docker cp {source_path} {container_nam......

关元
45分钟前
25
0
spring boot整合kafaka批量消费

spring boot整合kafaka批量消费: 配置文件: kafka: producer: bootstrap-servers: 127.0.0.1:9092 batch-size: 16785 #一次最多发送数据量 retries: 1 #发送失败后的重复发送次数 buffer-m...

漫步行者
50分钟前
7
0
最新苹果多屏电脑控制技术---ios群控/苹果群控/一键实时同步操作/入门安装步骤以及功能讲解

创联苹果群控是一款通过无线发送命令来操作主控手机来带动全部被控手机,主控手机怎么操作被控手机全部同步进行相同操作,支持一键每台手机输入不一样的文字!无需连接USB数据线、无需XP框架...

osc_bodzcw38
50分钟前
10
0
NOIP模拟赛 编码

题目描述 一个字符串str的p型编码a的定义如下:把str表示成b1个c1,b2个c2…bn个cn,然后将b1,c1,b2,c2,…,bn,cn收尾拼接成的字符串中最短的字符串设为a。例如:字符串122344111可被描述为"1个...

osc_wcs4pa6z
51分钟前
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部