2019 CSP-J 题解

前言

咕咕咕了好久,终于今天把 T3 的坑给补回来了,于是打算写一波题解。

勿吐槽码风,丑是必然的,毕竟好久前写的代码了。

T1 数字游戏

P5660 数字游戏

大意:给定长度为 8 的 01 串,求 1 的个数

sb 题,考察字符串基本使用,当时好像 2:30 还没到就已经切完了

考场代码:

#include <iostream>
#include <cstdio>
#include <string>
//#define LOCAL

using namespace std;

int main()
{
#ifndef LOCAL
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
#endif
    string s;
    cin>>s;
    int ans=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='1') ans++;
    }
    printf("%d\n",ans);
    return 0;
}

T2 公交换乘

P5661 公交换乘

大意:坐一次地铁可以获取一张有效期 45 分钟的优惠券,可以凭券免费坐票价不超过地铁票价的公交车,优惠票可累积,使用时优先使用最先获得的

模拟即可,这里使用 vector 模拟优惠票的队列,代码并不优美但是能过。

坑点就在于

  • 使用票要使用最先获得的
  • 优惠票用过要删掉

记得当时在考场上发现队列不能用之后还自己研究 vector::erase 的用法

#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
//#define LOCAL
struct ticket{
    int price;
    ll time;
};
vector<ticket> q;

int main()
{
#ifndef LOCAL
    freopen("transfer.in","r",stdin);
    freopen("transfer.out","w",stdout);
#endif
    int n;
    scanf("%d",&n);
    ll ans=0;
    while(n--)
    {
        int type,price;
        ll t;
        scanf("%d %d %lld",&type,&price,&t);
        if(type==0)//如果坐地铁
        {
            ans+=price;//更新答案
            ticket tt={price,t};
            q.push_back(tt);//插入候选队
        }
        else if(type==1)//如果是公交
        {
            while(!(q.empty())&&t-q.front().time>45) q.erase(q.begin());//先删掉超时的优惠票
            bool flag=0;
            for(int i=0;i<q.size();i++)//查询符合标准的第一张优惠票
            {

                if(q[i].price>=price)
                {
                    q.erase(q.begin()+i);//直接删掉
                    flag=1;
                    break;
                }
            }
            if(!flag) ans+=price;//如果不存在就需要付原价
        }
    }
    printf("%lld\n",ans);
    return 0;
}

T3 纪念品

P5662 纪念品

谁叫我太菜,当时考场上骗了 10 分走人,现在看题解才写出正解。

大意:T 天,N 种纪念品,每天不同的纪念品都有不同的价格,小伟一开始有 M 金币,每天可以卖掉手中的纪念品换取金币,买进纪念品花费金币或者什么都不做。在第 T 天一定会卖出手中所有纪念品,求最高收益

分析题意,可以发现需要使用 dp,发现状态貌似很复杂,又可以买进又可以卖出,然而,注意到买进和卖出都可以进行无数次,因此我们可以把所谓一直持有的纪念品看成先将其卖出,又将其买进,效果是一样的,实质上就是每一天都做一次完全背包。

f_{i,j,k} 表示第 i 天,考虑前 j 种物品,手里有 k 金币时,在下一天全部卖出能达到的最大收益,则有方程

f_{i,j,k}=\max(f_{i,j,k},f_{i,j-1,k+p_i,j}+p_{i,j}-p_{i+1,j})

表示如果要了第 j 个物品,那么净收益即为 p_{i,j}-p_{i+1,j},从 f_{i,j-1,k+p_i,j} 转移而来,利用完全背包思想压一下维度然后改循环顺序即可以达到正确结果。

(第一维的天数是可以不要的,第二维的物品也是可以用滚动数组优化掉的,保留第三维即可)

#include <cstdio>
#include <cctype>
#include <cstring>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

int n,t,p[105][105],f[10005];

