鹏鹏的旧OI博客

高二及以前的哦,只剩文字了,图片、附件等都没了



YZOI20170607模拟

出租车费

出租车3公里起步价10元,超过3公里部分每公里2元,超过15公里部分每公里3元,若为夜间行车,起步价11元,超过3公里部分加收20%。输入行驶里程和时间,输出车费。
大模拟。


足球联赛

t个队伍比赛n局,赢的+3分,平局各+1分,输的不变。输入最后的各队得分,输出平局的个数。
显然因为有输赢的是共加3分,平局的是共加两分,所以3n-(所有队的得分都加起来),就是答案。


进制转换

给p,q,r,问等式p×q=r能否在2-16进制内某一进制下成立。
大模拟。


青蛙王子

题意就是龙珠的玩法。
用链表表示珠子串,模拟射入和消失就可以了。


数的拆分

把数n分成k个数的乘积,求这k个数的和最小值。
我能说我第一反应是基本不等式吗。。。罗小斌:数学思想很重要啊
于是就用基本不等式做了,结果某些数据的结果和答案相去甚远。。。
这里应该用动态规划。fn表示把n分成k部分的最小的和,但由于数据范围有点大,所以直接开数组会爆炸,这里应该用二维的map。转移方程很简单,fn=min{fi+n/i,fn/i+i}i是n的因数。


奶牛排队

给一个长度n的01串,每次操作可以将连续的k个01取反,要把串全部变0,问当操作次数最少的时候k最小是多少。
这真是一道神奇的题,看起来很高深,其实就是一个模拟题orz。
其实对于每一个操作区间,区间里的每个元素需要进行的操作次数是确定的,所以这些区间的操作顺序是随意的。所以说只要枚举k,在串里碰到1就把长度k的子串取反,到最后判断一下是不是全变0了就能判断当前k是否合法了。
大模拟。。。。。。。。。。


修建泳池

一个n行m列的01矩阵,找出最大的一个0组成的子矩阵。
类似的题貌似在codevs上做过,貌似是动态规划做的,但是忘记了(pia~打脸
先把矩阵转化一下,把(i,j)记为在j这列上,从上到下,到第i个位置的连续的0的个数。枚举每一行作为下边界,用数组l[i]和r[i]分别表示高度取到i时,最左的边界和最右的边界,维护一个栈来更新lr数组,最后再根据lr求出面积取最大值就好了。


出租车费代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    freopen("taxi.in","r",stdin);
    freopen("taxi.out","w",stdout);
    int n,t;cin>>n>>t;
    double a,b,c;
    if(t){a=11;b=2*1.2;c=2*1.7;}
    else{a=10;b=2;c=3;}
    if(n<=3)printf("%.1f",a);
    else if(n<=15)printf("%.1f",a+(n-3)*b);
    else printf("%.1f",a+12*b+(n-15)*c);
    return 0;
}

足球联赛代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    freopen("football.in","r",stdin);
    freopen("football.out","w",stdout);
    int t,n,s=0;
    cin>>t>>n;
    for(int i=1;i<=t;++i){int a;cin>>a;s+=a;}
    cout<<n*3-s;
    return 0;
}

进制转换代码

#include<bits/stdc++.h>
using namespace std;
int chg(int a,int w){
    int s=0;
    for(int i=0;a;++i){
        if(a%10>=w)return 0;
        s+=pow(w,i)*(a%10);
        a/=10;
    }
    return s;
}
int main(){
    freopen("base.in","r",stdin);
    freopen("base.out","w",stdout);
    int p,q,r;cin>>p>>q>>r;
    for(int i=2;i<=16;++i){
        int a=chg(p,i),b=chg(q,i),c=chg(r,i);
        if(a&&b&&c&&a*b==c){cout<<i;return 0;}
    }
    cout<<0;
    return 0;
}

