2017/07/25 杂题（完全不可做题（划去））选讲

先膜一发主讲人@Antileaf

真是核平的一天那……大脑已经被蹂躏的死去活来了……

cogs2421 简单的Treap

链接：http://cogs.pro/cogs/problem/problem.php?pid=2421

题意：什么都给你了，建出Treap，输出先序遍历顺序。

实际上只是用了Treap的原则建树……先按照数值大小排序，然后按照建立笛卡尔树方法，维护单调栈，最大的全扔到右儿子去即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500005;
int n,lc[maxn],rc[maxn],stack[maxn],top,root;
struct node
{
    int val,fix;
    bool operator <(const node b)const{
        return val<b.val;
    }
}a[maxn];
void dfs(int root)
{
    printf("%d ",a[root].val);
    if(lc[root])dfs(lc[root]);
    if(rc[root])dfs(rc[root]);
}
int main()
{
    freopen("treap.in","r",stdin);
    freopen("treap.out","w",stdout);
    int __size__=128<<20;
    char *__p__=(char*)malloc(__size__)+__size__;
    __asm__("movl %0, %%esp
"::"r"(__p__));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].val);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].fix);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        stack[top+1]=0;
        while(top&&a[stack[top]].fix>a[i].fix)top--;
        lc[i]=stack[top+1];
        (top?rc[stack[top]]:root)=i;
        stack[++top]=i;
    }
    dfs(root);
}

cogs2434 暗之链锁

链接：http://cogs.pro/cogs/problem/problem.php?pid=2434

题意：一个图由一棵树和m条副边形成，只能砍一条树边、一条副边，问有多少种方法使原图不连通。

