程序员人生 网站导航

Codeforces Round #269 (Div. 2) Solution

栏目:codeigniter时间:2014-09-30 07:29:17

又趁夜撸了一发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 ", 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 ", 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 ", 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 ", tot); return 0; }

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