[luogu]P 3333[ZJOI 2013]クリーナー(欲張り)
4185 ワード
P 3333[ZJOI 2013]クリーンボディ
タイトルの説明
普段の練習や試験では、命題者が例文を出して、私たちに文を書くようにしなければならないという問題によく遭遇します.このようなよく似たような問題は、小学生の試験だけでなく、中試験にも登場することがある.多くの学生はこのような問題をするのが好きだ.他の問題より面白いからだ.模写された文は往々にして「A_B_C」の形式を有し、ここでA,B,Cは1つ以上の単語からなる短文であり、空の部分は学生が記入する必要がある.もちろん、試験の時は空いていてもいいです.例えば、「実は空は暗くなくて昙り果てて散って、実は、実は、道は远くなくてすべて愿い通りになることができて、苦しい日の中で私はあなたのために祈って、あなたに毎日を大切にしてください」.例えば、「海の荒れ狂うのを見て、大山の高くそびえるのを見たことがなくて、本当に残念です;大山の高くそびえるのを見て、見たことがなくて、やはり残念です.出発しましょう、永遠に出発します.、人は不老の気持ちがあります.」
今はネット時代なので、私たちは命題の人命の問題を模写するしかありません.私たちはネット上のいろいろな文と段落を模写することができます.2011年3月26日、ある人がブログで発表したニュースは多くの人の模写を引き起こした.
悲しいでしょう...试験が终わった...
......実は何も言うことはありません...こんにゃくの言い訳ばかり..
...自分はやっぱり中途半端なレベルなんですね...
...みんなが省隊に入ることを祈ります...本当は残念な思いさえしなければいいのにね...
残念ながら歩いていけないかも・・・
886
ネット上で広く伝わる模写は、あるところに独特の点があるため、「○○体」と命名されることが多い.人を开いて、微博を更新して、あなたもこのような体を発见することができて、例えば、体に合わないで、**は彼があなたの体を爱していることを说明します.金さんはこの現象に気づき、価値のある研究課題だと鋭敏に考え、研究を展開し、paperを送ろうとした.ネット上でメッセージを送るため、人々はもっと柔軟性があって、人々は时には表現の需要のため、またもとの固定したA、B、Cの中にいくつか修飾の言葉を追加します.これにより、ある文や段落が別の文や段落であるかどうかを判別するのに困難が増す.
金さんは今、「ABC」のような形の体作品を研究しています.その中で、A、B、Cはそれぞれいくつかの単語からなる短文で、*は0つ以上の単語を表しています.彼はネット上で大量の体作品を探したが、多くの体作品は原作者のフォーマットに合わない.つまり、正規の体作品に0つ以上の単語を挿入したに相当する.
データ量が多すぎて、金さんは一つ一つ見ることができないので、できるだけ少ない単語を削除して、指定された体にしたいと思っています.
にゅうしゅつりょくけいしき
入力形式:
4行を含む.
1行目はある規範的でないかもしれない体作品Tで、
次の3行はそれぞれA,B,Cを表す.
出力フォーマット:
1行のみで、単語数を最小限に抑える数が含まれます.
入出力サンプル
入力サンプル#1:コピー
xiang yao yi zhi ai zhe mou wu de hua yi yao guai zhi si lai shuo tai chang le xiang yao shi xian yi qie meng xiang de hua yi ren lei zhi sheng lai shuo tai duan le yao tai chang le yao tai duan le
出力サンプル#1:コピー
2
説明
【サンプル説明】
上記の例では、規範化されていない作品は「何かを愛し続けるには、妖怪の死が長すぎる.すべての夢を実現するには、人間の生が短すぎる」というものです.
規範的な体形は「長すぎると短すぎる」.
「何かを爱し続けるには、妖怪の死が长すぎる.すべての梦を実现するには、人间の生が短すぎる」.
【データ規模と約束】
20%のデータについては,1≦|T|,|A|,|B|,|C|≦10である.40%のデータに対して、1≦|T|,|A|,|B|,|C|≦100である.70%のデータに対して、1≦|T|,|A|,|B|,|C|≦1000である.100%のデータに対して、1≦|T|,|A|,|B|,|C|≦50000;すべての単語の長さは5を超えず、出現回数は500を超えない.データは答えが常に存在することを保証します.
問題解
本題の2つの難点.
1.読解問題は単語ごとに500個を超えないので注意してください.2.カード読み込みは改行読み込みが玄学だそうです.私は今までどうして私のローカルACのコードを知らないで、ずっとBZOJとX谷の上でRE.
簡単な欲張りです.Aに対して、Cは必ず両端を優先して選ぶことができます.Bについては、単語の繰り返しが500回を超えないので、Bと同じ500個の先頭を見つけて、(O(len|T|))を強引に走るたびに、最小値を取ればいいのです.
Code
転載先:https://www.cnblogs.com/hhh1109/p/10667126.html
タイトルの説明
普段の練習や試験では、命題者が例文を出して、私たちに文を書くようにしなければならないという問題によく遭遇します.このようなよく似たような問題は、小学生の試験だけでなく、中試験にも登場することがある.多くの学生はこのような問題をするのが好きだ.他の問題より面白いからだ.模写された文は往々にして「A_B_C」の形式を有し、ここでA,B,Cは1つ以上の単語からなる短文であり、空の部分は学生が記入する必要がある.もちろん、試験の時は空いていてもいいです.例えば、「実は空は暗くなくて昙り果てて散って、実は、実は、道は远くなくてすべて愿い通りになることができて、苦しい日の中で私はあなたのために祈って、あなたに毎日を大切にしてください」.例えば、「海の荒れ狂うのを見て、大山の高くそびえるのを見たことがなくて、本当に残念です;大山の高くそびえるのを見て、見たことがなくて、やはり残念です.出発しましょう、永遠に出発します.、人は不老の気持ちがあります.」
今はネット時代なので、私たちは命題の人命の問題を模写するしかありません.私たちはネット上のいろいろな文と段落を模写することができます.2011年3月26日、ある人がブログで発表したニュースは多くの人の模写を引き起こした.
悲しいでしょう...试験が终わった...
......実は何も言うことはありません...こんにゃくの言い訳ばかり..
...自分はやっぱり中途半端なレベルなんですね...
...みんなが省隊に入ることを祈ります...本当は残念な思いさえしなければいいのにね...
残念ながら歩いていけないかも・・・
886
ネット上で広く伝わる模写は、あるところに独特の点があるため、「○○体」と命名されることが多い.人を开いて、微博を更新して、あなたもこのような体を発见することができて、例えば、体に合わないで、**は彼があなたの体を爱していることを说明します.金さんはこの現象に気づき、価値のある研究課題だと鋭敏に考え、研究を展開し、paperを送ろうとした.ネット上でメッセージを送るため、人々はもっと柔軟性があって、人々は时には表現の需要のため、またもとの固定したA、B、Cの中にいくつか修飾の言葉を追加します.これにより、ある文や段落が別の文や段落であるかどうかを判別するのに困難が増す.
金さんは今、「ABC」のような形の体作品を研究しています.その中で、A、B、Cはそれぞれいくつかの単語からなる短文で、*は0つ以上の単語を表しています.彼はネット上で大量の体作品を探したが、多くの体作品は原作者のフォーマットに合わない.つまり、正規の体作品に0つ以上の単語を挿入したに相当する.
データ量が多すぎて、金さんは一つ一つ見ることができないので、できるだけ少ない単語を削除して、指定された体にしたいと思っています.
にゅうしゅつりょくけいしき
入力形式:
4行を含む.
1行目はある規範的でないかもしれない体作品Tで、
次の3行はそれぞれA,B,Cを表す.
出力フォーマット:
1行のみで、単語数を最小限に抑える数が含まれます.
入出力サンプル
入力サンプル#1:コピー
xiang yao yi zhi ai zhe mou wu de hua yi yao guai zhi si lai shuo tai chang le xiang yao shi xian yi qie meng xiang de hua yi ren lei zhi sheng lai shuo tai duan le yao tai chang le yao tai duan le
出力サンプル#1:コピー
2
説明
【サンプル説明】
上記の例では、規範化されていない作品は「何かを愛し続けるには、妖怪の死が長すぎる.すべての夢を実現するには、人間の生が短すぎる」というものです.
規範的な体形は「長すぎると短すぎる」.
「何かを爱し続けるには、妖怪の死が长すぎる.すべての梦を実现するには、人间の生が短すぎる」.
【データ規模と約束】
20%のデータについては,1≦|T|,|A|,|B|,|C|≦10である.40%のデータに対して、1≦|T|,|A|,|B|,|C|≦100である.70%のデータに対して、1≦|T|,|A|,|B|,|C|≦1000である.100%のデータに対して、1≦|T|,|A|,|B|,|C|≦50000;すべての単語の長さは5を超えず、出現回数は500を超えない.データは答えが常に存在することを保証します.
問題解
本題の2つの難点.
1.読解問題は単語ごとに500個を超えないので注意してください.2.カード読み込みは改行読み込みが玄学だそうです.私は今までどうして私のローカルACのコードを知らないで、ずっとBZOJとX谷の上でRE.
簡単な欲張りです.Aに対して、Cは必ず両端を優先して選ぶことができます.Bについては、単語の繰り返しが500回を超えないので、Bと同じ500個の先頭を見つけて、(O(len|T|))を強引に走るたびに、最小値を取ればいいのです.
Code
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+5;
int n,a,b,c,ans;
string s[N],A[N],B[N],C[N];
int main(){
char ss;n++;
/*while(1){
ss=getchar();
if(ss=='
')break;
if(ss==' '){n++;continue;}
s[n]+=ss;
}a++;
while(1){
ss=getchar();
if(ss=='
')break;
if(ss==' '){a++;continue;}
A[a]+=ss;
}b++;
while(1){
ss=getchar();
if(ss=='
')break;
if(ss==' '){b++;continue;}
B[b]+=ss;
}c++;
while(1){
ss=getchar();
if(ss=='
')break;
if(ss==' '){c++;continue;}
C[c]+=ss;
}*/
do{
cin>>s[++n];
}while(getchar()==' ');
do{
cin>>A[++a];
}while(getchar()==' ');
do{
cin>>B[++b];
}while(getchar()==' ');
do{
cin>>C[++c];
}while(getchar()==' ');
int l=1,r=n,top1=1,top2=c;
while(1){
if(top1==a&&s[l]==A[a]){ans+=l-a;break;}
if(s[l]==A[top1])top1++;l++;
}
while(1){
if(top2==1&&s[r]==C[1]){ans+=n-r+1-c;break;}
if(s[r]==C[top2])top2--;r--;
}l++;r--;int sum=200000000,cnt=20000000,top3,x;
for(int i=l;i<=r;i++){
if(s[i]==B[1]){
top3=1;cnt=0;x=i;
while(1){
if(x>r){cnt=2e9;break;}
if(top3==b&&s[x]==B[b])break;
if(s[x]==B[top3])top3++,x++;else x++,cnt++;
}sum=min(sum,cnt);
}
cout< 転載先:https://www.cnblogs.com/hhh1109/p/10667126.html