广东工业大学第十三届程序设计竞赛(初赛)部分题解

论坛 › 期权论坛 › 脚本     
已经匿名di用户   2022-5-29 19:06   1736   0

蒟蒻暂时只解了7道题,其他题目有想法但不一定对,没时间补了先搁着
(其实也并不想写但不写的话感觉浪费时间做题更不值..)
Problem A 第k大
被卡nlogn的STL了解一下?

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<bitset>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 1e6+11;
const int MOD = 2520;
const double eps = 1e-10;
typedef long long ll;
const int oo = 0x3f3f3f3f;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll res[maxn],n,a,b,c,k;
void C(int n,unsigned int A, unsigned int B, unsigned int c){
    for(int i=0;i<n;i++){
        res[i]=A+B;
        A=((A<<2)+c)*i*29+B;
        B=(((A+B)<<3)+c)*17;
    }
}
int main(){
    int T=read();
    while(T--){
        cin>>n>>a>>b>>c>>k;
        C(n,a,b,c);
        nth_element(res,res+n-k,res+n);
        printf("%lld\n",res[n-k]);
    }
}

Problem B zhazhahe对于不重复数的研究
dfs

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
using namespace std;
const int maxn = 1e6+11;
typedef long long ll;
ll dp[maxn],tot;
bool vis[12];
int n;
//ll solve(ll t){
//  ll tt=t+1,pos=0;
//  while(tt){
//      a[++pos]=tt%10;
//      tt/=10;
//  }
//  rep(i,1,pos){
//      
//  }
//  return tt;
//}
ll dfs(int cur,ll num,int st){
    if(tot>1000005) return 0;
    if(cur==0&&num==0) return dp[1]=0;
    else if(cur==0) return dp[++tot]=num;
    rep(i,0,9){
        if(st&&i==0){
            dfs(cur-1,0,1);
        }
        if((st&&i!=0)||(!st)){
            if(!vis[i]){
                vis[i]=1;
                dfs(cur-1,num*10+i,0);
                vis[i]=0; 
            }
        }
    }
}

int main(){
    dfs(10,0,1);//cout<<tot<<endl;
//  rep(i,1,100) cout<<i<<" "<<dp[i]<<endl;
    int T; cin>>T;
    while(T--){
        scanf("%d",&n);
        printf("%lld\n",dp[n]);
    }
    return 0;
}

Problem D 颁奖
水题

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<bitset>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 6e4+11;
const int MOD = 2520;
const double eps = 1e-10;
typedef long long ll;
const int oo = 0x3f3f3f3f;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool vis[666];
int n,kind;
int a[666];
int main(){
    while(cin>>n){
        memset(vis,0,sizeof vis);
        kind=0;
        rep(i,1,n) a[i]=read();
        rep(i,1,n){
            if(a[i]&&!vis[a[i]]) kind++;
            vis[a[i]]=1;
        }
        println(kind);
    }
    return 0;
}

Problem E 跳一跳
水题,注意取模时防爆大小

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<bitset>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 1e6+11;
const int MOD = 2520;
const double eps = 1e-10;
typedef long long ll;
const int oo = 0x3f3f3f3f;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll res[maxn],n,a,b,c,k;
void C(int n,unsigned int A, unsigned int B, unsigned int c){
    for(int i=0;i<n;i++){
        res[i]=A+B;
        A=((A<<2)+c)*i*29+B;
        B=(((A+B)<<3)+c)*17;
    }
}
int main(){
    int T=read();
    while(T--){
        cin>>n>>a>>b>>c>>k;
        C(n,a,b,c);
        nth_element(res,res+n-k,res+n);
        printf("%lld\n",res[n-k]);
    }
}

Problem H 三角形

CC特别喜欢三角形，他对三角形的性质了如指掌，他现在有n根木棍，长度为1、2、3……n，他现在从中选出X根木棍，
使得选出的木棍任意三根不能组成三角形，他现在想知道X最大是多少？

所求既两边之和小于等于第三边,边界条件f[i]=f[i-1]+f[i-2],斐波那契走起
PS.题目表述不明确,n<=2也算是合法的

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<bitset>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 1e5+11;
const int MOD = 2520;
const double eps = 1e-10;
typedef long long ll;
const int oo = 0x3f3f3f3f;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll fib[66666];
int main(){
    fib[1]=1;fib[2]=2;
    int up;
    rep(i,3,oo){
        if(fib[i-1]>1e18){
            up=i-1;
            break;
        }else{
            fib[i]=fib[i-1]+fib[i-2];
        }
    }
    int T=read();
    while(T--){
        ll n=read();
        // if(n<=2)println(0);
        ll pos=lower_bound(fib+1,fib+1+up,n)-fib;
        if(fib[pos]>n)pos--;
        println(pos);
    }
    return 0;
}

