首页 > 代码库 > Codeforces Round #269 (Div. 2) Solution
Codeforces Round #269 (Div. 2) Solution
又趁夜撸了一发DIV2,然后由于困完挂了。
现在最终测试的结果还没有出来,估计写完就出来了。
通过了前四道题的Pretest.
update:这一次rank220,坑了!
A:给你六个长度(分别是四肢,头,躯干),让你判断这是什么物种。判断规则十分清楚了,然而我自己没注意看。。。导致被hack,并wa了数次。
思路:排序后直接找出四个相同的长度,若不存在为alien,否则剩下的两个相等elephant,再否则bear.
Code:
#include <cstdio> #include <cstring> #include <climits> #include <algorithm> using namespace std; int main() { int a[6]; register int i, j; for(i = 0; i < 6; ++i) scanf("%d", &a[i]); sort(a, a + 6); int ins = -1; for(i = 0; i <= 2; ++i) if (a[i] == a[i + 1] && a[i + 1] == a[i + 2] && a[i + 2] == a[i + 3]) { ins = i; break; } if (ins == -1) { puts("Alien"); return 0; } int tmp1, tmp2; if (ins == 0) tmp1 = a[4], tmp2 = a[5]; if (ins == 1) tmp1 = a[0], tmp2 = a[5]; if (ins == 2) tmp1 = a[0], tmp2 = a[1]; if (tmp1 == tmp2) puts("Elephant"); else puts("Bear"); return 0; }
B:有n项工作,每个工作都有一个difficulty,要求以difficulty不下降的顺序完成这些工作。若存在至少三种方案,输出其中的三种,否则输出no.
思路:首先排序后找出若干块连续的相同块,那么他们长度的阶乘积就是总的方案数,首先判断是否不超过3.
若存在3种方案,我们这样构造方案。
(1)直接就是排序后的标号序列
(2)在(1)基础上,找出第一个长度不为1的块交换前两个元素
(3)在(1)基础上,找出最后个长度不为1的块交换最后两个元素
不难证明这样做是正确的。
Code:
#include <cstdio> #include <cstring> #include <cctype> #include <iostream> #include <algorithm> using namespace std; #define N 2010 struct Node { int lab, dif; Node(int _lab = 0, int _dif = 0):lab(_lab),dif(_dif){} bool operator < (const Node &B) const { return dif < B.dif; } }S[N], S1[N], S2[N]; int begin[N], end[N], size[N], tot; int main() { int n; scanf("%d", &n); register int i, j, k; int x; for(i = 1; i <= n; ++i) { scanf("%d", &x); S[i] = Node(i, x); } sort(S + 1, S + n + 1); S[n + 1].dif = -1 << 30; unsigned long long res = 1; bool find = 0; for(i = 1; i <= n;) { for(j = i; S[j].dif == S[j + 1].dif; ++j); size[++tot] = j - i + 1; begin[tot] = i; end[tot] = j; for(k = 2; k <= j - i + 1; ++k) { res *= k; if (res >= 3) find = 1; } i = j + 1; } if (!find) { printf("NO"); return 0; } puts("YES"); for(i = 1; i < n; ++i) printf("%d ", S[i].lab); printf("%d\n", S[n].lab); memcpy(S1, S, sizeof(S)); for(i = 1; i <= tot; ++i) if (size[i] >= 2) { swap(S1[begin[i]], S1[begin[i] + 1]); break; } for(i = 1; i < n; ++i) printf("%d ", S1[i].lab); printf("%d\n", S1[n].lab); memcpy(S2, S, sizeof(S)); for(i = tot; i >= 1; --i) if (size[i] >= 2) { swap(S2[end[i]], S2[end[i] - 1]); break; } for(i = 1; i < n; ++i) printf("%d ", S2[i].lab); printf("%d\n", S2[n].lab); return 0; }
C:用指定张数的扑克牌搭建建筑,问可以搭建成多少种不同的层数。详细题意看原题。
显然若某一层有t个房间,那么这一层消耗的牌数为3*t-1
那么若一共s层,第i层房间数为ai,则总牌数为3*(a1+a2+...+as)-s
也就是说,我们首先判断(n+s)%3=0,则s符合条件。但是还要保证房间数递增,即a1>=1,ai>ai-1(2<=i<=s),于是a1+a2+...+as>=(1+s)*s/2
我们知道当(n+s)/3>=(1+s)*s/2时,我们总能构造出一组ai,使得其满足条件。反之则一定不能。
显然s在sqrt(n)范围内,因此枚举到10^6就可以了。
Code:
#include <cstdio> #include <cstring> #include <climits> #include <algorithm> #include <iostream> #include <cmath> using namespace std; typedef long long LL; int main() { LL n; scanf("%I64d", &n); int res = 0; register int i, j; for(i = 1; i <= 1000000 && i <= n; ++i) { if ((n + i) % 3 == 0) { LL last = (n + i) / 3; if (last >= (LL)i * (i + 1) / 2) ++res; } } printf("%d", res); return 0; }
D:自己脑补= =
思路:差分后裸kmp串匹配,注意细节。
Code:
#include <cstdio> #include <cstring> #include <cctype> #include <iostream> #include <algorithm> using namespace std; #define N 200010 int a1[N], a2[N], res[N], text[N], pre[N], dp[N]; bool end[N]; int main() { int n, w; scanf("%d%d", &n, &w); if (w == 1) { printf("%d", n); return 0; } if (n < w) { printf("0"); return 0; } register int i, j; for(i = 1; i <= n; ++i) scanf("%d", &a1[i]); for(i = 1; i <= w; ++i) scanf("%d", &a2[i]); for(i = 1; i < w; ++i) res[i] = a2[i + 1] - a2[i]; --w; for(i = 1; i < n; ++i) text[i] = a1[i + 1] - a1[i]; --n; pre[1] = 0; j = 0; res[w + 1] = (int)1e9; for(i = 2; i <= w; ++i) { while(j && res[j + 1] != res[i]) j = pre[j]; if (res[j + 1] == res[i]) ++j; pre[i] = j; } int tot = 0; j = 0; for(i = 1; i <= n; ++i) { while(j && res[j + 1] != text[i]) j = pre[j]; if (res[j + 1] == text[i]) ++j; if (j == w) ++tot; } printf("%d\n", tot); return 0; }
Codeforces Round #269 (Div. 2) Solution
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。