又趁夜撸了一发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;
}