OJのいくつかのコード

32620 ワード
c++ アルゴリズム
質問1:敢えてフィボナッチ数列
Descriptionフィボナッチ数列ってみんな知ってるでしょ!フィボナッチ数列(Fibonacci sequence)は、黄金分割数列とも呼ばれ、数学者レオナルド・フィボナッチ(Leonardoda Fibonacci)がウサギの繁殖を例に導入したことから「ウサギ数列」とも呼ばれ、1、1、2、3、5、8、13......数学的に、フィボナッチ数列は、F(1)=1,F(2)=1,F(n)=F(n−1)+F(n−2)(n≧3,n∈N∗)という繰返し方法で定義される.この問題の意味も簡単で、正の整数n(1≦n≦107)をあげて、フィボナッチ数列のn番目の項目を出力させます~答えが大きいので、109+7に対して型を取った数を出力します.
Inputマルチグループ読み込みは、10グループを超えないことを保証し、各グループに1つの正の整数n(1≦n≦107)を保証する.
Outputフィボナッチ数列のn番目の項目で、答えは109+7で型を取ります.
Samples Input Copy 1 Output 1 Hint本題の使用スペースの制限に注意してください.
#pragma GCC optomize(2)
#pragma G++ optimize(2)
#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e7+7;
int s[maxn];
int main()
{
     
   ll n,i;
   s[1]=s[2]=1;
   for(i=3;i<=maxn;i++)
   {
     
      s[i]=(s[i-1]+s[i-2])%mod;
   }
   while(cin>>n)
   {
     
      cout<<s[n]%mod<<endl;
   }
   return 0;
}

注意本題は再帰的に解決するとタイムアウトするので、表を打つ(つまり、すべての結果を先に計算し、配列で格納する)ことを選択できます.
問題2:HJはまた花を植えた
Description HJGGには現在、n(m)*m(m)の大きさの矩形の花園があります.
HJGGは強迫症のため、この花園はn
今、HJはこの花園にたくさんの花を植えたいと思っています.そして、隣の格子に違う花を植えたいと思っています.
説明を追加します.隣接する格子に植えられた異なる花とは、一つの位置と彼の上下左右の4つの方向の位置の色が異なり、上下左右の4つの位置に対して、同じであることを指す.HJは合宿隊の可愛い蕾ちゃんに絡まれて抜けないので助けて欲しい~HJお兄さんの要望に応えられるなら「Beautiful flowers!」と伝え、ダメなら「Oh!My poor HJ!」(出力に二重引用符は含まれていません)誰がみんなにレイレイを断ることができませんか!
Inputは1行の3つの整数n,m,k(1≦n,m,k≦105)のみを入力し,それぞれHJGGガーデンの長さと幅,HJGGが持つ花の種類数を表す
Output出力1行Hjに伝えるなら~
Samples Input Copy 1 3 5 Output Beautiful flowers! 
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+9;
int a[1011][1011];
int main()
{
     
	int n,m,k;
	cin>>n>>m>>k;
	if((n+m==2)&&(k==1)||k>=2)
	cout<<"Beautiful flowers!"<<endl;
	else
	cout<<"Oh! My poor HJ!"<<endl;
   return 0;
}

