【近期刷题简要题解】

2015.05.06 09:43 Wed | 22次阅读 | 旧日oi | 固定链接 | 源码

明天去北京考APIO了,膜拜一个poi(A  Poi) ,求保佑QwQ
poi
把最近做的比较水的题放到一起写个题解吧- -
bzoj1455  裸的可并堆 贴代码备用……

我的程序

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 1000005
using namespace std;
int n,m;
int v[maxn],fa[maxn],die[maxn],d[maxn],l[maxn],r[maxn];
char s[10];
int find(int x)
{
    return fa[x]==x?x:(fa[x]=find(fa[x]));
}
int merge(int x,int y)
{
    if(!x) return y;
    if(!y) return x;
    if(v[x]>v[y]) swap(x,y);
    r[x]=merge(r[x],y);
    if(d[r[x]]>d[l[x]]) swap(l[x],r[x]);
    d[x]=d[r[x]]+1;
    return x;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&v[i]),fa[i]=i;
    cin>>m;
    d[0]=-1;
    for(int x,y,i=1;i<=m;i++)
    {
        scanf("%s",s);
        if(s[0]=='M')
        {
            scanf("%d%d",&x,&y);
            if(die[x]||die[y]) continue;
            int p=find(x),q=find(y);
            if(p==q) continue;
            int t=merge(p,q);
            fa[p]=fa[q]=t;
        }
        else
        {
            scanf("%d",&x);
            if(die[x])
            {
                puts("0");
                continue;
            }
            int p=find(x);
            die[p]=1;
            printf("%d\n",v[p]);
            fa[p]=merge(l[p],r[p]);
            fa[fa[p]]=fa[p];
        }
    }
    return 0;
}
bzoj1089  高精度+dp f[i]表示前深度小于等于in元树的总数,ans=f[d]-f[d-1],高精度果断上python
a=[int(i) for i in raw_input().split()]
f=[0 for x in range(0,20)]
f[0]=1
for i in range(1,a[1]+1):
    f[i]=1
    for j in range(1,a[0]+1):
        f[i]=f[i]*f[i-1]
    f[i]=f[i]+1
