STL

一些几乎没用过的STL函数
参考资料:ACM程序设计,曾棕根


UVA12096
很有意思的一道题

#include<iostream>
#include<set>
#include<vector>
#include<map>
#include<stack>
#include<algorithm>
using namespace std;
set<int> si;
stack<int> s;
map<set<int>,int> msi;
vector<set<int> > vs;
int ID(set<int> si){
    if(msi[si] != 0){
        return msi[si];
    }
    else{
        vs.push_back(si);
        msi[si] = vs.size()-1;
        return msi[si];
    }
}
string inp;
int main(){
    int T; cin >> T;
    while(T--){
        si.clear(); msi.clear(); vs.clear();
        while(!s.empty()) s.pop();
        int n; cin >> n;
        for(int i = 0; i < n; i++){
            cin >> inp;
            if(inp[0] == 'P'){
                s.push(ID(set<int>()));
            }
            else if(inp[0] == 'D'){
                s.push(s.top());
            }
            else{
                set<int> x1 = vs[s.top()]; s.pop();
                set<int> x2 = vs[s.top()]; s.pop();
                set<int> x;
                if(inp[0] == 'U'){
                    set_union(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));
                }
                else if(inp[0] == 'I'){
                    set_intersection(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));
                }
                else{
                    x = x2; x.insert(ID(x1));
                }
                s.push(ID(x));
            }
            cout << vs[s.top()].size() << endl;
        }
        cout << "***" << endl;
    }
}

HDU1053
野生版huffman树 31ms//写的极其糟糕
比赛时有点小错误改不过来就没了2000points,心疼1ms
G++无论开多大数组都会迷之越界,C++稳
排版被VS搅乱了就不改回来了

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<queue> 
using namespace std;
const int maxn = 5e5 + 11;
struct treenode {
    char ch;
    int weight;
    int lc, rc, p;
    int id;
    bool operator < (const treenode& b)const {
        return weight>b.weight;
    }
};
struct node {
    int n;
    char ch;
}b[100];
bool cmp(node a, node b) {
    return a.n>b.n;
}
vector<treenode> s;
string str;
priority_queue<treenode> pq;
queue<treenode> q;
string biao[maxn];
string yingshe[100];
int main() {
//    ios::sync_with_stdio(0);
    while (cin>>str) {
        if(str=="END") break; 
        while (!pq.empty()) pq.pop();
        s.clear(); memset(b, 0, sizeof b);
        for (int i = 0; i < 99; i++) b[i].ch = i + 'A';
        for (int i = 0; i < str.length(); i++) {
            b[str[i] - 'A'].n++;
        }
        sort(b, b + 100, cmp);
        int cnt = 0;
        for (int i = 0; i < 100; i++) {
            if (b[i].n>0) {
                cnt++;
            }
            else break;
        }
        for (int i = 0; i < cnt; i++) {
            treenode t;
            t.ch = b[i].ch; t.weight = b[i].n; t.lc = -1; t.rc = -1; t.p = -1; t.id = i;
            s.push_back(t);
            pq.push(t);
        }

        if (pq.size() == 1) {
            printf("%d %d 8.0\n",pq.top().weight*8,pq.top().weight);
//            cout << "8 1 8.0" << endl;
            continue;
        }
        treenode last;
        while (!pq.empty()) {
            treenode x = pq.top();
            last = x; pq.pop();
            if (pq.empty()) break;
            treenode y = pq.top(); pq.pop();
            treenode t;
            t.p = -1; t.lc = x.id; t.rc = y.id;
            t.id = s.size(); t.ch = '['; t.weight = x.weight + y.weight;
            s.push_back(t); s[x.id].p = t.id; s[y.id].p = t.id;
            pq.push(t);
        }
        while (!q.empty()) q.pop();
        q.push(last);
        memset(biao, 0, sizeof biao);
        bool flag = 0;
        while (!q.empty()) {
            treenode t = q.front(); q.pop();
            if (t.lc != -1) {
                q.push(s[t.lc]);
            }
            if (t.rc != -1) {
                q.push(s[t.rc]);
            }
            if (/*t.id==last.id||*/flag == 0) {
                biao[t.id] = "";//root
                flag = 1;
            }
            else {
                biao[t.id] = biao[t.p];
                if (t.id == s[t.p].lc) biao[t.id] += "0";
                else biao[t.id] += "1";
            }
        }
        memset(yingshe, 0, sizeof yingshe);
        for (int i = 0; i < s.size(); i++) {
            if (s[i].ch != '[') {
                yingshe[s[i].ch - 'A'] = biao[i];
            }
        }
        int sum = 0;
        for (int i = 0; i <str.length(); i++) {
            sum += yingshe[str[i] - 'A'].length();
        }
        printf("%d %d %.1lf\n",8 * str.length(),sum,(double)8 * str.length() / sum);
    }
    return 0;
}

