进阶指南0x00例题&&习题

JJZN 0x00做了两个半周了,习题还没做,例题还有几个没做完.啊,我太摸啦!

例题:

poj1958:
递归枚举前从上到下数前i层先放到一边得到的答案里的最小值:
先把前i层放到一根柱子上,此时有四根柱子,所以相当于four[i],
再把剩下的柱子放到目标柱上,此时因为其中一个柱子被占了,所以相当于只有一根辅助柱,thr[i-j],
然后再把前i层柱子放到目标住,虽然目标柱有剩下i-j层,但是可以让前i层随便放上去,
所以相当于four[i],四根柱子的情况…

#include <iostream>
#include <algorithm>
using namespace std;
int thr[20],four[20];
int main()
{
    fill_n(four,20,0x3f3f3f3f);
    for(int i=1;i<=12;++i)
    {
        thr[i]=2*thr[i-1]+1;
    }
    four[1]=1;
    for(int i=2;i<=12;++i)
    {
        for(int j=1;j<i;++j)
        {
            four[i]=min(four[i],2*four[j]+thr[i-j]);
        }
    }
    for(int i=1;i<=12;++i)
    cout<<four[i]<<endl;
    return 0;
} 

poj3263:

前缀和/差分,太简单没的说.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int,int> > v;
int h[10010];
int main()
{
    int n,i,hh,r;
    scanf("%d%d%d%d",&n,&i,&hh,&r);
    while(r--)
    {
        int a,b;scanf("%d%d",&a,&b);
        if(a>b) swap(a,b);
        v.push_back(make_pair(a,b));
    }
    sort(v.begin(),v.end());
    vector<pair<int,int> >::iterator ne=unique(v.begin(),v.end());
    for(vector<pair<int,int> >::iterator i=v.begin();i!=ne;++i)
    {
        if((*i).second-(*i).first==1) continue;
        h[(*i).first+1]-=1;
        h[(*i).second]+=1;
    }
    for(int i=1;i<=n;++i)
    {
        h[i]+=h[i-1];
        printf("%d\n",h[i]+hh);
    }
    return 0;
}

poj3889:

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
pll calc(int n,ll num)
{
    if(n==0) return make_pair(1,1);
    ll step=1LL<<(2*n-2);
    ll line=1LL<<(n-1);
    pll tmp=calc(n-1,num%step);
    ll &x=tmp.first,&y=tmp.second;
    switch(num/step)
    {
        case 0:
        return make_pair(y,x); 
        case 1:
        return make_pair(x+line,y);
        case 3:
        return make_pair(line-y+1,2*line-x+1);
        default:
        return make_pair(x+line,y+line);
    }
}
double dist(pll a,pll b)
{
    return 10.0*sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n; ll s,d;scanf("%d%lld%lld",&n,&s,&d);
        pll a=calc(n,s-1),b=calc(n,d-1);
        printf("%.0f\n",dist(a,b));
    }
    return 0;
}
/*
很恶心一道题,难度在于坐标的变换:

四个角的情况都是以右下角为基准进行各种变换:

可以拿n=2的情况来看:

其实0的情况可以和2找规律看出来,比如至少找两个坐标,然后可以看出来xy是相反的;

1和2一样,3是0先向下(上)翻再向左(右)翻,可以举例子去看,翻转是因为每个起点的位置走的方向是不同的(废话)

翻=line-x(y)+1,比较好想;

然而现在是相对于每个格自己的坐标,所以还得加上各种line处理一下;
并不好想,没书自己早放弃了...

*/

poj2018:

#include <cstdio>
#include <algorithm>
using namespace std;
int n,f;
double list[100010];
#define a(j) (list[j]-(j)*mid)
int main()
{
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;++i)
    scanf("%lf",&list[i]),list[i]+=list[i-1];
    double eps=1e-6;
    double l=-1e6,r=1e6;
    while(l+eps<r)
    {
        double mid=(l+r)/2;
        double ans=-1e10,sum=1e10;
        for(int i=f;i<=n;++i)
        {
            sum=min(sum,a(i-f));
            ans=max(ans,a(i)-sum);
        }
        if(ans>=0)
        {
            l=mid;
        } else r=mid;
    }
    printf("%d",int(r*1000));
    return 0;
}
/*
很好的题.首先想到二分答案:然而直接去求平均数肯定是不单调的,所以应该把数列每个数都减去这个平均数(二分的数),

这样就得到了一个有正有负的数列.然后去做一遍最大子段和,如果存在和>=0的数列那么说明该数列平均值大于那个平均数;

然而数列长度必须>=L,就是要求一个>=L的最大子段和,所以先想一个朴素的:

ans=max(sum[i]-min(sum[j]){j:from 0 to i-L}){i from L to n}

然后发现min(sum[j])每次只增加一个答案,所以没必要每次都从0到i-L取一遍min,

所以单独提出来每次对新值取一遍min就行了;从中也可以看出为什么要求最大子段和:保证答案是最大的.

如果最大的<0,说明没有值符合要求了.反之也是这样.

从浮点数二分到特殊需求的最大子段和都是坑...

浮点数二分:保留x位小数,精度eps=1-e(x+3)
*/

bzoj3032:

最难想的一道题之一:首先,显然每行or每列的操作是相互独立的,所以分成两个问题单独处理.

然后,首先你要懂均分纸牌这道题并理解其思想,详情请看书.其中又是通过减掉平均数构成一个有正有负的序列,感觉这种思想很常见.然后你就会发现这就是一环形的均分纸牌,但是原题第一个与最后一个实际上是不会有任何直接的交换的(当然这是废话,因为第一个和最后一个直接交换实际上就相当于最后一个把刚才给前面的牌又要了回来)(可以把发牌抽象为在环中从k往前转一圈在回到k-1的一个操作).这可以看成把环剪开然后就转化为原题.但是从哪剪呢?很显然剪的点不同答案也不同(比如{3,0,0}(3)和{0,3,0}(2)就是不同的).然后要枚举断点?写出式子之后你就会发现可以用一个贪心:中位数当断点时是最优的.结束.(详细关于公式可以看书)

总之难点在于思维量大而且需要数学公式推导(需要有把公式写下来不断转化简化的能力啊…),好难!

#include <cstdio>
#include <algorithm>
typedef long long ll;
ll row[100010],col[100010];
using namespace std;
int main()
{
//    freopen("./tanabata/tanabata9.in","r",stdin);
    int n,m,t;
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=t;++i)
    {
        int x,y;scanf("%d%d",&x,&y);
        ++row[x],++col[y];
    }
    ll ave1=0,ave2=0;
    for(int i=1;i<=n;++i) ave1+=row[i];
    for(int i=1;i<=m;++i) ave2+=col[i];
    ll sum1=-1,sum2=-1;
    if(ave1%n==0)
    {
        ave1/=n;
        for(int i=1;i<=n;++i) row[i]+=row[i-1]-ave1;
        sort(row+1,row+1+n);
        ll k=row[n/2+1];
        sum1=0;
        for(int i=1;i<=n;++i) sum1+=abs(row[i]-k);
    }
    if(ave2%m==0)
    {
        ave2/=m;
        for(int i=1;i<=m;++i) col[i]+=col[i-1]-ave2;
        sort(col+1,col+1+m);
        int k=col[m/2+1];
        sum2=0;
        for(int i=1;i<=m;++i)
        sum2+=abs(col[i]-k);
    }
    if(sum1!=-1&&sum2!=-1)
    printf("both %lld",sum1+sum2);
    else if(sum1!=-1&&sum2==-1)
    printf("row %lld",sum1);
    else if(sum1==-1&&sum2!=-1)
    printf("column %lld",sum2);
    else printf("impossible");
    return 0;
}

poj3784:

动态维护中位数.思想是开一个大根堆存序列后半段,小根堆存前半段.当偶数时要维护一下(关键!),奇数时输出.之前一直wa,wa哭了.

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int main()
{
    int T;scanf("%d",&T);
    for(int i=1;i<=T;++i)
    {
        int cnt=0;
        priority_queue<int,vector<int>,greater<int> > q;
        priority_queue<int,vector<int>,less<int> > q2;
        int x,n;scanf("%d%d",&x,&n);
        printf("%d %d\n",x,((n%2==1)?(n/2+1):(n/2)));
        int t1,t2;scanf("%d",&t1);
        if(n==1) {printf("%d\n",t1);continue;}
        else {
            printf("%d",t1);++cnt;
            scanf("%d",&t2);
            if(t1>t2) swap(t1,t2);
            q2.push(t1);q.push(t2);
            if(n==2) printf("\n");else printf(" ");
        }
        for(int j=3;j<=n;++j)
        {
            int num;scanf("%d",&num);
            if(num<q.top()) 
            q2.push(num); 
            else q.push(num);
            if(j%2==0)
            {
                if(q2.size()>q.size()) {q.push(q2.top());q2.pop();}
                if(q.size()>q2.size()) {q2.push(q.top());q.pop();}
            }
            else{
                printf("%d",(q2.size()>q.size())?q2.top():q.top());++cnt;
                if(cnt==10||j+1>=n) printf("\n"),cnt=0;
                else printf(" ");
            }
        } 
    }
    return 0;
}

hc1384:

因为每次校验复杂度较大,所以可以用倍增替代二分,复杂度依然是神奇的logn.以及可以每次只排新增的数.目前依然在wa. 过了!!!开心!

说说自己怎么wa的把.一开始直接快排然后tle.然后写了归并一直wa.看了别人blog后发现还没判断对不对就不能先存到之前已排好的数据中,之后经过了无数次wa和re后过了.所以很显然当wa了之后首先要看自己的思路对不对,大部分wa是因为当自己思路升级的时候有很多细节(在思维上或代码上)却依然有之前错误的认知导致的.以及wa了一定要耐心才行.气定神闲…

#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long ll;
ll a[500010],d[500010],t=0;
int n;ll m,k;
using namespace std;
vector<ll> b,c,e;
bool check(int l,int r,int p)
{
    int len=r+p-l+1;
    ll ans=0;
    for(int i=1;i<=t;++i)
    b.push_back(d[i]);
    for(int i=r+1;i<=r+p;++i)
    c.push_back(a[i]);
    sort(c.begin(),c.end());
    int i=0,j=0;
    while(i<b.size()||j<c.size())
    {
        if(i>=b.size()) {while(j<c.size()) e.push_back(c[j++]);break;}
        if(j>=c.size()) {while(i<b.size()) e.push_back(b[i++]);break;}
        if(b[i]<c[j]) e.push_back(b[i++]);
        else e.push_back(c[j++]);
    }
//    sort(b+1,b+1+len);
    for(int i=1;i<=e.size()/2&&i<=m;++i)
    {
        ll tmp=(e[i-1]-e[e.size()-i]);tmp*=tmp;
        ans+=tmp;
        if(ans>k) return 0;
    }
    t=0;for(int i=0;i<e.size();++i) d[++t]=e[i];
    return 1;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int cnt=0;t=0;scanf("%d%lld%lld",&n,&m,&k);
        for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
        for(int l=1,r=1,p=1;r<=n;)
        {
            if(l==r) d[++t]=a[l];
            while(p)
            {
                if(r+p<=n&&check(l,r,p))
                {
                    r+=p;p*=2;
                } else p/=2;
                b.clear();c.clear();e.clear();
            }
            ++cnt;l=++r;p=1;t=0;b.clear();c.clear();e.clear();
        }
        printf("%d\n",cnt);
    }
    return 0;
}

贪心:全都没写: 还在wa

poj3614:

一个贪心的策略,感觉自己想不到.不过看了看书上之后感觉还是挺简单的…可以类比区间选择?…

以及我的方法和书上是相反的.虽然原理是一样的但是因为需要对second排序而pair默认是以first排的所以把first和second反着用了.之前没意识到这点然后疯狂wa…

