《数据结构与算法》编程练习

2017年7月1日10,9705

数据结构与算法（上）

百练2746:约瑟夫问题

vector模拟操作

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
vector<int> ve;
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
        ve.push_back(i);
    int t=0;
    for(int i=1;i<n;i++)
    {
        t=(t+m-1)%ve.size();
        ve.erase(ve.begin()+t);
    }
    cout<<ve[0]<<endl;
    return 0;
}

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

vector<int> ve;

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)

ve.push_back(i);

int t=0;

for(int i=1;i<n;i++)

{

t=(t+m-1)%ve.size();

ve.erase(ve.begin()+t);

}

cout<<ve[0]<<endl;

return 0;

}

多项式加法

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T,n,a,b;
map<int,int> p;
int main()
{
    T=read();
    while(T--)
    {
        p.clear();
        while(1)
        {
            a=read();b=read();
            if(b<0)break;
            p[b]+=a;
        }
        while(1)
        {
            a=read();b=read();
            if(b<0)break;
            p[b]+=a;
        }
        for(map<int,int>::reverse_iterator i=p.rbegin();i!=p.rend();i++)
            if(i->second)printf("[ %d %d ] ",i->second,i->first);
        puts("");
    }
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T,n,a,b;

map<int,int> p;

int main()

{

T=read();

while(T--)

{

p.clear();

while(1)

{

a=read();b=read();

if(b<0)break;

p[b]+=a;

}

while(1)

{

a=read();b=read();

if(b<0)break;

p[b]+=a;

}

for(map<int,int>::reverse_iterator i=p.rbegin();i!=p.rend();i++)

if(i->second)printf("[ %d %d ] ",i->second,i->first);

puts("");

}

return 0;

}

百练2980:大整数乘法

#include<iostream> 
#include<cstdio> 
#include<cstring> 
using namespace std; 
int main() 
{ 
    char a1[500],b1[500]; 
    int a[500],b[500],c[1000],la,lb,lc,x,i,j; 
    while ((scanf("%s",a1))!=EOF)
    {     
        scanf("%s",b1);   
        memset(a,0,sizeof(a)); 
        memset(b,0,sizeof(b)); 
        memset(c,0,sizeof(c)); 
        la=strlen(a1); 
        lb=strlen(b1); 
        for(i=0;i<la;i++) a[la-i]=a1[i]-48; 
        for(i=0;i<lb;i++) b[lb-i]=b1[i]-48; 
        for(i=1;i<=la;i++)
        {
            x=0;
            for(j=1;j<=lb;j++)
            {
                c[i+j-1]=a[i]*b[j]+x+c[i+j-1];
                x=c[i+j-1]/10;
                c[i+j-1]%=10;
            }
            c[i+lb]=x;
        }
        lc=la+lb;
        while(c[lc]==0&&lc>1)lc--;
        for(i=lc;i>=1;i--) 
            cout<<c[i];
        cout<<endl;
    }
}

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int main()

{

char a1[500],b1[500];

int a[500],b[500],c[1000],la,lb,lc,x,i,j;

while ((scanf("%s",a1))!=EOF)

{

scanf("%s",b1);

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

memset(c,0,sizeof(c));

la=strlen(a1);

lb=strlen(b1);

for(i=0;i<la;i++) a[la-i]=a1[i]-48;

for(i=0;i<lb;i++) b[lb-i]=b1[i]-48;

for(i=1;i<=la;i++)

{

x=0;

for(j=1;j<=lb;j++)

{

c[i+j-1]=a[i]*b[j]+x+c[i+j-1];

x=c[i+j-1]/10;

c[i+j-1]%=10;

}

c[i+lb]=x;

}

lc=la+lb;

while(c[lc]==0&&lc>1)lc--;

for(i=lc;i>=1;i--)

cout<<c[i];

cout<<endl;

}

百练2702:密码翻译

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
string str;
int main()
{
    int T=read();
    while(T--)
    {
        getline(cin,str);
        for(int i=0;i<str.length();i++)
            if(str[i]>='a'&&str[i]<='y')str[i]++;
            else if(str[i]>='A'&&str[i]<='Y')str[i]++;
            else if(str[i]=='z')str[i]='a';
            else if(str[i]=='Z')str[i]='A';
        cout<<str<<endl;
    }
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

string str;

int main()

{

int T=read();

while(T--)

{

getline(cin,str);

for(int i=0;i<str.length();i++)

if(str[i]>='a'&&str[i]<='y')str[i]++;

else if(str[i]>='A'&&str[i]<='Y')str[i]++;

else if(str[i]=='z')str[i]='a';

else if(str[i]=='Z')str[i]='A';

cout<<str<<endl;

}

return 0;

}

百练4077:出栈序列统计

卡特兰数

#include <iostream>
using namespace std;
int main()
{
    int n,f[20]={0};
    cin>>n;
    f[0]=1;f[1]=1;
    for(int i=2;i<=n;i++)
       for(int j=0;j<i;j++)
          f[i]+=f[j]*f[i-j-1];
          cout<<f[n]<<endl;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n,f[20]={0};

cin>>n;

f[0]=1;f[1]=1;

for(int i=2;i<=n;i++)

for(int j=0;j<i;j++)

f[i]+=f[j]*f[i-j-1];

cout<<f[n]<<endl;

return 0;

}

POJ1686.等价表达式(Lazy Math Instructor)

给每个字母一个随机值，对两个式子做表达式计算

用一个数字栈+操作栈来实现

从左往右，将扫到的数字入数字栈，将扫到的操作与操作栈的栈顶对比优先级

如果当前操作优先级高，将其入栈

否则从数字栈中取出两个数字，用栈顶的操作进行运算

优先级次序是右括号和栈内左括号，运算符，未入栈的左括号

#include<map>
#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 10007
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T;
map<char,int>mp;
string a,b;
int getint(char a)
{
    if((a<='Z'&&a>='A')||(a<='z'&&a>='a'))
    {
        if(mp[a]==0)mp[a]=rand()%10007;
        return mp[a];
    }
    else if(a>='0'&&a<='9')
        return a-'0';
    else
    {
        if(a=='(')return -1;
        else if(a==')')return -2;
        else if(a=='(')return -3;
        else return -4;
    }
}
stack<int>num;
stack<char>opt;
void cal()
{
    if(opt.top()=='#')return;
    int b,a;
    b=num.top();num.pop();
    a=num.top();num.pop();
    if(opt.top()=='+')num.push(a+b);
    if(opt.top()=='-')num.push(a-b);
    if(opt.top()=='*')num.push(a*b);
    opt.pop();
}
int sum(string a)
{
    for(int i=0;i<a.size();i++)
    {
        if(a[i]==' ')continue;
        int t=getint(a[i]);
        if(t>=0)num.push(t);
        else
        {
            int pri=-t;
            if(a[i]=='(')pri=inf;
            if(pri<=-getint(opt.top()))cal();
            if(a[i]==')')
            {
                while(opt.top()!='(')cal();
                opt.pop();
            }
            else opt.push(a[i]);
        }
    }
    while(opt.size()!=1)cal();
    return num.top();
}
int main()
{
    opt.push('#');
    T=read();           
    while(T--)
    {
        getline(cin,a);
        getline(cin,b);
        if(sum(a)==sum(b))puts("YES");
        else puts("NO");
    }
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<stack>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define mod 10007

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T;

map<char,int>mp;

string a,b;

int getint(char a)

{

if((a<='Z'&&a>='A')||(a<='z'&&a>='a'))

{

if(mp[a]==0)mp[a]=rand()%10007;

return mp[a];

}

else if(a>='0'&&a<='9')

return a-'0';

else

{

if(a=='(')return -1;

else if(a==')')return -2;

else if(a=='(')return -3;

else return -4;

}

stack<int>num;

stack<char>opt;

void cal()

{

if(opt.top()=='#')return;

int b,a;

b=num.top();num.pop();

a=num.top();num.pop();

if(opt.top()=='+')num.push(a+b);

if(opt.top()=='-')num.push(a-b);

if(opt.top()=='*')num.push(a*b);

opt.pop();

}

int sum(string a)

{

for(int i=0;i<a.size();i++)

{

if(a[i]==' ')continue;

int t=getint(a[i]);

if(t>=0)num.push(t);

else

{

int pri=-t;

if(a[i]=='(')pri=inf;

if(pri<=-getint(opt.top()))cal();

if(a[i]==')')

{

while(opt.top()!='(')cal();

opt.pop();

}

else opt.push(a[i]);

}

while(opt.size()!=1)cal();

return num.top();

}

int main()

{

opt.push('#');

T=read();

while(T--)

{

getline(cin,a);

getline(cin,b);

if(sum(a)==sum(b))puts("YES");

else puts("NO");

}

return 0;

}

百练2121:英语数字转换器

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int read()  
{  
    int x=0,f=1;char ch=getchar();  
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}  
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  
    return x*f;  
}
int ans,tmp,sign=1;
string snum[28]={"zero","one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"};
int num[28]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,30,40,50,60,70,80,90};
string sunit[4]={"negative","hundred","thousand","million"};
int unit[4]={-1,100,1000,1000000};
int solve(int x,string a)
{
    for(int i=0;i<28;i++)
        if(snum[i]==a)return x+num[i];
    if(a=="hundred")return x*100;
    else if(a=="thousand")
        ans+=x*1000,x=0;
    else if(a=="million")
        ans+=x*1000000,x=0;
    else sign=-1;
    return 0;
}
int main()
{
    string a;
    while(cin>>a)
    {
        tmp=solve(tmp,a);
        char ch=getchar();
        if(ch=='\n')
        {
            cout<<sign*(tmp+ans)<<endl;
            tmp=ans=0;sign=1;
        }
    }
    return 0;
}

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<cmath>

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int ans,tmp,sign=1;

string snum[28]={"zero","one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"};

int num[28]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,30,40,50,60,70,80,90};

string sunit[4]={"negative","hundred","thousand","million"};

int unit[4]={-1,100,1000,1000000};

int solve(int x,string a)

{

for(int i=0;i<28;i++)

if(snum[i]==a)return x+num[i];

if(a=="hundred")return x*100;

else if(a=="thousand")

ans+=x*1000,x=0;

else if(a=="million")

ans+=x*1000000,x=0;

else sign=-1;

return 0;

}

int main()

{

string a;

while(cin>>a)

{

tmp=solve(tmp,a);

char ch=getchar();

if(ch=='\n')

{

cout<<sign*(tmp+ans)<<endl;

tmp=ans=0;sign=1;

}

return 0;

}

百练1035:拼写检查

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int read()  
{  
    int x=0,f=1;char ch=getchar();  
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}  
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  
    return x*f;  
}
string a;
vector<string> dic,ans;
bool check(string a,string b)
{
    if(a.length()<b.length())swap(a,b);
    if(a.length()>b.length()+1)return 0;
    if(a.length()==b.length())
    {
        int cnt=0;
        for(int i=0;i<a.length();i++)
            if(a[i]!=b[i])cnt++;
        return (cnt==1);
    }
    else
    {
        for(int i=0,j=0;i<a.length();i++)
        {
            if(a[i]==b[j])j++;
            if(j==b.length())return 1;
        }
    }
    return 0;
}
void solve()
{
    ans.clear();
    for(int i=0;i<dic.size();i++)
    {
        if(check(dic[i],a))ans.push_back(dic[i]);
        if(dic[i]==a)
        {
            cout<<a<<' '<<"is correct"<<endl;
            return;
        }
    }
    cout<<a<<":";
    for(int i=0;i<ans.size();i++)
        cout<<' '<<ans[i];
    cout<<endl;
}
int main()
{
    while(cin>>a)
    {
        if(a=="#")break;
        dic.push_back(a);
    }
    while(cin>>a)
    {
        if(a=="#")break;
        solve();
    }
    return 0;
}

#include<cmath>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

string a;

vector<string> dic,ans;

bool check(string a,string b)

{

if(a.length()<b.length())swap(a,b);

if(a.length()>b.length()+1)return 0;

if(a.length()==b.length())

{

int cnt=0;

for(int i=0;i<a.length();i++)

if(a[i]!=b[i])cnt++;

return (cnt==1);

}

else

{

for(int i=0,j=0;i<a.length();i++)

{

if(a[i]==b[j])j++;

if(j==b.length())return 1;

}

return 0;

}

void solve()

{

ans.clear();

for(int i=0;i<dic.size();i++)

{

if(check(dic[i],a))ans.push_back(dic[i]);

if(dic[i]==a)

{

cout<<a<<' '<<"is correct"<<endl;

return;

}

cout<<a<<":";

for(int i=0;i<ans.size();i++)

cout<<' '<<ans[i];

cout<<endl;

}

int main()

{

while(cin>>a)

{

if(a=="#")break;

dic.push_back(a);

}

while(cin>>a)

{

if(a=="#")break;

solve();

}

return 0;

}

poj1961.前缀中的周期（Period）

kmp求出fail数组后，前i个的重复子串就是i-fail(i)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<queue>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,T,l;
int fail[1000005];
char ch[1000005];
int main()
{
    while(scanf("%d",&n),n)
    {
        T++;
        printf("Test case #%d\n",T);
        scanf("%s",ch+1);
        l=strlen(ch+1);
        int t=0;
        for(int i=2;i<=n;i++)
        {
            while(ch[t+1]!=ch[i]&&t)t=fail[t];
            if(ch[t+1]==ch[i])t++;
            fail[i]=t;
        }
        for(int i=2;i<=n;i++)
        {
            if(fail[i]&&i%(i-fail[i])==0)
                printf("%d %d\n",i,i/(i-fail[i]));
        }
        puts("");
    }
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<queue>

#include<cmath>

#include<vector>

#include<algorithm>

#include<map>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,T,l;

int fail[1000005];

char ch[1000005];

int main()

{

while(scanf("%d",&n),n)

{

T++;

printf("Test case #%d\n",T);

scanf("%s",ch+1);

l=strlen(ch+1);

int t=0;

for(int i=2;i<=n;i++)

{

while(ch[t+1]!=ch[i]&&t)t=fail[t];

if(ch[t+1]==ch[i])t++;

fail[i]=t;

}

for(int i=2;i<=n;i++)

{

if(fail[i]&&i%(i-fail[i])==0)

printf("%d %d\n",i,i/(i-fail[i]));

}

puts("");

}

return 0;

}

由中根序列和后根序列重建二叉树

后根序列的最后一个元素是树根，在中根序列中找出这个根，划分左右子树递归

#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int x,rt,cnt;
int l[100005],r[100005],v[100005];
void insert(int &k,int x)
{
    if(!k)
    {
        k=++cnt;v[k]=x;
        return;
    }
    if(v[k]==x)return;
    if(x<v[k])insert(l[k],x);
    else insert(r[k],x);
}
void dfs(int x)
{
    if(!x)return;
    printf("%d ",v[x]);
    dfs(l[x]);dfs(r[x]);
}
int main()
{
    while(scanf("%d",&x)!=EOF)
        insert(rt,x);
    dfs(rt);
    return 0;
}

#include<queue>

#include<cmath>

#include<stack>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int x,rt,cnt;

int l[100005],r[100005],v[100005];

void insert(int &k,int x)

{

if(!k)

{

k=++cnt;v[k]=x;

return;

}

if(v[k]==x)return;

if(x<v[k])insert(l[k],x);

else insert(r[k],x);

}

void dfs(int x)

{

if(!x)return;

printf("%d ",v[x]);

dfs(l[x]);dfs(r[x]);

}

int main()

{

while(scanf("%d",&x)!=EOF)

insert(rt,x);

dfs(rt);

return 0;

}

实现堆结构

二叉堆模板

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,T;
struct data{
    int size;
    int heap[1000005];
    void swim(int x){
        while(x>1)
        {
            if(heap[x]<heap[x>>1])
                swap(heap[x],heap[x>>1]);
            else break;
            x>>=1;
        }
    }
    void sink(int x){
        while(1)
        {
            int mn=x;
            int l=(x<<1),r=(x<<1|1);
            if(l<=size&&heap[l]<heap[mn])mn=l;
            if(r<=size&&heap[r]<heap[mn])mn=r;
            if(mn!=x)
                swap(heap[mn],heap[x]),x=mn;
            else break;
        }
    }
    void push(int a){
        heap[++size]=a;
        swim(size);
    }
    void pop(){
        heap[1]=heap[size--];
        sink(1);
    }
}q;
int main()
{
    T=read();
    while(T--)
    {
        while(q.size)q.pop();
        n=read();
        for(int i=1;i<=n;i++)
        {
            int opt=read(),x;
            if(opt==1)
            {
                x=read();
                q.push(x);
            }
            else
            {
                printf("%d\n",q.heap[1]);
                q.pop();
            }
        }
    }
    return 0;
}

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,T;

struct data{

int size;

int heap[1000005];

void swim(int x){

while(x>1)

{

if(heap[x]<heap[x>>1])

swap(heap[x],heap[x>>1]);

else break;

x>>=1;

}

void sink(int x){

while(1)

{

int mn=x;

int l=(x<<1),r=(x<<1|1);

if(l<=size&&heap[l]<heap[mn])mn=l;

if(r<=size&&heap[r]<heap[mn])mn=r;

if(mn!=x)

swap(heap[mn],heap[x]),x=mn;

else break;

}

void push(int a){

heap[++size]=a;

swim(size);

}

void pop(){

heap[1]=heap[size--];

sink(1);

}

}q;

int main()

{

T=read();

while(T--)

{

while(q.size)q.pop();

n=read();

for(int i=1;i<=n;i++)

{

int opt=read(),x;

if(opt==1)

{

x=read();

q.push(x);

}

else

{

printf("%d\n",q.heap[1]);

q.pop();

}

return 0;

}

百练4080：Huffman编码树

用小根堆实现哈夫曼树

#include<map>
#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans;
int n;
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read();
        q.push(x);
    }
    while(q.size()!=1)
    {
        int a,b;
        a=q.top();q.pop();
        b=q.top();q.pop();
        ans+=(a+b);
        q.push(a+b);
    }
    cout<<ans;
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<stack>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll ans;

int n;

priority_queue<int,vector<int>,greater<int> >q;

int main()

{

n=read();

for(int i=1;i<=n;i++)

{

int x=read();

q.push(x);

}

while(q.size()!=1)

{

int a,b;

a=q.top();q.pop();

b=q.top();q.pop();

ans+=(a+b);

q.push(a+b);

}

cout<<ans;

return 0;

}

百练4079：二叉搜索树

#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int x,rt,cnt;
int l[100005],r[100005],v[100005];
void insert(int &k,int x)
{
    if(!k)
    {
        k=++cnt;v[k]=x;
        return;
    }
    if(v[k]==x)return;
    if(x<v[k])insert(l[k],x);
    else insert(r[k],x);
}
void dfs(int x)
{
    if(!x)return;
    printf("%d ",v[x]);
    dfs(l[x]);dfs(r[x]);
}
int main()
{
    while(scanf("%d",&x)!=EOF)
        insert(rt,x);
    dfs(rt);
    return 0;
}

#include<queue>

#include<cmath>

#include<stack>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int x,rt,cnt;

int l[100005],r[100005],v[100005];

void insert(int &k,int x)

{

if(!k)

{

k=++cnt;v[k]=x;

return;

}

if(v[k]==x)return;

if(x<v[k])insert(l[k],x);

else insert(r[k],x);

}

void dfs(int x)

{

if(!x)return;

printf("%d ",v[x]);

dfs(l[x]);dfs(r[x]);

}

int main()

{

while(scanf("%d",&x)!=EOF)

insert(rt,x);

dfs(rt);

return 0;

}

表达式•表达式树•表达式求值

#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long
using namespace std;
int n,m;
struct node{
    char c;
    int pos,dep;
    node* ch[2];
    node(){
        ch[0]=ch[1]=NULL;
    }
};
string s;
map<char,int> mp;
int findopt(int l,int r)
{
    int cnt=0,tmp1=0,tmp2=0;
    for(int i=r;i>=l;i--)
    {
        if(s[i]=='(')cnt++;
        if(s[i]==')')cnt--;
        if(cnt!=0)continue;
        if((!tmp1)&&(s[i]=='+'||s[i]=='-'))tmp1=i;
        if((!tmp2)&&(s[i]=='*'||s[i]=='/'))tmp2=i;    
    }
    if(tmp1)return tmp1;
    return tmp2;
}
node* build(int l,int r)
{
    if(l==r)
    {
        node* t=new node;
        t->c=s[l];
        return t;
    }
    node *pre=new node;
    int t=findopt(l,r);
    if(t==0)return build(l+1,r-1);
    pre->c=s[t];
    pre->ch[0]=build(l,t-1);
    pre->ch[1]=build(t+1,r);
    return pre;
}
int mxdep;
void dfs(node *x)
{
    if(x==NULL)return;
    if(x->ch[0])
    {
        x->ch[0]->pos=(x->pos<<1)-1;
        x->ch[0]->dep=x->dep+1;
    }
    if(x->ch[1])
    {
        x->ch[1]->pos=(x->pos<<1);
        x->ch[1]->dep=x->dep+1;
    }
    mxdep=max(mxdep,x->dep);
    dfs(x->ch[0]);dfs(x->ch[1]);
    printf("%c",x->c);
}
char st[105][200005];
void print(node *x)
{
    if(x==NULL)return;
    int dep=mxdep-x->dep+1,pos=(1<<(dep-1))+(1<<dep)*(x->pos-1);
    st[x->dep*2][pos]=x->c;
    if(x->ch[0])st[x->dep*2+1][pos-1]='/';
    if(x->ch[1])st[x->dep*2+1][pos+1]='\\';
    print(x->ch[0]);print(x->ch[1]);
    return;
}
int cal(node *x)
{
    if(mp.count(x->c))return mp[x->c];
    int a=cal(x->ch[0]),b=cal(x->ch[1]);
    if(x->c=='-')return a-b;
    if(x->c=='+')return a+b;
    if(x->c=='*')return a*b;
    if(x->c=='/')return a/b;
    return 0;
}
int main()
{
    cin>>s;
    n=s.length();
    s=" "+s;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        char c;cin>>c;
        cin>>mp[c];
    }
    node *root=build(1,n);
    root->pos=1;
    dfs(root);
    puts("");
    print(root);
    for(int i=0;i<=mxdep*2;i++)
    {
        for(int j=1;j<=200000;j++)
            if(!st[i][j])st[i][j]=' ';
        for(int j=200000;st[i][j]==' ';j--)st[i][j]=0;
        printf("%s\n",st[i]+1);
    }
    printf("%d\n",cal(root));
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

#include<map>

#include<cmath>

#include<queue>

#include<stack>

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

int n,m;

struct node{

char c;

int pos,dep;

node* ch[2];

node(){

ch[0]=ch[1]=NULL;

}

};

string s;

map<char,int> mp;

int findopt(int l,int r)

{

int cnt=0,tmp1=0,tmp2=0;

for(int i=r;i>=l;i--)

{

if(s[i]=='(')cnt++;

if(s[i]==')')cnt--;

if(cnt!=0)continue;

if((!tmp1)&&(s[i]=='+'||s[i]=='-'))tmp1=i;

if((!tmp2)&&(s[i]=='*'||s[i]=='/'))tmp2=i;

}

if(tmp1)return tmp1;

return tmp2;

}

node* build(int l,int r)

{

if(l==r)

{

node* t=new node;

t->c=s[l];

return t;

}

node *pre=new node;

int t=findopt(l,r);

if(t==0)return build(l+1,r-1);

pre->c=s[t];

pre->ch[0]=build(l,t-1);

pre->ch[1]=build(t+1,r);

return pre;

}

int mxdep;

void dfs(node *x)

{

if(x==NULL)return;

if(x->ch[0])

{

x->ch[0]->pos=(x->pos<<1)-1;

x->ch[0]->dep=x->dep+1;

}

if(x->ch[1])

{

x->ch[1]->pos=(x->pos<<1);

x->ch[1]->dep=x->dep+1;

}

mxdep=max(mxdep,x->dep);

dfs(x->ch[0]);dfs(x->ch[1]);

printf("%c",x->c);

}

char st[105][200005];

void print(node *x)

{

if(x==NULL)return;

int dep=mxdep-x->dep+1,pos=(1<<(dep-1))+(1<<dep)*(x->pos-1);

st[x->dep*2][pos]=x->c;

if(x->ch[0])st[x->dep*2+1][pos-1]='/';

if(x->ch[1])st[x->dep*2+1][pos+1]='\\';

print(x->ch[0]);print(x->ch[1]);

return;

}

int cal(node *x)

{

if(mp.count(x->c))return mp[x->c];

int a=cal(x->ch[0]),b=cal(x->ch[1]);

if(x->c=='-')return a-b;

if(x->c=='+')return a+b;

if(x->c=='*')return a*b;

if(x->c=='/')return a/b;

return 0;

}

int main()

{

cin>>s;

n=s.length();

s=" "+s;

cin>>m;

for(int i=1;i<=m;i++)

{

char c;cin>>c;

cin>>mp[c];

}

node *root=build(1,n);

root->pos=1;

dfs(root);

puts("");

print(root);

for(int i=0;i<=mxdep*2;i++)

{

for(int j=1;j<=200000;j++)

if(!st[i][j])st[i][j]=' ';

for(int j=200000;st[i][j]==' ';j--)st[i][j]=0;

printf("%s\n",st[i]+1);

}

printf("%d\n",cal(root));

return 0;

}

森林的带度数层次序列存储

从左往右扫过带度数层次序列，一个度数为x的结点决定之后x个连续结点的父亲

#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T,last,top,cur;
int d[30],st[30],fa[30];
vector<int>e[30];
string a;
void dfs(int x)
{
    for(int i=0;i<e[x].size();i++)
        dfs(e[x][i]);
    printf("%c ",x+'A');
}
int main()
{
    T=read();
    while(T--)
    {
        getline(cin,a);
        while(a[0]<'A'||a[0]>'Z')getline(cin,a);
        top=0;cur=1;
        for(int i=0;i<a.length();i++)
        {
            if(a[i]>='A'&&a[i]<='Z')
            {
                last=a[i]-'A';
                st[++top]=last;
            }
            else if(a[i]!=' ')
                d[last]=d[last]*10+a[i]-'0';
        }   
        for(int i=1,k=1;i<=top;i++)
            for(int j=1;j<=d[st[i]];j++)
                fa[++k]=st[i];
        for(int i=2;i<=top;i++)
            e[fa[i]].push_back(st[i]);
        dfs(st[1]);
    }
    return 0;
}

#include<queue>

#include<cmath>

#include<stack>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T,last,top,cur;

int d[30],st[30],fa[30];

vector<int>e[30];

string a;

void dfs(int x)

{

for(int i=0;i<e[x].size();i++)

dfs(e[x][i]);

printf("%c ",x+'A');

}

int main()

{

T=read();

while(T--)

{

getline(cin,a);

while(a[0]<'A'||a[0]>'Z')getline(cin,a);

top=0;cur=1;

for(int i=0;i<a.length();i++)

{

if(a[i]>='A'&&a[i]<='Z')

{

last=a[i]-'A';

st[++top]=last;

}

else if(a[i]!=' ')

d[last]=d[last]*10+a[i]-'0';

}

for(int i=1,k=1;i<=top;i++)

for(int j=1;j<=d[st[i]];j++)

fa[++k]=st[i];

for(int i=2;i<=top;i++)

e[fa[i]].push_back(st[i]);

dfs(st[1]);

}

return 0;

}

poj1182：食物链（food chain）

带权并查集

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,ans;
int d[50005],fa[50005];
//x=y x->y y->x
int find(int x)
{
	if(x==fa[x])return x;
	int t=fa[x];fa[x]=find(fa[x]);
	d[x]=(d[x]+d[t])%3;
	return fa[x];
}
void un(int x,int y,int f)
{
	int fx=find(x),fy=find(y);
	fa[fx]=fy;
	d[fx]=(d[y]-f-d[x]+3)%3;
}
int main()
{
	n=read();m=read();
	int f,u,v;
	for(int i=1;i<=n;i++)fa[i]=i;
	while(m--)
	{
		f=read(),u=read(),v=read();
		if(u>n||v>n||(f==2&&u==v))ans++;
		else 
		{
			if(find(u)==find(v))
			{
				if(f==1&&d[u]!=d[v])ans++;
				if(f==2&&(d[u]+1)%3!=d[v])ans++;
			}
			else un(u,v,f-1);
		}
	}
	printf("%d\n",ans);
	return 0;
}

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,ans;

int d[50005],fa[50005];

//x=y x->y y->x

int find(int x)

{

if(x==fa[x])return x;

int t=fa[x];fa[x]=find(fa[x]);

d[x]=(d[x]+d[t])%3;

return fa[x];

}

void un(int x,int y,int f)

{

int fx=find(x),fy=find(y);

fa[fx]=fy;

d[fx]=(d[y]-f-d[x]+3)%3;

}

int main()

{

n=read();m=read();

int f,u,v;

for(int i=1;i<=n;i++)fa[i]=i;

while(m--)

{

f=read(),u=read(),v=read();

if(u>n||v>n||(f==2&&u==v))ans++;

else

{

if(find(u)==find(v))

{

if(f==1&&d[u]!=d[v])ans++;

if(f==2&&(d[u]+1)%3!=d[v])ans++;

}

else un(u,v,f-1);

}

printf("%d\n",ans);

return 0;

}

百练4083：我爱北大

floyd求最短路，同时记录最短路上的最后一个结点

#include<map>
#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,q,r;
int dis[105][105],pre[105][105];
string str[105],str1,str2;
map<string,int>mp;
vector<int>ans;
void solve(int p,int q)
{
    ans.push_back(q);
    if(p==q)return;
    q=pre[p][q];
    solve(p,q);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        cin>>str[i];
        mp[str[i]]=i;
    }
    q=read();
    memset(dis,127/3,sizeof(dis));
    for(int i=1;i<=q;i++)
    {
        int x,p1,p2;
        cin>>str1>>str2;x=read();
        p1=mp[str1],p2=mp[str2];
        if(dis[p1][p2]>x)
        {
            dis[p1][p2]=dis[p2][p1]=x;
            pre[p1][p2]=p1;
            pre[p2][p1]=p2;
        }
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dis[i][k]+dis[k][j]<dis[i][j])
                {
                    dis[i][j]=dis[i][k]+dis[k][j];
                    pre[i][j]=pre[k][j];
                }
    r=read();
    while(r--)
    {
        cin>>str1>>str2;
        int p=mp[str1],q=mp[str2];
        ans.clear();
        solve(p,q);
        reverse(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++)
        {
            cout<<str[ans[i]];
            if(i!=ans.size()-1)cout<<"->("<<dis[ans[i]][ans[i+1]]<<")->";
        }
        puts("");
    }
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<stack>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,q,r;

int dis[105][105],pre[105][105];

string str[105],str1,str2;

map<string,int>mp;

vector<int>ans;

void solve(int p,int q)

{

ans.push_back(q);

if(p==q)return;

q=pre[p][q];

solve(p,q);

}

int main()

{

n=read();

for(int i=1;i<=n;i++)

{

cin>>str[i];

mp[str[i]]=i;

}

q=read();

memset(dis,127/3,sizeof(dis));

for(int i=1;i<=q;i++)

{

int x,p1,p2;

cin>>str1>>str2;x=read();

p1=mp[str1],p2=mp[str2];

if(dis[p1][p2]>x)

{

dis[p1][p2]=dis[p2][p1]=x;

pre[p1][p2]=p1;

pre[p2][p1]=p2;

}

for(int k=1;k<=n;k++)

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

if(dis[i][k]+dis[k][j]<dis[i][j])

{

dis[i][j]=dis[i][k]+dis[k][j];

pre[i][j]=pre[k][j];

}

r=read();

while(r--)

{

cin>>str1>>str2;

int p=mp[str1],q=mp[str2];

ans.clear();

solve(p,q);

reverse(ans.begin(),ans.end());

for(int i=0;i<ans.size();i++)

{

cout<<str[ans[i]];

if(i!=ans.size()-1)cout<<"->("<<dis[ans[i]][ans[i+1]]<<")->";

}

puts("");

}

return 0;

}

百练4084：拓扑排序

用小根堆来实现字典序最小的拓扑序

#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int d[100005];
vector<int>e[100005];
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        e[u].push_back(v);
        d[v]++;
    }
    for(int i=1;i<=n;i++)
        if(!d[i])q.push(i);
    while(!q.empty())
    {
        int x=q.top();q.pop();
        printf("v%d ",x);
        for(int i=0;i<e[x].size();i++)
        {
            int y=e[x][i];
            d[y]--;
            if(!d[y])q.push(y);
        }
    }
    return 0;
}

#include<queue>

#include<cmath>

#include<stack>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int d[100005];

vector<int>e[100005];

priority_queue<int,vector<int>,greater<int> >q;

int main()

{

n=read();m=read();

for(int i=1;i<=m;i++)

{

int u=read(),v=read();

e[u].push_back(v);

d[v]++;

}

for(int i=1;i<=n;i++)

if(!d[i])q.push(i);

while(!q.empty())

{

int x=q.top();q.pop();

printf("v%d ",x);

for(int i=0;i<e[x].size();i++)

{

int y=e[x][i];

d[y]--;

if(!d[y])q.push(y);

}

return 0;

}

poj2049：Finding Nemo

建图后01-bfs，由0的边扩展的点放在队首，1的边扩展的点放在队尾

#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long
using namespace std;
int n,m;
int mp[50005][4];
deque<int>q;
int xx[4]={0,1,0,-1},yy[4]={-1,0,1,0};
int dis[205][205],p[205][205],X[50005],Y[50005];
void bfs()
{
    q.push_back(0);
    dis[0][0]=0;
    while(!q.empty())
    {
        int now=q.front();q.pop_front();
        int x=X[now],y=Y[now];
        for(int d=0;d<4;d++)
        {
            int nx=x+xx[d],ny=y+yy[d];
            if(mp[now][d]==inf||nx<0||ny<0||nx>=200||ny>=200)continue;
            if(dis[nx][ny]==-1)
            {
                dis[nx][ny]=dis[x][y]+mp[now][d];
                if(mp[now][d]==0)q.push_front(p[nx][ny]);
                else q.push_back(p[nx][ny]);
            }
        }
    }
}
int main()
{
    int cnt=0;
    for(int i=0;i<=200;i++)
        for(int j=0;j<=199;j++)
        {
            p[i][j]=cnt;
            X[cnt]=i,Y[cnt]=j;cnt++;
        }
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==-1)return 0;
        memset(dis,-1,sizeof(dis));
        memset(mp,0,sizeof(mp));
        int x,y,d,t;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d%d",&x,&y,&d,&t);
            if(d==0)
                for(int j=0;j<t;j++)
                {
                    mp[p[x+j][y]][0]=inf;
                    mp[p[x+j][y-1]][2]=inf;
                }
            else
                for(int j=0;j<t;j++)
                {
                    mp[p[x][y+j]][3]=inf;
                    mp[p[x-1][y+j]][1]=inf;
                }
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&d);
            if(d==0)
            {
                mp[p[x][y]][0]=1;
                mp[p[x][y-1]][2]=1;
            }
            else                
            {
                mp[p[x][y]][3]=1;
                mp[p[x-1][y]][1]=1;
            }    
        }        
        bfs();
        double px,py;
        scanf("%lf%lf",&px,&py);
        if(px<0||py<0||px>199||py>199)puts("0");        
        else printf("%d\n",dis[(int)px][(int)py]);
    }
    return 0;
}

#include<map>

#include<cmath>

#include<queue>

#include<stack>

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

int n,m;

int mp[50005][4];

deque<int>q;

int xx[4]={0,1,0,-1},yy[4]={-1,0,1,0};

int dis[205][205],p[205][205],X[50005],Y[50005];

void bfs()

{

q.push_back(0);

dis[0][0]=0;

while(!q.empty())

{

int now=q.front();q.pop_front();

int x=X[now],y=Y[now];

for(int d=0;d<4;d++)

{

int nx=x+xx[d],ny=y+yy[d];

if(mp[now][d]==inf||nx<0||ny<0||nx>=200||ny>=200)continue;

if(dis[nx][ny]==-1)

{

dis[nx][ny]=dis[x][y]+mp[now][d];

if(mp[now][d]==0)q.push_front(p[nx][ny]);

else q.push_back(p[nx][ny]);

}

int main()

{

int cnt=0;

for(int i=0;i<=200;i++)

for(int j=0;j<=199;j++)

{

p[i][j]=cnt;

X[cnt]=i,Y[cnt]=j;cnt++;

}

while(scanf("%d%d",&n,&m)!=EOF)

{

if(n==-1)return 0;

memset(dis,-1,sizeof(dis));

memset(mp,0,sizeof(mp));

int x,y,d,t;

for(int i=1;i<=n;i++)

{

scanf("%d%d%d%d",&x,&y,&d,&t);

if(d==0)

for(int j=0;j<t;j++)

{

mp[p[x+j][y]][0]=inf;

mp[p[x+j][y-1]][2]=inf;

}

else

for(int j=0;j<t;j++)

{

mp[p[x][y+j]][3]=inf;

mp[p[x-1][y+j]][1]=inf;

}

for(int i=1;i<=m;i++)

{

scanf("%d%d%d",&x,&y,&d);

if(d==0)

{

mp[p[x][y]][0]=1;

mp[p[x][y-1]][2]=1;

}

else

{

mp[p[x][y]][3]=1;

mp[p[x-1][y]][1]=1;

}

bfs();

double px,py;

scanf("%lf%lf",&px,&py);

if(px<0||py<0||px>199||py>199)puts("0");

else printf("%d\n",dis[(int)px][(int)py]);

}

return 0;

}

数据结构与算法（下）

距离排序

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int x[15],y[15],z[15];
struct data{
    int a,b;
    int dis;
    friend bool operator<(data a,data b){
        return a.dis<b.dis;
    }
}a[105];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        x[i]=read(),y[i]=read(),z[i]=read();
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            a[++m].a=i,a[m].b=j;
            a[m].dis=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]);
        }
    for(int i=1;i<=m;i++)
        for(int j=1;j<m;j++)
            if(a[j]<a[j+1])swap(a[j],a[j+1]);
    for(int i=1;i<=m;i++)
        printf("(%d,%d,%d)-(%d,%d,%d)=%.2lf\n",x[a[i].a],y[a[i].a],z[a[i].a],x[a[i].b],y[a[i].b],z[a[i].b],sqrt(a[i].dis));
    return 0;
}

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int x[15],y[15],z[15];

struct data{

int a,b;

int dis;

friend bool operator<(data a,data b){

return a.dis<b.dis;

}

}a[105];

int main()

{

n=read();

for(int i=1;i<=n;i++)

x[i]=read(),y[i]=read(),z[i]=read();

for(int i=1;i<=n;i++)

for(int j=i+1;j<=n;j++)

{

a[++m].a=i,a[m].b=j;

a[m].dis=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]);

}

for(int i=1;i<=m;i++)

for(int j=1;j<m;j++)

if(a[j]<a[j+1])swap(a[j],a[j+1]);

for(int i=1;i<=m;i++)

printf("(%d,%d,%d)-(%d,%d,%d)=%.2lf\n",x[a[i].a],y[a[i].a],z[a[i].a],x[a[i].b],y[a[i].b],z[a[i].b],sqrt(a[i].dis));

return 0;

}

数据筛选

快速选择函数

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,K;
int a[1000005];
int main()
{
    n=read();K=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    nth_element(a+1,a+K,a+n+1);
    printf("%d\n",a[K]);
    return 0;
}

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,K;

int a[1000005];

int main()

{

n=read();K=read();

for(int i=1;i<=n;i++)

a[i]=read();

nth_element(a+1,a+K,a+n+1);

printf("%d\n",a[K]);

return 0;

}

数组取数

对每个数\(a_i\),二分查询\(a_i-T\)，注意\(T=0\)的情况

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,ans;
vector<int>a;
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        int x=read();
        a.push_back(x);
    }
    sort(a.begin(),a.end());
    a.push_back(inf);
    if(m==0)
    {
        for(int i=1;i<a.size()-1;i++)
            if(a[i]==a[i-1]&&a[i]!=a[i+1])
                ans++;
    }
    else 
    {
        a.erase(unique(a.begin(),a.end()),a.end());

        for(int i=0;i<a.size();i++)
        {
            if(*lower_bound(a.begin(),a.end(),a[i]-m)==a[i]-m)
                ans++;
        }
    }
        printf("%d\n",ans);
    return 0;
}

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,ans;

vector<int>a;

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)

{

int x=read();

a.push_back(x);

}

sort(a.begin(),a.end());

a.push_back(inf);

if(m==0)

{

for(int i=1;i<a.size()-1;i++)

if(a[i]==a[i-1]&&a[i]!=a[i+1])

ans++;

}

else

{

a.erase(unique(a.begin(),a.end()),a.end());

for(int i=0;i<a.size();i++)

{

if(*lower_bound(a.begin(),a.end(),a[i]-m)==a[i]-m)

ans++;

}

printf("%d\n",ans);

return 0;

}

牛的选举

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,K;
struct data{
    int a,b,id;
}a[50005];
bool cmp1(data a,data b)
{
    return a.a>b.a;
}
bool cmp2(data a,data b)
{
    return a.b>b.b;
}
int main()
{
    n=read();K=read();
    for(int i=1;i<=n;i++)
        a[i].a=read(),a[i].b=read();
    for(int i=1;i<=n;i++)
        a[i].id=i;
    sort(a+1,a+n+1,cmp1);
    sort(a+1,a+K+1,cmp2);
    printf("%d\n",a[1].id);
    return 0;
}

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,K;

struct data{

int a,b,id;

}a[50005];

bool cmp1(data a,data b)

{

return a.a>b.a;

}

bool cmp2(data a,data b)

{

return a.b>b.b;

}

int main()

{

n=read();K=read();

for(int i=1;i<=n;i++)

a[i].a=read(),a[i].b=read();

for(int i=1;i<=n;i++)

a[i].id=i;

sort(a+1,a+n+1,cmp1);

sort(a+1,a+K+1,cmp2);

printf("%d\n",a[1].id);

return 0;

}

The Peanuts

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T;
int m,n,K;
int ans,cnt;
struct data{
    int x,y,v;
    friend bool operator<(data a,data b){
        return a.v>b.v;
    }
}a[2505];
int dis(int x,int y)
{
    return abs(a[x].x-a[y].x)+abs(a[x].y-a[y].y);
}
int main()
{
    T=read();
    while(T--)
    {
        ans=cnt=0;
        m=read();n=read();K=read();
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
            {
                int x=read();
                if(x!=0)
                {
                    a[++cnt].x=i;a[cnt].y=j;
                    a[cnt].v=x;
                }
            }
        sort(a+1,a+cnt+1);
        a[0].y=a[1].y;
        for(int i=1;i<=cnt;i++)

            if(K-dis(i-1,i)-1-a[i].x>=0)
            {
                ans+=a[i].v;
                K-=dis(i-1,i)+1;
            }
            else break;
        printf("%d\n",ans);
    }
    return 0;
}

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T;

int m,n,K;

int ans,cnt;

struct data{

int x,y,v;

friend bool operator<(data a,data b){

return a.v>b.v;

}

}a[2505];

int dis(int x,int y)

{

return abs(a[x].x-a[y].x)+abs(a[x].y-a[y].y);

}

int main()

{

T=read();

while(T--)

{

ans=cnt=0;

m=read();n=read();K=read();

for(int i=1;i<=m;i++)

for(int j=1;j<=n;j++)

{

int x=read();

if(x!=0)

{

a[++cnt].x=i;a[cnt].y=j;

a[cnt].v=x;

}

sort(a+1,a+cnt+1);

a[0].y=a[1].y;

for(int i=1;i<=cnt;i++)

if(K-dis(i-1,i)-1-a[i].x>=0)

{

ans+=a[i].v;

K-=dis(i-1,i)+1;

}

else break;

printf("%d\n",ans);

}

return 0;

}

DNA排序

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
struct data{
    string str;
    int num;
    friend bool operator<(data a,data b){
        return a.num<b.num;
    }
}a[105];
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].str;
        for(int j=0;j<n;j++)
            for(int k=j+1;k<n;k++)
                if(a[i].str[j]>a[i].str[k])
                    a[i].num++;
    }
    sort(a+1,a+m+1);
    for(int i=1;i<=m;i++)
        cout<<a[i].str<<endl;
    return 0;
}

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

