牛客練習試合23:AB C D
A貪欲な考えで、できるだけ大きいものを選んで、このように支出する紙の切符の数と硬貨の数の和の最小コード:
B法則を探してf[i]が数字iを表す最大得点を設定すると、f[1]=0 f[2]=11=1 f[3]=f[2]+21=1+0+2=3 f[4]=f[2]+2]+f[2]+22=2+1+4=6 f[5]=f[3]+2=3+1+6=10 f[6]=f[3]+f[3]+3=3+3+3+3+3+9=15 f[7]=f[4]+f[3]+43=6+32=21
なぜnを均一または均一に近い2つに分けるのでしょうか.欲張り思想に基づいているので、結果はもっと大きくなるでしょう.証明?まさか...次はこの法則がわかりやすいでしょうf[2]-f[1]=1 f[3]-f[2]=2 f[4]-f[3]=3 f[5]-f[4]=4 f[6]-f[5]=5 f[7]-f[6]-f[6]=6...f[n]-f[n-1]=n-1
したがって、f[n]=(1+n-1)(n-1)/2=n(n-1)/2は、公差が1の等差数列接頭辞和である
コード:
C実はよく考えてみると、Kが出力するのを見ていないので、むだに4回もWAして、自分のコードに問題があると思って、コードをチェックして行って、出力がはっきり見えません.の
私の考え方:大きいから小さいまで列挙して位と低いビットbit(0<=bit<=30)、つまり列挙30-0これらのビットが状況に合えばすぐにbreakして、つまり答えを見つけて、そしてリアルタイムに集合の中で状況に合っている数が合わないことを保存して、どのように符が状況に合っていないことを知っていますか?実は考えてみてください.ビット数が1のとき、私たちはそれを集合に入れるに違いありません.なぜですか.私たちがこの数を加えると、bitビットより低いビットがビットと0になる可能性が高くなりますよね.そうすれば、ビットと最下位ビットがbitビットになる可能性が高いのではないでしょうか.考えてみれば、ビット対の最下位ビットを列挙するとき、私たちはビット1の数をすべてビット対にし、得られた数の最下位ビットが1<まだ理解していない場合は、コードを見てください.
D問題の理解が間違っていますか?もともと配列ごとに1回しか貢献できないので、簡単ではありません.私たちはすべての「a」-「i」の配列を列挙することができます.この配列が文字列のサブシーケンスであるかどうかを見て、そうであれば、貢献は+1でどのようにその配列が文字列のサブシーケンスであるかどうかを判断しますか.各配列の各文字には順番があるでしょう(つまり位置関係)、前の文字が後の文字より現れる位置は必ず前の文字、つまり下の文字より小さいので、その配列の1文字が文字列に現れる位置が前の文字よりも文字列に現れる位置があるかどうかを判断するだけで、私はあらかじめvectorで'a'-'i'を文字列の複数の位置に保存しておきましたので、位置関係を判断し、これらのvectorに二分すれば良いのですが(詳細はコードを参照)、配列の各位置文字が状況を満たしていれば、その配列が文字列のサブシーケンスであることを説明します.寄与+1詳細はコードを参照してください
コード:
#include
using namespace std;
int yuan[]={100,50,20,10,5,2,1};
int fen[]={50,20,10,5,2,1};
int num[20];
int main(){
int T;
scanf("%d",&T);
while(T--){
int a,b;
scanf("%d%d",&a,&b);
for(int i=0;i<7;i++){
num[i]=a/yuan[i];
a-=num[i]*yuan[i];
}
for(int i=0;i<6;i++){
num[i+7]=b/fen[i];
b-=num[i+7]*fen[i];
}
for(int i=0;i<=12;num[i]=0,i++) printf("%d%c",num[i],i==12?'
':' ');
}
}
B法則を探してf[i]が数字iを表す最大得点を設定すると、f[1]=0 f[2]=11=1 f[3]=f[2]+21=1+0+2=3 f[4]=f[2]+2]+f[2]+22=2+1+4=6 f[5]=f[3]+2=3+1+6=10 f[6]=f[3]+f[3]+3=3+3+3+3+3+9=15 f[7]=f[4]+f[3]+43=6+32=21
なぜnを均一または均一に近い2つに分けるのでしょうか.欲張り思想に基づいているので、結果はもっと大きくなるでしょう.証明?まさか...次はこの法則がわかりやすいでしょうf[2]-f[1]=1 f[3]-f[2]=2 f[4]-f[3]=3 f[5]-f[4]=4 f[6]-f[5]=5 f[7]-f[6]-f[6]=6...f[n]-f[n-1]=n-1
したがって、f[n]=(1+n-1)(n-1)/2=n(n-1)/2は、公差が1の等差数列接頭辞和である
コード:
#include
using namespace std;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
printf("%lld
",(long long)n*(n-1)/2);
}
}
C実はよく考えてみると、Kが出力するのを見ていないので、むだに4回もWAして、自分のコードに問題があると思って、コードをチェックして行って、出力がはっきり見えません.の
私の考え方:大きいから小さいまで列挙して位と低いビットbit(0<=bit<=30)、つまり列挙30-0これらのビットが状況に合えばすぐにbreakして、つまり答えを見つけて、そしてリアルタイムに集合の中で状況に合っている数が合わないことを保存して、どのように符が状況に合っていないことを知っていますか?実は考えてみてください.ビット数が1のとき、私たちはそれを集合に入れるに違いありません.なぜですか.私たちがこの数を加えると、bitビットより低いビットがビットと0になる可能性が高くなりますよね.そうすれば、ビットと最下位ビットがbitビットになる可能性が高いのではないでしょうか.考えてみれば、ビット対の最下位ビットを列挙するとき、私たちはビット1の数をすべてビット対にし、得られた数の最下位ビットが1<
#include
using namespace std;
const int maxn=100000+100;
int ans[maxn];
int tmp[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i=0;bi--){
int now=-1;
for(int i=0;i>bi)&1){
tmp[++tot]=ans[i];
if(now==-1) now=ans[i];
else now=now&ans[i];
}
}
if(now==-1 || (now&(-now))
D問題の理解が間違っていますか?もともと配列ごとに1回しか貢献できないので、簡単ではありません.私たちはすべての「a」-「i」の配列を列挙することができます.この配列が文字列のサブシーケンスであるかどうかを見て、そうであれば、貢献は+1でどのようにその配列が文字列のサブシーケンスであるかどうかを判断しますか.各配列の各文字には順番があるでしょう(つまり位置関係)、前の文字が後の文字より現れる位置は必ず前の文字、つまり下の文字より小さいので、その配列の1文字が文字列に現れる位置が前の文字よりも文字列に現れる位置があるかどうかを判断するだけで、私はあらかじめvectorで'a'-'i'を文字列の複数の位置に保存しておきましたので、位置関係を判断し、これらのvectorに二分すれば良いのですが(詳細はコードを参照)、配列の各位置文字が状況を満たしていれば、その配列が文字列のサブシーケンスであることを説明します.寄与+1詳細はコードを参照してください
コード:
#include
#include
#include
#include
using namespace std;
const int maxn=3000+100;
char ch[maxn];
int id[maxn];
vectorG[10];
int ind[10]={0,1,2,3,4,5,6,7,8}; // 'a'-'i'
int main(){
while(scanf("%s",ch)==1){
int len=strlen(ch);
for (int i=0;i=G[ind[i]].size()) {
isok=false;
break;
}
locate=G[ind[i]][locate];
}
if(isok) ans++;
}while(next_permutation(ind,ind+9));
printf("%d
",ans);
}
return 0;
}