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


コード#コード#

   
     
#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 ;
}