1、STL应用

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
vector<string> x,y,z,ans;

int main(){
    int a,b,c;
    string s;
    while(cin>>a>>b>>c){
        x.clear(),y.clear(),z.clear(),ans.clear();
        for(int i=0;i<a;i++){
            cin>>s;
            x.push_back(s);
        }
        for(int i=0;i<b;i++){
            cin>>s;
            y.push_back(s);
        }
        for(int i=0;i<c;i++){
            cin>>s;
            z.push_back(s);
        }
        for(int i=0;i<b;i++){//判断第二个字符串在第一个中出现，没在第三个中出现的    
            if(find(x.begin(),x.end(),y[i])!=x.end())
                if(find(z.begin(),z.end(),y[i])==z.end())
                    ans.push_back(y[i]);
        }
        if(!ans.size())
            cout<<"No enemy spy\n";
        else{
            for(int i=0;i<ans.size();i++){
                if(i!=0)
                    cout<<" ";
                cout<<ans[i];
            }
            cout<<endl;
        }
    }
    return 0;
}

#include<iostream>
#include<string>
#include<stack>
using namespace std;

int main(){
    stack<string>backward;//后向栈
    stack<string>forward;//前向栈
    string c;
    string cur="http://www.acm.org/";
    while(cin>>c&&c!="QUIT"){
        if(c=="VISIT"){
            backward.push(cur);
            cin>>cur;
            cout<<cur<<endl;
            while(!forward.empty())//前向栈不为空则清空
                forward.pop(); 
        }else if(c=="BACK"){ 
            if(backward.empty())
                cout<<"Ignored"<<endl;  
            else{
                forward.push(cur);
                cur=backward.top();
                backward.pop();
                cout<<cur<<endl;
            }
        }else{
            if(forward.empty())
                cout<<"Ignored"<<endl;  
            else{
                backward.push(cur);
                cur=forward.top();
                forward.pop();
                cout<<cur<<endl;
            }
        }
    }
    return 0 ;
}

#include<cstdio>
#include<cstring>
#include<queue>
const int maxn=310;
using namespace std;
struct point{
    int x,y;
    int step;
};//到达的点，和需要的步数 
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={1,-1,2,-2,2,-2,1,-1};
//int dir[8][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};
bool vis[maxn][maxn];
int sx,sy,ex,ey,tx,ty,L;

int bfs(){
    if(sx==ex&&sy==ey) return 0;
    memset(vis,false,sizeof(vis));//初始化 
    queue<point>Q;//定义个队列 
    point start,node;
    start.x=sx;
    start.y=sy;
    start.step=0;//队列初始化 
    Q.push(start);//压进队列
    int step,x,y;
    while(!Q.empty()){
        start=Q.front(),Q.pop();//取队列的头元素，同时把这个元素弹出 (队列从后往前进，先进的先出)
        x=start.x;
        y=start.y;
        step=start.step;//把队列头元素的x,y,step取出 
        for(int i=0;i<8;i++){//扩展 
            tx=x+dx[i];
            ty=y+dy[i];
            if(tx==ex&&ty==ey) return step+1;
            if(tx>=0&&tx<L&&ty>=0&&ty<L&&!vis[tx][ty]){
                node.x=tx;
                node.y=ty;
                node.step=step+1;
                Q.push(node);//满足条件的进队列 
                vis[tx][ty]=true;
            }
        }
    }
}

int main(){
    int N;
    scanf("%d",&N);
    while(N--){
        scanf("%d",&L);
        scanf("%d%d",&sx,&sy);
        scanf("%d%d",&ex,&ey);
        printf("%d\n",bfs());
    }
    return 0; 
}

#include<cstdio>
#include<list>
using namespace std;