int main()
{
    t=read(),n=read();
    int m=read();
    for(int i=1;i<=t;i++)
        for(int j=1;j<=n;j++)
            p[i][j]=read();
    int ans=m;
    for(int i=1;i<t;i++)
    {
        memset(f,~0x3f,sizeof(f));//先赋负无穷
        f[ans]=ans;//初始值,什么都不干的情况
        for(int j=1;j<=n;j++)//枚举物品,从小到大即为完全背包
            for(int k=ans;k>=p[i][j];k--)//枚举金钱
                f[k-p[i][j]]=max(f[k-p[i][j]],f[k]+p[i+1][j]-p[i][j]);
        int maxn=0;//统计最优答案用
        for(int j=0;j<=ans;j++)
            maxn=max(maxn,f[j]);
        ans=maxn;
    }
    printf("%d\n",ans);
    return 0;
}

T4 加工零件

P5663 加工零件

大意:一个工厂正在生产零件,工人从 1 到 n 标号,某些工人之间有双向传送带。

如果 x 号工人想生产一个被加工到第 L (L \gt 1) 阶段的零件,则所有与 x 号工人有传送带直接相连的工人,都需要生产一个被加工到第 L – 1 阶段的零件(但 x 号工人自己无需生产第 L – 1 阶段的零件)。

如果 x 号工人想生产一个被加工到第 1 阶段的零件,则所有与 x 号工人有传送带直接相连的工人,都需要为 x 号工人提供一个原材料。

给定一些工单,即需要某工人生产某阶段的零件,求 1 号是否需要提供原材料。


先将其抽象成图论问题,以工人为节点,传送带为边来建图。

考虑暴力,虽然一定超时,但还是能给我们一些启示,不难发现暴力就是在看 a 与 1 之间是否存在长度为 L 的路径,同时我们又注意到:如果 L 为奇数,且从 1 到 a 存在一条奇数路径,且最小奇数路径长小于等于 L,那么 1 就必须提供原材料(为什么可以:你可以两个传送带之间来回跳,比如 1->2->1->2->1…,但如果最小的奇数路径大于 L,说明从 aL 个阶段也轮不到 1,就不行)同样的,如果 L 为偶数,且从 1 到 a 存在一条偶数路径,且最小偶数路径长小于等于 L,那么 1 就必须提供原材料。

这就给我们了正解的方法:找到每个点距离 1 点的最小奇数路径与偶数路径即可,这一过程实现可以使用 bfs(因为我当时还没学过最短路),然后判定每一个工单的时候按照奇偶数去找最短奇偶路径是否小于等于工单给定阶段就可以判定 YesNo

当然,我写的考场代码有一个小 bug,就是没有判断 1 点不连通的情况,然而 ccf 的数据没有这种特殊情况,所以也就 A 了这道题

考场代码:

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
//#define LOCAL
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
vector<int> g[100020];//存图
bool vis0[100020],vis1[100020];//bfs用
int minans0[100020],minans1[100020];//存储奇偶最短路
struct node{
    int n,time;
};
queue<node> q;
void bfs()
{
    memset(minans0,inf,sizeof(minans0));
    memset(minans1,inf,sizeof(minans1));
    q.push((node){1,0});
    while(!q.empty())
    {
        int curn=q.front().n;//当前的点
        int nxtc=q.front().time+1;//下一个点会经过的路径长
        q.pop();
        for(int i=0;i<g[curn].size();i++)
        {
            int nxt=g[curn][i];
            if(nxtc%2==0)//如果下一个点是偶数到达
            {
                if(vis0[nxt]==0)//如果未访问
                {
                    vis0[nxt]=1;
                    q.push((node){nxt,nxtc});
                    minans0[nxt]=min(nxtc,minans0[nxt]);//就更新这里的结果
                    //cout<<"no."<<nxt<<" "<<nxtc<<endl;
                }
            }
            if(nxtc%2==1)//反之如果是奇数,也一样
            {
                if(vis1[nxt]==0)
                {
                    vis1[nxt]=1;
                    q.push((node){nxt,nxtc});
                    minans1[nxt]=min(nxtc,minans1[nxt]);
                    //cout<<"no."<<nxt<<" "<<nxtc<<endl;
                }
            }
        }
    }
    return;
}

void add_edge(int u,int v)
{
    g[u].push_back(v);//注意是无向图
    g[v].push_back(u);
    return;
}


