UOJ Logo kczno1的博客

博客

srm 691 div1 - 500的各种做法

2017-10-17 19:34:30 By kczno1

题意:

$n$场比赛

打第i场加 $a_{i}$ 经验,且打完获得当前经验 * $b_{i}$ 的奖金

打完$n/2$场获得$x$的经验(保证$n$为偶数)

任意安排顺序,求最大奖金

$b_i<=10,n<=50,x和a_i<=10^5$

题解:

1 dp(标算)

如果不考虑$x$的话是可以贪心的。

因为考虑相邻两个$a_1,b_1,a_2,b_2$

交换后的变化=$a_2*b_1-a_1*b_2$

所以交换更优<=>$a_2/b_2>a_1/b_2$

只有$a/b$降序时无法交换,达到最优

所以$1..n/2$场与$n/2+1..n$场都是按$a/b$降序的。

按$a/b$降序排序后

枚举$n/2+1..n$场的$b_i$的和

然后dp,记录打了前几场,有几场在后面一半打,以及后面一半打的$b_i$的和。

复杂度$O(n^4*b^2)$ ,常数较小

2 随机化

先按$a/b$降序排序

然后考虑随机哪些点在后面一半打之后就可以贪心了

先让在后面一半的在后面一半打作为初始解

每次随机交换一个在前面的和在后面的

退火,甚至只有更优才交换,都能过。。

可以极快ac。

我目前也不知道怎么卡。。。

3 贪心+枚举

注意到$b$很小,而$b$一样的必定要让$a$大的在前面

(其实一开始想的是利用这一点暴力dp,但发现状态数会达到6^10,时空都炸)

利用这一点,暴力枚举每个$b$在后面$n/2$个占几个 然后在$O(n)$检验

最差情况下就是每个$b$都有$5$的$a$,差不多要枚举$10^7$次

勉强能过吧

[Usaco2012 Open]Bookshelf 的O(n)做法

2017-09-23 22:53:10 By kczno1

官方,网上题解似乎都是$O(nlogn)$的

前面应该都差不多:

$dp[i]$表示$1..i$的$min$

则$dp[i]=min(dp[j-1]+max(h[j..i]))$ 且$w(j)+..w(i)<=L$

从左到右枚举$i$,

则所有$j$被所有$h[k]=max(h[k..i])$的$k$分成一段一段

每段由于$dp[j]$的单调递增肯定取最左边的那个$j$

$k$可以用单调栈维护

由于$w(j)+..w(i)$的限制,可以的$j$的左边界是单调左移的

所以问题就变成了两端删除,一端插入,维护最值。

我想了一个$O(n)$的方法,而且是能解决两端插入的 (求问有没有别的方法)

就是左右各开一个栈维护最值,

左边删除插入就用左边的

右边删除插入就用右边的

如果左或右的栈删没了,就重构,把队列分成两半,左边分一半,右边分一半

每次重构的时间复杂度和下次删完所需的时间是一样的,所以复杂度是线性的。

卡常后拿了bzoj rank1

bzoj3011

2017-08-30 18:08:05 By kczno1

网上题解似乎都是可并堆。

这题可以给每个点自己+1,上面第一个距离>=l的祖先-1,然后统计子树和,即为答案。

求那个祖先可以dfs一遍,把点存在栈里,然后二分。

$O(nlogn)$

能拿bzoj rank1。

#include<cstdio>
using namespace std;

typedef long long ll;
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)

template <typename T> inline void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> inline void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}

const int ch_top=1e7;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
#define gc (*++now_r)
#define c *now_r
void read(int &x)
{
    while(gc<'0');
    x=c-'0';
    while(gc>='0')x=x*10+c-'0';
}
void read(ll &x)
{
    while(gc<'0');
    x=c-'0';
    while(gc>='0')x=x*10+c-'0';
}
#undef gc
#undef c
void write(int x)
{
    static char st[20];
    int top=0;
    do{st[++top]='0'+x%10;}while(x/=10);
    do{*++now_w=st[top];}while(--top);
    *++now_w='\n';
}

const int N=2e5+5;
int n,t[N],nex[N];
ll l,a[N];
ll st[N];int stx[N],top;
int s[N];
void find(const ll &ns,int r)//将第一个<=ns的祖先-1 
{
    int l=1;
    if(st[r]<=ns){--s[stx[r]];return ;}
#define mid (l+r>>1)
    while(l+1!=r)
    if(st[mid]<=ns)l=mid;
    else r=mid;
    --s[stx[l]];
}
void dfs(int x,const ll &ns,int dep)
{
    st[dep]=ns;stx[dep]=x;
    if(ns>=l)
    {
        find(ns-l,dep-1);
    }
    s[x]=1;
    for(int y=t[x];y;y=nex[y]) 
    {
      dfs(y,ns+a[y],dep+1);
      s[x]+=s[y];
    }
}

int main()
{
    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
    ch[fread(ch,1,ch_top,stdin)]=0;
    read(n);read(l);l+=1;
    rep(i,2,n)
    {
        int x;
        read(x);read(a[i]);
        nex[i]=t[x];t[x]=i;        
    }
    dfs(1,0,1);
    rep(i,1,n)write(s[i]);
    fwrite(ch,1,now_w-ch+1,stdout);
}

[Cqoi2016]伪光滑数

2017-08-27 08:03:28 By kczno1

这题很多人都用DP+可并堆