本題では,1つの位置と彼の上下左右4方向の位置の色が異なり,上下左右4つの位置については同じであることが分かるので,k>=2の場合はいずれも状況を満たすことが分かるが,n 1&&m 1の場合はk=1も満足することが特判される.
質問3:川川監督の戸惑い
DescriptionはSMUアルゴリズムコンテストチームの中で、誰の地位が一番高いですか?答えは疑いの余地がない--みんなが心から愛している川川監督.川川監督はチーム内の事務に非常に関心を持っており、選手たちのニーズをできるだけ満たし、選手たちの問題もできるだけ早く解決した.しかし、最近川川さんはどうも力不足で、何でも自分でやるのは本当に疲れました.だから彼はあなたの助けが必要です.そうすれば、彼はもっと多くの時間と精力を持って指導者と知恵を闘って、チームのためにもっと多くの経費を稼ぐことができます.最近、川川監督は新しく加わった合宿選手の中から、一番強いチームを選んで大学生のプログラミングコンテストに参加しなければならない.
川川はこれまで忙しくて、新しい合宿隊員を知らなかったので、HJが提供した隊員の能力値に基づいて隊員を選抜するしかなかった.私たちの大原則は強引に手を組むことだ.具体的には、新しい合宿隊員は全部でn人で、HJはあなたに一人一人のプログラミング能力値wを提供します.プログラミング能力値と最大の**3人****を見つけて、プログラミング能力値の和を出力する必要があります.特に、チームのプログラミング能力値の和がmより大きいものが見つからない場合は「Waiver!」と出力します.
Inputの最初の行には、1つの整数n、1つの整数mが入力され、中間はスペースで区切られています.2行目にn個の整数wiを入力すると、プログラミング能力値を表す.すべてのデータを保証する:3≦n≦100≦m≦300−100≦wi≦100 Output任意の組み合わせでは、チームの英語能力値の和をmより大きくすることができず、1行の文字列を出力する:“Waiver!”(引用符なし)
そうでなければ、チームの英語能力値の和がmより大きい場合に構成できる最大プログラミング能力値を表す整数を出力する.
Samples Input Copy 4 100 50 50 55 -5 Output 155 Hint
  • サンプル1は、155のプログラミング能力が要求を満たすとともに、最大のプログラミング能力とを得ることができる上位3人を選択したことを示している.
  • サンプル2はどのように選んでも要求を満たすことができないことを説明して、Waiver!
  • 注意:プログラミング能力は負数かもしれませんよ.これも理解できます.
    • #include
using namespace std;
typedef long long ll;
const int maxn=1e5+9;
int a[1011];
int cmp(int a,int b)
{
     
   return a>b;
}
int main()
{
     
	ll n,m,i,k;
	cin>>n>>m;
	for(i=0;i<n;i++)
	{
     
	   cin>>a[i];
	}
	sort(a,a+n,cmp);
	k=a[0]+a[1]+a[2];
	if(k>m)
	cout<<k<<endl;
	else
	cout<<"Waiver!"<<endl;
   return 0;
}

    直接sortソートして、最初の3つを出力すればいいです.
    質問4:kthの自撮り
    Description kthは自撮りが大好きですが、彼女の携帯電話がzyjに地面に落ちた後、フロントカメラが壊れて、どんな写真を撮っても反時計回りに90°回転して、しかも写真は白黒です.このような写真はどうしてkthに対象を見つけることができますか?今kthは賢いあなたに助けを求めて、プログラムを書いてkthが画像を回転させるのを助けます.(彼女の携帯はゴミすぎて、画像の回転機能を持っていません).写真は白黒だから.携帯電話の画面には白と黒の2つしかない.次に、画像を(01マトリクスで示す)回転させます.画像を正常に表示する.
    Inputはn2≤n≤1000
    Outputは、回転後のマトリクスを出力.マトリクスは要素ごとにスペースを空ける.
    Samples Input Copy 2 0 1 1 0 Output 1 0 0 1 Hint回転方向を考えてみましょう.
    #include