int main()
{
#ifndef LOCAL
    freopen("work.in","r",stdin);
    freopen("work.out","w",stdout);
#endif
    int n,m,q;
    scanf("%d %d %d",&n,&m,&q);
    while(m--)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        add_edge(u,v);
    }
    bfs();//预处理
    while(q--)
    {
        int a,l;
        scanf("%d %d",&a,&l);
        bool flag=0;
        if(l%2==0&&vis0[a]==1&&minans0[a]<=l) flag=1;//如果是偶数阶段并且能到达
        if(l%2==1&&vis1[a]==1&&minans1[a]<=l) flag=1;
        if(flag) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

解题报告 P2831 愤怒的小鸟

题目内容

P2831

大意:(0,0) 处有一弹弓,有 n 只猪猪,弹弓发出的炮弹路径为 y=ax^2+bx,其中 a > 0,求最少的抛物线数量打掉所有猪猪。

解题思路

一开始的暴搜调了我很久,但是最后都只有 60 分,具体的思路就是两只两只的枚举猪猪,如果发现两只可以构成合法抛物线,那么就清算抛物线上的其他猪猪然后继续暴搜,但是复杂度比较高。状态的存储使用状压。

#include <cstdio>
#include <cmath>
#include <bitset>
#include <cstring>
#include <iostream>
#define EPS 1e-6
using namespace std;

class P2831
{
private:

    struct point
    {
        double x,y;
    };

    int ans;
    int n,m;
    point pig[19];
    int vis[1<<18];


    inline bool ison(point p,double a,double b)//判断点在不在抛物线上
    {
        return fabs(a*p.x*p.x+b*p.x-p.y)<=EPS;
    }

    inline bool calc(point d1,point d2,double &a,double &b)//计算过(x1,y1)和(x2,y2)的抛物线表达式
    {
        if(fabs(d1.x-d2.x)<EPS)
        {
            //cout<<"debug1"<<endl;
            return false;
        }
        if(fabs(d2.y/d2.x-d1.y/d1.x)<EPS)
        {
            //cout<<"debug2"<<endl;
            return false;
        }
        b=(d1.y*d2.x*d2.x/d1.x/d1.x-d2.y)/((d2.x*d2.x/d1.x)-d2.x);
        a=(d1.y-b*d1.x)/d1.x/d1.x;
        //cout<<"a:"<<a<<" b:"<<b<<endl;
        if(a>0)
            return false;
        return true;
    }

    void dfs(int cur,int opt,int step)
    {
        vis[cur]=min(vis[cur],step);
        //cout<<"step:"<<step<<' '<<cur<<endl;
        if(cur==(1<<n)-1)
        {
            ans=min(ans,step);
            return;
        }
        if(opt==1 && step>n/3.0+1)
            return;
        if(step>=ans || step>vis[cur])
            return;
        for(int i=0;i<n;i++)
        {
            bool flag=0;
            int now=cur;
            if(now&(1<<i))
                continue;
            now|=(1<<i);
            for(int j=0;j<n;j++)
            {
                int now2=now;
                if(now2&(1<<j))
                    continue;
                double a,b;
                if(!calc(pig[i],pig[j],a,b))
                    continue;
                flag=1;
                now2|=(1<<j);
                for(int k=0;k<n;k++)
                    if((!now2&(1<<k)) && ison(pig[k],a,b))
                        now2|=(1<<k);
                dfs(now2,opt,step+1);
            }
            if(!flag)
                dfs(now,opt,step+1);
        }
    }

public:

    int solve()
    {
        ans=0x3f3f3f3f;
        memset(vis,0x3f,sizeof(vis));
        scanf("%d %d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%lf %lf",&pig[i].x,&pig[i].y);
        dfs(0,m,0);
        return ans;
    }
};

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        P2831 a;
        printf("%d\n",a.solve());
    }
    return 0;
}

于是我放弃了调暴搜,在题解区发现了一种神奇的东西叫状压 dp,用 f_i 表示状态 i 需要的最少抛物线条数。同时抛物线预处理成能通过的点的集合,记作 para_j,转移方程如下:

