lg

lg

关注
发信
关注(28)粉丝(399)

【NOIP2011TG】solution

老师最近叫我把NOIPTG的题目给刷掉，于是就开始刷吧= =

链接：https://www.luogu.org/problem/lists?name=&orderitem=pid&tag=83%2C28

D1T1：carpet

题意简析：一个平面内有多个矩形按顺序覆盖平面，问覆盖后某个点属于哪个矩形。

解题思路：从n~1倒着check点有没有在矩形内即可，时间效率\( O(n) \)。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

#define For(i,a,b) for (int i=a; i<=b; i++)

#define Ford(i,a,b) for (int i=a; i>=b; i--)

#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);

#define mem(qaq,num) memset(qaq,num,sizeof(qaq));

#define ll long long

#define mod 1000000007

#define INF 2000000000

using namespace std;

struct zxy{

    int a,b,x,y;

}rect[];

int n,x,y;

inline int in(){

    int x=,f=;

    char ch=getchar();

    while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x*f;

}

int main(){

    n=in();

    For(i,,n)

        rect[i].a=in(),rect[i].b=in(),rect,rect[i].x=in()+rect[i].a,rect[i].y=in()+rect[i].b;

    x=in(),y=in();

    Ford(i,n,){

        if (x>=rect[i].a&&x<=rect[i].x&&y>=rect[i].b&&y<=rect[i].y){

            printf("%d",i);

            return ;

        }

    }

    printf("-1");

}

D1T2:hotel

题意简析：给你n个客栈，叫你选取任意2个色调相同的不同客栈，且它们之间（包括本身）所有的客栈内存在最低消费不超过p的咖啡店，问你有多少种方案。

解题思路：这题貌似有\( O(n) \)的算法，但是我只想到\( O(n^2) \)的贪心，然后用线段树存区间最小值优化一个log，然后存下不同色调的客栈数，顺推一下就行了。时间效率\( O(n \lg n) \).

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

#define For(i,a,b) for (int i=a; i<=b; i++)

#define Ford(i,a,b) for (int i=a; i>=b; i--)

#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);

#define mem(qaq,num) memset(qaq,num,sizeof(qaq));

#define ll long long

#define mod 1000000007

#define INF 2000000000

#define mid ((l+r)>>1)

using namespace std;

int mi[],color[][],cnt[],lst[],n,k,p;

inline int in(){

    int x=,f=;

    char ch=getchar();

    while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x*f;

}

inline void update(int x,int k,int l,int r,int add){

    if (l==r) {

        mi[k]=add;

        return;

    }

    if (x<=mid) update(x,k<<,l,mid,add);

    else update(x,k<<|,mid+,r,add);

    mi[k]=min(mi[k<<],mi[k<<|]);

}

inline int query(int l,int r,int k,int a,int b){

    if (!(l^a||r^b)) return mi[k];

    if (b<=mid) return query(l,mid,k<<,a,b);

    if (a>mid) return query(mid+,r,k<<|,a,b);

    return min(query(l,mid,k<<,a,mid),query(mid+,r,k<<|,mid+,b));

}

int main(){

    mem(mi,/);

    n=in(),k=in(),p=in();

    For(i,,n){

        int cl=in(),x=in();

        color[cl][++cnt[cl]]=i;

        update(i,,,n,x);

    }

    ll ans=;

    For(i,,k-)

        For(j,,cnt[i]){

            if (query(,n,,color[i][j-],color[i][j])<=p) ans+=j-,lst[i]=j-;

            else ans+=lst[i];

        }

    printf("%lld",ans);

}

D1T3:mayan

题意简析：看题目：)

解题思路：这种数据范围，就是爆搜啊= =，暴力枚举每次交换的点，然后按题意模拟一下，就行了。小剪枝：当任意一种颜色不足3个时就return。时间效率O(能过)。

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define For(i,a,b) for (int i=a; i<=b; i++)

#define Ford(i,a,b) for (int i=a; i>=b; i--)

#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);

#define ll long long

#define mod 1000000007

#define INF 2000000000

#define mem(qaq,num) memset(qaq,num,sizeof(qaq));

struct zxy{

    short x,y,op;

}ans[];

short pq[][],n;

inline short in(){

    short x=,f=;

    char ch=getchar();

    while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x*f;

}

inline void swap(short &a,short &b){

    short t=a;a=b,b=t;

}