也有很多人暴力上堆 复杂度是$klogk$乘上128以内的质因数个数,约30(不过实际效果挺好的)

然而直接上堆,可以做到$2*k$次$push$,$k$次$pop$ 。

首先枚举所有可能的最大质因子及质因子分解的项数

这样题目的限制就没了,每次拓展时就可以除掉一个质因数再乘上一个质因数(只要别把最大质因子除没了)

考虑如何可以使得所有数会被拓展到且只会被拓展到一次

一个想法就是每次拓展时除掉最小质因子再乘上其前驱(比它小的最大质数)

但对于一个有多个质因子的数这样还是不能拓展到

所以再加一个方向:除掉最大质因子再乘上最小质因子

这样就ok了。

$O(klogk)$

拿到了bzoj rank3。 (下面这个直接用priority_queue的就能拿rank5,后来我手写了二叉堆。 我还写了配对堆,但不知道为什么慢了一倍多)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)

const int N=128;
int pr[N],cnt;
struct point
{
    ll a;
    int b,c,d;
    point( ll a , int b , int c , int d ) : a( a ) , b( b ) , c( c ) , d( d ) {}
};
bool operator <(const point &p1,const point &p2)
{
    return p1.a<p2.a;
}
priority_queue<point> h;

bool is_p(int x)
{
    for(int i=2;i*i<=x;++i)
        if(x%i!=0) return 0;
    return 1;
}

int main()
{
    //freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
    ll n;int k;
    cin>>n>>k;
    rep(i,2,N)
    if(is_p(i))
    {
        pr[++cnt]=i;
        ll a=1;
        for(int j=1;a<=n/i;++j)
        {
            a*=i;
            h.push( point(a,i,0,0) );
            if(cnt>1&&j>1)
                h.push( point(a/i*pr[cnt-1],i,j-1,cnt-1) );
        }
    }

    while(--k)
    {
        point now=h.top();
        h.pop();
        if(now.d>1)
            h.push( point( now.a/pr[now.d]*pr[now.d-1],now.b,now.c,now.d-1 ) );
        if(now.c>1)
            h.push( point( now.a/now.b*pr[now.d],now.b,now.c-1,now.d ) );
    }
    cout<<h.top().a;
}

泉州一中oj 建造 题解

2017-08-19 11:06:11 By kczno1

https://v.qzyz.com/problem/show/2711

没有题解我来发一个。

有环删安全值最小,相当于维护安全值的最大生成树;

安全值一样删最后,相当于以排列中的位置为第二关键字(升序)。

如果要求最大价值,就按安全值为第一关键字(降序),价值为第二关键字(降序)排序做kruscal

但还要让排列的字典序最小

就贪心枚举每一位,从小到大枚举这一位填什么,然后判断是否可以达到最大价值。

判断的方法就是按安全值为第一关键字(降序),排列中的位置为第二关键字(升序),价值为第三关键字(降序)排序做kruscal
(对不在排列中的边就令他们位置都为最大)
(一开始我令在排列中的边位置都为最小。。居然还过了)

每次只改变一条边的位置,不用重新排序,可以直接特判

所以复杂度$O(m^3)$

(好像说有$mlogm$的做法?我不会)

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=l;i<=r;++i)
#define rep0(i,n) for(int i=0;i<n;++i)

#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'0');
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}

const int N=300+5;
int n,m,fa[N];
struct edge
{
    int x,y,p,c,dy;
}l[N];int nex[N],pre[N];
int dy[N];
bool operator <(const edge &e1,const edge &e2)
{
    if(e1.p!=e2.p) return e1.p>e2.p;
    return e1.c>e2.c;
}
int ans;

namespace get
{
int ans;
int find(int x)
{
    return fa[x]==0?x:fa[x]=find(fa[x]);
}
void add(int i)
{
    edge *it=l+i;
    int x=find(it->x),y=find(it->y);
    if(x==y)return ;
    fa[x]=y;ans+=it->c;
}
int g(int x)
{
    memset(fa+1,0,n*sizeof(int));
    ans=0;
    int i=1;
    while(i<=m)
    {
        if(i==pre[x])add(x);
        int j=nex[i];
        rep(k,i,j-1)add(k);
        i=j;
    }
    return ans;
}
};

int main()
{
    freopen("1.in","r",stdin);
    cin>>n>>m;
    rep(i,1,m)l[i]=(edge){read(),read(),read(),read(),i};
    sort(l+1,l+m+1);
    rep(i,1,m)dy[l[i].dy]=i;
    nex[m]=m+1;
    for(int i=m;--i;)
    if(l[i].p==l[i+1].p) nex[i]=nex[i+1];
    else nex[i]=i+1;
    nex[0]=1;
    rep(i,1,m)
    if(nex[i-1]==i)
    rep(j,i,nex[i]-1)
     pre[j]=i;

    ans=get::g(0);
    cout<<ans<<endl;
    static bool in[N];
    int top=0;
    while(++top<=m)
    {
        int i=0;
        while(++i<=m)
        if(!in[i])
        {
            in[i]=1;
            int x=dy[i];
            if(get::g(x)==ans)
            {
               int j=pre[x];
               while(x!=j)
               {
                 swap(l[x],l[x-1]);swap(dy[l[x].dy],dy[l[x-1].dy]);
                 --x;
               }
               while(++j<nex[x]) pre[j]=x+1;
               nex[x]=x+1;
               break;
            }
            in[i]=0;
        }
        printf("%d ",i);
    }
}
kczno1 Avatar