F001 木棒加工问题

Problem Description

现有n根木棒，已知它们的长度和重量。要用一部木工机一根一根地加工这些木棒。该机器在加工过程中需要一定的准备时间，是用于清洗机器，调整工具和模板的。木工机需要的准备时间如下：
（1） 第一根木棒需要1min的准备时间；
（2） 在加工了一根长为l，重为w的木棒之后，接着加工一根长为l’（l≤l’），重为w’（w≤w’）的木棒是不需要任何准备时间的。否则需要一分钟的准备时间。
给定n根木棒，你要找到最少的准备时间。例如现在有长和重分别为（4,9），（5,2），（2,1），（3,5）和（1,4）的五根木棒，那么所需准备时间最少为2min，顺序为（1,4），（3,5），（4,9），（2,1），（5,2）。

Input

输入有多组测试例。输入数据的第一行是测试例的个数（T）。每个测试例两行：第一行是一个整数n（1≤n≤5000），表示有多少根木棒；第二行包括n*2个整数，表示l1,w1,l2,w2,l3,w3,…,ln,wn,全部不大于10000，其中li和wi表示第i根木棒的长度和重量。数据由一个或多个空格分隔。

Output

输出是以分钟为单位的最少准备时间，一行一个。

Sample Input

3 
5 
4 9 5 2 2 1 3 5 1 4 
3 
2 2 1 1 2 2 
3 
1 3 2 2 3 1

Sample Output

2
1
3

实现思路

经典的双关键字dp题，首先对一个关键字进行从小到大的排序，那么这样对于其宽度就相当于是求其不降子序列的段数。对于这类问题我们知道有个很经典的实现方式就是转化为求解其最长严格下降子序列的长度

实现细节

同上

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
struct sti
{
    int l;
    int w;
};
sti a[5050];
bool cmp(sti x,sti y)
{
    return x.l<y.l;
}
int dp[5050];
int n;
int solve()
{
    dp[1] =1;
    int ret = 1;
    for (int i=2;i<=n;i++)
    {
        dp[i] = 1;
        for (int j=1;j<=i-1;j++)
            if (a[j].w>a[i].w)
                dp[i] = max(dp[i],dp[j]+1);
        ret = max(ret,dp[i]);
    }
    return ret;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i=1;i<=n;i++)
            scanf("%d%d",&a[i].l,&a[i].w);
        sort(a+1,a+n+1,cmp);
        cout << solve() << endl;
    }
}

F002 装箱

Problem Description

一个工厂生产的产品形状都是长方体，高度都是h，主要有11，22，33，44，55，66等6种。这些产品在邮寄时被包装在一个66h的长方体包裹中。由于邮费很贵，工厂希望减小每个订单的包裹数量以增加他们的利润。因此他们需要一个好的程序帮他们解决这个问题。你的任务就是设计这个程序。

Input

输入包括多组测试数据，每一行代表一个订单。每个订单里的一行包括六个整数，用空格隔开，从小到大分别为这6种产品的数量。6个0表示文件结束。

Output

针对每个订单输出一个整数，占一行，代表对应的订单所需的最小包裹数。没有多余的空行。

Sample Input

0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0

Sample Output

2
1

实现思路

一个考验细心程度的题，这里在对大块物体放入时统计可以放1、2块的数量，最后对1、2块进行单独处理判断

实现细节