struct data{

string str;

int num;

friend bool operator<(data a,data b){

return a.num<b.num;

}

}a[105];

int main()

{

n=read();m=read();

for(int i=1;i<=m;i++)

{

cin>>a[i].str;

for(int j=0;j<n;j++)

for(int k=j+1;k<n;k++)

if(a[i].str[j]>a[i].str[k])

a[i].num++;

}

sort(a+1,a+m+1);

for(int i=1;i<=m;i++)

cout<<a[i].str<<endl;

return 0;

}

置换选择排序

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int a[100005];
priority_queue<int,vector<int>,greater<int> >q;
vector<int> ve;
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=m;i++)
    {
        int x=read();
        q.push(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!q.empty())
        {
            if(a[i]>q.top())
                q.push(a[i]);
            else ve.push_back(a[i]);
            printf("%d ",q.top());q.pop();
        }
    }
    return 0;
}

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int a[100005];

priority_queue<int,vector<int>,greater<int> >q;

vector<int> ve;

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)a[i]=read();

for(int i=1;i<=m;i++)

{

int x=read();

q.push(x);

}

for(int i=1;i<=n;i++)

{

if(!q.empty())

{

if(a[i]>q.top())

q.push(a[i]);

else ve.push_back(a[i]);

printf("%d ",q.top());q.pop();

}

return 0;

}

