#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f; int main(void) {
int n; scanf ("%d", &n);
int ans = n / 4;
if (n % 4 == 0) {
ans--;
}
if (n % 2 != 0) ans = 0;
printf ("%d\n", ans); return 0;
}
构造+贪心 B - Vika and Squares
题意：给你一堆油漆，然后选择一个油漆开始涂，一个油漆一个油漆的涂，就是涂过4后面涂5，涂过n后面可以涂1，一直涂到不能继续就停止，问最多能涂多少块
有段时间了，都不知道当时自己怎么做出来的了。
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int a[N]; int main(void) {
int n; scanf ("%d", &n);
int mn = INF;
for (int i=1; i<=n; ++i) {
scanf ("%d", &a[i]);
if (a[i] < mn) mn = a[i];
}
vector<int> pos;
for (int i=1; i<=n; ++i) {
if (a[i] == mn) {
pos.push_back (i);
}
}
int mx_len = 0, sz = pos.size ();
for (int i=0; i<sz-1; ++i) {
mx_len = max (mx_len, pos[i+1] - pos[i] - 1);
}
mx_len = max (mx_len, n - pos[sz-1] + pos[0] - 1);
printf ("%I64d\n", 1ll * n * mn + mx_len); return 0;
}
题意：(1 << k)边长的矩形，第i行与第j行乘积和为0的方案
分析：因为每次都乘2，构造方法：比如++ 变成++ ++那么对应的有-- ++; 再如-++- 变成 -++- -++- 那么对应的有+--+ +--+
#include <bits/stdc++.h>
int a[522][522];
int main(void) {
int k; scanf ("%d", &k);
int tot = 1;
int len = 1 << k;
a[1][1] = 1;
for (int j=1; j<len; j<<=1) {
int t = tot;
for (int l=1; l<=t; ++l) {
for (int m=1; m<=j; ++m) {
a[l][m+j] = a[l][m];
}
tot++;
for (int m=1; m<=2*j; ++m) {
if (m <= j) a[tot][m] = 1 - a[l][m];
else a[tot][m] = a[l][m];
}
}
}
for (int i=1; i<=len; ++i) {
for (int j=1; j<=len; ++j) {
if (a[i][j] == 1) printf ("+");
else printf ("*");
}
puts ("");
}
return 0;
}
离线+扫描线+线段树 D - Vika and Segments
题意：给一些横线或者竖线，问一共有多少个点(重复的算一次)
分析：可以转换成求矩形面积的问题，把矩形左下角的点x1--, y1--构成一个宽度为1的矩形，点的个数：x2 - x1，那么面积就是点的个数，离散后加成端更新就可以了。
#include <bits/stdc++.h> typedef long long ll;
const int N = 1e5 + 5;
struct Seg {
int l, r, h, c;
Seg() {}
Seg(int l, int r, int h, int c) : l (l), r (r), h (h), c (c) {}
bool operator < (const Seg &a) const {
return h < a.h || (h == a.h && l < a.l);
}
};
Seg seg[N<<1];
int X[N<<1]; #define lson l, mid, o << 1
#define rson mid, r, o << 1 | 1
struct Segment_Tree {
int sum[N<<3], cover[N<<3];
void push_up(int l, int r, int o) {
if (cover[o]) {
sum[o] = X[r] - X[l];
}
else if (l + 1 == r) {
sum[o] = 0;
}
else {
sum[o] = sum[o<<1] + sum[o<<1|1];
}
}
void build(int l, int r, int o) {
sum[o] = cover[o] = 0;
if (l + 1 == r) return ;
int mid = l + r >> 1;
build (lson); build (rson);
}
void updata(int ql, int qr, int c, int l, int r, int o) {
if (ql <= l && r <= qr) {
cover[o] += c;
push_up (l, r, o);
return ;
}
else if (l + 1 == r) return ;
int mid = l + r >> 1;
if (ql <= mid) updata (ql, qr, c, lson);
if (qr > mid) updata (ql, qr, c, rson);
push_up (l, r, o);
}
}st; int n, totx, tots; ll run(void) {
ll ret = 0;
std::sort (seg, seg+tots);
std::sort (X, X+totx);
totx = std::unique (X, X+totx) - X;
st.build (0, totx - 1, 1);
for (int i=0; i<tots-1; ++i) {
int l = std::lower_bound (X, X+totx, seg[i].l) - X;
int r = std::lower_bound (X, X+totx, seg[i].r) - X;
st.updata (l, r, seg[i].c, 0, totx - 1, 1);
ret += 1ll * st.sum[1] * (seg[i+1].h - seg[i].h);
}
return ret;
} int main(void) {
scanf ("%d", &n);
int x1, y1, x2, y2;
totx = tots = 0;
for (int i=0; i<n; ++i) {
scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
if (x1 > x2 || y1 > y2) {
std::swap (x1, x2); std::swap (y1, y2);
}
x1--; y1--;
seg[tots++] = Seg (x1, x2, y1, 1);
seg[tots++] = Seg (x1, x2, y2, -1);
X[totx++] = x1; X[totx++] = x2;
}
printf ("%I64d\n", run ()); return 0;
}