首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。