「亜信科学技術杯」南郵第7回大学生プログラム設計コンテストのネット予選(KL題解)
21840 ワード
「亜信科学技術杯」南郵第7回大学生プログラム設計コンテストのネット予選(KL題解)
1回目の出題は、やはり背負い込みました.L問題はデータの問題で、2つの間違った方法acをさせました.それぞれ、H<0の時に前日に花(wa、考え方が間違っているはずです)を送り、2つ目はdfsの(TLEのはずです)ですが、データが小さすぎます.だから、強引に暖かく送ったつもりですが、みんなを誤解させたくないので、暇があれば考えてみてください.
まずK題です.
法師
時間制限(通常/Java):
1000 MS/
3000 MS
実行メモリ制限:65536 KByte
合計コミット:175テスト合格:30
タイトルの説明
法師といえば、もろい体と強い爆発力が第一反応かもしれない.確かに、「炉石伝説」では、法師が最もダメージの高い単体法術である炎爆術と、同じ高ダメージの火球術を持っている.しかし、法師はそれに限らず、この2枚の火系法術が法師の爆発を代表しているとすれば.氷系法術は法師の制御を代表し、氷霜新星、氷錐術、吹雪、寒氷矢は相手を凍結させることができる.
カード1枚につき一定のダメージを与えるとともに、一定の法力水晶を費やす.法力水晶が足りないときは、相応のカードを出すことはできません.
簡単にするために、私たちは以下のカードしか考えていません.
寒氷矢:2点の法力水晶を消耗し、1つのキャラクターに3点のダメージを与え、凍結させる.
氷銃術:1点の法力水晶を消費し、1つのキャラクターを凍結させ、凍結された場合は4点のダメージを与えるように変更します.
火球術:法力水晶を4点消費し、6点ダメージを与える.
炎爆術:10時の法力水晶を消耗し、10時の傷害をもたらす.
今、今持っている法力水晶と、手に持っているこの4種類のカードの数(0かもしれない)を教えて、敵の英雄にどれだけのダメージを与えることができるかを聞いてみましょう.
入力
第1の挙動は正の整数Tであり、Tグループデータがあることを示す.
各データの最初の行には1つの整数があります.nは、現在所有している法力水晶の個数0<=n<=10を表します.
第2の挙動の4つの整数a,b,c,dは、それぞれ、寒氷矢、氷銃術、火球術、炎爆術を有する数を示す.0<=a,b,c,d<=10.
しゅつりょく
1つの整数は、最大のダメージ値を表します.
サンプル入力
290 0 3 052 2 1 1
サンプル出力
1211
テーマソース
NUPT
タイトル:
今持っている法力水晶(n)と、手に持っている4種類のカードの数(0かもしれない)を教えて、敵の英雄にどれだけのダメージを与えることができるかを聞いてみましょう.
ps:凍結の特効は、凍結するとずっと凍結することです.
問題:
1.水の問題にしたい人は、みんなを困らせたくないので、データの範囲は<=10で、直接四重循環暴力でいいので、最後に凍ったことについて判断します.(寒氷矢がなければ、まず氷銃術を無駄にしなければならない)
2.データ範囲が大きければ、暴力がTLEになるので、リュックサックの発想(ダイナミックプランニングの一種)で、火の玉術と炎爆術を前処理することも考えられます.
dp[i]を取得し、i点法力水晶を使用したことで最大のダメージを与えることができることを示した上で、寒氷矢と氷銃術を考慮した.
2.1残りの法力水晶が十分であれば、一緒に加えます.
2.2余剰法力が不足している場合は、寒氷矢を使用する場合と使用しない場合の2つに分けられます.
2.2.1氷の矢を使わないで、氷の銃撃術の傷害をプラスします.
2.2.2氷の矢を使うなら、まず氷の矢を出して、それから氷の銃術(氷の問題にかかわらず、氷の銃術の性価比が高い)を優先して、それから氷の矢を加えます.
スレッド:
ここではまず暴力法の目安を示し、興味のある学生は、データが比較的大きい(1<=n,a,b,c,d<=10000000)場合、上記の方法でどのように解決するかを試してみることができます.
そしてL:
花を贈る
時間制限(通常/Java):
1000 MS/
3000 MS
実行メモリ制限:65536 KByte
総提出:117試験合格:42
タイトルの説明
萌え妹紙は普通きれいな花が好きです.いろいろな祝日になると、彼女たちは花をプレゼントしたいと思っています.もしあなたが妹の紙を持っている人で、いつも妹に紙の花をあげないと、結果がわかります.
もちろん、妹の紙はすべて道理にかなっていて、ある何度かあなたの木が花を送ったからといって、あなたの良い人カードを出すことはありません.王童靴は倹約(けち)な人としてこの道理を知っているので、妹紙がいい人カードを出さない前提で、できるだけ少ない花を送りたいと思っています.
簡単にするために、妹紙の幸福指数H(初期は0)を定義します.ある日幸福指数Hが0未満であれば...
もしある日、妹紙が花を受け取ったら、幸福指数Hはaiを増やし、受け取っていなければbiを下げる.日によっては幸福指数の増加が異なる可能性があります.例えば、2月14日に花を贈ると2月15日より効果的です.
つまり、総日数n(1<=n<=365)を教えて、毎日花幸福指数の増加値ai(1<=ai<=10)を受け取って、花幸福指数の低下値biを受け取っていないで、妹紙の幸福指数Hをずっと>=0にするために、王童靴は少なくとも妹紙に何輪の花を送ります.
入力
第1の挙動は正の整数Tであり、Tグループデータがあることを示す.
データのセットの最初の行には1つの整数があります.nは、合計日数1<=n<=365を表します.
第2の挙動n個の整数aiは、i日目に受信した花幸福指数の増加値を表し、1<=ai<=10である.第3の挙動n個の整数biは、i日目に花幸福指数の低下値が受信されなかったことを示し、1<=bi<=10である.
しゅつりょく
1つの整数は、少なくともどれだけの花を贈る必要があるかを示します.
サンプル入力
213455 2 10 1 11 1 1 5 5
サンプル出力
12
テーマソース
NUPT
この問題は皆さんに申し訳ありませんが、L問題はデータの問題で、2つの間違った方法acをさせました.それぞれ:H<0の時に前日に花を送ります(wa、考え方が間違っています)、2つ目はdfsの(TLEのはずです)、しかしデータが小さすぎます.だから、強引に暖かさを送りますが、みんなを誤解したくないので、みんなは暇があれば考えて正解~~
タイトル:
総日数n(1<=n<=365)を教えて、妹紙の幸福指数Hは初めは0で、毎日花幸福指数の増加値ai(1<=ai<=10)を受け取って、花幸福指数の低下値biを受け取っていないで、妹紙の幸福指数Hをずっと>=0にするために、王童靴は少なくとも妹紙に何輪の花を送ります.
問題:
1.もともとダイナミックな計画のテーマを思いついたのです.
つまり、毎日2つの選択肢しかなく、送るか送らないかです.では、dp[i][j]は、前日、妹紙の幸福値をjに必要な最小限の花の数にすることを意味する.最後に最後の日を列挙すればいい.
移行方程式も難しくありません.
花を贈ると:dp[i][j+a[i]=min(dp[i][j+a[i],dp[i-1][j]+1);
花を送らないと:dp[i][j-b[i]=min(dp[i][j-b[i],dp[i-1][j]);
2.この問題は欲張りな考えでもいいですが、簡単ではありません.H<0の時に前日に花をあげます.当然、H<0の場合は前に花を贈っていない日を取り、花を贈った場合は、花の収益が最も大きい日を選んで花を贈ります.
(妹紙の幸福値を最大にすることができ、ここでの増加はa[i]ではなくa[i]+b[i])
具体的なインプリメンテーションは、優先キューを使用することができる.H>=0の場合、H-=b[i]を選択せず、a[i]+b[i]の値を優先キューに格納します.
(この日に花を贈るようにすれば、妹紙の幸福指数はb[i]下がるどころか、a[i]上昇し、収益はa[i]+b[i])になるからだ.
次に、h<0の場合、優先キューのキューヘッダ要素をキューから出てtemp、h+=tempと記す
同様に、ここではダイナミックな計画のスケジュールだけを提供し、正しい貪欲なプログラムをどのように書くかを考えてほしい.データ範囲が変化すると、1<=n<=10000000、1<=ai<=100000、1<=bi<=100000となる.
転載先:https://www.cnblogs.com/njczy2010/p/4378596.html
1回目の出題は、やはり背負い込みました.L問題はデータの問題で、2つの間違った方法acをさせました.それぞれ、H<0の時に前日に花(wa、考え方が間違っているはずです)を送り、2つ目はdfsの(TLEのはずです)ですが、データが小さすぎます.だから、強引に暖かく送ったつもりですが、みんなを誤解させたくないので、暇があれば考えてみてください.
まずK題です.
法師
時間制限(通常/Java):
1000 MS/
3000 MS
実行メモリ制限:65536 KByte
合計コミット:175テスト合格:30
タイトルの説明
法師といえば、もろい体と強い爆発力が第一反応かもしれない.確かに、「炉石伝説」では、法師が最もダメージの高い単体法術である炎爆術と、同じ高ダメージの火球術を持っている.しかし、法師はそれに限らず、この2枚の火系法術が法師の爆発を代表しているとすれば.氷系法術は法師の制御を代表し、氷霜新星、氷錐術、吹雪、寒氷矢は相手を凍結させることができる.
カード1枚につき一定のダメージを与えるとともに、一定の法力水晶を費やす.法力水晶が足りないときは、相応のカードを出すことはできません.
簡単にするために、私たちは以下のカードしか考えていません.
寒氷矢:2点の法力水晶を消耗し、1つのキャラクターに3点のダメージを与え、凍結させる.
氷銃術:1点の法力水晶を消費し、1つのキャラクターを凍結させ、凍結された場合は4点のダメージを与えるように変更します.
火球術:法力水晶を4点消費し、6点ダメージを与える.
炎爆術:10時の法力水晶を消耗し、10時の傷害をもたらす.
今、今持っている法力水晶と、手に持っているこの4種類のカードの数(0かもしれない)を教えて、敵の英雄にどれだけのダメージを与えることができるかを聞いてみましょう.
入力
第1の挙動は正の整数Tであり、Tグループデータがあることを示す.
各データの最初の行には1つの整数があります.nは、現在所有している法力水晶の個数0<=n<=10を表します.
第2の挙動の4つの整数a,b,c,dは、それぞれ、寒氷矢、氷銃術、火球術、炎爆術を有する数を示す.0<=a,b,c,d<=10.
しゅつりょく
1つの整数は、最大のダメージ値を表します.
サンプル入力
290 0 3 052 2 1 1
サンプル出力
1211
テーマソース
NUPT
タイトル:
今持っている法力水晶(n)と、手に持っている4種類のカードの数(0かもしれない)を教えて、敵の英雄にどれだけのダメージを与えることができるかを聞いてみましょう.
ps:凍結の特効は、凍結するとずっと凍結することです.
問題:
1.水の問題にしたい人は、みんなを困らせたくないので、データの範囲は<=10で、直接四重循環暴力でいいので、最後に凍ったことについて判断します.(寒氷矢がなければ、まず氷銃術を無駄にしなければならない)
2.データ範囲が大きければ、暴力がTLEになるので、リュックサックの発想(ダイナミックプランニングの一種)で、火の玉術と炎爆術を前処理することも考えられます.
dp[i]を取得し、i点法力水晶を使用したことで最大のダメージを与えることができることを示した上で、寒氷矢と氷銃術を考慮した.
2.1残りの法力水晶が十分であれば、一緒に加えます.
2.2余剰法力が不足している場合は、寒氷矢を使用する場合と使用しない場合の2つに分けられます.
2.2.1氷の矢を使わないで、氷の銃撃術の傷害をプラスします.
2.2.2氷の矢を使うなら、まず氷の矢を出して、それから氷の銃術(氷の問題にかかわらず、氷の銃術の性価比が高い)を優先して、それから氷の矢を加えます.
スレッド:
ここではまず暴力法の目安を示し、興味のある学生は、データが比較的大きい(1<=n,a,b,c,d<=10000000)場合、上記の方法でどのように解決するかを試してみることができます.
1 #include
2 #include
3 using namespace std;
4 int main()
5 {
6 int T;
7 scanf("%d", &T);
8 while(T--)
9 {
10 int a, b, c, d, n;
11 scanf("%d", &n);
12 scanf("%d %d %d %d", &a, &b, &c, &d);
13 int ans = 0;
14
15 for(int i = 0; i <= a; i++)
16 {
17 for(int j = 0; j <= b; j++)
18 {
19 for(int k = 0; k <= c; k++)
20 {
21 for(int l = 0; l <= d; l++)
22 {
23 if(2 * i + 1 * j + 4 * k + 10 * l <= n)
24 {
25 if(i > 0) //
26 ans = max(ans, 3 * i + 4 * j + 6 * k + 10 * l);
27 else
28 {
29 if(j >= 1) //
30 ans = max(ans, 4 * (j - 1) + 6 * k + 10 * l);
31 else
32 ans = max(ans, 6 * k + 10 * l);
33 }
34 }
35 }
36 }
37 }
38 }
39 printf("%d
", ans);
40 }
41 } そしてL:
花を贈る
時間制限(通常/Java):
1000 MS/
3000 MS
実行メモリ制限:65536 KByte
総提出:117試験合格:42
タイトルの説明
萌え妹紙は普通きれいな花が好きです.いろいろな祝日になると、彼女たちは花をプレゼントしたいと思っています.もしあなたが妹の紙を持っている人で、いつも妹に紙の花をあげないと、結果がわかります.
もちろん、妹の紙はすべて道理にかなっていて、ある何度かあなたの木が花を送ったからといって、あなたの良い人カードを出すことはありません.王童靴は倹約(けち)な人としてこの道理を知っているので、妹紙がいい人カードを出さない前提で、できるだけ少ない花を送りたいと思っています.
簡単にするために、妹紙の幸福指数H(初期は0)を定義します.ある日幸福指数Hが0未満であれば...
もしある日、妹紙が花を受け取ったら、幸福指数Hはaiを増やし、受け取っていなければbiを下げる.日によっては幸福指数の増加が異なる可能性があります.例えば、2月14日に花を贈ると2月15日より効果的です.
つまり、総日数n(1<=n<=365)を教えて、毎日花幸福指数の増加値ai(1<=ai<=10)を受け取って、花幸福指数の低下値biを受け取っていないで、妹紙の幸福指数Hをずっと>=0にするために、王童靴は少なくとも妹紙に何輪の花を送ります.
入力
第1の挙動は正の整数Tであり、Tグループデータがあることを示す.
データのセットの最初の行には1つの整数があります.nは、合計日数1<=n<=365を表します.
第2の挙動n個の整数aiは、i日目に受信した花幸福指数の増加値を表し、1<=ai<=10である.第3の挙動n個の整数biは、i日目に花幸福指数の低下値が受信されなかったことを示し、1<=bi<=10である.
しゅつりょく
1つの整数は、少なくともどれだけの花を贈る必要があるかを示します.
サンプル入力
213455 2 10 1 11 1 1 5 5
サンプル出力
12
テーマソース
NUPT
この問題は皆さんに申し訳ありませんが、L問題はデータの問題で、2つの間違った方法acをさせました.それぞれ:H<0の時に前日に花を送ります(wa、考え方が間違っています)、2つ目はdfsの(TLEのはずです)、しかしデータが小さすぎます.だから、強引に暖かさを送りますが、みんなを誤解したくないので、みんなは暇があれば考えて正解~~
タイトル:
総日数n(1<=n<=365)を教えて、妹紙の幸福指数Hは初めは0で、毎日花幸福指数の増加値ai(1<=ai<=10)を受け取って、花幸福指数の低下値biを受け取っていないで、妹紙の幸福指数Hをずっと>=0にするために、王童靴は少なくとも妹紙に何輪の花を送ります.
問題:
1.もともとダイナミックな計画のテーマを思いついたのです.
つまり、毎日2つの選択肢しかなく、送るか送らないかです.では、dp[i][j]は、前日、妹紙の幸福値をjに必要な最小限の花の数にすることを意味する.最後に最後の日を列挙すればいい.
移行方程式も難しくありません.
花を贈ると:dp[i][j+a[i]=min(dp[i][j+a[i],dp[i-1][j]+1);
花を送らないと:dp[i][j-b[i]=min(dp[i][j-b[i],dp[i-1][j]);
2.この問題は欲張りな考えでもいいですが、簡単ではありません.H<0の時に前日に花をあげます.当然、H<0の場合は前に花を贈っていない日を取り、花を贈った場合は、花の収益が最も大きい日を選んで花を贈ります.
(妹紙の幸福値を最大にすることができ、ここでの増加はa[i]ではなくa[i]+b[i])
具体的なインプリメンテーションは、優先キューを使用することができる.H>=0の場合、H-=b[i]を選択せず、a[i]+b[i]の値を優先キューに格納します.
(この日に花を贈るようにすれば、妹紙の幸福指数はb[i]下がるどころか、a[i]上昇し、収益はa[i]+b[i])になるからだ.
次に、h<0の場合、優先キューのキューヘッダ要素をキューから出てtemp、h+=tempと記す
同様に、ここではダイナミックな計画のスケジュールだけを提供し、正しい貪欲なプログラムをどのように書くかを考えてほしい.データ範囲が変化すると、1<=n<=10000000、1<=ai<=100000、1<=bi<=100000となる.
1 #include
2 #include
3 #include
4 #include
5 #include
6
7 #define ll long long
8 int const N = 405;
9 int const M = 205;
10 int const inf = 1000000000;
11 ll const mod = 1000000007;
12
13 using namespace std;
14
15 int T;
16 int n;
17 int dp[N][10*N];
18 int mi;
19 int a[N];
20 int b[N];
21 int suma;
22
23 void ini()
24 {
25 int i;
26 mi=inf;
27 suma=0;
28 scanf("%d",&n);
29 memset(dp,-1,sizeof(dp));
30 dp[0][0]=0;
31 for(i=1;i<=n;i++){
32 scanf("%d",&a[i]);
33 suma+=a[i];
34 }
35 for(i=1;i<=n;i++){
36 scanf("%d",&b[i]);
37 }
38 }
39
40 void solve()
41 {
42 int i,j;
43 int temp;
44 for(i=1;i<=n;i++){
45 for(j=0;j<=suma-a[i];j++){
46 if(dp[i-1][j]==-1) continue;
47 temp=j+a[i];
48 if(dp[i][temp]==-1){
49 dp[i][temp]=dp[i-1][j]+1;
50 }
51 else{
52 dp[i][temp]=min(dp[i][temp],dp[i-1][j]+1);
53 }
54 }
55
56 for(j=b[i];j<=suma;j++){
57 if(dp[i-1][j]==-1) continue;
58 temp=j-b[i];
59 if(dp[i][temp]==-1){
60 dp[i][temp]=dp[i-1][j];
61 }
62 else{
63 dp[i][temp]=min(dp[i][temp],dp[i-1][j]);
64 }
65 }
66 }
67
68 for(j=0;j<=suma;j++){
69 if(dp[n][j]==-1) continue;
70 mi=min(mi,dp[n][j]);
71 }
72 }
73
74 void out()
75 {
76 printf("%d
",mi);
77 }
78
79 int main()
80 {
81 //freopen("data.in","r",stdin);
82 scanf("%d",&T);
83 for(int cnt=1;cnt<=T;cnt++)
84 //while(T--)
85 //while(scanf("%d",&n)!=EOF)
86 {
87 ini();
88 solve();
89 out();
90 }
91 } 転載先:https://www.cnblogs.com/njczy2010/p/4378596.html