CodeChef March Lunchtime 2018 div2
CodeChef March Lunchtime 2018 div2
attack
发布于 2019-01-30 16:10:13
发布于 2019-01-30 16:10:13
文章被收录于专栏：数据结构与算法
地址https://www.codechef.com/LTIME58B?order=desc&sortBy=successful_submissions
简单做了一下，前三题比较水，第四题应该算是经典题
AChef and Friends
直接暴力枚举即可
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1001, INF = 1e9 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, ans = 0;
char s[MAXN];
main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
N = read();
for(int i = 1; i <= N; i++) {
scanf("%s", s + 1);
int L = strlen(s + 1);
for(int j = 1; j <= L - 1; j++) {
if((s[j] == 'c' && s[j + 1] == 'h')||
(s[j] == 'h' && s[j + 1] == 'e')||
(s[j] == 'e' && s[j + 1] == 'f'))
{ans++; break;}
}
}
printf("%d", ans);
} BMagic Elements
维护一个所有元素的和，直接模拟即可
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, K, ans = 0;
int a[MAXN];
main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
int T = read();
while(T--) {
N = read(); K = read();
int sum = 0, ans = 0;
for(int i = 1; i <= N; i++) a[i] = read(), sum += a[i];
for(int i = 1; i <= N; i++)
if(a[i] + K > sum - a[i])
ans++;
printf("%d\n", ans);
}
} CThree Integers
把式子化成$2B = A +C$的形式，不难看出改B一定是最优的。
特判一下奇偶性即可
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
int N = read();
while(N--) {
int A = read(), B = read(), C = read();
int ans = abs(2 * B - A - C);
if(ans & 1) printf("%lld\n", ans / 2 + 1);
else printf("%lld\n", ans / 2);
}
} DPartitions
个人感觉是一道比较好的题
设所有元素的和为$sum$
不难发现，不论如何分，分成的段数一定是$sum$的因子
而且不论如何分，第一段一定是$1-x$（以$1$为起点）
这样我们遇到一个因子就枚举一边序列暴力分割就可以
这题TM居然卡常
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int a[MAXN];
char ans[MAXN];
main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
int T = read();
while(T--) {
int N = read(), sum = 0;
for(int i = 1; i <= N; i++) a[i] = read(), sum += a[i];
for(int i = 1; i <= N; i++) {
if(sum % i != 0) {ans[i] = '0'; continue;}
int cur = 0, num = 0;
for(int j = 1; j <= N; j++) {
cur += a[j];
if(cur == sum / i) cur = 0;
else if(cur > sum / i) {ans[i] = '0'; break;}
}
ans[i] = (cur == 0 ? '1' : '0');
}
for(int i = 1; i <= N; i++)
putchar(ans[i]);
puts("");
}
} 本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018-06-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