using namespace std;
typedef long long ll;
const int maxn=1e5+9;
int a[1011][1011];
int main()
{
     
	ll n,i,j;
	cin>>n;
	for(i=0;i<n;i++)
	{
     
	   for(j=0;j<n;j++)
	   {
     
	     cin>>a[i][j];
	   }
	}
	for(i=0;i<n;i++)
	{
     
	   for(j=n-1;j>=0;j--)
	   {
     
	      if(j==n-1)
	         cout<<a[j][i];
	      else
	         cout<<" "<<a[j][i];
	   }
	   putchar('
    '    );
	}
   return 0;
}

    質問5:We are singers
    Descriptionはスペクトルで,音符は音の高低と長さを記録する記号である.これらの音の高低を表す記号は、1、2、3、4、5、6、7と7つのアラビア数字で表記され、読み方はdo、re、mi、fa、sol、la、siである.今、N個の音符で構成された簡単なスペクトルと、10未満の長さの文字列を歌った読み方の記録をあげます.全部でいくつかの読み方を間違えたと判断してください.
    Inputの1行目に入力整数N(0行目はN個の数字からなるスペクトルを含み、数字間はスペースで区切る;3行目はN個の読み方を含み、読み方間はスペースで区切る.
    Outputは全部で間違った読み方の個数を歌った.
    Samples Input Copy 8 1 2 3 4 5 6 7 1 do re mi fa sol la si der Output 1 
    #pragma GCC optomize(2)
#pragma G++ optimize(2)
#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e7+7;
int a[maxn];
map<int,string> p;
vector<int> q;
void init()
{
     
   p[1]="do",p[2]="re",p[3]="mi",p[4]="fa",p[5]="sol",p[6]="la",p[7]="si";
}

int main()
{
     
	init();
	int n,i,sum=0;
	string s;
	cin>>n;
	q.resize(n);
	for(i=0;i<n;i++)
	{
     
		cin>>q[i];
	}
    for(i=0;i<n;i++)
    {
     
       cin>>s;
       if(s==p[q[i]])
       continue;
       else
       sum++;
	}
	cout<<sum<<endl;
   return 0;
}

    この問題はstlに関する知識点に関し、現在studying中である.
    質問6:Incompement Fury of a Single Dog
    Description SMUの英語のフルネームはSouthwest Minzu Universityで、中国語名は西南民族大学と呼ばれています.この大学は男女比が約2対8のため、稀男民族大学と呼ばれ、民族学生たちが歌や踊りが上手で、校内のダンスや歌の活動が非常に多いため、稀男歌舞大学と呼ばれている.コンピュータ学院では、男子学生の割合が他の学院よりはるかに高いため、コンピュータ学院の脱単率ははるかにリードしている.しかし、コンピューター学院のアルゴリズムコンテストチームでは、ある合宿隊員がみなSingleDogだったという奇妙な現象が現れた.彼らはプライベートでSingleDogと笑われるのが大嫌いだ.最初は、SingleDogという言葉を聞いたり見たりすると、理性を失い、徐々にカップルが現れるのを見て、怒りを抑えることができませんでした.今は状況がさらに深刻になった!彼らはペアになったものを見ると、無能に怒り始める.今、合宿チームの通知書類があります.グループに送らなければなりません.彼らが心を落ち着かせるために、この書類を読むには、いくつかの文字を簡略化するしかありません.具体的な簡略化戦略:合宿チームの通知書類は小文字の山で、これらのアルファベットがペアにならないように、私たちはすべてのアルファベットが現れた最初の文字だけを残しておけばいいです.
    Inputの最初の行にnを入力し、合宿チームを代表する通知ファイルの長さを入力します.2行目には、合宿チームの通知ファイルを表す文字列sを入力します.すべてのデータ:1≦n≦1000であることを保証し、文字列sには、a~zの小文字のみが含まれている.
    Output 1行目出力処理後の通知ファイル長.
    2行目は処理後の合宿チーム通知ファイルを出力する.
    Samples Input Copy 18 woyexiangtanlianai Output 11 woyexiangtl 
    #pragma GCC optomize(2)
#pragma G++ optimize(2)
#include
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn=1e5+9;
const int N=1e9+7;
char a[1010];
char flag[1010];
int main()
{
     
   int i,j,sum=0,n;
   cin>>n;
   cin>>a;
   for(i=0;i<n;i++)
   {
     
      for(j=i+1;j<n;j++)
      {
     
        if(a[i]==a[j]){
     
        	flag[j]=1;
		}
	  }
   }
   for(i=0;i<n;i++)
   {
     
      if(flag[i]!=1)
      sum++;
   }
   cout<<sum<<endl;
   for(i=0;i<n;i++)
   {
     
      if(flag[i]!=1)
      cout<<a[i];
   }
   return 0;
}

    配列をスキャンして比較し、flag配列でマークします.
    MyCat入門から放棄まで(二、設置)
    Linuxシステムmysqlデータベースのインストール