CSP-S2周末刷题班（第一场）
http://csp.ac/contest/44
发现这个比赛自己死亡鸽者了....
另外打的确实很死亡...QAQ
全都会,但是挂挂挂
A
哈希写错了,人没了
连续两次哈希写炸了,上次我双模哈希也炸裂了
死因1,bas取得贼大,然后*bas直接没用longlong自然溢出
只能告诉我们以后哈希用longlong
死因2.负数直接上没有+P变成P-
我.....以后哈希一定要取模上心啊啊啊!!!!!!!
做法 : 直接处理每一行每一列的哈希值,然后单点删除即可,使用map记录哈希值
另外记一下:哈希查询一次冲突概率为1/mod
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define pii pair
#define mkp(x,y) (make_pair(x,y))
const int B1 = 101;
const ll P1 = 1e9 + 7;
const ll P2 = 1e9 + 9;
const int MAXN = 3007;
const int B2 = 132;
int n, m, q;
char s[MAXN][MAXN], t[20];
ll bh1[MAXN], bl1[MAXN], Bs1[MAXN], Bs2[MAXN], bh2[MAXN], bl2[MAXN];
map<pii<ll, ll>, int> mp;
inline void add1(ll &x, ll y) {
x += y;
if(x >= P1)x -= P1;
}
inline void add2(ll &x, ll y) {
x += y;
if(x >= P2)x -= P2;
}
inline void inith(int x) {
bh1[x] = 0;
for(int i = 1; i <= m; ++i) {
bh1[x] = (bh1[x] * B1 % P1 + s[x][i] - 'a' + 1) % P1;
bh2[x] = (bh2[x] * B2 % P2 + s[x][i] - 'a' + 1) % P2;
}
mp[mkp(bh1[x], bh2[x])] = 1;
}
inline void initl() {
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
bl1[i] = (bl1[i] * B1 % P1 + s[j][i] - 'a' + 1) % P1;
bl2[i] = (bl2[i] * B2 % P2 + s[j][i] - 'a' + 1) % P2;
}
mp[mkp(bl1[i], bl2[i])] = 1;
}
Bs1[0] = 1;
for(int i = 1; i <= max(n, m); ++i) {
Bs1[i] = Bs1[i - 1] * B1 % P1;
}
Bs2[0] = 1;
for(int i = 1; i <= max(n, m); ++i) {
Bs2[i] = Bs2[i - 1] * B2 % P2;
}
return ;
}
int main() {
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; ++i) {
scanf("%s", s[i] + 1);
inith(i); //
}
initl();
printf("%lld\n", (ll)mp.size());
for(int i = 1, x, y; i <= q; ++i) {
scanf("%d%d", &x, &y);
scanf("%s", t);
int tmp = t[0] - 'a' + 1;
add1(bh1[x], P1 - 1ll * Bs1[m - y] * (s[x][y] - 'a' + 1) % P1);
add1(bl1[y], P1 - 1ll * Bs1[n - x] * (s[x][y] - 'a' + 1) % P1);
add1(bh1[x], 1ll * Bs1[m - y] * tmp % P1);
add1(bl1[y], 1ll * Bs1[n - x] * tmp % P1);
add2(bh2[x], P2 - 1ll * Bs2[m - y] * (s[x][y] - 'a' + 1) % P2);
add2(bl2[y], P2 - 1ll * Bs2[n - x] * (s[x][y] - 'a' + 1) % P2);
add2(bh2[x], 1ll * Bs2[m - y] * tmp % P2);
add2(bl2[y], 1ll * Bs2[n - x] * tmp % P2);
s[x][y] = t[0];
mp[mkp(bh1[x], bh2[x])] = 1;
mp[mkp(bl1[y], bl2[y])] = 1;
printf("%lld\n", (ll)mp.size());
}
return 0;
}
/*
2 2 10000
aa
aa
1 1 b
2 2 b
1 1 b
*/
B
ljh就是个菜鸡这题都写不对??
发现当ab互质的时候,能走到的最大不能表示的数是,所以我们只需要考虑这个深度小于的点
然后ab不互质的时候深度是g的倍数时必要条件....
然后统计所有深度为g的倍数的点的个数-深度为g倍数走不到的点的个数即可
换根dp维护
C
哇偶!考场直接冲了个状压拿到90,复杂度其实是?
首先表示S里面的球已经选了,从S局面到游戏结束的最优期望值是什么,倒退dp
然后转移考虑是否直接结束游戏即可,如果不终结就是从所有多一个球的状态他们的期望 * 概率求和
否则就是现在的状态结束,得到的值就是这轮结束的价值,二者取max作为答案
这样子dp qwq,就是答案
显然的是,状态存在等价的情况qwq
因为前n/2个和后n/2他们的概率是等价的,所以我们10/01这个状态是一样的,直接记录其中一个就好,然后改变一下转移的系数即可
这样每一位我们只用一个三进制数压起来
#include<bits/stdc++.h>
#define db double
#define ll long long
#define lowbit(x) (x&(-x))
using namespace std;
const int MAXH = 30;
const int MAXS = (1 << 26) + 1;
int T, a, b, n;
ll V[MAXH];
db dp[MAXH][MAXH];
db g[MAXS];
db f[MAXS], ans;
inline void init() {
dp[1][1] = 1;
for(int i = 2; i <= n; ++i) {
for(int j = 1; j <= i; ++j) {
dp[i][j] = 0.5 * dp[i - 1][j] + 0.5 * dp[i - 1][j - 1];
}
}
for(int i = 1; i <= n; ++i) {
g[(1 << (i - 1))] = dp[n][i];
}
ans = 0;
return ;
}
inline void solve() {
int mS = (1 << n) - 1;
for(int i = 1; i <= n; ++i)
V[i] = a * i * i + b * i;
for(int S = mS, cnt; S >= 0; --S) {
cnt = 0;
int T = (~S)&mS;
db psum = 0;
while(T) {
int t = lowbit(T);
psum += f[S ^ t] * g[t];
T ^= t;
++cnt;
}
f[S] = (V[n - cnt] > psum) ? V[n - cnt] : psum;
}
printf("%.4lf\n", f[0]);
for(int S = 0; S <= mS; ++S) {
f[S] = 0;
}
return ;
}
int main() {
scanf("%d", &T);
T--;
scanf("%d%d%d", &n, &a, &b);
init();
solve();
while(T-- > 0) {
scanf("%d%d%d", &n, &a, &b);
solve();
}
return 0;
}
这份是暴力代码...摸了摸了
D
首先看k=3,会发现每个宽度为2的连通块对答案的倍数贡献要么是0要么是1要么是2
所以发现,如果我们这个2*3的小矩形,改了两列不同行的贡献就是0
改了两列相同列贡献为1
改了中间贡献0,因为所有路径的所有中间都要经过
没改贡献2
然后起点和终点被改了就不行
然后起点终点所在的块的另一端点被改没事情这样子分类讨论.....
4?矩阵快速幂啊,显然的吧?
直接维护暴力dp的转移矩阵然后如果有很长的连续段就分隔开这样子qwq
谁愿意实现啊??