B（建图技巧+最小生成树）
题目链接
⭐⭐⭐
题目：
给定一个\(n\times m\)的网格，每个格点对应有权值\(w(i,j)\)。初始时所有格点均为白色，一个格点被染成黑色需要花费对应的权值，且如果不都在一条直线的三个点均已染色，则他们所确定的矩形对应的第四个顶点，免费染色。现要将所有格点染成黑色，问最小花费
解析：
根据所对应的免费染色的规则，可以将问题进行转换。构造一个图，其中每个点对应为坐标轴上的点，边权为端点对应的坐标轴上的点组合所确定的格点的权值，所有格点染成黑色即任意两个点都可达（满足传递性）。那么只需要求这幅图中的最小生成树即可，跑一遍prim算法
#include<bits/stdc++.h>
using namespace std;
int n, m, a, b, c, d, p;
const int maxn = 1e4 + 5;
long long w[5000*5000+5];
long long dis[maxn];
int main() {
scanf("%d%d%d%d%d%d%d", &n, &m, &a, &b, &c, &d, &p);
long long t = a;
for (int i = 0; i < n * m; ++i)
w[i] = t = (t * t * b + t * c + d) % p;
memset(dis, 0x3f, sizeof(dis));
dis[0] = 0;
long long ans = 0;
for (int _ = 0; _ < n + m; ++_) {
int mn = -1;
for (int i = 0; i < n + m; i++)
if (~dis[i] && (mn < 0 || dis[i] < dis[mn]))
mn = i;
ans += dis[mn];
dis[mn] = -1;
if (mn < n)
for (int i = 0; i < m; ++i)
dis[n + i] = min(dis[n + i], w[m * mn + i]);
else
for (int i = 0; i < n; ++i)
dis[i] = min(dis[i], w[m * i + mn - n]);
}
printf("%lld", ans);
}
C（建图技巧+二分图匹配）
题目链接
⭐⭐⭐⭐
题目：
给出一个\(n\times n\)的网格，其中有\(m\)个点存在数字，给出每一行以及每一列的最大值，以及所有数字的上限\(k\)，求出构造这样的网格中所有数字和的最小值
解析：
考虑对于每一行与每一列的限定值的最大值，假如记为\(x\)，这个\(x\)必须存在于对应的行和列中，记对应的行数为\(r\)，列数为\(c\)，则最差情况下需要\((r+c)\)个\(x\)去填充。但是由于这是一个二维网格，在满足行（列）的过程中，对应的列（行）也得到了满足，这样就可以减少需要填充的\(x\)的数量
考虑到指定位置上才可以填数字，可以将问题抽象成一个由对应行以及对应列作为点，所确定的格点可以填充数字作为边的一个二分图，求他的最大匹配\(match\)，\((r+x-match)x\)即为\(x\)对答案的贡献，而后再继续计算更小的限定值的贡献，累加入答案即可
#include<bits/stdc++.h>
using namespace std;
int n, m, k;
bool nodes[2005 * 2005];
vector<int> c, r;
namespace Hungary
{
//修改顶点数
const int MAX_V = 4005;
int V;
vector<int> G[MAX_V];
int match[MAX_V];
bool used[MAX_V];
void add_edge(int u, int v)
{
G[u].push_back(v);
G[v].push_back(u);
}
bool dfs(int v)
{
used[v] = true;
for (auto& i : G[v])
if (match[i] < 0 || !used[match[i]] && dfs(match[i]))
{
match[v] = i;
match[i] = v;
return true;
}
return false;
}
int bipartite_matching()
{
int res = 0;
memset(match, -1, sizeof(match));
for (auto& v : c)
if (match[v] < 0)
{
memset(used, 0, sizeof(used));
if (dfs(v))
++res;
}
return res;
}
}
int main() {
int sc;
int x, y;
scanf("%d%d%d", &n, &m, &k);
vector<pair<int, int>> v(2 * n);
for (int i = 0; i < 2 * n; ++i)
scanf("%d", &sc), v[i] = { sc,i };
sort(v.begin(), v.end(), greater<pair<int, int>>());
while (m--)
scanf("%d%d", &x, &y), nodes[--x * n + --y] = true;
int p = 0;
long long ans = 0;
while (p < v.size()) {
c.clear(), r.clear();
bool ne = true;
while (p < v.size() && (ne || v[p].first == v[p - 1].first)) {
if (v[p].second < n)
r.push_back(v[p].second);
else
c.push_back(v[p].second);
ne = false;
++p;
}
long long x = v[p - 1].first;
for (auto& i : r)
for (auto& j : c)
if (nodes[i * n + j - n]) {
nodes[i * n + j - n] = false;
Hungary::add_edge(i, j);
}
ans += (c.size() + r.size() - Hungary::bipartite_matching()) * x;
for (auto& i : r)
Hungary::G[i].clear();
for (auto& i : c)
Hungary::G[i].clear();
}
printf("%lld", ans);
}
E（数学推导or打表找规律）
题目链接
⭐⭐⭐
题目：
指定\(n\)，求出满足\(xy+1|x^2+y^2\wedge1\le x\le y\le n\)的\((x,y)\)数目
解析：
给定式进行转换为\(y^2-kxy+x^2-k\)，如果给定一组合法解\((x,y_1)\)，且\(x\)固定进而得到\(y_1+y_2=kx,y_1y_2=x^2-k\)，便可以获得另一个合法解\(y_2=kx-y_1\)，通过上述韦达定理也可以知晓\(y_1\ge x\ge y_2\ge0\)，且两解对应的\(k\)值相同，当\(y_2=0\)时，对应的\((x,y)\)也是\(k\)对应的最小解，此时将\(y=kx\)代入原方程，解得\(k=x^2\)，最小解形如\((a,a^3)\)
可以枚举不同的最小解，并通过上述的\((x,y)\rightarrow(kx-y,x)\)进行反向推导，也就是\((y',ky'-x')\leftarrow(x',y')\)，再进行归纳可以发现对于任意一个\(k^2\)有一个对应的数列\(a\)，其中\(a[n]=k^2\times a[n-1]-a[n-2],a[0]=k,a[1]=k^3\)，且\((a[n-1],a[n]])\)构成一组合法解（也可以通过打表发现）
这样只需要找出所有的数列\(a\)，二分答案即可
注意：
- 由于\(n\in[1,10^{18}]\)，所以\(k\)的枚举范围为\([1,10^6]\)
- 由于计算过程可能爆精度，所以需要先进行除法运算判断是否上溢
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 1;
const long long MAX = 1e18;
vector<long long> v;
int main() {
v.push_back(1);
for (int i = 2; i < maxn; ++i) {
long long last = i;
long long now = 1ll * i * i * i;
long long t;
do {
v.push_back(now);
t = now;
if (MAX / now < i || MAX / now / i < i) break;
now = now * i * i - last;
last = t;
} while (now < MAX);
}
sort(v.begin(), v.end());
int T;
long long n;
scanf("%d", &T);
while (T--) {
scanf("%lld", &n);
printf("%d\n", upper_bound(v.begin(), v.end(), n) - v.begin());
}
}
F（爆搜模拟）
题目链接
⭐⭐⭐
题目：
给出\(n\)张牌，每张牌大小\(1\sim13\)，先要给出凑成\(m\)的方案，且保证所有可能得到答案的方法中计算过程中均出现分数运算
解析：
直接进行暴力搜索即可，枚举出所有牌的可能性后，对这副牌进行搜索，用\(vis\)数组标记牌是否被使用过，并且用\(f\)标记当前搜索过程中拥有的牌计算结果是否含有分数，\(flag[0]\)标记是否搜索过程中出现不含有分数的可行方案，\(flag[1]\)代表是否出现可行方案
#include<bits/stdc++.h>
using namespace std;
map<int, map<double, int>> dp;
vector<double> v(4);
bool vis[4];
int n, m;
bool flag[2]; //0 代表无整数出现下得到m，1 代表得到m
const double eps = 1e-9;
vector<vector<double>> ans;
void dfs(int x, bool f) {
if (x == n) {
if (fabs(v[0] - m) < eps) {
flag[1] = true;
if (!f) flag[0] = true;
}
return;
}
for (int i = 0; i < n; ++i) if (fabs(floor(v[i]) - v[i]) > eps) f = true;
for (int i = 0; i < n; ++i) {
if (vis[i]) continue;
for (int j = i + 1; j < n; ++j) {
if (vis[j]) continue;
double t1 = v[i], t2 = v[j];
vis[j] = true;
v[i] = t1 + t2, dfs(x + 1, f);
v[i] = t1 * t2, dfs(x + 1, f);
v[i] = t1 - t2, dfs(x + 1, f);
v[i] = t2 - t1, dfs(x + 1, f);
if (fabs(t2 > eps)) v[i] = t1 / t2, dfs(x + 1, f);
if (fabs(t1 > eps)) v[i] = t2 / t1, dfs(x + 1, f);
vis[j] = false;
v[i] = t1, v[j] = t2;
}
}
}
void get_permu(int x, int last) {
if (x == n) {
flag[0] = flag[1] = false;
dfs(1, false);
if (!flag[0] && flag[1])
ans.push_back(v);
return;
}
for (int i = last; i <= 13; ++i) {
v[x] = i;
get_permu(x + 1, i);
}
}
int main() {
scanf("%d%d", &n, &m);
if (n < 3) printf("0");
else {
get_permu(0, 1);
printf("%d\n", ans.size());
for (auto& i : ans) {
for (auto& j : i)
printf("%d ", (int)j);
printf("\n");
}
}
}
J（思维）
题目链接
⭐⭐⭐
题目：
给出\(n\)个点之间的边，\(0\)代表白边，\(1\)代表黑边，问图中有多少个三角形构成他的三条边颜色相同
解析：
考虑问题的反面，用所有三角形的组成情况减去不可以构成三条边颜色相同的情况，那这样也就只有两黑一白和两白一黑两种可能，对于这样的情况下，有两个角构成他们的两条边是不一样的，因此可以计算每个点对应的黑白边的条数，考虑匹配出这样的异边角的个数，最后总个数除以2即为不满足条件的三角形个数（不满足条件的三角形恰有两个异边角）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 8005;
int du[maxn];
int edge[maxn][maxn];
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;
}
}
using namespace GenHelper;
int main()
{
int n, seed;
scanf("%d%d", &n, &seed);
srand(seed);
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
edge[j][i] = edge[i][j] = read();
if (edge[i][j] == 1)
{
du[i]++;
du[j]++;
}
}
}
ll ans = (1ll) * n * (n - 1) * (n - 2) / 6;
ll sum = 0;
for (int i = 1; i <= n; i++)
sum += 1ll * du[i] * (n - 1 - du[i]);
ans = ans - sum / 2;
printf("%lld\n", ans);
}