这次，很失败，知识点都学过，打不出来。
A
找规律，很简单，也是我唯一做过的题。
每次是2的幂时，它就会加一。
复杂度是 log \log log 级别的。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int s[1001];
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
if (n == 1) cout << 0;
else {
int res = 1, c = 2, ans = 0;
while (res * 2 < n) {
ans += res * c;
res *= 2;
c++;
}
cout << ans + c * (n - res);
}
}
B
并查集，没想到。
合并是朋友的两个点。
最后统计每一个完全连通分量的大小，即其边数，这些边所连接的点就是
z
z
z。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
int n, m, ans;
int fa[maxn], s[maxn];
int find(int x) {return (x == fa[x] ? x : fa[x] = find(fa[x]));}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n>> m;
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int i = 1, x, y; i <= m; ++i) {
cin >> x >> y;
int fx = find(x), fy = find(y);
fa[fx] = fy;
}
for (int i = 1; i <= n; ++i) s[find(i)] ++;
for (int i = 1; i <= n; ++i) if (s[i]) ans += s[i] * (s[i] - 1) / 2;
cout << ans - m << '\n';
}
C
状压 d p dp dp，可以说是炮兵阵地的简化版。一个十字中只有一只奶牛。
状压 d p dp dp 需要注意：将原来的状态转化为每一行一个只包括 1 , 0 1,0 1,0 数字表示状态，判断上下左右是否有牛（check）。详情见代码。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 10, mod = 1e8;
// 没有相邻草地即一个十字只有一只奶牛
int n, m, ans;
int f[13][maxn];
// f[i][j] 表示第 i 行状态为 j 的方案数
int a[13];
int ck(int x, int y){// 判断上下左右是否有奶牛
if((x & a[y]) != x) return 0;
if((x & (x << 1))) return 0;
return 1;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1, x; j <= m; ++j) {
cin >> x;
a[i] = a[i] * 2 + x;
}
for (int i = 0; i < (1 << m); ++i) if(ck(i, 1)) f[1][i] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < (1 << m); ++j) { // 枚举这一行的状态
if (!ck(j, i)) continue;
for (int k = 0; k < (1 << m); ++k) { // 上一行的状态
if (!ck(k, i - 1)) continue;
if (j & k) continue;
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
}
}
}
for (int i = 0; i < (1 << m); ++i) ans = (ans + f[n][i]) % mod;
cout << ans << '\n';
}
D
分层图，跑最短路。主要是想到分层图不太容易。
当起始两点都在第 i i i 层上时，表示已经使用了 i i i 条免费道路，并且当前道路不是免费道路。
若起始点在第 i i i 层且终点在第 i + 1 i+1 i+1 层上时，表示已经使用了 i i i 条免费道路，并且当前道路是免费道路。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
int n, m, k;
struct node {int v, w;};
vector<node> e[maxn];
void add(int u, int v, int w) {e[u].push_back({v, w});}
struct edge {
int to, dis;
bool operator < (const edge &o) const {return dis > o.dis;}
};
int dis[maxn];
bool vis[maxn];
void dijkstra(int s) {
memset(dis, 0x3f, sizeof dis);
priority_queue<edge> q;
q.push({s, 0});
dis[s] = 0;
while (!q.empty()) {
int u = q.top().to;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto ed: e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({v, dis[v]});
}
}
}
}
signed main() {
cin >> n >> m >> k;
for (int i = 1, u, v, w; i <= m; ++i) {
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
for (int j = 1; j <= k; ++j) {
add(u + j * n, v + j * n, w);
add(v + j * n, u + j * n, w);
add(u + (j - 1) * n, v + j * n, 0);
add(v + (j - 1) * n, u + j * n, 0);
}
}
dijkstra(1);
int ans = dis[n];
for (int i = 1; i <= k; ++i) {
ans = min(ans, dis[i * n + n]);
}
cout << ans << '\n';
}