ZJT's Blog

Keep your determination.

[自选题 #140] Swap

2018-1-5 10:272018-1-5 10:28
集训队作业自选题贪心

传送门

他既然要求字典序最小,那我们就一个个大力贪心模拟选哪个就好了。对于每个点,它跟儿子的交换可能是确定的,可能是不确定的(当右儿子小于左儿子的时候就不确定,因为不知道交换完之后左右儿子分别对应哪个值会比较优,需要留到后面处理)。从小到大考虑每个点,我们沿着不确定的点一直向上走,就能得到这个点可能取到的值。因为字典序要最小,所以我们选其中最小的一个值。这时候有三种情况,一个是这个最小值比左儿子大,且左儿子小于右儿子,这时最优的方案显然是把这个点跟左儿子交换;第二种情况是最小值大于右儿子,且右儿子小于左儿子,这时的情况就不确定了,但这个点取到的值一定就是右儿子的值,剩下两个值怎么分配留到后面去处理;最后一种情况就是不跟儿子交换,直接取上面换下来的值,这样我们就可以一路往上,把所有不确定方向的点都改为确定方向,直到碰到那个最小值的点为止。这样就在$O(n\log n)$的时间内做完了。

感觉这题可以出到一般的二叉树上?把暴力跳换成数据结构是不是就行了呢?

#include <cstdio>
#include <cstring>
#define MAXN 200010

int n;
int v[MAXN],v2[MAXN],d[MAXN];

int gao(int x){
    int minv=n+1;
    for(int i=x>>1,j=x;;i>>=1,j>>=1){
        if(d[i]==-1){
            if(v2[i]<minv) minv=v2[i];
        }else if(i*2+d[i]!=j){
            if(v[j]<minv) minv=v[j];
            break;
        }
    }
    int c1=x<<1,c2=x<<1|1;
    if(c1>n) c1=0;
    if(c2>n) c2=0;
    if(minv<v[c1] && minv<v[c2]){
        d[x]=2;
        v2[x]=n+1;
        for(int i=x>>1,j=x;;i>>=1,j>>=1){
            if(d[i]==-1){
                if(v2[i]!=minv){
                    d[i]=j-i*2;
                    v[j^1]=v2[i];
                }else{
                    d[i]=(j-i*2)^1;
                    v[j]=v2[i];
                    break;
                }
            }else if(i*2+d[i]!=j){
                d[j]=2;
                break;
            }
        }
        return minv;
    }else if(v[c1]<v[c2]){
        d[x]=0;
        v2[x]=v[c2];
        return v[c1];
    }else{
        v2[x]=v[c1];
        return v[c2];
    }
}

int main(){
#ifdef DEBUG
    freopen("140.in","r",stdin);
#endif
    scanf("%d",&n);
    v[0]=n+1;
    memset(d,-1,sizeof d);
    d[0]=2;
    for(int i=1;i<=n;i++) scanf("%d",v+i);
    for(int i=1;i<=n;i++) printf("%d ",gao(i));
    return 0;
}

查看详细内容

[自选题 #130] [Usaco2012 Feb] Cow Coupons

2017-12-25 6:12017-12-25 6:1
集训队作业自选题网络流费用流贪心

传送门

我们先二分答案,这样就确定了优惠购买的个数和不优惠购买的个数,判断可行性即可。这时容易建出费用流模型,跟二分图最大权匹配类似,不过右边只有两个点,且右边的每个点可以匹配多个左边的点。

我们考虑怎么优化这个费用流,跟朴素的找最短增广路的费用流算法类似,我们也可以每次找一条权值最小的增广路进行增广。由于增广路的长度是$O(1)$的(因为如果不是$O(1)$的,增广路会经过右边的两个点中的其中一个至少两次,然而最短路费用流算法是不会在增广过程中产生负权回路的,这就意味着不可能重复经过一个点,这就矛盾了),所以我们可以用数据结构维护最优的增广路(分四种情况讨论)。

结果写完之后T了。。。想了想怎么1个log做,发现直接把二分答案去掉,从0开始枚举,每次在上一次跑的残量网络上直接把容量会改变的那条边的容量+1,然后接着找增广路就行了。由于改动的边费用是0,所以改完之后并不会产生负权回路,所以这个做法是正确的,复杂度变成了$O(n\log n)$。

#include <bits/stdc++.h>
#define MAXN 100010
#define LL long long
using namespace std;

int n,m,m1,m2;
int c1,c2;
LL lim,res;
pair<LL,LL> a[MAXN];
set< pair<LL,int> > S1,S2,S3,S4;

bool check(){
    pair<LL,int> t1=*S1.begin(),t2=*S2.begin(),t3=*S3.begin(),t4=*S4.begin();
    LL s1=t1.first; if(c1==m1) s1=1LL<<50;
    LL s2=t2.first; if(c2==m2) s2=1LL<<50;
    LL s3=t1.first+t3.first; if(c2==m2) s3=1LL<<50;
    LL s4=t2.first+t4.first; if(c1==m1) s4=1LL<<50;
    LL s=min(min(s1,s2),min(s3,s4));
    if(s1==s){
        int i=t1.second;
        S1.erase(S1.find(make_pair(a[i].first,i)));
        S2.erase(S2.find(make_pair(a[i].second,i)));
        S3.insert(make_pair(a[i].second-a[i].first,i));
        c1++;
    }else if(s2==s){
        int i=t2.second;
        S1.erase(S1.find(make_pair(a[i].first,i)));
        S2.erase(S2.find(make_pair(a[i].second,i)));
        S4.insert(make_pair(a[i].first-a[i].second,i));
        c2++;
    }else if(s3==s){
        int i=t1.second,j=t3.second;
        S1.erase(S1.find(make_pair(a[i].first,i)));
        S2.erase(S2.find(make_pair(a[i].second,i)));
        S3.insert(make_pair(a[i].second-a[i].first,i));
        S3.erase(S3.find(make_pair(a[j].second-a[j].first,j)));
        S4.insert(make_pair(a[j].first-a[j].second,j));
        c2++;
    }else if(s4==s){
        int i=t2.second,j=t4.second;
        S1.erase(S1.find(make_pair(a[i].first,i)));
        S2.erase(S2.find(make_pair(a[i].second,i)));
        S4.insert(make_pair(a[i].first-a[i].second,i));
        S4.erase(S4.find(make_pair(a[j].first-a[j].second,j)));
        S3.insert(make_pair(a[j].second-a[j].first,j));
        c1++;
    }
    res+=s;
    return res<=lim;
}

int gao(){
    m1=m;
    m2=1;
    S3.insert(make_pair(1LL<<50,0));
    S4.insert(make_pair(1LL<<50,0));
    for(int i=1;i<=n;i++){
        S1.insert(make_pair(a[i].first,i));
        S2.insert(make_pair(a[i].second,i));
    }
    for(int i=1;i<=m;i++) check();
    while(check()) 
        m2++;
    return m1+m2-1;
}

int main(){
#ifdef DEBUG
    freopen("130.in","r",stdin);
#endif
    scanf("%d%d%lld",&n,&m,&lim);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].second,&a[i].first);
    sort(a+1,a+n+1);
    LL temp=0;
    for(int i=1;i<=m;i++){
        temp+=a[i].first;
        if(temp>lim){
            printf("%d\n",i-1);
            return 0;
        }
    }
    printf("%d\n",gao());
    return 0;
}