败方树

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,cnt,rt;
queue<int>q;
int l[100005],r[100005],fa[100005],lose[100005],win[100005];
int val[100005];
void update(int rt)
{
    int a=l[rt],b=r[rt];
    if(val[win[a]]>val[win[b]])
        lose[rt]=win[a],win[rt]=win[b];
    else lose[rt]=win[b],win[rt]=win[a];
}
int merge(int a,int b)
{
    int rt=++cnt;
    l[rt]=a;r[rt]=b;fa[a]=fa[b]=rt;
    update(rt);
    return rt;
}
void print()
{
    q.push(rt);
    cout<<val[win[rt]]<<' ';
    while(!q.empty())
    {
        int x=q.front();q.pop();
        if(l[x]>n)q.push(l[x]);
        if(r[x]>n)q.push(r[x]);
        printf("%d ",val[lose[x]]);
    }
    puts("");
}
int main()
{
    n=read();m=read();cnt=n;
    for(int i=1;i<=n;i++)val[i]=read();
    for(int i=1;i<=n;i++)win[i]=i,q.push(i);
    while(q.size()!=1)
    {
        int a=q.front();q.pop();
        int b=q.front();q.pop();
        q.push(merge(a,b));
    }
    rt=q.front();q.pop();
    print();
    for(int i=1;i<=m;i++)
    {
        int x=read();x++;
        val[x]=read();
        while(fa[x]!=0)
            x=fa[x],update(x);
        print();
    }
    return 0;
}

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,cnt,rt;