f_{i|para_j}=\min(f_{i|para_j},f_i+1)

预处理抛物线的时候首先枚举单个的猪猪,因为每只猪猪必过一个抛物线,然后再枚举第二个猪猪,如果能构成的抛物线合法的话再将其他在抛物线上的点加入即可。

关于数学:要求过 (x_1,y_1)(x_2,y_2) 的抛物线 y=ax^2+bxab 的值,列出来式子然后消元即可。

b=\frac{\frac{y_1x^2_2}{x_1^2}-y_2}{\frac{x_2^2}{x_1}-x_2}\
a=\frac{y_1-bx_1}{x_1^2}

代码如下:

#include <cstdio>
#include <cmath>
#include <cstring>
#define EPS 1e-6
using namespace std;

struct point
{
    double x,y;
};

int n,m,para[200],f[1<<18],cnt;

inline bool ison(point p,double a,double b)//判断点在不在抛物线上
{
    return fabs(a*p.x*p.x+b*p.x-p.y)<=EPS;
}

inline bool calc(point d1,point d2,double &a,double &b)//计算过(x1,y1)和(x2,y2)的抛物线表达式
{
    if(fabs(d1.x-d2.x)<EPS)//判断横坐标相等的情况
        return false;
    if(fabs(d2.y/d2.x-d1.y/d1.x)<EPS)//判断构不成抛物线的情况
        return false;
    b=(d1.y*d2.x*d2.x/d1.x/d1.x-d2.y)/((d2.x*d2.x/d1.x)-d2.x);
    a=(d1.y-b*d1.x)/d1.x/d1.x;
    if(a>0)
        return false;
    return true;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

void pre()//预处理
{
    scanf("%d %d",&n,&m);
    memset(f,0x3f,sizeof(f));//先赋极大值
    cnt=0;//cnt为抛物线的数量
    point pig[18];
    for(int i=0;i<n;i++)
        scanf("%lf %lf",&pig[i].x,&pig[i].y);
    for(int i=0;i<n;i++)
    {
        para[cnt++]=1<<i;//先加入一个新抛物线
        for(int j=i+1,vis=0;j<n;j++)//定义的vis是枚举过的小猪,避免重复
        {
            if((1<<j)&vis)//判重
                continue;
            double a,b;
            if(!calc(pig[i],pig[j],a,b))//如果不合法
                continue;
            para[cnt]=1<<i;//先暂时加进去只有第一只猪猪的抛物线
            for(int k=j;k<n;k++)//然后枚举加新点进去
            {
                if(ison(pig[k],a,b))//如果第k只猪猪在上面
                {
                    vis|=(1<<k);//更新vis数组
                    para[cnt]|=(1<<k);//更新抛物线
                }
            }
            cnt++;//然后抛物线的条数要加一
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        pre();
        f[0]=0;
        for(int i=0;i<(1<<n);i++)//枚举每个状态
            for(int j=0;j<cnt;j++)//枚举每一条抛物线
                f[i|para[j]]=min(f[i|para[j]],f[i]+1);//状态转移
        printf("%d\n",f[(1<<n)-1]);//输出答案
    }
    return 0;
}

解题报告 P1941 飞扬的小鸟

虽说 AFO 了,但是我做下题总还是可以的吧我不想学文化课

题目内容

flappy bird 的改编题,地图为 n\times m,分别是长和高。每秒钟内可以点击多次屏幕,在第 i 位置处点击一次屏幕可以在下一秒上升 x_i 格,不点击屏幕下降 y_i 格,不能碰到管道或者触底(高度为 0),求如果可以通过游戏的最小点击屏幕次数或不可以通过游戏的话最多通过的管道数。

解题思路

考虑 f_{i,j} 表示到达 (i,j) 的最少点击次数,如不能到达用 INF 表示。

于是可以将状态的转移抽象成背包,每次可以选择点击无数次或者下降一次,转移方程如下:

f_{i,j}=\min(f_{i,j-x_i},f_{i-1,j-x_i})+1

这是上升来的,意义就是从前一秒的状态点击一次或者从当前秒再点击一次取最优

f_{i,j}=\min(f_{i,j},f_{i-1,j+y_i})

这就是下降来的

这题需要注意的地方:

  • 上升的过程是一个完全背包(可以点击屏幕无限次),下降的是 0-1 背包
  • 有可能会飞出去(大于 m),这个时候要特判,将其还原

我使用了结构体封装地图的每一格,包含了是否有管道,下降/上升的高度以及最高能通过的高度以及最低能通过的高度。

最后统计答案的时候如果不能过,那就从最后往前寻找第一个能过的点,然后统计前面有多少管道

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define a(x) game[x]
using namespace std;

const int maxn = 10005, INF = 0x3f3f3f3f;
int n, m, k;
int f[maxn][3005];

struct node
{
    int x, y, high, low;
    bool flag;
} game[maxn];

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int main()
{
    n = read(), m = read(), k = read();
    for (int i = 1; i <= n; i++)
    {
        a(i).x = read(), a(i).y = read();
        a(i).high = m, a(i).low = 1;
    }
    int p, l, h;
    for (int i = 1; i <= k; i++)
    {
        p = read(), l = read(), h = read();
        a(p).flag = 1,
        a(p).high = h - 1,
        a(p).low = l + 1;
    }
    memset(f, INF, sizeof(f));
    for (int i = 1; i <= m; i++)
        f[0][i] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = a(i).x + 1; j <= m + a(i).x; j++)
            f[i][j] = min(f[i][j], min(f[i][j - a(i).x] + 1, f[i - 1][j - a(i).x] + 1));
        for (int j = m; j <= m + a(i).x; j++)
            f[i][m] = min(f[i][m], f[i][j]);
        for (int j = 1; j <= m - a(i).y; j++)
            f[i][j] = min(f[i][j], f[i - 1][j + a(i).y]);
        for (int j = 1; j < a(i).low; j++)
            f[i][j] = INF;
        for (int j = m; j > a(i).high; j--)
            f[i][j] = INF;
    }
    int ans = INF;
    for (int i = 1; i <= m; i++)
        ans = min(ans, f[n][i]);
    if (ans < INF)
    {
        printf("1\n%d\n", ans);
        return 0;
    }
    for (int i = n - 1; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            if (f[i][j] < INF)
            {
                ans = 0;
                for (int t = 1; t <= i; t++)
                    if (a(t).flag)
                        ans++;
                printf("0\n%d\n", ans);
                return 0;
            }
}

解题报告 P2196 挖地雷【NOIP1996TGT3】

题目内容

P2196

大意:在一个地图上有 N 个地窖 (N \le 20),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径。当地窖及其连接的数据给出之后,某人可以从任一处开始挖地雷,然后可以沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使某人能挖到最多的地雷。注意是单向边

解题思路

和租船的思路差不多,都是 dp,但关键在于记录路径,所以这里选择倒着 dp,顺着打印路径

f_i=\max\lbrace f_j+a_i\rbrace

表示很讨厌远古的 noip 题,题面各种描述不清

#include <cstdio>

const int maxn=21;
int n,a[maxn],f[maxn],nxt[maxn];
bool b[maxn][maxn];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            scanf("%d",&b[i][j]);
    f[n]=a[n];
    for(int i=n-1;i>=1;i--)
    {
        for(int j=i+1;j<=n;j++)
            if(f[j]>f[i] && b[i][j])
            {
                f[i]=f[j];
                nxt[i]=j;
            }
        f[i]+=a[i];
    }
    int ans=0,st;
    for(int i=1;i<=n;i++)
        if(f[i]>ans)
            ans=f[i],st=i;
    printf("%d ",st);
    for(int i=st;nxt[i];i=nxt[i])
        printf("%d ",nxt[i]);
    printf("\n%d\n",ans);
    return 0;
}

