首页 > 代码库 > Codeforces Round #267 (Div. 2)

Codeforces Round #267 (Div. 2)

QAQAQAQAQ

D题sb题没写出来(大雾)

QAQAQAQ

差点掉ratingQAQ

c题我能再wa多次吗,就打错个max的转移啊!QAQ

 

A.George and Accommodation

题意:给你a和b,问你a是否小于等于b-2

这。。。

#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << #x << " = " << x << endl#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }int main() {	int n=getint(), ans=0;	while(n--) {		int a=getint(), b=getint();		if(b-2>=a) ++ans;	}	print(ans);	return 0;}

 

B.Fedor and New Game

题意:给你m+1个数让你判断所给的数的二进制形式与第m+1个数不想同的位数是否小于等于k,累计答案

能再水点吗。。

#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << #x << " = " << x << endl#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }const int N=1005;int a[N], my, ans;int main() {	int n=getint(), m=getint(), k=getint();	for1(i, 1, m) read(a[i]);	read(my);	for1(i, 1, m) {		int tot=0;		for3(j, n-1, 0) {			if(((1<<j)&a[i])!=((1<<j)&my)) ++tot;		}		if(tot<=k) ++ans;	}	print(ans);	return 0;}

 

C.George and Job

题意:给你n个数,让你分成k块不相交的大小为m的连续的块,然后求所有可行方案的最大值

设d[i, j]表示前i个数分成j块的最大值

d[i, j]=max{d[k, j-1]}+sum[i-m, i],1<=k<=i-m

答案是max{d[i, k]}

这里是n^3的,我们考虑优化横n^2

设mx[i, j]表示max{d[k, j]} 1<=k<=j

然后转移变成

d[i, j]=mx[i-m, j-1]+sum[i-m, i]

而mx的转移是

mx[i, j]=max{mx[i-1, j], d[i, j]}

#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%I64d", a)#define dbg(x) cout << #x << " = " << x << endl#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }inline const ll getint() { ll r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const ll max(const ll &a, const ll &b) { return a>b?a:b; }inline const ll min(const ll &a, const ll &b) { return a<b?a:b; }const int N=5005;int n, m, k;ll sum[N], d[N], ans, mx[N][N], f[N], a[N];int main() {	read(n); read(m); read(k);	for1(i, 1, n) read(a[i]), sum[i]=sum[i-1]+a[i];	for1(i, m, n) d[i]=sum[i]-sum[i-m];	for1(i, m, n) {		for3(j, k, 1) {			f[j]=mx[i-m][j-1]+d[i];			mx[i][j]=max(mx[i-1][j], f[j]);		}		ans=max(ans, f[k]);	}	print(ans);	return 0;}

 

D.Fedor and Essay

字符串题,,,要上课了,,中午回来补。。

 

Codeforces Round #267 (Div. 2)