[关闭]
@morehigh 2017-02-25T03:13:29.000000Z 字数 3135 阅读 992

CQUPT 集训队专题训练（花式STL）

STL

b

A - Moo University - Financial Aid
题意：

  1. 有C(N <= C <= 100,000)头奶牛，现要招收N(1 <= N <= 19999)头奶牛上大学，给定每头奶牛的智商和所需补助，并给定最大可提供补助和F,0 <= F <= 2000000000，求补助奶牛的智商最大中位数

解题思路：

  1. 将奶牛按智商从小到大排序，然后枚举中位数,那么问题就是如何确定中位数左右分别选取n/2头奶牛的最小费用,这个可以通过堆预处理得出,(堆的维护要用到优先队列），正向扫描一遍每次看当前奶牛所需费用是否小于堆顶元素费用，若小于队顶出堆，当前奶牛费用入堆.反向同理,然后枚举一下中位数即可

代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <queue>
  6. const int inf=10*0x7ffffff;
  8. using namespace std;
  9. long long s1[100050],s2[100050];
  10. struct Node
  11. {
  12.     int fir,sec;
  13.     bool operator< (const Node &a) const
  14.     {
  15.         return sec<a.sec;
  16.     }
  17. }cow[100050];
  18. bool cmp(Node x,Node y)
  19. {
  20.     return x.fir<y.fir;
  21. }
  22. int main()
  23. {
  24.     int n,c,f;
  25. //  cout<<inf<<" "<<10*0x7ffffff<<endl;
  26.     while(~scanf("%d%d%d",&n,&c,&f))
  27.     {
  28.         for(int i=0;i<c;i++)
  29.          scanf("%d%d",&cow[i].fir,&cow[i].sec);
  30.         sort(cow,cow+c,cmp);
  31.         priority_queue<Node> pq;
  32.         int sum=0;
  33.         for(int i=0;i<c;i++)
  34.         {
  35.             s1[i]=inf;
  36.             if(i<n/2)
  37.             {
  38.                 pq.push(cow[i]);
  39.                 sum+=cow[i].sec;
  40.                 continue;
  41.             }
  42.             s1[i]=sum;
  43.             if(cow[i].sec>=pq.top().sec)continue;
  44.             sum-=pq.top().sec;
  45.             pq.pop();
  46.             sum+=cow[i].sec;
  47.             pq.push(cow[i]);
  48.         }
  49.         sum=0;
  50.         while(!pq.empty())pq.pop();
  51.         for(int i=c-1;i>=0;i--)
  52.         {
  53.             s2[i]=inf;
  54.             if(i>c-1-n/2)
  55.             {
  56.                 pq.push(cow[i]);
  57.                 sum+=cow[i].sec;
  58.                 continue;
  59.             }
  60.             s2[i]=sum;
  61.             if(cow[i].sec>=pq.top().sec)continue;
  62.             sum-=pq.top().sec;
  63.             pq.pop();
  64.             sum+=cow[i].sec;
  65.             pq.push(cow[i]);
  66.         }
  67.         int ans=-1;
  68.         for(int i=c-1-n/2;i>=n/2;i--)
  69.         {
  70.         //  cout<<s1[i]<<s2[i]<<" "<<cow[i].sec<<endl;
  71.             if(s1[i]+s2[i]+cow[i].sec<=f)
  72.             {
  73.                 ans=cow[i].fir;
  74.                 break;
  75.             }
  76.         }
  77.         printf("%d\n",ans);
  78.     }
  79.     return 0;
  80. }

C - HDU Today
题意：

  1. N(0<=N<=10000)是公交车总数，从起始点start到终点end，有n行每一行有一个s,e分别代表车站的站名，和时间t.求坐公交车的最短时间，

解题思路：

  1. 首先考虑到要用 dijkstra算法求最短时间，不过每一站的站名是字符串，需要用map将字符串映射为数字，便于处理

代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <map>
  6. #include <string>
  7. #include <cmath>
  8. #define inf 0x3f3f3f3f
  9. using namespace std;
  10. char start[100],endd[100],s[100],e[100];
  11. int t,ma[200][200],dis[200],vis[200];
  13. void dijkstra()
  14. {
  15.     memset(vis,0,sizeof(vis));
  16.     for(int i=1;i<=t;i++)
  17.     dis[i]=ma[1][i];
  18.     dis[1]=0;
  19.     vis[1]=1;
  20.     for(int i=1;i<=t;i++)
  21.     {
  22.         int mm=inf,mk=-1;
  23.         for(int j=1;j<=t;j++)
  24.         {
  25.             if(mm>dis[j]&&!vis[j])
  26.             {
  27.                 mm=dis[j];
  28.                 mk=j;
  29.             }
  30.         }
  31.         if(mk==-1)
  32.         break;
  33.         vis[mk]=1;
  34.         for(int j=1;j<=t;j++)
  35.         {
  36.             if(dis[j]>dis[mk]+ma[mk][j]&&!vis[j])
  37.             dis[j]=dis[mk]+ma[mk][j];
  38.         }
  39.     }
  40. }
  41. int main()
  42. {
  43.     int n,w;
  44.     map<string,int> q;
  45.     while(scanf("%d",&n),n!=-1)
  46.     {
  47.         memset(ma,inf,sizeof(ma));
  48.          scanf("%s%s",start,endd);
  49.          q.clear();
  50.          q[start]=1;
  51.          q[endd]=2;
  52.          t=3;
  53.          for(int i=0;i<n;i++)
  54.          {
  55.             scanf("%s%s%d",s,e,&w);
  56.             if(!q[s])
  57.             q[s]=t++;
  58.             if(!q[e])
  59.             q[e]=t++;
  60.             if(ma[q[s]][q[e]]>w)
  61.             ma[q[e]][q[s]]=ma[q[s]][q[e]]=w;
  62.          }
  63.          if(strcmp(start,endd)==0)
  64.          {
  65.             printf("0\n");
  66.             continue;
  67.          }
  68.          dijkstra();
  69.          if(dis[2]==inf)
  70.          printf("-1\n");
  71.          else
  72.          printf("%d\n",dis[2]);
  73.     }
  74.     return 0;
  75. }

F - Pearls in a Row
题意：

  1. 一个长度为n (1 ≤ n ≤ 3·105)的字符串，从中截取一段，如果这一段中有两个相同的数字，则为一个好串，求出有多少个这样的子串和这个子串的左右端点

解题思路：

  1. 直接将序列中出现的点标记为1，然后如果下一次出现的话，就记录一下左右端点，并将子串数目加1，加标记的1取消，继续遍历此序列

代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <map>
  8. using namespace std;
  9. map<int,int> mm;
  10. int a[350000];
  11. struct Node
  12. {
  13.     int x,y;
  14. }rang[200005];
  15. int main()
  16. {
  17.     int n;
  18.     scanf("%d",&n);
  19.     for(int i=1;i<=n;i++)
  20.     {
  21.         scanf("%d",&a[i]);
  22.     }
  23.     int ll=0,num=0;
  24.     for(int i=1;i<=n;i++)
  25.     {
  26.         if(mm[a[i]]==1)
  27.         {
  28.             mm.clear();
  29.             num++;
  30.             rang[num].x=ll+1;
  31.             rang[num].y=i;
  32.             ll=i;
  33.         }else
  34.         {
  35.             mm[a[i]]=1;
  36.         }
  37.     }
  38.     if(num==0)
  39.     printf("-1\n");
  40.     else
  41.     {
  42.         cout<<num<<endl;
  43.         for(int i=1;i<num;i++)
  44.         {
  45.             printf("%d %d\n",rang[i].x,rang[i].y);
  46.         }
  47.         printf("%d %d\n",rang[num].x,n);
  48.     }
  49.     return 0;
  50. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注