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

STL

题目链接

A - Moo University - Financial Aid

题意

现在有c个人，要资助n个人，一共只有f元可以资助
每个人都有一个考核分数和要求资助资金
问如何资助才能使得c个人的中位数最大
输出最大中位数
输入保证c为奇数，1 <= c <= n <= 1e5,c <= 19,999 , 0 < f < 2e9\

思路

从高分开始枚举每一个数作为中位数是否可以，如果可以直接结束循环，当前为最大中位数

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e5 + 7;
typedef long long LL;
LL n,c,f,ans;
LL begin[N],rightstu[N];

struct st{
    LL score , need;
    bool operator < (const st &a) const{
        return need < a.need;
    }
};

st s[N];

bool cmp( st a , st b ){
    return a.score > b.score;
}

priority_queue<st> pq;

void clear_pq(){
    while( ! pq.empty() )   pq.pop();
}

void solve(){
    sort(s+1,s+(int)c+1,cmp);

    //for(int i = 1 ; i <= c ; i++) printf("%lld and %lld\n",s[i].score , s[i].need);

    clear_pq();
    int now = n / 2, zy = now++ , end = (int)c - zy;
    LL add = 0;
    for( int i = 1 ; i < now ; i++ )    pq.push(s[i]) , add += s[i].need;
    for( int i = now; i <= end ; i++ ){
        while( pq.size() > zy ){
            st d = pq.top();
            add -= d.need;
            pq.pop();
        }
        begin[i] = add;
        pq.push(s[i]);
        add += s[i].need;               
    }
    clear_pq();
    add = 0;
    for( int i = (int)c ; i > end ; i-- )   pq.push(s[i]) , add += s[i].need;
    for( int i = end ; i >= now ; i-- ){
        while( pq.size() > zy ){
            st d = pq.top();
            add -= d.need;
            pq.pop();
        }
        rightstu[i] = add;
        pq.push(s[i]);
        add += s[i].need;
    }

    //for(int i = 1 ; i <= c ; i++) printf("%6lld",begin[i]);printf("\n");
    //for(int i = 1 ; i <= c ; i++) printf("%6lld",rightstu[i]);printf("\n");


    for( int i = now ; i <= end ; i++ ){
        if( s[i].need + begin[i] + rightstu[i] <= f ){
            ans = s[i].score;
            return;
        }
    }
    ans = -1;
}

int main(){
    while( scanf("%lld%lld%lld",&n,&c,&f) != EOF && n ){
        ans = -1;
        for(int i = 1 ; i <= c ; i++)   scanf("%lld%lld",&s[i].score,&s[i].need);
        solve();
        printf("%lld\n",ans);
    }
    return 0;
}

B - Sockets

题意

有n台电脑和m个电源适配器
每台电脑需要一种电压值的电源适配器
每个电源适配器都有自己的电压值
可以用一个降压器使得电源适配器的电压下降一半（向上取整）
一个电源适配器可以用多个降压器
问需要多少个电源适配器使得尽可能多的电脑能够拥有合适的电源适配器

思路

暴力匹配即可
每一次都对当前的电源适配器匹配电脑，匹配上的直接匹配
匹配完一轮后所有电源适配器都下降一半，再匹配一次
直到最大电源适配器的值到达1即结束匹配

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
using namespace std;
const int N = 2e5 + 7;
typedef long long LL;
int n,m;

struct comp{
    int val;
    int we;
    int can;
    int count;
    bool operator < (const comp & a){
        return val < a.val;
    }
};

comp c[N] , s[N];

bool cmp1( comp a , comp b ){
    return a.val < b.val;
}

bool cmp2( comp a , comp b ){
    return a.we < b.we;
}

map<int,vector<int> > mp;

int find_tp_in_c(int x , int w){
    for( int i = w - 1; i >= 0 && c[i].val == x; i-- )  if( c[i].can == -1 )    return i;
    for( int i = w + 1; i < n && c[i].val == x; i++ )   if( c[i].can == -1 )    return i;
}