解题报告 P1077 摆花【NOIP2012PJT3】

题目内容

P1077

大意:现要摆 m 盆花,一共 n 种花,从种类编号小到大摆,每种花最多摆 a_i 盆,求方案数

解题思路

此题抽象出来后可看作多重背包问题求方案数,每盆花的价值是 1,求装满 m 的方案数。

#include <cstdio>

const int p=1000007;
int n,m,f[105],w[1005];

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    scanf("%d %d",&n,&m);
    int x;
    for(int i=1;i<=n;i++)
        scanf("%d",w+i);
    f[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=1;k<=min(w[i],j);k++)//枚举这种花的数量
                f[j]=(f[j]%p+f[j-k]%p)%p;
    printf("%d\n",f[m]);
    return 0;
}

解题报告 P1095 守望者的逃离【NOIP2007PJ】

题目内容

P1095

大意:要在 t 秒内逃离 s 距离,每秒可以选择跑步(17m/s),闪现(60m/s)且消耗 10 点蓝,回蓝(4 点一秒),求是否能逃离,若能,求最短时间,若不能,求最长距离

解题思路

这题设计状态比较麻烦,如果都要一起考虑的话明显不行,所以只能分跑步和闪现两种情况来考虑。

f_i 为第 i 秒能跑的最远距离。

