T1.欧几里得的噩梦
第一眼，这不是线性基板子题吗。但是值域是\(2^{5e5}\)，但是我们发现它的一个神奇性质，一个数的二进制中只有两个一。我们定义高位为x，低位为y。如果线性基中\(p[x]\)空，直接插入，令\(p[x]=y\)；如果非空，x这一位被消掉，令\(x=p[x]\)，如果x这时小于y就交换一下，因为线性基的构造是从高到低的。我们发现当这个数不能被插入时当且仅当有一个时刻\(x=y\)。这样暴力跳的时间复杂度不能保证，但是数据太水了，基本和正解一个速度。但是我们还是需要优化的，发现\(x=p[x]\)的状态为一棵树，而且这个关系是可传递的，并且如果存在某一时刻\(x=y\)，那么之后这些位的p相同。所以这启发我们用并查集维护，每次\(find\)它们的最低位，看是否相等，如果相等，说明异或和为0。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <bits/stdc++.h>
#define re register int
using namespace std; int wrt[20], TP;
const int Z = 5e5 + 10; const int mod = 1e9 + 7; typedef long long ll;
inline int read() { int x = 0, f = 0; char c = getchar(); while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; }
inline void write(int x) { TP = 0; if (x < 0) putchar('-'), x = -x; while (x >= 10) wrt[++TP] = x % 10, x /= 10; wrt[++TP] = x; while (TP) putchar(wrt[TP--] | 48); putchar(' '); }
inline int qpow(int b) { ll res = 1; while (b--) res = res * 2 % mod; return res; }
int n, m, ans[Z], tot;
int p[Z];
inline int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
inline bool insert(int x, int y)
{
x = find(x), y = find(y);
if (x == y) return false;
if (x < y) swap(x, y);
p[x] = y; return true;
}
sandom main()
{
n = read(), m = read();
for (re i = 0; i <= m; i++) p[i] = i;
for (re i = 1; i <= n; i++)
{
int op = read(), x = read(), y = 0;
if (op == 2) y = read();
if (insert(x, y)) ans[++tot] = i;
}
write(qpow(tot)), write(tot), putchar('\n');
for (re i = 1; i <= tot; i++) write(ans[i]);
return 0;
}
T2.清扫
考试只打了菊花图的，但是考后发现只需要对此拓展一下，对于每一个节点都判断一下就可以了。但是CD大佬有了更加简洁、通俗的方法。将贪心转化为方程问题。对于一棵子树，它的叶子节点中要么两两配对，两个叶子节点分别减1，根节点减1；要么一个叶子节点与子树外的一个叶子节点配对，叶子节点减1，根节点减1。我们设\(x\)为第一种情况的操作数，\(y\)为第二种情况的操作数。定义\(sum\)为子树的石子和（不包括自己）。则有方程组
\[2x+y=sum[rt] \\ x+y=a[rt] \\ \]显然方程有解要满足\(x,y>=0\)，同时还需要规定一个上界，即为\(max[rt]<=a[rt]\)（\(max[rt]\)为子树中最大的\(sum\)），因为超过了的话，显然父亲根本不够减完儿子。对于每一个非叶子节点，进行这样的处理，并把节点的石子数减去\(x,y\)的开销，作为新的叶子节点，向上回溯。最后需要判断根节点的石子数是否为0。细节：根节点的度数大于1，不然就作为叶子了。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <bits/stdc++.h>
#define re register int
using namespace std;
const int Z = 1e5 + 10;
inline int read() { int x = 0, f = 0; char c = getchar(); while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; }
inline int max(int a, int b) { return a > b ? a : b; } inline int min(int a, int b) { return a < b ? a : b; }
int n, m, k, ans;
vector <int> e[Z];
int a[Z], root;
int sum[Z], siz[Z];
bool dfs(int rt, int fa)
{
if (e[rt].size() == 1) { sum[rt] = a[rt]; return true; }//叶子节点
for (re i = 0; i < e[rt].size(); i++)
{
int son = e[rt][i];
if (son == fa) continue;
if (!dfs(son, rt)) return false;
sum[rt] += sum[son];
siz[rt] = max(siz[rt], sum[son]);
}
if (siz[rt] > a[rt]) return false;
int x = sum[rt] - a[rt], y = 2 * a[rt] - sum[rt];
sum[rt] = y;//将它作为叶子节点上传
return x >= 0 && y >= 0;
}
sandom main()
{
n = read();
for (re i = 1; i <= n; i++) a[i] = read();
if (n == 2) { a[1] == a[2] ? puts("YES") : puts("NO"); return 0; }
for (re i = 1; i < n; i++)
{
int x = read(), y = read();
e[x].push_back(y), e[y].push_back(x);
}
for (re i = 1; i <= n; i++) if (e[i].size() > 1) { root = i; break; }
if (dfs(root, 0) && sum[root] == 0) puts("YES");
else puts("NO");
return 0;
}
T3.购物
这么水的题，我竟然没有做！！！结论题，但是证明是难点。先说结论：对于某一个价格\(w\)，k的取值范围是\([\lceil \frac{w}{2}\rceil,w ]\)。按\(a\)排序后，定义\(s[i]\)为a的前缀和。对于其中一个\(a[i]\)的加入，新扩展的区间最远将到\(s[i]\)，中间部分要么连续，要么只在\([s[i-1],\frac{a[i]}{2}]\)有空隙，要么连续，对于\([\frac{a[i]}{2}, s[i]]\)一定可以被覆盖。
首先明确：1式\([\frac{a[i]}{2}, a[i]]\)以及2式\([\frac{s[i]}{2}, s[i]]\)一定可以覆盖，3式\([1,s[i-1]]\)以及处理完，默认全部覆盖。需证明\([\frac{a[i]}{2}, s[i]]\)一定可以覆盖。
证明：假设前\(i-1\)个已经处理好，把问题看作两条线段的覆盖问题。分情况讨论：
1.3式包含1式，此时有\(\frac{a[i]}{2}<a[i]<s[i-1]\quad \because s[i]=s[i-1]+a[i]\quad \therefore 2a[i]< s[i]< 2s[i-1]\quad \therefore \frac{a[i]}{2}< a[i]< \frac{s[i]}{2}< s[i-1]< s[i]\)，因为\(s[i-1]\)前已经处理完，且2式与\(s[i-1]\)相交，得证。覆盖连续。
2.3式与1式相交，此时有\(\frac{a[i]}{2}<s[i-1]<a[i]\quad \because s[i]=s[i-1]+a[i]\quad \therefore 2s[i-1]< s[i]< 2a[i]\quad \therefore \frac{a[i]}{2}< s[i-1]< \frac{s[i]}{2}< a[i]< s[i]\)，因为1式与2式相交，得证。覆盖连续。
3.3式与1式分离，此时有\(s[i-1]<\frac{a[i]}{2}<a[i]\quad \because s[i]=s[i-1]+a[i]\quad \therefore 2s[i-1]< s[i]< 2a[i]\quad \therefore \frac{a[i]}{2}< s[i-1]< \frac{s[i]}{2}< a[i]< s[i]\)，因为1式与2式相交，得证。只有\((s[i-1], \frac{a[i]}{2})\)断层。
证毕，开始贪心。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <bits/stdc++.h>
#define re register int
#define int long long
using namespace std; int wrt[20], TP;
const int Z = 1e5 + 10;
inline int read() { int x = 0, f = 0; char c = getchar(); while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; }
inline void write(int x) { TP = 0; if (x < 0) putchar('-'), x = -x; while (x >= 10) wrt[++TP] = x % 10, x /= 10; wrt[++TP] = x; while (TP) putchar(wrt[TP--] | 48); putchar('\n'); }
inline int max(int a, int b) { return a > b ? a : b; } inline int min(int a, int b) { return a < b ? a : b; }
inline int lowbit(int x) { return x & (-x); }
int n, m, k, ans;
int a[Z];
sandom main()
{
fre(test, test);
n = read();
for (re i = 1; i <= n; i++) a[i] = read();
sort(a + 1, a + 1 + n);
int sum = 0;
for (re i = 1; i <= n; i++)
{
int j = (a[i] - 1) / 2 + 1;
if (j <= sum) ans += a[i];//相交
else ans += sum + a[i] - j + 1;//断层
sum += a[i];//维护前缀和
}
cout << ans;
return 0;
}
T4.ants
回滚莫队板子题。permu的加强版。但是当时用普通莫队加山海经水过了，这次被卡了，不仅如此，由于我的莫队没有排序……，喜提20分。由于是板子，直接上代码。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <bits/stdc++.h>
#define re register int
using namespace std; int wrt[20], TP;
const int Z = 1e5 + 10;
inline int read() { int x = 0, f = 0; char c = getchar(); while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; }
inline void write(int x) { TP = 0; if (x < 0) putchar('-'), x = -x; while (x >= 10) wrt[++TP] = x % 10, x /= 10; wrt[++TP] = x; while (TP) putchar(wrt[TP--] | 48); putchar('\n'); }
inline int max(int a, int b) { return a > b ? a : b; } inline int min(int a, int b) { return a < b ? a : b; }
int n, m, k, ans[Z];
int be[Z], p[Z], d[Z];
struct ant
{
int l, r, id;
friend bool operator <(ant A, ant B)
{
if (be[A.l] == be[B.l]) return A.r < B.r;//保证同一块内右端点只扩展
return be[A.l] < be[B.l];//分块讨论
}
}; ant que[Z];
int L[Z], R[Z];
int l, r, res, top;
struct delte { int a, b, c, d, e; }; delte stk[Z];
inline void add(int x, bool op)
{
L[x] = R[x] = x;
if (L[x - 1]) L[x] = L[x - 1];
if (R[x + 1]) R[x] = R[x + 1];
if (op) stk[++top] = delte{L[x], R[L[x]], R[x], L[R[x]], x};
R[L[x]] = R[x], L[R[x]] = L[x];
res = max(res, R[x] - L[x] + 1);
}
inline void del(delte x) { R[x.a] = x.b, L[x.c] = x.d, L[x.e] = R[x.e] = 0; }
inline int violent(int l, int r)//在同一块内暴力扫
{
int ans = 1, cnt = 1;
for (re i = l; i <= r; i++) d[i] = p[i];
sort(d + l, d + r + 1); d[l - 1] = -1;
for (re i = l; i <= r; i++)
{
if (d[i] == d[i - 1] + 1) cnt++;
else cnt = 1;
ans = max(ans, cnt);
}
return ans;
}
sandom main()
{
n = read(), m = read(); int t = sqrt(n);
for (re i = 1; i <= n; i++) be[i] = (i - 1) / t + 1;
for (re i = 1; i <= n; i++) p[i] = read();
for (re i = 1; i <= m; i++) que[i].l = read(), que[i].r = read(), que[i].id = i;
sort(que + 1, que + 1 + m);
for (re i = 1; i <= m; i++)
{
ant q = que[i];
if (be[q.l] != be[que[i - 1].l])//进入下一块清空
{
for (re i = 1; i <= n; i++) L[i] = R[i] = 0;
r = min(t * be[q.l], n), l = r + 1; res = 0;
}
if (be[q.l] == be[q.r]) ans[q.id] = violent(q.l, q.r);//同一块暴力扫
else
{
while (r < q.r) add(p[++r], 0);//持续扩展
int tmp = res;
while (l > q.l) add(p[--l], 1);//扩展完撤销
ans[q.id] = res; res = tmp;
while (top) del(stk[top--]), l++;//回滚撤销
}
}
for (re i = 1; i <= m; i++) write(ans[i]);
return 0;
}