int find_in_c(int x){
    int begin = 0 , end = n-1 , mid = (begin + end) / 2;
    while( mid > begin ){
        if( c[mid].val == x ){
            if( c[mid].can != -1 )  return find_tp_in_c(x,mid);
            return mid;
        }
        if( c[mid].val > x )    end = mid-1;
        else    begin = mid+1;
        mid = (begin+end)/2;
    }
    if( c[begin].val == x && c[begin].can == -1 )   return begin;
    if( c[end].val == x && c[end].can == -1 )   return end;
    return -1;
}

void solve(){
    for( int i = 0 ; i < m ; i++ ){
        for( int k = 0 ; k < 31 ; k++ ){
            if( mp[s[i].val].size() ){
                int t = mp[s[i].val].back();

                if( c[t].val == s[i].val && c[t].can == -1 ){
                    s[i].can = c[t].we;
                    c[t].can = s[i].we;
                    s[i].count = k;
                    mp[s[i].val].pop_back();
                    break;
                }
            }
            ++s[i].val /= 2;
        }
    }
}


void printf_ans(){
    sort(s,s+m,cmp2);
    int cans = 0, spcount = 0;
    for( int i = 0 ; i < n ; i++ ){
        if( c[i].can == -1 ){
            c[i].can = 0;
        }
        else    cans++;
    }
    for( int i = 0 ; i < m ; i++ ){
        if( s[i].can != -1 ){
            spcount += s[i].count;
        }
        else{
            s[i].count = 0;
        }
    }
    printf("%d %d\n",cans,spcount);
    printf("%d",s[0].count);
    for( int i = 1 ; i < m ; i++ )  printf(" %d",s[i].count);printf("\n");
    printf("%d",c[0].can);
    for( int i = 1 ; i < n ; i++ )  printf(" %d",c[i].can);printf("\n");
}

int main(){
    while( scanf("%d%d",&n,&m) != EOF && n ){
        for(int i = 0 ; i < n ; i++)    scanf("%d",&c[i].val) , c[i].we = i+1 , c[i].can = -1 , mp[c[i].val].push_back(i) , c[i].count = 0;
        for(int i = 0 ; i < m ; i++)    scanf("%d",&s[i].val) , s[i].we = i+1 , s[i].can = -1 , s[i].count = 0;sort(s,s+m,cmp1);
        solve();
        printf_ans();
    }
    return 0;
}

C - HDU Today

题意

中文题诶，不用讲吧

思路

这居然是无向图，当成有向图wa了好久。。。
Dijkstra算法模板题，直接贴代码（按照紫书写的。。）

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
using namespace std;
const int N = 155;
const int INF = 1e9 + 7;
typedef long long LL;

struct Edge{
    int form, to, dist;
    Edge(int u, int v, int d):form(u),to(v),dist(d){}
};

struct HeapNode{
    int d,u;
    bool operator < (const HeapNode& rhs) const{
        return d > rhs.d;
    }
};

struct Dijkstra{
    int n,m;
    vector<Edge> edges;
    vector<int> G[N];
    bool done[N];
    int d[N];
    int p[N];

    void init(int n){
        this->n = n;
        for(int i = 0 ; i < n ; i++)    G[i].clear();
        edges.clear();
    }

    void AddEdge(int from, int to, int dist){
        edges.push_back(Edge(from,to,dist));
        m = edges.size();
        G[from].push_back(m-1);
    }

    void dijkstra(int s){
        priority_queue<HeapNode> Q;
        while( !Q.empty() ) Q.pop();
        for(int i = 0 ; i < 155 ; i++)  d[i] = INF;
        d[s] = 0;
        memset(done,false,sizeof(done));
        Q.push((HeapNode){0,s});
        while( !Q.empty() ){
            HeapNode x = Q.top();Q.pop();
            int u = x.u;
            if( done[u] )   continue;
            done[u] = true;
            for( int i = 0 ; i < G[u].size() ; i++ ){
                Edge& e = edges[G[u][i]];
                if( d[e.to] > d[u] + e.dist ){
                    d[e.to] = d[u] + e.dist;
                    p[e.to] = G[u][i];
                    Q.push((HeapNode){d[e.to],e.to});
                }
            }
        }
    }
};