先考虑闪现,如果蓝够的话,就拼命闪现,蓝不够就回蓝直到蓝够了为止,再考虑跑步,如果发现某一秒跑步能达到的距离比闪现更远的话,更新他。

这样的方法就将需要考虑蓝和不考虑蓝的情况分开了,减少了难度,具体代码:

#include <cstdio>

int M,S,T,f[300005];

inline int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    scanf("%d %d %d",&M,&S,&T);
    int maxs=0;
    for(int t=1;t<=T;t++)
    {
        if(M>=10)//蓝够
            f[t]=f[t-1]+60,M-=10;//闪现
        else
            f[t]=f[t-1],M+=4;//回蓝
    }
    for(int t=1;t<=T;t++)
    {
        f[t]=max(f[t],f[t-1]+17),maxs=max(maxs,f[t]);//如果跑步更优,更新
        if(f[t]>=S)
        {
            printf("Yes\n%d\n",t);
            return 0;
        }
    }
    printf("No\n%d\n",maxs);
    return 0;
}

解题报告 P1020 导弹拦截【NOIP1999TG】

题目内容

P1020

大意:求最长不下降子序列和最长上升子序列。

解题思路

半年前的坑,今天给填上。不难想出 O(n^2) 的做法:设 f_i 为以 a_i 结尾的 LIS 的长度,则有状态转移方程

