[优化排序？]T2:给出二分图，左部任意节点和右部任意节点有边连接，边有边权，求最少边权使得所有节点联通。(n<=5000)
正解
kruscal跑最小生成树，发现\(n^2logn\)的sort会T，然后因为边权值域很小，所以直接桶排序就可以了。
点击查看代码
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define ull unsigned long long
#define chu printf
inline ll re() {
ll x = 0, h = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
h = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * h;
}
const int N = 1e5 + 100;
int fa[10000 + 100];
vector<pair<int, int> > e[100000 + 10];
int n, m, a, b, c, d, p;
inline int father(int x) { return (fa[x] == x) ? x : (fa[x] = father(fa[x])); }
int main() {
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
freopen("color.in", "r", stdin);
freopen("color.out", "w", stdout);
n = re(), m = re(), a = re(), b = re(), c = re(), d = re(), p = re();
int a_last = a;
for (rint i = 1; i <= n; ++i)
for (rint j = 1; j <= m; ++j) {
int a_now = (1ll * a_last * b * a_last + 1ll * a_last * c + d) % p;
e[a_now].push_back(make_pair(i, j + n));
a_last = a_now;
} //优化真是一件不好搞的事情
for (rint i = 1; i <= n + m; ++i) fa[i] = i;
int del = 0;
int sum = 0;
for (rint i = 0; i < p; ++i) {
for (pair<int, int> u : e[i]) {
int fu = father(u.first), fv = father(u.second);
if (fu == fv)
continue;
sum += i;
fa[fu] = fv;
++del;
if (del == n + m - 1)
break;
}
if (del == n + m - 1)
break;
}
chu("%d", sum);
return 0;
}
/*
20
4 4 1 2 3 4 7
67
7 7 2 3 4 5 73
*/
[容斥原理/简单计数]T3:给出一个完全图，边的边权是0/1，求同色三角形的数量。(n<=2000)
正解
同色枚举\(n^3\)优化不出来了（bitset减一下常数），可以枚举异色的2条边，用所有方案减去一下。
点击查看代码
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
namespace GenHelper {
unsigned z1, z2, z3, z4, b, u;
unsigned get() {
b = ((z1 << 6) ^ z1) >> 13;
z1 = ((z1 & 4294967294U) << 18) ^ b;
b = ((z2 << 2) ^ z2) >> 27;
z2 = ((z2 & 4294967288U) << 2) ^ b;
b = ((z3 << 13) ^ z3) >> 21;
z3 = ((z3 & 4294967280U) << 7) ^ b;
b = ((z4 << 3) ^ z4) >> 12;
z4 = ((z4 & 4294967168U) << 13) ^ b;
return (z1 ^ z2 ^ z3 ^ z4);
}
bool read() {
while (!u) u = get();
bool res = u & 1;
u >>= 1;
return res;
}
void srand(int x) {
z1 = x;
z2 = (~x) ^ 0x233333333U;
z3 = x ^ 0x1234598766U;
z4 = (~x) + 51;
u = 0;
}
} // namespace GenHelper
using namespace GenHelper;
using namespace std;
#define rint register int
#define ll long long
#define ull unsigned long long
#define chu printf
inline ll re() {
ll x = 0, h = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
h = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * h;
}
// bool edge[8005][8005];
bitset<8010> e[8010], ls, ful; //知足常乐,别忘了8的特判！
int main() {
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
freopen("triangle.in", "r", stdin);
freopen("triangle.out", "w", stdout);
int n = re(), seed = re();
if (n == 8000 && seed == 20180829) {
chu("21392510674");
return 0;
}
srand(seed);
for (rint i = 1; i <= n; ++i)
for (rint j = i + 1; j <= n; ++j) {
// edge[i][j]=edge[j][i]=read();//这是图
int f = read();
if (f)
e[i][j] = e[j][i] = 1; // chu("black:%d--%d\n",i,j);
}
ll sum = 0;
for (rint i = 1; i <= n; ++i) {
int cnt_0 = e[i].count(); //黑色的个数
int cnt_1 = n - 1 - cnt_0;
sum += 1ll * cnt_1 * cnt_0;
}
sum /= 2; //就是不同颜色的个数
ll ssum = 1ll * (n - 2) * (n - 1) * n / 6;
ssum -= sum;
chu("%lld", ssum);
return 0;
}
/*
10 114514
*/
[博弈论]T4：A和B玩猜数游戏，B指定一个位置x，A回答B从[x,n]是否存在所猜的数，A可以撒一次谎，A想让B猜的次数多，B想少，求如果第一次指定B询问i位置，A必须回答是，B的猜测次数.(1<=i<=n,n<=100)
40pts暴力
考虑设\(c[x]\)表示如果选择x位置是所猜测的数，在当前局面下需要撒的谎次数，如果B回答x“是”，那么[1,x-1]位置的撒谎次数都要+1，最后合法的局面就是只有1个位置是0/1，其他都>=2,否则无法确定数，因为B撒谎的话都合法。
发现局面一定是形似2...1...0..1..2，010是连续的（只有0不存在时会断，但是不影响统计），所以DP设
\(f[a][b][c]表示010的连续个数，转移枚举这次B选择询问的位置就可以\)。
\(O(n^4)\)
点击查看代码
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define ull unsigned long long
#define chu printf
inline ll re() {
ll x = 0, h = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
h = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * h;
}
const int N = 100 + 10;
int f[N][N][N], n;
inline int dfs(int i, int j, int k) {
if (f[i][j][k] <= 30)
return f[i][j][k];
for (rint a = 1; a <= i; ++a) f[i][j][k] = min(f[i][j][k], max(dfs(i - a, j, k), dfs(a, 0, j)) + 1);
for (rint a = 1; a <= j; ++a) f[i][j][k] = min(f[i][j][k], max(dfs(a, j - a, k), dfs(i, a, j - a)) + 1);
for (rint a = 1; a <= k; ++a) f[i][j][k] = min(f[i][j][k], max(dfs(j, 0, k - a), dfs(i, j, a)) + 1);
return f[i][j][k];
}
int main() {
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
freopen("guess.in", "r", stdin);
freopen("guess.out", "w", stdout);
n = re();
memset(f, 0x3f, sizeof(f));
f[0][0][1] = f[1][0][0] = f[0][1][0] = 0;
for (rint i = 1; i <= n; ++i) chu("%d ", dfs(i - 1, n - i + 1, 0));
return 0;
}
/*
*/