UESTC 1262 Memory暴力法
Memory
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
小xと小hは良い盆友で、小hは小体から弱く病気が多く、しかもとても忘れっぽいので、自分が普段飲んでいるn本の薬を小xたちに保管しました.
ある日霧都のpm 2.5爆表により、小hの慢性呼吸器疾患が再発したが、小xが薬瓶を取り出したところ、異常が発見された.
小xは今n本の薬があって、1本の薬の中に無限の錠剤があって、1錠の薬の重量は厳格に1グラムに等しいです.しかし、あら探しの小xはn本の薬のうち2本の薬の錠剤が重量的に不合格であることを発見した.
はい、不合格の錠剤は正常な錠剤より0.1 g軽いです.
小xは現在電子称(具体的な重量を示すことができる)があり、時間が緊急であるため、小xは1本の薬からbi(1≦bi)を選択することにした. つの錠剤を量って、それらの総和を量って、しかも一回だけ量って、それによって探します
この2本の不合格薬の番号を出します.
ここで、最小辞書順のシーケンスb( biからなる)はいくらですか.
Input
1行1個の整数n(2≦n≦52)
Output
1行n個の数字で、2つの間はスペースで区切られており、末尾にスペースがないことに注意してください.
Sample input and output
Sample Input
Sample Output
Hint
若し a1,a2..an 比 b1,b2..bn 辞書の順序が小さいと、必ず存在します. j(1≤j≤n) にさせる aj < bj すべてのi例の解釈:5.7 gと呼ぶと、1本目と2本目が不合格になる.5.6 gなら、1本目と3本目が不合格です.
5.5 gなら2本目と3本目が不合格です.
Source
第7回ACM趣味プログラミングコンテスト第3戦(公式戦)E
My Solution
構想はすでにi-1の条件を満たす数があって、更にiの数を加えて入って依然として満足して、任意の2つの数の和は他の2つの数と等しくありません.
前の試合の時はフィボナッチ数列かと思っていたのですが、先輩がフィブではないと宣言したのを終えて、確かに当時筆者自身もデータが大きい時にi-1個目とi個目の数がかなり違うと感じましたし、
何億もの差がある(n<=52)ので,jがFibのi番目の数よりも小さい可能性が高いが,条件も満たす.
当時は自分が漏らしたと思っていたので、確かによく反省しなければなりませんね.
それでは暴力法を使うのはやはり比較的に良い選択で、ほほほ、暴力法はもともととても良いです.
sum[i][j]はi番目の数とj番目の数の和を表す.どうせn<=52なら大丈夫
まずans[i]のiの各iを処理し、jからインクリメントし、サブブロックx=i sum[x][前の数]を更新し、マトリクス全体をforforでスキャンします.もちろん、x-1行までです.
时を止めて、自分の行をスキャンすることはできません.もし真ん中に直接returnが現れたら、これも関数が直接中にネストされているメリットで、1つのreturnが直接何層もジャンプしますfor.
また、sum[i][j]のほとんどのsum[i]の後ろの部分は処理されていないかもしれませんが、よくスキャンされますが、アルゴリズムを簡潔に理解するためには、ここでは気にしないでください.
memsetを覚えていればいいのに、どうせ0ばかりだから、掃除したほうが健康だ.私たちが探しているのは同じ和があるかどうかで、後ろの数の和はどうして0と等しいのだろうか.☺,(結局n<=52で、一発渡して、タイムアウトしてから直して、
速くないと普通はタイムアウトできないので、気にしないでください.
ありがとう
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
小xと小hは良い盆友で、小hは小体から弱く病気が多く、しかもとても忘れっぽいので、自分が普段飲んでいるn本の薬を小xたちに保管しました.
ある日霧都のpm 2.5爆表により、小hの慢性呼吸器疾患が再発したが、小xが薬瓶を取り出したところ、異常が発見された.
小xは今n本の薬があって、1本の薬の中に無限の錠剤があって、1錠の薬の重量は厳格に1グラムに等しいです.しかし、あら探しの小xはn本の薬のうち2本の薬の錠剤が重量的に不合格であることを発見した.
はい、不合格の錠剤は正常な錠剤より0.1 g軽いです.
小xは現在電子称(具体的な重量を示すことができる)があり、時間が緊急であるため、小xは1本の薬からbi(1≦bi)を選択することにした. つの錠剤を量って、それらの総和を量って、しかも一回だけ量って、それによって探します
この2本の不合格薬の番号を出します.
ここで、最小辞書順のシーケンスb( biからなる)はいくらですか.
Input
1行1個の整数n(2≦n≦52)
Output
1行n個の数字で、2つの間はスペースで区切られており、末尾にスペースがないことに注意してください.
Sample input and output
Sample Input
Sample Output
31 2 3Hint
若し a1,a2..an 比 b1,b2..bn 辞書の順序が小さいと、必ず存在します. j(1≤j≤n) にさせる aj < bj すべてのi
5.5 gなら2本目と3本目が不合格です.
Source
第7回ACM趣味プログラミングコンテスト第3戦(公式戦)E
My Solution
構想はすでにi-1の条件を満たす数があって、更にiの数を加えて入って依然として満足して、任意の2つの数の和は他の2つの数と等しくありません.
前の試合の時はフィボナッチ数列かと思っていたのですが、先輩がフィブではないと宣言したのを終えて、確かに当時筆者自身もデータが大きい時にi-1個目とi個目の数がかなり違うと感じましたし、
何億もの差がある(n<=52)ので,jがFibのi番目の数よりも小さい可能性が高いが,条件も満たす.
当時は自分が漏らしたと思っていたので、確かによく反省しなければなりませんね.
それでは暴力法を使うのはやはり比較的に良い選択で、ほほほ、暴力法はもともととても良いです.
sum[i][j]はi番目の数とj番目の数の和を表す.どうせn<=52なら大丈夫
まずans[i]のiの各iを処理し、jからインクリメントし、サブブロックx=i sum[x][前の数]を更新し、マトリクス全体をforforでスキャンします.もちろん、x-1行までです.
时を止めて、自分の行をスキャンすることはできません.もし真ん中に直接returnが現れたら、これも関数が直接中にネストされているメリットで、1つのreturnが直接何層もジャンプしますfor.
また、sum[i][j]のほとんどのsum[i]の後ろの部分は処理されていないかもしれませんが、よくスキャンされますが、アルゴリズムを簡潔に理解するためには、ここでは気にしないでください.
memsetを覚えていればいいのに、どうせ0ばかりだから、掃除したほうが健康だ.私たちが探しているのは同じ和があるかどうかで、後ろの数の和はどうして0と等しいのだろうか.☺,(結局n<=52で、一発渡して、タイムアウトしてから直して、
速くないと普通はタイムアウトできないので、気にしないでください.
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int sum[56][56],ans[56],n;
inline bool judge(int x,int y) // ， 。
{
for(int i=1;i<x;i++){
sum[x][i]=y+ans[i];
for(int k=1;k<x;k++){ //k x，
for(int l=1;l<x;l++){ // n， ， x ， n ，
if(sum[x][i]==sum[k][l]) return false;
//cout<<sum[k][l]<<" ";
}
//printf("
");
}
}
return true;
}
int main()
{
scanf("%d",&n);
memset(sum,0,sizeof(sum));
if(n==2) printf("1 1");
else if(n==3) printf("1 2 3");
else{
ans[1]=1;ans[2]=2;ans[3]=3;
sum[1][2]=3;sum[1][3]=4;sum[2][3]=5;
printf("1 2 3");
for(int i=4;i<=n;i++){
for(int j=ans[i-1]+1;;j++){
if(judge(i,j)){
ans[i]=j;
printf(" %d",j);
break;
}
}
}
}
return 0;
}ありがとう