查看详细内容

集训队作业之AGC010-E

2017-12-16 8:202017-12-16 8:20
集训队作业AtCoder贪心

传送门

想了想感觉可以直接决策最终形成的序列,即要找到一个字典序最小的序列,使得对方不能使它变得更大。由于跟字典序有关,考虑从前往后贪心选数。

然后瞎推了个结论,大概就是在某个时刻,如果把当前还没放进去的数按不互质的关系建出无向图之后,每个连通块里都有能插到序列末端的数,那当前这个状态就是可行的。证明的话,大概就是维护一个当前能插到最后的集合,每次取一个最大的插进去,并且再在无向图中把它相邻的数加进集合。由于选的数是最大的,原先在集合中的数不会在操作后跑出集合。

有了结论之后,我们可以每步找出所有连通块,并且只要某个数当前能插到序列末端,并且大于所有其他连通块中的最小值,那这个数就是可行的。我们只要找到最小的这样一个数,然后再更新别的数的可行性,这样把所有数一个一个插进去就行了。

然而每步直接把连通块搜出来是$O(n+m)$的,而$m$可能会达到$O(n^2)$。。。为了优化建图,我把每个数分解了质因数,然后把每个作为质因子出现过的质数也建出节点,然后把每个数往它的质因子连边就行了。这样边数就变成了$O(n\log A_i)$,可以放心暴搜啦。但是总复杂度多了个分解质因数,大概是$O(n\times(\sqrt{A_i}$内的质数个数$))$,不过也不是很多,不会很影响最终的时间。

正解好像是每个连通块单独处理之后再插回去?不是很懂。。。

#include <cstdio>
#include <cstring>
#include <cassert>
#include <map>
#define MAXN 2010
#define MAXM 100010
using namespace std;

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXM<<1];

int n,numn;
int a[MAXN];
bool flag[10010];
int prime[10010],nump;
int g[MAXM],nume;
int d[MAXN][MAXN];
bool tag[MAXM],visit[MAXM],used[MAXM];
map<int,int> Sp;
int c[MAXM],numc;
int maxv[MAXN],totmax,totmax2;

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

int gcd(int x,int y){
    if(!y) return x;
    return gcd(y,x%y);
}

