POI20

想看英文题目右转http://main.edu.pl/en/archive/oi/20
中文翻译如果没人翻的话我啥时候抽空翻译一下传bzoj上好了
题目是很早前就出完的……只是没啥人做的样子……最近挑着做了几题……但愿不是太火星吧……
官方题解找不到……大概现在还没出……

stage 1

Taxis
容易发现……在能一次从现在所处位置到达出租车站之前……从大往小取出租车比较优(自己推式子吧……调整可破)
问题在于最后一辆到终点的出租车……
首先我们如果从大到小一个一个搭下来,最后到达m最小需要的车数为x(到不了则为n+1),那么显然ans<=x
我猜了一个性质……将x[]从小到大排序后,设满足xi>=m-d的最小的i为sel
那么我们从大到小一个一个搭过来……跳过sel不搭……把sel留到最后使用……那么这时候需要的车数为y
那么显然ans<=y
我猜的性质就是ans=min(x,y)
可以过……证明未知(我直觉上这是错的……本来是写上去试试看的可是它就是能过……)

tak.cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
#define N 500001
LL a[N],m,d,p=0;
int n,ans,sel=-1;
bool move(LL x){
    if(p<d){
        if(x>d-p)p+=x-(d-p);
    }else p=max(p,d+x);
}int main(){
    scanf("%lld%lld%d",&m,&d,&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    for(int i=n;i>=1;i--){
        move(a[i]);
        if(p>=m){ans=n-i+1;break;}
        if(a[i]>=m-d)sel=i;
    }p=0;
    if(sel>0){
        for(int i=n,cnt=0;i>=1;i--)if(i!=sel){
            move(a[i]);cnt++;
            if(p>=d||(p+a[sel]-(d-p))>=m)
                if(ans==0||ans>cnt+1)ans=cnt+1;
        }
    }printf("%d\n",ans);
}

Price List
简单的分析之后可以得到一个乱搞bfs办法——边bfs边删边
这样就可以过了
复杂度是对的……O(msqrtm)
注意结论:n点m边的无向图的三元环个数上界是O(m^1.5)
相关资料:http://arxiv.org/pdf/math/0111106v1.pdf
自己看去吧……
分析以后补

cen.cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define N 200000
#define M 400000
int n,m,k,a,b,dis[N],fa[N],lab[N],vis[N],core[N],used[N];
struct edge{
    edge*nex,*pre;
    int v;
}E[M],*G[N],*etp=E,cE[M],*cG[N],*ctp=cE;
void addedge(int u,int v){
    etp->v=v;etp->nex=G[u];if(G[u])G[u]->pre=etp;G[u]=etp++;
    etp->v=u;etp->nex=G[v];if(G[v])G[v]->pre=etp;G[v]=etp++;
    ctp->v=v;ctp->nex=cG[u];if(cG[u])cG[u]->pre=ctp;cG[u]=ctp++;
    ctp->v=u;ctp->nex=cG[v];if(cG[v])cG[v]->pre=ctp;cG[v]=ctp++;
}
queue<int>Q;
void del(int u,edge*e){
    if(cG[u]==e)cG[u]=e->nex;
    if(e->pre)e->pre->nex=e->nex;
    if(e->nex)e->nex->pre=e->pre;
}
void bfs(int S){
    memset(vis,0,sizeof(vis));
    vis[S]=1;
    for(Q.push(S);!Q.empty();Q.pop()){
        int u=Q.front();
        for(edge*e=G[u];e;e=e->nex)
            if(!vis[e->v]){
                dis[e->v]=dis[u]+1;
                fa[e->v]=u;
                vis[e->v]=1;
                Q.push(e->v);
            }
    }
    if(b>a+a)b=a+a;
    for(int i=1;i<=n;i++)lab[i]=dis[i]/2*b+((dis[i]%2==1)?a:0);//,cG[i]=G[i];
 if(b>a)return;
    memset(vis,0,sizeof(vis));vis[S]=1;
    for(Q.push(S);!Q.empty();Q.pop()){
        int u=Q.front();
        for(edge*e=G[u];e;e=e->nex)
            used[e->v]=u;
        for(edge*e=G[u];e;e=e->nex)
        {
            for(edge*x=cG[e->v];x;x=x->nex)
            {
                if(!vis[x->v]&&used[x->v]!=u)
                    vis[x->v]=1,dis[x->v]=dis[u]+2,Q.push(x->v),del(e->v,x);
            }
        }
    }for(int i=1;i<=n;i++)
    if(vis[i])
        lab[i]=min(lab[i],dis[i]/2*b);
}
int main(){
    scanf("%d%d%d%d%d",&n,&m,&k,&a,&b);
    for(int u,v;m--;)scanf("%d%d",&u,&v),addedge(u,v);
    bfs(k);
    for(int i=1;i<=n;i++)
        printf("%d\n",lab[i]);
}

Take-out

构造题苦手……正着做一直在想怎么分治真是没救了……
whitetooth神告诉我们可以倒着来……
我们可以这样想……如果我们得到了答案……
那么从后往前删……
删一次产生了k+1个空当,然后将序列往左对齐去掉所有空当……
那么每次删掉的都是当前序列连续的位置……
然后推一推就是一个栈的问题……
轻松O(n)构造……

大家可以想一想spj怎么做到O(n)……

usu.cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 1000005
int n,k,pos[N],tot,stack[N],c[2],top,s[2][N];
char st[N];
int main(){
    scanf("%d%d",&n,&k);
    scanf("%s",st+1);
    for(int i=1;i<=n;i++){
        s[st[i]=='b'][i]=s[st[i]=='b'][i-1]+1,s[(st[i]=='b')^1][i]=s[(st[i]=='b')^1][i-1];
        stack[++tot]=i;
        if(s[1][stack[tot]]-s[1][stack[tot-k]-1]==k&&s[0][stack[tot]]-s[0][stack[tot-k]-1]==1){
            s[1][stack[tot]]=s[1][stack[tot-k]-1];
            s[0][stack[tot]]=s[0][stack[tot-k]-1];
            for(int j=1;j<=k+1;j++)
                pos[++top]=stack[tot--];
        }
    }for(int j=n;j>=1;j--)
        printf("%d",pos[j]),putchar((j-1)%(k+1)==0?'\n':' ');
}

stage 2

Triumphal arch

二分答案是可以显然看出的……
我一直在想二分后怎么弄一个比较好的策略……无果
后来发现直接dp就可以了……
首先最坏情况下……国王的路径一定是一直往深度最大的地方去的
这就可以树形dp了
定义f[i]表示……
如果我们要走到i节点,那么在到达i节点之前……除了i节点自身的凯旋门之外……
至少要在i节点的子树内建立f[i]个凯旋门来支援它
边界条件:叶子节点的f[i]=0
设二分的答案为curans,然后i号节点有cnt[i]个子节点
然后就有递推式子
最后如果f[1]==0那么当前二分的答案合法否则不合法……
注意一下bzoj略卡常数……main上很好过……

luk.in
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
queue<int>Q;
#define N 1000000
int a[N],ans,n,d[N],b[N],l,r,m,f[N];
struct edge{
    int v;
    edge*nex;
}E[N],*stp=E,*G[N];
void addedge(int u,int v){
    stp->v=v;stp->nex=G[u];G[u]=stp++;
    stp->v=u;stp->nex=G[v];G[v]=stp++;
}int dfs(int u){
    int tmp=0;
    for(edge*e=G[u];e;e=e->nex)if(d[e->v]==-1||d[e->v]==d[u]+1)tmp++;
    f[u]=tmp-m;
    for(edge*e=G[u];e;e=e->nex)
        if(d[e->v]==-1||d[e->v]==d[u]+1){
            d[e->v]=d[u]+1;
            f[u]+=dfs(e->v);
        }
    f[u]=max(0,f[u]);
    return f[u];
}int main(){
    scanf("%d",&n);
    for(int i=1,u,v;i<n;i++)
        scanf("%d%d",&u,&v),addedge(u,v);
    if(n==1)return puts("0"),0;
    l=1,r=ans=n-1;
    memset(d,-1,sizeof(d));d[1]=0;
    while(l<=r){
        m=(l+r)/2;
        if(dfs(1))l=m+1;
        else ans=min(ans,m),r=m-1;
    }cout<<ans<<endl;
}

Comments

comments powered by Disqus