T1
洛谷 P9923 Przyciski
对于每个 \(\texttt{1}\)，将其所在行与列连边。最终构成的图显然是二分图。我们希望能在图中选出若干条边，使得原图的点集和选出的边构成的图中每个点度数的奇偶性都相同。以下将度数为奇数的称为奇数解，度数为偶数的称为偶数解。首先如果图中存在环，则一定存在偶数解：我们只需要把环上的所有边选上即可。否则整张图一定是一座森林。此时，由于叶子的存在，偶数解已是不可能。接下来我们只能尝试构造奇数解。首先所有叶子上面的边都必须选，然后叶子上一层的点 由于叶子的选择 其奇偶性会改变，只需要根据其当前的奇偶性来决定这个点上面的边要不要选。以此类推，可以构造出唯一的一组奇数解，如果构造不出就无解。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int n, m;
int head[1000005], nxt[1000005], to[1000005], ecnt = 1;
int rec[1000005];
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
bool vis[1000005];
int stk[1000005], sz;
int ans[1000005], acnt;
bool ban[1000005];
bool asdf[1000005];
bool fdsa[1000005];
int pre[1000005];
bool dfs(int x, int in) {
// cout << x << " x\n";
pre[x] = in;
if (vis[x]) {
int t;
do t = ans[++acnt] = stk[sz--];
while (t != x);
cout << "TAK\n";
cout << acnt << "\n";
for (int j = 1; j <= acnt; j++) asdf[ans[j]] = 1;
for (int j = 1; j <= acnt; j++) fdsa[pre[ans[j]]] = 1;
for (int j = 2; j <= ecnt; j += 2) {
if (asdf[to[j]] && asdf[to[j ^ 1]] && (fdsa[j] || fdsa[j ^ 1]))
cout << (j >> 1) << " ";
}
exit(0);
}
vis[x] = 1;
stk[++sz] = x;
for (int i = head[x]; i; i = nxt[i]) {
head[x] = i;
ban[i] = 1, ban[i ^ 1] = 1;
if ((i ^ in ^ 1)) {
if (dfs(to[i], i))
return 1;
}
}
--sz;
vis[x] = 0;
return 0;
}
bool cur[1000005];
void dfs2(int x, int fa) {
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa) {
dfs2(v, x);
if (!cur[v]) {
ans[++acnt] = (i >> 1);
cur[x] ^= 1;
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
add(u, v + n);
add(v + n, u);
}
memcpy(rec, head, sizeof head);
for (int i = 1; i <= n * 2; i++) dfs(i, 0);
acnt = 0;
memcpy(head, rec, sizeof head);
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n * 2; i++) {
if (!vis[i]) {
dfs2(i, 0);
if (!cur[i]) {
cout << "NIE\n";
return 0;
}
}
}
cout << "TAK\n";
cout << acnt << "\n";
sort(ans + 1, ans + acnt + 1);
for (int i = 1; i <= acnt; i++) cout << ans[i] << " ";
return 0;
}
T2
洛谷 P9925 Zapobiegliwy Student
设最多能选出 \(x\) 条不交线段，则答案为 \(x - 1\) 的构造是非常典的。只需要把所有点按右端点升序，然后顺序扫每条线段，维护当前选的最靠右的右端点，如果当前线段左端点大于当前维护的右端点，就选这条线段，然后更新右端点。最终只需要把其中一条线段拿出来当全相等的 \(v\)，剩下的全当 \(u\) 答案就是 \(x - 1\)。接下来只需要构造答案为 \(x\)。跟刚才类似，我们把所有线段按右端点升序，维护当前 \(u\) 集合的右端点和 \(v\) 集合的右端点和当前填到了第几组。如果这一组还没有 \(u\) 而且当前线段可以当这一组的 \(u\)，那就拿来当 \(u\)。对于 \(v\) 也同理。注意，判断是否能填进来时是和上一组的 \(u\) 和 \(v\) 的右段点比，然后对于填 \(u\) 的要求会更严。
代码
include
include
using namespace std;
int n;
struct node {
int l, r, id;
} a[500005];
int a1 = 0, a2 = 0;
int u[500005], v[500005];
int x[500005];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r, a[i].id = i;
sort(a + 1, a + n + 1, [](node a, node b) { return (a.r < b.r); });
for (int i = 1, r = 0; i <= n; i++) {
if (a[i].l >= r)
x[++a1] = a[i].id, r = a[i].r;
}
a2 = 1;
for (int i = 1, ur = 0, vr = 0, ut, vt; i <= n; i++) {
if (!u[a2] && a[i].l >= ur && a[i].l >= vr)
u[a2] = a[i].id, ut = a[i].r;
else if (!v[a2] && a[i].l >= ur)
v[a2] = a[i].id, vt = a[i].r;
if (u[a2] && v[a2])
++a2, ur = ut, vr = vt;
}
--a2;
if (a1 == a2) {
cout << a1 << "\n";
for (int i = 1; i <= a1; i++) cout << u[i] << " " << v[i] << "\n";
} else {
cout << a1 - 1 << "\n";
for (int i = 1; i < a1; i++) cout << x[i] << " " << x[a1] << "\n";
}
return 0;
}
T3
洛谷 P9924 Satelity
我没拼错，原题面就是 Satelity 而不是 Satellite。这就是波兰语带给我的自信。
做法大概是类似于划分等价类，对于每个集合里向另一个集合连边情况相同的点和这些点连向的另一个集合中的点都属于一个等价类，然后在每个连通块内二进制编号一类的。但是关于不向另一个集合连边构成的等价类，实现细节，正确性我还没有搞明白。先咕这。虽然大概率要是这么说的话后面就是不会补了
代码
你在期待什么？
行列之间连边。
经典贪心。
划分等价类。
标签：cout,int,线段,1000005,a2,端点,20240412 From： https://www.cnblogs.com/forgotmyhandle/p/18139163