夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

CSP-S2考前综合强化刷题（第一场)

2020-10-01 8 min read # 前缀和优化 # 培训题 # 比赛题 # 动态规划

屑

A

考虑必胜策略的构造

假设我有最后一张牌

如果对方选取i,我就选择i+1

然后考虑我们这样做一定能有一个牌权

如果对方先手而且我的牌不比他多就能靠这个牌权取胜

所以:

奇数+奇先手必胜

奇数+偶先手必胜

偶数 偶必胜

n=2先手必胜

code:


#include<bits/stdc++.h>
using namespace std;
string s;
int T;
int main() {
	scanf("%d",&T);
	while(T-->0) {
		int op;
		cin>>s;
		scanf("%d",&op);
		if(s.size()==1 && s[s.size()-1]=='2') {
			printf("%d\n",op);
		} else if((s[s.size()-1]-'0')%2==0)puts("1");
		else {
			if(op==0)puts("0");
			else puts("1");
		}
	}
	return 0;
}

B

发现我们可以在线/se

举个例子:

染色一行,那么我们如果染蓝色,看看这一行最近一次染得是蓝色还是红色

如果染的蓝色,那么我们查询这个上次到这次时间区域染列红色的个数,那些会变蓝,对应加上

如果染的是红色,那么我们查询这次到上次时域染的行蓝色的个数,那些会不变,加上m−cntm-cnt

直接暴力分类讨论要8中,所以我在代码中压缩了行列的区别

考场心态炸裂QAQ

不该打grakn forces2020

齐神的O(n)做法

每一行每一列按照染色的最后时间排序

然后就会发现上述过程可以排序双指针了....

code:


#include<bits/stdc++.h>
#define ll long long
const int MAXN=1e6+7;
using namespace std;
int n,m,k;
ll ans;
int col[2][MAXN],tim[2][MAXN];
//color time
const int MAXT=2e6+7;
struct rec {
#define lowbit(x) (x&(-x))
	int tr[MAXT];
	inline void mdf(int x,int v) {
		for(; x<=k; x+=lowbit(x))tr[x]+=v;
	}
	inline ll qry(int x) {
		ll ret=0;
		for(; x; x-=lowbit(x))ret+=tr[x];
		return ret;
	}
} tr[2][2];//first h,l second r,b

namespace fastIO {
#define BUF_SIZE (1<<21)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = BUF_SIZE + buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;

int main() {
	n=read();
	m=read();
	k=read();
	ans=1ll*n*m;
	for(int i=1,x,y,z; i<=k; ++i) {
		x=read();
		z=read();
		y=read();
		if(y==0) {//红色
			if(col[x][z]==0) {//base red paint red
				ans += tr[x^1][1].qry(i)-tr[x^1][1].qry(tim[x][z]);
			} else {//base blue paint ret
				if(x==1) {
					ans += (n-tr[x^1][0].qry(i)+tr[x^1][0].qry(tim[x][z]));
				} else ans += (m-tr[x^1][0].qry(i)+tr[x^1][0].qry(tim[x][z]));
			}
            		} else {//蓝色
			if(col[x][z]==1) {
				ans -= tr[x^1][0].qry(i)-tr[x^1][0].qry(tim[x][z]);
			} else {//红色？？
				if(x==0)
					ans -= (m-tr[x^1][1].qry(i)+tr[x^1][1].qry(tim[x][z]));
				else ans -= (n-tr[x^1][1].qry(i)+tr[x^1][1].qry(tim[x][z]));
			}
		}
		if(tim[x][z]!=0) {
			tr[x][col[x][z]].mdf(tim[x][z],-1);
		}
		tr[x][y].mdf(i,1);
		col[x][z]=y;
		tim[x][z]=i;
	}
	ans=1ll*n*m-ans;
	printf("%lld\n",ans);
	return 0;
}

C

nth_element

QAQ降智了

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=12345;
int n,Q,a[MAXN],v[MAXN];

struct rec {
	ll W;
	int id;
	bool operator<(const rec &x)const {
		return W==x.W?id<x.id:W>x.W;
	}
} p[MAXN];

int t,k;

int main() {
	scanf("%d",&n);
	for(int i=0; i<n; ++i)scanf("%d%d",&v[i],&a[i]);
	scanf("%d",&Q);
	for(int i=1; i<=Q; ++i) {
		scanf("%d%d",&t,&k);
		for(int i=0; i<n; ++i) {
			p[i].W=1ll*a[i]+1ll*v[i]*t;
			p[i].id=i+1;
		}
		nth_element(p,p+k-1,p+n);
		printf("%d\n",p[k-1].id);
	}
	return 0;
}

D

考虑DP,设fi,jf_{i,j}表示看了前i个A数前j个B数能够得到的最小划分代价

然后转移是O(n2)O(n^2)的,因为要枚举上一行上一列是什么

然后转移能优化吗QAQ?

你会发现:

结论：存在一个最优解的每次删数，至少有一段长度是1

因为我们有一段都大于1的

我们可以拆成(x+y)(x+y)和(a+b)(a+b)

然后xa+yb<=(x+y)∗(a+b)xa+yb<=(x+y)*(a+b)

所以整完了,转移式子变得可以优化

实现的时候有一维可以直接前缀最小值

另一维...好像按理说也是可以的,不过我的实现是使用N2N^2数组

code:


#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2005;
int n, m;
int A[MAXN], B[MAXN];
ll f[MAXN][MAXN], suma[MAXN], sumb[MAXN];
ll minxa[MAXN][MAXN], minxb[MAXN];
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &A[i]);
		A[i]--;
		suma[i] = suma[i - 1] + A[i];
	}
	for(int i = 1; i <= m; ++i) {
		scanf("%d", &B[i]);
		B[i]--;
		sumb[i] = sumb[i - 1] + B[i];
	}
	if(n < m) {
		swap(n, m);
		swap(A, B);
		swap(suma, sumb);
	}
	memset(f, 0x3f3f3f3f, sizeof(f));
	memset(minxa, 0x3f3f3f3f, sizeof(minxa));
	memset(minxb, 0x3f3f3f3f, sizeof(minxb));
	minxa[0][0] = 0;
	for(int i = 1; i <= m; ++i)minxa[0][i] = 0;
	minxb[0] = 0;
	f[0][0] = 0;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			f[i][j] = min(f[i][j], minxa[i - 1][j - 1] + A[i] * sumb[j]);
			f[i][j] = min(f[i][j], minxb[j - 1] + B[j] * suma[i]);
		}
		for(int j = 1; j <= m; ++j) {
			minxa[i][j] = min(minxa[i][j - 1], f[i][j] - A[i + 1] * sumb[j]);
			minxb[j] = min(minxb[j], f[i][j] - B[j + 1] * suma[i]);
		}
	}
	printf("%lld\n", f[n][m]);
	return 0;
}
/*
3 4
2 4 3
2 6 6 4
*/
Powered by Gridea RSS