A coin
题目大意 ： 给出每个人喜欢每个物品的概率，问期望满意人数的最大值
-
可以贪心的选可以增加期望最大的物品，用个堆就行
-
设f[k][c][n]表示前i个人c个k物品的期望，增加的期望就是f[k][c][n]-f[k][c-1][n]
-
转移的话就看这个人喜欢的是这个物品，或不是这个物品
Code
Show Code
#include <queue>
#include <vector>
#include <cstdio>
using namespace std;
const int N = 3005, M = 305;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
return x * f;
}
int n, m, s[M];
double p[N][M], ans;
vector<double> f[M][N];
priority_queue< pair<double, int> > q;
double F(int k, int c, int n) {
while (!p[n][k] && n) n--;
if (!c || !n) return 0.0;
if (f[k][c][n]) return f[k][c][n];
return f[k][c][n] = (1 + F(k, c - 1, n - 1)) * p[n][k] + F(k, c, n - 1) * (1 - p[n][k]);
}
int main() {
n = read(); m = read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
p[i][j] = read() / 1000.0;
for (int i = 1; i <= m; ++i) {
f[i][1].resize(n + 1);
q.push(make_pair(F(i, 1, n), i));
}
for (int i = 1; i <= n; ++i) {
int x = q.top().second; ans += q.top().first;
q.pop(); s[x]++;
f[x][s[x]+1].resize(n + 1);
q.push(make_pair(F(x, s[x] + 1, n) - F(x, s[x], n), x));
}
printf("%.10lf
", ans);
return 0;
}
B B
题目大意 ： n个点的树，断k条边再脸上k条边共会出现多少种树
-
先矩阵树定理再来个高斯消元，复杂度n4
-
还可以容斥，复杂度n2，不过没有写
Code
Show Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55, M = 998244353;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
return x * f;
}
bool v[N][N];
int a[N][N], b[N][N], n, m, ans;
int Pow(int a, int k = M - 2, int ans = 1) {
for (; k; k >>= 1, a = 1ll * a * a % M)
if (k & 1) ans = 1ll * ans * a % M;
return ans;
}
int Det(int n) {
int ans = 1;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n && !a[i][i]; ++j)
if (a[j][i]) swap(a[i], a[j]), ans = M - ans;
int inv = Pow(a[i][i]);
for (int j = i + 1; j <= n; ++j) {
if (!a[j][i]) continue;
int tmp = 1ll * a[j][i] * inv % M;
for (int k = i; k <= n; ++k)
if ((a[j][k] -= 1ll * a[i][k] * tmp % M) < 0) a[j][k] += M;
}
ans = 1ll * ans * a[i][i] % M;
}
return ans;
}
void Gs(int (*a)[N]) {
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n && !a[i][i]; ++j)
if (a[j][i]) swap(a[i], a[j]);
int inv = Pow(a[i][i]);
for (int j = i + 1; j <= n; ++j) {
if (!a[j][i]) continue;
int tmp = 1ll * a[j][i] * inv % M;
for (int k = i; k <= n + 1; ++k)
if ((a[j][k] -= 1ll * a[i][k] * tmp % M) < 0) a[j][k] += M;
}
}
for (int i = n; i >= 1; --i) {
int sum = 0;
for (int j = i + 1; j <= n; ++j)
sum = (sum + 1ll * a[i][j] * a[j][j]) % M;
a[i][i] = 1ll * (a[i][n+1] - sum + M) * Pow(a[i][i]) % M;
}
}
int main() {
#ifdef Shawk
freopen("in", "r", stdin);
#endif
n = read(); m = read();
for (int i = 2; i <= n; ++i) {
int x = read() + 1;
v[x][i] = v[i][x] = 1;
}
for (int k = 1; k <= n; ++k) {
memset(a, 0, sizeof(a));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j) continue;
int x = v[i][j] ? 1 : k;
if ((a[i][j] -= x) < 0) a[i][j] += M;
if ((a[i][i] += x) >= M) a[i][i] -= M;
}
}
b[k][1] = 1; b[k][n+1] = Det(n - 1);
for (int i = 2; i <= n; ++i)
b[k][i] = 1ll * b[k][i-1] * k % M;
//printf("%d %d
", k, b[k][n+1]);
}
Gs(b);
for (int i = 1; i <= m + 1; ++i)
if ((ans += b[i][i]) >= M) ans -= M;
printf("%d
", ans);
return 0;
}
C battery
题目大意 ： 炮台可以横着摆放，也可以竖着摆放，两端都可以发射激光。图中有反射镜，问怎样摆放才能让炮台达不到炮台并且每个空地都会被激光经过
-
很容易想到对炮台横竖摆放做2-sat，但是不好保证每个空地的都能被经过
-
我们再考虑，每个空地在横着或竖着不可能会被两个以上的炮台经过，因为这样如果想让这个空地被激光经过，这条激光一定会打到炮台
-
所以可以找到横竖两个方向经过空地的炮台，要求要空地必须有激光，如果炮台没有被经过，就无解;如果只被一个炮台经过，这个炮台强制选这个方向;
如果被两个炮台经过，那一个炮台换别的方向的时候另一个就得强制在这个方向 -
当然如果有炮台横竖都能打到炮台，也是无解
-
接下来2-sat就行了
Code
Show Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55, M = N * N * 2;
struct Edge {
int n, t;
}e[M];
int h[M], edc;
void Add(int x, int y) {
e[++edc] = (Edge) {h[x], y}; h[x] = edc;
}
bool g;
char s[N][N];
int n, m, c0, c1, id[N][N], stk[M], tp, b[M][2];
int dfn[M], dfc, low[M], c[M], cnt, px[M], py[M];
int dx[] = {0, 1, -1, 0}, dy[] = {1, 0, 0, -1};
//u2,d1,l3,r0
void Dfs(int x, int y, int k) {
while(g) {
x += dx[k], y += dy[k];
if (s[x][y] == '-') g = 0;
if (s[x][y] == '.') stk[++tp] = id[x][y];
if (s[x][y] == '#' || !s[x][y]) return;
if (s[x][y] == '\') k ^= 1;
if (s[x][y] == '/') k ^= 2;
}
}
void Tarjan(int x) {
dfn[x] = low[x] = ++dfc; stk[++tp] = x;
for (int i = h[x], y; i; i = e[i].n) {
if (!dfn[y=e[i].t]) Tarjan(y), low[x] = min(low[x], low[y]);
else if (!c[y]) low[x] = min(low[x], dfn[y]);
}
if (dfn[x] == low[x] && ++cnt) while (1) {
c[stk[tp]] = cnt;
if (stk[tp--] == x) break;
}
}
void Solve() {
scanf("%d%d", &n, &m);
memset(s[n+1] + 1, 0, m);
memset(b + 1, 0, c0 * 8);
memset(c + 1, 0, c1 * 8);
memset(h + 1, 0, c1 * 8);
memset(dfn + 1, 0, c1 * 8);
c0 = edc = dfc = cnt = 0; c1 = 1;
for (int i = 1; i <= n; ++i) {
scanf("%s", s[i] + 1);
for (int j = 1; j <= m; ++j) {
if (s[i][j] == '.') id[i][j] = ++c0;
if (s[i][j] == '|') s[i][j] = '-';
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s[i][j] != '-') continue;
c1++, px[c1] = i; py[c1] = j;
g = 1; Dfs(i, j, 0); Dfs(i, j, 3); bool tmp = g;
if (!g) tp = 0;
while (tp) (b[stk[tp]][0] ? b[stk[tp]][1] : b[stk[tp]][0]) = c1, tp--;
c1++;
g = 1; Dfs(i, j, 1); Dfs(i, j, 2);
if (!g) tp = 0;
while (tp) (b[stk[tp]][0] ? b[stk[tp]][1] : b[stk[tp]][0]) = c1, tp--;
if (!tmp && !g) return puts("IMPOSSIBLE"), void();
if (!tmp) Add(c1 - 1, c1);
if (!g) Add(c1, c1 - 1);
}
}
for (int i = 1; i <= c0; ++i) {
if (b[i][0] && b[i][1]) Add(b[i][0] ^ 1, b[i][1]), Add(b[i][1] ^ 1, b[i][0]);
else if (b[i][0]) Add(b[i][0] ^ 1, b[i][0]);
else return puts("IMPOSSIBLE"), void();
}
for (int i = 2; i <= c1; ++i)
if (!dfn[i]) Tarjan(i);
for (int i = 2; i <= c1; i += 2) {
if (c[i] == c[i+1]) return puts("IMPOSSIBLE"), void();
else if (c[i] > c[i+1]) s[px[i]][py[i]] = '|';
}
puts("POSSIBLE");
for (int i = 1; i <= n; ++i)
printf("%s
", s[i] + 1);
}
int main() {
int T; scanf("%d", &T);
while (T--) Solve();
return 0;
}