DQS DQS

HIT Summer Training Day10 set|map|bitset

in set&&map,bitset,算法,STL,模拟赛read (146) 文章转载请注明来源!

A题WA4,可能是因为智商低吧……
超级困的时候打比赛就是不太好……


A : codeforces - 275C

给n个互不相同的数,问最多选出多少个数使其中不存在两个数x和y,使得y=kx。

对于一个数x,不断枚举它的k倍,直到不存在为止。这些数形成了一个链,这条链上相邻两个点只能选一个,所以最多选(len+1)/2个。

注意k=1时答案是n。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int n,m;
LL a[SZ],k,sz[SZ];
bool use[SZ],vis[SZ];

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

map<LL,int> mp;

int main()
{
    n = read(),k = read();
    for(int i = 1;i <= n;i ++) a[i] = read();
    if(k == 1) { cout << n << endl; return 0; }
    int ans = 0;
    sort(a + 1,a + 1 + n,cmp);
    for(int i = 1;i <= n;i ++) mp[a[i]] = i;

    for(int i = 1;i <= n;i ++)
    {
        if(use[i]) continue;
        use[i] = 1;
        LL x = a[i];
        int t = 1;
        while(x % k == 0 && mp[x / k])
            t ++,use[mp[x / k]] = 1,x /= k;
        //cout << a[i] << " " << t << endl;
        ans += t + 1 >> 1;
    }
    printf("%d\n",ans);
    return 0;
}


B : hdu - 4585

找个前驱和后继。set练习题。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int n,m;

struct haha
{
    int id,v;
};

bool operator <(haha a,haha b) { return a.v < b.v; }

set<haha> s;

int main()
{
    while(scanf("%d",&n) && n)
    {
        s.clear();
        s.insert((haha){1,1000000000});
        for(int i = 1;i <= n;i ++)
        {
            int id = read(),v = read();
            set<haha> :: iterator suf = s.lower_bound((haha){id,v});
            set<haha> :: iterator pre = suf; pre --;
            if(suf == s.begin())
            {
                printf("%d %d\n",id,suf -> id);
                s.insert((haha){id,v});
            }
            else
            {
                int a = abs(suf -> v - v),b = abs(pre -> v - v);
                int ans;
                if(a < b) ans = suf -> id;
                if(a > b) ans = pre -> id;
                if(a == b) ans = pre -> id;
                printf("%d %d\n",id,ans);
                s.insert((haha){id,v});
            }
        }
    }
    return 0;
}


C : hdu - 1387

给一些team,每个team里有至多1k人。这些人要排队,如果他看到有自己队的人在排队,那么就排到自己队的最后的队员后面,否则就排到整个队列后面。给一些人的入队和出队,对每次出队输出人的编号。

对每个team开个双端队列,每个人附一个权值。每一队的第一个人来排队的权值为队尾权值+1k,用set维护队列。出队时删除set队头,对当前team的queue弹出。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int n,m;

struct haha
{
    int id,v;
};

bool operator <(haha a,haha b) { return a.v < b.v; }

set<haha> s;
deque<haha> q[SZ];
map<int,int> mp;

int Tcnt = 0;

int main()
{
    int cc = 0;
    while(scanf("%d",&n) && n)
    {
        mp.clear();
        for(int i = 1;i <= n;i ++) q[i].clear();
        s.clear();
        for(int i = 1;i <= n;i ++)
        {
            int k = read(),x;
            while(k --)
                x = read(),mp[x] = i;
        }
        char str[20];
        printf("Scenario #%d\n",++ cc);
        while(scanf("%s",str) && str[0] != 'S')
        {
            if(str[0] == 'E')
            {
                int x = read(),tem = mp[x];
                if(q[tem].size()) //有队友
                {
                    int val = q[tem].back().v + 1;
                    s.insert((haha){x,val});
                    q[tem].push_back((haha){x,val});
                }
                else //无队友
                {
                    if(s.empty())
                    {
                        int val = 1;
                        s.insert((haha){x,val});
                        q[tem].push_back((haha){x,val});
                    }
                    else
                    {
                        set<haha> :: iterator it = s.end(); it --;
                        int val = it -> v + 1000;
                        s.insert((haha){x,val});
                        q[tem].push_back((haha){x,val});
                    }
                }
            }
            else
            {
                set<haha> :: iterator it = s.begin();
                printf("%d\n",it -> id);
                int tem = mp[it -> id];
                q[tem].pop_front();
                s.erase(it);
            }
        }
        puts("");
    }
    return 0;
}