f_i= \max_{j

每次都往前面扫描一遍,复杂度 O(n^2)

#include <cstdio>
#include <cstring>
#define maxn 100009
int a[maxn],b[maxn],h[maxn];

using namespace std;
int main()
{
    int ans1=0;
    memset(a,0,sizeof(a));
    memset(b,1,sizeof(b));
    memset(h,0x7ffffff,sizeof(h));
    int n=1,m=0;//n:the num of missiles, m:the num of sys
    while(scanf("%d",&a[n])!=EOF)
    {
        int l=0;
        for(int i=n-1;i>0;i--)
        {
            if(a[i]>=a[n]&&b[i]>l)
                l=b[i];
        }
        b[n]=l+1;
        if(b[n]>ans1) ans1=b[n];
        int x=0;
        for(int k=1;k<=n;k++)
        {
            if(h[k]>=a[n])
                if(x==0)
                    x=k;
                else if(h[k]<h[x])
                    x=k;
        }
        if(x==0)
        {
            m++;
            x=m;
        }
        h[x]=a[n];
        n++;
    }
    printf("%d %d\n",ans1,m);
    return 0;
}

当然这个算法太慢了,过不了洛谷的后面 10 个极限数据,因此我们需要 O(n\log n) 的做法,这个算法结合了二分查找和贪心。

如果我们此时设 f_i 表示长度为 i 的 LIS 的结尾的数字的话,思考:是不是当 f_i 越小,才越方便后面的数接进这个 LIS 呢,具体维护 f_i 的方法如下:

a_2 开始枚举每一个 a_i,如果新的 a_i 能接上这个已知最长的 LIS,那就接上去,否则就在 f 数组里面寻找能让 a_i 接上的 LIS 的长度,由于 f 数组一定满足单调递减,所以只需要利用二分查找在里面寻找第一个 f_j 使得 f_j\ge a_i 就可以了,然后更新对应的 f_j 即可。二分查找可以使用 STL 来偷懒降低代码复杂度。

该算法的复杂度为 O(n\log n)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=100000+5;
int f1[maxn],f2[maxn],a[maxn],tot;

bool cmp(const int& a,const int& b)
{
    return a>b;
}

int main()
{
    memset(f1,0x7fffffff,sizeof(f1));
    memset(f2,0x7fffffff,sizeof(f2));
    while(scanf("%d",&a[++tot])!=EOF);
    f1[1]=a[1],f2[1]=a[1];
    //f[i]存储长度为i的序列的尾元素
    int len1=1,len2=1;//len表示查询到的LIS的最长长度
    for(int i=2;i<tot;i++)
    {
        if(a[i]<=f1[len1])//如果当前的a[i]可以接在最长的LIS的末尾
            f1[++len1]=a[i];//就接上去
        else
        {
            int p1=upper_bound(f1+1,f1+1+len1,a[i],cmp) - f1;
            //否则找到第一个大于他的
            f1[p1]=a[i];//然后接在后面,更新最小值
        }
        if(a[i]>f2[len2])
            f2[++len2]=a[i];
        else
        {
            int p2=lower_bound(f2+1,f2+len2+1,a[i])-f2;
            f2[p2]=a[i];
        }
    }
    printf("%d\n%d\n",len1,len2);
    return 0;
}

解题报告 P1019 单词接龙【NOIP2000TGT3】

题目内容

P1019

大意:给出 n 个单词,每个单词最多出现两遍,求最长的龙的长度,前单词和后单词之间不能包含。

解题思路

这题一看就很难调细节,直到我看了题解才发现了新世界。

大体的思路非常好想,就是无脑 dfs 下去,但是整道题的难点就在于字符串的拼接处理。

每次 dfs 的时候函数长这样:dfs(string now,int l),其中 now 是上一个单词,l 是龙的长度,所以根本没必要存龙(我是sb),直接存上一个单词,然后接着拼接就可以了。

然后拼接有一个原则(贪心):为了保证最后接出来的龙最长,相交的字符串部分需要尽可能的短,所以定义了一个 link() 函数返回的是两个单词之间最小重叠部分的长度。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int n;
string word[22];
int vis[21];
int ans=0;

int link(string a,string b)//返回两个字符串的最小重叠部分的长度
{
    for(int i=1;i<min(a.size(),b.size());i++)//枚举重叠部分的长度
    {
        bool flag=1;
        for(int j=0;j<i;j++)
            if(a[a.size() - i + j] != b[j])//每一位来判
                flag = 0;
        if(flag)
            return i;
    }
    return 0;
}

void dfs(string now,int l)//now为上一个单词,l为龙的长度
{
    ans=max(ans,l);//每次更新一下答案
    for(int i=0;i<n;i++)//枚举下一个单词
    {
        if(vis[i]>=2)//如果已经用过两次了
            continue;
        int c=link(now,word[i]);//获取两个单词间的重叠长度
        if(c)
        {
            vis[i]++;
            dfs(word[i],l+word[i].size()-c);//继续搜
            vis[i]--;
        }
    }
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<=n;i++)
        cin>>word[i];
    dfs(" "+word[n],1);//这里的空格防link函数错误返回
    cout<<ans<<endl;
    return 0;
}

解题报告 P1063 能量项链【NOIP2006TGT1】

题目内容

P1063

本题对于题意的理解很重要

Mars 星球上,每个 Mars 人都随身佩带着一串能量项链。在项链上有 N 颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是 Mars 人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 m,尾标记为 r,后一颗能量珠的头标记为 r,尾标记为 n,则聚合后释放的能量为 m \times r \times nMars 单位),新产生的珠子的头标记为 m,尾标记为 n

需要时,Mars 人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。