在对二判断的时候也不要忘了增加对一可用容量的增加

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
int main()
{
    int a[10];
    int ret[10];
    while (1)
    {
        bool flag =false;
        for (int i=1;i<=6;i++)
        {
            cin >> a[i];
            ret[i]=0;
            if (a[i]!=0)
                flag = true;
        }
        if (!flag)
            break;
        int ans=0;
        ans+=a[6];
        ans+=a[5];
        ret[1] = a[5]*11;
        ans+=a[4];
        ret[2] = a[4]*5;
        ans+=a[3]/4;
        if (a[3]%4!=0)
            ans++;
        if (a[3]%4==1)
        {
            ret[2]+=5;
            ret[1]+=7;
        }
        else if(a[3]%4==2)
        {
            ret[2]+=3;
            ret[1]+=6;
        }
        else if(a[3]%4==3)
        {
            ret[2]+=1;
            ret[1]+=5;
        }
        if (ret[2]>=a[2])
        {
            ret[2]-=a[2];
            a[2]=0;
            a[1]=max(0,a[1]-ret[2]*4);
            a[1]=max(0,a[1]-ret[1]);
            if (a[1]>0)
            {
                ans+=a[1]/36;
                a[1]%=36;
                if (a[1]!=0)
                    ans++;
            }
        }
        else
        {
            a[2]-=ret[2];
            if (a[2]>0)
            {
                ans+=a[2]/9;
                a[2]%=9;
                if (a[2]!=0)
                    ans++;
                ret[1]+=36-a[2]*4;
            }
            a[1]=max(0,a[1]-ret[1]);
            if (a[1]>0)
            {
                ans+=a[1]/36;
                a[1]%=36;
                if (a[1]!=0)
                    ans++;
            }
        }
        cout << ans << endl;
    }
}

F003 移动桌子

Problem Description

著名的ACM（Advanced Computer Maker）公司租用了一层有400个房间的办公楼，结构如下。

这层楼沿着走廊南北向的两边各有200个房间。最近，公司要做一次装修，需要在各个办公室之间搬运办公桌。由于走廊狭窄，办公桌都很大，走廊里一次只能通过一张办公桌。必须制定计划提高搬运效率。经理制定如下计划：一张办公桌从一个房间移动到另一个房间最多用十分钟。当从房间i移动一张办公桌到房间j，两个办公室之间的走廊都会被占用。所以，每10分钟内，只要不是同一段走廊，都可以在房间之间移动办公桌。为了说得更清楚一些，经理举例说明哪些情况可以同时移动，哪些情况不能同时移动。

每个房间，只有一张办公桌进出。现在，经理想找到一种方案，使移动桌子的事情尽快完成。请编写程序解决经理的难题

Input

输入数据有T组测试例，在第一行给出测试例个数（T）。每个测试例的第一行是一个整数N（1≤N≤200），表示要搬运办公桌的次数。接下来N行，每行两个正整数s和t，表示一张桌子，是从房间号码s移到房间号码t。有多组输入数据，输入第一行为一个表示输入数据总数的整数N，然后是N组输入数据。

Output

每组输入都有一行的输出数据，为一整数T，表示完成任务所花费的最少时间。

Sample Input

2 
4 
10 20 
30 40 
50 60 
70 80 
2 
1 3 
2 200

Sample Output

10
20

实现思路

没给编号范围本来以为挺麻烦的，后来发现数据很小，是最大重复子段的暴力求解

实现细节

同上

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
int cor[10010];
int main()
{
    int t,n,s,e;
    cin >> t;
    while (t--)
    {
        cin >> n;
        memset(cor, 0, sizeof(cor));
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d",&s,&e);
            for (int j=s;j<=e;j++)
                cor[j]++;
        }
        int ret=-1;
        for (int i=1;i<=10000;i++)
            ret = max(ret,cor[i]);
        cout << ret*10 << endl;
    }
}

F004 基因集合

Problem Description

随着大量的基因组DNA序列数据被获得，它对于了解基因越来越重要（基因组DNA的一部分，是负责蛋白质合成的）。众所周知，在基因组序列中，由于存在垃圾的DNA中断基因的编码区，真核生物（相对于原核生物）的基因链更加复杂。也就是说，一个基因被分成几个编码片段（称为外显子）。虽然在蛋白质的合成过程中，外显子的顺序是固定的，但是外显子的数量和长度可以是任意的。
大多数基因识别算法分为两步：第一步，寻找可能的外显子；第二步，通过寻找一条拥有尽可能多的外显子的基因链，尽可能大地拼接一个基因。这条链必须遵循外显子出现在基因组序列中的顺序。外显子i在外显子j的前面的条件是i的末尾必须在j开头的前面。
本题的目标是，给定一组可能的外显子，找出一条拥有尽可能多的外显子链，拼接成一个基因。

Input

