ツーショットプログラムの方法
5931 ワード
ビートプログラム、すなわち2つのプログラムを持って、同じ入力を使って出力の結果を比較します.撮影プログラムの使用が広く、以下の状況に遭遇した場合、撮影プログラムを行うことができます.
1.試合の過程(主にOI試合制)で、効率的なアルゴリズムを書いた後、アルゴリズムが正しいことを保証できなければ、写真を撮ることができます.
2.普段テーマを作るとき、データが手に入らなかったり、手で計算できなかったりするデータの規模が大きいので、このときに撮ってもいいです.
3.自分で問題を出した場合、通常は対拍が必要です.
ツーショットの主な流れ:
まず2つのプログラムを書いて、彼らをコンパイルします.通常、dpのような効率的なアルゴリズムがあり、暴力的なアルゴリズムがあります(つまり、後者が正しいことを保証しなければなりません)、ランダム数を作るプログラムを書いてコンパイルします.次は対拍を開始することができます.
まず乱数で生成されたプログラムを実行し、自分が間違っていると思っているプログラムを実行し、最後に暴力プログラムを実行します.次に2つのプログラムの出力結果を比較し,エラーを発見すると,エラー要因を確認し,プログラムを修正することができる.
次に、私が自作したdp問題を例に挙げます.
グルメ(food)
タイトルの説明:
明ちゃんはレストランに来ました.この店には全部でn種類の美食があり、それぞれの美食には全部でa部があり、それぞれの価格はc元で、美味しさはwです.明ちゃんは全部でv元を持っていて、もっとお金を使いたいので、購入した美食の総美味しさが一番大きいです.しかし、このレストランの主人はとても遠慮して、すべての美食に対して、あなたは買わないで、1部買うことができます.さもないと、全部買います.明ちゃんは困っています.今、彼が購入できる美食の総美味しさの最大値を計算してください.
入力形式:
全部で4行あります.
1行目には、2つの整数n,vがあります.
2行目には、n個の整数aがある.
3行目には、n個の整数cがある.
4行目、n個の整数wがあります.
出力フォーマット:
1つの整数は、購入できる美食の総美味しさの最大値です.
サンプル入力1:
2 17
3 2
4 3
9 6
サンプル出力1:
33
サンプル入力2:
2 10
3 2
2 4
5 3
サンプル出力2:
18
データ範囲と説明:
すべてのデータについて、1<=n<=1000、1<=v<=1000、1<=a、c、w、<=100である.
明らかに、これはdpのリュックサックの問題で、ただ普通のものとは違って、この中にはすべてのものに対して、全部か0つか1つを使うことができます.
以下は本人のスケジュールです:(本人は現地で評価して、書類の操作に参加する必要があります)
リュックサックの問題を学んだことがある学生は理解できると信じています.
次は暴力的なコードです.
明らかに、非常に暴力的で、時間の複雑さは3のn次方に達した.
次に、乱数を生成する方法を説明します.
C++が持つ関数を使用して乱数を生成できます.乱数を生成する場合は、次の2つのライブラリを呼び出す必要があります.
まず、次の関数を呼び出さなければなりません.そうしないと、実行ごとに生成される乱数は同じです.
次に、この関数を呼び出すと、乱数が返されます.
この乱数は範囲があり、範囲は0~32767なので、範囲を拡大または縮小する関数をカスタマイズすることができます.
これで、範囲は10億余りになります.
範囲を制限したい場合は、例えば1~nの間に乱数を生成し、結果%n+1を返すだけでよい.
このように、問題の意味に基づいて、以下は乱数を生成するコードです.
n,mのような変数はカスタマイズでき,残りの大量のデータはランダムに生成すればよい.
それから、私たちは対拍プログラムを書くことができます.
効率を高めるために,対拍プログラムで無限ループを用い,答えが対応しない点が現れ,対拍を終了する.
まず、乱数ジェネレータを実行し、
注意:プラス記号がない場合は、現在のディレクトリからディレクトリの計算を開始します.
そして、自分が間違っていると思っているプログラム(試合中はあなたが提出するプログラムで、出題時はスケジュール)を実行し、
暴力プログラムを実行し
3つのプログラムが実行されたら、2つの答えを比較します.以前、私たちのエラープログラムの出力ファイル名はfoodです.out,暴力プログラムの出力ファイル名food.ansは、次のコマンドを使用して比較します.
注意:比較時に余分な改行やスペースはフィルタされませんので、2つのプログラムの出力フォーマットは同じです.つまり、1つのプログラムの最後にある場合は、別のプログラムの最後にもスペースが必要です.2つの結果が異なる場合はtrueを返し、そうでない場合はfalseを返します.
完全な対拍プログラムは以下の通りです.
時間を計ることができます.そうすれば、アルゴリズムがタイムアウトしたかどうかを知ることができます.
データの范囲については、撮影を始める时に定义することができます.このように计算しやすくて、次はゆっくりと拡大して、最后にテーマが与えたデータの范囲と同じに拡大します.対拍プログラムにWAが現れず、止まらず、無限ループが発生すれば、効率的なアルゴリズムが正しいと考えることができます.
撮影時のいくつかのポイント:
1.試合中、時間を節約するために、暴力コードの時間の複雑さが非常に高い場合は、暴力コードを実行しながら、他の問題を続けることができます.
2.試合の最後にチェックして、他のコードに提出しないでください.
3.暴力コードが正しいことを確認し、時間もあまり長くしないでください.そうしないと、同じ時間にいくつかの点しかテストできません.効果は強くありません.
これは本人がまとめた対拍テクニックで、ランダム数の使用テクニック(例えば生成数が重複しないなど)について、紙幅が限られているため、ここでは詳しく説明しないで、他の文章を参考にすることができます.
1.試合の過程(主にOI試合制)で、効率的なアルゴリズムを書いた後、アルゴリズムが正しいことを保証できなければ、写真を撮ることができます.
2.普段テーマを作るとき、データが手に入らなかったり、手で計算できなかったりするデータの規模が大きいので、このときに撮ってもいいです.
3.自分で問題を出した場合、通常は対拍が必要です.
ツーショットの主な流れ:
まず2つのプログラムを書いて、彼らをコンパイルします.通常、dpのような効率的なアルゴリズムがあり、暴力的なアルゴリズムがあります(つまり、後者が正しいことを保証しなければなりません)、ランダム数を作るプログラムを書いてコンパイルします.次は対拍を開始することができます.
まず乱数で生成されたプログラムを実行し、自分が間違っていると思っているプログラムを実行し、最後に暴力プログラムを実行します.次に2つのプログラムの出力結果を比較し,エラーを発見すると,エラー要因を確認し,プログラムを修正することができる.
次に、私が自作したdp問題を例に挙げます.
グルメ(food)
タイトルの説明:
明ちゃんはレストランに来ました.この店には全部でn種類の美食があり、それぞれの美食には全部でa部があり、それぞれの価格はc元で、美味しさはwです.明ちゃんは全部でv元を持っていて、もっとお金を使いたいので、購入した美食の総美味しさが一番大きいです.しかし、このレストランの主人はとても遠慮して、すべての美食に対して、あなたは買わないで、1部買うことができます.さもないと、全部買います.明ちゃんは困っています.今、彼が購入できる美食の総美味しさの最大値を計算してください.
入力形式:
全部で4行あります.
1行目には、2つの整数n,vがあります.
2行目には、n個の整数aがある.
3行目には、n個の整数cがある.
4行目、n個の整数wがあります.
出力フォーマット:
1つの整数は、購入できる美食の総美味しさの最大値です.
サンプル入力1:
2 17
3 2
4 3
9 6
サンプル出力1:
33
サンプル入力2:
2 10
3 2
2 4
5 3
サンプル出力2:
18
データ範囲と説明:
すべてのデータについて、1<=n<=1000、1<=v<=1000、1<=a、c、w、<=100である.
明らかに、これはdpのリュックサックの問題で、ただ普通のものとは違って、この中にはすべてのものに対して、全部か0つか1つを使うことができます.
以下は本人のスケジュールです:(本人は現地で評価して、書類の操作に参加する必要があります)
#include
#include
using namespace std;
const int maxn=1005;
int n,v;
int f[maxn],a[maxn],c[maxn],w[maxn];
int main() {
freopen("food.in","r",stdin);
freopen("food.out","w",stdout);
scanf("%d %d",&n,&v);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
for(int j=v;j>=c[i];j--) {
if(j>=a[i]*c[i])
f[j]=max(f[j],max(f[j-c[i]]+w[i],f[j-a[i]*c[i]]+a[i]*w[i]));
else
f[j]=max(f[j],f[j-c[i]]+w[i]);
}
cout< リュックサックの問題を学んだことがある学生は理解できると信じています.
次は暴力的なコードです.
#include
#include
using namespace std;
const int maxn=102;
int n,v,ans;
int a[maxn],c[maxn],w[maxn],l[maxn];
void dfs(int x) {
if(x>n) {
int jiage=0;
for(int i=1;i<=n;i++)
jiage+=l[i]*c[i];
if(jiage<=v) {
int mwd=0;
for(int i=1;i<=n;i++)
mwd+=l[i]*w[i];
ans=max(ans,mwd);
}
return;
}
l[x]=0;
dfs(x+1);
l[x]=1;
dfs(x+1);
l[x]=a[x];
dfs(x+1);
}
int main() {
freopen("food.in","r",stdin);
freopen("food.ans","w",stdout);
scanf("%d %d",&n,&v);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
dfs(1);
cout< 明らかに、非常に暴力的で、時間の複雑さは3のn次方に達した.
次に、乱数を生成する方法を説明します.
C++が持つ関数を使用して乱数を生成できます.乱数を生成する場合は、次の2つのライブラリを呼び出す必要があります.
#include
#include まず、次の関数を呼び出さなければなりません.そうしないと、実行ごとに生成される乱数は同じです.
srand((unsigned)time(NULL));次に、この関数を呼び出すと、乱数が返されます.
rand();この乱数は範囲があり、範囲は0~32767なので、範囲を拡大または縮小する関数をカスタマイズすることができます.
int random() {
return rand()*rand();
}これで、範囲は10億余りになります.
範囲を制限したい場合は、例えば1~nの間に乱数を生成し、結果%n+1を返すだけでよい.
このように、問題の意味に基づいて、以下は乱数を生成するコードです.
#include
#include
#include
#include
using namespace std;
int main() {
freopen("food.in","w",stdout);
srand((unsigned)time(NULL));
const int cc=5;
int n=5,v=50;
printf("%d %d
",n,v);
for(int i=1;i<=n;i++)
printf("%d ",rand()%cc+1);
printf("
");
for(int i=1;i<=n;i++)
printf("%d ",rand()%cc+1);
printf("
");
for(int i=1;i<=n;i++)
printf("%d ",rand()%cc+1);
return 0;
} n,mのような変数はカスタマイズでき,残りの大量のデータはランダムに生成すればよい.
それから、私たちは対拍プログラムを書くことができます.
効率を高めるために,対拍プログラムで無限ループを用い,答えが対応しない点が現れ,対拍を終了する.
まず、乱数ジェネレータを実行し、
system("food_r.exe");注意:プラス記号がない場合は、現在のディレクトリからディレクトリの計算を開始します.
そして、自分が間違っていると思っているプログラム(試合中はあなたが提出するプログラムで、出題時はスケジュール)を実行し、
system("food.exe");暴力プログラムを実行し
system("food_s.exe");3つのプログラムが実行されたら、2つの答えを比較します.以前、私たちのエラープログラムの出力ファイル名はfoodです.out,暴力プログラムの出力ファイル名food.ansは、次のコマンドを使用して比較します.
system("fc food.ans food.out");注意:比較時に余分な改行やスペースはフィルタされませんので、2つのプログラムの出力フォーマットは同じです.つまり、1つのプログラムの最後にある場合は、別のプログラムの最後にもスペースが必要です.2つの結果が異なる場合はtrueを返し、そうでない場合はfalseを返します.
完全な対拍プログラムは以下の通りです.
#include
#include
#include
#include
using namespace std;
int main() {
while(1) {
system("food_r.exe");
double t1=clock();
system("food.exe");
double t2=clock();
system("food_s.exe");
if(system("fc food.ans food.out")) {
printf("WA time used:%lfms
",t2-t1);
return 0;
}
else
printf("AC time used:%lfms
",t2-t1);
}
return 0;
} 時間を計ることができます.そうすれば、アルゴリズムがタイムアウトしたかどうかを知ることができます.
データの范囲については、撮影を始める时に定义することができます.このように计算しやすくて、次はゆっくりと拡大して、最后にテーマが与えたデータの范囲と同じに拡大します.対拍プログラムにWAが現れず、止まらず、無限ループが発生すれば、効率的なアルゴリズムが正しいと考えることができます.
撮影時のいくつかのポイント:
1.試合中、時間を節約するために、暴力コードの時間の複雑さが非常に高い場合は、暴力コードを実行しながら、他の問題を続けることができます.
2.試合の最後にチェックして、他のコードに提出しないでください.
3.暴力コードが正しいことを確認し、時間もあまり長くしないでください.そうしないと、同じ時間にいくつかの点しかテストできません.効果は強くありません.
これは本人がまとめた対拍テクニックで、ランダム数の使用テクニック(例えば生成数が重複しないなど)について、紙幅が限られているため、ここでは詳しく説明しないで、他の文章を参考にすることができます.