Codeforces Round #269 (Div. 2) Solution
來源：程序員人生 發布時間：2014-09-30 07:29:17 閱讀次數：3813次
又趁夜擼了一發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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
