首页 > 代码库 > 暑期刷题记录

暑期刷题记录

2024-07-14 16:14:58   216人阅读

已经决定不玩空间了，在这里开一贴，用来记录暑假期间刷过的每一题。

时间从7.29号开始计算。

 

1. HDU 4883 TIANKENG’s restaurant    ( 贪心 )

这个是bestcoder #2 的第一题，，居然想半天没有做出来，简直是太弱了，居然又在分情况讨论题目大意：TIANKENG的饭店有客人陆续到达，如果再一批客人没有走的情况下，新来的客人就需要另外的座位，问最少需要多少座位。题解： 贪心算法，首先对所有时间进行排序(时间相同以人数为第二关键字), 然后如果是到达，加上该人数，如果是离开，减去该人数，然后从头到尾扫一遍找到最大值。
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define maxn 10010 6  7 struct node 8 { 9   int time;10   int peo;11 }E[maxn<<1];12 13 int cmp(node x,node y)14 {15     if(x.time != y.time)    return x.time < y.time;16     else                    return x.peo < y.peo;17 }18 int t,n,a,b,c,d,p;19 20 int main()21 {22     scanf("%d",&t);23     while(t--)24     {25         int cnt = 0;26         scanf("%d",&n);27         for(int i=0;i<n;i++)28         {29             scanf("%d %d:%d %d:%d",&p,&a,&b,&c,&d);30             E[cnt].peo = p;31             E[cnt++].time = a*60 + b;32             E[cnt].peo = -p;33             E[cnt++].time = c*60 + d;34         }35         sort(E,E+cnt,cmp);36         int res = 0;37         int put = -1;38         for(int i=0;i<cnt;i++)39         {40             res += E[i].peo;41             if(res > put)   put = res;42         }43         printf("%d\n",put);44     }45     return 0;46 }
代码君

 

2. HDU 4521 小明系列问题――小明序列   ( 线段树 + dp思想 )

题目大意：给出一个序列，找出这个序列的"小明序列"所需要的元素的个数。小明序列的要求： 是原序列的递增子序列，并且子序列中相邻元素的下标为d思路： 线段树 + dp思想来更新(无奈dp思想太弱了)线段树的域 Max[] 用来存放当前结点结束的Sub序列的最大元素个数, 从下标 d + 1 开始更新，
#include <cstdio>#include <cstring>#include <algorithm>#define lson l, m, rt << 1#define rson m + 1, r, rt << 1 | 1#define mid(l,r) (l + r) >> 1#define maxn 101000#define inf 0x3f3f3f3fusing namespace std;int Max[maxn<<2];int d, n, s[maxn], dp[maxn], res, len;void PushUp(int rt){    Max[rt] = max(Max[rt<<1], Max[rt<<1|1]);}void Build(int l,int r,int rt){    Max[rt] = 0;    if(l == r)  return;    int m = mid(l,r);    Build(lson);    Build(rson);}void Update(int pos,int val,int l,int r,int rt){    if(l == r)    {        Max[rt] = max(val,Max[rt]);        return;    }    int m = mid(l,r);    if(pos <= m)    Update(pos,val,lson);    else            Update(pos,val,rson);    PushUp(rt);}int Query(int L,int R,int l,int r,int rt){    if(L <= l && r <= R)    return Max[rt];    int m = mid(l,r);    int t1 = -inf;    int t2 = -inf;    if(L <= m)  t1 = Query(L,R,lson);    if(R >  m)  t2 = Query(l,R,rson);    return max(t1,t2);}int main(){    while(~scanf("%d %d",&n,&d))    {        res = len = 0;        for(int i=1;i<=n;i++)        {            scanf("%d",&s[i]);            len = max(s[i],len);        }        Build(0,len,1);        for(int i=1;i<=n;i++)        {            //从d + 1 位置开始更新            if(i > d + 1)   Update(s[i-d-1],dp[i-d-1],0,len,1);            //状态转移时，查询比当前值小(即s[i]-1)的最大值               if(s[i] > 0)  dp[i] = Query(0,s[i]-1,0,len,1) + 1;            else          dp[i] = 1;            res = max(res,dp[i]);        }        printf("%d\n",res);    }    return 0;}
代码君

 


 

 


联系
我们