别人家的线性表huffman树,只有简单统计功能
UESTC - 204

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+11;
const int INF = 0x3f3f3f3f;
int n,m,now1,now2,ans,x,y;
int a[maxn],b[maxn];
int find(){
    int mmin=INF,flag=0;
    if(now1<n&&a[now1]<mmin){
        mmin=a[now1];
        flag=1;
    }
    if(now2<m&&b[now2]<mmin){
        mmin=b[now2];
        flag=2;
    }
    if(flag==1) now1++;
    if(flag==2) now2++;
    return mmin;
}
int main(){
    while(scanf("%d\n",&n)!=EOF){
        for(int i = 0; i < n; i++){
            scanf("%d",&a[i]);
        }
        if(n==1){printf("%d\n",a[0]);continue;}
        sort(a,a+n);
        now1=0;now2=0;m=0;ans=0;
        for(int i = 0; i < n-1; i++){
            x=find();
            y=find();
            ans+=x+y;
            b[m++]=x+y;
        }
        printf("%d\n",ans);
    }
    return 0;
}

HDU4006
手写最小堆,124ms

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6+11;
int heap[maxn],sz;
void down(int rt){
    int lc,rc;
    while(rt<sz){
        lc=rt<<1,rc=rt<<1|1;
        if(rc<=sz) lc=heap[lc]>heap[rc]?rc:lc;
        if(lc<=sz&&heap[rt]>heap[lc]){
            heap[rt]^=heap[lc];
            heap[lc]^=heap[rt];
            heap[rt]^=heap[lc];
        }
        else return;
        rt=lc;
    }
}
void up(int rt){
    while(rt!=1&&heap[rt]<heap[rt/2]){
        heap[rt]^=heap[rt/2];
        heap[rt/2]^=heap[rt];
        heap[rt]^=heap[rt/2];
        rt>>=1;
    }
}
void push(int k){
    heap[++sz]=k;
    up(sz);
}
void pop(){
    heap[1]=heap[sz--];
    down(1);
}
int main(){
    int n,k,x;char c[100];
    while(scanf("%d%d",&n,&k)!=EOF){
        sz=0;
        for(int i = 0; i < n; i++){
            scanf("%s",c);
            if(c[0]=='I'){
                scanf("%d",&x);
                push(x);
                if(sz>k) pop();
            }
            else printf("%d\n",heap[1]);
        }
    }
    return 0;
}

UVA514
一些逻辑上的编写技巧
先写出最容易想出的,后面的就跟着来了

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+11;
int B[maxn],n,f;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    while(cin>>n){
        if(n==0) break;
        while(1){
            f=0;
            for(int i = 1; i <= n; i++){
                cin>>B[i];
                if(i==1&&B[i]==0){
                    cout<<endl;f=1;break;
                } 
            }
            if(f) break;
            int head=1,rear=1,flag=0;
            stack<int> s; 
            while(rear<=n){
                if(B[rear]==head){
                    head++;rear++;//直接驶入 
                }
                else if(!s.empty()&&B[rear]==s.top()){
                    s.pop();rear++;
                } 
                else if(head<=n){//注意不要加s.empty 
                    s.push(head);head++;
                }
                else{
                    flag=1;break;
                }
            }
            if(flag) cout<<"No"<<endl;
            else cout<<"Yes"<<endl;
        }
    }
    return 0;
} 
如何用set吊打线段树:http://blog.csdn.net/zearot/article/details/44759437
//2017.9.8

标签: 算法, 学习

添加新评论