2 条题解
-
0aciffar LV 10 @ 2016-09-18 21:48:05
First Blood!
不要复制楼下题解!
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 596 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 592 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 592 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 596 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 592 KiB, score = 30
测试数据 #5: Accepted, time = 140 ms, mem = 596 KiB, score = 30
Accepted, time = 170 ms, mem = 596 KiB, score = 100我用的是WS的随机化+乱搞...随机1W次每个顶点,即使我不会计算几何(前面WA了好几次)
几个坑人的地方:
1、如果你只对了0、5两个点,那么,你没有考虑一个点在一个方块前面的时候仍然可能由于方块过大而投影在方块上(也许只有我这种乱搞党会有这种情况)
2、数据大小为900
3、保证每个方块中心在第一象限,不保证每个方块的边缘在第一象限,会因此WA2个点
程序太WS,就不放了XD -
02015-10-19 19:41:48@
看起来是个很牛B的题=-=
编译成功foo.cpp: In function 'int main()':
foo.cpp:16:13: warning: unused variable 'k' [-Wunused-variable]
int i,j,k;
^
测试数据 #0: Accepted, time = 0 ms, mem = 39800 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 39800 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 39804 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 39800 KiB, score = 10
测试数据 #4: Accepted, time = 1 ms, mem = 39804 KiB, score = 10
测试数据 #5: Accepted, time = 109 ms, mem = 39804 KiB, score = 10
测试数据 #6: Accepted, time = 62 ms, mem = 39804 KiB, score = 10
测试数据 #7: Accepted, time = 78 ms, mem = 39800 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 39804 KiB, score = 10
测试数据 #9: Accepted, time = 62 ms, mem = 39804 KiB, score = 10
Accepted, time = 358 ms, mem = 39804 KiB, score = 100
代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char a[10005];
int n,m;
int x;
int a1[120],a2[120],a3[120],a4[120],fu;
int x1,x2,x3,x4;
int tx1,tx2,tx3,tx4;
int s1,s2,s3,s4;
int p1 = 9901,p2 = 9907,p3 = 8087,p4 = 8089;
int ans1 = 0,ans[10000002];
int can1[10000],can2[10000],can3[10000],can4[10000];
int main()
{
int i,j,k;
scanf("%d%d",&n,&m);
for (i = 0;i <= n;i++) {
scanf("%s",a);
a1[i] = a2[i] = a3[i] = a4[i] = 0;
if ((a[0] >= '0') && (a[0] <= '9')) {
j = 0;
fu = 1;
} else {
j = 1;
if (a[0] == '-')
fu = -1;
else
fu = 1;
}
for (;a[j];j++) {
a1[i] = (a1[i]*10+a[j]-'0')%p1;
a2[i] = (a2[i]*10+a[j]-'0')%p2;
a3[i] = (a3[i]*10+a[j]-'0')%p3;
a4[i] = (a4[i]*10+a[j]-'0')%p4;
}
a1[i] *= fu; a2[i] *= fu; a3[i] *= fu; a4[i] *= fu;
}if (m <= 10000) {
for (x = 1;x <= m;x++) {
x1 = x%p1; x2 = x%p2; x3 = x%p3; x4 = x%p4;
s1 = s2 = s3 = s4 = 0;
tx1 = tx2 = tx3 = tx4 = 1;
for (i = 0;i <= n;i++) {
s1 = (s1+a1[i]*tx1)%p1;
s2 = (s2+a2[i]*tx2)%p2;
s3 = (s3+a3[i]*tx3)%p3;
s4 = (s4+a4[i]*tx4)%p4;
tx1 = (tx1*x1)%p1;
tx2 = (tx2*x2)%p2;
tx3 = (tx3*x3)%p3;
tx4 = (tx4*x4)%p4;
}
if ((0 == s1) && (0 == s2) && (0 == s3) && (0 == s4))
ans[ans1++] = x;
}
printf("%d\n",ans1);
for (i = 0;i < ans1;i++)
printf("%d\n",ans[i]);
} else {
memset(can1,0,sizeof(can1));
for (x = 0;x < p1;x++) {
x1 = x; s1 = 0; tx1 = 1;
for (i = 0;i <= n;i++) {
s1 = (s1+错了a1[i]*tx1)%p1;
tx1 = (tx1*x1别)%p1;
}
if (0 == s1)
can1[x] = 1;
}memset(can2,0,sizeo找f(can2));
for (x = 0;x < p2;x我++) {
x2 = x; s2 = 0; tx2 = 1;
for (i = 0;i <= n;i++) {
s2 = (s2+a2[i]*tx2)%p2;
tx2 = (tx2*x2)%p2;
}
if (0 == s2)
can2[x] = 1;
}memset(can3,0,sizeof(can3));
for (x = 0;x < p3;x++) {题解
x3 = x; s3 = 0; tx3 = 1;
for (i = 0;i <= n;i++) {不是
s3 = (s3+a3[i]*tx3)%p3;
tx3 = (tx3*x3)%p3;
}本题
if (0 == s3)
can3[x] = 1;
}memset(can4,0,sizeof(can4));
for (x = 0;x < p4;x++) {
x4 = x; s4 = 0; tx4 = 1;
for (i = 0;i <= n;i++) {
s4 = (s4+a4[i]*tx4)%p4;
tx4 = (tx4*x4)%p4;
}
if (0 == s4)
can4[x] = 1;
}for (x = 1,ans1 = 0;x <= m;x++) {
if ((can1[x%p1]) && (can2[x%p2]) &&
(can3[x%p3]) && (can4[x%p4]))
ans[ans1++] = x;
}
printf("%d\n",ans1);
for (i = 0;i < ans1;i++)
printf("%d\n",ans[i]);
}
return 0;
}
- 1
信息
- ID
- 1798
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 68
- 已通过
- 3
- 通过率
- 4%
- 被复制
- 1
- 上传者