专栏首页ypw2017 年ICPC 中国大陆区域赛铜牌题解

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

北京 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;
            }
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最快最简单的排序---桶排序

    是不是很好理解,就是开一个比最大数据大或者等于的一个数组,然后相应的桶遇到数就++,最后输出就行了。

    用户7727433
  • 牛客小白月赛22 A~~J

    A.链接:https://ac.nowcoder.com/acm/contest/4462/A 来源:牛客网

    用户7727433
  • AtCoder Beginner Contest 177 A ~ E

    C 思路:数据范围比较大,O(n^n)的复杂度肯定不可以,那么我们要分析式子 假设有一组数据:

    用户7727433
  • Backpack problem

    AngelNH
  • 【POJ 2923】Relocation(状压DP+DP)

    题意是给你n个物品,每次两辆车运,容量分别是c1,c2,求最少运送次数。 好像不是很好想,我看了网上的题解才做出来。 先用状压DP计算i状态下,第一辆可以运送的...

    饶文津
  • HDU-4539郑厂长系列故事——排兵布阵(状态压缩,动态规划)

    郑厂长系列故事——排兵布阵 Time Limit : 10000/5000ms (Java/Other) Memory Limit : 65535/3276...

    ShenduCC
  • 牛客网2018年全国多校算法寒假训练营练习比赛(第二场)

    Zoctopus
  • 程序员进阶之算法练习(九)附两道扩展题答案

    前言 在上文程序员进阶之算法练习(八)附两道搜狐笔试题中,在搜狐笔试题的基础上稍微改编后的题目: 《宝石二》 有一串宝石首尾相连,用一个大写字母表示一个宝...

    落影
  • 87. [NOIP2000] 乘积最大

    ★☆   输入文件:cjzd.in   输出文件:cjzd.out 简单对比 时间限制:1 s   内存限制:128 MB   问题描述 今年是国际...

    attack
  • 几道暑期实习笔试题

    DFS 回溯法,先判断组成三连对和组成顺子需要的次数,递归深度 k 就是次数。对于对子和单张的可以直接通过枚举数需要打多少次。可以在组成三连对和顺子的时候增加剪...

    echobingo

扫码关注云+社区

领取腾讯云代金券