这场比赛演的逼真，感谢队友不杀之恩
总结：卡题了赶紧换，手上捏着的题尽快上机解决
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 = ;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + ;
using namespace std;
map<int, bool>mp[];
set<int>st;
int a[maxn];
int main() { int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
} for(int i = n; i >= ; i--) {
mp[i] = mp[i + ];
mp[i][a[i]] = true;
} int ans = ;
for(int k = ; k <= n; k++) {
for(int l = k - ; l >= ; l--) {
if(mp[k + ][a[k] - a[l]]) {
ans++;
break;
}
}
}
printf("%d\n", ans); return ;
}
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 = ;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + ;
using namespace std;
int a[maxn];
int sum[maxn << ];
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) >> ;
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) >> ;
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) >> ;
int ans = ;
if(L <= mid) ans ^= query(L, R, lson);
if(R > mid) ans ^= query(L, R, rson);
return ans;
} set<int> st[];
map<int, int>mp;
int main() {
int n, q;
scanf("%d%d", &n, &q);
int tot = ;
for(int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
if(!mp[a[i]]) {
mp[a[i]] = ++tot;
}
st[mp[a[i]]].insert(i);
}
build(, n, );
while(q--) {
int op;
scanf("%d", &op);
if(op == ) {
int pos, val;
scanf("%d%d", &pos, &val);
int t = query(pos, pos, , n, );
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, , n, );
} else {
int l, r;
scanf("%d%d", &l, &r);
int x = query(l, r, , n, );
if(!mp[x]) {
mp[x] = ++tot;
printf("%d\n", r - l + );
} else {
x = mp[x];
int ans = ;
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 + - 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 = ;
const int inf = 2.1e9;
const ll Inf = ;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-); int p1[maxn], p2[maxn];
int h[maxn][maxn];
char a[maxn][maxn];//字符矩阵
ull seed1 = , seed2 = ; //随机种子
void init() { //放在多组外面
p1[] = p2[] = ;
for (int i = ; i <= ; i++) {
p1[i] = p1[i - ] * seed1 ;
p2[i] = p2[i - ] * seed2 ;
}
}
void get_h(int n, int m) {//得到n,m区间内的h值
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
h[i][j] = (h[i][j - ] * seed1 + a[i][j] - 'a' + ) ;
}
}
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
h[i][j] = (h[i - ][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 = ;
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 != -) {
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 = ;
while (scanf("%d%d%d%d%d", &n, &m, &t, &x, &y) != EOF) {
for(int i = ; i <= n; i++) {
scanf("%s", a[i] + );
}
memset(Head, -, sizeof(Head));
tot = ;
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 = ;
while(t--) {
for(int i = ; i <= x; i++) {
scanf("%s", a[i] + );
}
get_h(x, y);
if(hash_map(get_hash(x, y, x, y), false)) {
ans++;
}
}
printf("Case %d: %d\n", ++cases, ans);
}
return ;
}
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 = , f = ; char ch = getchar();
while(ch < '' || ch > '') {
if(ch == '-')f = -;
ch = getchar();
}
while(ch >= '' && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x * f;
}
const double eps = 1e-;
const int mod = 1e9 + ;
const int maxn = 3e5 + ;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f;
int a[maxn];
int l[maxn][], r[maxn][];
unordered_map<int, int> vis,vis1;
int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
} for(int i = ; i <= n; i++) {
for(int j = ; j < ; j++) {
if(a[i] >> j & )l[i][j] = i;
else l[i][j] = l[i - ][j];
}
} for(int i = ; i < ; i++) {
r[n + ][i] = n + ;
}
for(int i = n; i >= ; i--) {
for(int j = ; j < ; j++) {
if(a[i] >> j & ) {
r[i][j] = i;
} else {
r[i][j] = r[i + ][j];
}
}
}
LL ans = ;
for(int i = ; i <= n; i++) {
int L = , R = n + ;
for(int j = ; j < ; j++) {
if((a[i] >> j & )) 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 + ) / - ans);
return ;
}
姿势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 = , f = ; char ch = getchar();
while(ch < '' || ch > '') {
if(ch == '-')f = -;
ch = getchar();
}
while(ch >= '' && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x * f;
}
const double eps = 1e-;
const int mod = 1e9 + ;
const int maxn = 3e5 + ;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f; int n;
int a[maxn];
pii MAX[maxn << ];
void push_up(int rt) {
if (MAX[rt << ].first > MAX[rt << | ].first)
MAX[rt] = MAX[rt << ];
else
MAX[rt] = MAX[rt << | ];
}
void build(int l, int r, int rt) {
if (l == r) {
MAX[rt] = make_pair(a[l], l);
return;
}
int mid = (l + r) >> ;
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) >> ;
pii res = make_pair(, );
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 ;
pii cnt = query(L, R, , n, );
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 = ;
if ((a[id] | a[l]) > a[id]) res += LL(l - L + ) * (R - id + );
if ((a[id] | a[r]) > a[id]) res += LL(R - r + ) * (id - L + );
if ((a[id] | a[l]) > a[id] && (a[id] | a[r]) > a[id]) res -= LL(l - L + ) * (R - r + );
res += solve(L, id - ) + solve(id + , R);
return res;
} int main() {
#ifndef ONLINE_JUDGE
FIN;
#endif
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
build(, n, );
printf("%lld\n", solve(, n));
return ;
}
姿势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 = , f = ; char ch = getchar();
while(ch < '' || ch > '') {
if(ch == '-')f = -;
ch = getchar();
}
while(ch >= '' && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x * f;
}
const double eps = 1e-;
const int mod = 1e9 + ;
const int maxn = 3e5 + ;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f; LL ans;
int n, f[][], a[][];
int x[], pre[][], nxt[][];
void zh(int i, int x) {
int len = ;
while (x) {
a[i][++len] = x & ;
x >>= ;
}
while (len < ) a[i][++len] = ;
}
int MAX(int L, int R) {
int k = (double)log(R - L + ) / (double)log();
if (x[f[L][k]] > x[f[R - ( << k) + ][k]]) return f[L][k];
else return f[R - ( << k) + ][k];
}
void solve(LL L, LL R) {
if (L > R) return;
int m = MAX(L, R);
LL l = L - , r = R + ;
for (int i = ; i <= ; i++)
if (!(x[m] & ( << ( - i))))
l = max(l, (LL)pre[m][ - i]), r = min(r, (LL)nxt[m][ - i]);
ans += (l - L + ) * (R - m + ) + (R - r + ) * (m - L + ) - (l - L + ) * (R - r + ); //计算答案***
solve(L, m - );
solve(m + , R);
}
int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%d", &x[i]);
f[i][] = i;
zh(i, x[i]);
}
int last[];
memset(last, , sizeof(last));
for (int i = ; i <= n; i++) {
for (int j = ; j <= ; j++) {
pre[i][j] = last[j];
if (a[i][j] == ) last[j] = i;
}
}
for (int i = ; i <= ; i++) {
last[i] = n + ;
}
for (int i = n; i; i--) {
for (int j = ; j <= ; j++) {
nxt[i][j] = last[j];
if (a[i][j] == ) last[j] = i;
}
}
for (int j = ; j <= ; j++) {
for (int i = ; i <= n; i++)
if (i + ( << j) - > n) break;
else {
if (x[f[i][j - ]] > x[f[i + ( << (j - ))][j - ]]) {
f[i][j] = f[i][j - ];
} else {
f[i][j] = f[i + ( << (j - ))][j - ];
}
}
}
ans = 0LL;
solve(, n);
cout << ans << endl;
return ;
}
姿势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 = , f = ; char ch = getchar();
while(ch < '' || ch > '') {
if(ch == '-')f = -;
ch = getchar();
}
while(ch >= '' && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x * f;
}
const double eps = 1e-;
const int mod = 1e9 + ;
const int maxn = 1e6 + ;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f; int Stack[maxn], a[maxn];
int L[maxn], R[maxn];
LL lmax[maxn][], rmax[maxn][]; int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
int n = read();
for(int i = ; i <= n; i++) {
rmax[i][] = lmax[i][] = a[i] = read();
}
for(int j = ; j <= ; j++) {
for(int i = ; i <= n; i++) {
lmax[i][j] = lmax[i][j - ] | lmax[i + ( << (j - ))][j - ];
}
for(int i = n; i >= ; i--) {
rmax[i][j] = rmax[i][j - ];
if (i >= ( << (j - ))) {
rmax[i][j] |= rmax[i - ( << (j - ))][j - ];
}
}
}
for (int i = , top = ; i <= n; ++i) {
while(top && a[Stack[top]] <= a[i]) {
top--;
}
L[i] = Stack[top] + ;
Stack[++top] = i;
}
Stack[] = n + ;
for ( int i = n, top = ; i >= ; --i) {
while (top && a[Stack[top]] < a[i]) {
top--;
}
R[i] = Stack[top] - ;
Stack[++top] = i;
}
LL ans = ;
for(int i = ; 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 = ; k >= ; k--) {
if ((now + ( << k) <= R[i]) && (tmp | lmax[now + ][k]) <= a[i]) {
tmp |= lmax[now + ][k];
now += ( << k);
}
}
if (now >= i && now <= R[i]) {
ans += now - i + ;
}
}
} else {
for ( int j = i; j <= R[i]; ++j) {
LL tmp = a[j]; int now = j;
for(int k = ; k >= ; k--) {
if (now - ( << k) >= L[i] && (tmp | rmax[now - ][k]) <= a[i]) {
tmp |= rmax[now - ][k];
now -= ( << k);
}
}
if (now <= i && now >= L[i]) {
ans += i - now + ;
}
}
}
}
printf("%lld\n", 1LL * n * (n + 1LL) / - ans);
return ;
}
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 = ;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + ;
using namespace std;
int a[];
ll dp[][][][][];
ll dfs(int pos, int num2, int num0, int num1, int num9, bool limit) {
if(pos == -) {
if(num2 && num0 && num1 && num9) {
return ;
} else
return ;
}
if(!limit && dp[pos][num2][num0][num1][num9] != -) {
return dp[pos][num2][num0][num1][num9];
}
ll ans = ;
int up = limit ? a[pos] : ;
for(int i = ; i <= up; i++) {
if(i == || i == || i == || i == || i == || i == ) {
ans += dfs(pos - , num2, num0, num1, num9, limit && i == up);
} else if(!num2 && i == ) {
ans += dfs(pos - , , num0, num1, num9, limit && i == up);
} else if(num2 && !num0 && i == ) {
ans += dfs(pos - , num2, , num1, num9, limit && i == up);
} else if(num2 && num0 && !num1 && i == ) {
ans += dfs(pos - , num2, num0, , num9, limit && i == up);
} else if(num2 && num0 && num1 && !num9 && i == ) {
ans += dfs(pos - , num2, num0, num1, , limit && i == up);
}
}
if(!limit ) {
dp[pos][num2][num0][num1][num9] = ans;
}
return ans;
} ll solve(ll x) {
int pos = ;
while(x) {
a[pos++] = x % ;
x /= ;
}
return dfs(pos - , , , , , );
}
ll ans[];
int main() {
int T;
memset(dp, -, sizeof(dp));
scanf("%d", &T);
ll t = ;
for(int i = ; i <= ; i++) {
ans[i] = solve(t);
t = t * + ;
}
while(T--) {
ll x;
scanf("%lld", &x);
ll cnt = solve(x);
int pos = ;
while(x) {
pos++;
x /= ;
}
for(int i = ; 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 = , f = ; char ch = getchar();
while(ch < '' || ch > '') {
if(ch == '-')f = -;
ch = getchar();
}
while(ch >= '' && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x * f;
}
const double eps = 1e-;
const int mod = 1e9 + ;
const int maxn = ;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f;
LL dis[maxn][maxn];
LL dp[ << ][];
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 = ; i <= n; i++) {
dis[i][i] = ;
}
LL w;
for(int i = , 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 = ; k <= n; k++) {
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
int up = ( << n);
memset(dp, 0x3f, sizeof(dp));
dp[][] = ;
for(int sta = ; sta < up; ++sta) {
for(int i = ; i < n; i++) {
if((sta & ( << i))) {
for(int j = ; j < n; ++j) {
if((sta & ( << j)) == ) {
if(i != j) {
dp[sta + ( << j)][j] = min(dp[sta + ( << j)][j], dp[sta][i] + dis[i + ][j + ]);
}
}
}
}
}
}
while(k--) {
int t, num, x;
scanf("%d%d", &t, &num);
int sta = ;
sta |= ( << (t - ));
while(num--) {
scanf("%d", &x);
sta |= ( << (x - ));
}
printf("%lld\n", dp[sta][t - ]);
}
return ;
}
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 = , f = ; char ch = getchar();
while(ch < '' || ch > '') {
if(ch == '-')f = -;
ch = getchar();
}
while(ch >= '' && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x * f;
}
const double eps = 1e-;
const int mod = 1e9 + ;
const int maxn = 1e7 + ;
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 << ];
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) >> ;
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) >> ;
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) >> ;
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() + ;
}
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 = ; 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 + , a + n + ); // 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(, sz, );
update(get_pos(k), , , sz, );
for(int i = ; 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, , sz, ) + a[i].t;
// debug1(val);
update(r, val, , sz, );
}
LL ans = query(get_pos(m), sz, , sz, );
if(ans != 1e18) {
printf("%lld\n", ans);
} else {
printf("impossible\n");
}
}
return ;
}
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 = ;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+;
using namespace std; void view(int x){
if(x==){return;}
view(x/);
cout<<(x&);
} int vis[]; int main(){ int T;
scanf("%d",&T);
while(T--){
memset(vis,,sizeof(vis));
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
int x;
scanf("%d",&x);
vis[x%]++;
}
bool flag=false;
if(vis[]>=||vis[]>=||vis[]>=||vis[]>=){flag=true;}
int ans=;
ans=vis[]/;
ans+=vis[]/;
ans+=min(vis[],vis[]);
if(ans>=){flag=true;}
if(vis[]>=&&vis[]&&vis[]){flag=true;}
if(vis[]>=&&vis[]&&vis[]){flag=true;}
if(flag){printf("YES\n"); }
else printf("NO\n"); }
return ;
}
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 + ;
int prime[maxn];
int v[maxn];
int m; bool is_prime(int n) {
for(int i = ; i * i <= n; i++) {
if(n % i == )
return false;
}
return true;
}
int solve(int n) {
int maxx = ;
for(int i = ; i * i <= n; i++) {
if(n % i == ) {
maxx = max(i, maxx);
maxx = max(n / i, maxx);
return maxx;
}
}
return ;
} 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 = ;
if(k == ) {
for(int i = ; i * i <= n; i++) {
if(n % i == ) {
maxx = max(i, maxx);
maxx = max(n / i, maxx);
break;
}
}
}
if(k >= ) {
if(n % ) {
int num = n;
for(int i = n - ; i >= ; i--) {
if(is_prime(i)) {
num = n - i;
break;
}
}
maxx += num / ;
maxx++; } else {
maxx = ;
}
}
if(k >= ) {
if(n % ) {
maxx = min(maxx, );
} else {
maxx = ;
}
}
printf("%d\n", maxx);
}
}
return ;
}