Porblem K 吃瓜群众rab0t

从小在北方长大的rab0t来到了广工，对这边的天气不太适应，特别是在夏天，这里的温度简直是热到爆炸，于是他爱上了吃冰镇西瓜。
但是瓜价格一般浮动比较大，经常出现今天瓜2块钱一斤，明天就要5块钱一斤，所以精打细算的rab0t要合理的吃瓜，使得他花的钱尽可能少
现在假设他从第一天开始要连续N天都有瓜可以吃，第i天的瓜卖Pi元，能吃Di天，如果某天买了新的瓜就会把没吃完的都扔掉，毕竟rab0t喜欢新鲜的食物。
问你他最少要花多少钱？

DP+线段树,详细参考我前一遍文章

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<bitset>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 6e4+11;
const int MOD = 2520;
const double eps = 1e-10;
typedef long long ll;
const int oo = 0x3f3f3f3f;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll dp[maxn],a[maxn],b[maxn],n;
struct ST{
    ll mn[maxn<<2];
    #define lc o<<1
    #define rc o<<1|1
    void build(int o,int l,int r){
        mn[o]=oo;
        if(l==r)return;
        int m=l+r>>1;
        build(lc,l,m);
        build(rc,m+1,r);
    }
    void pu(int o){
        mn[o]=min(mn[lc],mn[rc]);
    }
    void update(int o,int l,int r,int k,ll v){
        if(l==r){
            mn[o]=min(v,mn[o]);
            return;
        }
        int m=l+r>>1;
        if(k<=m) update(lc,l,m,k,v);
        else update(rc,m+1,r,k,v);
        pu(o);
    }
    ll query(int o,int l,int r,int L,int R){
        if(L<=l&&r<=R) return mn[o];
        int m=l+r>>1;
        ll ans=oo;
        if(L<=m) ans=min(ans,query(lc,l,m,L,R));
        if(R>m) ans=min(ans,query(rc,m+1,r,L,R));
        return ans;
    }
}st;
int main(){
    int T=read();
    while(T--){
        n=read();
        rep(i,1,n) a[i]=read();
        rep(i,1,n) b[i]=min(read(),n);
        st.build(1,1,n);
        dp[0]=0;
        dp[1]=a[1];st.update(1,1,n,b[1],dp[1]);
         
        rep(i,2,n){
            dp[i]=dp[i-1]+a[i];
            st.update(1,1,n,min(i+b[i]-1,n),dp[i]);//mai gua
            ll t=st.query(1,1,n,i,n);//xu ming
            if(t<dp[i]) dp[i]=t;
        }
        println(dp[n]);
    }
    return 0;
}

Problem M 瓦西里的破车

瓦西里有一辆车，他要从家去邮局。
他家距邮局d公里。
瓦西里的车很差-它每行驶k公里就需要修理t秒后才能重新发动。
开车一公里汽车瓦西里需要花a秒，走一公里步行他需要花费b秒。(a<b)
你的任务是求瓦西里到达邮局的最短时间。
瓦西里可以在任何时候离开车开始步行。

写出函数,假设汽车走的历程为\(d_1\),那么\(f(d_1)=(a-b)*d_1+d*b+[(d_1-1)/k]*t\)
斜率不变那函数肯定单调

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 1e6+11;
const int oo = 0x3f3f3f3f;
const double eps = 1e-7;
typedef long long ll;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll k,a,b,t,d;
ll cal(ll d1){
    if(d1==0) return d*b;
    return (a-b)*d1+d*b+(d1-1)/k*t;
}
int main(){
    while(cin>>d){
        k=read();
        a=read();
        b=read();
        t=read();
        bool flag=0;
        ll delta1=-(cal(d)-cal(1));
        ll delta2=cal(k+1)-cal(k);
        if(delta1>=delta2) flag=1;
        if(flag) println(min(cal(d),cal(d-d%k)));//jiang
        else println(cal(min(k,d)));
    }
    return 0;
}

转载于:https://www.cnblogs.com/caturra/p/8620549.html

回复
分享到 :
0 人收藏
返回列表
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

3级会员
已经匿名di用户

积分:81
帖子:4969
精华:0
+ 关注 私信
期权论坛 期权论坛
期权网络科技版权所有
关于我们
联系我们
加入我们
反馈问题
免责声明
积分充值
统一社会信用代码
积分规则
网站地图
爱文库
下属网站
官方
新浪微博
微信公众号
◆
下载
表情包
App下载
期权论坛 期权论坛

QQ咨询|关于我们|Archiver|手机版|小黑屋|( 辽ICP备15012455号-4 ) Powered by 期权论坛 X3.2 © 2001-2016 期权工具网&期权论坛 Inc.

发布
内容

下载期权论坛手机APP