这场比赛演的逼真，感谢队友不杀之恩
总结：卡题了赶紧换，手上捏着的题尽快上机解决
1113~1122
1113：六学家
题意：找出满足ai+aj=ak,i<k<j的个数
题解：用map将每个数映射一下n方暴力扫即可
代码:
#include<bits/stdc++.h> #define fuck(x) cout<<#x<<" = "<<x<<endl; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define ls rt<<1 #define rs rt<<1|1 typedef long long ll; typedef long long LL; const int maxn = 100086; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; using namespace std; map<int, bool>mp[2008]; set<int>st; int a[maxn]; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for(int i = n; i >= 1; i--) { mp[i] = mp[i + 1]; mp[i][a[i]] = true; } int ans = 0; for(int k = 1; k <= n; k++) { for(int l = k - 1; l >= 1; l--) { if(mp[k + 1][a[k] - a[l]]) { ans++; break; } } } printf("%d\n", ans); return 0; }
1114:Tulip Festival
题意：单点修改，区间查询非区间异或值的数的个数
题解：线段树维护区间异或值，由于区间内相同的数字不能超过200个，可以用set和mp乱搞
首先用set记录下标，用于之后的修改操作，mp去重
对于每次修改操作，先query出当前位置的值，然后在mp中查找这个数离散化后的位置，得到位置后在set中删除，如果单点更新的值没有在mp中出现过就加入，然后将离散后的下标放进set中，然后单点更新即可
对于每次查询操作，查询区间的异或值，如果当前异或值没有出现过，那么答案就是区间的长度，如果出现过，就把这个异或值离散化后的下标在set中暴力扫，如果set中的下标在区间的范围内，ans++，最终得到的答案就是区间长度减去ans
代码：
#include<bits/stdc++.h> #define fuck(x) cout<<#x<<" = "<<x<<endl; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define ls rt<<1 #define rs rt<<1|1 typedef long long ll; typedef long long LL; const int maxn = 1000086; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; using namespace std; int a[maxn]; int sum[maxn << 2]; void push_up(int rt) { sum[rt] = sum[ls] ^ sum[rs]; return; } void build(int l, int r, int rt) { if(l == r) { sum[rt] = a[l]; return; } int mid = (l + r) >> 1; build(lson); build(rson); push_up(rt); } void update(int L, int R, int val, int l, int r, int rt) { if(L <= l && r <= R) { sum[rt] = val; return; } int mid = (l + r) >> 1; if(L <= mid) update(L, R, val, lson); if(R > mid) update(L, R, val, rson); push_up(rt); } int query(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) { return sum[rt]; } int mid = (l + r) >> 1; int ans = 0; if(L <= mid) ans ^= query(L, R, lson); if(R > mid) ans ^= query(L, R, rson); return ans; } set<int> st[1100008]; map<int, int>mp; int main() { int n, q; scanf("%d%d", &n, &q); int tot = 0; for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); if(!mp[a[i]]) { mp[a[i]] = ++tot; } st[mp[a[i]]].insert(i); } build(1, n, 1); while(q--) { int op; scanf("%d", &op); if(op == 1) { int pos, val; scanf("%d%d", &pos, &val); int t = query(pos, pos, 1, n, 1); t = mp[t]; st[t].erase(pos); int pval; if(!mp[val]) { mp[val] = ++tot; } pval = mp[val]; st[pval].insert(pos); update(pos, pos, val, 1, n, 1); } else { int l, r; scanf("%d%d", &l, &r); int x = query(l, r, 1, n, 1); if(!mp[x]) { mp[x] = ++tot; printf("%d\n", r - l + 1); } else { x = mp[x]; int ans = 0; set<int>::iterator it = st[x].begin(); for(; it != st[x].end(); it++) { if((*it) >= l && (*it) <= r) { ans++; } else if((*it) > r) { break; } } printf("%d\n", r - l + 1 - ans); } } } }
1115：简单的kmp算法
题意：查询子矩阵
题解：二维hash，手写hash_map会快很多
代码：
#include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #include<unordered_map> #define fuck(x) cout<<#x<<" = "<<x<<endl; #define ls (t<<1) #define rs ((t<<1)|1) using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 1086; const int inf = 2.1e9; const ll Inf = 999999999999999999; const int mod = 1000000007; const double eps = 1e-6; const double pi = acos(-1); int p1[maxn], p2[maxn]; int h[maxn][maxn]; char a[maxn][maxn];//字符矩阵 ull seed1 = 131, seed2 = 13331; //随机种子 void init() { //放在多组外面 p1[0] = p2[0] = 1; for (int i = 1; i <= 1005; i++) { p1[i] = p1[i - 1] * seed1 ; p2[i] = p2[i - 1] * seed2 ; } } void get_h(int n, int m) {//得到n,m区间内的h值 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { h[i][j] = (h[i][j - 1] * seed1 + a[i][j] - 'a' + 1) ; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { h[i][j] = (h[i - 1][j] * seed2 + h[i][j]); } } } ull get_hash(int i, int j, int x, int y) { //终点坐标是i，j，长宽是x，y的矩阵的hash值 return h[i][j] - h[i - x][j] * p2[x] - h[i][j - y] * p1[y] + h[i - x][j - y] * p2[x] * p1[y] ; } const int maxm = 400007; int Head[maxm]; ull viss[maxm]; int Next[maxm]; int tot;//别忘了初始化 bool hash_map(ull n, bool in) { //查询后完成了插入操作 int s = n % maxm; int k = Head[s]; while(k != -1) { if(viss[k] == n) { return true; } k = Next[k]; } if(!in) { return false; } tot++; Next[tot] = Head[s]; viss[tot] = n; Head[s] = tot; return false; } int main() { int n, m, x, y, t; init(); int cases = 0; while (scanf("%d%d%d%d%d", &n, &m, &t, &x, &y) != EOF) { for(int i = 1; i <= n; i++) { scanf("%s", a[i] + 1); } memset(Head, -1, sizeof(Head)); tot = 0; get_h(n, m); for(int i = x; i <= n; i++) { for(int j = y; j <= m; j++) { hash_map(get_hash(i, j, x, y), true); } } int ans = 0; while(t--) { for(int i = 1; i <= x; i++) { scanf("%s", a[i] + 1); } get_h(x, y); if(hash_map(get_hash(x, y, x, y), false)) { ans++; } } printf("Case %d: %d\n", ++cases, ans); } return 0; }
1117： 爬山
题意：查询连续区间的或值大于该区间内最大值的区间个数
题解：
姿势1：统计不合法的区间，然后用总区间个数减去不合法区间个数即可，对于每一个数，将他按二进制位处理，这个数的或值大于这个数，只有当这个数二进制的第j位为0时，向左或者向右拓展时，拓展到的数二进制的第j位不为0时，他们的或值就大于这个数，L[i][j]记录的是第i个数往左拓展时第j位可以拓展的最远的位置，R[i][j]记录的是第i个数往右拓展时第j位可以拓展的最远的位置，这样两个位置包围的位置就是不合法的区间，注意从左往右扫时，可能会出现重复的数，我们要在重复的数里面取离当前点最近的那个点
代码：
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ ＞ ＜ ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! #include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; typedef long long LL; typedef pair<LL, LL> pLL; typedef pair<LL, int> pLi; typedef pair<int, LL> pil;; typedef pair<int, int> pii; typedef unsigned long long uLL; #define ls rt<<1 #define rs rt<<1|1 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define bug printf("*********\n") #define FIN freopen("input.txt","r",stdin); #define FON freopen("output.txt","w+",stdout); #define IO ios::sync_with_stdio(false),cin.tie(0) #define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n" #define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n" #define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n" LL read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const double eps = 1e-8; const int mod = 1e9 + 7; const int maxn = 3e5 + 5; const int INF = 0x3f3f3f3f; const LL INFLL = 0x3f3f3f3f3f3f3f3f; int a[maxn]; int l[maxn][33], r[maxn][33]; unordered_map<int, int> vis,vis1; int main() { #ifndef ONLINE_JUDGE FIN #endif int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for(int i = 1; i <= n; i++) { for(int j = 0; j < 32; j++) { if(a[i] >> j & 1)l[i][j] = i; else l[i][j] = l[i - 1][j]; } } for(int i = 0; i < 32; i++) { r[n + 1][i] = n + 1; } for(int i = n; i >= 1; i--) { for(int j = 0; j < 32; j++) { if(a[i] >> j & 1) { r[i][j] = i; } else { r[i][j] = r[i + 1][j]; } } } LL ans = 0; for(int i = 1; i <= n; i++) { int L = 0, R = n + 1; for(int j = 0; j < 32; j++) { if((a[i] >> j & 1)) continue; L = max(L, l[i][j]); R = min(R, r[i][j]); } L = max(L, vis[a[i]]); vis[a[i]] = i; ans += (LL)(i - L) * (R - i); } printf("%lld\n", (LL)n * (n + 1) / 2 - ans); return 0; }
姿势2：分治+线段树。线段树维护区间最大值和他的位置，用一个pair装起来，分治的话，询问分治的区间【L，R】的最值，然后从这个最值的两边开始找，找到左边最近的 ”或上这个最大值“ 大于 ”最大值“的位置和右边最近的”或上这个最大值“大于”最大值“的位置，然后用乘法计数即可，注意要减去重复的部分
代码:
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ ＞ ＜ ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! #include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; typedef pair<LL, LL> pLL; typedef pair<LL, int> pLi; typedef pair<int, LL> pil;; typedef pair<int, int> pii; typedef unsigned long long uLL; #define ls rt<<1 #define rs rt<<1|1 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define bug printf("*********\n") #define FIN freopen("input.txt","r",stdin); #define FON freopen("output.txt","w+",stdout); #define IO ios::sync_with_stdio(false),cin.tie(0) #define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n" #define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n" #define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n" LL read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const double eps = 1e-8; const int mod = 1e9 + 7; const int maxn = 3e5 + 5; const int INF = 0x3f3f3f3f; const LL INFLL = 0x3f3f3f3f3f3f3f3f; int n; int a[maxn]; pii MAX[maxn << 2]; void push_up(int rt) { if (MAX[rt << 1].first > MAX[rt << 1 | 1].first) MAX[rt] = MAX[rt << 1]; else MAX[rt] = MAX[rt << 1 | 1]; } void build(int l, int r, int rt) { if (l == r) { MAX[rt] = make_pair(a[l], l); return; } int mid = (l + r) >> 1; build(lson); build(rson); push_up(rt); } pii query(int L, int R, int l, int r, int rt) { if (L <= l && r <= R) return MAX[rt]; int mid = (l + r) >> 1; pii res = make_pair(0, 0); if (L <= mid) { pii cnt = query(L, R, lson); if (res.first < cnt.first) res = cnt; } if (R > mid) { pii cnt = query(L, R, rson); if (res.first < cnt.first) res = cnt; } return res; } LL solve(int L, int R) { if (L >= R) return 0; pii cnt = query(L, R, 1, n, 1); int id = cnt.second; int l = id, r = id; while ((a[id] | a[l]) <= a[id] && l >= L) l--; while ((a[id] | a[r]) <= a[id] && r <= R) r++; LL res = 0; if ((a[id] | a[l]) > a[id]) res += LL(l - L + 1) * (R - id + 1); if ((a[id] | a[r]) > a[id]) res += LL(R - r + 1) * (id - L + 1); if ((a[id] | a[l]) > a[id] && (a[id] | a[r]) > a[id]) res -= LL(l - L + 1) * (R - r + 1); res += solve(L, id - 1) + solve(id + 1, R); return res; } int main() { #ifndef ONLINE_JUDGE FIN; #endif scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); build(1, n, 1); printf("%lld\n", solve(1, n)); return 0; }
姿势3：分治+ST表，用ST表查询最大值，分治的姿势和上面相同
代码：
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ ＞ ＜ ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! #include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; typedef pair<LL, LL> pLL; typedef pair<LL, int> pLi; typedef pair<int, LL> pil;; typedef pair<int, int> pii; typedef unsigned long long uLL; #define ls rt<<1 #define rs rt<<1|1 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define bug printf("*********\n") #define FIN freopen("input.txt","r",stdin); #define FON freopen("output.txt","w+",stdout); #define IO ios::sync_with_stdio(false),cin.tie(0) #define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n" #define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n" #define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n" LL read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const double eps = 1e-8; const int mod = 1e9 + 7; const int maxn = 3e5 + 5; const int INF = 0x3f3f3f3f; const LL INFLL = 0x3f3f3f3f3f3f3f3f; LL ans; int n, f[200005][20], a[200005][31]; int x[200005], pre[200005][31], nxt[200005][31]; void zh(int i, int x) { int len = 0; while (x) { a[i][++len] = x & 1; x >>= 1; } while (len < 30) a[i][++len] = 0; } int MAX(int L, int R) { int k = (double)log(R - L + 1) / (double)log(2); if (x[f[L][k]] > x[f[R - (1 << k) + 1][k]]) return f[L][k]; else return f[R - (1 << k) + 1][k]; } void solve(LL L, LL R) { if (L > R) return; int m = MAX(L, R); LL l = L - 1, r = R + 1; for (int i = 1; i <= 30; i++) if (!(x[m] & (1 << (30 - i)))) l = max(l, (LL)pre[m][31 - i]), r = min(r, (LL)nxt[m][31 - i]); ans += (l - L + 1) * (R - m + 1) + (R - r + 1) * (m - L + 1) - (l - L + 1) * (R - r + 1); //计算答案*** solve(L, m - 1); solve(m + 1, R); } int main() { #ifndef ONLINE_JUDGE FIN #endif scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &x[i]); f[i][0] = i; zh(i, x[i]); } int last[35]; memset(last, 0, sizeof(last)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= 30; j++) { pre[i][j] = last[j]; if (a[i][j] == 1) last[j] = i; } } for (int i = 1; i <= 30; i++) { last[i] = n + 1; } for (int i = n; i; i--) { for (int j = 1; j <= 30; j++) { nxt[i][j] = last[j]; if (a[i][j] == 1) last[j] = i; } } for (int j = 1; j <= 30; j++) { for (int i = 1; i <= n; i++) if (i + (1 << j) - 1 > n) break; else { if (x[f[i][j - 1]] > x[f[i + (1 << (j - 1))][j - 1]]) { f[i][j] = f[i][j - 1]; } else { f[i][j] = f[i + (1 << (j - 1))][j - 1]; } } } ans = 0LL; solve(1, n); cout << ans << endl; return 0; }
姿势4：单调栈+倍增
跑两次单调栈求出每个数作为最大值的区间，也还是用拆位的思想，答案的求法和之前一样
代码：
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ ＞ ＜ ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! #include <set> #include <map> #include <deque> #include <queue> #include <Stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; typedef pair<LL, LL> pLL; typedef pair<LL, int> pLi; typedef pair<int, LL> pil;; typedef pair<int, int> pii; typedef unsigned long long uLL; #define ls rt<<1 #define rs rt<<1|1 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define bug printf("*********\n") #define FIN freopen("input.txt","r",stdin); #define FON freopen("output.txt","w+",stdout); #define IO ios::sync_with_stdio(false),cin.tie(0) #define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n" #define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n" #define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n" int read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const double eps = 1e-8; const int mod = 1e9 + 7; const int maxn = 1e6 + 5; const int INF = 0x3f3f3f3f; const LL INFLL = 0x3f3f3f3f3f3f3f3f; int Stack[maxn], a[maxn]; int L[maxn], R[maxn]; LL lmax[maxn][21], rmax[maxn][21]; int main() { #ifndef ONLINE_JUDGE FIN #endif int n = read(); for(int i = 1; i <= n; i++) { rmax[i][0] = lmax[i][0] = a[i] = read(); } for(int j = 1; j <= 18; j++) { for(int i = 1; i <= n; i++) { lmax[i][j] = lmax[i][j - 1] | lmax[i + (1 << (j - 1))][j - 1]; } for(int i = n; i >= 1; i--) { rmax[i][j] = rmax[i][j - 1]; if (i >= (1 << (j - 1))) { rmax[i][j] |= rmax[i - (1 << (j - 1))][j - 1]; } } } for (int i = 1, top = 0; i <= n; ++i) { while(top && a[Stack[top]] <= a[i]) { top--; } L[i] = Stack[top] + 1; Stack[++top] = i; } Stack[0] = n + 1; for ( int i = n, top = 0; i >= 1; --i) { while (top && a[Stack[top]] < a[i]) { top--; } R[i] = Stack[top] - 1; Stack[++top] = i; } LL ans = 0; for(int i = 1; i <= n; i++) { if (i - L[i] <= R[i] - i) { for (int j = L[i]; j <= i; ++j) { LL tmp = a[j]; int now = j; for(int k = 18; k >= 0; k--) { if ((now + (1 << k) <= R[i]) && (tmp | lmax[now + 1][k]) <= a[i]) { tmp |= lmax[now + 1][k]; now += (1 << k); } } if (now >= i && now <= R[i]) { ans += now - i + 1; } } } else { for ( int j = i; j <= R[i]; ++j) { LL tmp = a[j]; int now = j; for(int k = 18; k >= 0; k--) { if (now - (1 << k) >= L[i] && (tmp | rmax[now - 1][k]) <= a[i]) { tmp |= rmax[now - 1][k]; now -= (1 << k); } } if (now <= i && now >= L[i]) { ans += i - now + 1; } } } } printf("%lld\n", 1LL * n * (n + 1LL) / 2 - ans); return 0; }
1118：好数
题意：如果从一个数中删去所有的3,4,5,6,7,8后剩下的数按照与按顺序排列刚好等于2019，则称这个数为好数。找出1~n之间的好数的个数
题解：非常明显的数位dp，前导0用跑18次dfs处理掉。
代码:
#include<bits/stdc++.h> #define fuck(x) cout<<#x<<" = "<<x<<endl; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define ls rt<<1 #define rs rt<<1|1 typedef long long ll; typedef long long LL; const int maxn = 100086; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; using namespace std; int a[50]; ll dp[50][2][2][2][2]; ll dfs(int pos, int num2, int num0, int num1, int num9, bool limit) { if(pos == -1) { if(num2 && num0 && num1 && num9) { return 1; } else return 0; } if(!limit && dp[pos][num2][num0][num1][num9] != -1) { return dp[pos][num2][num0][num1][num9]; } ll ans = 0; int up = limit ? a[pos] : 9; for(int i = 0; i <= up; i++) { if(i == 3 || i == 4 || i == 5 || i == 6 || i == 7 || i == 8) { ans += dfs(pos - 1, num2, num0, num1, num9, limit && i == up); } else if(!num2 && i == 2) { ans += dfs(pos - 1, 1, num0, num1, num9, limit && i == up); } else if(num2 && !num0 && i == 0) { ans += dfs(pos - 1, num2, 1, num1, num9, limit && i == up); } else if(num2 && num0 && !num1 && i == 1) { ans += dfs(pos - 1, num2, num0, 1, num9, limit && i == up); } else if(num2 && num0 && num1 && !num9 && i == 9) { ans += dfs(pos - 1, num2, num0, num1, 1, limit && i == up); } } if(!limit ) { dp[pos][num2][num0][num1][num9] = ans; } return ans; } ll solve(ll x) { int pos = 0; while(x) { a[pos++] = x % 10; x /= 10; } return dfs(pos - 1, 0, 0, 0, 0, 1); } ll ans[50]; int main() { int T; memset(dp, -1, sizeof(dp)); scanf("%d", &T); ll t = 9; for(int i = 1; i <= 18; i++) { ans[i] = solve(t); t = t * 10 + 9; } while(T--) { ll x; scanf("%lld", &x); ll cnt = solve(x); int pos = 0; while(x) { pos++; x /= 10; } for(int i = 4; i < pos; i++) { cnt += ans[i]; } printf("%lld\n", cnt); } }
1119：搬砖
题意：从1出发走过指定numi个点后终点为t的最短路径
题解：看见n=18就是非常明显的状压了，比赛的时候把这题给忘写了，背锅++。
dp[sta][j]表示的是状态为sta时，终点为j时的最短路径，sta中二进制为1的数表示经过了第k个点，用floyd跑出dis数组，
dp[sta + (1 << j)][j] = min(dp[sta + (1 << j)][j], dp[sta][i] + dis[i + 1][j + 1]);
dp边界：dp[1][0]=0;
对于每次询问，将其二进制状态表示出来O（1）查询即可
代码：
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ ＞ ＜ ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! #include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; typedef pair<LL, LL> pLL; typedef pair<LL, int> pLi; typedef pair<int, LL> pil;; typedef pair<int, int> pii; typedef unsigned long long uLL; #define ls rt<<1 #define rs rt<<1|1 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define bug printf("*********\n") #define FIN freopen("input.txt","r",stdin); #define FON freopen("output.txt","w+",stdout); #define IO ios::sync_with_stdio(false),cin.tie(0) #define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n" #define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n" #define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n" LL read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const double eps = 1e-8; const int mod = 1e9 + 7; const int maxn = 20; const int INF = 0x3f3f3f3f; const LL INFLL = 0x3f3f3f3f3f3f3f3f; LL dis[maxn][maxn]; LL dp[1 << 19][19]; int main() { #ifndef ONLINE_JUDGE FIN #endif int n, m, k; memset(dis, 0x3f, sizeof(dis)); scanf("%d%d%d", &n, &m, &k); for(int i = 1; i <= n; i++) { dis[i][i] = 0; } LL w; for(int i = 1, u, v; i <= m; i++) { scanf("%d%d%lld", &u, &v, &w); dis[u][v] = dis[v][u] = min(dis[u][v], w); } for(int k = 1; k <= n; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); } } } int up = (1 << n); memset(dp, 0x3f, sizeof(dp)); dp[1][0] = 0; for(int sta = 1; sta < up; ++sta) { for(int i = 0; i < n; i++) { if((sta & (1 << i))) { for(int j = 0; j < n; ++j) { if((sta & (1 << j)) == 0 ) { if(i != j) { dp[sta + (1 << j)][j] = min(dp[sta + (1 << j)][j], dp[sta][i] + dis[i + 1][j + 1]); } } } } } } while(k--) { int t, num, x; scanf("%d%d", &t, &num); int sta = 1; sta |= (1 << (t - 1)); while(num--) { scanf("%d", &x); sta |= (1 << (x - 1)); } printf("%lld\n", dp[sta][t - 1]); } return 0; }
1120：买鞋
题意：有n份工作，每份工作的限制是，手上的钱小于p元，花费时间t，可以将手上的钱变为q元，问最少花费多少时间得到大于m的钱
建立模型，手上最初时有k元，为了得到m元，表示线段的起点为k，终点为m，花费的最小时间
每份工作表示，从点p到点q花费时间t，这样就变成了线段树的最小区间覆盖问题，
由于p和q比较大，我们放进vector里面离散化掉，用线段树维护区间【l，r】的最小值，从1—n扫一遍，每次更新离散后区间的最小值
答案就是查询区间离散化后m到N的最小值为多少，如果不能得到答案返回INF
代码：
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ ＞ ＜ ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! #include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; typedef pair<LL, LL> pLL; typedef pair<LL, int> pLi; typedef pair<int, LL> pil;; typedef pair<int, int> pii; typedef unsigned long long uLL; #define ls rt<<1 #define rs rt<<1|1 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define bug printf("*********\n") #define FIN freopen("input.txt","r",stdin); #define FON freopen("output.txt","w+",stdout); #define IO ios::sync_with_stdio(false),cin.tie(0) #define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n" #define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n" #define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n" LL read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const double eps = 1e-8; const int mod = 1e9 + 7; const int maxn = 1e7 + 5; const int INF = 0x3f3f3f3f; const LL INFLL = 0x3f3f3f3f3f3f3f3f; struct node { int p, q, t; node() {} node(int _p, int _q, int _t) { p = _p, q = _q, t = _t; } bool operator<(const node &A)const { return q < A.q; } } a[maxn]; vector<int> vec; LL Min[maxn << 2]; void push_up(int rt) { Min[rt] = min(Min[ls], Min[rs]); return; } void build(int l, int r, int rt) { Min[rt] = 1e18; if(l == r) return; int mid = (l + r) >> 1; build(lson); build(rson); push_up(rt); } void update(int pos, LL val, int l, int r, int rt) { // if(pos > r || pos < l) { // return; // } if(l == r) { Min[rt] = min(Min[rt], val); return; } int mid = (l + r) >> 1; if(pos <= mid) update(pos, val, lson); else update(pos, val, rson); push_up(rt); } LL query(int L, int R, int l, int r, int rt) { // if(L > r || R < l) return 1e18; if(L <= l && r <= R) { return Min[rt]; } int mid = (l + r) >> 1; LL ans = 1e18; if(L <= mid) ans = min(ans, query(L, R, lson)); if(R > mid) ans = min(ans, query(L, R, rson)); return ans; } int get_pos(int val) { return lower_bound(vec.begin(), vec.end(), val) - vec.begin() + 1; } int main() { #ifndef ONLINE_JUDGE FIN #endif int T; scanf("%d", &T); while(T--) { int n, k, m; vec.clear(); vec.clear(); scanf("%d%d%d", &n, &m, &k); vec.push_back(k); vec.push_back(m); for(int i = 1; i <= n; i++) { scanf("%d%d%d", &a[i].p, &a[i].q, &a[i].t); vec.push_back(a[i].p); vec.push_back(a[i].q); } sort(a + 1, a + n + 1); // for(int i = 1; i <= n; i++) { // debug3(a[i].p, a[i].q, a[i].t); // } sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); int sz = vec.size(); build(1, sz, 1); update(get_pos(k), 0, 1, sz, 1); for(int i = 1; i <= n; i++) { int l = get_pos(a[i].p); int r = get_pos(a[i].q); // debug2(l, r); LL val = query(l, r, 1, sz, 1) + a[i].t; // debug1(val); update(r, val, 1, sz, 1); } LL ans = query(get_pos(m), sz, 1, sz, 1); if(ans != 1e18) { printf("%lld\n", ans); } else { printf("impossible\n"); } } return 0; }
1121：抽抽抽
题意：n个数里是否有四个数可以凑出4的倍数
题解：直接模拟即可
代码：
#include<bits/stdc++.h> #define fuck(x) cout<<#x<<" = "<<x<<endl; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define ls rt<<1 #define rs rt<<1|1 typedef long long ll; typedef long long LL; const int maxn = 100086; const int inf = 0x3f3f3f3f; const int mod = 1e9+7; using namespace std; void view(int x){ if(x==0){return;} view(x/2); cout<<(x&1); } int vis[10]; int main(){ int T; scanf("%d",&T); while(T--){ memset(vis,0,sizeof(vis)); int n; scanf("%d",&n); for(int i=1;i<=n;i++){ int x; scanf("%d",&x); vis[x%4]++; } bool flag=false; if(vis[2]>=4||vis[0]>=4||vis[1]>=4||vis[3]>=4){flag=true;} int ans=0; ans=vis[0]/2; ans+=vis[2]/2; ans+=min(vis[1],vis[3]); if(ans>=2){flag=true;} if(vis[1]>=2&&vis[2]&&vis[0]){flag=true;} if(vis[3]>=2&&vis[2]&&vis[0]){flag=true;} if(flag){printf("YES\n"); } else printf("NO\n"); } return 0; }
1122：进贡
题意：对于一个数n，能否用最多k个数，使得，用了num个数，这num个数的最大的约数和最小
题解：如果这个数是质数，其最大的约数是1，所以我们要尽可能分解质数
如果这个数是质数，答案为1
如果这个数不是质数，如果k==1，我们就只能暴力找这个数的最大约数
如果k>=2,对于偶数，他可以分解为2个质数的和，答案为2，对于奇数，我们将其分解为一个最大的质数和一个偶数，这个偶数的最大约数就是这个偶数/2
如果k>=3，如果是奇数，可以分解为一个3，和两个质数，如果是偶数，分解为两个质数，答案为2
代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int prime[maxn]; int v[maxn]; int m; bool is_prime(int n) { for(int i = 2; i * i <= n; i++) { if(n % i == 0) return false; } return true; } int solve(int n) { int maxx = 0; for(int i = 2; i * i <= n; i++) { if(n % i == 0) { maxx = max(i, maxx); maxx = max(n / i, maxx); return maxx; } } return 1; } int main() { int T; scanf("%d", &T); while(T--) { int n, k; scanf("%d%d", &n, &k); if(is_prime(n)) { printf("1\n"); } else { int maxx = 0; if(k == 1) { for(int i = 2; i * i <= n; i++) { if(n % i == 0) { maxx = max(i, maxx); maxx = max(n / i, maxx); break; } } } if(k >= 2) { if(n % 2) { int num = n; for(int i = n - 2; i >= 0; i--) { if(is_prime(i)) { num = n - i; break; } } maxx += num / 2; maxx++; } else { maxx = 2; } } if(k >= 3) { if(n % 2) { maxx = min(maxx, 3); } else { maxx = 2; } } printf("%d\n", maxx); } } return 0; }