207 条题解
-
0
huzujun LV 8 @ 2013-12-08 15:01:49
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>using namespace std;
int a[10],b[10][10]={{0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,1,0,0,0,0,0,0},
{0,0,1,1,0,1,1,0,0,0},
{0,1,0,0,1,0,0,1,0,0},
{0,0,1,0,1,1,1,0,1,0},
{0,0,0,1,0,0,1,0,0,1},
{0,0,0,0,1,1,0,1,1,0},
{0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,1,1,0,1,1}},s=0,m=1000000,c[10],d[10],e[10];
void find()
{
for(c[1]=0;c[1]<=3;c[1]++)
for(c[2]=0;c[2]<=3;c[2]++)
for(c[3]=0;c[3]<=3;c[3]++)
for(c[4]=0;c[4]<=3;c[4]++)
for(c[5]=0;c[5]<=3;c[5]++)
for(c[6]=0;c[6]<=3;c[6]++)
for(c[7]=0;c[7]<=3;c[7]++)
for(c[8]=0;c[8]<=3;c[8]++)
for(c[9]=0;c[9]<=3;c[9]++)
{
bool flag=true;
for (int i=1; i<=9; i++) a[i]=d[i];
for (int i=1; i<=9; i++)
{
for (int j=1; j<=9; j++) a[i]+=c[j]*b[j][i];
a[i]%=4;
if (a[i]!=0) {flag=false; break;}
}
if (flag)
{
int ss=0;
for (int i=1; i<=9; i++) ss+=c[i];
if (ss<m) ss=m;
for(int i=1; i<=9; i++) e[i]=c[i];
}
}
}
int main()
{
for(int i=1; i<=9; i++)
{
cin>>a[i];
d[i]=a[i];
}
find();
bool flag=false;
for(int i=1;i<=9;i++)
for(int j=1; j<=e[i]; j++)
{
if(flag) cout<<" "; else flag=true;
cout<<i;
}
return 0;
} -
0
测试数据 #0: Accepted, time = 15 ms, mem = 476 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 472 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 476 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 476 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 472 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 472 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 472 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 472 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 476 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 476 KiB, score = 10
Accepted, time = 90 ms, mem = 476 KiB, score = 100
-
0
这才是正解
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>using namespace std;
int a[10],b[10][10]={{0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,1,0,0,0,0,0,0},
{0,0,1,1,0,1,1,0,0,0},
{0,1,0,0,1,0,0,1,0,0},
{0,0,1,0,1,1,1,0,1,0},
{0,0,0,1,0,0,1,0,0,1},
{0,0,0,0,1,1,0,1,1,0},
{0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,1,1,0,1,1}},s=0,m=1000000,c[10],d[10],e[10];
void find()
{
for(c[1]=0;c[1]<=3;c[1]++)
for(c[2]=0;c[2]<=3;c[2]++)
for(c[3]=0;c[3]<=3;c[3]++)
for(c[4]=0;c[4]<=3;c[4]++)
for(c[5]=0;c[5]<=3;c[5]++)
for(c[6]=0;c[6]<=3;c[6]++)
for(c[7]=0;c[7]<=3;c[7]++)
for(c[8]=0;c[8]<=3;c[8]++)
for(c[9]=0;c[9]<=3;c[9]++)
{
bool flag=true;
for (int i=1; i<=9; i++) a[i]=d[i];
for (int i=1; i<=9; i++)
{
for (int j=1; j<=9; j++) a[i]+=c[j]*b[j][i];
a[i]%=4;
if (a[i]!=0) {flag=false; break;}
}
if (flag)
{
int ss=0;
for (int i=1; i<=9; i++) ss+=c[i];
if (ss<m) ss=m;
for(int i=1; i<=9; i++) e[i]=c[i];
}
}
}
int main()
{
for(int i=1; i<=9; i++)
{
cin>>a[i];
d[i]=a[i];
}
find();
bool flag=false;
for(int i=1;i<=9;i++)
for(int j=1; j<=e[i]; j++)
{
if(flag) cout<<" "; else flag=true;
cout<<i;
}
return 0;
} -
0
尝试写了下位运算...BFS懒得剪枝。
总用时213ms= =！ 真是个好数字。
const
mov : array[1..9] of longint=(4617,73,36936,262657,2134536,16810048,2363904,19136512,18911232);
mo=57521883;
var
t,i,l,r,st,opt,ro,num : longint;
vis : array[0..mo+2] of boolean;
q,xl,pa : array[1..2000007] of longint;
flag : boolean;procedure prinf(k : longint);
begin
if xl[k]=0 then exit;
prinf(pa[k]);
write(xl[k],' ');
end;begin
for i := 1 to 9 do
begin
read(num); inc(t); st := st+num<<(t*3-3);
end;
l := 1; r := 1; q[1] := st; xl[1] := 0; vis[st] := true;
repeat
opt := q[l];
for i := 1 to 9 do
begin
ro := opt+mov[i];
ro := ro and mo;
if not vis[ro] then
begin
inc(r); q[r] := ro; xl[r] := i; pa[r] := l; vis[ro] := true;
end;
if ro=0 then begin flag := true; break; end;
end;
inc(l);
until flag;
prinf(r);
end. -
0
九维标记数组加强力BFS剪枝，
无压力全过。。。
测试数据 #0: Accepted, time = 156 ms, mem = 6780 KiB, score = 10
测试数据 #1: Accepted, time = 125 ms, mem = 6776 KiB, score = 10
测试数据 #2: Accepted, time = 78 ms, mem = 6780 KiB, score = 10
测试数据 #3: Accepted, time = 93 ms, mem = 6776 KiB, score = 10
测试数据 #4: Accepted, time = 203 ms, mem = 6776 KiB, score = 10
测试数据 #5: Accepted, time = 265 ms, mem = 6780 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 6776 KiB, score = 10
测试数据 #7: Accepted, time = 125 ms, mem = 6776 KiB, score = 10
测试数据 #8: Accepted, time = 78 ms, mem = 6780 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 6780 KiB, score = 10
Accepted, time = 1185 ms, mem = 6780 KiB, score = 100
/**********************************
User:Kevin.Deng
Date:2013.07.20
Lang:C++
Prog:Vijos 1016
Scho:HNSDFZ
**********************************/
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
using namespace std;
#define ufor(i,j,k) for (int i=j;i<=k;i++)
#define dfor(i,j,k) for (int i=j;i>=k;i--)
#define m_int 2147483647
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define pi 3.1415926535897
#define re return 0
#define pn printf("\n")
#define ll long long
#define real double
struct rt
{
int a;
int fa,so;
int x1,x2;
}z[270000];/*0 1 2 3 4 5 6 7 8 9*/
int c[10]= {0,110110000,111000000,11011000,100100100,10111010,1001001,110110,111,11011};
int b[4][4][4][4][4][4][4][4][4];
int n=3;
int x,l,r;
int tsqr(int x)
{
int s=1;
ufor(i,1,x)
s=s*10;
return s;
}
void file_o()
{
freopen(".","r",stdin);
freopen(".","w",stdout);
}
void file_c()
{
fclose(stdin);fclose(stdout);
}
void init()
{
ufor(i,1,n)
ufor(j,1,n){
scanf("%d",&x);
z[1].a=z[1].a*10+x;
}
//printf("%d\n",z[1].a);
}
void outp(int s)
{
for (int i=r;i!=0;i=z[i].fa){
//printf("%d %d\n",z[i].x1,i);
z[z[i].fa].so=i;z[z[i].fa].x2=z[i].x1;
}
for (int i=1;i!=0;i=z[i].so)
if (z[i].x2!=0)
printf("%d ",z[i].x2);
pn;
exit(0);
}void work()
{
l=1;r=1;
b[z[1].a/100000000][z[1].a/10000000%10][z[1].a/1000000%10][z[1].a/100000%10][z[1].a/10000%10][z[1].a/1000%10][z[1].a/100%10][z[1].a/10%10][z[1].a%10]=1;
z[1].fa=0;
while (l<=r)
{
ufor(i,1,9)
{
//printf("%d\n",z[l].a);
int s=z[l].a+c[i];
//printf("%d\n",s);
int s1,s2;
s2=0;
ufor(j,1,9){
s1=s%10;
s1=s1%4;
s=s/10;
s2=s2+s1*tsqr(j-1);
//printf("%d\n",s2);
}
//printf("%d\n",s2);
//system("pause");
if (b[s2/100000000][s2/10000000%10][s2/1000000%10][s2/100000%10][s2/10000%10][s2/1000%10][s2/100%10][s2/10%10][s2%10]==0)
{
b[s2/100000000][s2/10000000%10][s2/1000000%10][s2/100000%10][s2/10000%10][s2/1000%10][s2/100%10][s2/10%10][s2%10]=1;
z[++r].a=s2;z[r].fa=l;z[r].x1=i;
//printf("!\n");
}
if (s2==0)
outp(s2);
}
l++;
}
}
int main()
{
//file_o();
init();
work();
//file_c();
re;
} -
0
-
0
const
w:array[1..9,1..5] of char=
(('A','B','D','E',' '),
('A','B','C',' ',' '),
('B','C','E','F',' '),
('A','D','G',' ',' '),
('B','D','E','F','H'),
('C','F','I',' ',' '),
('D','E','G','H',' '),
('G','H','I',' ',' '),
('E','F','H','I',' '));
var
t:boolean;
j,k,ans,tem:longint;
s:char;
ansl:array[1..10000] of longint;
i:array[1..9] of longint;
c,ct:array['A'..'I'] of longint;
begin
ans:=100000;
for s:='A' to 'I' do read(c);
while i[9] -
0
z287438743z LV 7 @ 2012-09-05 19:47:10
伟大的枚举。菜鸟专用。
恶心的PASCAL，数组不给用for的变量，于是while。
整齐。
由于钟转4次等于没有转，那么每个操作枚举0~3则相当于全部枚举了。
一次全过，没有压力。
├ 测试数据 01：答案正确... (112ms, 620KB)
├ 测试数据 02：答案正确... (128ms, 620KB)
├ 测试数据 03：答案正确... (0ms, 620KB)
├ 测试数据 04：答案正确... (0ms, 620KB)
├ 测试数据 05：答案正确... (0ms, 620KB)
├ 测试数据 06：答案正确... (7ms, 620KB)
├ 测试数据 07：答案正确... (89ms, 620KB)
├ 测试数据 08：答案正确... (85ms, 620KB)
├ 测试数据 09：答案正确... (108ms, 620KB)
├ 测试数据 10：答案正确... (96ms, 620KB)
const
w:array[1..9,1..5] of char=
(('A','B','D','E',' '),
('A','B','C',' ',' '),
('B','C','E','F',' '),
('A','D','G',' ',' '),
('B','D','E','F','H'),
('C','F','I',' ',' '),
('D','E','G','H',' '),
('G','H','I',' ',' '),
('E','F','H','I',' '));
var
t:boolean;
j,k,ans,tem:longint;
s:char;
ansl:array[1..10000] of longint;
i:array[1..9] of longint;
c,ct:array['A'..'I'] of longint;
begin
ans:=100000;
for s:='A' to 'I' do read(c);
while i[9] -
0
chenjunhao LV 7 @ 2009-11-08 13:01:22
编译通过...
├ 测试数据 01：答案正确... 25ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 41ms
├ 测试数据 06：答案正确... 41ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：107ms
Bfs+强大的优化 -
0
xjcjason123 LV 10 @ 2009-11-07 17:38:03
9维布尔数组太强了，秒杀！！
-
0
First_blood LV 9 @ 2009-11-05 13:28:50
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 72ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 9ms
├ 测试数据 06：答案正确... 150ms
├ 测试数据 07：答案正确... 72ms
├ 测试数据 08：答案正确... 41ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：344ms很丑的10层 - -|||
另：AC100纪念，- -|||
没想到是这个水题 - -||| -
0
#include
int opt[10][10]=
{
{/*A B C D E F G H I*/},//0
{0,1,1,0,1,1,0,0,0,0},//1
{0,1,1,1,0,0,0,0,0,0},//2
{0,0,1,1,0,1,1,0,0,0},//3
{0,1,0,0,1,0,0,1,0,0},//4
{0,0,1,0,1,1,1,0,1,0},//5
{0,0,0,1,0,0,1,0,0,1},//6
{0,0,0,0,1,1,0,1,1,0},//7
{0,0,0,0,0,0,0,1,1,1},//8
{0,0,0,0,0,1,1,0,1,1}//9
};
int clock[10];
int com[10];
inline
void as(int f[10],int t[10])
{
for (int i=1;i -
0
编译通过...
├ 测试数据 01：答案正确... 41ms
├ 测试数据 02：答案正确... 9ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：运行超时|无输出...
├ 测试数据 05：答案正确... 306ms
├ 测试数据 06：答案正确... 291ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 41ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：90 有效耗时：688ms
唉,本来是打算来做100AC纪念的,宽搜咋这样...........9循环.....传说啊啊啊啊啊啊啊啊啊....... -
0
HelloCheaty LV 9 @ 2009-11-02 20:57:31
Accepted 有效得分：100 有效耗时：541ms
-
0
BFS+剪枝
注意减枝～
1、每种操作应不超过3次
2、操作序列是非降的program clocks;
var
len,f,gg:array[1..9] of integer;
a:array[1..9,1..5] of integer;
he,h1,h2,num:array[1..300000] of longint;
h:array[1..300000,1..9] of integer;
g:array[0..262143] of boolean;
mm:array[0..300000,1..9] of integer;i,j,s,t,tmp,m,aa,k:longint;
tt,it:boolean;begin
len[1]:=4; a[1,1]:=1; a[1,2]:=2; a[1,3]:=4; a[1,4]:=5;
len[2]:=3; a[2,1]:=1; a[2,2]:=2; a[2,3]:=3;
len[3]:=4; a[3,1]:=2; a[3,2]:=3; a[3,3]:=5; a[3,4]:=6;
len[4]:=3; a[4,1]:=1; a[4,2]:=4; a[4,3]:=7;
len[5]:=5; a[5,1]:=2; a[5,2]:=4; a[5,3]:=5; a[5,4]:=6;a[5,5]:=8;
len[6]:=3; a[6,1]:=3; a[6,2]:=6; a[6,3]:=9;
len[7]:=4; a[7,1]:=4; a[7,2]:=5; a[7,3]:=7; a[7,4]:=8;
len[8]:=3; a[8,1]:=7; a[8,2]:=8; a[8,3]:=9;
len[9]:=4; a[9,1]:=5; a[9,2]:=6; a[9,3]:=8; a[9,4]:=9;readln(f[1],f[2],f[3]);
readln(f[4],f[5],f[6]);
readln(f[7],f[8],f[9]);aa:=f[9];
k:=1;
for i:=8 downto 1 do
begin
k:=k*4;
aa:=aa+f[i]*k;
end;
g[aa]:=true;s:=1;
t:=2;
for i:=1 to 9 do h[1][i]:=f[i];
for i:=1 to 9 do mm[1][i]:=0;
he[1]:=0;
h1[1]:=0;
h2[1]:=0;
while s -
0
qyjubriskxp LV 10 @ 2009-11-01 10:35:04
碰到很水的测评机，连bfs都700ms!!
局部数组竟然不能开太大,我不用dev竟然查不出来，ac率... -
0
DFS=AC (EXIT(0 MS))
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
program ex;
type arr=array[1..9]of longint;
const d:array[1..9,0..9]of longint=((4,1,2,4,5,0,0,0,0,0),
(3,1,2,3,0,0,0,0,0,0),
(4,2,3,5,6,0,0,0,0,0),
(3,1,4,7,0,0,0,0,0,0),
(5,2,4,5,6,8,0,0,0,0),
(3,3,6,9,0,0,0,0,0,0),
(4,4,5,7,8,0,0,0,0,0),
(3,7,8,9,0,0,0,0,0,0),
(4,5,6,8,9,0,0,0,0,0));
var i,j:longint;
a,ans:arr;procedure print;
var i,j:longint;
begin
for i:=1 to 9 do
for j:=1 to ans[i] do
write(i,' ');
writeln;
halt;
end;function check:boolean;
var i,j:longint;
begin
for i:=1 to 9 do
if a[i] mod 40 then exit(false);
exit(true);end;
procedure dfs(step:longint);
var i,j:longint;
begin
if step>9 then
begin
if check then print;
exit;
end;
for i:=0 to 3 do
begin
ans[step]:=i;
for j:=1 to d[step,0] do inc(a[d[step,j]],i);
dfs(step+1);
for j:=1 to d[step,0] do dec(a[d[step,j]],i);
end;
end;begin
for i:=1 to 9 do read(a[i]);
dfs(1);
end. -
0
prince_hao LV 10 @ 2009-10-29 22:00:25
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 9ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 9ms
├ 测试数据 06：答案正确... 9ms
├ 测试数据 07：答案正确... 9ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 9ms
├ 测试数据 10：答案正确... 9ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：54ms哎
第2009个差了一点。。快来看我的沙茶九重循环！
program p1016;
const w1:array[1..9]of integer=(1,1,0,1,1,0,0,0,0);
w2:array[1..9]of integer=(1,1,1,0,0,0,0,0,0);
w3:array[1..9]of integer=(0,1,1,0,1,1,0,0,0);
w4:array[1..9]of integer=(1,0,0,1,0,0,1,0,0);
w5:array[1..9]of integer=(0,1,0,1,1,1,0,1,0);
w6:array[1..9]of integer=(0,0,1,0,0,1,0,0,1);
w7:array[1..9]of integer=(0,0,0,1,1,0,1,1,0);
w8:array[1..9]of integer=(0,0,0,0,0,0,1,1,1);
w9:array[1..9]of integer=(0,0,0,0,1,1,0,1,1);
c:array[1..9]of integer=(0,0,0,0,0,0,0,0,0);
var a,b:array[1..9]of longint;
i1,i2,i3,i4,i5,i6,i7,i8,i9,a1,a2,a3,a4,a5,a6,a7,a8,a9,ans:integer;
procedure init;
var i:longint;
begin
for i:=1 to 9 do
read(a[i]);
end;
function check:boolean;
var j:integer;fl:boolean;
begin
fl:=true;
for j:=1 to 9 do if b[j]0 then begin fl:=false; break;end;
check:=fl;
end;
procedure print;
var j:integer;
begin
for j:=1 to a1 do
write(1,' ');
for j:=1 to a2 do
write(2,' ');
for j:=1 to a3 do
write(3,' ');
for j:=1 to a4 do
write(4,' ');
for j:=1 to a5 do
write(5,' ');
for j:=1 to a6 do
write(6,' ');
for j:=1 to a7 do
write(7,' ');
for j:=1 to a8 do
write(8,' ');
for j:=1 to a9 do
write(9,' ');
end;
procedure save;
begin
if i1+i2+i3+i4+i5+i6+i7+i8+i9
huzujun
LV 8
@ 2013-12-08 15:01:49
信息
- ID
- 1016
- 难度
- 5
- 分类
- 搜索 | 搜索与剪枝 点击显示
- 标签
- 递交数
- 4788
- 已通过
- 1606
- 通过率
- 34%
- 被复制
- 18
- 上传者
-
Vivian Snow