queue<int>q;

int l[100005],r[100005],fa[100005],lose[100005],win[100005];

int val[100005];

void update(int rt)

{

int a=l[rt],b=r[rt];

if(val[win[a]]>val[win[b]])

lose[rt]=win[a],win[rt]=win[b];

else lose[rt]=win[b],win[rt]=win[a];

}

int merge(int a,int b)

{

int rt=++cnt;

l[rt]=a;r[rt]=b;fa[a]=fa[b]=rt;

update(rt);

return rt;

}

void print()

{

q.push(rt);

cout<<val[win[rt]]<<' ';

while(!q.empty())

{

int x=q.front();q.pop();

if(l[x]>n)q.push(l[x]);

if(r[x]>n)q.push(r[x]);

printf("%d ",val[lose[x]]);

}

puts("");

}

int main()

{

n=read();m=read();cnt=n;

for(int i=1;i<=n;i++)val[i]=read();

for(int i=1;i<=n;i++)win[i]=i,q.push(i);

while(q.size()!=1)

{

int a=q.front();q.pop();

int b=q.front();q.pop();

q.push(merge(a,b));

}

rt=q.front();q.pop();

print();

for(int i=1;i<=m;i++)

{

int x=read();x++;

val[x]=read();

while(fa[x]!=0)

x=fa[x],update(x);

print();

}

return 0;

}