给出几组输入实例。每个实例的开头是基因组序列中可能的外显子数n(0 < n < 1000)。接着的n行，每行是一对整数，表示外显子在基因组序列中的起始和结束位置。假设基因组序列最长为50000。当一行是0时，表示输入结束。

Output

给出几组输入实例。每个实例的开头是基因组序列中可能的外显子数n(0 < n < 1000)。接着的n行，每行是一对整数，表示外显子在基因组序列中的起始和结束位置。假设基因组序列最长为50000。当一行是0时，表示输入结束。

Sample Input

6
340 500
220 470
100 300
880 943
525 556
612 776
0

Sample Output

3 1 5 6 4

实现思路

。。。刚开始看错题了。实际上就是一个基本的贪心，第一个必取，后面贪心取就可

实现细节

同上

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
struct gen
{
    int s;
    int e;
    int no;
};
gen a[1010];
int ans[50010];
bool cmp(gen x,gen y)
{
    return x.e<y.e;
}
int main()
{
    int n;
    while (cin >> n)
    {
        if (n==0)
            break;
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i].s,&a[i].e);
            a[i].no = i;
        }
        sort(a+1,a+n+1,cmp);
        int co=1;
        int tim = a[1].e;
        ans[co] = 1;
        for (int i=2;i<=n;i++)
        {
            if (a[i].s<=tim)
                continue;
            ans[++co] = i;
            tim = a[i].e;
        }
        for (int i=1;i<=co;i++)
            cout << a[ans[i]].no << " ";
        cout << endl;
    }
}

F005 主框架

Problem Description

多纳先生是ACM（Agent on Computing of Mathematics，计算数学代理商）大型计算机的管理员。该代理商为一些公司承担在大型计算机上的计算工作，完成工作后获得报酬，因此大型计算机对这个代理商来说太重要了。多纳先生需要为这些在大型计算机上运行的作业安排顺序。一旦要运行某个作业，他就要检查运行该作业所需要的空闲资源。如果空闲资源足够的话，他就为该作业分配这些资源；否则就将该作业挂起，直至有足够的资源投入运行。
刚开始他并不熟悉这项工作，把事情搞得很乱。日积月累，他就胜任这项工作了。而且他还总结了一套规则：
（1）大型计算机有M个CPU和N大小的内存空间可供分配
（2）对等待运行的作业有一个等待队列。可以假定这个队列足够长，能够存放所有等待运行的作业。
（3）假定作业Ji需要Ai个CPU和Bi的内存空间，在时间Ti到达等待队列，需要在时间Ui之前完成。成功运行后，代理商可以获得Vi($)的报酬；如果能在规定的时间之前完成，则每小时还可以额外获得Wi($)的奖金；如果工期拖延，则每小时赔偿Xi($)。例如，假定一个作业的报酬是10$，时限8小时，每拖欠一小时罚2$。如果该作业在10小时完成，则代理商可以获得10-(10-8)*2=6$。
（4）当一个作业开始后，就独占了分配给它的CPU和内存空间，不能同时再分配给其他作业。当该作业运行结束后，这些资源被释放。如果资源足够多，同时可以运行多个作业。
（5）为了最大限度地发挥大型计算机的计算能力，每个作业在开始运行后刚好一小时就完成。你可以假定每个作业的运行时间就是一小时。
（6）没有作业运行时，机器空闲，一直到一个作业进入作业等待队列。
（7）如果有多个作业进入作业等待队列，则报酬高的作业优先。可以假定这些作业的报酬都不相等。
（8）如果某个作业的空闲CPU或内存空间不能满足，它就是被挂起一小时，也不占用任何资源。一小时后，再次为该作业检查资源，而不需要考虑等待队列里的其他作业。如果资源仍不满足要求，那就继续挂起一小时，把资源分配给其他在等待队列里的作业。否则，该作业将独占CPU和存储空间并投入运行。
（9）当多个作业挂起时，采取先来先服务的原则。
使用这些规则，多纳先生把事情安排得井井有条。现在除了日常公务外，代理商要求他根据作业列表计算收入。给定某个时间F，计算出已经完成的作业和应该被完成的作业。对作业Ji，如果它的时限Ui>F并且仍未完成，就不需要统计收入。对已经完成的作业或Ui≤F的作业都要统计。如果工作没有完成，它不会给代理商带来报酬，但到这个时间F为止的罚款仍要计算。
他不会程序设计，又不想手工做，现在你帮助他解决这个问题。

