プログラミングの美2015初戦第2戦AB
8510 ワード
タイトル1:トランプ
時間制限:2000 ms単点時限:1000 msメモリ制限:256 MBは王を含まないトランプを52枚のトランプから構成し、赤桃、黒桃、梅、ブロックの4組のトランプから構成され、各組13枚の異なる額面を記述している.52枚のカードのうち数枚を指定し、隣接するカードの額面が異なるシナリオ数を計算してください.
カードの表示方法はXYで、Xは額面値で、2、3、4、5、6、7、8、9、T、J、Q、K、Aのうちの1つである.Yは、S、H、D、Cのいずれかである.例えば2 S、2 H、TDなど.
第1の動作の整数Tをデータ群数として入力する.
その後、各グループのデータが1行を占めます.この行には、まず整数Nが含まれ、与えられたカードの枚数を表し、次にN個のスペースで区切られた文字列が含まれ、各文字列の長さは2で、1枚のカードを表す.各グループのデータのトランプはそれぞれ違います.
出力は、データのセットごとに「Case#X:Y」のように1行出力される.Xはデータ群数であり、1から始まる.Yは可能なシナリオ数であり、答えが大きい可能性があるので、モード264以降の値を出力してください.
データ範囲1≦T≦20000
ミニデータ
1 ≤ N ≤ 5
ビッグデータ
1 ≤ N ≤ 52
サンプル入力5 1 TC 2 TC TS 5 2 C AD AC JC JH 4 AC KC QC JC 6 AC AD AS JC JD KDサンプル出力Case#1:1 Case#2:0 Case#3:48 Case#4:24 Case#5:120
dp.
(配列組だと思って、長い間考えていましたが)実は【BZOJ 1079】と全く同じです.
dpの状態が1面あたり数枚残っていれば複雑度はO(413)であるが,残り数枚になって数種類の面があるとO(134)であり,残り数が同じ面が等価であるためである.
f[a][b][c][d][last]は残り1枚にa種の額面があり、残り2枚にb種の額面があることを示す...前回は残りlast枚の一種の額面が選ばれた.
遷移とは,残りのlast−1枚の面値を選択する中で選択肢が1つ少ないことであり,その他は任意であり,詳細はコードを参照する.
テーマ2:城を攻める略地
時間制限:2000 ms単点時限:1000 msメモリ制限:256 MB A、B両国の間に戦争が発生したことを説明し、B国は最短時間でA国を攻撃しなければならない.A国にはn都市(都市番号1,2,…,n)があることが知られており、都市間にはいくつかの道路が接続されている.各都市の防御力はwであり、直接その都市を攻める代価はwである.この都市の隣接都市(道路接続あり)のうち1つが占領されていれば、その都市を攻める代価は0である.
都市を占領する以外に、B国はA国の交通システムを破壊しなければならないので、少なくともk本の道路を破壊する必要があります.道路が破壊されたため、すべての都市を攻略する代価が増加する.もしB国が破壊する道を任意に選択できるとしたら、すべての都市を攻める最小の代価はいくらですか?
1行目の整数Tを入力し、データ群数を表し、以下はT群データである.
各データのセットの最初の行には、3つの整数n,m,kが含まれる.
2行目はn個の整数で、それぞれ都市1,2,...,nを占領する代価wを表す.
次にm行毎に2つの数i,jがあり、都市iと都市jとの間に道路があることを示す.
出力は、データのセットごとに1行ずつ出力され、フォーマットは「Case#X:Y」である.Xはデータ番号(1から)を表し、Yは答えです.
データ範囲1≦T≦30
k ≤ m
0 ≤ w ≤ 108
ミニデータ
1 ≤ n ≤ 1000
0 ≤ m ≤ 5000
ビッグデータ
1 ≤ n ≤ 106
0 ≤ m ≤ 106
サンプル入力2 4 4 4 2 6 5 3 4 1 2 1 3 3 3 2 4 4 4 4 6 5 3 4 1 2 3 2 4サンプル出力Case#1:7 Case#2:18
欲張る.
各連通ブロックでは、重み値が最も小さいものを選択して占領し、必ず最適である.
すなわち、重み値が大きいものは、連通ブロックから分離しないほうがよい.
法一:まずansを重みの総和とし,重みの降順に並べ,大きな使用辺を連通ブロックに加え,ansはm−k辺をすべて使い切るまで大きな重み値を減算する.(注意連通ブロック内の最小ポイントの重み値は外せません)
法2:各連通ブロックの中で木の上の辺を除いてすべて削除することができて、k本の辺を削除するかどうかを見て、もし足りないならば連通ブロックの中で最小の重みの点を除いた点を並べ替えて、解答にこの重みの値(彼が独立したため)を加えさせます;k本の辺を削除するまで.
時間制限:2000 ms単点時限:1000 msメモリ制限:256 MBは王を含まないトランプを52枚のトランプから構成し、赤桃、黒桃、梅、ブロックの4組のトランプから構成され、各組13枚の異なる額面を記述している.52枚のカードのうち数枚を指定し、隣接するカードの額面が異なるシナリオ数を計算してください.
カードの表示方法はXYで、Xは額面値で、2、3、4、5、6、7、8、9、T、J、Q、K、Aのうちの1つである.Yは、S、H、D、Cのいずれかである.例えば2 S、2 H、TDなど.
第1の動作の整数Tをデータ群数として入力する.
その後、各グループのデータが1行を占めます.この行には、まず整数Nが含まれ、与えられたカードの枚数を表し、次にN個のスペースで区切られた文字列が含まれ、各文字列の長さは2で、1枚のカードを表す.各グループのデータのトランプはそれぞれ違います.
出力は、データのセットごとに「Case#X:Y」のように1行出力される.Xはデータ群数であり、1から始まる.Yは可能なシナリオ数であり、答えが大きい可能性があるので、モード264以降の値を出力してください.
データ範囲1≦T≦20000
ミニデータ
1 ≤ N ≤ 5
ビッグデータ
1 ≤ N ≤ 52
サンプル入力5 1 TC 2 TC TS 5 2 C AD AC JC JH 4 AC KC QC JC 6 AC AD AS JC JD KDサンプル出力Case#1:1 Case#2:0 Case#3:48 Case#4:24 Case#5:120
dp.
(配列組だと思って、長い間考えていましたが)実は【BZOJ 1079】と全く同じです.
dpの状態が1面あたり数枚残っていれば複雑度はO(413)であるが,残り数枚になって数種類の面があるとO(134)であり,残り数が同じ面が等価であるためである.
f[a][b][c][d][last]は残り1枚にa種の額面があり、残り2枚にb種の額面があることを示す...前回は残りlast枚の一種の額面が選ばれた.
遷移とは,残りのlast−1枚の面値を選択する中で選択肢が1つ少ないことであり,その他は任意であり,詳細はコードを参照する.
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <map>
#include <vector>
#include <iostream>
#include <set>
#define ull unsigned long long
using namespace std;
ull f[14][14][14][14][5];
char s[10];
int T,n,c[14],sum[10];
ull dfs(int a,int b,int c,int d,int last)
{
if (f[a][b][c][d][last]) return f[a][b][c][d][last];
ull tmp=0;
if (a) tmp+=dfs(a-1,b,c,d,1)*(a-(last==2));
if (b) tmp+=dfs(a+1,b-1,c,d,2)*(b-(last==3));
if (c) tmp+=dfs(a,b+1,c-1,d,3)*(c-(last==4));
if (d) tmp+=dfs(a,b,c+1,d-1,4)*d;
f[a][b][c][d][last]=tmp;
return tmp;
}
int main()
{
cin>>T;
for (int t=1;t<=T;t++)
{
printf("Case #%d: ",t);
scanf("%d",&n);
for (int i=1;i<=13;i++)
c[i]=0;
for (int i=1;i<=n;i++)
{
scanf("%s",s);
if (s[0]-'0'>=2&&s[0]-'0'<=9)
c[s[0]-'0']++;
if (s[0]=='A') c[1]++;
if (s[0]=='T') c[10]++;
if (s[0]=='J') c[11]++;
if (s[0]=='Q') c[12]++;
if (s[0]=='K') c[13]++;
}
for (int i=1;i<=10;i++)
sum[i]=0;
for (int i=1;i<=13;i++)
sum[c[i]]++;
for (int i=1;i<=4;i++)
f[0][0][0][0][i]=1;
ull ans=dfs(sum[1],sum[2],sum[3],sum[4],0);
for (int i=1;i<=13;i++)
if (c[i]>1)
{
for (int j=2;j<=c[i];j++)
ans*=j;
}
printf("%llu
",ans);
}
return 0;
}
テーマ2:城を攻める略地
時間制限:2000 ms単点時限:1000 msメモリ制限:256 MB A、B両国の間に戦争が発生したことを説明し、B国は最短時間でA国を攻撃しなければならない.A国にはn都市(都市番号1,2,…,n)があることが知られており、都市間にはいくつかの道路が接続されている.各都市の防御力はwであり、直接その都市を攻める代価はwである.この都市の隣接都市(道路接続あり)のうち1つが占領されていれば、その都市を攻める代価は0である.
都市を占領する以外に、B国はA国の交通システムを破壊しなければならないので、少なくともk本の道路を破壊する必要があります.道路が破壊されたため、すべての都市を攻略する代価が増加する.もしB国が破壊する道を任意に選択できるとしたら、すべての都市を攻める最小の代価はいくらですか?
1行目の整数Tを入力し、データ群数を表し、以下はT群データである.
各データのセットの最初の行には、3つの整数n,m,kが含まれる.
2行目はn個の整数で、それぞれ都市1,2,...,nを占領する代価wを表す.
次にm行毎に2つの数i,jがあり、都市iと都市jとの間に道路があることを示す.
出力は、データのセットごとに1行ずつ出力され、フォーマットは「Case#X:Y」である.Xはデータ番号(1から)を表し、Yは答えです.
データ範囲1≦T≦30
k ≤ m
0 ≤ w ≤ 108
ミニデータ
1 ≤ n ≤ 1000
0 ≤ m ≤ 5000
ビッグデータ
1 ≤ n ≤ 106
0 ≤ m ≤ 106
サンプル入力2 4 4 4 2 6 5 3 4 1 2 1 3 3 3 2 4 4 4 4 6 5 3 4 1 2 3 2 4サンプル出力Case#1:7 Case#2:18
欲張る.
各連通ブロックでは、重み値が最も小さいものを選択して占領し、必ず最適である.
すなわち、重み値が大きいものは、連通ブロックから分離しないほうがよい.
法一:まずansを重みの総和とし,重みの降順に並べ,大きな使用辺を連通ブロックに加え,ansはm−k辺をすべて使い切るまで大きな重み値を減算する.(注意連通ブロック内の最小ポイントの重み値は外せません)
法2:各連通ブロックの中で木の上の辺を除いてすべて削除することができて、k本の辺を削除するかどうかを見て、もし足りないならば連通ブロックの中で最小の重みの点を除いた点を並べ替えて、解答にこの重みの値(彼が独立したため)を加えさせます;k本の辺を削除するまで.