T1
Topcoder SRM 579 div1 Medium - TravellingPurchasingMan
发现行动肯定是从当前点沿最短路走到目标然后等开门然后买然后去下一个目标。所以先对每个关键点为原点跑一遍最短路，然后状压一下，\(dp[S][i]\) 表示已经买了 \(S\) 集合，当前在 \(S\) 中的 \(i\)。转移就枚举目的地，看过去之后能不能赶上开门，赶得上就买，否则不管。
代码
#include <iostream>
#include <queue>
#define int long long
using namespace std;
const int inf = 2147483647;
int n, m, K;
int dist[20][55];
struct node {
int x, dis;
};
bool operator<(node a, node b) { return a.dis > b.dis; }
priority_queue<node> q;
int head[55], nxt[105], to[105], ew[105], ecnt;
void add(int u, int v, int ww) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, ew[ecnt] = ww; }
bool vis[55];
void dijkstra(int id, int S) {
for (int i = 1; i <= n; i++) dist[id][i] = inf, vis[i] = 0;
dist[id][S] = 0;
q.push((node) { S, 0 });
while (!q.empty()) {
node tmp = q.top();
q.pop();
int x = tmp.x;
if (vis[x])
continue;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (dist[id][v] > dist[id][x] + ew[i])
q.push((node) { v, dist[id][v] = dist[id][x] + ew[i] });
}
}
}
int dp[70005][20];
int Count(int x) {
int ret = 0;
while (x) ret += (x & 1), x >>= 1;
return ret;
}
int st[55], ed[55], tm[55];
signed main() {
cin >> n >> K;
for (int i = 1; i <= K; i++) cin >> st[i] >> ed[i] >> tm[i];
cin >> m;
for (int i = 1; i <= m; i++) {
int u, v, ww;
cin >> u >> v >> ww;
++u, ++v;
add(u, v, ww);
add(v, u, ww);
}
for (int i = 1; i <= K; i++) dijkstra(i, i);
dijkstra(0, n);
for (int i = 0; i <= (1 << K); i++) {
for (int j = 0; j <= K; j++)
dp[i][j] = inf;
}
int ans = 0;
for (int i = 1; i <= K; i++) dp[1 << (i - 1)][i] = (dist[0][i] <= ed[i] ? max(st[i], dist[0][i]) + tm[i] : inf);
for (int i = 1; i < (1 << K); i++) {
for (int j = 1; j <= K; j++) {
if ((i & (1 << (j - 1))) == 0 || dp[i][j] >= inf)
continue;
ans = max(ans, Count(i));
for (int k = 1; k <= K; k++){
if (i & (1 << (k - 1)))
continue;
int tmp = dp[i][j] + dist[j][k];
if (tmp <= ed[k])
dp[i | (1 << (k - 1))][k] = min(dp[i | (1 << (k - 1))][k], max(tmp, st[k]) + tm[k]);
}
}
}
cout << ans << "\n";
return 0;
}
T2
Topcoder SRM 643 div1 Medium - TheKingsArmyDiv1
先不管上下相同的列。把剩下的东西分段，每段内列都相同，相邻段不同，如果只分了一段，肯定一次搞定。分了两段就是两次。分了超过两端之后，一定可以通过一次操作将段数减少 \(2\)。所以操作次数 \(f(x) = f(x - 2) + 1, f(1) = 1, f(2) = 2\)。可以发现实际上 \(f(x) = \lceil \frac{x}{2} \rceil\)。然后考虑上下相同的列。这样的列并不影响我们操作上下不同的列，而且只有全 \(\texttt{S}\) 的列会增加一个代价。所以只需要分出段数然后数全 \(\texttt{S}\) 的列有多少即可。
代码
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
string a, b;
cin >> a >> b;
n = a.size();
int cs = 0, ch = 0, cd = 0;
int lst = -1;
for (int i = 0; i < n; i++) {
if (a[i] == 'H' && b[i] == 'H')
++ch;
else if (a[i] == 'S' && b[i] == 'S')
++cs;
else {
cd += (lst != -1 && (lst != (a[i] == 'H')));
lst = (a[i] == 'H');
}
}
if (ch == n)
cout << 0 << "\n";
else if (cs == n)
cout << "-1\n";
else if (cs + ch == n)
cout << cs << "\n";
else
cout << (cd + 1) / 2 + 1 + cs << "\n";
return 0;
}
T3
Topcoder SRM 571 div1 Medium - MagicMolecule
要求一个最大团，可以在补图上求一个最大独立集，转化成 \(n - 最小点覆盖\)。然后直接搜每条边，如果当前边还没有被覆盖，就任选一个端点加入点覆盖，然后分别递归下去。否则直接递归下去。搜到最后就更新一下答案。注意这里选的点的个数是有限制的，最多只能选 \(n - \lceil \frac{n}{3} \rceil\) 个点。注意到搜索只有在任选一个点加入点覆盖之后才会产生一个分支，而点覆盖最多只有 \(16\) 个点，所以分支只有 \(2^{16}\) 个。所以复杂度就是没有问题的。
代码
#include <iostream>
#define int long long
using namespace std;
int n;
int u[2505], v[2505];
int a[55];
int ecnt;
int ans = -1;
bool c[55];
void dfs(int x, int k) {
if (x == ecnt + 1) {
int tmp = 0;
for (int i = 1; i <= n; i++) tmp += (!c[i] ? a[i] : 0);
ans = max(ans, tmp);
return;
}
if (c[u[x]] || c[v[x]])
dfs(x + 1, k);
else if (k) {
c[u[x]] = 1;
dfs(x + 1, k - 1);
c[u[x]] = 0, c[v[x]] = 1;
dfs(x + 1, k - 1);
c[v[x]] = 0;
}
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> n;
for (int i = 1; i <= n; i++) {
string str;
cin >> str;
str = ' ' + str;
for (int j = i + 1; j <= n; j++) {
if (str[j] == 'N')
u[++ecnt] = i, v[ecnt] = j;
}
}
dfs(1, n - (2 * n + 2) / 3);
cout << ans << "\n";
return 0;
}
T4
Topcoder SRM 581 div1 Hard - YetAnotherBoardGame
枚举第一行执行什么操作，枚举对哪些列执行这个操作，然后往下走。对于当前行的上一行中所有白点所在列，这一行必须在这些列上进行操作。然后就可以根据这些列上的限制判断是无解还是进行哪种操作或是两种都行。然后返回无解或者搜下去。别忘了给列加限制。复杂度应为 \(\mathcal{o}(3^n)\)，因为每一列要么在第一行被确定，要么在之后的搜索中确定为操作 \(1\)，要么被确定为操作 \(2\)，这样相当于枚举子集的子集。
代码
#include <iostream>
#include <string.h>
#define int long long
using namespace std;
const int inf = 2147483647;
int n, m;
int a[15][15];
int A[15][15];
int res[15];
inline void f1(int x, int y) {
a[x - 1][y] ^= 1, a[x][y] ^= 1, a[x + 1][y] ^= 1;
a[x][y - 1] ^= 1, a[x][y + 1] ^= 1;
}
inline void f2(int x, int y) {
a[x - 1][y] ^= 1, a[x + 1][y] ^= 1;
a[x][y - 1] ^= 1, a[x][y + 1] ^= 1;
}
int p[15][15];
int rrr[15][15];
int dfs(int x) {
if (x == n + 1) {
for (int i = 1; i <= m; i++) {
if (a[x - 1][i] == 0)
return inf;
}
return 0;
}
p[x][0] = 0;
int ot = 0;
for (int i = 1; i <= m; i++) {
if (a[x - 1][i] == 0) {
p[x][++p[x][0]] = i;
if (ot != 0 && ot != res[i] && res[i] != 0)
return inf;
ot = max(ot, res[i]);
}
}
int r1 = inf, r2 = inf;
for (int i = 1; i <= p[x][0]; i++) f1(x, p[x][i]), rrr[x][p[x][i]] = res[p[x][i]], res[p[x][i]] = 1;
if (ot != 2)
r1 = p[x][0] + dfs(x + 1);
for (int i = 1; i <= p[x][0]; i++) a[x][p[x][i]] ^= 1, res[p[x][i]] = 2;
if (ot != 1)
r2 = p[x][0] + dfs(x + 1);
for (int i = 1; i <= p[x][0]; i++) f2(x, p[x][i]), res[p[x][i]] = rrr[x][p[x][i]];
return min(r1, r2);
}
int cnt[100005];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
string str;
cin >> str;
m = str.size();
str = ' ' + str;
for (int j = 1; j <= m; j++) A[i][j] = (str[j] == 'B');
}
int ans = inf;
cnt[0] = -1;
for (int i = 0; i < (1 << m); i++) {
cnt[i] = cnt[i - (i & (-i))] + 1;
memcpy(a, A, sizeof A);
for (int j = 0; j < m; j++) {
if (i & (1 << j))
f1(1, j + 1), res[j + 1] = 1;
}
ans = min(ans, dfs(2) + cnt[i]);
memcpy(a, A, sizeof A);
for (int j = 0; j < m; j++) {
if (i & (1 << j))
f2(1, j + 1), res[j + 1] = 2;
}
ans = min(ans, dfs(2) + cnt[i]);
for (int j = 1; j <= m; j++) res[j] = 0;
}
cout << (ans == inf ? -1 : ans) << "\n";
return 0;
}
T5
Topcoder 538 div1 Hard SkewedPerspective
后面再说。
代码
后面再说。
以每个关键点为源点跑最短路，然后状压关键点的套路。
从特殊情况开始考虑。
爆搜出奇迹。
标签：15,int,ecnt,55,str,include,20240415 From： https://www.cnblogs.com/forgotmyhandle/p/18144238