void init(){
    for(int i=2;i<10010;i++){
        if(!flag[i]) prime[++nump]=i;
        for(int j=1;j<=nump && i*prime[j]<10010;j++){
            flag[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

void pre_gao(int x,int v){
    int v0=v;
    for(int i=1;i<=nump && prime[i]*prime[i]<=v0;i++)
        if(v%prime[i]==0){
            while(v%prime[i]==0) v/=prime[i];
            if(!Sp.count(prime[i])) Sp[prime[i]]=++numn;
            addEdge(x,Sp[prime[i]]);
            addEdge(Sp[prime[i]],x);
        }
    if(v>1){
        if(!Sp.count(v)) Sp[v]=++numn;
        addEdge(x,Sp[v]);
        addEdge(Sp[v],x);
    }
}

void dfs(int x){
    visit[x]=1;
    c[x]=numc;
    if(tag[x] && a[x]<maxv[numc]) maxv[numc]=a[x];
    for(int i=g[x];~i;i=e[i].next)
        if(!used[e[i].to] && !visit[e[i].to]){
            dfs(e[i].to);
        }
}

int gao(int l){
    for(int i=1;i<=numn;i++) visit[i]=0;
    totmax2=totmax=numc=0;
    for(int i=1;i<=n;i++)
        if(!used[i] && !visit[i]){
            maxv[++numc]=1<<30;
            dfs(i);
            if(maxv[numc]>totmax){
                totmax2=totmax;
                totmax=maxv[numc];
            }else if(maxv[numc]>totmax2) totmax2=maxv[numc];
        }
    int minv=1<<30;
    for(int i=1;i<=n;i++)
        if(!used[i] && tag[i] && a[i]<minv){
            if(maxv[c[i]]==totmax && a[i]<totmax2) continue;
            if(maxv[c[i]]!=totmax && a[i]<totmax) continue;
            minv=a[i];
        }
    for(int i=1;i<=n;i++)
        if(!used[i] && tag[i] && a[i]==minv){
            used[i]=1;
            for(int j=1;j<=n;j++)
                if(tag[j] && a[j]>a[i]) 
                    tag[j]=0;
            for(int j=1;j<=n;j++)
                if(!used[j] && !tag[j] && d[j][i]!=1)
                    tag[j]=1;
            return minv;
        }
    assert(0);
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    init();
    scanf("%d",&n);
    numn=n;
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        pre_gao(i,a[i]);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            d[i][j]=gcd(a[i],a[j]);
    for(int i=1;i<=n;i++) tag[i]=1;
    for(int i=1;i<=n;i++) printf("%d ",gao(i));
    return 0;
}

查看详细内容

集训队作业之AGC018-B

2017-12-13 18:32017-12-13 18:3
集训队作业AtCoder贪心

传送门

我们先把全部都选中,然后再删掉其中的一部分。显然,为了使答案变小,当前方案中作为第一项出现次数最多的那项应该被删掉。所以,我们就不停地找出在序列第一项出现次数最多的值,然后把所有这种值都去掉,并不断统计答案即可。

#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 510
using namespace std;

int n,m;
queue<int> a[MAXN];
int cnt[MAXN];
bool removed[MAXN];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int t;
            scanf("%d",&t);
            a[i].push(t);
        }
    }
    for(int i=1;i<=n;i++) cnt[a[i].front()]++;
    int ans=n;
    for(int i=1;i<=m;i++){
        int res=0;
        int maxj;
        for(int j=1;j<=m;j++)
            if(!removed[j] && cnt[j]>res) res=cnt[j],maxj=j;
        if(res<ans) ans=res;
        removed[maxj]=1;
        for(int i=1;i<=n;i++)
            while(removed[a[i].front()]){
                a[i].pop();
                cnt[a[i].front()]++;
            }
    }
    printf("%d\n",ans);
}

查看详细内容

集训队作业之AGC008-D

2017-11-27 9:32017-11-27 9:3
集训队作业AtCoder贪心

传送门

直接贪心,按$x_i$排序,每次尽量靠前把第$1$到第$i$个$i$填进去,最后再从后往前把剩下的数填进去。

#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
#define MAXN 250010
using namespace std;

int n;
pair<int,int> a[MAXN];
stack<pair<int,int> > S;
int b[MAXN];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].first);
        a[i].second=i;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        int cnt=1;
        int x=1;
        b[a[i].first]=a[i].second;
        while(x<a[i].first && cnt<a[i].second){
            if(!b[x]){
                b[x]=a[i].second;
                cnt++;
            }
            x++;
        }
        if(cnt<a[i].second){
            puts("No");
            return 0;
        }
        for(int j=1;j<=n-a[i].second;j++)
            S.push(make_pair(a[i].first,a[i].second));
    }
    for(int i=n*n;i>=1;i--)
        if(!b[i]){
            if(S.top().first>=i){
                puts("No");
                return 0;
            }
            b[i]=S.top().second;
            S.pop();
        }
    puts("Yes");
    for(int i=1;i<=n*n;i++) printf("%d ",b[i]);
}

查看详细内容