#include <cstdio>
#include <set>
using namespace std;
typedef pair<int,int> pii;
multiset<pii> cover;
multiset<pii> qu;
int c,l;
typedef multiset<pii>::iterator st;
int main()
{
 //   freopen("data","r",stdin);
    int ans=0;
    pii t;
    scanf("%d%d",&c,&l);
    for(int i=1;i<=c;++i) scanf("%d%d",&t.second,&t.first),qu.insert(t);
    for(int i=1;i<=l;++i) scanf("%d%d",&t.first,&t.second),cover.insert(t);
    for(st i=qu.begin();i!=qu.end();++i)
    {
        st j;
        for(j=cover.begin();j!=cover.end()
        &&(j->first<i->second||j->second<=0)&&j->first<=i->first;++j);
        if(j==cover.end()) continue;
        if(j->first>i->first) continue;
        pii tmp=*j;cover.erase(j);
        ++ans;tmp.second-=1;cover.insert(tmp);
    }
    printf("%d",ans);
    return 0;
}

poj3190:

并不难,然而一直wa…

习题:

全都没写(您太摸了!)

2.poj2965:

就是枚举每行状态然后模拟.因为懒得写递归于是写了四个for然后调试火葬场:

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
int a[20][20], b[20][20];
typedef pair<int, int> pii;
vector<pii> v[5];
bool mode = 0;
void mk(int y, int x)
{
    for (int i = 1; i <= 4; ++i)
    {
        a[y][i] = !a[y][i];
        a[i][x] = !a[i][x];
    }
    a[y][x]=!a[y][x];
}
bool check()
{
    for (int i = 1; i <= 4; ++i)
    {
        for (int j = 1; j <= 4; ++j)
        {
            if (a[i][j])
                return 0;
        }
    }
    return 1;
}
int main()
{
    for (int i = 1; i <= 4; ++i)
    {
        for (int j = 1; j <= 4; ++j)
        {
            char ch = getchar();
            a[i][j] = (ch == '+') ? 1 : 0;
        }
        getchar();
    }
    for (int j = 0; j < 16; ++j)
    {
        int d = j;
        for (int k = 0; k < 4; ++k)
        {
            if ((d >> k) & 1)
            {
                mk(1, k + 1);
                v[1].push_back(pii(1, k + 1));
            }
        } //1
        for (int j = 0; j < 16; ++j)
        {
            int d = j;
            for (int k = 0; k < 4; ++k)
            {
                if ((d >> k) & 1)
                {
                    mk(2, k + 1);
                    v[2].push_back(pii(2, k + 1));
                } //2
            }
            for (int j = 0; j < 16; ++j)
            {
                int d = j;
                for (int k = 0; k < 4; ++k)
                {
                    if ((d >> k) & 1)
                    {
                        mk(3, k + 1);
                        v[3].push_back(pii(3, k + 1));
                    }
                } //3
                for (int j = 0; j < 16; ++j)
                {
                    int d = j;
                    for (int k = 0; k < 4; ++k)
                    {
                        if ((d >> k) & 1)
                        {
                            mk(4, k + 1);
                            v[4].push_back(pii(4, k + 1));
                        }
                    }
                    mode = 1;
                    if (check())
                    {
                        printf("%d\n", v[4].size()+v[3].size()+v[2].size()+v[1].size());
                        for (int x = 1; x <= 4; ++x)
                            for (int i = 0; i < v[x].size(); ++i)
                            {
                                printf("%d %d\n", v[x][i].first, v[x][i].second);
                            }
                        exit(0);
                    }
                    else
                    {
                        for (int i = 0; i < v[4].size(); ++i)
                        {
                            mk(v[4][i].first, v[4][i].second);
                        }
                    }
                    v[4].clear();
                }
                for (int i = 0; i < v[3].size(); ++i)
                {
                    mk(v[3][i].first, v[3][i].second);
                }
                v[3].clear();
            }
            for (int i = 0; i < v[2].size(); ++i)
            {
                mk(v[2][i].first, v[2][i].second);
            }
            v[2].clear();
        }
        for (int i = 0; i < v[1].size(); ++i)
        {
            mk(v[1][i].first, v[1][i].second);
        }
        v[1].clear();
    }
    return 0;
}

4.poj2083:

看见分形还以为又是例题那种毒瘤题,结果是水题,写了20mins左右.