int main(){
    int T,n;
    list<int> a;
    list<int>::iterator it; 
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        a.clear();
        int k=2;//第一次删喊“2”的 
        for(int i=1;i<=n;i++)
            a.push_back(i);//存每个士兵的编号
        while(a.size()>3){
            int cnt=1;
            for(it=a.begin();it!=a.end();){
                if(cnt++%k==0)//删除喊“k”的士兵 
                    it=a.erase(it);//it指到下一个的地址 
                else
                    it++;//it指到下一位的地址 
            }
            k=(k==2?3:2); 
        }
        for(it=a.begin();it!=a.end();it++){
            if(it!=a.begin()) printf(" "); 
            printf("%d",*it);
        }
        printf("\n");
    }
    return 0;
}

#include<cstdio>
#include<deque>
using namespace std;
const int maxn=15e4+10;
int n,m;
deque<int> d[maxn];

void read(int &x){
    char ch=getchar();x=0;
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++)
            d[i].clear();
        int k,u,v,w;
        while(m--){
            read(k);
            switch(k){
            case 1:
                read(u),read(w),read(v);
                if(w==0)
                    d[u].push_front(v);
                else
                    d[u].push_back(v);
                break;  
            case 2:
                read(u),read(w);
                if(d[u].empty())
                    printf("-1\n");
                else{
                    if(w==0){
                        printf("%d\n",d[u].front());
                        d[u].pop_front();
                    }
                    else{
                        printf("%d\n",d[u].back());
                        d[u].pop_back();
                    }
                }
                break;
            case 3:
                read(u),read(v),read(w);
                if(w)
                    d[u].insert(d[u].end(),d[v].rbegin(),d[v].rend());
                else
                    d[u].insert(d[u].end(),d[v].begin(),d[v].end());
                d[v].clear();
                break;
            }
        }
    }
    return 0;
}

#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int>q1;
priority_queue<int,vector<int>,greater<int> >q2;
int a[30010];

int main(){
    int n,m,x;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        scanf("%d",&a[i]);
    int cnt=1;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        while(cnt<=x){
            if(!q1.empty()&&a[cnt]<q1.top()){
                q2.push(q1.top());
                q1.pop();
                q1.push(a[cnt]);
            }
            else
                q2.push(a[cnt]);
            cnt++;
        }
        printf("%d\n",q2.top());
        q1.push(q2.top());
        q2.pop();
    }
    return 0;
}

#include<cstdio>
#include<bitset>
#include<algorithm>
using namespace std;
const int maxn=10010;
bitset<1010>s[maxn];

int main(){
    int N,Q,num,x,y;
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%d",&num);
        while(num--){
            scanf("%d",&x);
            s[x][i]=1;
        }
    }
    scanf("%d",&Q);
    while(Q--){
        scanf("%d%d",&x,&y);
        if((s[x]&s[y]).count())
            printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

#include<cstdio>
#include<set>
using namespace std;
int n,m,x;
set<int> sum;

int main(){
    while(~scanf("%d%d",&n,&m)){
        sum.clear();
        for(int i=0;i<n;i++){
            scanf("%d",&x);
            sum.insert(x);
        }
        for(int j=0;j<m;j++){
            scanf("%d", &x);
            sum.insert(x);
        }
        for(set<int>::iterator it=sum.begin();it!=sum.end();it++){
            if(it!=sum.begin())
                printf(" ");
            printf("%d",*it);
        }
        printf("\n");
    }
    return 0;
}

#include<cstdio>
#include<vector>
#include<cstring>
#include<set>
using namespace std;
bool vis[10005];
multiset<int>s;
int k;

void del(int p){
    if(s.empty()){
        printf("-1\n");
        return;
    }
    if(p==1){
        if(vis[k++])
            printf("%d\n",*s.begin());
        s.erase(*s.begin());
    }
    else{
        if(vis[k++])
            printf("%d\n",*s.rbegin());
        s.erase(*s.rbegin());
    }
}

int main(){
    char c;
    int m,n,x,p;
    while(~scanf("%d%d",&m,&n)){
        memset(vis,false,sizeof(vis));
        s.clear();
        for(int i=0;i<n;i++){
            scanf("%d",&x);
            vis[x]=true;
        }
        p=1;
        k=1;
        while(scanf("%c",&c)){
            if(c=='e') break;
            if(c=='a'){
                scanf("%d",&x);
                s.insert(x);
            }
            else if(c=='p'){
                scanf("%d",&x);
                p=x;
            }
            else if(c=='r')
                del(p);       
        }
        printf("\n");
    }
    return 0;
}

//1
#include<iostream>
#include<cstdio>
#include<string>
#include<map>
using namespace std;

int main(){
    map<string,int>mp;
    int cnt=0;
    string s;
    while(getline(cin,s)){
        mp[s]++;
        cnt++;
    }
    for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++){
        cout<<it->first<<" ";
        printf("%.4f\n",100.0*(it->second)/cnt);
    }
    return 0;
}