青蛙王子代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct Node{int a;Node *pre,*nxt;};
Node *head;
void add(int a){
    Node *p=head;
    while(p->nxt)p=p->nxt;
    Node *k=new Node();
    p->nxt=k;
    k->pre=p;
    k->nxt=0;
    k->a=a;
}
void doit(Node *k){
    Node *l=k,*r=k;
    int ls=0,rs=0;
    while(l->pre!=head&&l->a==k->a)l=l->pre,ls++;
    while(r->nxt&&r->a==k->a)r=r->nxt,rs++;
    if(l->a==k->a)ls++;if(l!=r&&r->a==k->a)rs++;
    if(ls+rs>3){
        if(l->a==k->a&&r->a==k->a)head->nxt=0;
        else if(l->a==k->a)head->nxt=r,r->pre=head;
        else if(r->a==k->a)l->nxt=0;
        else{l->nxt=r;r->pre=l;}
    }
    else return;
    while(1){
        if(l==head||!r)return;
        if(l->pre==head||r->nxt==0)return;
        if(l->a!=r->a)return;
        int t=l->a;ls=rs=0;
        while(l->pre!=head&&l->a==t)l=l->pre,ls++;
        while(r->nxt&&r->a==t)r=r->nxt,rs++;
        if(l->a==t)ls++;if(r->a==t)rs++;
        if(ls+rs>2){
            if(l->a==t&&r->a==t)head->nxt=0;
            else if(l->a==t)head->nxt=r,r->pre=head;
            else if(r->a==t)l->nxt=0;
            else{l->nxt=r;r->pre=l;}
        }
        else return;
    }
}
int main(){
    freopen("zuma.in","r",stdin);
    freopen("zuma.out","w",stdout);
    head=new Node();
    head->pre=head->nxt=0;
    cin>>n>>m;
    for(int i=1;i<=n;++i){int a;cin>>a;add(a);}
    for(int i=1;i<=m;++i){
        int c,x;cin>>c>>x;
        Node *p=head;
        while(x--)p=p->nxt;
        Node *k=new Node();
        if(p->nxt)p->nxt->pre=k,k->nxt=p->nxt;
        else k->nxt=0;
        p->nxt=k;
        k->pre=p;
        k->a=c;
        doit(k);
    }
    int ans=0;
    while(head->nxt)head=head->nxt,ans++;
    cout<<ans;
    return 0;
}

数的拆分代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
map<int,map<int,int> >f;
int dfs(int n,int k){
    if(f[n][k])return f[n][k];
    if(k==1)return f[n][k]=n;
    f[n][k]=n+k-1;
    for(int i=2;i*i<=n;++i)
        if(n%i==0)f[n][k]=min(f[n][k],(dfs(i,k-1)+n/i,dfs(n/i,k-1)+i));
    return f[n][k];
}
int main(){
    freopen("divide.in","r",stdin);
    freopen("divide.out","w",stdout);
    cin>>n>>k;cout<<dfs(n,k);
    return 0;
}

奶牛排队代码

#include<bits/stdc++.h>
using namespace std;
int n,a[3010],b[3010],anss=1e8,ansi;
int getAns(int k){
    int s=0;
    for(int i=1;i<=n;++i)b[i]=a[i];
    for(int i=1;i<=n-k+1;++i)
        if(b[i]){s++;for(int j=i;j<=i+k-1;++j)b[j]=!b[j];}
    for(int i=n-k+1;i<=n;++i)if(b[i])return 1e8;
    return s;
}
int main(){
    freopen("cow.in","r",stdin);
    freopen("cow.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    for(int i=1;i<=n;++i){
        int tmp=getAns(i);
        if(tmp<anss){
            anss=tmp;
            ansi=i;
        }
    }
    cout<<ansi;
    return 0;
}

修建泳池代码

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int n,m,a[N][N],ans,l[N],r[N],sta[N],top;
#define For(i,n) for(int i=1;i<=n;++i)
void work(int i){
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
    a[i][0]=-1;
    For(j,m+1){
        while(top&&a[i][sta[top]]>a[i][j])
            r[sta[top--]]=j;
        l[j]=sta[top];
        sta[++top]=j;
    }
    while(top)r[sta[top--]]=m+1;
    For(j,m)ans=max(ans,a[i][j]*(r[j]-l[j]-1));
}
int getc(){
    char ch=getchar();
    while(ch!='0'&&ch!='1')ch=getchar();
    return ch-'0';
}
int main(){
    freopen("pool.in","r",stdin);
    freopen("pool.out","w",stdout);
    cin>>n>>m;
    For(i,n)For(j,m)a[i][j]=getc()?0:(i>1?a[i-1][j]:0)+1;
    for(int i=1;i<=n;++i)work(i);
    cout<<ans;
    return 0;
}

题目