import java.io.*;
import java.util.*; public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner (System.in);
int r = cin.nextInt ();
int c = cin.nextInt ();
int n = cin.nextInt ();
int k = cin.nextInt ();
int[][] a = new int[12][12];
for (int i=0; i<n; ++i) {
int x = cin.nextInt ();
int y = cin.nextInt ();
a[x][y] = 1;
}
int ans = 0;
for (int sx=1; sx<=r; ++sx) {
for (int lx=0; sx+lx<=r; ++lx) {
for (int sy=1; sy<=c; ++sy) {
for (int ly=0; sy+ly<=c; ++ly) {
int cnt = 0;
for (int i=sx; i<=sx+lx; ++i) {
for (int j=sy; j<=sy+ly; ++j) {
if (a[i][j] == 1) cnt++;
if (cnt >= k) break;
}
}
if (cnt >= k) ans++;
}
}
}
}
System.out.println (ans);
}
}
相对位置不变，０的位置任意，当做不存在．查看每个点到对应的点是否能一起移动到．
#include <bits/stdc++.h> const int N = 2e5 + 5;
int a[N], b[N];
int n; int main() {
scanf ("%d", &n);
int tot1 = 0, tot2 = 0;
for (int x, i=0; i<n; ++i) {
scanf ("%d", &x);
if (x != 0) a[tot1++] = x;
}
for (int x, i=0; i<n; ++i) {
scanf ("%d", &x);
if (x != 0) b[tot2++] = x;
}
int s = 0;
for (; s<tot2; ++s) {
if (b[s] == a[0]) break;
}
bool flag = true;
for (int i=0; i<tot1; ++i) {
if (b[(i+s)%(n-1)] != a[i]) {
flag = false; break;
}
}
if (flag) puts ("YES");
else puts ("NO"); return 0;
}
数位DP C - XOR Equation
题意：求多少对(a, b)满足a + b == s && a ^ b == x
分析：ｓ和ｘ拆分成二进制，dp[i][4][0/1]第一维是二进制长度，第二维是ａ和ｂ二进制下第ｉ位的方案（０１，１０，００，１１），第三维是是否第ｉ位会进位，递推一下能够在ｌｏｇ（Ｎ）解决．
#include <bits/stdc++.h> typedef long long ll;
int s[41], x[41];
ll dp[41][4][2]; void updata(int id) {
if (s[id] == x[id]) {
if (s[id] == 0) { //0 0
if (id == 0) {
dp[id][2][0] = dp[id][3][1] = 1;
}
else {
for (int j=0; j<4; ++j) {
dp[id][2][0] += dp[id-1][j][0];
dp[id][3][1] += dp[id-1][j][0];
}
}
}
else { //1 1
if (id == 0) {
dp[id][0][0] = dp[id][1][0] = 1;
}
else {
for (int j=0; j<4; ++j) {
dp[id][0][0] += dp[id-1][j][0];
dp[id][1][0] += dp[id-1][j][0];
}
}
}
}
else {
if (s[id] == 0) { //0 1
for (int j=0; j<4; ++j) {
dp[id][0][1] += dp[id-1][j][1];
dp[id][1][1] += dp[id-1][j][1];
}
}
else { //1 0
for (int j=0; j<4; ++j) {
dp[id][2][0] += dp[id-1][j][1];
dp[id][3][1] += dp[id-1][j][1];
}
}
}
} int main() {
ll S, X; std::cin >> S >> X;
if (X == 0) {
puts ("1"); return 0;
}
bool same = false;
if (S == X) same = true;
int n = 0, m = 0;
while (S) {
if (S & 1) s[n++] = 1;
else s[n++] = 0;
S >>= 1;
}
while (X) {
if (X & 1) x[m++] = 1;
else x[m++] = 0;
X >>= 1;
}
int len = std::max (n, m);
for (int i=0; i<len; ++i) {
updata (i);
}
ll ans = 0;
for (int i=0; i<4; ++i) {
ans += dp[len-1][i][0];
}
if (same && ans >= 2) ans -= 2;
std::cout << ans << '\n'; return 0;
}
树状数组 D - Factory Repairs
单点更新以及区间求和，不过不知道该点是ｋ天前还是后，树状数组开二维．
import java.io.*;
import java.util.*; public class Main {
static int[][] C;
static int[] A;
static int n;
static void updata(int i, int j, int x) {
while (i <= n) {
C[i][j] += x;
i += i & -i;
}
}
static int query(int i, int j) {
int ret = 0;
while (i > 0) {
ret += C[i][j];
i -= i & -i;
}
return ret;
}
static int min(int a, int b) {
if (a < b) return a;
else return b;
}
public static void main(String[] args) {
Scanner cin = new Scanner (new BufferedInputStream (System.in));
n = cin.nextInt ();
int k = cin.nextInt ();
int a = cin.nextInt ();
int b = cin.nextInt ();
int q = cin.nextInt ();
C = new int[n+5][2];
A = new int[n+5];
for (int i=0; i<q; ++i) {
int op = cin.nextInt ();
if (op == 1) {
int d = cin.nextInt ();
int e = cin.nextInt ();
int tmp = A[d]; A[d] += e;
updata (d, 0, min (b, A[d]) - min (b, tmp));
updata (d, 1, min (a, A[d]) - min (a, tmp));
}
else {
int p = cin.nextInt ();
int ans = query (p - 1, 0) + query (n, 1) - query (p+k-1, 1);
System.out.println (ans);
}
}
}
}
贪心＋双端队列 E - Package Delivery
题意：ｍ个加油站，每单位油有价格，汽车有油的容量，初始满油，问到终点最少消费多少．
分析： 假设起点也算是一个加油站，免费，且汽车初始空油，那么每一个加油站最多能给汽车充ｎ单位油，那么到下一个加油站要选择之前加油站价格最少的加油，这里用双端队列维护最低价格的加油站．
#include <bits/stdc++.h> typedef long long ll;
const int N = 2e5 + 5;
int dque[N];
std::pair<int, int> station[N];
int d, n, m; int main() {
scanf ("%d%d%d", &d, &n, &m);
for (int i=0; i<m; ++i) {
scanf ("%d%d", &station[i].first, &station[i].second);
}
station[m++] = std::make_pair (0, 0);
station[m++] = std::make_pair (d, 0);
std::sort (station, station+m);
for (int i=0; i<m-1; ++i) {
if (station[i].first + n < station[i+1].first) {
puts ("-1"); return 0;
}
}
int qs = 0, qe = 0, now = 0; ll ans = 0;
for (int i=0; i<m; ++i) {
int x = station[i].first, p = station[i].second;
while (qs < qe && station[dque[qs]].first + n < x) {
ans += 1ll * (station[dque[qs]].first + n - now) * station[dque[qs]].second;
now = station[dque[qs]].first + n;
qs++;
}
ans += 1ll * (x - now) * station[dque[qs]].second;
now = x;
while (qs < qe && station[dque[qe-1]].second > p) {
qe--;
}
dque[qe++] = i;
}
std::cout << ans << '\n'; return 0;
}
树形ＤＰ F - Preorder Test
题意：选择一条ｋ长的ＤＦＳ先序遍历路径，使得其中的最小值最大
分析：二分枚举最小值，然后枚举每个点出发的大于最小值的路径长度．求路径长度用到树形ＤＰ
首先ｄｏｗｎ［ｕ］表示ｕ的子树下最多能走的路径长度，然后第二次ｄｐ［ｕ］表示以ｕ为根节点下最多能走的路径长度，ｕｐ是ｕ以上完整的最大长度
#include <bits/stdc++.h> const int N = 2e5 + 5;
struct DP {
int sum, mx;
DP operator + (const DP &rhs) const {
return DP {sum + rhs.sum, std::max (mx, rhs.mx)};
}
};
int a[N], total[N], down[N], dp[N];
bool good[N];
std::vector<int> edge[N];
int n, k; void DFS(int u, int fa) {
total[u] = 1;
int sum = 0, mx = 0;
for (auto v: edge[u]) {
if (v == fa) continue;
DFS (v, u);
total[u] += total[v];
if (down[v] == total[v]) {
sum += total[v];
} else {
mx = std::max (mx, down[v]);
}
}
down[u] = sum + mx + 1;
if (!good[u]) down[u] = 0;
} void DFS2(int u, int fa, int up) { //learn from tourist
std::vector<int> children;
int sum = 0, mx = 0;
for (auto v: edge[u]) {
if (v == fa) continue;
if (down[v] == total[v]) {
sum += down[v];
} else {
mx = std::max (mx, down[v]);
}
children.push_back (v);
}
if (up == n - total[u]) {
sum += up;
} else {
mx = std::max (mx, up);
}
dp[u] = sum + mx + 1;
if (!good[u]) dp[u] = 0; int sz = children.size ();
if (sz == 0) return ;
std::vector<DP> predown (sz + 1);
predown[0] = {0, 0};
for (int i=0; i<sz; ++i) {
int v = children[i];
predown[i+1] = predown[i];
if (down[v] == total[v]) {
predown[i+1].sum += down[v];
} else {
predown[i+1].mx = std::max (predown[i+1].mx, down[v]);
}
}
std::vector<DP> sufdown (sz + 1);
sufdown[sz] = {0, 0};
for (int i=sz-1; i>=0; --i) {
int v = children[i];
sufdown[i] = sufdown[i+1];
if (down[v] == total[v]) {
sufdown[i].sum += down[v];
} else {
sufdown[i].mx = std::max (sufdown[i].mx, down[v]);
}
}
for (int i=0; i<sz; ++i) {
int v = children[i];
DP now = predown[i] + sufdown[i+1];
if (up == n - total[u]) {
now.sum += up;
} else {
now.mx = std::max (now.mx, up);
}
int new_up = now.sum + now.mx + 1;
if (!good[u]) new_up = 0;
DFS2 (v, u, new_up);
}
} bool check(int v) {
for (int i=1; i<=n; ++i) good[i] = (a[i] >= v);
DFS (1, 0);
DFS2 (1, 0, 0);
for (int i=1; i<=n; ++i) {
if (dp[i] >= k) return true;
}
return false;
} int main() {
scanf ("%d%d", &n, &k);
for (int i=1; i<=n; ++i) {
scanf ("%d", a+i);
}
for (int u, v, i=1; i<n; ++i) {
scanf ("%d%d", &u, &v);
edge[u].push_back (v);
edge[v].push_back (u);
}
int low = 0, high = 1000005;
while (low < high) {
int mid = (low + high + 1) >> 1;
if (check (mid)) {
low = mid;
} else {
high = mid - 1;
}
}
printf ("%d\n", low); return 0;
}