您的位置: 首页  >  IT文章  >  2019牛客多校第二场 2019牛客多校第二场

2019牛客多校第二场 2019牛客多校第二场

分类: IT文章 • 2022-09-01 12:41:30

A. Eddy Walker

upsloved

有一个长为(n)的环，一开始位于(0)，每次随机向前或者向后走，求最后一个走到(m)的概率

ps:这题实际上求的是所有询问的前缀积

实际上概率相等（俺也不知道为啥）如果(m!=0)，则概率是(frac 1 {n-1})，特判(n=1,m=0)就行了

代码不放了

B. Eddy Walker2

solved at 03:54(+2)

有一个无限长的序列，一开始位于(0)，每次概率均等地往前走(1)到(k)步，求经过(n)的概率

(1<=n<=1e18, 1<=k<=1000)

如果(n=-1)表示求(n)趋近于正无穷时的概率

显然(dp[i] = sumlimits_{j=i-k}^{i-1}dp[j])

这是个线性递推式，我们赛中BM搞过去了...

(n=-1)时小数据打表发现是(frac 2 {k+1})

矩阵快速幂是(k^3log(n))的，据说可以利用转移矩阵和特征方程的联系优化成(k^2log(n))的，并不是很懂，可以搜叉姐论文看一看

代码也没啥好放的

D. Kth Minimum Clique

upsloved

(n)个点的带点权的图，求权值第(k)小的完全子图的权值(1<=n<=100, 1<=k<=1e6))

看着咖啡鸡的代码恍然大悟，咖啡鸡nb

用优先队列保存当前完全子图，然后尝试往这个图里塞一个点，为避免重复只塞下标比当前完全子图最大点下标还要大的点，复杂度大概是(klog(k)+kn^2/64)

#include <bits/stdc++.h>
using namespace std;
using bs = bitset<105>;
using LL = long long;

struct node {
	LL val;
	bs mask;
	bool operator<(const node &rhs) const {
		return val > rhs.val;
	}
};

int s[105][105], n, a[105], k;
bs f[105];


int main() {
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
	}
	for(int i = 0; i < n; ++i) {
		f[i].reset();
		for(int j = 0; j < n; ++j) {
			scanf("%1d", &s[i][j]);
			if(s[i][j] == 1)
				f[i].set(j);
		}
	}
	priority_queue<node> pq;
	bs p;
	p.reset();
	pq.push({0, p});
	while(!pq.empty()) {
		node u = pq.top();
		pq.pop();
		if(--k == 0) {
			printf("%lld
", u.val);
			return 0;
		}
		int pos = 0;
		for(int i = 0; i < n; ++i)
			if(u.mask[i])
				pos = i + 1;
		for(int i = pos; i < n; ++i) if((f[i] & u.mask) == u.mask) {
			u.mask[i] = 1;
			pq.push({u.val + a[i], u.mask});
			u.mask[i] = 0;
		}
	}
	puts("-1");
	return 0;
}

E. MAZE

upsolved

你有一个(n*m)的(01)矩阵，(1)代表墙，你每次可以往下，左，右走（不能往上，也不能走回头路）

有两种操作

1.修改(i, j)位置的矩阵状态

2.询问从(1, a)走到(n, b)的方案数

设(dp[l][r][i][j])代表从(l, i)走到(r,j)的方案数

显然(dp[l][r][i][j] = sumlimits_{k=1}^mdp[l][x][i][k]*dp[x+1][r][k][j])，(x)是(l)到(r-1)之间的任意一个值

因为不能走回头路，相当于枚举怎么从(x)走到(x+1)的

然后这个东西显然可以用线段树，支持(O(m^3log(n)))修改, (O(1))查询

总复杂度是(O(q*m^3log(n)+m^3n))

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7, N = 5e4 + 10;
int n, m, q, b[N][10], x, y, z;
char s[14];

struct Matrix {
	int a[10][10];
	Matrix operator*(const Matrix &rhs) const {
		Matrix c;
		memset(c.a, 0, sizeof(c.a));
		for(int i = 0; i < m; ++i)  
			for(int j = 0; j < m; ++j) 
				for(int k = 0; k < m; ++k) 
					c.a[i][j] = (c.a[i][j] + 1LL * a[i][k] * rhs.a[k][j] % mod) % mod;
		return c;
	}
}tree[N << 2];

void pushup(int rt) {
	tree[rt] = tree[rt << 1] * tree[rt << 1 | 1];
}

void calc(int b[], Matrix &c) {
	memset(c.a, 0, sizeof(c.a));
	for(int i = 0; i < m; ++i) {
		for(int j = i; j < m && b[j] == 0; ++j) 
			c.a[i][j] = 1;
		for(int j = i; ~j && b[j] == 0; --j)
			c.a[i][j] = 1;
	}
}

void build(int rt, int l, int r) {
	if(l == r) {
		calc(b[l], tree[rt]);
		return;
	}
	int mid = l + r >> 1;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
	pushup(rt);
}

void update(int rt, int l, int r, int pos) {
	if(l == r) {
		calc(b[l], tree[rt]);
		return;
	}
	int mid = l + r >> 1;
	if(pos <= mid)
		update(rt << 1, l, mid, pos);
	else
		update(rt << 1 | 1, mid + 1, r, pos);
	pushup(rt);
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i <= n; ++i) {
		scanf("%s", s);
		for(int j = 0; j < m; ++j)
			b[i][j] = s[j] - '0';
	}
	build(1, 1, n);
	while(q--) {
		scanf("%d%d%d", &x, &y, &z);
		if(x == 1) {
			b[y][z - 1] ^= 1;
			update(1, 1, n, y);
		}
		else {
			printf("%d
", tree[1].a[y - 1][z - 1]);
		}
	}
	return 0;
}

