首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2017 年ICPC 中国大陆区域赛铜牌题解

2017 年ICPC 中国大陆区域赛铜牌题解

作者头像
杨鹏伟
发布2020-09-10 23:47:10
4140
发布2020-09-10 23:47:10
举报
文章被收录于专栏:ypwypw

北京 E 题 Cats and Fish

题意:有n只猫m条鱼,然后每只猫吃鱼的速度不同,为ci,,,然后吃完当前鱼可以继续吃下一条,问经过x分钟后还剩下几只完整的鱼几只不完整的鱼。

思路:模拟,简单模拟这个过程就行,我们用一个bool数组来记录当前猫是否在吃鱼。遍历时间渐推,如果当前时间点吃完鱼,看是否还有鱼,还有时间,如果有的话,这只猫继续吃鱼。否则就是正在吃鱼时间到了。将vis改变即可。

#include<bits/stdc++.h>

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的石头合并成一堆,每一个石头都有一个时间,,每次需要合并的时间等于合并的石头总和,然后让你求合并这堆石头需要的最少的解决时间,如果没有解决方案就输出0。

思路:emmm…拿到题看着也不难,以前好像也遇见过这样子的题目。好的,我是废物,做了一个小时愣是想不到dp…

参考大佬思路: 状态转移:dp[I][j][k]表示从I到j的石头区间里分成k堆的情况

当k=1时,石头可以从L到R堆合并为1堆有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<iostream>
#include<cstring>
#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<bits/stdc++.h>
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.\n");
        }
        printf("Abiyoyo, yo yoyo yo yoyo.\n");
        printf("Abiyoyo, yo yoyo yo yoyo.\n");
    }
    return 0;
}

F F 题 The Chosen One 题意:

有n个小孩排成一排,每次除去站在奇数位置上的小孩,问最后剩下哪一个

思路:自己动手看看模拟一下与样例,就会发现求得是小于n的2的最大次幂。 好像用py跟jave简单。

#include <bits/stdc++.h>  

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;
            }
        }
    }
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-09-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档