鹏鹏的旧OI博客

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



NOIp2002解题报告

均分纸牌

给n个数字Ai,\( n | sum{A_{i}} \),令\( t = sum{A_{i}} / n \),每个数可以往左或往右匀一些过去,除了端点两个,问最少需要匀几次,可以让每个数都变成t。n<=100,Ai<=10000。
n如果比较小的话,当然是暴力大法吼啊,而且这是T1额,照例说应该都是些送分暴力水题,然而却不行。
然后想动态规划,用fiu=1..2表示区间匀好[i,j]后,在i(k==1)或者j(k==2)上还多出v可以匀出去,然后答案就是f11或者f12,但是2亿的数组是无论如何也开不下的,况且这个DP还是我瞎鸡巴意淫的,根本不知道怎么转移。。。
最后就想用贪心了。先把Ai都减去t,让Ai有正有负。从左往右依次累加Ai到变量s,中间过程中s势必会变号,即从负数变成正数,或反之。这样的意义何在?如果之前都是负数,现在变正数了,说明到这里为止,把当前这个数向左边匀去,最终能使左边的数都变成t,并且当前数还有剩余。当之前都是正数,现在变负数了,说明到这里为止,把前面的数向后匀到这里,可以将这区间的数都变成t,并且当前数还不到t。如果由负数或正数变成0,那么当前数是没有剩余或缺少,就是t。因为Ai的和肯定是整除n的,累加器s到最后一定是变为0。
于是100啦耶耶耶。


字串变换

给S和T两个字符串,几个变换规则Ai和Bi,规定字符串中的子串Ai能变换成Bi,问从S到T最少需要几步。
一开始就打了双向bfs,因为据说数据加强到20步以内了(然而实际上并没有加强,是10步以内)。字符串的查找替换使用的是string里的find和replace,根本不需要自己手写2333333。本来是个裸题,但由于本宝宝太傻,代码出现了很危险的BUG,双向BFS代码交上去以后不能AC,于是怀疑是双向广搜写错了,就打了单向光搜,结果错的点,错的答案一毛一样。WTF
好的,其实结果就是,在替换字符串的时候,我默认就只替换了一个,比如当数据出现S=“abaa”时,程序只会把第一个“a”替换掉,而T=“abac”是要把第三个“a”替换,于是就出现了明明有解,但是输出无解的尴尬情况。
改了一下,双向和单向光搜都能AC了,单向113ms,双向1ms,我只能说双向的效率666。


自由落体

<s>我想试试从教学中心顶楼开始做自由落体运动的快感</s>
n个小球,第i个小球放在(i-1,h)的位置上,一辆小车,宽l,高k,左端为(s1,0),向左做速度为v的匀速直线运动,小球同时以g=10做自由落体运动,当小球和小车的距离小于等于0.00001时,认为小车接住了小球,问小车一共能接住多少球。

这题简直就是物理题,可是我的物理比我的信息竞赛还差劲,怎么破,急在线等。
一开始,我就用最原始的方法,用循环逐一判断小球能否在小车到来之前落到小车的上方,并且能在小车开走之前落到小车上。由于物理渣,没能AC。
后来某hcn大神看了别人题解(额这是不是暴露了什么),说这可以看成小车不动的平抛运动。于是我就开始膜了起来。

每个小球的平抛轨迹都是一样的,只要算出哪个小球正好落上小车正前方,哪个小球正好与小车擦肩而去,就知道哪些小球是能被接住的了。用一堆物理公式可以意淫出来。但是公式什么的写对了,输出答案的时候没处理好。。。之后搞了一下就AC辣。
那个0.00001的精度,完全可以忽略的辣。


矩形覆盖

