2017-10-27

2016ccpc杭州

HDU 5933

题目要求

给出n个数字的大小问能否通过某种操作变成大小全部相等的k堆
有两种操作：把相邻的两堆合并把一堆拆成两堆
问最小的操作次数无解输出-1

参考AC代码

#include<bits/stdc++.h>
#define maxn 100050
#define LL long long
using namespace std;
deque<LL>q;
int t,n,k;
int Case=1;
int main(){
//    freopen("input.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        q.clear();
        LL sum=0;
        for(int i=1;i<=n;i++){
            LL x;
            scanf("%d",&x);
            sum+=x;
            q.push_back(x);
        }
        printf("Case #%d: ",Case++);
        if(sum%k!=0){
            puts("-1");
            continue;
        }
        LL temp=sum/k;
        int ans=0;
        while(!q.empty()){
            LL x=q.front();
            q.pop_front();
            if(x==temp) continue;
            else if(x>temp){
                q.push_front(x-temp);
                ans++;
            }
            else if(x<temp){
                while(!q.empty()){
                    LL y=q.front();
                    q.pop_front();
                    ans++;
                    x+=y;
                    if(x>=temp){
                        q.push_front(x);
                        break;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

思路

双端队列模拟(普通队列也可以答案跟合并顺序无关)
若大于平均数temp 拆成temp和x-temp
若小于temp 向后合并直到大于temp 再次执行上一次操作

HDU 5934

转跳链接

HDU 5935

题目要求

一辆车从t=0开始走速度只能递增可为小数警察在t为整数的时候记录了N个车的位置(整数) 问到达最后一个位置时最少开了多久

参考AC代码

#include<bits/stdc++.h>
#define maxn 100050
#define LL long long
using namespace std;
int t,n;
LL a[maxn];
int Case=1;
int main(){
//    freopen("input.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        LL fenzi=a[n]-a[n-1],fenmu=1;
        LL time=1;
        for(int i=n-1;i>=1;i--){
            LL d=a[i]-a[i-1];  
            fenmu*=d;  
            LL tmp=fenmu/fenzi;  
            if(fenmu%fenzi!=0) tmp++;
            time+=tmp;  
            fenzi=d;  
            fenmu=tmp;  
        }
        printf("Case #%d: %lld\n",Case++,time);
    }
    return 0;
}

思路

贪心模拟
这题会卡精度
用分子分母模拟
先除再乘会损失精度所以我们先乘再除

HDU 5938

题目要求

给出长度为20的字符串每个位置为1-9
现在我们把他分成5段四个间隔上依次加上+-×/四种符号问能获得的最大数字是多少

参考AC代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL inf=(LL)1e18;
int t,Case=1;
char s[30];
int main(){
//    freopen("input.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        scanf("%s",s+1);
        int len=strlen(s+1);
        LL ans=-inf;
        for(int i=1;i<=len-4;i++){
            LL a=0;
            for(int j=1;j<=i;j++) a=a*10*1LL+(s[j]-'0')*1LL;
            for(int j=i+1;j<=len-3;j++){
                LL b=0,c=0,d=0,e=0;
                for(int k=i+1;k<=j;k++) b=b*10*1LL+(s[k]-'0')*1LL;
                c=s[j+1]-'0';
                d=s[j+2]-'0';
                for(int k=j+3;k<=len;k++) e=e*10*1LL+(s[k]-'0')*1LL;
                ans=max(ans,a+b-c*d/e);
            }
        }
        printf("Case #%d: %lld\n",Case++,ans);
    }
    return 0;
}

思路

贪心模拟
要使减号后面的数字尽可能小所以c和d只取一位剩下的自然是e 所以只需n²枚举加号和减号即可
注意答案可能为负数 ans初始化为-inf 以及会爆int
注意b初始化的位置

本文标题:2016ccpc杭州

文章作者:Hippopmonkey

发布时间:2017-10-27, 10:29:22

最后更新:2017-10-27, 10:44:21

原始链接:http://xuboming8.github.io/2017/10/27/2016ccpc杭州/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。