inline void print(int x,char ch){

    if (!x){

       putchar('');

       putchar(ch);

       return;

    }

    if (x<){

       putchar('-');

       x*=-;

    }

    char num[];

    short cnt=;

    while(x) num[++cnt]=x%+'',x/=;

    while(cnt) putchar(num[cnt--]);

    putchar(ch);

}

void output(){

    For(i,,n) print(ans[i].x,' '),print(ans[i].y,' '),print(ans[i].op,'\n');

    exit();

}

inline void down(){

    For(i,,){

        short pos=;

        For(j,,)

            if (pq[i][j]) pq[i][pos++]=pq[i][j];

        For(j,pos,) pq[i][j]=;

    }

}

inline bool check(){

    For(i,,) For(j,,) if (pq[i][j]) return ;

    return ;

}

inline bool move(){

    bool flag=,used[][]={};

    For(i,,)

        For(j,,){

            if (i<&&pq[i][j]==pq[i+][j]&&pq[i][j]==pq[i+][j]&&pq[i][j]){

                used[i][j]=used[i+][j]=used[i+][j]=;

                flag=;

            }

            if (j<&&pq[i][j]==pq[i][j+]&&pq[i][j]==pq[i][j+]&&pq[i][j]){

                used[i][j]=used[i][j+]=used[i][j+]=;

                flag=;

            }

        }

    For(i,,)

        For(j,,)

            if (used[i][j]) pq[i][j]=;

    return flag;

}

inline void dfs(int k){

    if (k>n) if (check()) output(); else return;

    int memory[][],cnt[]={};

    For(i,,) For(j,,) ++cnt[pq[i][j]];

    For(i,,) if (cnt[i]<&&cnt[i]) return;

    memcpy(memory,pq,sizeof(pq));

    For(x,,)

        For(y,,)

            if(pq[x][y]!=pq[x+][y]){

                if (pq[x][y]) ans[k].x=x,ans[k].y=y,ans[k].op=;

                else ans[k].x=x+,ans[k].y=y,ans[k].op=-;

                swap(pq[x][y],pq[x+][y]);

                down();while(move()) down();

                dfs(k+);

                memcpy(pq,memory,sizeof(pq));

            }

}

int main(){

    n=in();

    For(i,,){

        short pos=,x=in();

        while(x) pq[i][pos++]=x,x=in();

    }

    dfs();

    printf("-1\n");

}

D2T1:factor

题意简析：就是题目要求的啊。

解题思路：把ax和by看成整体，杨辉三角形求完全k次方式的各项系数，然后再用ax和by代进去就行了。时间效率\( O(k^2) \)。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

#define For(i,a,b) for (int i=a; i<=b; i++)

#define Ford(i,a,b) for (int i=a; i>=b; i--)

#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);

#define mem(qaq,num) memset(qaq,num,sizeof(qaq));

#define ll long long

#define mod 10007

#define INF 2000000000

using namespace std;

int tri[][],n,m,k,a,b;

inline int in(){

    int x=,f=;

    char ch=getchar();

    while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x*f;

}

inline int ksm(int a,int k){

    if (!k) return ;

    if (!(k^)) return a%mod;

    int ans=ksm(a,k/)%mod;

    if (k&) return ans*ans%mod*a%mod;

    return ans*ans%mod;

}

int main(){

    a=in()%mod,b=in()%mod,k=in(),n=in(),m=in();

    tri[][]=;

    For(i,,k+)

        For(j,,i)

            tri[i][j]=(tri[i-][j-]+tri[i-][j])%mod;

    printf("%d",ksm(a,n)*ksm(b,m)%mod*tri[k+][k-n+]%mod);

}

D2T2:qc

题意简析：叫你确定一个参数W按照公式计算后使得|S-∑y[i]|最小。

解题思路：显然对于W的递增，有∑y[i]单调递减，我们考虑二分W，然后进行check。这样的效率是\( O（nm \lg S）\)的，我们可以发现我们可以通过每次2分后进行一个O(n)的预处理，计算≥W的个数与总和前缀，这样就可以优化效率。时间效率\( O((n+m) \lg max{W[i]}) \)

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

#define For(i,a,b) for (int i=a; i<=b; i++)

#define Ford(i,a,b) for (int i=a; i>=b; i--)

#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);

#define mem(qaq,num) memset(qaq,num,sizeof(qaq));

#define mod 1000000007

