FZU ICPC 2020冬休みトレーニング5——ランキング
8879 ワード
P 177【テンプレート】クイックソート
タイトルの説明
高速ソートアルゴリズムを用いて,読み込んだN個の数を小さいものから大きいものにソートして出力する.高速ソートは情報学コンテストの必須アルゴリズムの一つである.クイックソートについてよく知らない学生は、自分でインターネットで関連資料を検索し、把握してから独立して完成することができます.(C++選手はSTLを使わないでください.sortを使ってもいいですが、クイックソートアルゴリズムの真髄を把握していません.)
入力フォーマット
1行目は正の整数N、2行目はN個のスペースで区切られた正の整数aiを含み、ソートする必要がある数であり、データはAiが1 e 9を超えないことを保証している.
出力フォーマット
与えられたN個の数を小さいから大きいまで出力し、数の間にスペースを隔て、行の最後に改行し、スペースがない.
入力#1
5 4 2 4 5 1
出力#1
1 2 4 4 5
Accepted
本題はsort関数を用いると直接過ぎるが,よりよく理解するために並べ替え,問題解の方法を参考にした.同時に多くの種類の並べ替え方式(今日テーマを完成してから勉強を始めます!)の出所を見ました:洛谷快速並べ替え(quicksort)は1960年代に提出したアルゴリズムで、集計に似ていて、分治の1種の思想もあって、つまり1つの基準数を見つけて、それより大きいものをその右に置いて、それより小さいものをその左に置きます.1.基準数位置.基準数の位置は教科書の中で一番左か一番右で、私は普通一番左を選ぶことに慣れています.異なる選択は実行に大きな影響を及ぼさない.2.左右に移動する方法現在私が見ている移動の方法は、主に2つあります.1つは、j(右から)が基準数(kと記す)より小さい数を見つけ、i(左から)がkより大きい数を見つけて交換する.i、jが出会うまで分治処理を開始する.もう1つは基準数をkと記す.基準数の下にx①i(左から)がkより大きい数を見つけ、a[x]=a[i];2 j(右から)がkより小さい数を見つけ、a[i]=a[j]; ③i(左から)kより大きい数を見つけて、a[j]=a[i];④②③を繰り返してi=jになるまで;⑤a[i]を基準数kに賦値する;1つ目は速排の原始思想で、交換->分治するが、tを借りてa[i]とa[j]を交換する;2つ目の思想は巧みで、1回の3つの言葉で操作するのではなく、交換するたびにa[i]>a[j]を保証することができる.
P 068分数線画定
タイトルの説明
万博ボランティアの選考がA市で盛んに行われている.最適な人材を選抜するため、A市は応募したすべての選手に対して筆記試験を行い、筆記試験の点数が面接の点数ラインに達した選手が面接に入ることができる.面接スコアラインは、計画採用人数の150%によって決まります.つまり、m名のボランティアを採用する予定であれば、面接スコアラインはm位です.×150%(下から全体)の選手の点数で、最終的に面接に入った選手は筆記試験の成績が面接の点数ラインを下回らないすべての選手です.今、プログラムを書いて面接の点数ラインを画定し、面接に入ったすべての選手の応募番号と筆記試験の成績を出力してください.
入力フォーマット
1行目は、2つの整数n,m(5≦n≦5000,3≦m≦n)で、中間は1つのスペースで隔てられ、そのうちnは筆記試験に応募した選手の総数を表し、mは採用予定のボランティアの人数を表す.入力データ保証m×150%が下向きに整列した後、n以下である.2行目からn+1行目まで、各行は2つの整数を含み、中間は1つのスペースで隔てられ、それぞれ選手のエントリー番号k(1000≦k≦9999)とその選手の筆記試験成績s(1≦s≦100)である.データは選手の申し込み番号がそれぞれ異なることを保証している.
出力フォーマット
最初の行には、2つの整数があり、1つのスペースで区切られ、最初の整数は面接点数線を表します.2番目の整数は面接に入った選手の実際の人数です.2行目から各行に2つの整数を含み、中間を1つのスペースで区切って、面接に入った選手のエントリー番号と筆記試験の成績をそれぞれ表し、筆記試験の成績が高いものから低いものまで出力し、成績が同じであればエントリー番号が小さいものから大きいものまで出力します.
入力#1
6 3 1000 90 3239 88 2390 95 7231 84 1005 95 1001 88
出力#1
88 5 1005 95 2390 95 1000 90 1001 88 3239 88
説明/ヒント
【サンプル説明】m×150%=3×150%=4.5、下向きに整頓すると4になります.4人が面接に入ることを保証する点数ラインは88だが、88には重い点数があるため、88以上の成績の選手はすべて面接に入ることができるため、最終的には5人が面接に入る.
Accepted
この問題は最初は速い列を使っていたが、点数が等しいときに番号を並べ替えることができないことに気づいたので、sort関数+構造体の方法を採用した.
P 1781宇宙大統領
タイトルの説明
地球暦6036年、全宇宙は最も有能な人を大統領に立候補する準備をしています.n人の抜群の人が大統領に立候補しています.今、票数は統計が終わりました.誰が大統領になれるか計算してください.
入力フォーマット
第一行為は整数nで、大統領選挙に立候補する人数を代表する.次はn行で、それぞれ1番目の候補からn番目の候補の票です.
出力フォーマット
全部で2行で、1行目は整数mで、大統領になった人の番号です.2行目は大統領になった人の票だ.
入力#1
5 98765 12365 87954 1022356 985678
出力#1
4 1022356
説明/ヒント
票数は大きいかもしれませんが、100桁になるかもしれません.
Accepted
この問題はヒントを見て文字列を比較することを理解して、この問題は私にc++が文字列を操作する時cよりもっと便利なところを見ました:
もちろん、この問題は構造体+sort関数で解決することもできます.cで次のビットよりも速いです(ソース:洛谷):
P 1309スイスホイール
テーマの背景
卓球、バドミントン、チェスのようなペア対決の競技的な試合では、トーナメントと循環試合が最もよく見られる.前者の特徴は試合数が少なく、1試合ごとに緊張して刺激するが、偶然性が高いことだ.後者の特徴は公平で、偶然性が低いが、試合の過程は往々にして冗長である.本題で紹介したスイスラウンド制は、1895年にスイスで開催されたチェスの試合で最初に使われたことから名付けられた.トーナメントとリーグ戦の折衷と見なすことができ、試合の安定性を保証するとともに、試合の距離を長すぎないようにすることができる.
タイトルの説明
2×N名の1〜2 Nの選手がRラウンドを行う.各試合が始まる前、そしてすべての試合が終わると、総得点の高さから低さまで選手をランキングします.選手の総得点は1回戦開始前の初期点数に参加したすべての試合の得点と加算される.総得点が同じで、約束番号の小さい選手が上位にランクインした.各ラウンドの対戦スケジュールは、1位と2位、3位と4位、…、2 K−1位と2 K位、…、2 N−1位と2 N位に関係し、それぞれ1試合ずつ行われる.試合ごとに勝者は1点、敗者は0点を取る.つまり、1回戦以外の試合の予定は事前に決められず、選手の前の試合での演技にかかっている.各選手の初期点数とその実力値を与え、Rラウンド後、Q位の選手番号を計算してみる.私たちは選手の実力値が2つ違い、試合ごとに実力値が高い人が勝つと仮定します.
入力フォーマット
1行目は3つの正の整数N,R,Qで、2つの数の間に1つのスペースで区切られ、2を表す.×N名選手、Rラウンド、そして私たちが関心を持っている順位Q.2行目は2×N個の非負の整数s 1,s 2,...,s 2 Nは、2つの数の間に1つのスペースで区切られ、siはi番の選手の初期点数を表す.3行目は2×N個の正の整数w 1,w 2,...,w 2 Nは、2個の数の間に1つのスペースで区切られ、wiはi番の選手の実力値を表す.
出力フォーマット
Rラウンド終了後、Q位の選手の番号です.
入力#1
2 4 2 7 6 6 7 10 5 20 15
出力#1
1
Wrong Answer
Accepted
この問題は私がちょうど速い列を採用し始めたばかりで、しかし依然として2つの点が過ぎていないで、O 2を開いてやっとACを開いて、後で問題の解を見てやっと知っていて、この問題が使うのは並べ替えの方法に帰着するのです:(出所:洛谷)一、sortの浪費についてまず私たちに考えさせて、sortは実は速い順序付けです.安定するとO(nlogn)程度です.しかし、この問題をよく考えてみると、更新が必要な値は、隣接する2人が変化した点数です.隣接する点数は、位置を変えることはありませんが、クイックソートはすべて修正するたびに無駄になります.2、並べ替えについては、並べ替えを考慮します.並べ替えの考え方は、2つの同順序配列を統合することです線形方式--2つの秩序配列のポインタが指す値を比較するたびに、誰がもっと小さい(大きい)かはtemp配列に入れ、tempに入った要素、ポインタ++を削除します.
タイトルの説明
高速ソートアルゴリズムを用いて,読み込んだN個の数を小さいものから大きいものにソートして出力する.高速ソートは情報学コンテストの必須アルゴリズムの一つである.クイックソートについてよく知らない学生は、自分でインターネットで関連資料を検索し、把握してから独立して完成することができます.(C++選手はSTLを使わないでください.sortを使ってもいいですが、クイックソートアルゴリズムの真髄を把握していません.)
入力フォーマット
1行目は正の整数N、2行目はN個のスペースで区切られた正の整数aiを含み、ソートする必要がある数であり、データはAiが1 e 9を超えないことを保証している.
出力フォーマット
与えられたN個の数を小さいから大きいまで出力し、数の間にスペースを隔て、行の最後に改行し、スペースがない.
入力#1
5 4 2 4 5 1
出力#1
1 2 4 4 5
Accepted
本題はsort関数を用いると直接過ぎるが,よりよく理解するために並べ替え,問題解の方法を参考にした.同時に多くの種類の並べ替え方式(今日テーマを完成してから勉強を始めます!)の出所を見ました:洛谷快速並べ替え(quicksort)は1960年代に提出したアルゴリズムで、集計に似ていて、分治の1種の思想もあって、つまり1つの基準数を見つけて、それより大きいものをその右に置いて、それより小さいものをその左に置きます.1.基準数位置.基準数の位置は教科書の中で一番左か一番右で、私は普通一番左を選ぶことに慣れています.異なる選択は実行に大きな影響を及ぼさない.2.左右に移動する方法現在私が見ている移動の方法は、主に2つあります.1つは、j(右から)が基準数(kと記す)より小さい数を見つけ、i(左から)がkより大きい数を見つけて交換する.i、jが出会うまで分治処理を開始する.もう1つは基準数をkと記す.基準数の下にx①i(左から)がkより大きい数を見つけ、a[x]=a[i];2 j(右から)がkより小さい数を見つけ、a[i]=a[j]; ③i(左から)kより大きい数を見つけて、a[j]=a[i];④②③を繰り返してi=jになるまで;⑤a[i]を基準数kに賦値する;1つ目は速排の原始思想で、交換->分治するが、tを借りてa[i]とa[j]を交換する;2つ目の思想は巧みで、1回の3つの言葉で操作するのではなく、交換するたびにa[i]>a[j]を保証することができる.
#include
#include
#include
int a[1000000];
void sort(int left,int right){
int mid=a[(left+right)/2];//
int i=left,j=right;
while(i<=j){
while(a[i]mid) j--;//
if(i<=j){// （ ）
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++;
j--;
}
}
if(lefti) sort(i, right);
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i P 068分数線画定
タイトルの説明
万博ボランティアの選考がA市で盛んに行われている.最適な人材を選抜するため、A市は応募したすべての選手に対して筆記試験を行い、筆記試験の点数が面接の点数ラインに達した選手が面接に入ることができる.面接スコアラインは、計画採用人数の150%によって決まります.つまり、m名のボランティアを採用する予定であれば、面接スコアラインはm位です.×150%(下から全体)の選手の点数で、最終的に面接に入った選手は筆記試験の成績が面接の点数ラインを下回らないすべての選手です.今、プログラムを書いて面接の点数ラインを画定し、面接に入ったすべての選手の応募番号と筆記試験の成績を出力してください.
入力フォーマット
1行目は、2つの整数n,m(5≦n≦5000,3≦m≦n)で、中間は1つのスペースで隔てられ、そのうちnは筆記試験に応募した選手の総数を表し、mは採用予定のボランティアの人数を表す.入力データ保証m×150%が下向きに整列した後、n以下である.2行目からn+1行目まで、各行は2つの整数を含み、中間は1つのスペースで隔てられ、それぞれ選手のエントリー番号k(1000≦k≦9999)とその選手の筆記試験成績s(1≦s≦100)である.データは選手の申し込み番号がそれぞれ異なることを保証している.
出力フォーマット
最初の行には、2つの整数があり、1つのスペースで区切られ、最初の整数は面接点数線を表します.2番目の整数は面接に入った選手の実際の人数です.2行目から各行に2つの整数を含み、中間を1つのスペースで区切って、面接に入った選手のエントリー番号と筆記試験の成績をそれぞれ表し、筆記試験の成績が高いものから低いものまで出力し、成績が同じであればエントリー番号が小さいものから大きいものまで出力します.
入力#1
6 3 1000 90 3239 88 2390 95 7231 84 1005 95 1001 88
出力#1
88 5 1005 95 2390 95 1000 90 1001 88 3239 88
説明/ヒント
【サンプル説明】m×150%=3×150%=4.5、下向きに整頓すると4になります.4人が面接に入ることを保証する点数ラインは88だが、88には重い点数があるため、88以上の成績の選手はすべて面接に入ることができるため、最終的には5人が面接に入る.
Accepted
この問題は最初は速い列を使っていたが、点数が等しいときに番号を並べ替えることができないことに気づいたので、sort関数+構造体の方法を採用した.
#include
#include
#include
#include
struct player{
int s;
int k;
}a[100000];
bool cmp(player a1,player b1){ //
if(a1.s==b1.s) return a1.kb1.s;
}
int main(){
int n,i;
int m;
int num=0;
int score_num=0;
int score=0;
scanf("%d %d",&n,&m);
score_num=(int)m*1.5;
for(i=1;i<=n;i++)
scanf("%d %d",&a[i].k,&a[i].s);
std::sort(a+1,a+n+1,cmp);
score=a[score_num].s;
for(i=1;i<=n;i++){
if(a[i].s P 1781宇宙大統領
タイトルの説明
地球暦6036年、全宇宙は最も有能な人を大統領に立候補する準備をしています.n人の抜群の人が大統領に立候補しています.今、票数は統計が終わりました.誰が大統領になれるか計算してください.
入力フォーマット
第一行為は整数nで、大統領選挙に立候補する人数を代表する.次はn行で、それぞれ1番目の候補からn番目の候補の票です.
出力フォーマット
全部で2行で、1行目は整数mで、大統領になった人の番号です.2行目は大統領になった人の票だ.
入力#1
5 98765 12365 87954 1022356 985678
出力#1
4 1022356
説明/ヒント
票数は大きいかもしれませんが、100桁になるかもしれません.
Accepted
この問題はヒントを見て文字列を比較することを理解して、この問題は私にc++が文字列を操作する時cよりもっと便利なところを見ました:
#include
#include
#include
using namespace std;
int main(){
int n,i;
int num = 0;
string str_max="";
string str;
cin >> n;
for(i=1;i<=n;i++){
cin >> str;
int str_size=(int)str.size();
int str_max_size=(int)str_max.size();
if(str_size>str_max_size||(str_size>=str_max_size&&str>str_max)){
str_max=str;
num=i;
}
}
cout << num << endl << str_max << endl;
return 0;
}
もちろん、この問題は構造体+sort関数で解決することもできます.cで次のビットよりも速いです(ソース:洛谷):
#include
#include
#include
using namespace std;
struct node
{
string x; //
int num; //
int lenx; //
}s[25];
bool cmp(node a,node b)
{
if(a.lenx>b.lenx) return 1; // ，
if(a.lenx==b.lenx&&a.x>b.x) return 1; // ， ， 。
return 0; // 。
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s[i].x;
s[i].num=i; //
s[i].lenx=s[i].x.size(); //
}
sort(s+1,s+n+1,cmp); //
cout< P 1309スイスホイール
テーマの背景
卓球、バドミントン、チェスのようなペア対決の競技的な試合では、トーナメントと循環試合が最もよく見られる.前者の特徴は試合数が少なく、1試合ごとに緊張して刺激するが、偶然性が高いことだ.後者の特徴は公平で、偶然性が低いが、試合の過程は往々にして冗長である.本題で紹介したスイスラウンド制は、1895年にスイスで開催されたチェスの試合で最初に使われたことから名付けられた.トーナメントとリーグ戦の折衷と見なすことができ、試合の安定性を保証するとともに、試合の距離を長すぎないようにすることができる.
タイトルの説明
2×N名の1〜2 Nの選手がRラウンドを行う.各試合が始まる前、そしてすべての試合が終わると、総得点の高さから低さまで選手をランキングします.選手の総得点は1回戦開始前の初期点数に参加したすべての試合の得点と加算される.総得点が同じで、約束番号の小さい選手が上位にランクインした.各ラウンドの対戦スケジュールは、1位と2位、3位と4位、…、2 K−1位と2 K位、…、2 N−1位と2 N位に関係し、それぞれ1試合ずつ行われる.試合ごとに勝者は1点、敗者は0点を取る.つまり、1回戦以外の試合の予定は事前に決められず、選手の前の試合での演技にかかっている.各選手の初期点数とその実力値を与え、Rラウンド後、Q位の選手番号を計算してみる.私たちは選手の実力値が2つ違い、試合ごとに実力値が高い人が勝つと仮定します.
入力フォーマット
1行目は3つの正の整数N,R,Qで、2つの数の間に1つのスペースで区切られ、2を表す.×N名選手、Rラウンド、そして私たちが関心を持っている順位Q.2行目は2×N個の非負の整数s 1,s 2,...,s 2 Nは、2つの数の間に1つのスペースで区切られ、siはi番の選手の初期点数を表す.3行目は2×N個の正の整数w 1,w 2,...,w 2 Nは、2個の数の間に1つのスペースで区切られ、wiはi番の選手の実力値を表す.
出力フォーマット
Rラウンド終了後、Q位の選手の番号です.
入力#1
2 4 2 7 6 6 7 10 5 20 15
出力#1
1
Wrong Answer
#include
#include
struct player{
int s;
int w;
int num;
}a[1000000];
bool cmp(player a, player b){
if(a.s==b.s) return a.numb.s;
}
int main(){
int n,i,q,r;
scanf("%d %d %d",&n,&r,&q);
for(i=1;i<=2*n;i++){
scanf("%d",&a[i].s);
a[i].num=i;
}
for(i=1;i<=2*n;i++){
scanf("%d",&a[i].w);
}
while(r--){
std::sort(a+1,a+1+2*n,cmp);
for(i=1;i<2*n;i+=2){
if(a[i].w>a[i+1].w) a[i].s++;
else a[i+1].s++;
}
}
std::sort(a+1,a+1+2*n,cmp);
printf("%d
",a[q].num);
return 0;
} Accepted
この問題は私がちょうど速い列を採用し始めたばかりで、しかし依然として2つの点が過ぎていないで、O 2を開いてやっとACを開いて、後で問題の解を見てやっと知っていて、この問題が使うのは並べ替えの方法に帰着するのです:(出所:洛谷)一、sortの浪費についてまず私たちに考えさせて、sortは実は速い順序付けです.安定するとO(nlogn)程度です.しかし、この問題をよく考えてみると、更新が必要な値は、隣接する2人が変化した点数です.隣接する点数は、位置を変えることはありませんが、クイックソートはすべて修正するたびに無駄になります.2、並べ替えについては、並べ替えを考慮します.並べ替えの考え方は、2つの同順序配列を統合することです線形方式--2つの秩序配列のポインタが指す値を比較するたびに、誰がもっと小さい(大きい)かはtemp配列に入れ、tempに入った要素、ポインタ++を削除します.
#include
#include
struct player{
int s;
int num;
}a[2000005];
player v[200005],l[200005];//v: l:
bool cmp(player a, player b){
if(a.s==b.s) return a.numb.s;
}
// v l stu
void merge(int n){
int i=1,j=1,k=1;
while(i<=n&&j<=n){
if(v[i].s>l[j].s||(v[i].s==l[j].s&&v[i].numw[a[i+1].num]){
v[ind].s=a[i].s+1;
v[ind].num=a[i].num;
l[ind].s=a[i+1].s;
l[ind].num=a[i+1].num;
ind++;
}
else{
v[ind].s=a[i+1].s+1;
v[ind].num=a[i+1].num;
l[ind].s=a[i].s;
l[ind].num=a[i].num;
ind++;
}
}
merge(n);
}
printf("%d
",a[q].num);
return 0;
}