2018「百度の星」プログラムデザインコンテスト-資格試合A B C E F
1001考え方:
問題数mは10を超えないので、問題数mを状態圧縮し、各状態についていくつかの問題の集合を得ることができ、これらの問題集合はこのm個の問題集合に属し、重複しないので、各状態に基づいてn人のこの状態での回答状況を得ることができる.各質問の答えは「A」か「B」しかないので、このn人のこの状態での答えを2進数(「A」は0「B」は1)に変えて、このn人の中でどれだけ異なる答えがあるかを簡単に得て、kと比較してカウントすればいい.
コード:
1002考え方:
私は莫隊で書いたので、このような区間の問題を書くかもしれません.私は莫隊で書くことに慣れました.莫隊がこの問題を書くのも簡単です.もちろん、他の考えもできます.例えば、接頭辞や何かを書くと、私は繰り返し書きません.次は莫隊の考えのコードです.
コード:
1003考え方:
条件x[i]+y[j]<=a[i][j]求x[1]+x[2]+...+x[n]+y[1]+y[2]+...+y[n]の最大値x[]とy[]を2つ組み合わせることができます.例えば、n=2の場合、1つ目はx[1]+y[1]、x[2]+y[2]+a[1][1]、a[2][2]2つ目はx[1]+y[2]、x[2]+y[1]はa[1][2]、a[2][1]だから答えはmin(a[1][1]+a[2][2],a[1][2]+a[2][1])だから答えは行列が同行しない異なる列の中でn個の数の最小値を取って、KMで私のKMの板の品質があまりにも悪いことを責めることができて、試合の時無限Tの下のコードは私の新しいKMの板です
コード:DFS実装
BFS実装
1005考え方:
データがランダムなので、データの中で各配列の最長上昇サブシーケンス長の期待はn^(0.5)(問題解説の、私も知らない)なので、試合の時、ダイナミックプランニングの解法を考えましたが、dp[ind][len]=sum(dp[res][len-1])(ind>res,id[res]コード:
1006考え方:Q神の題解をコピーします:
条件を満たすk本のエッジは、必然的に赤色エッジと緑色エッジからなる最小生成ツリーまたは青色エッジと緑色エッジからなる最小生成ツリーを含み、1つの図中のすべての最小生成ツリーのエッジ重み集合が同じであることを証明することは難しくないので、2つの状況に対してそれぞれ1つの最小生成ツリーを求めることができ、さらに,最小生成ツリーにないエッジを,エッジ重みが小さい順に加える.
コード:
問題数mは10を超えないので、問題数mを状態圧縮し、各状態についていくつかの問題の集合を得ることができ、これらの問題集合はこのm個の問題集合に属し、重複しないので、各状態に基づいてn人のこの状態での回答状況を得ることができる.各質問の答えは「A」か「B」しかないので、このn人のこの状態での答えを2進数(「A」は0「B」は1)に変えて、このn人の中でどれだけ異なる答えがあるかを簡単に得て、kと比較してカウントすればいい.
コード:
#include
#include
using namespace std;
const int maxn=1000+10;
char ch[maxn][20];
int kaven[maxn];
int M[1<<11];
int main(){
int T,C=0;
scanf("%d",&T);
while(T--){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
getchar();
for(int i=1;i<=n;i++) scanf("%s",ch[i]);
if(n*(n-1)/2>t&1 && ch[j][t]=='B'){
tot+=(1<=k) cnt++;
}
printf("Case #%d: %d
",++C,cnt);
}
}
1002考え方:
私は莫隊で書いたので、このような区間の問題を書くかもしれません.私は莫隊で書くことに慣れました.莫隊がこの問題を書くのも簡単です.もちろん、他の考えもできます.例えば、接頭辞や何かを書くと、私は繰り返し書きません.次は莫隊の考えのコードです.
コード:
#include
#include
#include
using namespace std;
const int maxn=100000+100;
char ch[maxn];
struct Mo{
int l,r;
int id;
}mo[maxn];
int R[maxn];
int Ans[maxn];
int num[30];
inline bool cmp(Mo a,Mo b){
return R[a.l]==R[b.l]?a.rmo[i].l) kaven(l-1,1),l--;
while(rmo[i].r) kaven(r,-1),r--;
int key;
for(key=0;key<=25;key++) if(num[key]) break;
Ans[mo[i].id]=num[key];
}
printf("Case #%d:
",++C);
for(int i=1;i<=m;i++) printf("%d
",Ans[i]);
}
}
1003考え方:
条件x[i]+y[j]<=a[i][j]求x[1]+x[2]+...+x[n]+y[1]+y[2]+...+y[n]の最大値x[]とy[]を2つ組み合わせることができます.例えば、n=2の場合、1つ目はx[1]+y[1]、x[2]+y[2]+a[1][1]、a[2][2]2つ目はx[1]+y[2]、x[2]+y[1]はa[1][2]、a[2][1]だから答えはmin(a[1][1]+a[2][2],a[1][2]+a[2][1])だから答えは行列が同行しない異なる列の中でn個の数の最小値を取って、KMで私のKMの板の品質があまりにも悪いことを責めることができて、試合の時無限Tの下のコードは私の新しいKMの板です
コード:DFS実装
#include
#include
using namespace std;
#define MEM(a,b,start,end) for(int ii=start;ii<=end;ii++) a[ii]=b
#define max(a,b) a>b?a:b
#define min(a,b) aslack[j]) tmp=slack[j];
}
for(int j=1;j<=n;j++){
if(visx[j]) valx[j]-=tmp;
if(visy[j]) valy[j]+=tmp;
else slack[j]-=tmp;
}
for(int j=1;j<=n;j++){
if(!visy[j] && slack[j]==0){
visy[j]=true;
if(match[j]==-1 || DFS(match[j],0)){
isok=false;
break;
}
}
}
}
MEM(visx,false,1,n);
MEM(visy,false,1,n);
DFS(i);
}
long long res=0;
for(int i=1;i<=n;i++) res+=xy[match[i]][i];
return res;
}
int main(){
int T,C=0;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
valx[i]=-INF;
valy[i]=0;
match[i]=-1;
for(int j=1;j<=n;j++) scanf("%d",&xy[i][j]),xy[i][j]*=-1,valx[i]=max(valx[i],xy[i][j]);
}
printf("Case #%d: %lld
",++C,-KM());
}
}
BFS実装
#include
#include
#include
using namespace std;
#define MEM(a,b,start,end) for(int ii=start;ii<=end;ii++) a[ii]=b
#define max(a,b) a>b?a:b
#define min(a,b) a Q;
Q.push(u);
visx[u]=true;
while(1){
while(!Q.empty()){
int x=Q.front();
Q.pop();
for(int y=1;y<=n;y++){
int tmp=valx[x]+valy[y]-xy[x][y];
if(!visy[y] && tmp<=slack[y]){
pre[y]=x;
if(!tmp){
if(!l[y]){
for(;y;l[y]=pre[y],swap(y,r[pre[y]]));
return;
}
else{
visx[l[y]]=visy[y]=true;
Q.push(l[y]);
}
}
else{
slack[y]=tmp;
}
}
}
}
int tmp=INF;
int node=u;
for(int i=1;i<=n;i++){
if(!visy[i] && slack[i]<=tmp){
node=i,tmp=slack[i];
}
}
for(int i=1;i<=n;i++){
if(visx[i]) valx[i]-=tmp;
if(visy[i]) valy[i]+=tmp;
else slack[i]-=tmp;
}
if(!l[node]){
for(;node;l[node]=pre[node],swap(node,r[pre[node]]));
return;
}
else{
visx[l[node]]=visy[node]=true;
Q.push(l[node]);
}
}
}
void KM(){
for(int i=1;i<=n;i++){
MEM(visx,false,1,n);
MEM(visy,false,1,n);
MEM(slack,INF,1,n);
BFS(i);
}
}
int main(){
int T,C=0;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
valx[i]=-INF;
valy[i]=0;
l[i]=r[i]=pre[i]=0;
for(int j=1;j<=n;j++) scanf("%d",&xy[i][j]),xy[i][j]*=-1,valx[i]=max(valx[i],xy[i][j]);
}
KM();
long long res=0;
for (int i=1;i<=n;i++) res+=(-valx[i]-valy[i]);
printf("Case #%d: %I64d
",++C,res);
}
}
1005考え方:
データがランダムなので、データの中で各配列の最長上昇サブシーケンス長の期待はn^(0.5)(問題解説の、私も知らない)なので、試合の時、ダイナミックプランニングの解法を考えましたが、dp[ind][len]=sum(dp[res][len-1])(ind>res,id[res]
#include
#include
using namespace std;
const int maxn=10000+10;
const int mod=1e9+7;
int tree[maxn][maxn],ans[maxn];
int n;
inline int lowbit(int x){
return x&(-x);
}
inline void Add(int ind,int len,int v){
while(ind<=n){
tree[ind][len]=(tree[ind][len]+v)%mod;
ind+=lowbit(ind);
}
}
inline int getSum(int ind,int len){
int sum=0;
while(ind>0){
sum=(sum+tree[ind][len])%mod;
ind-=lowbit(ind);
}
return sum;
}
int main(){
int T,C=0;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&ans[i]);
for(int i=1;i<=n;i++){
Add(ans[i],1,1);
for(int j=2;j<=i;j++){
int val=getSum(ans[i]-1,j-1);
if(val==0) break;
Add(ans[i],j,val);
}
}
int i;
int val=1;
printf("Case #%d: ",++C);
for(i=1;i<=n;i++){
if(val) {
val=getSum(n,i);
for(int j=1;j<=n;j++) tree[j][i]=0;
}
else val=0;
printf("%d%c",val,i==n?'
':' ');
}
}
}
1006考え方:Q神の題解をコピーします:
条件を満たすk本のエッジは、必然的に赤色エッジと緑色エッジからなる最小生成ツリーまたは青色エッジと緑色エッジからなる最小生成ツリーを含み、1つの図中のすべての最小生成ツリーのエッジ重み集合が同じであることを証明することは難しくないので、2つの状況に対してそれぞれ1つの最小生成ツリーを求めることができ、さらに,最小生成ツリーにないエッジを,エッジ重みが小さい順に加える.
コード:
#include
#include
#include
#include
using namespace std;
#define MEM(a,b) memset(a,b,sizeof(a))
const int maxn=110;
struct Edge{
int from,to,w;
char type;
int id;
Edge(int from_,int to_,int w_,char type_,int id_):from(from_),to(to_),w(w_),type(type_),id(id_){}
};
vectorRG,BG;
int fa[maxn][2];
bool vis[maxn<<2][2];
int n,m;
inline bool cmp(Edge a,Edge b){
return a.w kaven(vector G,int reg,char type1,char type2){
int mst=0; //
int cnt=0; //
for(int i=0;i'Z') type=type-'a'+'A';
RG.push_back(Edge(from,to,w,type,2*i));
RG.push_back(Edge(to,from,w,type,2*i+1));
BG.push_back(Edge(from,to,w,type,2*i));
BG.push_back(Edge(to,from,w,type,2*i+1));
//printf("%d %d %d %c
",from,to,w,type);
}
sort(RG.begin(),RG.end(),cmp);
sort(BG.begin(),BG.end(),cmp);
MEM(vis,false);
for(int i=1;i<=n;i++) fa[i][0]=fa[i][1]=i;
pair rg=kaven(RG,0,'R','G');
pair bg=kaven(BG,1,'B','G');
printf("Case #%d:
",++C);
if(rg.first==1e9 && bg.first==1e9){
for(int i=1;i<=m;i++) printf("-1
");
}
else{
int minedge=min(rg.second,bg.second);
for(int i=1;i