print f[a[1]]-f[a[1]-1]
bzoj2809  可并堆应用,肯定所选忍者薪金越低越好,所以维护一个大根堆,然后合并就好了……
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100005
int n,m,tot;
int c[N],w[N];
struct edge{
    int to,next;
}e[N*2];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
int root[N],v[N],d[N],l[N],r[N];
long long size[N],sum[N],ans;
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(v[x]<v[y]) swap(x,y);
    r[x]=merge(r[x],y);
    if(d[r[x]]>d[l[x]]) swap(l[x],r[x]);
    d[x]=d[r[x]]+1;
    return x;
}
void dfs(int u)
{
    root[u]=++tot;v[tot]=c[u];size[u]=1;sum[u]=c[u];
    for(int v,i=h[u];e[i].to;i=e[i].next)
    {
        dfs(v=e[i].to);
        sum[u]+=sum[v];size[u]+=size[v];
        root[u]=merge(root[u],root[v]);
    }
    while(sum[u]>m)
    {
        sum[u]-=v[root[u]];
        root[u]=merge(l[root[u]],r[root[u]]);
        size[u]--;
    }
    ans=max(ans,size[u]*w[u]);
}
int main()
{
    cin>>n>>m;
    for(int f,i=1;i<=n;i++)
    {
        scanf("%d%d%d",&f,&c[i],&w[i]);
        ae(f,i);
    }
    dfs(1);
    cout<<ans<<endl;
}
bzoj3011 依然裸可并堆……
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define ll long long
#define N 200005
int n,f;
ll m,w;
struct edge{
    int to,next;
    ll val;
}e[N*2];
int h[N],tp;
void ae(int u,int v,ll w)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    e[tp].val=w;
    h[u]=tp;
}
ll v[N],l[N],r[N],d[N],root[N],ans[N],tot;
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(v[x]<v[y]) swap(x,y);
    r[x]=merge(r[x],y);
    if(d[l[x]]<d[r[x]]) swap(l[x],r[x]);
    d[x]=d[r[x]]+1;
    return x;
}
void dfs(int u,ll dis)
{
    ans[u]=1;root[u]=++tot;v[tot]=dis;
    for(int v,i=h[u];e[i].to;i=e[i].next)
    {
        dfs(v=e[i].to,dis+e[i].val);
        ans[u]+=ans[v];
        root[u]=merge(root[u],root[v]);
    }
    while(v[root[u]]-dis>m)
    {
        root[u]=merge(l[root[u]],r[root[u]]);
        ans[u]--;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=2;i<=n;i++)
    {
        scanf("%d%lld",&f,&w);
        ae(f,i,w);
    }
    dfs(1,0ll);
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
bzoj1078 杂题……每次选择最左侧的深度最小的没有右子树的点,如果这个点的左子树是叶子节点,就选择叶子节点,然后把路径上的点的左右儿子交换,最后逆序输出答案
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
int n,x,l[300],r[300],fa[300];
int st[300];
int work(int &x)
{
    int e;
    if(r[x]==-1)
    {
        if(l[l[x]]==-1&&r[l[x]]==-1)
        {
            e=l[x];l[x]=-1;return e;
        }
        e=x;x=l[x];return e;
    }
    e=work(l[x]);
    swap(l[x],r[x]);
    return e;
}
int main()
{
    cin>>n;l[0]=r[0]=-1;
    for(int i=1;i<=n;i++)
    {
        l[i]=r[i]=-1;
        cin>>x;
        if(x>=100) r[x-100]=i;
        else l[x]=i;
    }
    int ans[300],root=0;
    for(int i=1;i<=n+1;i++) ans[i]=work(root);
    for(int i=n+1;i>1;i--) cout<<ans[i]<<" ";
    cout<<ans[1];
}
bzoj1177  开始APIO大作战……  画图可以发现,情况只有6种,分别算一下就好了,开始还写了个二维线段树,其实分别维护四个角的前缀最大值就好了……算了之后不贴代码了……
bzoj1178 如果不要求字典序最小那么贪心就可以了,但是它要求……所以我们先求出ans之后,按照输入顺序,考虑每个区间选不选,假设一个区间是[x,y],那么如果[1,x),(y,n]中可以选出ans-1个区间,那么说明这个区间可以选,维护那个东西可以用一个倍增来搞,d[l][i]表示从l开始选2^i个不相交区间之后所能达到的最小位置,预处理啊,判重啊什么的都好麻烦……
bzoj1179    tarjan缩点+spfa求最长路搞定……
bzoj3624   如果0边总数小于k,无解。求一遍最大生成树,如果选择的0边多于k条,也无解。其它情况都是有解的,随便加入k条白边(当然不能出环),剩余的用黑边补全就可以了。
bzoj1913   如果4个点构成凸四边形,那么任选3点,圆内包含的三角形有2个,凹四边形有一个。凸四边形的数量可以这么求:以每一个点为原点把其它点按极角排序,再枚举每一个点,用叉积找到第一个逆时针和这个点相差的角度大于180度的点,记录中间经过的点的数量,则任选中间经过的两个点,和原点,和枚举点构成的一定是凸四边形。凹四边形的数量就是(总数-凸四边形的数量)。
bzoj1912 求两遍树的直径……第一次求完把直径上的边的边权设为-1,话说以前写的方法好烂,还容易错……留个代码备用
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int n,k,ans,mx,dis;
struct edge
{
    int to,next,val;
}e[200005];
int h[100005],tp;
int s1[100005],s2[100005],mx1,mx2;
void ae(int u,int v,int w)
{
    e[tp].to=v;
    e[tp].next=h[u];
    e[tp].val=w;
    h[u]=tp++;
}
int dfs(int u,int f)
{
    int mx1=0,mx2=0;
    for(int v,i=h[u];i!=-1;i=e[i].next)
    if((v=e[i].to)!=f)
    {
        int val=e[i].val+dfs(v,u);
        if(val>mx1) mx2=mx1,mx1=val,s2[u]=s1[u],s1[u]=i;
        else if(val>mx2) mx2=val,s2[u]=i;
    }
    if(mx1+mx2>dis) dis=mx1+mx2,mx=u;
    return mx1;
}
int main()
{
    cin>>n>>k;
    memset(h,-1,sizeof(h));
    for(int w=1,u,v,i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        ae(u,v,w);ae(v,u,w);
    }
    dfs(1,0);ans=2*(n-1)-dis+1;
    if(k==2)
    {
        for(int i=s1[mx];i;i=s1[e[i].to]) e[i].val=e[i^1].val=-1;
        for(int i=s2[mx];i;i=s1[e[i].to]) e[i].val=e[i^1].val=-1;
        dis=0;dfs(1,0);ans=ans-dis+1;
    }
    cout<<ans<<endl;
    return 0;
}
bzoj3675 斜率优化
bzoj3098   随机一个串,看脸
bzoj2084,就是求一个变一下匹配规则的回文串,用manacher就可以,留代码备用
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 2000010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
char s[maxn];
int n,p[maxn],a[maxn];
int main()
{
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++) a[i<<1]=(s[i]=='0')?0:2;
    n=2*n+1;
    for(int i=1;i<=n;i+=2) a[i]=1;
    for(int mx=0,id=0,i=1;i<=n;i+=2)
    {
        if(mx>i) p[i]=min(p[2*id-i],mx-i);
        else p[i]=1;
        for(;i-p[i]>0&&i+p[i]<=n&&a[i+p[i]]+a[i-p[i]]==2;p[i]++);
        if(p[i]+i>mx) mx=p[i]+i,id=i;
    }
    ll ans=0;
    for(int i=1;i<=n;i+=2) ans+=(p[i]-1)>>1;
    cout<<ans<<endl;
}
bzoj3676  string这东西太坑了……轻易不要用……找到每个点的极长回文串,用hash将串变成节点,一个回文串删掉首尾还是回文串,所以我们可以把每个回文串对应的点和删除首尾后的回文串对应的点连边,最后回文串的贡献就是串的长度*(这个回文串对应的点的子树中节点的出现子树之和).
bzoj3677 看具体题解……
bzoj1088  大水题,不说了
bzoj1090 区间DP,用f[i][j]表示ij折叠后所需的最短长度,则f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]) 如果i-j是由i-k重复而来,就有f[i][j]=min(f[i][j],f[i][k]+2+(r-l+1)/(k-i+1)的数位)
bzoj4003  可并堆,本来想单独开一篇,但是觉得也没什么好写的,传标记这东西还是挺恶心……注意乘数是正的,所以堆的性质不会改变……
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
#define N 300005
#define ll long long
int n,m,f[N],a[N],c[N],ind[N],dep[N];
ll val[N],h[N],s[N];
vector<int> son[N];
struct kebing_heap
{
    int l[N],r[N],fa[N],tot,x;
    int die[N],idx[N],st[N],d[N],root[N],con[N];
    ll v[N],add[N],mu[N];
    void mul(int x,ll val)
    {
        mu[x]*=val;
        v[x]*=val;
        add[x]*=val;    
    }
    void ad(int x,ll val)
    {
        v[x]+=val;
        add[x]+=val;
    }
    void pushdown(int x)
    {
        if(mu[x]!=1)
        {
            if(l[x]) mul(l[x],mu[x]);
            if(r[x]) mul(r[x],mu[x]);
            mu[x]=1;
        }
        if(add[x]!=0)
        {
            if(l[x]) ad(l[x],add[x]);
            if(r[x]) ad(r[x],add[x]);
            add[x]=0;
        }
    }
    int merge(int x,int y)
    {
        if(!x||!y) return x+y;
        if(v[x]>v[y]) swap(x,y);
        pushdown(x);
        r[x]=merge(r[x],y);
        if(d[r[x]]>d[l[x]]) swap(l[x],r[x]);
        d[x]=d[r[x]]+1;
        return x;
    }
    void init()
    {
        scanf("%lld%d",&v[++tot],&x);
        mu[tot]=1;
        if(v[tot]>=h[x]) 
        {
            con[tot]=dep[x];
            root[x]=merge(tot,root[x]);
        }
        else die[x]++;
    }
    int q[N],fr,ta;
    void work()
    {
        q[++ta]=1;
        while(fr!=ta)
        {
            int u=q[++fr];
            for(int i=0;i<son[u].size();i++) 
            q[++ta]=son[u][i];
        }
        for(int j=n;j;j--)
        {
            int u=q[j];
            for(int i=0;i<son[u].size();i++)
                root[u]=merge(root[u],root[son[u][i]]);
            while(root[u]&&v[root[u]]<h[u]) 
            {   
                con[root[u]]=con[root[u]]-dep[u];die[u]++;
                pushdown(root[u]);
                root[u]=merge(l[root[u]],r[root[u]]);
            }
            if(root[u]) 
            {
                if(a[u]) mul(root[u],val[u]);
                else ad(root[u],val[u]);
            }
        }
    }
    void print()
    {
        for(int i=1;i<=n;i++) printf("%d\n",die[i]);
        for(int i=1;i<=m;i++) printf("%d\n",con[i]);
    }
}heap;
queue<int> q;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
    for(int i=2;i<=n;i++) 
    {
        scanf("%d%d%lld",&f[i],&a[i],&val[i]);
        son[f[i]].push_back(i);
        ind[f[i]]++;
    }
    q.push(1);dep[1]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=0;i<son[u].size();i++)
        {
            dep[son[u][i]]=dep[u]+1;
            q.push(son[u][i]);
        }
    }
    for(int i=1;i<=m;i++) heap.init();
    heap.work();
    heap.print();
    return 0;
}
bzoj2333,好题号~ 正常的可并堆操作+用一个set记录每个堆的最大值,操作挺全的,留个代码吧
#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 300005
#define inf 0x3f3f3f3f
multiset<int> s;
void erase(int x)
{
    s.erase(s.find(x));
}
void insert(int x)
{
    s.insert(x);
}
int n,q,x,y,addmark;
struct kebing_heap
{
    int l[N],r[N],v[N],fa[N],flag[N],q[N],tot;
    int find(int x)
    {
        while(fa[x]) x=fa[x];
        return x;
    }
    void pushdown(int x)
    {
        if(!flag[x]) return;
        int t=flag[x],ls=l[x],rs=r[x];
        if(ls) flag[ls]+=t,v[ls]+=t;
        if(rs) flag[rs]+=t,v[rs]+=t;
        flag[x]=0;
    }
    void pushpath(int x)
    {
        while(x) q[++tot]=x,x=fa[x];
        while(tot) pushdown(q[tot--]);
    }
    int merge(int x,int y)
    {
        if(!x||!y) return x+y;
        if(v[x]<v[y]) swap(x,y);
        pushdown(x);
        r[x]=merge(r[x],y);
        fa[r[x]]=x;
        swap(l[x],r[x]);
        return x;
    }
    int del(int x)
    {
        int t=merge(l[x],r[x]),f=fa[x];
        r[x]=l[x]=fa[x]=0;
        if(x==l[f]) l[f]=t;
        else r[f]=t;
        fa[t]=f;
        return find(t);
    }
    void add(int x,int y)
    {
        pushpath(x);
        erase(v[find(x)]);
        v[x]+=y;
        insert(v[merge(x,del(x))]);
    }
    void heap_add(int x,int y)
    {
        int p=find(x);
        flag[p]+=y;v[p]+=y;
        erase(v[p]-y);insert(v[p]);
    }
    void ae(int x,int y)
    {
        int p=find(x),q=find(y);
        if(p==q) return;
        if(merge(p,q)==p) erase(v[q]);
        else erase(v[p]);
    }
    void print(int x)
    {
        pushpath(x);
        printf("%d\n",v[x]+addmark);
    }
}h;
void printmax()
{
    printf("%d\n",*--s.find(inf)+addmark);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&h.v[i]),insert(h.v[i]);
    cin>>q;
    char s[5];
    for(int i=1;i<=q;i++)
    {
        scanf("%s",s);
        if(s[0]=='U') scanf("%d%d",&x,&y),h.ae(x,y);
        else if(s[0]=='A')
        {
            if(s[1]=='1') scanf("%d%d",&x,&y),h.add(x,y);
            else if(s[1]=='2') scanf("%d%d",&x,&y),h.heap_add(x,y);
            else scanf("%d",&x),addmark+=x;
        }
        else
        {
            if(s[1]=='1')  scanf("%d",&x),h.print(x);
            else if(s[1]=='2') scanf("%d",&x),h.print(h.find(x));
            else printmax();
        }
    }
    return 0;
}```