//2
#include<cstdio>
#include<map>
using namespace std;
map<int,int>mp;
map<int,int>::iterator it;

int main(){
    int n,k,p;
    while(scanf("%d",&n)&&n){
        switch(n){
            case 1:
                scanf("%d%d",&k,&p);
                mp[p]=k;//按优先级有序，因此p为键 
                break;
            case 2:
                if(mp.empty()){
                    printf("0\n");
                    break;
                }
                it=--mp.end();
                printf("%d\n",it->second);  
                mp.erase(it);
                break;
            case 3:
                if(mp.empty()){
                    printf("0\n");
                    break;
                }
                it=mp.begin();
                printf("%d\n",it->second);  
                mp.erase(it);
                break;  
        }
    }
    return 0;
}

//3
#include<iostream>
#include<string>
#include<map>
using namespace std;
int T,m,num;
string place,name;

int main(){
    cin>>T;
    while(T--){
        map<string,map<string,int> >mp; //二维map，注意空格！
        cin>>m;
        for(int i=0;i<m;i++){
           cin>>name>>place>>num;
           mp[place][name]+=num;
        }
        map<string,map<string,int> >::iterator iter1;
        map<string,int>::iterator iter2;
        for(iter1=mp.begin();iter1!=mp.end();iter1++){ //第一关键字
            cout<<iter1->first<<endl;
            for(iter2=iter1->second.begin();iter2!=iter1->second.end();iter2++) //第二关键字
                cout<<"   |----"<<iter2->first<<"("<<iter2->second<<")"<<endl;
        }
       if(T) cout<<endl;
    }
    return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+1000;
int a[maxn],n,m;

bool check(int val){
    int cnt=0;
    for(int i=0;i<n;i++)
        cnt+=n-(lower_bound(a,a+n,a[i]+val)-a);
    return cnt>m;
}

int main(){
    while(~scanf("%d",&n)){
        m=n*(n-1)/4;
        int ans=-1;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        int l=0,r=a[n-1]-a[0];
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }
            else
                r=mid-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=10010;
int r[MAXN];
int n,m,x;

int main(){
    int n;
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++)
            scanf("%d",&r[i]);
        int mid=n>>1;
        nth_element(r,r+mid,r+n);//nth_element(a+l,a+k,a+r)求[l,r)之间第k小 
        printf("%d\n",r[mid]);
    }
    return 0;
}

//1
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[300];

int main(){
    int len,i,n;
    while(~scanf("%s",s)){
        len=strlen(s);
        sort(s,s+len);
        printf("%s\n",s);
        while(next_permutation(s,s+len))
            printf("%s\n",s);
    }
    return 0;
}

//2
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int cmp(char a,char b){//'A'<'a'<'B'<'b'<...<'Z'<'z'
    if(tolower(a)!=tolower(b))
        return tolower(a)<tolower(b);
    else
        return a<b;
}
int main(){
    char ch[20];
    int n;
    cin>>n;
    while(n--){
        scanf("%s",ch);
        sort(ch,ch+strlen(ch),cmp);
        do{
            printf("%s\n",ch);
        }while(next_permutation(ch,ch+strlen(ch),cmp));
    }
    return 0;
}