NOIP2011题解

程序员文章站 2022-05-21 23:31:01

...

NOIP2011题解

当然还是早就做完了啊，重新写一遍。

Day1

铺地毯 carpet

倒着检查最后被哪个覆盖了就好了。

#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 10100
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int a[MAX],b[MAX],g[MAX],k[MAX];
int n,x,y;
int main()
{
    n=read();
    for(int i=1;i<=n;++i)
        a[i]=read(),b[i]=read(),g[i]=read(),k[i]=read();
    x=read(),y=read();
    for(int i=n;i;--i)
        if(a[i]<=x&&a[i]+g[i]>x&&b[i]<=y&&b[i]+k[i]>y)
        {
            printf("%d\n",i);
            return 0;
        }
    puts("-1");
    return 0;
}

选择客栈 hotel

对于每种颜色维护一下前面有多少个可以和当前这个酒店配对，显然这个是单调递增的。每次找到一个合法的咖啡馆之后显然可以把前面一段连续区间加入贡献，直接开一个桶记录就好了。

#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
#define MAX 200200
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int n,k,p;ll ans;
int a[MAX],s[MAX],col[MAX];
int main()
{
    n=read();k=read();p=read();
    for(int i=1;i<=n;++i)a[i]=read(),s[i]=read();
    for(int i=1,lst=0;i<=n;++i)
    {
        if(s[i]<=p){for(int j=lst+1;j<=i;++j)col[a[j]]+=1;lst=i;}
        ans+=col[a[i]];if(s[i]<=p)ans-=1;
    }
    printf("%lld\n",ans);
    return 0;
}

玛雅游戏 mayan

看到数据范围就是爆搜。实现一个掉落函数以及一个消去函数就好了。细节上掉落函数很好实现。消去的话可以枚举一个消去中心，如果可以消去就打个标记，然后全部标记完再一起删就很好做了。记得如果消去了方块就要掉落一遍再消一次。最后是爆搜的时候的剪枝，有且仅有一个，就是当且仅当左边是空位置的时候才能左移，没有其他剪枝，网上的说同色方块不换的剪枝是假的。因为题目限定了步数而不是让你求出一个最优解，意味着可能存在让你做一些无用步数保证字典序最小。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int a[7][9];
int b[7],n;
bool book[7][9];
void Recalc(){for(int i=1;i<=5;++i){b[i]=0;while(a[i][b[i]+1])b[i]+=1;}}
void Fall()
{
    for(int i=1;i<=5;++i)
    {
        int t=0;
        for(int j=1;j<=7;++j)
            if(a[i][j])a[i][++t]=a[i][j];
        for(int j=t+1;j<=7;++j)a[i][j]=0;
        b[i]=t;
    }
}
void Delete()
{
    Recalc();memset(book,0,sizeof(book));bool fl=false;
    for(int i=2;i<=4;++i)
        for(int j=1;j<=b[i];++j)
            if(a[i][j]==a[i-1][j]&&a[i][j]==a[i+1][j])
                book[i][j]=book[i-1][j]=book[i+1][j]=true;
    for(int i=1;i<=5;++i)
        for(int j=2;j<b[i];++j)
            if(a[i][j]==a[i][j-1]&&a[i][j]==a[i][j+1])
                book[i][j]=book[i][j-1]=book[i][j+1]=true;
    for(int i=1;i<=5;++i)
        for(int j=1;j<=b[i];++j)
            if(book[i][j])a[i][j]=0,fl=true;
    Fall();if(fl)Delete();
}
bool Clear(){return !b[1]&&!b[2]&&!b[3]&&!b[4]&&!b[5];}
struct Opt{int x,y,d;}S[50];int top;
void Output(){for(int i=1;i<=n;++i)printf("%d %d %d\n",S[i].x-1,S[i].y-1,S[i].d);exit(0);}
void Draw()
{
    for(int i=1;i<=5;++i)
    {
        for(int j=1;j<=b[i];++j)printf("%d",a[i][j]);
        for(int j=b[i]+1;j<=7;++j)printf("0");
        puts("");
    }
    puts("");
}
void dfs(int x)
{
    if(x==n+1)
    {
        if(Clear())Output();
        return;
    }
    //Draw();
    if(Clear())return;
    int tmp[7][9];memcpy(tmp,a,sizeof(a));
    int bb[7];memcpy(bb,b,sizeof(b));
    for(int i=1;i<=5;++i)
        for(int j=1;j<=b[i];++j)
        {
            if(i!=5)//Right
            {
                swap(a[i][j],a[i+1][j]);
                Fall();Delete();S[++top]=(Opt){i,j,1};
                dfs(x+1);--top;
                memcpy(a,tmp,sizeof(a));
                memcpy(b,bb,sizeof(b));
            }
            if(i!=1&&!a[i-1][j])//Left
            {
                swap(a[i][j],a[i-1][j]);
                Fall();Delete();S[++top]=(Opt){i,j,-1};
                dfs(x+1);--top;
                memcpy(a,tmp,sizeof(a));
                memcpy(b,bb,sizeof(b));
            }
        }
}
int main()
{
    n=read();
    for(int i=1;i<=5;++i)while(a[i][++b[i]]=read());
    for(int i=1;i<=5;++i)b[i]-=1;
    dfs(1);puts("-1");
    return 0;
}