例如:设 N=44 颗珠子的头标记与尾标记依次为 (2,3) (3,5) (5,10) (10,2)。我们用记号 表示两颗珠子的聚合操作,(j⊕k) 表示第 j,k 两颗珠子聚合后所释放的能量。则第 4、1 两颗珠子聚合后释放的能量为:

(4⊕1)=10 \times 2 \times 3=60=10×2×3=60

第一行是一个正整数 N(4≤N≤100),表示项链上珠子的个数。第二行是 N 个用空格隔开的正整数,所有的数均不超过 1000。第 i 个数为第 i 颗珠子的头标记 (1≤i≤N),当 i 时,第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记。第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。

至于珠子的顺序,你可以这样确定:将项链放到桌面上,不要出现交叉,随意指定第一颗珠子,然后按顺时针方向确定其他珠子的顺序。

解题思路

一个项链,说明是环形区间 dp,但这题比较注重细节。我们设 f(i,j) 表示区间 [i,j] 上的所有珍珠合并后能释放的最大能量,而 a_i 又是第 i 颗珠子的头标记,所以我们有如下的状态转移方程:

f(i,j)=\max_{k\in [i,j)}\lbrace f(i,k)+f(k+1,j)+a_i\times a_{k+1}\times a_{j+1}\rbrace

这个方程的解释:首先枚举 k 作为断点,表示将区间 [i,k](k,j] 的珠子合并,而合并释放的能量是前珠子的头标记乘 k 珠子的尾标记乘后珠子的尾标记,必须清楚自己设的东西表示的是什么否则就是像我一样调半个小时

除此之外没有什么难点,代码见下:

#include <cstdio>
inline int max(int a,int b)
{
    return a>b?a:b;
}

const int maxn=205;
int n,f[maxn][maxn],a[maxn];

//f[i][j]表示[i,j]区间内的珠合并后能达到的最大价值

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        a[n+i]=a[i];//常规环状展开
    }
    int ans=0;
    for(int l=2;l<=n;l++)//l表示枚举的区间长度
        for(int i=1,j=i+l-1;i<n<<1&&j<=n<<1;i++,j++)//枚举左右端点
            for(int k=i;k<j;k++)//然后枚举中间断点
            {
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);//转移方程
                ans=max(ans,f[i][j]);//其实可以直接统计答案
            }
    printf("%d\n",ans);
    return 0;
}

解题报告 P1541 乌龟棋【NOIP2010TG】

题目内容

P1541

大意:乌龟棋的棋盘是一行 N 个格子,每个格子上一个分数(非负整数)。棋盘第 1 格是唯一的起点,第 N 格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 M 张爬行卡片,分成 4 种不同的类型(M 张卡片中不一定包含所有 4 种类型的卡片,见样例),每种类型的卡片上分别标有 1,2,3,4 四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能使用一次。

游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?

解题思路

想到卡片的使用顺序可能影响到最终获得的分数,就需要使用 dp,设 f(i,j,k,l) 表示 4 种卡片分别使用了 i,j,k,l 张,则这一个状态可以由四个之前的状态递推而来(只要不为 0,可以选 1~4 号卡中的任意一个)。

方程:

f(i,j,k,l)=\max\lbrace f(i,j,k,l),f(i-1,j,k,l),f(i,j-1,k,l),f(i,j,k-1,l),f(i,j,k,l-1)\rbrace+a_{i+2j+3k+4l+1}

代码:

#include <cstdio>

const int maxn=355,maxg=41;
int n,m,g[5],a[maxn],f[maxg][maxg][maxg][maxg];

inline int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    register int x;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        g[x]++;
    }
    f[0][0][0][0]=a[1];
    for(int i=0;i<=g[1];i++)
        for(int j=0;j<=g[2];j++)
            for(int k=0;k<=g[3];k++)
                for(int l=0;l<=g[4];l++)
                {
                    int r=i+j*2+k*3+l*4+1;
                    if(i)
                        f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[r]);
                    if(j)
                        f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[r]);
                    if(k)
                        f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[r]);
                    if(l)
                        f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[r]);
                }
    printf("%d\n",f[g[1]][g[2]][g[3]][g[4]]);
    return 0;
}