D : hdu - 5818

给两个栈A和B,对这两个栈进行push和pop操作。一个新操作是merge:将A和B合并,元素按当时插入的时间戳排序。求每次pop的元素。

开两个set,每次merge时启发式合并,如果需要就改变一下A和B的指针。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 100010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int n,m;

struct haha
{
    int id,v;
};

bool operator <(haha a,haha b) { return a.v < b.v; }

set<haha> s[2];


int main()
{
    int cc = 0;
    while(scanf("%d",&n) && n)
    {
        int pa = 0,pb = 1;
        s[0].clear(); s[1].clear();
        printf("Case #%d:\n",++ cc);
        for(int i = 1;i <= n;i ++)
        {
            char str[10],a[10],b[10];
            int d;
            scanf("%s",str);
            if(str[1] == 'u') //push
            {
                scanf("%s%d",a,&d);
                if(a[0] == 'A') s[pa].insert((haha){d,i});
                else s[pb].insert((haha){d,i});
            }
            if(str[1] == 'o') //pop
            {
                scanf("%s",a);
                if(a[0] == 'A')
                {
                    set<haha> :: iterator it = s[pa].end(); it --;
                    printf("%d\n",it -> id);
                    s[pa].erase(it);
                }
                else
                {
                    set<haha> :: iterator it = s[pb].end(); it --;
                    printf("%d\n",it -> id);
                    s[pb].erase(it);
                }
            }
            if(str[1] == 'e') //merge
            {
                scanf("%s%s",a,b);
                if(a[0] == 'A')
                {
                    if(s[pa].size() < s[pb].size()) swap(pa,pb);
                    while(s[pb].size())
                    {
                        set<haha> :: iterator it = s[pb].begin();
                        s[pa].insert((haha){it -> id,it -> v});
                        s[pb].erase(it);
                    }
                }
                if(a[0] == 'B')
                {
                    if(s[pb].size() < s[pa].size()) swap(pa,pb);
                    while(s[pa].size())
                    {
                        set<haha> :: iterator it = s[pa].begin();
                        s[pb].insert((haha){it -> id,it -> v});
                        s[pa].erase(it);
                    }
                }
            }
        }

    }
    return 0;
}


E : poj - 2352

做过了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mem(a,t) memset(a,t,sizeof(a))
using namespace std;
 
typedef long long LL;
const int SZ = 300010;
const int INF = 1000000010;
 
int n,m;
 
int bit[SZ];
 
int ask(int x)
{
    int ans = 0;
    for(int j = x;j > 0;j -= j & -j)
        ans += bit[j];
    return ans;
}
 
void change(int x,int d)
{
    for(int j = x;j <= 50000;j += j & -j)
        bit[j] += d;
}
 
struct node
{
    int x,y;
}l[SZ];
 
bool cmp(node a,node b)
{
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
 
int ans[SZ];
 
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
        scanf("%d%d",&l[i].x,&l[i].y),l[i].x ++,l[i].y ++;
    sort(l + 1,l + 1 + n,cmp);
    for(int i = 1;i <= n;i ++)
    {
        int x = l[i].y,lev = ask(l[i].y);
        ans[lev] ++;
        change(l[i].y,1);
    }
    for(int i = 0;i <= n - 1;i ++)
        printf("%d\n",ans[i]);
    return 0;
}

