按点赞数降序
297 二分
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e5 + ;
int a[N], c, n;
bool check(int d) {
int pre = a[], cnt = ;
for(int i = ; i <= n; i++) {
if((a[i] - pre) >= d) {
pre = a[i];
cnt++;
}
}
return cnt >= c;
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &c);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
sort(a+, a++n);
int l = , r = 1e9+, m = (l+r) >> ;
while(l < r) {
if(check(m)) l = m;
else r = m - ;
m = (l+r+) >> ;
//cout << l <<" " << r << endl;
}
printf("%d\n", m);
}
return ;
}
2 区间素数筛
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e5 + ;
bool notp_big[N], notp_small[N];
void prime(LL a, LL b) {
mem(notp_big, false);
if(a==) notp_big[] = true;
for (LL i = ; i*i <= b; i++) {
if(!notp_small[i]) {
for (LL j = i+i; j*j <= b; j += i) notp_small[j] = true;
for (LL j = max(2LL, (a+i-)/i)*i; j <= b; j += i)notp_big[j-a] = true;
}
}
}
int main() {
int T, n, m;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
prime(n, m);
for (int i = n; i <= m; i++) if(!notp_big[i-n])printf("%d\n", i);
}
return ;
}
346 dp 小于5e6预处理，大于5e6递归
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 5e6+;
int dp[N];
map<int, LL>mp;
LL f(int n) {
if(n <= 5e6) return dp[n];
else if(mp[n] != ) return mp[n];
return max((LL)n, f(n/)+f(n/)+f(n/));
}
int main() {
int n;
dp[]=;
dp[]=;
for (int i = ; i < N; i++) {
dp[i] = max(i, dp[i/]+dp[i/]+dp[i/]);
}
while(~ scanf("%d", &n)) {
mp.clear();
printf("%lld\n", f(n));
}
return ;
}
394 dp 注意0的情况
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = ;
char s[N];
LL dp[N];
int main() {
while(~scanf("%s", s+)) {
//printf("%s\n", s+1);
if(s[] == '')break;
dp[] = dp[] = ;
int n = strlen(s+);
for (int i = ; i <= n; i++) {
if(s[i-] != '') {
int t = (s[i-]-'')* + s[i]-'';
//cout << t << endl;
if(t <= ) {
if(s[i] != '')dp[i] = dp[i-] + dp[i-];
else dp[i] = dp[i-];
}
else dp[i] = dp[i-];
}
else dp[i] = dp[i-];
}
printf("%lld\n", dp[n]);
}
return ;
}
1043 线段数区间合并，lv记录这段区间以左端点为起点的最大和，rv同理
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 5e4 + ;
const int INF = 0x7f7f7f7f;
struct Tree {
int sum, lv, rv, ans;
}tree[N<<];
void push_up(int rt) {
tree[rt].sum = tree[rt<<].sum + tree[rt<<|].sum;
tree[rt].lv = max(tree[rt<<].lv, tree[rt<<].sum + tree[rt<<|].lv);
tree[rt].rv = max(tree[rt<<|].rv, tree[rt<<|].sum + tree[rt<<].rv);
tree[rt].ans = max(tree[rt<<].rv + tree[rt<<|].lv, max(tree[rt<<].ans, tree[rt<<|].ans));
}
void build(int rt, int l, int r) {
if(l == r) {
scanf("%d", &tree[rt].ans);
tree[rt].lv = tree[rt].rv = tree[rt].sum = tree[rt].ans;
return ;
}
int m = (l+r) >> ;
build(ls);
build(rs);
push_up(rt);
}
Tree query(int L, int R, int rt, int l, int r) {
if(L <= l && r <= R) return tree[rt];
int m = (l + r) >> ;
if(R <= m) return query(L, R, ls);
else if(L > m) return query(L, R, rs);
Tree lft = query(L, R, ls);
Tree rit = query(L, R, rs);
int sum = lft.sum+rit.sum;
int lv = max(lft.lv, lft.sum+rit.lv);
int rv = max(rit.rv, rit.sum+lft.rv);
int ans = max(lft.rv+rit.lv, max(lft.ans, rit.ans));
return Tree{sum, lv, rv, ans};
}
int main() {
int n, m, x, y;
scanf("%d", &n);
build(, , n);
scanf("%d", &m);
while(m --) {
scanf("%d%d", &x, &y);
Tree res = query(x, y, , , n);
printf("%d\n", res.ans);
}
return ;
}
6256 普通的逆序数，不过我使用了最近学的方法，从大到小加入位置，跑的比较优秀
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 2e5 + ;
pii a[N];
int bit[N], n;
void add(int x, int a) {
while(x <= n) bit[x] += a, x += x&-x;
}
int query(int x) {
int ans = ;
while(x) ans += bit[x], x -= x&-x;
return ans;
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%d", &a[i].fi);
a[i].se = i;
}
sort(a+, a++n);
mem(bit, );
LL ans = ;
for(int i = n; i >= ; i--) {
ans += query(a[i].se);
//cout <<".............."<< ans << endl;
add(a[i].se, );
}
printf("%lld\n", ans);
}
return ;
}
5 纯暴力，从中间加
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e6 + ;
char s[N];
int num[N], t[N], n;
bool cmp() {
for(int i = ;i <= n; i++) {
if(t[i] < num[i]) return true;
else if(t[i] > num[i]) return false;
}
return true;
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%s", s+);
n = strlen(s+);
for (int i = ; i <= n; i++) num[i] = s[i] - '';
for (int i = ; i <= (n+)/; i++) {
t[i] = t[n-i+] = num[i];
}
if(n==) {
if(num[] == ) printf("11\n");
else printf("%d\n", num[]+);
continue;
}
while(cmp()) {
t[(n+)/]++;
for (int i = (n+)/; i >= ; i--) {
t[i-] += t[i]/;
t[i] %= ;
}
for (int i = ; i <= (n+)/; i++) {
t[n-i+] = t[i];
}
}
for (int i = ; i < n; i++) printf("%d", t[i]);
if(t[n] == ) printf("1\n");//样例999
else printf("%d\n", t[n]);
}
return ;
}
8002 树状数组区间更新，区间查询
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e5 + ;
int a[N], n;
LL sum[N], c1[N], c2[N];
void add(int x, int a) {
LL t = x;
while(x <= n) c1[x] += a, c2[x] += t*a, x += x&-x;
}
LL query(int x) {
LL ans = ;
LL t = x;
while(x) ans += (t+) * c1[x] - c2[x], x -= x&-x;
return ans;
}
int main() {
int T, op, c, p, q, v;
scanf("%d", &T);
while(T--) {
mem(c1, );
mem(c2, );
scanf("%d%d", &n, &c);
while(c--) {
scanf("%d", &op);
if(op == ) {
scanf("%d%d", &p, &q);
printf("%lld\n", query(q) - query(p-));
}
else {
scanf("%d%d%d", &p, &q, &v);
add(p, v);
add(q+, -v);
}
}
}
return ;
}
3267 离线+树状数组，每次保证这段区间每个数只更新一次，或者主席树(不会，等我学了在a)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 3e5 + , M = 2e5 + ;
int a[N], nxt[N], bit[N], mp[M*], n;
struct node {
int l, r, id;
bool operator < (const node & t) const {
if(l == t.l) return r < t.r;
else return l < t.l;
}
}Q[M];
int ans[N];
void add(int x, int a) {
while(x <= n) bit[x] += a, x += x&-x;
}
int query(int x) {
int ans = ;
while(x) ans += bit[x], x -= x&-x;
return ans;
}
int main() {
int q;
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
for (int i = ; i <= n; i++) {
if(mp[a[i]] == ) {
add(i, );
mp[a[i]] = i;
}
}
mem(mp, );
for (int i = n; i; i--) {
if(mp[a[i]] == ) {
nxt[i] = n+;
mp[a[i]] = i;
}
else {
nxt[i] = mp[a[i]];
mp[a[i]] = i;
}
}
scanf("%d", &q);
for (int i = ; i < q; i++) scanf("%d%d", &Q[i].l, &Q[i].r), Q[i].id = i;
sort(Q, Q+q);
int t = ;
for (int i = ; i < q; i++) {
while(t <= n && t < Q[i].l) add(nxt[t++], );
ans[Q[i].id] = query(Q[i].r) - query(Q[i].l-);
}
for (int i = ; i < q; i++) printf("%d\n", ans[i]);
return ;
}
主席树（2019.3更新），感觉这个没有离线优秀，不过思想还行，就当练练可持久化
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<iostream>
#include<cstdio>
#include<vector>
#include<climits>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 3e4 + , M = 1e6 + ;
int root[N], lson[M], rson[M], tree[M], tot = ;
void build(int &x, int l, int r) {
x = ++tot;
if(l == r) return ;
int m = l+r >> ;
build(lson[x], l, m);
build(rson[x], m+, r);
tree[x] = tree[lson[x]] + tree[rson[x]];
}
void update(int old, int &x, int p, int v, int l, int r) {
x = ++tot;
lson[x] = lson[old], rson[x] = rson[old], tree[x] = tree[old] + v;
if(l == r) return ;
int m = l+r >> ;
if(p <= m) update(lson[x], lson[x], p, v, l, m);
else update(rson[x], rson[x], p, v, m+, r);
}
int query(int L, int R, int x, int l, int r) {
if(L <= l && r <= R) return tree[x];
int m = l+r >> , ans = ;
if(L <= m) ans += query(L, R, lson[x], l, m);
if(R > m ) ans += query(L, R, rson[x], m+, r);
return ans;
}
int n, a, mp[M], tmp, q, l, r;
int main() {
scanf("%d", &n);
build(root[], , n);
for (int i = ; i <= n; ++i) {
scanf("%d", &a);
if(mp[a]) {
update(root[i-], tmp, mp[a], -, , n);
update(tmp, root[i], i, , , n);
}
else update(root[i-], root[i], i, , , n);
mp[a] = i;
}
scanf("%d", &q);
while(q--) {
scanf("%d %d", &l, &r);
printf("%d\n", query(l, r, root[r], , n));
}
return ;
}
1437 树的直径，两遍dfs
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e4 + ;
vector<int>g[N];
int mx = , ed = ;
void dfs(int o, int u, int st) {
if(st > mx) {
mx = st;
ed = u;
}
for (int i = ; i < g[u].size(); i++) {
if(g[u][i] != o) {
dfs(u, g[u][i], st+);
}
}
}
int main() {
int n, u, v;
scanf("%d", &n);
for (int i = ; i < n-; i++) {
scanf("%d%d", &u, &v);
g[u].pb(v);
g[v].pb(u);
}
dfs(, , );
dfs(, ed, );
printf("%d\n", mx);
return ;
}
1436 dfs
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e4 + ;
vector<int>g[N];
bool vis[N];
bool f = true;
void dfs(int o, int u) {
vis[u] = true;
for (int i = ; i < g[u].size(); i++) {
if(g[u][i] != o) {
if(!vis[g[u][i]])dfs(u, g[u][i]);
else f = false;
}
}
}
int main() {
int n, m, u, v;
scanf("%d%d", &n, &m);
for (int i = ; i < m; i++) {
scanf("%d%d", &u, &v);
g[u].pb(v);
g[v].pb(u);
}
dfs(, );
for (int i = ; i <= n; i++) if(!vis[i]) f = false;
if(f) puts("YES");
else puts("NO");
return ;
}
6219 普通dp, 与LCS相似
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 2e3 + ;
char s[N], t[N];
int dp[N][N];
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%s", s+);
scanf("%s", t+);
int n = strlen(s+), m = strlen(t+);
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
if(i||j){
if(i == ) dp[i][j] = j;
else if(j == ) dp[i][j] = i;
else if(s[i] == t[j]) dp[i][j] = dp[i-][j-];
else dp[i][j] = min(dp[i-][j-]+, min(dp[i-][j]+, dp[i][j-]+));
}
}
}
printf("%d\n", dp[n][m]);
}
return ;
}
3923 普通dp
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = ;
int a[N][N], dp[N][N];
int main() {
int T, n, m;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
scanf("%d", &a[i][j]);
}
}
mem(dp, );
for (int i = ; i <= m; i++) dp[][i] = a[][i];
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
dp[i][j] = max(dp[i-][j], max(dp[i-][j-], dp[i-][j+])) + a[i][j];
}
}
int ans = ;
for (int i = ; i <= m; i++) ans = max(ans, dp[n][i]);
printf("%d\n", ans);
}
return ;
}
95 栈模拟
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head stack<int>s;
int main() {
int n, t;
while(~scanf("%d", &n) && n) {
while(!s.empty()) s.pop();
int now = ;
for (int i = ; i <= n; i++) {
scanf("%d", &t);
if(t == now) now++;
else {
s.push(t);
}
while(!s.empty() && s.top() == now) {
s.pop();
now++;
}
}
//cout << now << endl;
if(now == n+) puts("yes");
else puts("no");
}
return ;
}
1021 原串与反串的LCS就是原串的最长回文子序列
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 6e3 + ;
char s[N], t[N];
int dp[N][N];
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%s", s+);
int n = strlen(s+);
for (int i = ; i <= n; i++) t[i] = s[n-i+];
for (int i = ; i <= n; i++) {
for (int j = ; j <= n; j++) {
if(s[i] == t[j]) dp[i][j] = max(dp[i-][j-]+, max(dp[i-][j], dp[i][j-]));
else dp[i][j] = max(dp[i-][j], dp[i][j-]);
}
}
printf("%d\n", n-dp[n][n]);
}
return ;
}
14930 记忆化搜索
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e4 + ;
LL dp[N][];
int a[N], n;
LL dfs(int pos, int sta) {
if(pos == n) {
if(sta == ) return ;
else return a[n];
}
if(~dp[pos][sta]) return dp[pos][sta];
if(sta == ) return dp[pos][sta] = a[pos] + dfs(pos+, );
else return dp[pos][sta] = max(dfs(pos+, ), dfs(pos+, ));
}
int main() {
int T;
scanf("%d", &T);
for (int cs = ; cs <= T; cs++) {
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
mem(dp, -);
LL ans = max(dfs(, ), dfs(, ));
printf("Case %d: %lld\n", cs, ans);
}
return ;
}
1841 bfs
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e4 + ;
bool notp[N];
bool vis[N];
int d[], dd[];
int p[] = {, , , , };
int a, b, ans;
bool bfs() {
mem(vis, false);
queue<pii>q;
q.push(mp(a, ));
vis[a] = true;
while(!q.empty()) {
pii p = q.front();
q.pop();
int t = p.fi;
if(t == b) {
ans = p.se;
return true;
}
for (int i = ; i <= ; i++) {
d[i] = t%;
t /= ;
}
for (int i = ; i <= ; i++) {
int t = ;
if(i == ) t = ;
for (int j = t; j < ; j++) {
if(j == d[i]) continue;
for (int k = ; k <= ; k++) {
if(k == i) continue;
dd[k] = d[k];
}
dd[i] = j;
int n = ;
for (int k = ; k >=; k--) n = n * + dd[k];
if(!notp[n] && !vis[n]) {
vis[n] = true;
q.push(mp(n, p.se+));
}
}
}
}
return false;
}
int main() {
int T;
scanf("%d", &T);
for (int i = ; i < N; i++) {
if(!notp[i]) {
for (int j = i+i; j < N ;j += i) notp[j] = true;
}
}
for (int cs = ; cs <= T; cs++) {
scanf("%d%d", &a, &b);
if(bfs())printf("%d\n", ans);
else printf("Impossible\n");
}
return ;
}
97 背包dp
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = ;
int dp[N], c[N], v[N];
int main() {
int n, m;
while(~scanf("%d%d", &n, &m)) {
if(!n && !m) return ;
int ans;
mem(dp, );
for (int i = ; i <= m; i++) scanf("%d%d", &c[i], &v[i]);
for (int i = ; i <= m; i++) {
for (int j = n; j >= c[i]; j--) {
dp[j] = max(dp[j-c[i]]+v[i], dp[j]);
}
}
for (int i = n; i >= ; i--) if(dp[i] == dp[n]) ans = i;
printf("%d %d\n", ans, dp[n]);
}
return ;
}
740 区间dp， 小区间推大区间，dp[i][j] = max(dp[i+1][j] + (n+i-j) * a[i], dp[i][j-1] + (n+i-j) * a[j])
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 2e3 + ;
int dp[N][N], a[N];
int main() {
int n;
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
for (int i = n; i >=; i--) {
dp[i][i] = a[i] * n;
for (int j = i+; j <= n; j++) {
dp[i][j] = max(dp[i+][j] + (n+i-j) * a[i], dp[i][j-] + (n+i-j) * a[j]);
}
}
printf("%d\n", dp[][n]);
return ;
}
206 每次向外扩展一次，做多扩展max(n,m)次，所以复杂度为max(n,m)*n*m
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = ;
const int INF = 0x3f3f3f3f;
char s[N][N];
int ans[N][N];
int dir[][] = {, , , , , -, -, };
int main() {
int T, n, m;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
mem(ans, INF);
for (int i = ; i <= n; i++) scanf("%s", s[i]+);
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
if(s[i][j] == '') ans[i][j] = ;
}
}
for (int i = ; i <= max(n, m); i++) {
for (int j = ; j <= n; j++) {
for (int k = ; k <= m; k++) {
if(ans[j][k] != INF)
for (int l = ; l < ; l++) {
int x = j + dir[l][];
int y = k + dir[l][];
if( <= x && x <= n && <= y && y <= m) {
ans[x][y] = min(ans[x][y], ans[j][k] + );
}
}
}
}
}
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
printf("%d%c", ans[i][j], " \n"[j==m]);
}
}
}
return ;
}
9861 双指针
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 3e5 + ;
int a[N];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) {
scanf("%d", &a[i]);
}
int ans = ;
int l = , r = , sum = ;
while(true) {
while(sum <= m && r < n) {
ans = max(ans, sum);
sum += a[++r];
}
if(sum <= m) ans = max(ans, sum);
while(sum > m) {
sum -= a[++l];
}
if(sum <= m) ans = max(ans, sum);
if(r == n) break;
}
printf("%d\n", ans);
return ;
}
3377 带权并查集或普通并查集
带权
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 2e3 + ;
int fa[N], rnk[N];
void init(int n) {
for (int i = ; i <= n; i++) {
fa[i] = i;
rnk[i] = ;
}
}
int find(int x) {
if(fa[x] == x) return x;
else{
int tmp = fa[x];
fa[x] = find(fa[x]);
rnk[x] = (rnk[x] + rnk[tmp]) % ;
return fa[x];
}
}
void merge(int x, int y) {
int rx = find(x), ry = find(y);
if(rx == ry) return;
fa[rx] = ry;
rnk[rx] = (rnk[y] + -rnk[x]) % ;
}
int main() {
int T, n, m, u, v;
scanf("%d", &T);
for (int cs = ; cs <= T; cs++) {
scanf("%d%d", &n, &m);
printf("Scenario #%d:\n", cs);
init(n);
bool f = false;
for (int i = ; i < m; i++) {
scanf("%d%d", &u, &v);
if(find(u) == find(v) && rnk[u] == rnk[v]) f = true;
else merge(u, v);
}
if(f) printf("Suspicious bugs found!\n");
else printf("No suspicious bugs found!\n");
}
return ;
}
普通
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 2e3 + ;
int fa[N*];
void init(int n) {
for (int i = ; i <= n*; i++) {
fa[i] = i;
}
}
int find(int x) {
if(x == fa[x]) return x;
else return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
int rx = find(x), ry = find(y);
if(rx == ry) return;
fa[rx] = ry;
}
int main() {
int T, n, m, u, v;
scanf("%d", &T);
for (int cs = ; cs <= T; cs++) {
scanf("%d%d", &n, &m);
printf("Scenario #%d:\n", cs);
init(n);
bool f = false;
for (int i = ; i < m; i++) {
scanf("%d%d", &u, &v);
if(find(u) == find(v) || find(u+n) == find(v+n)) f = true;
else merge(u, v+n), merge(v, u+n);
}
if(f) printf("Suspicious bugs found!\n");
else printf("No suspicious bugs found!\n");
}
return ;
}
10582 multiset维护（注意删一个元素需要s.erase(s.find(x)),否则会把所有的x都会删掉），顺便复习了一下st表，用st表写了一发
multiset
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e6 + ;
int a[N];
multiset<int>s;
int main() {
int n, k;
scanf("%d", &n);
for (int i = ; i <= n; ++i) scanf("%d", &a[i]);
scanf("%d", &k);
for (int i = ; i < k; i++) s.insert(a[i]);
for (int i = k; i <= n; i++) {
s.insert(a[i]);
auto it = s.end();
it --;
printf("%d%c", *it, " \n"[i==n]);
s.erase(s.find(a[i-k+]));
}
return ;
}
st表
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e6 + ;
int a[N], st[N][];
int query(int l, int r) {
int k = floor(log(r-l+)/log());
return max(st[l][k], st[r - ( << k) + ][k]);
}
int main() {
int n, k;
scanf("%d", &n);
for (int i = ; i <= n; ++i) scanf("%d", &a[i]);
scanf("%d", &k);
for (int i = n; i >= ; i--) {
st[i][] = a[i];
for (int j = ; j + ( << j-) <= n; j++) {
st[i][j] = max(st[i][j-], st[i+( << j-)][j-]);
}
}
for (int i = k; i <= n; i++) printf("%d%c", query(i-k+, i), " \n"[i==n]);
return ;
}
4 stack
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e4 + ;
char s[N];
bool is(char c) {
if(c == '+' || c == '-' || c == '*' || c == '/' || c == '^') return true;
else return false;
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%s", s+);
int n = strlen(s+);
stack<char>st;
for (int i = ; i <= n; i++) {
if(isalpha(s[i])) putchar(s[i]);
else if(is(s[i])) st.push(s[i]);
else if(s[i] == ')') putchar(st.top()), st.pop();
}
puts("");
}
return ;
}
61 线段树区间合并，左区间的左括号和右区间的有括号抵消，看有没有剩下的没匹配的括号
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 3e4 + ;
char s[N];
struct sg_tree{
int L[N<<], R[N<<];
void push_up(int rt) {
L[rt] = L[rt<<] + L[rt<<|] - min(L[rt<<], R[rt<<|]);
R[rt] = R[rt<<] + R[rt<<|] - min(L[rt<<], R[rt<<|]);
}
void build(int rt, int l,int r) {
if(l == r) {
if(s[l] == '(') L[rt] = , R[rt] = ;
else R[rt] = , L[rt] = ;
return ;
}
int m = (l+r) >> ;
build(ls);
build(rs);
push_up(rt);
}
void update(int p, int rt, int l, int r) {
if(l == r) {
L[rt] ^= ;
R[rt] ^= ;
return ;
}
int m = (l+r) >> ;
if(p <= m) update(p, ls);
else update(p, rs);
push_up(rt);
}
}sg; int main() {
int n, m, t, cs = ;
while(~ scanf("%d", &n)) {
scanf("%s", s+);
scanf("%d", &m);
printf("Test %d:\n", ++cs);
sg.build(, , n);
while(m--) {
scanf("%d", &t);
if(!t) {
if(sg.L[] || sg.R[]) printf("NO\n");
else printf("YES\n");
}
else sg.update(t, , , n);
}
}
return ;
}
1716 线段树区间合并，同1043
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 5e4 + ;
const int INF = 0x7f7f7f7f;
struct Tree {
int sum, lv, rv, ans;
}tree[N<<];
void push_up(int rt) {
tree[rt].sum = tree[rt<<].sum + tree[rt<<|].sum;
tree[rt].lv = max(tree[rt<<].lv, tree[rt<<].sum + tree[rt<<|].lv);
tree[rt].rv = max(tree[rt<<|].rv, tree[rt<<|].sum + tree[rt<<].rv);
tree[rt].ans = max(tree[rt<<].rv + tree[rt<<|].lv, max(tree[rt<<].ans, tree[rt<<|].ans));
}
void build(int rt, int l, int r) {
if(l == r) {
scanf("%d", &tree[rt].ans);
tree[rt].lv = tree[rt].rv = tree[rt].sum = tree[rt].ans;
return ;
}
int m = (l+r) >> ;
build(ls);
build(rs);
push_up(rt);
}
void update(int p, int x, int rt, int l ,int r) {
if(l == r) {
tree[rt].lv = tree[rt].rv = tree[rt].sum = tree[rt].ans = x;
return ;
}
int m = (l+r) >> ;
if(p <= m) update(p, x, ls);
else update(p, x, rs);
push_up(rt);
}
Tree query(int L, int R, int rt, int l, int r) {
if(L <= l && r <= R) return tree[rt];
int m = (l + r) >> ;
if(R <= m) return query(L, R, ls);
else if(L > m) return query(L, R, rs);
Tree lft = query(L, R, ls);
Tree rit = query(L, R, rs);
int sum = lft.sum+rit.sum;
int lv = max(lft.lv, lft.sum+rit.lv);
int rv = max(rit.rv, rit.sum+lft.rv);
int ans = max(lft.rv+rit.lv, max(lft.ans, rit.ans));
return Tree{sum, lv, rv, ans};
}
int main() {
int n, m, x, y, op;
scanf("%d", &n);
build(, , n);
scanf("%d", &m);
while(m --) {
scanf("%d%d%d", &op, &x, &y);
if(op) {
Tree res = query(x, y, , , n);
printf("%d\n", res.ans);
}
else {
update(x, y, , , n);
}
}
return ;
}
345 区间dp,经典石子归并问题
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = ;
const int INF = 0x3f3f3f3f;
int a[N], sum[N], dp[N][N];
int main() {
int n;
while(~scanf("%d", &n)) {
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
for (int i = ; i <= n; i++) sum[i] = sum[i-] + a[i];
for (int l = ; l <= n; l ++) {
for (int i = ; i+l- <= n; i++) {
int j = i+l-;
dp[i][j] = INF;
for (int k = i; k < j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+][j] + ((sum[k]-sum[i-])%) * ((sum[j]-sum[k])%));
}
}
}
printf("%d\n", dp[][n]);
}
return ;
}
4580 折半枚举
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = , M = 1e6 + ;
int a[N], b[M];
int main() {
int n;
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
int cnt = ;
for (int i = ; i <= n; i++) {
for (int j = ; j <= n; j++) {
for (int k = ; k <= n; k++) {
b[++cnt] = a[i] * a[j] + a[k];
}
}
}
sort(b+, b++cnt);
LL ans = ;
for (int i = ; i <= n; i++) {
for (int j = ; j <= n; j++) {
for (int k = ; k <= n; k++) {
if(a[i] != ) {
int t1 = lower_bound(b+, b++cnt, a[i]*(a[j]+a[k])) - b;
int t2 = upper_bound(b+, b++cnt, a[i]*(a[j]+a[k])) - b;
ans += t2-t1;
}
}
}
}
printf("%d\n", ans);
return ;
}
302 数学
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head int main() {
int T, n;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
int nn = n;
int t = sqrt(*n);
t++;
if(t*(t-)/ >= n) t--;
n -= t*(t-)/;
if(t%==)printf("TERM %d IS %d/%d\n", nn, n, t-n+);
else printf("TERM %d IS %d/%d\n", nn, t-n+, n);
}
return ;
}
423 状压dp，一开始写了个n*n*(1<<n)，后来发现每次不用枚举每个状态，只需枚举到上一行为止的所有状态就可以了，开个二维vector滚动保存状态，暴力水过？
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = ;
LL dp[(<<) + ][N];
int a[N][N];
bool vis[(<<) + ];
vector<int>sta[];
int main() {
int T, n;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for (int i = ; i <= n; i++) {
for (int j = ; j <= n; j++) scanf("%d", &a[i][j]);
}
mem(dp, );
dp[][] = ;
int cur = ;
sta[].clear();
sta[].clear();
sta[cur].pb();
for (int i = ; i <= n; i++) {
cur ^= ;
sta[cur].clear();
mem(vis, false);
for (int j = ; j <= n; j++) {
if(a[i][j]) {
for (int k = ; k < sta[-cur].size(); k++) {
if(!(sta[-cur][k] & ( << (j-)))) {
dp[sta[-cur][k]|( << (j-))][i] += dp[sta[-cur][k]][i-];
if(!vis[sta[-cur][k]|( << (j-))])sta[cur].pb(sta[-cur][k]|( << (j-))), vis[sta[-cur][k]|( << (j-))] = true;
}
}
}
}
}
printf("%lld\n", dp[(<<n)-][n]);
}
return ;
}
3266 离线+树状数组，先按询问的k排序，然后把从大到小（我的代码是从小到大，求的是小于等与k的）加入这些数的位置，然后只需要维护前缀和就可以了
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 3e4 + , M = 2e5 + ;
int id[N], a[N], bit[N], ans[M], n;
struct node {
int l, r, k, id;
bool operator < (const node & t) const {
return k < t.k;
}
}b[M];
bool cmp(int x, int y) {
return a[x] < a[y];
}
void add(int x, int a) {
while(x <= n) bit[x] += a, x += x&-x;
}
int query(int x) {
int ans = ;
while(x) ans += bit[x], x -= x&-x;
return ans;
}
int main() {
int q;
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &a[i]), id[i] = i;
scanf("%d", &q);
for (int i = ; i <= q; i++) scanf("%d%d%d", &b[i].l, &b[i].r, &b[i].k), b[i].id = i;
sort(b+, b++q);
sort(id+, id++n, cmp);
int t = ;
for (int i = ; i <= q; i++) {
while(t <= n && a[id[t]] <= b[i].k) add(id[t], ), t++;
ans[b[i].id] = b[i].r - b[i].l + - query(b[i].r) + query(b[i].l-);
}
for (int i = ; i <= q; i++) printf("%d\n", ans[i]);
return ;
}
3946 线段树每个节点开个vector, 然后二分求区间第k大，单次询问复杂度（logn)^3，二分一个logn，线段树一个logn，每个节点二分一个logn
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e5 + ;
int a[N];
vector<int>vc[N<<];
vector<int>node;
void build(int rt, int l, int r) {
if(l == r) {
scanf("%d", &a[l]);
vc[rt].pb(a[l]);
return ;
}
int m = (l+r) >> ;
build(ls);
build(rs);
for (int i = l; i <= r; i++) vc[rt].pb(a[i]);
sort(vc[rt].begin(), vc[rt].end());
}
void query(int L, int R, int rt, int l, int r) {
if(L <= l && r <= R) {
node.pb(rt);
return ;
}
int m = (l+r) >> ;
if(L <= m) query(L, R, ls);
if(R > m) query(L, R, rs);
}
int cal(int x) {
int ans = ;
for (int i = ; i < node.size(); i++) {
ans += lower_bound(vc[node[i]].begin(), vc[node[i]].end(), x) - vc[node[i]].begin();
}
return ans;
}
int main() {
int n, m, l, r, k;
scanf("%d%d", &n, &m);
build(, , n);
sort(a+, a++n);
while(m--) {
scanf("%d%d%d", &l, &r, &k);
node.clear();
query(l, r, , , n);
l = , r = n;
int md = (l+r+) >> ;
while(l < r) {
int cnt = cal(a[md]);
if(cnt < k) l = md;
else r = md - ;
md = (l+r+) >> ;
}
printf("%d\n", a[md]);
}
return ;
}
16487 差分数组
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e4 + ;
int a[N];
int main() {
int T, n, m, q, v, l, r;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
mem(a, );
for (int i = ; i <= m; i++) scanf("%d%d%d", &l, &r, &v), l++, r++, a[l] += v, a[r+] -= v;
for (int i = ; i <= n; i++) a[i] += a[i-];
scanf("%d", &q);
for (int i = ; i <= q; i++) scanf("%d", &l), printf("%d\n", a[l+]);
}
return ;
}
4300 暴力水题
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head int main() {
int n;
scanf("%d", &n);
int ans = ;
for (int i = ; i <= n; i++) {
for (int j = ; j * j <= i; j++) {
if(i%j == ) ans++;
}
}
printf("%d\n", ans);
return ;
}
14932 lca水题
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e3 + ;
int anc[N][], deep[N];
vector<int>g[N];
bool vis[N];
void dfs(int o, int u) {
deep[u] = deep[o] + ;
for (int i = ; i < g[u].size(); i++) {
anc[g[u][i]][] = u;
for (int j = ; j < ; j++) anc[g[u][i]][j] = anc[anc[g[u][i]][j-]][j-];
dfs(u, g[u][i]);
}
}
int lca(int u, int v) {
if(deep[u] > deep[v]) swap(u, v);
for (int i = ; i >= ; i--) if(deep[anc[v][i]] >= deep[u]) v = anc[v][i];
if(u == v) return u;
for (int i = ; i >= ; i--) if(anc[u][i] != anc[v][i]) u = anc[u][i], v= anc[v][i];
return anc[u][];
}
int main() {
int T, n, t, u, v, m;
scanf("%d", &T);
for (int cs = ; cs <= T; cs++) {
mem(vis, false);
mem(deep, );
scanf("%d", &n);
for (int i = ; i <= n; i++) g[i].clear();
for (int i = ; i <= n; i++) {
scanf("%d", &t);
while(t--) scanf("%d", &u), vis[u] = true, g[i].pb(u);
}
int rt = ;
for (int i = ; i <= n; i++) if(!vis[i]) rt = i;
dfs(, rt);
scanf("%d", &m);
printf("Case %d:\n", cs);
while(m--) {
scanf("%d%d", &u, &v);
printf("%d\n", lca(u, v));
}
}
return ;
}
32 kmp 或者 字符串hash
kmp
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e6 + ;
const int MOD = 1e9 + ;
int nxt[N];
char a[N], b[N];
vector<int>ans;
int main() {
int n, m;
while(~scanf("%d", &n)){
scanf("%s", a);
scanf("%s", b);
m = strlen(b);
nxt[] = -;
for (int i = ; i < n; i++) {
int j = nxt[i-];
while(a[j+] != a[i] && j >= ) j = nxt[j];
if(a[j+] == a[i]) nxt[i] = j+;
else nxt[i] = -; }
int i = , j = ;
ans.clear();
while(j < m) {
if(b[j] == a[i]) {
i++;
j++;
if(i == n) ans.pb(j - n), i = nxt[i-]+;
}
else {
if(i == ) j++;
else i = nxt[i-]+;
}
}
if(ans.size() == ) puts("");
else {
for (int i = ; i < ans.size(); i++) printf("%d\n", ans[i]);
}
}
return ;
}
字符串hash
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e6 + ;
const int MOD = 1e9 + ;
const int base = ;
char a[N], b[N];
int H[N], p[N];
int get_H(int l, int r) {
return (H[r] - 1LL * H[l-] * p[r-l+] % MOD + MOD)%MOD;
}
vector<int>ans;
int main() {
int n, m;
p[] = ;
for (int i = ; i < N; i++)p[i] = (1LL * p[i-] * base)%MOD;
while(~scanf("%d", &n)){
scanf("%s", a+);
int f = ;
for (int i = ; i <= n; i++) f = (1LL * f * base + a[i] - 'a')%MOD;
scanf("%s", b+);
m = strlen(b+);
for (int i = ; i <= m; i++) H[i] = (1LL * H[i-] * base + (b[i] - 'a'))%MOD;
ans.clear();
for (int i = ; i+n- <= m; i++) {
if(get_H(i, i+n-) == f) ans.pb(i);
}
if(ans.size() == ) puts("");
else {
for (int i = ; i < ans.size(); i++) printf("%d\n", ans[i]-);
}
}
return ;
}
我的傻逼写法：离线+指针，复杂度：Maxa * log(a) + n
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e5 + ;
pii Q[N];
int ans[N];
int main() {
int T;
scanf("%d", &T);
for (int i = ; i <= T; i++) scanf("%d", &Q[i].fi), Q[i].se = i;
sort(Q+, Q++T);
int l = , c2 = , c5 = ;
for (int i = ; i <= T; i++) {
while(l < Q[i].fi) {
l++;
int t = l;
while(t% == ) c2++, t /= ;
while(t% == ) c5++, t /= ;
}
ans[Q[i].se] = min(c2, c5);
}
for (int i = ; i <= T; i++) printf("%d\n", ans[i]);
return ;
}
正解：数学
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head int main() {
int T, n;
scanf("%d", &T);
for (int i = ; i <= T; i++) {
scanf("%d", &n);
int ans = ;
for (LL i = ; i <= n; i *= ) ans += n/i;
printf("%d\n", ans);
}
return ;
}
7742 水题
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 5e5 + ;
int a[N];
int main() {
int n;
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
sort(a+, a++n);
int c = ;
for (int i = ; i <= n; i++) {
if(a[i] != a[i-]) {
if(c == ) return * printf("%d\n", a[i-]);
c = ;
}
else c++;
}
if(c == ) printf("%d\n", a[n]);
return ;
}
54 java大数
import java.math.*;
import java.util.*; public class Main {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
BigInteger d = new BigInteger("2");
while(reader.hasNext()){
BigInteger a = reader.nextBigInteger();
BigInteger b = reader.nextBigInteger();
BigInteger c = a.subtract(b);
c = c.divide(d);
System.out.println(c.add(b));
System.out.println(c);
}
}
}
3442 快速幂
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL q_pow(LL n, LL k) {
LL ans = ;
while(k) {
if(k&) ans = (ans * n) % ;
n = (n*n) % ;
k >>= ;
}
return ans;
}
int main() {
int T;
LL a, b;
scanf("%d", &T);
while(T--) {
scanf("%lld%lld", &a, &b);
printf("%lld\n", q_pow(a, b));
}
return ;
}
11515 贪心，每次取这个位置之后能达到的最近的位置，先把每个l和r标记为a[l] = r，然后求个后缀最小值，预处理或者树状数组都可以
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e5 + , M = 1e6 + ;
const int INF = 0x3f3f3f3f;
pii a[N];
int b[M], bit[M];
int mx;
void add(int x, int a) {
while(x) bit[x] = min(bit[x], a), x -= x&-x;
}
int query(int x) {
int ans = INF;
while(x <= mx) ans = min(ans, bit[x]), x += x&-x;
return ans;
}
int main() {
int T, n;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
mx = ;
for (int i = ; i <= n; i++) scanf("%d%d", &a[i].fi, &a[i].se), a[i].fi++, a[i].se++, mx = max(mx, a[i].se);
//sort(a+1, a+1+n);
mem(b, INF);
mem(bit, INF);
for (int i = ; i <= n; i++) b[a[i].fi] = min(b[a[i].fi], a[i].se);
for (int i = ; i < mx; i ++) {
if(b[i] != INF) add(i, b[i]); //cout << i << " " << b[i] << endl;
}
int st = , ans = ;
while(st <= mx) {
st = query(st);
if(st == INF) break;
else ans++;
}
printf("%d\n", ans);
}
return ;
}
39 完全背包
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = , M = 1e4 + ;
const int INF = 0x3f3f3f3f;
pii a[N];
int dp[M];
int main() {
int T, n, e, f, w;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &e, &f);
scanf("%d", &n);
for (int i = ; i <= n; i++)scanf("%d%d", &a[i].fi, &a[i].se);
mem(dp, INF);
dp[] = ;
w = f - e;
for (int i = ; i <= n; i++) {
for (int j = a[i].se; j <= w; j++) {
dp[j] = min(dp[j], dp[j-a[i].se]+a[i].fi);
}
}
if(dp[w] == INF) printf("This is impossible.\n");
else printf("The minimum amount of money in the piggy-bank is %d.\n", dp[w]);
}
return ;
}
3273 离散化+树状数组+二分
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 2e5 + ;
pair<int, char> Q[N];
int a[N], bit[N], cnt[N], q;
char s[];
void add(int x, int a) {
while(x <= q) bit[x] += a, x += x&-x;
}
int query(int x) {
int ans = ;
while(x) ans += bit[x], x -= x&-x;
return ans;
}
int MP[N];
int main() {
int t;
scanf("%d", &q);
for (int i = ; i <= q; i++) {
scanf("%s%d", s, &t);
Q[i] = mp(t, s[]);
a[i] = t;
}
sort(a+, a++q);
for (int i = ; i <= q; i++) {
t = lower_bound(a+, a++q, Q[i].fi) - a;
if(Q[i].se != 'K') {
MP[t] = Q[i].fi;
Q[i].fi = t;
}
}
for (int i = ; i <= q; i++) {
if(Q[i].se == 'I') {
if(!cnt[Q[i].fi])add(Q[i].fi, ), cnt[Q[i].fi]++;
}
else if(Q[i].se == 'D') {
if(cnt[Q[i].fi]) cnt[Q[i].fi]--, add(Q[i].fi, -);
}
else if(Q[i].se == 'K') {
if(Q[i].fi > query(q)) {
printf("invalid\n");
continue;
}
int l = , r = q, m = (l+r) >> ;
while(l < r) {
if(query(m) < Q[i].fi) l = m+;
else r = m;
m = (l+r) >> ;
}
printf("%d\n", MP[m]);
}
else if(Q[i].se == 'C') {
printf("%d\n", query(Q[i].fi-));
}
}
return ;
}
5449 stack
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 2e3 + ;
char s[N];
int main() {
int cs = ;
while(~scanf("%s", s+)) {
if(s[] == '-') break;
int n = strlen(s+);
int l = , ans = ;
for (int i = ; i <= n; i++) {
if(s[i] == '{') l++;
else {
if(l) l--;
else ans++, l++;
}
}
ans += l/;
printf("%d. %d\n", ++cs, ans);
}
return ;
}
12471 dp+记忆化搜索
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 2e3 + ;
int dp[N][N][];
int dir[][] = {, , -, -, -, };
int dfs(int a, int b, int t) {
if(a <= || b <= ) return -;
if(~dp[a][b][t]) return dp[a][b][t];
for (int i = ; i < ; i++) {
if(i != t)dp[a][b][t] = max(dp[a][b][t], dfs(a+dir[i][], b+dir[i][], i)+);
}
return dp[a][b][t];
}
int main() {
int T, h, a;
mem(dp, -);
scanf("%d", &T);
while(T--) {
scanf("%d%d", &h, &a);
printf("%d\n", max(max(dfs(h, a, ), dfs(h, a, )), dfs(h, a, )));
}
return ;
}
24 java大数
import java.math.*;
import java.util.*; public class Main {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int t;
long n;
t = reader.nextInt();
for (int i = 1; i <= t; i++) {
n = reader.nextLong();
BigInteger ans = new BigInteger("1");
for (long j = 1; j <= n; j++) {
ans = ans.multiply(BigInteger.valueOf(j));
}
System.out.println(ans);
}
}
}
9921 bfs水题
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define piii pair<int,pii>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = ;
char s[N][N];
bool vis[N][N];
int n, m;
int dir[][] = {, , , , -, , , -, , -, -, , , , -, -};
queue<piii>q;
int main() {
int cs = ;
while(~scanf("%d%d", &n, &m)) {
if(!n && !m) break;
for (int i = ; i <= n; i++) scanf("%s", s[i]+);
mem(vis, false);
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
if(s[i][j] == 'A') {
q.push({, {i, j}});
vis[i][j] = true;
}
}
}
int ans = ;
while(!q.empty()) {
piii p = q.front();
q.pop();
ans = p.fi;
for (int i = ; i < ; i++) {
int x = p.se.fi + dir[i][];
int y = p.se.se + dir[i][];
if( <= x && x <= n && <= y && y <= m && !vis[x][y] && s[x][y] == s[p.se.fi][p.se.se]+) {
vis[x][y] = true;
ans = p.fi + ;
q.push({p.fi+, {x, y}});
}
}
}
printf("Case %d: %d\n", ++cs, ans);
}
return ;
}
总结1：按点赞数降序第一页都是水题，不过复习了之前学过的算法（线段树合并、区间dp之类的），学会了各种离线操作，所以不打算刷简单题了。