ZZULI-Summer Training Contest(Six)解題レポート
51108 ワード
試合の住所:
http://acm.hdu.edu.cn/diy/contest_show.php?cid=7262
1001 --HDU2203
秒殺型水題
strcpy strcat strstrstr関数の応用を強固にする
1002 --HDU1846
ゲーム問題
最も基礎的なゲームは、法則が発見されやすい.
1003 –HDU1071
簡単な数学の問題
放物線y=a*x^2+b*x+c、直線y=kx+mとする.与えられた3点から係数a,b,c,k,mを決定した.
次に定積分を用いて面積式を算出すればよい.
注意問題で与えられたP 1点は放物線の頂点であることを保証する.
1004 –HDU2986
文字列処理問題
みんなのコード能力を鍛えて、この問題は精度の問題に注意しなければなりません.
1005 –HDU1422
簡単DP問題
みんなはMax Sumという問題に触れたことがあるでしょう.この問題の構想はその問題を参考にすることができます.
1006 –HDU1078
DFS+DP
現在の状態の値は、状態を検索する最適値で決定することができるので、現在の状態の最適解を決定するために、サブ問題を深く検索して決定する最適解がある.
1007 –HDU1068
二分図最大一致
二分図最大マッチングを用いて最大独立セットを決定し,ここでは今後学習させるためである.
1008 –HDU1403
接尾辞配列
接尾辞配列を用いて最長共通接頭辞配列height配列を求め,最長共通接頭辞の定義から,答えは2つの順位が隣接する接尾辞の最長共通接頭辞であり,2つの列に属するか否かを判断すればOKである.
1009 –HDU1075
ディクショナリツリー
簡単な辞書ツリーアプリケーションです.こっそり教えて、この問題はSTL mapでも水で渡ることができます......
1006100701008の問題のコードを添付します
HDU1078
コード#コード#
HDU1068
コード#コード#
HDU 1403はlookerに由来する
コード#コード#
http://acm.hdu.edu.cn/diy/contest_show.php?cid=7262
1001 --HDU2203
秒殺型水題
strcpy strcat strstrstr関数の応用を強固にする
1002 --HDU1846
ゲーム問題
最も基礎的なゲームは、法則が発見されやすい.
1003 –HDU1071
簡単な数学の問題
放物線y=a*x^2+b*x+c、直線y=kx+mとする.与えられた3点から係数a,b,c,k,mを決定した.
次に定積分を用いて面積式を算出すればよい.
注意問題で与えられたP 1点は放物線の頂点であることを保証する.
1004 –HDU2986
文字列処理問題
みんなのコード能力を鍛えて、この問題は精度の問題に注意しなければなりません.
1005 –HDU1422
簡単DP問題
みんなはMax Sumという問題に触れたことがあるでしょう.この問題の構想はその問題を参考にすることができます.
1006 –HDU1078
DFS+DP
現在の状態の値は、状態を検索する最適値で決定することができるので、現在の状態の最適解を決定するために、サブ問題を深く検索して決定する最適解がある.
1007 –HDU1068
二分図最大一致
二分図最大マッチングを用いて最大独立セットを決定し,ここでは今後学習させるためである.
1008 –HDU1403
接尾辞配列
接尾辞配列を用いて最長共通接頭辞配列height配列を求め,最長共通接頭辞の定義から,答えは2つの順位が隣接する接尾辞の最長共通接頭辞であり,2つの列に属するか否かを判断すればOKである.
1009 –HDU1075
ディクショナリツリー
簡単な辞書ツリーアプリケーションです.こっそり教えて、この問題はSTL mapでも水で渡ることができます......
1006100701008の問題のコードを添付します
HDU1078
コード#コード#
#include
<
stdio.h
>
int
map[
101
][
101
];
int
dp[
101
][
101
];
int
dir[
4
][
2
]
=
{{
1
,
0
},{
0
,
1
},{
-
1
,
0
},{
0
,
-
1
}};
int
n,k;
int
dfs(
int
x,
int
y)
//
{
int
i,j,a,b,max
=
0
;
if
(dp[x][y])
return
dp[x][y];
for
(i
=
1
;i
<=
k;i
++
)
//
1 k
{
for
(j
=
0
;j
<
4
;j
++
)
//
{
a
=
x
+
dir[j][
0
]
*
i;
b
=
y
+
dir[j][
1
]
*
i;
if
(a
>=
0
&&
a
<
n
&&
b
>=
0
&&
b
<
n
&&
map[a][b]
>
map[x][y])
{
int
tmp
=
dfs(a,b);
//
if
(max
<
tmp)
//
max
=
tmp;
}
}
}
dp[x][y]
=
map[x][y]
+
max;
//
return
dp[x][y];
}
int
main()
{
int
i,j;
while
(scanf(
"
%d%d
"
,
&
n,
&
k),n
+
k
+
2
)
{
for
(i
=
0
;i
<
n;i
++
)
for
(j
=
0
;j
<
n;j
++
)
scanf(
"
%d
"
,
&
map[i][j]), dp[i][j]
=
0
;
printf(
"
%d
"
,dfs(
0
,
0
));
}
return
0
;
}
HDU1068
コード#コード#
#include
<
stdio.h
>
#include
<
string
.h
>
#define
N 1000
int
map[N][N];
int
link[N],useif[N];
int
n;
int
can(
int
t)
{
int
i;
for
(i
=
0
;i
<
n;i
++
)
{
if
(useif[i]
==
0
&&
map[t][i])
{
useif[i]
=
1
;
if
(link[i]
==-
1
||
can(link[i]))
{
link[i]
=
t;
return
1
;
}
}
}
return
0
;
}
int
maxmatch()
{
int
i,num
=
0
;
memset(link,
-
1
,
sizeof
(link));
for
(i
=
0
;i
<
n;i
++
)
{
memset(useif,
0
,
sizeof
(useif));
if
(can(i))
num
++
;
}
return
num;
}
int
main()
{
int
i,a,b,t;
while
(scanf(
"
%d
"
,
&
n)
!=
EOF)
{
memset(map,
0
,
sizeof
(map));
for
(i
=
0
;i
<
n;i
++
)
{
scanf(
"
%d: (%d)
"
,
&
a,
&
t);
while
(t
--
)
{
scanf(
"
%d
"
,
&
b);
map[a][b]
=
1
;
}
}
printf(
"
%d
"
,n
-
maxmatch()
/
2
);
}
return
0
;
}
HDU 1403はlookerに由来する
コード#コード#
#include
<
stdio.h
>
#include
<
string
.h
>
#define
maxm 200015
#define
maxn 200015
int
sa[maxn],height[maxn],bar[maxm],Rank[maxn],Rank_f[maxn],Result_s[maxn];
bool
cmp(
int
*
r,
int
a,
int
b,
int
len)
{
return
r[a]
==
r[b]
&&
r[a
+
len]
==
r[b
+
len];
}
void
get_sa(
int
*
r,
int
n)
{
int
i,j,p,
*
rank
=
Rank,
*
rank_f
=
Rank_f,
*
result_s
=
Result_s,
*
t,m
=
300
;
for
(i
=
0
; i
<=
m; i
++
) bar[i]
=
0
;
for
(i
=
0
; i
<
n; i
++
) bar[rank[i]
=
r[i]]
++
;
for
(i
=
0
; i
<
m; i
++
) bar[i
+
1
]
+=
bar[i];
for
(i
=
n
-
1
; i
>=
0
; i
--
) sa[
--
bar[rank[i]]]
=
i;
for
(j
=
1
,p
=
1
; p
<
n; j
*=
2
,m
=
p){
for
(p
=
0
,i
=
n
-
j; i
<
n; i
++
) result_s[p
++
]
=
i;
for
(i
=
0
; i
<
n; i
++
)
if
(sa[i]
>=
j) result_s[p
++
]
=
sa[i]
-
j;
for
(i
=
0
; i
<
n; i
++
) rank_f[i]
=
rank[result_s[i]];
for
(i
=
0
; i
<=
m; i
++
) bar[i]
=
0
;
for
(i
=
0
; i
<
n; i
++
) bar[rank_f[i]]
++
;
for
(i
=
0
; i
<
m; i
++
) bar[i
+
1
]
+=
bar[i];
for
(i
=
n
-
1
; i
>=
0
; i
--
) sa[
--
bar[rank_f[i]]]
=
result_s[i];
t
=
result_s; result_s
=
rank; rank
=
t;
for
(rank[sa[
0
]]
=
0
,i
=
1
,p
=
1
; i
<
n; i
++
)
rank[sa[i]]
=
cmp(result_s,sa[i],sa[i
-
1
],j)
?
p
-
1
:p
++
;
}
}
void
get_height(
int
*
r,
int
n)
{
int
i,j,
*
rank
=
Rank,len
=
0
;
for
(i
=
0
; i
<
n; i
++
) rank[sa[i]]
=
i;
height[
0
]
=
0
;
for
(i
=
0
; i
<
n
-
1
; i
++
){
if
(len
!=
0
) len
--
;
for
(j
=
sa[rank[i]
-
1
]; r[j
+
len]
==
r[i
+
len]; len
++
);
height[rank[i]]
=
len;
}
}
void
solve(
int
len,
int
n)
{
int
i,max
=
0
;
for
(i
=
3
; i
<
n; i
++
)
if
(height[i]
>
max)
if
((sa[i]
>
len
&&
sa[i
-
1
]
<
len)
||
(sa[i]
<
len
&&
sa[i
-
1
]
>
len))
max
=
height[i];
printf (
"
%d
"
,max);
}
int
main()
{
int
i,r[
200010
];
char
str1[
100010
],str2[
100010
];
memset(str1,
0
,
sizeof
(str1)); memset(str2,
0
,
sizeof
(str2));
while
(scanf (
"
%s%s
"
,
&
str1,
&
str2)
!=
EOF)
{
int
len1
=
strlen(str1),len2
=
strlen(str2);
for
(i
=
0
; i
<
len1; i
++
) r[i]
=
str1[i]; r[len1
++
]
=
'
$
'
;
for
(i
=
0
; i
<
len2; i
++
) r[i
+
len1]
=
str2[i]; r[len1
+
len2
++
]
=
'
#
'
;
int
len
=
len1
+
len2; get_sa(r,len); get_height(r,len);
solve(len1
-
1
,len);
memset(str1,
0
,
sizeof
(str1)); memset(str2,
0
,
sizeof
(str2));
}
return
0
;
}