小阮的菜田
一个人一种命,各安天命吧。
C++博客
首页
新随笔
联系
聚合
管理
随笔-141 评论-9 文章-3 trackbacks-0
USACO 2.1.5 Hamming Codes
/**/
/*
ID: lorelei3
TASK: hamming
LANG: C++
*/
#include
<
fstream
>
#include
<
iostream
>
using
namespace
std;
const
int
MAX
=
0xFFF
;
int
N, B, D;
int
mask
=
0xFFFF
;
int
ans[MAX];
int
count
=
0
,num
=
0
;
bool
haming(
int
a,
int
b)
{
int
c
=
mask
&
(a
^
b);
int
d
=
0
;
for
(
int
i
=
0
; i
<
B;
++
i)
if
(c
&
1
<<
i)
{
d
++
;
if
(d
>=
D)
return
true
;
}
return
false
;
}
bool
check(
int
num)
{
for
(
int
i
=
0
; i
<
count;
++
i)
{
if
(
!
haming(num, ans[i]))
return
false
;
}
return
true
;
}
int
main()
{
ifstream
in
(
"
hamming.in
"
);
ofstream
out
(
"
hamming.out
"
);
in
>>
N
>>
B
>>
D;
ans[count
++
]
=
0
;
num
=
1
;
while
(count
<
N)
{
if
(check(num))
{
ans[count
++
]
=
num;
}
num
++
;
}
char
*
sep
=
"
"
;
int
ends
=
1
;
for
(
int
i
=
0
; i
<
count;
++
i)
{
sep
=
"
"
;
if
(i
==
count
-
1
||
ends
==
10
)
{
ends
=
0
;
sep
=
"
\n
"
;
}
out
<<
ans[i]
<<
sep;
ends
++
;
}
return
0
;
}
posted @
2010-11-21 00:47
小阮 阅读(353) |
评论 (0)
|
编辑
收藏
USACO 2.1.4 Healthy Holsteins
/**/
/*
ID: lorelei3
TASK: holstein
LANG: C++
*/
#include
<
fstream
>
#include
<
stdio.h
>
#include
<
stdlib.h
>
#include
<
string
.h
>
using
namespace
std;
const
int
MAX
=
30
;
int
V, G;
//
V 需要维他命种类数, G可以喂牛的饲料种数
int
need[MAX];
int
kind[MAX][MAX];
int
x[MAX];
int
best[MAX];
int
y[MAX];
int
total
=
100000000
, num
=
MAX;
bool
check()
{
int
i,j, times
=
0
,to
=
0
;
memset(y,
0
,
sizeof
(y));
for
(i
=
0
; i
<
G;
++
i)
{
if
(x[i])
{
times
++
;
for
(j
=
0
; j
<
V;
++
j)
y[j]
+=
kind[i][j];
}
}
for
(i
=
0
; i
<
V;
++
i)
{
if
(y[i]
<
need[i])
return
false
;
else
to
+=
y[i];
}
if
(times
<
num)
{
if
(to
<
total)
{
total
=
to;
return
true
;
}
else
return
false
;
}
else
return
false
;
}
void
dfs(
int
t)
{
if
(t
>=
G)
{
if
(check())
{
num
=
0
;
for
(
int
i
=
0
; i
<
G;
++
i)
{ best[i]
=
x[i]; num
+=
best[i]; }
}
}
else
for
(
int
i
=
0
; i
<=
1
;
++
i)
{
x[t]
=
i;
dfs(t
+
1
);
}
}
int
main()
{
int
i,j;
ifstream
in
(
"
holstein.in
"
);
ofstream
out
(
"
holstein.out
"
);
in
>>
V;
for
(i
=
0
; i
<
V;
++
i)
in
>>
need[i];
in
>>
G;
for
(i
=
0
; i
<
G;
++
i)
for
(j
=
0
; j
<
V;
++
j)
in
>>
kind[i][j];
dfs(
0
);
char
*
ch
=
"
"
;
out
<<
num
<<
ch;
for
(i
=
0
,j
=
0
; i
<
G;
++
i)
{
if
(best[i])
{
j
++
;
if
(j
==
num) ch
=
""
;
out
<<
i
+
1
<<
ch;
}
}
out
<<
endl;
return
0
;
}
posted @
2010-11-21 00:46
小阮 阅读(166) |
评论 (0)
|
编辑
收藏
USACO 2.1.3 Sorting A Three-Valued Sequence
/**/
/*
ID: lorelei3
TASK: sort3
LANG: C++
*/
#include
<
fstream
>
#include
<
iostream
>
#include
<
algorithm
>
using
namespace
std;
const
int
MAX
=
1005
;
int
first[MAX], second[MAX];
int
n;
int
main()
{
int
i,j, npairs
=
0
, ntriples
=
0
, nswap
=
0
;
ifstream
in
(
"
sort3.in
"
);
ofstream
out
(
"
sort3.out
"
);
in
>>
n;
for
(i
=
0
; i
<
n;
++
i)
{
in
>>
first[i];
second[i]
=
first[i];
}
sort(second, second
+
n);
for
(i
=
0
; i
<
n;
++
i)
for
(j
=
0
; j
<
n;
++
j)
if
(first[i]
!=
second[i]
&&
first[j]
!=
second[j]
&&
first[i]
==
second[j]
&&
second[i]
==
first[j])
{
first[i]
=
second[i];
first[j]
=
second[j];
npairs
++
;
}
for
(i
=
0
; i
<
n;
++
i)
if
(first[i]
!=
second[i])
ntriples
++
;
nswap
=
npairs
+
ntriples
/
3
*
2
;
out
<<
nswap
<<
endl;
return
0
;
}
posted @
2010-11-21 00:45
小阮 阅读(119) |
评论 (0)
|
编辑
收藏
USACO 2.1.2 Ordered Fractions
/**/
/*
ID: lorelei3
TASK: frac1
LANG: C++
*/
#include
<
fstream
>
#include
<
iostream
>
#include
<
algorithm
>
#include
<
cstdio
>
#include
<
cstdlib
>
using
namespace
std;
const
int
MAX
=
165
;
typedef
struct
Frac
{
int
a,b;
double
val;
bool
operator
<
(
const
Frac
&
t)
const
{
return
val
<
t.val;
}
}
Frac;
int
gcd(
int
a,
int
b)
{
if
(b
==
0
)
return
a;
else
return
gcd(b, a
%
b);
}
int
n;
Frac num[MAX
*
MAX];
int
main()
{
ifstream
in
(
"
frac1.in
"
);
ofstream
out
(
"
frac1.out
"
);
in
>>
n;
int
k
=
0
;
for
(
int
b
=
1
; b
<=
n;
++
b)
for
(
int
a
=
1
; a
<
b;
++
a)
{
if
(
!
(a
%
2
)
&&
!
(b
%
2
))
continue
;
if
(gcd(a,b)
==
1
)
{
num[k].a
=
a;
num[k].b
=
b;
num[k].val
=
(
double
)a
/
b;
k
++
;
}
}
sort(num, num
+
k);
out
<<
"
0/1\n
"
;
for
(
int
i
=
0
; i
<
k;
++
i)
out
<<
num[i].a
<<
"
/
"
<<
num[i].b
<<
endl;
out
<<
"
1/1\n
"
;
return
0
;
}
posted @
2010-11-21 00:44
小阮 阅读(105) |
评论 (0)
|
编辑
收藏
USACO 2.1.1 The Castle
/**/
/*
ID: lorelei3
TASK: castle
LANG: C++
*/
#include
<
fstream
>
using
namespace
std;
const
int
MAX
=
55
;
int
t;
int
g[MAX][MAX];
int
area[
3000
];
bool
f[MAX][MAX][
5
];
bool
floodfill(
int
x,
int
y)
{
if
(g[x][y]
!=-
1
)
return
false
;
g[x][y]
=
t;
area[t]
++
;
if
(
!
f[x][y][
1
]) floodfill(x, y
-
1
);
if
(
!
f[x][y][
2
]) floodfill(x
-
1
, y);
if
(
!
f[x][y][
3
]) floodfill(x, y
+
1
);
if
(
!
f[x][y][
4
]) floodfill(x
+
1
, y);
return
true
;
}
int
main()
{
int
i,j,k,n,m;
ifstream
in
(
"
castle.in
"
);
ofstream
out
(
"
castle.out
"
);
in
>>
m
>>
n;
for
(i
=
1
; i
<=
n;
++
i)
for
(j
=
1
; j
<=
m;
++
j)
{
in
>>
k;
if
(k
>=
8
)
{ k
-=
8
; f[i][j][
4
]
=
true
; }
if
(k
>=
4
)
{ k
-=
4
; f[i][j][
3
]
=
true
; }
if
(k
>=
2
)
{ k
-=
2
; f[i][j][
2
]
=
true
; }
if
(k
>=
1
)
{ k
-=
1
; f[i][j][
1
]
=
true
; }
g[i][j]
=
-
1
;
}
t
=
0
;
for
(i
=
1
; i
<=
n;
++
i)
for
(j
=
1
; j
<=
m;
++
j)
if
(floodfill(i,j))
t
++
;
int
max_room
=
0
;
for
(i
=
0
;i
<=
t;
++
i)
max_room
=
max_room
>
area[i]
?
max_room:area[i];
out
<<
t
<<
endl;
out
<<
max_room
<<
endl;
int
max_area
=
0
, mx
=
0
, my
=
0
, x
=
0
;
char
ch
=
0
;
for
(j
=
1
; j
<=
m;
++
j)
for
(i
=
n; i
>=
1
; i
--
)
{
if
(g[i][j]
!=
g[i
-
1
][j]
&&
i
-
1
!=
0
)
x
=
area[g[i][j]]
+
area[g[i
-
1
][j]];
if
(x
>
max_area)
{
max_area
=
x; mx
=
i; my
=
j; ch
=
'
N
'
;
}
if
(g[i][j]
!=
g[i][j
+
1
]
&&
j
+
1
<=
m)
x
=
area[g[i][j]]
+
area[g[i][j
+
1
]];
if
(x
>
max_area)
{
max_area
=
x; mx
=
i; my
=
j; ch
=
'
E
'
;
}
}
out
<<
max_area
<<
endl;
out
<<
mx
<<
"
"
<<
my
<<
"
"
<<
ch
<<
endl;
return
0
;
}
posted @
2010-11-21 00:43
小阮 阅读(128) |
评论 (0)
|
编辑
收藏
USACO 1.5.4 Checker Challenge
/**/
/*
ID: lorelei3
TASK: checker
LANG: C++
*/
#include
<
fstream
>
FILE
*
fi,
*
fo;
const
int
N
=
20
;
int
n ;
int
sum
=
0
;
int
a[
20
];
unsigned
long
int
upperlim ;
int
ps(
int
a)
//
不用 log 节省时间
{
switch
(a)
{
case
1
:
return
1
;
case
2
:
return
2
;
case
4
:
return
3
;
case
8
:
return
4
;
case
16
:
return
5
;
case
32
:
return
6
;
case
64
:
return
7
;
case
128
:
return
8
;
case
256
:
return
9
;
case
512
:
return
10
;
case
1024
:
return
11
;
case
2048
:
return
12
;
case
4096
:
return
13
;
}
}
void
test(unsigned
long
int
row, unsigned
long
int
ld, unsigned
long
int
rd,
int
depth)
{
unsigned
long
int
pos, p;
if
(row
!=
upperlim)
{
pos
=
upperlim
&
~
(row
|
ld
|
rd);
while
(pos
!=
0
)
{
p
=
pos
&
(
-
pos);
pos
=
pos
-
p;
if
(sum
<
3
)
a[depth]
=
p;
test(row
+
p, (ld
+
p)
<<
1
, (rd
+
p)
>>
1
, depth
+
1
);
}
}
else
{
sum
++
;
if
(sum
<=
3
)
{
for
(
int
i
=
0
;i
<
n
-
1
;i
++
)
fprintf(fo,
"
%d
"
,ps(a[i]));
fprintf(fo,
"
%d\n
"
,ps(a[n
-
1
]));
}
}
}
int
main(
void
)
{
fi
=
fopen(
"
checker.in
"
,
"
r
"
);
fo
=
fopen(
"
checker.out
"
,
"
w
"
);
fscanf(fi,
"
%d
"
,
&
n);
upperlim
=
(
1
<<
n)
-
1
;
test(
0
,
0
,
0
,
0
);
fprintf(fo,
"
%d\n
"
, sum);
return
0
;
}
posted @
2010-11-09 13:00
小阮 阅读(165) |
评论 (0)
|
编辑
收藏
USACO 1.5.3 SuperPrime Rib
/**/
/*
ID: lorelei3
TASK: sprime
LANG: C++
*/
#include
<
fstream
>
#include
<
math.h
>
using
namespace
std;
int
N;
int
isPrime(
int
a)
{
if
(a
==
2
)
return
0
;
for
(
int
i
=
2
; i
<=
sqrt(a);
++
i)
if
( a
%
i
==
0
)
return
0
;
return
1
;
}
void
sprime(
int
n,
int
depth)
{
if
(depth
==
N)
{
//
cout<<n<<endl;
printf(
"
%d\n
"
, n);
return
;
}
n
*=
10
;
if
(isPrime(n
+
1
))
sprime(n
+
1
, depth
+
1
);
if
(isPrime(n
+
3
))
sprime(n
+
3
, depth
+
1
);
if
(isPrime(n
+
7
))
sprime(n
+
7
, depth
+
1
);
if
(isPrime(n
+
9
))
sprime(n
+
9
, depth
+
1
);
}
int
main()
{
freopen(
"
sprime.in
"
,
"
r
"
,stdin);
freopen(
"
sprime.out
"
,
"
w
"
,stdout);
scanf(
"
%d\n
"
,
&
N);
//
cin>>N;
sprime(
2
,
1
);
sprime(
3
,
1
);
sprime(
5
,
1
);
sprime(
7
,
1
);
return
0
;
}
posted @
2010-11-09 12:59
小阮 阅读(162) |
评论 (0)
|
编辑
收藏
USACO 1.5.2 Prime Palindromes
/**/
/*
ID: lorelei3
TASK: pprime
LANG: C++
*/
#include
<
fstream
>
#include
<
iostream
>
#include
<
algorithm
>
#include
<
string
.h
>
#include
<
math.h
>
using
namespace
std;
const
int
BASE
=
10
;
const
int
MAX
=
100000
;
int
ans[MAX];
int
isPrime(
int
a)
{
int
n
=
static_cast
<
int
>
(sqrt(a));
for
(
int
i
=
2
; i
<=
n;
++
i)
if
(
!
(a
%
i))
return
0
;
return
1
;
}
int
getPal(
int
i,
int
j)
{
/**/
/*
if (j==1)
{
char a[30];
sprintf(a,"%d",i);
int len=strlen(a);
for(int k=0;k<len;k++)
a[k+len]=a[len-k-1];
a[len*2]='\0';
char* b;
return atoi(a);
//return strtol(a,&b,10);
}
if (j==0)
{
char a[30];
sprintf(a,"%d",i);
int len=strlen(a);
for(int k=0;k<len;k++)
a[k+len-1]=a[len-k-1];
a[len*2-1]='\0';
char* b;
return atoi(a);
//return strtol(a,&b,10);
}
*/
if
(j
==
1
)
{
char
a[
30
];
sprintf(a,
"
%d
"
,i);
int
len
=
strlen(a);
for
(
int
k
=
0
;k
<
len;k
++
)
a[k
+
len]
=
a[len
-
k
-
1
];
a[len
*
2
]
=
'
\0
'
;
char
*
b;
return
atoi(a);
//
return strtol(a,&b,10);
/**/
/*
char a[30];
sprintf(a, "%d", i);
int len = strlen(a);
for(int k=0; k<len; k++)
a[k+len] = a[len-k-1];
a[len*2] = '\0';
return atoi(a);
*/
//
char str[20];
//
sprintf(str, "%d", i);
//
string s(str), t(str);
//
reverse(t.begin(), t.end());
//
s.append(t);
//
return atoi(s.c_str());
}
if
(j
==
0
)
{
/**/
/*
char a[30];
sprintf(a,"%d",i);
int len=strlen(a);
for(int k=0;k<len;k++)
a[k+len-1]=a[len-k-1];
a[len*2-1]='\0';
char* b;
return atoi(a);
//return strtol(a,&b,10);
*/
char
a[
30
];
sprintf(a,
"
%d
"
, i);
int
len
=
strlen(a);
for
(
int
k
=
0
; k
<
len; k
++
)
a[k
+
len
-
1
]
=
a[len
-
k
-
1
];
a[len
*
2
-
1
]
=
'
\0
'
;
return
atoi(a);
//
char str[20];
//
sprintf(str, "%d", i);
//
string s(str), t(str);
//
t = t.substr(0, t.size()-1);
//
reverse(t.begin(), t.end());
//
s.append(t);
//
return atoi(s.c_str());
}
}
int
main()
{
int
i,j,a,b;
ifstream
in
(
"
pprime.in
"
);
ofstream
out
(
"
pprime.out
"
);
in
>>
a
>>
b;
int
t
=
0
;
for
(i
=
1
; i
<=
9999
;
++
i)
for
(j
=
0
; j
<
2
;
++
j)
{
int
x
=
getPal(i,j);
if
(isPrime(x)
&&
x
>=
a
&&
x
<=
b)
{
ans[t
++
]
=
x;
}
}
sort(ans, ans
+
t);
for
(i
=
0
; i
<
t;
++
i)
out
<<
ans[i]
<<
endl;
return
0
;
}
posted @
2010-11-09 12:58
小阮 阅读(164) |
评论 (0)
|
编辑
收藏
USACO 1.5.1 Number Triangles
/**/
/*
ID: lorelei3
TASK: numtri
LANG: C++
*/
#include
<
fstream
>
using
namespace
std;
const
int
N
=
1005
;
int
a[N][N];
int
max(
int
a,
int
b)
{
return
a
>
b
?
a:b;
}
int
main()
{
int
n,i,j;
ifstream
in
(
"
numtri.in
"
);
ofstream
out
(
"
numtri.out
"
);
in
>>
n;
for
(i
=
0
; i
<
n;
++
i)
for
(j
=
0
; j
<=
i;
++
j)
in
>>
a[i][j];
for
(i
=
n
-
2
; i
>=
0
; i
--
)
for
(j
=
0
; j
<=
i;
++
j)
a[i][j]
=
a[i][j]
+
max(a[i
+
1
][j], a[i
+
1
][j
+
1
]);
out
<<
a[
0
][
0
]
<<
endl;
return
0
;
}
posted @
2010-11-09 12:57
小阮 阅读(116) |
评论 (0)
|
编辑
收藏
USACO 1.4.4 Mother's Milk
/**/
/*
ID: lorelei3
TASK: milk3
LANG: C++
*/
#include
<
iostream
>
#include
<
fstream
>
using
namespace
std;
const
int
MAX
=
25
;
typedef
struct
State
{
int
bucket[
3
];
}
State;
int
flag[MAX][MAX][MAX];
int
full_bucket[
3
];
int
can[MAX];
State pour(State s,
int
from,
int
to)
{
int
amt
=
s.bucket[from];
if
(s.bucket[to]
+
amt
>
full_bucket[to])
amt
=
full_bucket[to]
-
s.bucket[to];
s.bucket[from]
-=
amt;
s.bucket[to]
+=
amt;
return
s;
}
void
search(State s)
{
if
(flag[s.bucket[
0
]][s.bucket[
1
]][s.bucket[
2
]])
return
;
flag[s.bucket[
0
]][s.bucket[
1
]][s.bucket[
2
]]
=
true
;
if
(s.bucket[
0
]
==
0
)
can[s.bucket[
2
]]
=
true
;
for
(
int
i
=
0
; i
<
3
;
++
i)
for
(
int
j
=
0
; j
<
3
;
++
j)
search(pour(s,i,j));
}
int
main()
{
ifstream
in
(
"
milk3.in
"
);
ofstream
out
(
"
milk3.out
"
);
in
>>
full_bucket[
0
]
>>
full_bucket[
1
]
>>
full_bucket[
2
];
State s;
s.bucket[
0
]
=
0
;
s.bucket[
1
]
=
0
;
s.bucket[
2
]
=
full_bucket[
2
];
search(s);
char
*
sep
=
""
;
for
(
int
i
=
0
; i
<
MAX;
++
i)
if
(can[i])
{
out
<<
sep
<<
i;
sep
=
"
"
;
}
out
<<
endl;
return
0
;
}
posted @
2010-11-09 12:55
小阮 阅读(174) |
评论 (0)
|
编辑
收藏
仅列出标题
共14页:
First
6
7
8
9
10
11
12
13
14
<
2011年1月
>
日
一
二
三
四
五
六
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(1)
给我留言
查看公开留言
查看私人留言
随笔分类
C++程序设计语言(6)
POJ(13)
USACO(97)
计算几何(5)
数据结构和算法(20)
网络编程(1)
随笔档案
2011年10月 (2)
2011年6月 (3)
2011年5月 (2)
2011年4月 (6)
2011年3月 (17)
2011年2月 (25)
2011年1月 (24)
2010年12月 (28)
2010年11月 (34)
文章档案
2011年2月 (3)
搜索
最新评论
1. re: USACO 4.2.3 Job Processing (平均贪心)
如何证明其正确性
--膜
2. re: USACO 5.2.2 Electric Fences (模拟退火算法)[未登录]
666@匿名
--xixi
3. re: USACO 2.3.1 The Longest Prefix [未登录]
发现一个错误,对于测试实例
AE ABC CDEF .
ABCDEFG
错误
正确答案是3
--z
4. re: USACO 4.2.3 Job Processing (平均贪心)
平均的贪心,好像没听说诶。
--怡红公子
5. re: USACO 5.4.2 Canada Tour (DP)
不明白如何去除重复的,就是怎么解决两个人交叉问题?
--zyz913614263
阅读排行榜
1. 计算几何 - 判断线段相交(转)(3661)
2. N个点中求三个点组成的三角形面积最大(2034)
3. [网络流]最小路径覆盖问题 (二分图最大匹配, 最大流)(1693)
4. ural 1297 最长回文子串(后缀数组)(1677)
5. [网络流] 方格取数问题 ( 二分图点权最大独立集, 最小割模型, 最大流)(1352)
评论排行榜
1. USACO 5.2.2 Electric Fences (模拟退火算法)(3)
2. USACO 4.2.3 Job Processing (平均贪心)(2)
3. pku 1948 Triangular Pastures (01背包)(1)
4. USACO 2.3.1 The Longest Prefix (1)
5. pku 1625 Censored! (AC自动机, DP, 高精度加法)(1)