Input

有多组测试例。每个测试例描述大型计算机的资源和作业列表，第一行是整数F（0≤F≤10000），表示时限。接下来的一行是三个整数M，N和L（M，N，L≥0），M是机器CPU的数量，N是存储空间的大小，L是作业等待队列中作业的数量。最多有10000个作业。
后面的L行是作业的信息。描述作业Ji的数据是7个整数：Ai，Bi，Ti，Ui，Vi，Wi，Xi。Ai和Bi（Ai，Bi≥0）指出了该作业对CPU和内存的需求。Ti和Ui表示作业的到达时间和时限（0≤Ti≤Ui）。Vi，Wi，Xi分别是工作的报酬、奖励和罚款。
一个空的测试例（F=0）表示输入结束，该测试点无需处理。

Output

根据作业列表计算总收入。对每个测试例，输出测试例编号，一个冒号，一个空格，然后是收入。
测试例之间有一个空行。
注意：对尚未投入运行的、且时限超过F的作业，不必统计。

Sample Input

10
4 256 3
1 16 2 3 10 5 6
2 128 2 4 30 10 5
2 128 2 4 20 10 5
0

Sample Output

Case 1: 74

实现思路

这。。题目也太长了。简单点说就是有一些任务，按题目给的要求先排队，每次用两层遍历，第一遍遍历时刻，第二遍遍历每个任务，用数组记录是否已经完成。最后统计即可

实现细节

1、在完成其中一项任务的同时要处理其罚款/奖金

2、当全部完成后还要遍历一遍所有的任务，如果任务已经到时并未完成需要计算罚款

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
struct work
{
    int a,b,t,u,v,w,x;
};
work q[10010];
bool cmp(work p1,work p2)
{
    if (p1.t==p2.t)
        return p1.v>p2.v;
    else return p1.t<p2.t;
}
bool ok[10010];
int main()
{
    int f,cpuh,memh,l,cpun,memn;
    int co=0;
    while(cin >> f)
    {
        if (f==0)
            break;
        co++;
        cin >> cpuh >> memh >> l;
        for (int i=1;i<=l;i++)
            scanf("%d%d%d%d%d%d%d",&q[i].a,&q[i].b,&q[i].t,&q[i].u,&q[i].v,&q[i].w,&q[i].x);
        sort(q+1,q+l+1,cmp);
        int ret =0;
        memset(ok, false, sizeof(ok));
        for (int i=1;i<=f;i++)
        {
            cpun = cpuh;
            memn = memh;
            for (int j=1;j<=l;j++)
            {
                if (q[j].t>=i)
                    break;
                if (ok[j] || cpun<q[j].a || memn<q[j].b)
                    continue;
                ok[j] = true;
                cpun-=q[j].a; memn-=q[j].b;
                ret += q[j].v;
                if (i>q[j].u)
                    ret-=(i-q[j].u)*q[j].x;
                else if (i<q[j].u)
                    ret += (q[j].u-i)*q[j].w;
            }
        }
        for (int i=1;i<=l;i++)
            if (!ok[i] && q[i].u<=f)
                ret -= (f-q[i].u)*q[i].x;
        printf("Case %d: %d\n",co,ret);
        cout << endl;
    }
}

F006 整数区间

Problem Description

一个整数区间[a,b](a < b)，是一个从a到b连续整数的集合。 现在给你n个整数区间，编程找出一个集合R，使得n个集合中的每个集合都有2个整数出现在R中，并且这个集合R包含的整数个数最少。

Input

输入有多组数据，每组第一行包含整数n(1 <= n <= 10000)，表示整数区间的个数。接下来n行，每行包含两个整数a和b(0 <= a < b <= 10000, a < b)。

Output

输出符合条件的集合R中元素的个数。

Sample Input