一个坐标系上n个点,有k个矩形可以用,问怎么放这k个矩形可以把所有点都覆盖,并且这k个矩形互不重叠且面积和最小。特殊地,覆盖一个点的矩形,或者是覆盖同一直线上的点的矩形,面积都是0。
一开始连暴力都不知道怎么打。
正确算法是暴力(蛤,其实DP更好
DP之前,先把点按y升序排,fi[k]表示数组序号i到j的点,用k个矩形覆盖所需要的最小面积,当成一个区间DP做就可以了。


均分纸牌代码

#include<bits/stdc++.h>
using namespace std;
int n,a[110],x;
int s,last,ans;
bool change(int x){
    s+=x;
    return s*(s-x)<=0;
}
int main(){
    freopen("noipg1.in","r",stdin);
    freopen("noipg1.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;++i){cin>>a[i];x+=a[i];}x/=n;
    for(int i=1;i<=n;++i)a[i]-=x;
    for(int i=1;i<=n;++i){
        if(a[i]==0)continue;
        if(change(a[i])){
            if(s!=a[i])ans+=i-last;
            last=i;
        }
    }
    cout<<ans;
    return 0;
}

字串变换代码

#include<bits/stdc++.h>
using namespace std;
string S,T,a[10],b[10],tmp,t;
int n=1,c,cc;
queue<string> q,qq;
map<string,int> m,mm;
size_t pos;
/*int n=1,c;
queue<string> q;
map<string,int> m;
size_t pos;*/
int main(){
    freopen("noipg2.in","r",stdin);
//    freopen("noipg2.out","w",stdout);
    cin>>S>>T;
    if(S==T){cout<<0;return 0;}
    while(cin>>a[n])cin>>b[n++];n--;
    /*m[S]=1;q.push(S);
    while(!q.empty()){
        t=tmp=q.front();q.pop();
        c=m[tmp];if(c==11){cout<<"NO ANSWER!";return 0;}
        for(int i=1;i<=n;++i){
            pos=t.find(a[i]);
            while(pos!=string::npos){
                t.replace(pos,a[i].size(),b[i]);
                if(t==T){cout<<c;return 0;}
                if(!m[t])m[t]=c+1,q.push(t);
                t=tmp;pos=t.find(a[i],pos+a[i].size());
            }
        }
    }*/
    m[S]=1;mm[T]=1;
    q.push(S);qq.push(T);
    while(!q.empty()||!qq.empty()){
        if(!q.empty()){
            t=tmp=q.front();q.pop();
            c=m[tmp];
            for(int i=1;i<=n;++i){
                pos=t.find(a[i]);
                while(pos!=string::npos){
                    t.replace(pos,a[i].size(),b[i]);
                    if(mm[t]){
                        if(c+mm[t]-1>10)cout<<"NO ANSWER!";
                        else cout<<c+mm[t]-1;
                        return 0;
                    }
                    if(!m[t])m[t]=c+1,q.push(t);
                    t=tmp;pos=t.find(a[i],pos+a[i].size());
                }
            }
        }
        if(!qq.empty()){
            t=tmp=qq.front();qq.pop();
            cc=mm[tmp];
            for(int i=1;i<=n;++i){
                pos=t.find(b[i]);
                while(pos!=string::npos){
                    t.replace(pos,b[i].size(),a[i]);
                    if(m[t]){
                        if(cc+m[t]-1>10)cout<<"NO ANSWER!";
                        else cout<<cc+m[t]-1;
                        return 0;
                    }
                    if(!mm[t])mm[t]=cc+1,qq.push(t);
                    t=tmp;pos=t.find(b[i],pos+b[i].size());
                }
            }
        }
        if(c+cc>12){cout<<"NO ANSWER!";return 0;}
    }
    cout<<"NO ANSWER!";
    return 0;
}

自由落体代码

#include<bits/stdc++.h>
using namespace std;
double h,s1,v,l,k;int n;
int main(){
//    freopen("noipg3.in","r",stdin);
//    freopen("noipg3.out","w",stdout);
    cin>>h>>s1>>v>>l>>k>>n;
    int x1=int(s1-sqrt(h/5.0)*v),x2=int(s1-sqrt((h-k)/5.0)*v+l);
    x1=max(x1,0);x2=min(x2,n);if(x1>x2)x1=x2;
    cout<<x2-x1;
    return 0;
}

矩形覆盖代码

#include<bits/stdc++.h>
using namespace std;
const int N=60;
int n,k,f[N][N][5];
struct node{
    int x,y;
    bool operator<(const node &b)const{if(y==b.y)return x<b.x;return y<b.y;}
}a[N];
int main(){
//    freopen("noipg4.in","r",stdin);
//    freopen("noipg4.out","w",stdout);
    memset(f,0x5f,sizeof(f));
    cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1);
    for(int i=1,l,r;i<=n;++i){
        l=r=a[i].x;
        for(int j=i;j<=n;++j){
            l=min(l,a[j].x);
            r=max(r,a[j].x);
            f[i][j][1]=(a[j].y-a[i].y)*(r-l);
        }
    }
    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j)
            for(int k=i;k<j;++k)
                f[i][j][2]=min(f[i][j][2],f[i][k][1]+f[k+1][j][1]);
    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j)
            for(int k=i;k<j;++k)
                f[i][j][3]=min(f[i][j][3],f[i][k][1]+f[k+1][j][2]);
    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j)
            for(int k=i;k<j;++k)
                f[i][j][4]=min(f[i][j][4],min(f[i][k][1]+f[k+1][j][3],f[i][k][2]+f[k+1][j][2]));
    cout<<f[1][n][k];
    return 0;
}