Solved:2
Rank:136
A Eddy Walker
题意:T个场景 每个场景是一个长度为n的环 从0开始 每次要么向前走要么向后走 求恰好第一次到m点且其他点都到过的概率
每次的答案是前缀概率积
题解:m=0的时候 只有n=1的时候是1 否则是0 然后感性的理解到其他n-1点的概率是一样的 所以每个点的概率是1/(n-1)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll pow_mod(ll x, ll y) { ll res = 1; while(y) { if(y & 1) res = res * x % mod; x = x * x % mod; y >>= 1; } return res; } int main() { ll ans = 1; int T; scanf("%d", &T); while(T--) { ll n, m; scanf("%lld%lld", &n, &m); if(n == 1 && m == 0) { printf("%lld ", ans); continue; } if(m == 0) ans = 0; else ans = ans * pow_mod(n - 1, mod - 2) % mod; printf("%lld ", ans); } return 0; }
D Kth Minimum Clique
题意:100个点的图 输出点权第k小的团
题解:考虑把点一个一个插入进去 用优先队列维护团的大小
每次取出最小的团 然后判断一下可以把哪个点放进来继续是团 用bitset维护
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, k, cnt; int val[105]; char tu[105][105]; struct node { int pos; ll sum; bitset<105> bt; friend bool operator < (node A, node B) { return A.sum > B.sum; } }; bitset<105> btt[105]; int main() { cnt = 0; scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++) scanf("%d", &val[i]); for(int i = 1; i <= n; i++) { scanf("%s", tu[i] + 1); for(int j = 1; j <= n; j++) if(tu[i][j] == '1') btt[i][j] = 1; } if(k == 1) { puts("0"); return 0; } k--; priority_queue<node> que; for(int i = 1; i <= n; i++) que.push((node){i, 1LL * val[i], btt[i]}); while(!que.empty()) { node t = que.top(); que.pop(); k--; if(k == 0) { printf("%lld ", t.sum); return 0; } for(int i = t.pos + 1; i <= n; i++) if(t.bt[i]) que.push((node){i, t.sum + 1LL * val[i], t.bt & btt[i]}); } puts("-1"); return 0; }
E MASE
题意:给一个N x M的01矩阵(M <= 10) 1表示墙 每个点可以往左右下走
一个修改操作 把之前矩阵中某个位置的数取反
一个查询操作 查询从第一行的一个位置走到第n行一个位置的方案数
题解:做的第一道动态DP的题 由于一些奇特的性质
DP的转移可以用矩阵表示 矩阵乘法有结合率 线段树可以维护矩阵的区间积
然后就这样了....
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; int n, m, t; char s[100005][12]; struct martix { ll c[10][10]; }sum[400005]; martix mul(martix x, martix y) { martix res; for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) res.c[i][j] = 0; for(int i = 0; i < m; i++) for(int k = 0; k < m; k++) for(int j = 0; j < m; j++) res.c[i][j] = (res.c[i][j] + x.c[i][k] * y.c[k][j] % mod) % mod; return res; } martix fun(char a[12]) { martix res; for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) res.c[i][j] = 0; for(int i = 0; i < m; i++) { if(a[i] == '0') { int l = i, r = i; while(l - 1 >= 0 && a[l - 1] == '0') l--; while(r + 1 < m && a[r + 1] == '0') r++; for(int j = l; j <= r; j++) res.c[i][j] = 1; } } return res; } void pushup(int rt) { sum[rt] = mul(sum[rt << 1], sum[rt << 1 | 1]); } void build(int l, int r, int rt) { if(l == r) { sum[rt] = fun(s[l]); return; } int m = l + r >> 1; build(l, m, rt << 1); build(m + 1, r, rt << 1 | 1); pushup(rt); } void update(int k, int l, int r, int rt) { if(l == r) { sum[rt] = fun(s[k]); return; } int m = l + r >> 1; if(k <= m) update(k, l, m, rt << 1); else update(k, m + 1, r, rt << 1 | 1); pushup(rt); } int main() { scanf("%d%d%d", &n, &m, &t); for(int i = 1; i <= n; i++) { scanf("%s", s[i]); } build(1, n, 1); while(t--) { int opt, a, b; scanf("%d%d%d", &opt, &a, &b); if(opt == 1) { if(s[a][b - 1] == '0') s[a][b - 1] = '1'; else s[a][b - 1] = '0'; update(a, 1, n, 1); } else if(opt == 2) { printf("%lld ", sum[1].c[a - 1][b - 1]); } } return 0; }
F Partition problem
签到题
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll ans; int n; ll q[30][30]; ll sum[30]; int id[30]; void dfs(int now, int tot, ll val) { if(tot == n) { ans = max(ans, val); return; } if(now > n * 2) return; for(int i = now; i <= n * 2; i++) { ll tmp = val + sum[i]; for(int j = 1; j <= tot; j++) tmp -= q[i][id[j]] * 2LL; tot++; id[tot] = i; dfs(i + 1, tot, tmp); tot--; } return; } int main() { ans = 0; scanf("%d", &n); for(int i = 1; i <= n * 2; i++) { for(int j = 1; j <= n * 2; j++) { scanf("%lld", &q[i][j]); sum[i] += q[i][j]; } } dfs(1, 0, 0); printf("%lld ", ans); return 0; }