map<string,int> mp;
Dijkstra ans;
int n;

int main(){
    string now,to,st,en;
    while( scanf("%d",&n) != EOF && n != -1 ){
        mp.clear(); 
        ans.init(155);
        cin>>st>>en;
        int top = 1;
        mp[st] = top++;
        mp[en] = top++;
        int dist;
        for( int i = 0 ; i < n ; i++ ){
            cin>>now>>to;
            scanf("%d",&dist);
            if( mp.find(now) == mp.end() )  mp[now] = top++;
            if( mp.find(to) == mp.end() )   mp[to] = top++;
            /*cout<<now<<" "<<to<<" "<<dist<<endl;
            printf("form = %d , to = %d , dist = %d\n",form,to1,dist);//*/
            ans.AddEdge(mp[now],mp[to],dist);
            ans.AddEdge(mp[to],mp[now],dist);
        }
        ans.dijkstra(mp[st]);
        printf("%d\n",ans.d[mp[en]] == INF ? -1 : ans.d[mp[en]]);
    }
    return 0;
}

D - Music in Car

题意

有n首歌，每首歌都有自己的播放时间和愉悦值
现在可以听k分钟，但是因为SaSha有超级VIP
所以他可以选择最多w首歌，使得这些歌时间减半（愉悦值不变）
这些歌必须连续听，不能跳着听（选择的歌必须为序列中的连续子序列）
选择w首歌减半可以在选择序列中选择任意的w首歌进行减半，无限制
问获得的最大愉悦值为多少？

思路

看了下题解，这题可以用set来维护
首先用s1表示不减半的歌曲，s2表示减半的歌曲
则按序列顺序便利一次
如果当前s2中没有w首歌，则把歌放入s2中
否则当前歌就与s2中时间最短的歌相比，如果当前歌的时间长于s2中最短的歌，则当前的歌放入s2中，并且把s2中时间最短的歌放入s1中
如果当前的时间限制超出k就先更新当前最大愉悦值并弹出最前面的那首歌
如果弹出的是s2中的歌曲，那么需要将s1中时间最长的压入s2

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int N = 2e5+7;
const int INF = 1e8 + 7;
typedef long long LL;

struct node{
    int val,min;
    node(int u,int v):val(u),min(v){}
    bool operator < (const node&rhs) const{
        return val == rhs.val ? min < rhs.min : val < rhs.val;
    }
};

int p[N] , q[N] , nowmin = 0;
set<node> s1,s2;

void s_push(bool is_one , int val , int min){
    if( is_one ){
        s1.insert((node){val,min});
        nowmin += val;
    }else{
        s2.insert((node){val,min});
        nowmin += (val+1)/2;
    }
}

void s_del(bool is_one, int val , int min){
    if( is_one ){
        s1.erase((node){val,min});
        nowmin -= val;
    }else{
        s2.erase((node){val,min});
        nowmin -= (val+1)/2;
    }
}

void s_pop(int x){
    if( s1.find((node){q[x],x}) != s1.end() )   s_del(true,q[x],x);
    else{
        s_del(false,q[x],x);
        if( s1.size() > 0 ){
            node tmp = *(--s1.end());
            s_del(true,tmp.val,tmp.min);
            s_push(false,tmp.val,tmp.min);
        }
    }
}