#include <cstdio>
#include <cstring>
#include <algorithm>
int a[10]={0,1};
char b[3000][3000];
void sp_mk(int n,int y,int x)
{
    for(int i=0;i<a[n];++i)
    {
        for(int j=0;j<a[n];++j)
        {
            b[y+i][x+j]=' ';
        }
    }
}
void mk(int n,int y,int x)
{
    if(n==1) {b[y][x]='X';return;}
    mk(n-1,y,x);
    sp_mk(n-1,y,x+a[n-1]);
    mk(n-1,y,x+2*a[n-1]);
    sp_mk(n-1,y+a[n-1],x);
    mk(n-1,y+a[n-1],x+a[n-1]);
    sp_mk(n-1,y+a[n-1],x+2*a[n-1]);
    mk(n-1,y+2*a[n-1],x);
    sp_mk(n-1,y+2*a[n-1],x+a[n-1]);
    mk(n-1,y+2*a[n-1],x+2*a[n-1]);
}
int main()
{
    for(int i=2;i<=8;++i) a[i]=a[i-1]*3;
    while(1)
    {
        int i;scanf("%d",&i);
        if(i==-1) break;
        for(int i=0;i<3000;++i) for(int j=0;j<3000;++j) b[i][j]='\0';
        mk(i,0,0);
        for(int j=0;j<a[i];++j)
        {
            printf("%s\n",b[j]);
        }
        printf("-\n");
    }
    return 0;
}

5.poj3714:

这里要任意两个点的最短距离(平面最近点对),朴素n^2肯定不行,怎么办呢?分治+二分(或者这篇).

看完两篇文章之后,可能会对答案在中间的情况为什么只要看后面7个点有疑问.翻了算导中文版第三版ch33.4之后明白了.首先,那个最优答案a<δ.为什么δx2δ的区域里只有最多8个点?首先,左(右)边的δxδ正方形里最多有4个点,因为正方形中任意两点距离>=δ(否则最短的就会在一侧了);然后这四个点也只能是正方形的四个端点.为什么?假设随便取四个点两两相连,就构成了连了两条对角线的四边形对吧(因为画图不好请自行脑补),
显然两条对角线里至少有一条>外面四条边,所以外面四条边>=δ,对角线想象把正方形捏住两边拽瘦试试(强行证明)…然后矩形里就至少八个点了(当然有四个点是重合的).当然现实情况肯定是小于8个点的,所以从该点往上看就相当于从该点往上的δ*2δ矩阵里找,找7个点虽然有可能会超出矩阵,但尽量往大里去找.这也就是为啥也要对y排序.最后整体nlogn.因为不会(懒得)画图所以光看有点抽象所以一定要自己画画看.

然而一直wa,调了一天也不行…于是先放放鸽了.

6.ch0805:

一开始看到数据范围慌了,还想用数组存…后来发现前缀和有规律.因为只有一个奇数所以此项及之后的项前缀和肯定都是奇数,然后二分就行了.也不用真搞前缀和,把规则存下来check的时候算一下在范围里有几个点就行了.挺简单的水题,然而写了40mins左右,真是慢死了.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
struct p{ll s,e,d;};
vector<p> v;
ll ansp;
bool check(ll n)
{
    ll ans=0,ansk=0;
    for(vector<p>::size_type i=0;i<v.size();++i)
    {
        if(n<v[i].s) continue;
        ans+=((min(n,v[i].e)-v[i].s)/v[i].d+1);
        if((n-v[i].s)%v[i].d==0) ++ansk;
    }
    if(ans%2) {ansp=ansk;return 1;}
    return 0;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        ll r=0;
        int n;scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            ll s,e,d;scanf("%lld%lld%lld",&s,&e,&d);
            v.push_back((p){s,e,d});
            r=max(r,e);
        }
        int tmp=r;++r;ll l,mid;
        for(l=-1;l<r;)
        {
            mid=(l+r)>>1;
            if(check(mid))
            {
                r=mid;
            } else l=mid+1;
        }
        if(l==tmp+1) printf("There's no weakness.\n");
        else
        printf("%lld %lld\n",r,ansp);
        v.clear();
    }
    return 0;
}

tobecontinued…