词典

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
string str;
map<string,string>mp;
int main()
{
    while(getline(cin,str))
    {
        string a,b;a=b="";
        bool flag=0;
        if(str=="")break;
        for(int i=0;i<str.length();i++)
            if(str[i]==' ')flag=1;
            else if(flag)b+=str[i];
            else a+=str[i];
        mp[b]=a;
    }
    while(cin>>str)
    {
        if(mp[str]!="")cout<<mp[str]<<endl;
        else puts("eh");
    }
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

string str;

map<string,string>mp;

int main()

{

while(getline(cin,str))

{

string a,b;a=b="";

bool flag=0;

if(str=="")break;

for(int i=0;i<str.length();i++)

if(str[i]==' ')flag=1;

else if(flag)b+=str[i];

else a+=str[i];

mp[b]=a;

}

while(cin>>str)

{

if(mp[str]!="")cout<<mp[str]<<endl;

else puts("eh");

}

return 0;

}

集合运算

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int a[1000005],b[1000005];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    m=read();
    for(int i=1;i<=m;i++)b[i]=read();
    int i=1,j=1;
    while(i<=n||j<=m)
    {
        if(i>n)printf("%d ",b[j]),j++;
        else if(j>m)printf("%d ",a[i]),i++;
        else if(a[i]==b[j])i++,j++;
        else if(a[i]<=b[j])printf("%d ",a[i]),i++;
        else printf("%d ",b[j]),j++;
    }        
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int a[1000005],b[1000005];

int main()

{

n=read();

for(int i=1;i<=n;i++)a[i]=read();

m=read();

for(int i=1;i<=m;i++)b[i]=read();

int i=1,j=1;

while(i<=n||j<=m)

{

if(i>n)printf("%d ",b[j]),j++;

else if(j>m)printf("%d ",a[i]),i++;

else if(a[i]==b[j])i++,j++;

else if(a[i]<=b[j])printf("%d ",a[i]),i++;

else printf("%d ",b[j]),j++;

}

return 0;

}

发现它，抓住它

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T,n,m;
int fa[200005];
int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
    T=read();
    while(T--)
    {
        n=read();m=read();
        for(int i=1;i<=2*n;i++)fa[i]=i;
        for(int i=1;i<=m;i++)
        {
            char ch[2];int a,b;
            scanf("%s",ch+1);
            a=read();b=read();
            if(ch[1]=='D')
                fa[find(a)]=find(b+n),fa[find(b)]=find(a+n);
            else
            {
                if(find(a)==find(b)||find(a+n)==find(b+n))
                    puts("In the same gang.");
                else if(find(a)==find(b+n)||find(b)==find(a+n))
                    puts("In different gangs.");
                else puts("Not sure yet.");
            }
        }
    }
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T,n,m;

int fa[200005];

int find(int x)

{

return x==fa[x]?x:fa[x]=find(fa[x]);

}

int main()

{

T=read();

while(T--)

{

n=read();m=read();

for(int i=1;i<=2*n;i++)fa[i]=i;

for(int i=1;i<=m;i++)

{

char ch[2];int a,b;

scanf("%s",ch+1);

a=read();b=read();

if(ch[1]=='D')

fa[find(a)]=find(b+n),fa[find(b)]=find(a+n);

else

{

if(find(a)==find(b)||find(a+n)==find(b+n))

puts("In the same gang.");

else if(find(a)==find(b+n)||find(b)==find(a+n))

puts("In different gangs.");

else puts("Not sure yet.");

}

return 0;

}

倒排索引

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
map<string,vector<int> >mp;
string str;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read();
        for(int j=1;j<=x;j++)
        {
            cin>>str;
            mp[str].push_back(i);
        }
    }
    m=read();
    for(int i=1;i<=m;i++)
    {
        cin>>str;
        vector<int> ve=mp[str];
        if(ve.size())
        {
            for(int j=0;j<ve.size();j++)
                if(j==0||ve[j]!=ve[j-1])
                    printf("%d ",ve[j]);
            puts("");
        }
        else puts("NOT FOUND");
    }
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

map<string,vector<int> >mp;

string str;

int main()

{

n=read();

for(int i=1;i<=n;i++)

{

int x=read();

for(int j=1;j<=x;j++)

{

cin>>str;

mp[str].push_back(i);

}

m=read();

for(int i=1;i<=m;i++)

{

cin>>str;

vector<int> ve=mp[str];

if(ve.size())

{

for(int j=0;j<ve.size();j++)

if(j==0||ve[j]!=ve[j-1])

printf("%d ",ve[j]);

puts("");

}

else puts("NOT FOUND");

}

return 0;

}

倒排索引查询

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool flag;
int n,m,cnt;
map<int,int>mp[100005],Hash;
int a[105],id[100005];
bool check(int x)
{
    for(int i=1;i<=n;i++)
        if(a[i]==1&&!mp[x][i])return 0;
        else if(a[i]==-1&&mp[x][i])return 0;
    return 1;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read();
        while(x--)
        {
            int y=read();
            if(!Hash[y])
            {
                Hash[y]=++cnt;
                id[cnt]=y;
            }
            y=Hash[y];
            mp[y][i]=1;
        }
    }
    m=read();
    for(int i=1;i<=m;i++)
    {
        vector<int>ans;
        for(int j=1;j<=n;j++)
            a[j]=read();
        for(int j=1;j<=cnt;j++)
            if(check(j))
            {
                ans.push_back(id[j]);
                flag=1;
            }
        if(!ans.size())puts("NOT FOUND");
        else
        {
            sort(ans.begin(),ans.end());
            for(int j=0;j<ans.size();j++)
                printf("%d ",ans[j]);
            puts("");
        }
    }
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

bool flag;

int n,m,cnt;

map<int,int>mp[100005],Hash;

int a[105],id[100005];

bool check(int x)

{

for(int i=1;i<=n;i++)

if(a[i]==1&&!mp[x][i])return 0;

else if(a[i]==-1&&mp[x][i])return 0;

return 1;

}

int main()

{

n=read();

for(int i=1;i<=n;i++)

{

int x=read();

while(x--)

{

int y=read();

if(!Hash[y])

{

Hash[y]=++cnt;

id[cnt]=y;

}

y=Hash[y];

mp[y][i]=1;

}

m=read();

for(int i=1;i<=m;i++)

{

vector<int>ans;

for(int j=1;j<=n;j++)

a[j]=read();

for(int j=1;j<=cnt;j++)

if(check(j))

{

ans.push_back(id[j]);

flag=1;

}

if(!ans.size())puts("NOT FOUND");

else

{

sort(ans.begin(),ans.end());

for(int j=0;j<ans.size();j++)

printf("%d ",ans[j]);

puts("");

}

return 0;

}

开关问题

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T,ans;
int n;
int a[35],b[35];
map<int,int>mp;
vector<int>e[35];
void dfs(int k,int n,int flag,int sta)
{
    if(k==n+1)
    {
        if(flag==0)mp[sta]++;
        else ans+=mp[sta];
        return;
    }
    int tmp=sta^(1<<k-1);
    for(int j=0;j<e[k].size();j++)
        tmp^=(1<<e[k][j]-1);
    dfs(k+1,n,flag,sta);
    dfs(k+1,n,flag,tmp);
}
int main()
{
    T=read();
    while(T--)
    {
        n=read();
        int st=0,ed=0;
        ans=0;
        for(int i=1;i<=n;i++)a[i]=read();        
        for(int i=1;i<=n;i++)b[i]=read();
        for(int i=1;i<=n;i++)
            st|=(a[i]<<i-1),ed|=(b[i]<<i-1);
        while(1)
        {
            int u=read(),v=read();
            if(u==0)break;
            e[u].push_back(v);
        }
        dfs(1,n/2,0,st^ed);
        dfs(n/2+1,n,1,0);
        if(ans)printf("%d\n",ans);
        else puts("Oh,it's impossible~!!");
        mp.clear();
        for(int i=1;i<=n;i++)e[i].clear();
    }
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T,ans;

int n;

int a[35],b[35];

map<int,int>mp;

vector<int>e[35];

void dfs(int k,int n,int flag,int sta)

{

if(k==n+1)

{

if(flag==0)mp[sta]++;

else ans+=mp[sta];

return;

}

int tmp=sta^(1<<k-1);

for(int j=0;j<e[k].size();j++)

tmp^=(1<<e[k][j]-1);

dfs(k+1,n,flag,sta);

dfs(k+1,n,flag,tmp);

}

int main()

{

T=read();

while(T--)

{

n=read();

int st=0,ed=0;

ans=0;

for(int i=1;i<=n;i++)a[i]=read();

for(int i=1;i<=n;i++)b[i]=read();

for(int i=1;i<=n;i++)

st|=(a[i]<<i-1),ed|=(b[i]<<i-1);

while(1)

{

int u=read(),v=read();

if(u==0)break;

e[u].push_back(v);

}

dfs(1,n/2,0,st^ed);

dfs(n/2+1,n,1,0);

if(ans)printf("%d\n",ans);

else puts("Oh,it's impossible~!!");

mp.clear();

for(int i=1;i<=n;i++)e[i].clear();

}

return 0;

}

Binary Search Heap Construction

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,rt,cnt;
int l[50005],r[50005],fa[50005];
struct data{
    string lab;int pri;
    friend bool operator<(data a,data b){
        return a.lab<b.lab;
    }
}a[50005];
char ch[50005];
void dfs(int x)
{
    if(!x)return;
    printf("(");
    dfs(l[x]);
    cout<<a[x].lab<<a[x].pri;
    dfs(r[x]);
    printf(")");
}
int main()
{
    while(1)
    {
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        memset(r,0,sizeof(fa));
        n=read();if(n==0)return 0;
        rt=cnt=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",ch+1);
            a[i].pri=0;a[i].lab="";
            int l=strlen(ch+1);            
            for(int j=1;j<=l;j++)
            {
                if(ch[j]>='0'&&ch[j]<='9')a[i].pri=a[i].pri*10+ch[j]-'0';
                else a[i].lab+=ch[j];
            }
        }
        sort(a+1,a+n+1);
        int now=0;
        for(int i=1;i<=n;i++)
            if(a[i].pri>=a[rt].pri)
            {
                l[i]=rt;fa[rt]=i;rt=i;
                now=rt;
            }
            else
            {
                while(a[now].pri<a[i].pri)
                    now=fa[now];
                l[i]=r[now];fa[r[now]]=i;
                r[now]=i;fa[i]=now;now=i;
            }
        dfs(rt);
        puts("");
    }
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,rt,cnt;

int l[50005],r[50005],fa[50005];

struct data{

string lab;int pri;

friend bool operator<(data a,data b){

return a.lab<b.lab;

}

}a[50005];

char ch[50005];

void dfs(int x)

{

if(!x)return;

printf("(");

dfs(l[x]);

cout<<a[x].lab<<a[x].pri;

dfs(r[x]);

printf(")");

}

int main()

{

while(1)

{

memset(l,0,sizeof(l));

memset(r,0,sizeof(r));

memset(r,0,sizeof(fa));

n=read();if(n==0)return 0;

rt=cnt=0;

for(int i=1;i<=n;i++)

{

scanf("%s",ch+1);

a[i].pri=0;a[i].lab="";

int l=strlen(ch+1);

for(int j=1;j<=l;j++)

{

if(ch[j]>='0'&&ch[j]<='9')a[i].pri=a[i].pri*10+ch[j]-'0';

else a[i].lab+=ch[j];

}

sort(a+1,a+n+1);

int now=0;

for(int i=1;i<=n;i++)

if(a[i].pri>=a[rt].pri)

{

l[i]=rt;fa[rt]=i;rt=i;

now=rt;

}

else

{

while(a[now].pri<a[i].pri)

now=fa[now];

l[i]=r[now];fa[r[now]]=i;

r[now]=i;fa[i]=now;now=i;

}

dfs(rt);

puts("");

}

return 0;

}

Training little cats

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,K;
struct M{
    ll a[105][105];
    M(){
        memset(a,0,sizeof(a));
    }
    friend M operator*(M a,M b){
        M c;
        for(int i=0;i<=n;i++)
            for(int k=0;k<=n;k++)
                if(a.a[i][k])
                    for(int j=0;j<=n;j++)
                        c.a[i][j]+=a.a[i][k]*b.a[k][j];
        return c;
    }
    friend M operator^(M a,int b){
        M ans;
        for(int i=0;i<=n;i++)
            ans.a[i][i]=1;
        for(int i=b;i;i>>=1,a=a*a)
            if(i&1)ans=ans*a;
        return ans;
    }
};
int main()
{
    while(1)
    {
        n=read();m=read();K=read();
        if(!n)break;
        M I,T;for(int i=0;i<=n;i++)I.a[i][i]=1;T=I;
        for(int i=1;i<=K;i++)
        {
            string opt;int u,v;
            M tmp=I;
            cin>>opt;u=read();
            if(opt=="g")
                tmp.a[u][0]=1;
            else if(opt=="e")
                tmp.a[u][u]=0;
            else
            {
                v=read();
                tmp.a[u][u]=tmp.a[v][v]=0;
                tmp.a[u][v]=tmp.a[v][u]=1;
            }
            T=tmp*T;
        }
        T=T^m;
        for(int i=1;i<=n;i++)
            cout<<T.a[i][0]<<' ';
        cout<<endl;
    }
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,K;

struct M{

ll a[105][105];

M(){

memset(a,0,sizeof(a));

}

friend M operator*(M a,M b){

M c;

for(int i=0;i<=n;i++)

for(int k=0;k<=n;k++)

if(a.a[i][k])

for(int j=0;j<=n;j++)

c.a[i][j]+=a.a[i][k]*b.a[k][j];

return c;

}

friend M operator^(M a,int b){

M ans;

for(int i=0;i<=n;i++)

ans.a[i][i]=1;

for(int i=b;i;i>>=1,a=a*a)

if(i&1)ans=ans*a;

return ans;

}

};

int main()

{

while(1)

{

n=read();m=read();K=read();

if(!n)break;

M I,T;for(int i=0;i<=n;i++)I.a[i][i]=1;T=I;

for(int i=1;i<=K;i++)

{

string opt;int u,v;

M tmp=I;

cin>>opt;u=read();

if(opt=="g")

tmp.a[u][0]=1;

else if(opt=="e")

tmp.a[u][u]=0;

else

{

v=read();

tmp.a[u][u]=tmp.a[v][v]=0;

tmp.a[u][v]=tmp.a[v][u]=1;

}

T=tmp*T;

}

T=T^m;

for(int i=1;i<=n;i++)

cout<<T.a[i][0]<<' ';

cout<<endl;

}

return 0;

}

Shortest Prefixes

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,cnt;
string a[1005];
int ch[20005][26],val[20005];
void add(int x)
{
    int now=0;
    for(int i=0;i<a[x].length();i++)
    {
        int t=a[x][i]-'a';
        if(!ch[now][t])ch[now][t]=++cnt;
        now=ch[now][t];
        val[now]++;
    }        
}
string query(int x)
{
    string ans="";
    int now=0;
    for(int i=0;i<a[x].length();i++)
    {
        int t=a[x][i]-'a';
        ans+=t+'a';
        now=ch[now][t];
        if(val[now]==1)break;
    }
    return ans;
}
int main()
{
    while(cin>>a[++n])
        add(n);
    for(int i=1;i<n;i++)
        cout<<a[i]<<' '<<query(i)<<endl;
    return 0;
}

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,cnt;

string a[1005];

int ch[20005][26],val[20005];

void add(int x)

{

int now=0;

for(int i=0;i<a[x].length();i++)

{

int t=a[x][i]-'a';

if(!ch[now][t])ch[now][t]=++cnt;

now=ch[now][t];

val[now]++;

}

string query(int x)

{

string ans="";

int now=0;

for(int i=0;i<a[x].length();i++)

{

int t=a[x][i]-'a';

ans+=t+'a';

now=ch[now][t];

if(val[now]==1)break;

}

return ans;

}

int main()

{

while(cin>>a[++n])

add(n);

for(int i=1;i<n;i++)

cout<<a[i]<<' '<<query(i)<<endl;

return 0;

}

双队列

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
set<pair<int,int> >bst;
int main()
{
    while(1)
    {
        int opt=read();
        if(opt==0)break;
        if(opt==1)
        {
            int K=read(),P=read();
            bst.insert(make_pair(P,K));            
        }
        if(opt==2)
        {
            if(bst.empty())
            {
                puts("0");continue;
            }
            pair<int,int> t=*--bst.end();
            printf("%d\n",t.second);
            bst.erase(bst.lower_bound(t));
        }
        if(opt==3)
        {
            if(bst.empty())
            {
                puts("0");continue;
            }
            pair<int,int> t=*bst.begin();
            printf("%d\n",t.second);
            bst.erase(bst.lower_bound(t));
        }
    }
    return 0;
}

#include<map>

#include<set>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

set<pair<int,int> >bst;

int main()

{

while(1)

{

int opt=read();

if(opt==0)break;

if(opt==1)

{

int K=read(),P=read();

bst.insert(make_pair(P,K));

}

if(opt==2)

{

if(bst.empty())

{

puts("0");continue;

}

pair<int,int> t=*--bst.end();

printf("%d\n",t.second);

bst.erase(bst.lower_bound(t));

}

if(opt==3)

{

if(bst.empty())

{

puts("0");continue;

}

pair<int,int> t=*bst.begin();

printf("%d\n",t.second);

bst.erase(bst.lower_bound(t));

}

return 0;

}

« 2015程序设计实习之上机练习题北京大学计算概论A 2018年期中考试 »

叶志晟大帅比

哈哈哈哈哈哈哈抄作业就来这了！（大雾

柯南和酵母菌

约瑟胡 2^63 怎么做啊。。

bigmingod

哈哈哈哈哈哈哈抄作业就来这了！

Orz

吐槽一下一月能学完这么多算法嘛。。

hzwer.com _ Home | http://hzwer.com

《数据结构与算法》编程练习

数据结构与算法（上）

数据结构与算法（下）

分类目录

热门文章

Myfriends

近期评论