UOJ Logo C_SUNSHINE的博客

博客

集训队互测 2016 Round #4

2016-04-11 23:58:03 By C_SUNSHINE

国家集训队互测2016 Round #4(镜像)将于4月17日星期日晚上18:00举行!比赛将进行5个小时,共三道题。

欢迎大家来虐~!

(lzz温馨提示:参加此次比赛有可能获得吊打集训队的荣誉!)

相信大家都已经被前面的胡策虐爆了,于是我们来送温暖啦!

出题人:Newnode,faebdc,C_SUNSHINE

这场比赛计入rating,涨跌幅度为正常比赛的 $\frac 1 4$。

题目难度和题目顺序无关

UPD:比赛已经结束!

恭喜获得前 5 名的选手!

  1. WrongAnswer
  2. bright_sun
  3. pyz5715
  4. masanzhou
  5. SKE_tlzmybm

Segment Tree Beats!

2016-02-10 23:10:14 By C_SUNSHINE

唔……既然有人说没收到完整版课件,我发一下吧QAQ

摘要

PDF课件

PPT课件

课件预览可以去我的博客(图片版所以流量党慎入)

醉醺醺的幻想乡 题解

2015-06-30 00:09:57 By C_SUNSHINE

在vfk的帮助下终于做掉了这题QAQ……vfk建议萌萌哒lzz来放个题解(里面很多是口胡的)

Description

一个二分图,左边$n$个点右边$m$个点。$S$向左边第$i$个点连的边容量为$c_i$,流量为$x$时费用为$a_ix^2+b_ix$。 左边到右边有一些边,容量为无穷大,没有费用。 右边第$j$个点到$T$连的边容量为$d_j$,没有费用。 求最小费用最大流。 $0 \leq a_i,b_i,c_i,d_i \leq 3,a_i+b_i>0,n,m \leq 100$,左边到右边的边数不超过$1000$。

Solution

我们从一个新的角度考虑总费用,假设我们有了一个费用的上界$\lambda$,可以求出费用$\leq \lambda$条件下的最大流,这个函数记为$f(\lambda)$,那么把$f(\lambda)$对$\lambda$积分就能得到答案。

每条边的流量$x_i$都满足$2a_ix_i+b_i \leq \lambda$

将$f(\lambda)$分段积分,分段时保证段内每条边的流量都是关于$\lambda$的一次函数。

那么如何估计段数呢,考虑最小割,一个割的代价是一个关于$\lambda$的一次函数,而且一次函数的斜率取值是$O(n)$的,而最小割是这些割的$\min$相当于半平面交。所以段数是$O(n)$的。

关于有意义的割的数目是$O(n)$的,可以这么考虑,假设缓慢增大某些边的流量,用dinic增广,每个点的level一定是非减的(level=$\infty$表示在T集合),则割集的变化次数一定不超过$n$。所以至多有$n+1$个有意义的割。

接下来就是把这些断点找出来,可以采用经典的分治办法,先用网络流求出$f(\lambda)$在左右端点的一次函数,然后每次对两条直线求交点,判断交点处的$f(\lambda)$是否符合,不符合说明中间存在其他的半平面,递归左右两边。这样需要$O(n)$次网络流。

最后在整点处需要注意,由于存在$a_i=0$的情况,函数值可能不连续,这时候将跳跃的流量直接乘以费用加入答案里,然后对区间$[i,i+1]$采用分段积分就可以了。

至于实现嘛,有很多要考虑的细节,首先得实现一个分数类。跑网络流时用实数,得到最小割之后用分数计算最小割关于$\lambda$的函数。

分治的时候判断交点$px$是否符合可以看$px+\epsilon$处的函数是否跟右端点函数一样。

其实很(ji)多(hu)关(suo)键(you)姿势都是vfk教我的

//frac是分数类