F. Partition problem

solved at 02:38(+3)

有(2n)个人，把他们分为大小各为(n)的两个集合，不在同一个集合里的人会获得贡献(v_{i,j}),求最大贡献

((1<=n<=14))

比赛的时候并没有发现(C_{28}^{14})只有4e7, 可以直接(O(n*C_{28}^{14}))dfs过去

比赛的时候我写了个折半搜索，打了四个表，实际上复杂度也是(O(n*C_{28}^{14}))的...

折半的两个东西拼起来的时候要一些骚操作，不然很容易变成(2*n*C_{28}^{14})的或者是(n*2^{2*n})的

#include <bits/stdc++.h>
using namespace std;

const int N = 10 + (1 << 14);

long long dp[N], dp2[N];
long long p[14][N], p2[14][N], ans;

int a[28][28], n, t[N], f[N];
int c[N], tot;
vector<int> v[15];

int main() {
	scanf("%d", &n);
	for(int i = 0; i < 2 * n; ++i) {
		for(int j = 0; j < 2 * n; ++j) {
			scanf("%d", &a[i][j]);
		}
	}
	tot = (1 << n) - 1;
	c[0] = 0;
	v[0].push_back(0);
	for(int i = 1; i <= tot; ++i) {
		c[i] = c[i >> 1] + (i & 1);
		v[c[i]].push_back(i);
	}
	f[0] = 1;
	t[f[0]] = 0;
	for(int i = 1; i < n; ++i) {
		f[i] = 2 * f[i - 1];
		t[f[i]] = i;
	}
	for(int i = 0; i < n; ++i) {
		for(int mask = 0; mask <= tot; ++mask) {
			long long val = 0;
			for(int j = 0; j < n; ++j) {
				if((1 << j) & mask) {
					val += a[i][j + n];
				}
			}
			p[i][mask] = val;
		}
	}
	for(int i = 0; i < n; ++i) {
		for(int mask = 0; mask <= tot; ++mask) {
			long long val = 0;
			for(int j = 0; j < n; ++j) {
				if((1 << j) & mask) {
					val += a[i + n][j];
				}
			}
			p2[i][mask] = val;
		}
	}
	for(int mask = 0; mask <= tot; ++mask) {
		for(int i = 0; i < n; ++i) {
			for(int j = i + 1; j < n; ++j) {
				if(((mask >> i) & 1) == ((mask >> j) & 1)) continue;
				dp[mask] += a[i][j];
			}
		}
	}
	for(int mask = 0; mask <= tot; ++mask) {
		for(int i = 0; i < n; ++i) {
			for(int j = i + 1; j < n; ++j) {
				if(((mask >> i) & 1) == ((mask >> j) & 1)) continue;
				dp2[mask] += a[i + n][j + n];
			}
		}
	}
	for(int mask = 0; mask <= tot; ++mask) {
		for(auto mask2: v[n - c[mask]]) {
			long long val = dp[mask] + dp2[mask2];
			for(int x = mask; x; x -= x & -x) 
				val += p[t[x & -x]][tot ^ mask2];
			for(int x = mask2; x; x -= x & -x) 
				val += p2[t[x & -x]][tot ^ mask];
			ans = max(ans, val);
		}
	}
	printf("%lld
", ans);
	return 0;
}

H. Second Large Rectangle

solved at 01:00(+2)

有一个(n*m)的(01)矩阵，求面积第二大的全(1)子矩阵面积(1<=n,m<=1000)

最大的是用悬线法(O(nm))处理出来，第二大的也差不多，把每个位置对应的最大的要么行减一，要么列减一，第二大的肯定在这些里面

注意可能很多位置的最大全(1)子矩阵是同一个矩阵，标记掉就好了

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int a[N][N], d[N][N], s[N][N], s2[N][N], mx, mx2, n, m, vis[N][N];

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j)
			scanf("%1d", &a[i][j]);
	}
	for(int j = 1; j <= m; ++j) {
		for(int i = 1; i <= n; ++i) {
			if(a[i][j] == 0)
				d[i][j] = 0;
			else
				d[i][j] = d[i - 1][j] + 1;
		}
	}
	for(int i = 1; i <= n; ++i) {
		stack<int> st;
		while(!st.empty()) st.pop();
		d[i][m + 1] = -1;
		st.push(m + 1);
		for(int j = m; j; --j) {
			while(d[i][st.top()] >= d[i][j]) st.pop();
			s[i][j] = st.top();
			st.push(j);
		}
	}
	for(int i = 1; i <= n; ++i) {
		stack<int> st;
		while(!st.empty()) st.pop();
		d[i][0] = -1;
		st.push(0);
		for(int j = 1; j <= m; ++j) {
			while(d[i][st.top()] >= d[i][j]) st.pop();
			s2[i][j] = st.top();
			st.push(j);
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			if(a[i][j] == 0) continue;
			int r = s[i][j], l = s2[i][j];
			if(vis[l][r] == i) continue;
			vis[l][r] = i;
			mx2 = max(mx2, d[i][j] * (r - l - 1));
			if(mx2 > mx) swap(mx2, mx);
			mx2 = max(mx2, d[i][j] * (r - l - 2));
			if(mx2 > mx) swap(mx2, mx);
			mx2 = max(mx2, (d[i][j] - 1) * (r - l - 1));
			if(mx2 > mx) swap(mx2, mx);
		}
	}
	printf("%d
", mx2);
	return 0;
}

J. Subarray

upsolved

开场就有人过，看了半天不怎么会，没想到是个暴力

参考博客

相关推荐