Day2

计算系数 factor

简单题，求一个组合数之后就做完了。

#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
#define MOD 10007
#define MAX 1020
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int C[MAX][MAX];
int ans;
int a,b,k,n,m;
int main()
{
    a=read()%MOD,b=read()%MOD,k=read(),n=read(),m=read();
    for(int i=0;i<=k;++i)C[i][0]=1;
    for(int i=1;i<=k;++i)
        for(int j=1;j<=i;++j)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
    ans=C[k][n];
    for(int i=1;i<=n;++i)ans=ans*a%MOD;
    for(int i=1;i<=m;++i)ans=ans*b%MOD;
    printf("%d\n",ans);
    return 0;
}

聪明的质检员 qc

不难，二分限制\(W\)，利用前缀和求出当前的\(Y\)，显然\(Y\)和\(W\)之间是一个单调的关系，直接\(check\)就好了。每次求完值之后取个\(min\)。或者你强制二分出\(Y\le S\)的最小的\(W\)。这样子直接算\(W,W+1,W-1\)的最小值就好了。

#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
#define MAX 200200
inline ll read()
{
    ll x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
ll ans=1e18,S;
int n,m;
int w[MAX],v[MAX],L[MAX],R[MAX];
int s[MAX];ll sv[MAX];
ll check(int W)
{
    for(int i=1;i<=n;++i)
        if(w[i]>=W)s[i]=1,sv[i]=v[i];
        else s[i]=sv[i]=0;
    for(int i=1;i<=n;++i)s[i]+=s[i-1];
    for(int i=1;i<=n;++i)sv[i]+=sv[i-1];
    ll Y=0;
    for(int i=1;i<=m;++i)Y+=(s[R[i]]-s[L[i]-1])*(sv[R[i]]-sv[L[i]-1]);
    return Y;
}
int main()
{
    n=read();m=read();S=read();
    for(int i=1;i<=n;++i)w[i]=read(),v[i]=read();
    for(int i=1;i<=m;++i)L[i]=read(),R[i]=read();
    int l=0,r=1e6;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        ll Y=check(mid);ans=min(ans,abs(S-Y));
        if(S==Y)break;
        if(S>Y)r=mid-1;
        else l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}

观光公交 bus

这一年最难的题目。很好的题目。

发现\(O(nk)\)的复杂度是可以接受的。那么我们每次就修改一个权值。不难求出每个站的出发时间和到站时间，求出来之后考虑减少每一条路的长度。显然减少一之后会影响一段区间的时间，使得出发时间全部减少了\(1\)。那么扫一遍求出对于每条路减少\(1\)之后对于答案的影响，贪心的减去最大的那个就好了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 100100
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int A[MAX],B[MAX],T[MAX];
int n,m,K,d[MAX],s[MAX],ss[MAX];
int a[MAX],b[MAX],t[MAX];
ll ans;
int lef[MAX],minus[MAX],eff[MAX];
int main()
{
    n=read();m=read();K=read();
    for(int i=1;i<n;++i)d[i]=read();
    for(int i=1;i<=m;++i)
    {
        t[i]=read(),a[i]=read(),b[i]=read();
        T[a[i]]=max(T[a[i]],t[i]);
        A[a[i]]+=1;B[b[i]]+=1;
    }
    for(int i=1;i<=n;++i)ss[i]=ss[i-1]+B[i];
    for(int i=1,t=0;i<=n;++i)lef[i]=t=max(t,T[i]),t+=d[i];
    for(int i=1;i<=m;++i)ans+=(lef[b[i]-1]+d[b[i]-1])-t[i];
    while(K--)
    {
        for(int i=1,t=0;i<=n;++i)lef[i]=t=max(t,T[i]),t+=d[i];
        eff[n]=eff[n-1]=n-1;
        for(int i=n-2;i;--i)
        {
            int arr=lef[i]+d[i];
            if(arr>T[i+1])eff[i]=eff[i+1];
            else eff[i]=i;
        }
        int mx=0,val=0;
        for(int i=1;i<n;++i)
            if(d[i]&&ss[eff[i]+1]-ss[i]>val)
                val=ss[eff[i]+1]-ss[i],mx=i;
        ans-=val;d[mx]-=1;
    }
    printf("%lld\n",ans);
    return 0;
}

上一篇： pku acm 2362 square 解题报告

下一篇：数据结构第二遍思维导图

NOIP2011题解

NOIP2011题解

Day1

铺地毯 carpet

选择客栈 hotel

玛雅游戏 mayan

Day2

计算系数 factor

聪明的质检员 qc

观光公交 bus

问题解决：多种方式完美解决pip命令下载第三方库的问题

ocp 1Z0-051 1-22题解析

【题解】【中国大学MOOC】（北京大学）人工智能与信息社会测验——3基于决策树和搜索的智能系统（下）

PHP 生成中文验证码乱码问题解决(1/2)

【题解】【中国大学MOOC】（北京大学）人工智能与信息社会测验——4基于仿生算法的智能系统

Python开发sprintf()和QString中文乱码问题解决

Mysql重置密码过程中遇到的问题解析

SQL SERVER应用问题解答13例（三）

apache虚拟主机配置问题解决方案_PHP教程

myeclipse连接mysql数据库错误问题解决（搞了好久才发现是这个问