4
3 6
2 4
0 2
4 7

Sample Output

4

Hint

对于输入样例，我们可以找到集合R{1,2,4,5}和R{1,2,4,6}，这里R的元素的个数为4.

实现思路

使用贪心策略，现按结束位置从小到达进行排序，然后维护两个点，表示能够覆盖上一个区域的两个点。那么在下一次判断时只要判明两个点是否还能继续用。

实现细节

这里增加点的策略是总是加在需要加的这个区间的结尾

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
struct qu
{
    int a,b;
};
qu l[10010];
bool cmp(qu p,qu q)
{
    if (p.b==q.b)
        return p.a<q.a;
    return p.b<q.b;
}
int main()
{
    int n,s,e;
    while (cin >> n)
    {
        int ret=0;
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d",&l[i].a,&l[i].b);
        }
        sort(l+1,l+n+1,cmp);
        s = l[1].b-1;
        e = l[1].b;
        ret=2;
        for (int i=2;i<=n;i++)
        {
            if (l[i].a<=s)
                continue;
            else if (l[i].a>s && l[i].a<=e)
            {
                ret++;
                int t = e;
                e = l[i].b;
                s = t;
            }
            else
            {
                ret+=2;
                s = l[i].b-1;
                e = l[i].b;
            }
        }
        cout << ret << endl;
    }
}

F007 安装雷达

Problem Description

我们假设海岸线是一条无限直线：以海岸线为界，陆地和海洋被分开，在海边分布着很多小岛。现在，我们在海岸线上安装雷达，每个雷达有固定的通讯范围（以d为半径的圆形区域），这样，海边的小岛就可以被某个雷达信号覆盖。
这里我们使用笛卡尔坐标系，定义海岸线为x轴，x轴上方是海洋，下方是陆地。给出分布在海边每个小岛的坐标位置和雷达信号能覆盖的范围d，你的任务是计算出最小需要安装的雷达数目，使得这些雷达信号能覆盖到所有海边的小岛。每个小岛的坐标格式为(x,y)。
如下图所示，给出第一个输入样例的坐标表示，这样在(-2,0),(1,0)上分别安装雷达就可以覆盖所有的小岛（p点），所以我们只需要安装2个雷达。

Input

输入包含多组测试样例。每组测试第一行包含两个整数n(1<=n<=1000)和d，n表示小岛的数目，d表示雷达能覆盖的范围的半径。接下来n行，每行由整数x和y组成，表示n个小岛的坐标位置。每两组数据之间有一个空行。
输入0 0表示输入的结束。

Output

对于每一组输入，按照输出样例中的格式输出：包含输出序号和最少需要安装雷达的数目。如果找不到解决方案，即不能找到一种安装方案覆盖所有的小岛，输出”-1”。

Sample Input

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

Sample Output

Case 1: 2
Case 2: 1

实现思路

这应该是很经典的打击贪心初学者的题。这个题其实是一个线段覆盖问题，这样的话比上面一题更为简单

实现细节

不要忘了输出-1的时候也要加case。。。

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
struct ra
{
    double l,r;
};
ra a[1010];
bool cmp(ra x,ra y)
{
    if (fabs(y.r-x.r)<1e-6)
        return x.l<y.l;
    return x.r<y.r;
}
int main()
{
    int n,d;
    int t1,t2;
    int co=0;
    while(cin >> n >> d)
    {
        if (n==0 && d==0)
            break;
        bool flag = true;
        for (int i=1;i<=n;i++)
        {
            cin >> t1 >> t2;
            if (t2>d)
                flag = false;
            a[i].l = (double)t1 - sqrt(d*d - t2*t2);
            a[i].r = (double)t1 + sqrt(d*d - t2*t2);
        }
        if (!flag)
        {
            printf("Case %d: %d\n",++co,-1);
            continue;
        }
        sort(a+1,a+n+1,cmp);
        int ret=1;
        int poi =a[1].r;
        for (int i=1;i<=n;i++)
        {
            if (a[i].l<=poi)
                continue;
            ret++;
            poi = a[i].r;
        }
        printf("Case %d: %d\n",++co,ret);
    }
}