全是\(JOI\)的题……为什么不做本民族的题（恼）
T1.选举
原以为是一道神奇贪心，所以写了\(O(n)\)的转移，但是发现\(n<=500\)，这……都不用跑都知道假了。好吧，是一道dp——我们把n个州分为A、B、C（分别表示只赢得选票、又赢得选举、啥也没得到）。\(dp[i][j]\)定义为前\(i\)个州，得到了\(j\)个协助者。显然如果已知了需要\(k\)个\(B\)州，那么一定先在这\(k\)个州演讲，在从剩下的州里选几个\(A\)州演讲，每一个州的时间都是\(\frac{a}{k+1}\)。外层枚举想要得到几个协助者，我们先不考虑\(A\)州，只\(O(n^2)\)处理与\(B\)州有关的\(dp\)，先选够\(B\)州，那么显然只需要在剩下的\(A、C\)州里选最小的几个作为\(A\)州即可。
代码
#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 = 520;
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; }
int n, m, k;
struct vote { int a, b; }; vote c[Z], d[Z];
inline bool cmp1(vote A, vote B) { return A.a == B.a ? A.b < B.b : A.a < B.a; }//按a排序
inline bool cmp2(vote A, vote B) { return A.b == B.b ? A.a < B.a : A.b < B.b; }//按b排序
double ans = 1e9, res;
double dp[Z][Z];
inline void init() { for (re i = 0; i <= n; i++) for (re j = 0; j <= n; j++) dp[i][j] = 1e9; }
sandom main()
{
n = read(), k = read();
for (re i = 1; i <= n; i++)
{
c[i].a = read(), c[i].b = read();
if (c[i].b == -1) c[i].b = 1e9;
}
sort(c + 1, c + 1 + n, cmp2);
for (re t = 0; t <= k; t++)//枚举选几个协助者
{
init(); dp[0][0] = 0;
for (re i = 1; i <= n; i++)//前i个州
for (re j = 0; j <= min(i, t); j++)//得到了j个协助者
{
dp[i][j] = dp[i - 1][j] + 1.0 * c[i].a / (t + 1);//不要协助者
if (j && c[i].b < 1e9) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1.0 * c[i].b / j);//得到协助者
}
for (re i = t; i <= k; i++)//已经不需要协助者，贪心选最小的A
{
for (re j = 1; j <= n; j++) d[j] = c[j];
sort(d + i + 1, d + n + 1, cmp1); res = 0;
for (re j = i + 1; j <= k; j++) res += 1.0 * d[j].a / (t + 1);
ans = min(ans, dp[i][t] + res);
}
}
printf("%.10lf\n", ans);
return 0;
}
T2.港口设施
我们把每一个集装箱覆盖的时间看做一个线段，那么当两个线段相交时，它们会产生矛盾，不能放在一个栈里，联想到关押罪犯。所以用扩展域并查集，当产生环时无解，否则因为各连通块之间相互独立，所以最后的答案就是\(2^{tot}\)（tot为连通块的数量）。这样建图是\(O(n^2)\)，显然不行，其实有一个问题，对于一个连通块内的点，我们建了很多没有用的边，为了判无解只需要保证其中最小的一个环存在即可，其他的如果已知在一个连通块里就不再考虑。
Talking is easy, but…code is not。首先按桶的顺序遍历，当遇到左端点就入栈，遇到右端点，意味着从左端点到现在的中间的线段与它有交叉，我们需要分别连边，并把这个点删除，但是发现这不是从栈中间删除了吗。所以考虑用链表维护（或者并查集）。但这个时间复杂度还是不行，我们考虑上述所说的，有很多边有必要连，但是对答案没有贡献。我们对于已可以确定颜色的点的连续集合，只和其中一个连边，这样就大大减少了连边数量。这个可以用一个数组\(jump\)来维护，表示下一个可能不同色的点——对于一些点，如果和同一条线段相交，说明同色，那么把他们看成一个点，更新\(jump\)，但是有一个细节，不能全部跳过，对于与它相交的线段，至少要连一个，这样才能保证正确性。
代码
#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 = 2e6 + 10; const int mod = 1e9 + 7;
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, ans = 1;
struct DSU
{
int dad[Z];
inline void init() { for (re i = 1; i <= m; i++) dad[i] = i; }
inline int find(int x) { return x == dad[x] ? x : dad[x] = find(dad[x]); }
inline bool un(int x, int y)
{
if (find(x) == find(y)) return false;
dad[find(x)] = find(y + n), dad[find(y)] = find(x + n);
return true;
}
}; DSU nxt, graph;
int id[Z], jmp[Z], stk[Z], top, in[Z];
bool vs[Z];
sandom main()
{
n = read(); m = n << 1;
for (re i = 1; i <= n; i++)
{
int a = read(), b = read();
id[a] = id[b] = i;//桶排
}
nxt.init(), graph.init();
for (re i = 1; i <= n; i++) jmp[i] = i + 1;
for (re i = 1; i <= m; i++)
{
int j = id[i];
if (!in[j]) stk[++top] = j, in[j] = top;//左端点
else//右端点
{
int u = in[j], k;
for (int v = nxt.find(u + 1); v <= top; v = k)//不断跳下一个需要连边的位置（从+1开始保证至少连一个）
{
if (!graph.un(j, stk[v])) { puts("0"); return 0; }
k = nxt.find(jmp[v]);//找到一下个需要连边的位置
jmp[v] = top + 1;//因为只需要保留最小的奇环（所以直接跳过）
}
nxt.dad[u] = u + 1;//把这个点删掉
}
}
int tot = 0;
for (re i = 1; i <= m; i++)
{
int j = graph.find(i);
if (!vs[j]) tot++, vs[j] = 1;
}
for (re i = tot / 2; i >= 1; i--) (ans *= 2) %= mod;
cout << ans << endl;
return 0;
}
T3.幽深府邸
\(O(n^2)\)暴力只需要以每个点为出发点不断向两边扩展。但是我们发现到一个性质：对于已经被扩展玩的点\(j\)，如果从\(i\)出发到达了\(j\)，那么\(i\)的覆盖范围要至少大于\(j\)，所以当我们走到已经被扩展过了的点时，直接取\(max\)，就不再走重复的路。我们的暴力是开了个桶记录每一把钥匙，其实没有必要，我们只需要维护两个东西：左边第一个能拿到开启此房间的钥匙的位置，右边第一个能拿到开启此房间的钥匙的位置，显然再远的也被包含在内。那么根据此就可以快速得知能否到达。虽然加入了优化，但这仍然是暴力，所以为了防止被卡，我们\(random_shuffle\)一下，跑的飞起。
代码
#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 = 5e5 + 100;
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, q, ans;
int c[Z], L[Z], R[Z];
vector <int> key[Z];
int pos[Z], l[Z], r[Z], p[Z];
bool sol[Z];
void solve(int i)
{
L[i] = R[i] = i; sol[i] = 1;
bool flag = 1;
while (flag)//还可以扩展
{
flag = 0;
while (r[L[i] - 1] >= L[i] && r[L[i] - 1] <= R[i])//扩展左边
{
L[i]--, flag = 1;
if (sol[L[i]]) L[i] = min(L[i], L[L[i]]), R[i] = max(R[i], R[L[i]]);
}
while (l[R[i] + 1] >= L[i] && l[R[i] + 1] <= R[i])//扩展右边
{
R[i]++, flag = 1;
if (sol[R[i]]) L[i] = min(L[i], L[R[i]]), R[i] = max(R[i], R[R[i]]);
}
}
}
sandom main()
{
n = read();
for (re i = 1; i < n; i++) c[i] = read();
for (re i = 1; i <= n; i++)
for (re j = read(); j > 0; j--) key[i].push_back(read());
for (re i = 0; i <= n; i++) pos[i] = 0;
for (re i = 1; i <= n; i++)
{
l[i] = pos[c[i - 1]];//i房间左边第一个可以到达自己的位置
for (re j = 0; j < key[i].size(); j++) pos[key[i][j]] = i;
}
for (re i = n; i >= 0; i--) pos[i] = n + 1;
for (re i = n; i >= 1; i--)
{
r[i] = pos[c[i]];//i房间右边第一个可以到达自己的位置
for (re j = 0; j < key[i].size(); j++) pos[key[i][j]] = i;
}
for (re i = 1; i <= n; i++) p[i] = i;
random_shuffle(p + 1, p + 1 + n);
for (re i = 1; i <= n; i++) solve(p[i]);
q = read();
while (q--)
{
int x = read(), y = read();
if (y >= L[x] && y <= R[x]) puts("YES");
else puts("NO");
}
return 0;
}
T4.长途巴士
蒟蒻、不会、鸽。
标签：int,re,while,freopen,getchar,CSP,模拟,define From： https://www.cnblogs.com/sandom/p/16735922.html