int main(){
    int n,w,k;
    int ans = 0,rans = 0,st = 1,top = 0;
    scanf("%d%d%d",&n,&w,&k);
    for(int i = 1; i <= n ; i++)    scanf("%d",p+i);
    for(int i = 1; i <= n ; i++)    scanf("%d",q+i);
    while( st <= n ){
        while( nowmin <= k ){
            top++;
            if( top > n )   break;
            if( s2.size() < w ){
                s_push(false,q[top],top);
            }else{
                node tmp = *s2.begin();
                if( tmp.val < q[top] ){
                    s_del(false,tmp.val,tmp.min);
                    s_push(true,tmp.val,tmp.min);
                    s_push(false,q[top],top);
                }else   s_push(true,q[top],top);
            }
            if( nowmin <= k )   ans += p[top];
            else{
                s_pop(top);
                top--;
                break;
            }
            rans = max(rans,ans);
        }
        s_pop(st);
        ans -= p[st];
        st++;
    }
    printf("%d\n",rans);
    return 0;
} 

E - Leaving Auction

题意

有一个物品拍卖记录
里面记录了所有人的出价记录
这时候有人向拍卖场提出了q次查询
每次查询都询问将本次拍卖记录中的ai个人除去后最后拍卖者与拍卖价格为多少
在删除ai个人后还应该删除所有自己与自己喊价的记录

思路

用set记录所有人的最高出价，然后每次查询现在其中删除需要删除的人，查询完毕后再放回set中
每次查询有三种情况
set空出0 0
set为1出唯一拍卖者与其第一次出价
set大于1则出最高出价者高于第二最高出价者最高出价的最低出价

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int N = 2e5+7;
const int INF = 1e8 + 7;
typedef long long LL;

set<pair<int,int> > s;
vector<int> v[N];
bool vis[N];
int del[N],mx[N];

int main(){ 
    int n,a,b;
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i++)   vis[i] = 0 , v[i].clear() , mx[i] = 0;
    for(int i = 0 ; i < n ;i++){
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        vis[a] = true;
        mx[a] = max(mx[a],b);
    }
    for(int i = 1 ; i <= n ; i++)
        if( vis[i] )    s.insert({mx[i],i});
    int q,p;
    scanf("%d",&q);
    while( q-- ){       
        scanf("%d",&p);
        for(int i = 0 ; i < p ; i++){
            scanf("%d",del+i);
            if( vis[del[i]] )   s.erase({mx[del[i]],del[i]});
        }

        if( s.size() == 0 ){
            printf("0 0\n");
        }else if( s.size() == 1 ){
            printf("%d %d\n",s.begin()->second,*(v[s.begin()->second].begin()));
        }else{
            auto no1 = s.end(), no2 = s.end();
            no2--;no2--;
            no1--;
            int now_max = no2->first;
            int no1_id = no1->second;
            auto ans = upper_bound(v[no1_id].begin(),v[no1_id].end(),now_max);
            printf("%d %d\n",no1_id,*ans);
        }

        for(int i = 0 ; i < p ; i++)
            if( vis[del[i]] )   s.insert({mx[del[i]],del[i]});      
    }


    return 0;
}

F - Pearls in a Row

题意

有一个序列
你要在序列中找到尽可能多的子序列使得每个子序列中至少有一对数字相同
所有子序列应该覆盖整个序列，且无重叠

思路

贪心，遇到一对匹配马上匹配时有最优解，此时注意子序列将所有序列覆盖即可

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int N = 3e5+7;
const int INF = 1e8 + 7;
typedef long long LL;

map<int,int> m;
int p[N], ansl[N],ansr[N];

int main(){
    int n,now = 1,k = 0;
    m.clear();
    memset(p,0,sizeof(p));
    memset(ansl,0,sizeof(ansl));
    memset(ansr,0,sizeof(ansr));
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i++){
        scanf("%d",p+i);
        if( m.find(p[i]) != m.end() ){
            ansl[k] = now;
            ansr[k++] = i;
            now = i+1;
            m.clear();
        }else
            m[p[i]] = 1;
    }
    ansr[k-1] = n;
    if( k ) printf("%d\n",k);
    else    printf("-1\n");
    for(int i = 0 ; i < k ; i++)
        printf("%d %d\n",ansl[i],ansr[i]);
    return 0;
}