2017年ICPC中国大陸地域大会銅メダル問題解

北京E題Cats and Fish
标题:n匹の猫がいてm匹の魚を食べて、それからすべての猫が魚を食べるスピードが異なって、ciで、、、、それから今の魚を食べ終わって次の魚を引き続き食べることができて、x分を経た後にまだ何匹の完全な魚が残って何匹の不完全な魚が残っていますかと聞きます.
構想:シミュレーション、この過程を簡単にシミュレーションすればいいので、現在の猫が魚を食べているかどうかをbool配列で記録します.時間が経つにつれて、今の時間に魚を食べ終わったら、魚がいるかどうか、まだ時間があるかどうかを見て、もしあれば、この猫は魚を食べ続けます.さもないと魚を食べている時間です.visを変えればいい.

#include

using namespace std;
int a[1005];
bool vis[1005];

int main(){
     
	int n,m,x;
	while(cin>>m>>n>>x){
     
		memset(vis,0,sizeof(vis)); 
		for(int i=0;i<n;i++) cin>>a[i];
		if(x == 0){
     
			cout<<"m 0"<<endl;
			continue;
		}
		sort(a,a+n);//        
		for(int i=0;i<n;i++){
     
			if(m>0){
     //          
				vis[i] = 1;//           
				m--;
			}
		}
		for(int i=1;i<=x;i++){
     //    
		  for(int j=0;j<n;j++){
     //   
		  if(i%a[j]==0 && m>0 &&i!=x)  m--;//     ，         ，      
          else if(i%a[j]==0) vis[j]=0;//    ，       
		  }	
		}
		int ans = 0;
		for(int i=0;i<n;i++){
     
			if(vis[i]) ans++;
		} 
		cout<<m<<" "<<ans<<endl;
	}
	return 0;
} 

F題Secret Poems
図から変わった図を印刷して、そのまま見本を見て理解しました.でも本当に悪い癖ですよ.しばらく見ても法則が何なのか分かりません.前にやった蛇行行列を戻し行列にしたのですが、こんなテーマは嫌です!!!まず穴をあける.
J題Pangu and Stones
标题:一山の石があって、毎回LからRの石を一山にまとめるしかなくて、すべての石にはすべて1つの时間があって、毎回合併する必要がある时間は合併する石の総和に等しくて、それからあなたにこの石を合併するのに必要な最小限の解決時間を求めさせて、もし解決策がなければ0を出力します.
考え方:emmm...問題を手に入れるのも難しくないし、以前もこのような問題に出会ったことがあるようです.はい、私は廃物です.1時間もやったのにdpが思いもよらなかったのです.
参考大男の考え方:状態遷移:dp[I][j][k]はIからjまでの石区間をk山に分ける場合を表す
k=1の場合、石はLからRのスタックに合併してdp[I][j][k]=max(dp[I][j][k],dp[I][j][d]+num[j]-num[I-1]のスタックを持つことができ、ここでdはスタック数(L<=d<=R)を表す.numは接頭辞和の配列です.
k!=1の場合、石は石Aとk-1の石Bの合併と理解でき、dp[I][j][k]=max(dp[I][j][k]、dp[I][e][1]+dp[e+1][j][k-1])もあり、ここでのeはAとBの境界点、つまり普通の区間dpを表しており、次のコードは比較的明確になっている.

#include
#include
#define mem(s,t) memset(s,t,sizeof(s))
using namespace std;
int dp[105][105][105];
int val[105];
int sum[105];
int main()
{
     
    int n,l,r;
    while(cin>>n>>l>>r)
    {
     
        mem(sum,0);
        for(int i=1;i<=n;i++){
     
            cin>>val[i];
            sum[i]=sum[i-1]+val[i]; //    ，    
        }
        mem(dp,0x3f);
        for(int i=1;i<=n;i++){
     
            dp[i][i][1]=0;
        }//   ，                    0

        for(int i=2;i<=n;i++){
     //    
            for(int j=1;j<=n;j++){
     //  
                int e=i+j-1;
                if(e>n)break;//      n
                for(int k=i;k>=1;k--){
     //    
                    if(k==1){
     
                        for(int z=l;z<=r;z++)
                        dp[j][e][k]=min(dp[j][e][k],dp[j][e][z]+sum[e]-sum[j-1]);
                    }else{
     
                        for(int z=j;z<e;z++)
                        dp[j][e][k]=min(dp[j][e][k],dp[j][z][1]+dp[z+1][e][k-1]);
                    }
                }
            }
        }
        if(dp[1][n][1]!=0x3f3f3f3f)cout<<dp[1][n][1]<<endl;
        else cout<<0<<endl;
    }
}

南寧A-Abiyoyo題意:事実に基づいて速やかに署名する

#include
using namespace std;
int main(){
     
    int t,k;
    scanf("%d",&t);
    while(t--){
     
        scanf("%d",&k);
        for(int i=0;i<k;i++){
     
            printf("Abiyoyo, Abiyoyo.
");
        }
        printf("Abiyoyo, yo yoyo yo yoyo.
");
        printf("Abiyoyo, yo yoyo yo yoyo.
");
    }
    return 0;
}

F題The Chosen One題意:
n人の子供が一列に並んでいて、奇数の位置に立っている子供を除去するたびに、最後にどれが残っているかを聞いています.
考え方:自分でシミュレーションとサンプルを見てみると、nより小さい2の最大乗数を求めることがわかります.pyとjaveで簡単そうです.

#include   

using namespace std; 

char anss[205][100],temp[205][100];
int jin=0,cnt=0,i,j,t,lang[200];



int main()
{
     
    anss[0][0]='1';
    for(i=1;i<=200;i++)
    {
     
        for(j=0;j<=cnt;j++)
        {
     
        
            anss[i][j]=((anss[i-1][j]-'0')*2+jin)%10+'0';
            jin=((anss[i-1][j]-'0')*2+jin)/10;
        }
  
        while(jin){
     
            anss[i][++cnt]=jin%10+'0';
            jin=jin/10;
   
        }
        lang[i]=cnt;
    }
    for(i=1;i<=200;i++)
    {
     
        for(j=lang[i];j>=0;j--)
        {
     
            temp[i][lang[i]-j]=anss[i][j];
        }    
    }
    cin>>t;
    while(t--)
    {
     
        char str[200];
        cin>>str;
        for(i=0;i<200;i++)
        {
     
            int flag1=0;
            int flag2=0;
            if(strlen(str)<lang[i+1]+1)
            {
     
                cout<<temp[i]<<endl;
                break;
            }
            if(strlen(str)>lang[i]+1&&strlen(str)==lang[i+1]+1)
            {
     
                if(strcmp(temp[i+1],str)>0)
                {
     
                    cout<<temp[i]<<endl;
                    break;
                }
            }
            if(strlen(str)==lang[i]+1&&strlen(str)==lang[i+1]+1)
            if(strcmp(temp[i],str)<=0&&strcmp(temp[i+1],str)>0)
            {
     
                cout<<temp[i]<<endl;
                break;
            }
        }
    }
}

私のブログは間もなくテンセントの雲+コミュニティに同期して、みんなを招待して一緒に入居します:雲+コミュニティに入居します