//带费用限制的网络流(我比较懒每次重新构图)
pair<frac,frac> dinic(DB lambda)//返回函数kx+b的pair(k,b)
{
    tot=1;
    memset(head,0,T+1<<2);
    DB w;
    for(int i=1;i<=n;i++)
    {
        if(A[i]==0)
            addedge(S,i,B[i]>lambda?0:C[i]);
        else
        {
            if(B[i]>lambda)w=0;
            w=(lambda-B[i])/(2.0*A[i]);
            if(w>-feps)
                addedge(S,i,min(w,DB(C[i])));
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(G[i][j])
                addedge(i,n+j,finf);
    for(int i=1;i<=m;i++)
        addedge(n+i,T,D[i]);
    mf=0;
    while(bfs())
        mf+=aug(S,1e10);
    frac k(0),b(0);
    for(int i=1;i<=n;i++)
        if(level[i]==-1)
        {
            if(A[i]==0)
                b+=B[i]>lambda?frac(0):frac(C[i]);
            else
            {
                if(B[i]>lambda)b+=frac(0);
                else if(A[i]*2*C[i]+B[i]>lambda)
                    k+=frac(1,A[i]*2),b-=frac(B[i],A[i]*2);
                else b+=frac(C[i]);
            }
        }
    for(int i=1;i<=m;i++)
        if(level[n+i]!=-1)
            b+=frac(D[i]);
    return make_pair(k,b);
}

//分治求断点

#define fun(_x) MF::dinic(_x)

vector<pair<frac,frac> > bp;//断点

void solve(pair<frac,frac> fl,pair<frac,frac> fr)
{
    if(fl==fr)return;
    frac px=(fr.second-fl.second)/(fl.first-fr.first);
    pair<frac,frac> fml=fun(px.toDB()-eps),fmr=fun(px.toDB()+eps);
    if(fmr==fr)
        bp.push_back(make_pair(px,px*fl.first+fl.second));
    else
    {
        solve(fl,fml);
        solve(fmr,fr);
    }
}

BestCoder Round #46 即将开始,欢迎来虐

2015-06-24 21:26:11 By C_SUNSHINE

BestCoder Round #46将于6月27日晚19:00举行,比赛将进行1小时45分钟,共4道题,一(yi)如(fan)既(chang)往(tai)的NOIP难度。欢迎大家来虐。

UPD: 由于和期末考试撞上了,报名人数不够,改成下周了QAQ

大家见过这张图片吗

这个文字在图挂了的时候会显示

你一定认出来了,这就是红遍各大QQ群,平均不超过两页聊天记录就要出现一次的神图——小火车照片。
众所周知,一列成功的火车背后一定有一个身经百战的老司机,本次比赛将以YJC是小火车的老司机为主题,向您揭示火车与火车背后的男人——YJC之间不为人知的故事……

萌萌哒C_SUNSHINE去采访出题人了,大家看看出题人是如何评价这次比赛的呢

这个文字在图挂了的时候会显示

另外可以告诉大家的是,我没有出D题。

出题人名单(打乱过了哦)

Rating_Jia_Su_Qi1150076053JOHNKRAMLyraC_SUNSHINE

noip 2014 day2 T3 LZZ做法

2014-11-09 17:06:00 By C_SUNSHINE

看标题,不敢说是题解,因为我不敢保证正确哈

首先给vfleakingjcvbPicksydc等神犇的做法跪了

我发现a[i]很大,于是想到要对大质数取模,O(nm),极限数据1.68s。试着常数优化但是无效(可能我不会常数优化)

于是我找一个比较小的质数(30000到40000),在模这个质数p意义下计算[1,p-1],如果某个x答案不为0,然后把m以内mod p余x的数筛掉,这样复杂度是O(pn+m),但是有可能会错…

于是我找了5个(好像是6个,我不记得了)质数去筛,把剩余的数直接输出,这样正确率貌似提高了,时间复杂度是O(kpn),由于开了 long long 所以极限数据0.5s。

也许能过或者得一些分吧(不过考完有人跟我讲出题人可以把50000以内质数全部卡掉……似乎滚粗了呵呵)

共 15 篇博客