F : hdu - 4268

Alice和Bob有一些牌,如果A的牌的长和宽都大于等于B的牌则可以覆盖,一张牌只可以用一次。问A最多覆盖B多少牌。

对每张牌都找一下它刚好能覆盖的那张……sort一下搞一搞就行了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define fir first
#define sec second
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int n,m;

pair<int,int> A[SZ],B[SZ];

multiset<int> s;

int main()
{
    int T = read();
    while(T --)
    {
        s.clear();
        n = read();
        for(int i = 1;i <= n;i ++)
            scanf("%d%d",&A[i].fir,&A[i].sec);
        for(int i = 1;i <= n;i ++)
            scanf("%d%d",&B[i].fir,&B[i].sec);
        sort(A + 1,A + 1 + n);
        sort(B + 1,B + 1 + n);
        s.insert(-INF);
        int ans = 0;
        for(int i = 1,j = 1;i <= n;i ++) //i:A j:B
        {
            while(j <= n && B[j].fir <= A[i].fir)
                s.insert(B[j].sec),j ++;
            set<int> :: iterator it = s.upper_bound(A[i].sec); it --;
            if(*it != -INF && *it <= A[i].sec) s.erase(it),ans ++;
        }
        printf("%d\n",ans);
    }
    return 0;
}


G : hdu - 6085

给5w个$a_i$和$b_i$还有$k_i$,$a_i,b_i,k_i<=5w$问对于每一个$k$,有多少对$(i,j)$满足$a_i\mod b_j=k$,答案模2。

转化为$(a_i-k)\mod b_j=0$,这样就变成每次询问一个k,问所有的$a_i$减去k后有多少个数是$b_j$的倍数。

于是记一个bitset为A,每个$a_i$位记为1,对于每个$b_j$,开个bitset为B将其从0开始的倍数全flip(因为答案只要求模2)。将A右移k位即为把每个$a_i$减去k,然后如果A>>k某一位为1,那么累加B的那一位,可以用与运算然后用.count()计数。

有一个小bug:如果a=5,b=2,k=3,这样会记一个数。但这时是不能计数的。原因是这时k大于b。于是要把k和b从大到小排序,对于一个k,把大于这个k的B加入bitset里,这样就可以了。

枚举b的倍数的复杂度是$\sum \frac{n}{b_i}$,这是一个调和级数,复杂度是$O(nlogn)$,所以没有问题。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 50000;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

bitset<SZ + 10> A,B;
int a[SZ],b[SZ],c[SZ],ans[SZ];

struct haha
{
    int k,id;
}l[SZ];

bool cmp(int a,int b) { return a > b; }
bool cmp2(haha a,haha b) { return a.k > b.k; }

int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
        A.reset();
        B.reset();
        int n = read(),m = read(),q = read();
        int maxn = 0;
        for(int i = 1;i <= n;i ++)
            a[i] = read(),A.set(a[i]),maxn = max(maxn,a[i]);
        for(int i = 1;i <= m;i ++)
            b[i] = read();

        sort(b + 1,b + 1 + m,cmp);

        for(int i = 1,j = 1;i <= q;i ++)
            c[i] = read(),l[i] = (haha){c[i],i};
        sort(l + 1,l + 1 + q,cmp2);

        for(int i = 1,j = 1;i <= q;i ++)
        {
            int k = l[i].k;
            while(j <= m && b[j] > k)
            {
                for(int k = 0;k <= maxn;k += b[j])
                    B.flip(k);
                j ++;
            }
            ans[l[i].id] = (A & (B << k)).count() & 1;
        }
        for(int i = 1;i <= q;i ++)
            printf("%d\n",ans[i]);
    }
    return 0;
}

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

set&&mapbitset算法STL模拟赛
最后由DQS修改于2017-08-11 19:19
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