感覺還是該從今天開始記下來

5.8日查詢 870(查詢系統(tǒng)) + 100(洛谷) + 100(牛客) = 1070題, 去重按1000題算

?

5.8

牛客寒訓(xùn)營 3F 雙向搜索+處理前后綴積

牛客寒訓(xùn)營 5G 唯一分解, 埃氏篩法的理解

牛客寒訓(xùn)營 5D 二進(jìn)制, 關(guān)于建圖的一個有意思的思維題

還是牛客寒訓(xùn)5 E題, 線段樹維護(hù)區(qū)間RMQ, 還有一個神奇的樹狀數(shù)組姿勢

?

5.9

牛客寒訓(xùn)營 5 B, H, F 一些姿勢題

?

5.10

牛客寒訓(xùn)營 6E, G, J思維

?

5.11

Gym101875 ABCDEFJIL

CF Round#558 B2

?

5.12

牛客寒訓(xùn)營 6H 單調(diào)隊列

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 樹狀數(shù)組+離散化求貢獻(xiàn)

?

5.15

病假

?

5.16

鴿

?

5.21

CF 573B 單調(diào)隊列搞一搞

?

5.27

camp day1 F 爬山 最短路搞搞

?

?

?

?

----------------------------------------------------暑訓(xùn)的分割線------------------------------------------------------------

?

7.9

今天開始暑訓(xùn)，廢了一個多月開始刷手感，目前的任務(wù)是補(bǔ)10場cf，希望暑訓(xùn)下來省賽能整個銀，不要再給我破銅爛鐵了

（胡適之日記警告

?

CF Round #572 ABCD1E 知道RMQ不會手寫×1，初中數(shù)競技巧不會×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?

咕了好幾天

主要是學(xué)了一下SG函數(shù)打表 補(bǔ)了補(bǔ)狀壓dp

BZOJ 4197 BUG了很多次

設(shè)f[i][j][k]表示前i個,兩個人狀態(tài)為j和k時的方案,為了表示重復(fù)的大質(zhì)數(shù)還要設(shè)dp[0/1][i][j][k]表示對應(yīng)的第一個人拿和第二個人拿的方案

i可以完全和01背包那樣滾動掉然后我滾動忘記倒序了(

然后是"完全沒拿大質(zhì)數(shù)"的去重,在處理完這個大質(zhì)數(shù)的時候才執(zhí)行

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

轉(zhuǎn)載于:https://www.cnblogs.com/QAQorz/p/10833922.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的QAQorz的训练记录的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。