#define INF 1e18

#define mid (l+r>>1)

using namespace std;

int cnt[],sum[],w[],n,m,ll[],rr[],maw,miw=0x7fffffff,v[];

long long s,ans=1e18;

template <class T>

inline void in(T &x){

    x=;

    short f=;

    char ch=getchar();

    while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    x*=f;

}

void init(int k){

    cnt[]=sum[]=;

    For(i,,n)

        if (w[i]>=k){

            cnt[i]=cnt[i-]+;

            sum[i]=sum[i-]+v[i];

        }

        else cnt[i]=cnt[i-],sum[i]=sum[i-];

    return;

}

inline void BS(int l,int r){

    if (l>r) return;

    init(mid);

    long long tmp=;

    For(i,,m){

        tmp+=abs((long long)((cnt[rr[i]]-cnt[ll[i]-])*(sum[rr[i]]-sum[ll[i]-])));

        if (tmp>INF) break;

    }

    if (tmp==s){

        ans=;

        return;

    }

    if (tmp<s){

        if (s-tmp<ans){

            ans=s-tmp;

        }

        BS(l,mid-);

        return;

    }

    if (tmp-s<ans){

        ans=tmp-s;

    }

    BS(mid+,r);

}

int main(){

    in(n); in(m); in(s);

    For(i,,n)

        in(w[i]),in(v[i]),miw=miw>w[i]?w[i]:miw,maw=maw<w[i]?w[i]:maw;

    For(i,,m)

        in(ll[i]),in(rr[i]);

    BS(miw,maw);

    printf("%lld",ans);

}

D2T3:bus

题意：就是一条链，每个点之间有限定条件，叫你求权值最小是多少。

解题思路：枚举每个加速器放在哪里，用前缀和优化找出对于可能的加速可以减少多少等待时间即可。时间效率\( O(kn) \)。（貌似有\( O(n) \)的算法）

#include<stdio.h>

#define For(i,a,b) for (int i=a; i<=b; i++)

#define Ford(i,a,b) for (int i=a; i>=b; i--)

#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);

#define ll long long

#define mod 1000000007

#define INF 2000000000

int n,m,k,num[],st[],tim[],dis[],ans,use[];

struct zxy{

    int a,b,t;

}tou[];

template <class T>

inline void in(T &x){

    x=;

    short f=;

    char ch=getchar();

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    x*=f;

}

template <class T>

inline void print(T x,char ch){

    if (!x){

       putchar('');

       putchar(ch);

       return;

    }

    if (x<){

       putchar('-');

       x*=-;

    }

    char num[];

    short cnt=;

    while(x) num[++cnt]=x%+'',x/=;

    while(cnt) putchar(num[cnt--]);

    putchar(ch);

}//for integer only

template <class T>

inline T max(T a,T b){

    return a>b?a:b;

}

template <class T>

inline T min(T a,T b){

    return a<b?a:b;

}

template <class T>

inline void abs(T &x){

    x=x<?-x:x;

}

void init(){

    in(n),in(m),in(k);

    For(i,,n-) in(dis[i]);

    For(i,,m)

        in(tou[i].t),in(tou[i].a),in(tou[i].b),num[tou[i].b]++,st[tou[i].a]=max(tou[i].t,st[tou[i].a]);

    For(i,,n) num[i]+=num[i-];

    tim[]=;

    For(i,,n)

        tim[i]=max(tim[i-],st[i-])+dis[i-];

    For(i,,m)

        ans+=tim[tou[i].b]-tou[i].t;

}

void solve(){

    while(k){

        use[n]=use[n-]=n;

        Ford(i,n-,)

            use[i]=tim[i+]<=st[i+]?i+:use[i+];

        int np=,p;

        For(i,,n)

            if (num[use[i]]-num[i]>np&&dis[i])

                np=num[use[i]]-num[i],p=i;

        if (!np) break;

        ans-=np;

        dis[p]--;

        k--;

        tim[]=;

        For(i,,n)

            tim[i]=max(tim[i-],st[i-])+dis[i-];

    }

    print(ans,'\n');

}

int main(){

    init();

    solve();

    return ;

}

本文由Melacau编写，Melacau代表M星向您问好，如果您不是在我的博客http://www.cnblogs.com/Melacau上看到本文，请您向我联系，email:[email protected].

05-11 17:12
Powered by LMLPHP ©2024 lg 0.065469