树上差分啊……找到每条副边，差分处理，然后对每条树边考虑被几条副边覆盖，$x=0$时有m种，$x=1$时就一种。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=100005,maxm=200005;
vector<int>G[maxn],q[maxn];
int n,m,prt[maxn],anc[maxn],a[maxn],x,y,ans;
bool vis[maxn];
int findroot(int x)
{
    return anc[x]==x?x:(anc[x]=findroot(anc[x]));
}
void dfs1(int x)
{
    int cnt=G[x].size();
    anc[x]=x;
    for(int i=0;i<cnt;i++)
        if(G[x][i]!=prt[x])
        {
            prt[G[x][i]]=x;
            dfs1(G[x][i]);
        }
    vis[x]=1;cnt=q[x].size();
    for(int i=0;i<cnt;i++)
        if(vis[q[x][i]])a[findroot(q[x][i])]-=2;
    anc[x]=prt[x];
}
void dfs2(int x)
{
    int cnt=G[x].size();anc[x]=x;
    for(int i=0;i<cnt;i++)
        if(G[x][i]!=prt[x])
        {
            dfs2(G[x][i]);
            a[x]+=a[G[x][i]];
        }
    if(prt[x])
        if(!a[x])ans+=m;
        else if(a[x]==1)ans++;
}
int haha()
{
    freopen("yam.in","r",stdin);
    freopen("yam.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);G[y].push_back(x);
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        if(x==y)continue;
        a[x]++;a[y]++;
        q[x].push_back(y),q[y].push_back(x);
    }
    dfs1(1);dfs2(1);
    printf("%d
",ans);
    //while(1);
}
int sb=haha();
int main(){;}

HEOI2017 组合数问题

挖坑……

NOI2016区间

链接：http://cogs.pro/cogs/problem/problem.php?pid=2406

题意：数轴上有n个闭区间，求出m个区间，使至少1个点被这些区间全部包括，并最小化最大区间长度与最小区间长度之差。

真是妙啊……首先对区间按长度排序，对坐标离散化，随后，动态增减区间，线段树动态维护。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=1000005;
int n,m,x,sm[maxn<<2],mx[maxn<<2],b[maxn],p[maxn],cnt;
struct districts
{
    int l,r,len;
}ques[maxn];
int cmp(const int &a,const int &b)
{
    return ques[a].len<ques[b].len;
}
#define mid ((l+r)>>1)
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define lc root<<1
#define rc root<<1|1
void Modify(int root,int l,int r,int L,int R,int val)
{
    if(L<=l&&r<=R)
    {
        mx[root]+=val;
        sm[root]+=val;
        return;
    }
    if(mid>=L)Modify(lson,L,R,val);
    if(mid<R)Modify(rson,L,R,val);
    mx[root]=max(mx[lc],mx[rc])+sm[root];
}
int haha()
{
    freopen("interval.in","r",stdin);
    freopen("interval.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        p[i]=i;districts &d=ques[i];
        scanf("%d%d",&d.l,&d.r);
        d.len=d.r-d.l+1;
        b[++cnt]=d.l;b[++cnt]=d.r;
    }
    sort(p+1,p+n+1,cmp);sort(b+1,b+cnt+1);
    cnt=unique(b+1,b+cnt+1)-b-1;
    for(int i=1;i<=n;i++)
    {
        int t=p[i];districts &d=ques[t];
        d.l=lower_bound(b+1,b+cnt+1,d.l)-b;
        d.r=lower_bound(b+1,b+cnt+1,d.r)-b;
    }
    int ans=0x7f7f7f7f;
    for(int i=1,j=0;j<n||(mx[1]==m&&j==n);)
    {
        while(mx[1]<m&&j<n)
        {
            j++;
            Modify(1,1,cnt,ques[p[j]].l,ques[p[j]].r,1);
        }
        while(mx[1]==m&&i<=n)
        {
            ans=min(ans,ques[p[j]].len-ques[p[i]].len);
            Modify(1,1,cnt,ques[p[i]].l,ques[p[i]].r,-1);
            i++;
        }
    }
    if(ans==0x7f7f7f7f)ans=-1;
    printf("%d
",ans);
}
int sb=haha();
int main(){;}

ZJOI2004 树的果实

挖坑……

HNOI2016 序列

挖坑……

cogs2582 动物城的鸳鸯蛋传说

链接：http://cogs.pro/cogs/problem/problem.php?pid=2582

题意：有两个数列，问用第一个数列能组出第二个数列中哪些数。

bitset第一题……

http://cogs.pro/cogs/problem/problem.php?pid=2582

cogs2089 平凡的测试数据

出门左转：http://www.cnblogs.com/Loser-of-Life/p/7236695.html

cogs1000 伊吹萃香

出门左转：http://www.cnblogs.com/Loser-of-Life/p/7237419.html

NOI2014 起床困难综合症

链接：http://cogs.pro/cogs/problem/problem.php?pid=1684

题意：一路位运算，求最大攻击伤害。

对每一位进行处理，在m范围内能大伤害就大伤害，相同就在这一位取0。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int haha()
{
    freopen("sleep.in","r",stdin);
    freopen("sleep.out","w",stdout);
    int n,m;scanf("%d%d",&n,&m);
    int id,ide=0;for(id=1;id<m;id=id<<1|1);
    for(int i=1;i<=n;i++)
    {
        char opt[5];int v;scanf("%s%d",opt,&v);
        switch(opt[0])
        {
            case 'O':ide|=v;id|=v;break;
            case 'X':ide^=v;id^=v;break;
            case 'A':ide&=v;id&=v;break;
        }
    }
    bool judge=0;int q=0;
    for(int i=29;i>=0;i--)
    {
        int t=ide>>i&1;
        if((judge||(m>>i&1))&&(id>>i&1)>t)t=id>>i&1;
        if(m>>i&1)judge=1;
        q|=t<<i;
    }
    printf("%d
",q);
}
int sb=haha();
int main(){;}

cogs2235 烤鸡翅

出门左转：http://www.cnblogs.com/Loser-of-Life/p/7236721.html

HEOI2017 期末考试

链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4868

题意：有一些人等成绩，每超过预期一天会增加学生不满度，减少判卷时间会增加老师不满度(⊙﹏⊙)b……求最低总不满度。

通过一顿乱搞可以得出总不满度关于时间的函数是一个严格的凹函数，三分时间，求最小值水之。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100005;
int A,B,C;int n,m,t[maxn],b[maxn];
LL work(int val)
{
    LL res=0,v1=0,v2=0;
    for(int i=1;i<=n;i++)
        if(val>t[i])res+=(LL)(val-t[i])*C;
    for(int i=1;i<=m;i++)
        if(b[i]<val)v1+=val-b[i];
        else v2+=b[i]-val;
    if(A>=B)res+=(LL)v2*B;
    else
    {
        res+=(LL)min(v1,v2)*A;
        if(v1<v2) res+=(LL)(v2-v1)*B;
    }
    return res;
}
int haha()
{
    scanf("%d%d%d",&A,&B,&C);
    scanf("%d%d",&n,&m);
    int maxx=0;
    for(int i=1;i<=n;i++)scanf("%d",&t[i]);
    for(int i=1;i<=m;i++)scanf("%d",&b[i]);
    int l=0,r=100000;
    LL ans=1e18;
    while(r-l>5)
    {
        int mid=l+(r-l)/3,midmid=r-(r-l)/3;
        LL v1=work(mid),v2=work(midmid);
        if(v1<=v2) 
        {
            ans=min(ans,v1);
            r=midmid;
        }
        else
        {
            ans=min(ans,v2);
            l=mid;
        }
    }
    for(int i=l;i<=r;i++)ans=min(ans,work(i));
    printf("%lld
",ans);
}
int sb=haha();
int main(){;}

51nod1597 有限背包计数问题

挖坑……

cogs1825 道路和航线

链接：http://cogs.pro/cogs/problem/problem.php?pid=1825

题意：一张带权混合图，保证无向边权值非负，有向边保证不会带来环，求1号节点到所有节点最短路。

我们知道，非负权图可以用Dijkstra保证时间复杂度在$O(nlogn)$，而有向图可以用记忆化搜索保证线性时间复杂度。那么想法就出现了：将每一个无向图中连通块缩成一个点，再进行记忆化搜索。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxt=25005,maxr=50005;
struct node
{
    int from,to,weight,next;
}edge1[maxr<<1];
int head1[maxt],tot,t,r,p,s,cnt;
void addedge1(int u,int v,int w)
{
    edge1[++tot]=(node){u,v,w,head1[u]};head1[u]=tot;
}
vector<int>a[maxt];
int id[maxt];
void dfs1(int x)
{
    id[x]=cnt;a[cnt].push_back(x);
    for(int i=head1[x];i;i=edge1[i].next)
        if(!id[edge1[i].to])dfs1(edge1[i].to);
}
vector<int>G[maxt],W[maxt],G2[maxt];
int entrance_degree[maxr];
bool vis[maxr];
void dfs2(int x)
{
    vis[x]=1;
    for(int i=0;i<G2[x].size();i++)
    {
        entrance_degree[G2[x][i]]++;
        if(!vis[G2[x][i]])dfs2(G2[x][i]);
    }
}
struct point
{
    int dis,id;
    bool operator <(const point &b)const{
        return dis>b.dis;
    }
};
priority_queue<point>heap;
int dist[maxt];
void Dijkstra()
{
    while(!heap.empty())
    {
        point tmp=heap.top();heap.pop();
        int dis=tmp.dis,iden=tmp.id;
        if(vis[iden])continue;
        vis[iden]=1;
        for(int i=head1[iden];i;i=edge1[i].next)
        {
            int v=edge1[i].to;
            if(dist[v]>dist[iden]+edge1[i].weight)
            {
                dist[v]=dist[iden]+edge1[i].weight;
                heap.push((point){dist[v],v});
            }
        }
    }
}
void bfs()
{
    memset(vis,0,sizeof(vis));
    memset(dist,63,sizeof(dist));
    queue<int>q;q.push(id[s]);dist[s]=0;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=0;i<a[x].size();i++)
            if(dist[a[x][i]]<0x3f3f3f3f)heap.push((point){dist[a[x][i]],a[x][i]});
        Dijkstra();
        for(int i=0;i<a[x].size();i++)
            for(int j=0;j<G[a[x][i]].size();j++)
            {
                dist[G[a[x][i]][j]]=min(dist[G[a[x][i]][j]],dist[a[x][i]]+W[a[x][i]][j]);
                if(!--entrance_degree[id[G[a[x][i]][j]]])q.push(id[G[a[x][i]][j]]);
            }
    }
}
int haha()
{
    freopen("roadplane.in","r",stdin);
    freopen("roadplane.out","w",stdout);
    scanf("%d%d%d%d",&t,&r,&p,&s);
    for(int i=1;i<=r;i++)
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        addedge1(u,v,w);addedge1(v,u,w);
    }
    for(int i=1;i<=t;i++)
        if(!id[i])
        {
            cnt++;
            dfs1(i);
        }
    for(int i=1;i<=p;i++)
    {
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        G[x].push_back(y);
        W[x].push_back(z);
        G2[id[x]].push_back(id[y]);
    }
    dfs2(id[s]);
    bfs();
    for(int i=1;i<=t;i++)
        if(dist[i]==0x3f3f3f3f)puts("NO PATH");
        else printf("%d
",dist[i]);
}
int sb=haha();
int main(){;}

HEOI2016 排序

链接：http://cogs.pro/cogs/problem/problem.php?pid=2276

题意：区间修改，每一次对于一个子区间进行升序排列、降序排列，问最后某个位置的值是多少。

我们可以发现：当我们钦定一个答案的时候，可以得出最后结果是大于还是小于这个钦定结果的。很明显这个东西具有单调性。那么我们就二分答案，对于每个答案线段树验证即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define lc root<<1
#define rc root<<1|1
using namespace std;
const int maxn=100005;
int sm[maxn<<2],st[maxn<<2],a[maxn];
void Build(int root,int l,int r,int val)
{
    st[root]=-1;
    if(l==r)
    {
        if(a[l]>=val)sm[root]=1;
        else sm[root]=0;
        return;
    }
    int mid=(l+r)>>1;
    Build(lson,val);Build(rson,val);
    sm[root]=sm[lc]+sm[rc];
}
void pushdown(int root,int l,int r)
{
    if(l==r)return;
    if(st[root]!=-1)
    {
        st[lc]=st[rc]=st[root];
        int mid=(l+r)>>1;
        sm[lc]=st[lc]*(mid-l+1);
        sm[rc]=st[rc]*(r-mid);
        st[root]=-1;
    }
}
void pushup(int root)
{
    sm[root]=sm[lc]+sm[rc];
}
int Query(int root,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)return sm[root];
    pushdown(root,l,r);
    int mid=(l+r)>>1,ans=0;
    if(R<=mid)ans=Query(lson,L,R);
    else if(L>mid)ans=Query(rson,L,R);
    else
    {
        ans+=Query(lson,L,mid);
        ans+=Query(rson,mid+1,R);
    }
    return ans;
}
void Set(int root,int l,int r,int L,int R,int val)
{
    if(L>R)return;
    if(L<=l&&r<=R)
    {
        st[root]=val;
        sm[root]=val*(r-l+1);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(root,l,r);
    if(R<=mid)Set(lson,L,R,val);
    else if(L>mid)Set(rson,L,R,val);
    else
    {
        Set(lson,L,mid,val);
        Set(rson,mid+1,R,val);
    }
    pushup(root);
}
int n,m,q;
struct Ques
{
    int l,r,val;
}qu[maxn];
bool Check(int val)
{
    Build(1,1,n,val);
    for(int i=1;i<=m;i++)
    {
        int wal=Query(1,1,n,qu[i].l,qu[i].r);
        int fenjiexian;
        if(qu[i].val)
        {
            fenjiexian=qu[i].l+wal-1;
            Set(1,1,n,qu[i].l,fenjiexian,1);
            Set(1,1,n,fenjiexian+1,qu[i].r,0);
        }
        else
        {
            fenjiexian=qu[i].r-wal+1;
            Set(1,1,n,qu[i].l,fenjiexian-1,0);
            Set(1,1,n,fenjiexian,qu[i].r,1);
        }
    }
    int k=Query(1,1,n,q,q);
    if(k)return 1;
    else return 0;
}
int haha()
{
    freopen("heoi2016_sort.in","r",stdin);
    freopen("heoi2016_sort.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&qu[i].val,&qu[i].l,&qu[i].r);
    scanf("%d",&q);
    int l=1,r=n,ans;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(Check(mid))
            l=mid+1;
        else r=mid-1;
    }
    printf("%d
",r);
}
int sb=haha();
int main(){;}

Tower

挖坑……

（所以这么多坑我填的完么……）