正文

BZOJ一句话

IP云
IP云V管理员/2 阅读
11/29
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

一句话题解集合。

1061: [Noi2008]志愿者招募

单纯形，运用对偶原理转化过来，变成标准形然后单纯性裸上即可。 

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<cstring>

 #include<algorithm>

 const double eps=1e-;

 const double oo =1e9;

 double a[][];

 double b[];

 double c[];

 int n,m;

 int read(void)

 {

     int ans=;

     int f=;

     char ch=getchar();

     while(ch<''||ch>'')

     {

         if(ch=='-')f=-f;

         ch=getchar();

     }

     while(ch<=''&&ch>='')

     {

         ans=ans*+ch-'';

         ch=getchar();

     }

     return ans*f;

 }

 void pivot(double&ans,int l,int e)

 {

     b[l]/=a[l][e];

     for(int i=;i<=n;i++)if(i!=e)a[l][i]/=a[l][e];

     a[l][e]=1.00/a[l][e];

     for(int i=;i<=m;i++)

     if(fabs(a[i][e])>eps&&i!=l)

     {

         b[i]-=b[l]*a[i][e];

         for(int j=;j<=n;j++)if(j!=e)

             a[i][j]-=a[i][e]*a[l][j];

         a[i][e]=-a[i][e]*a[l][e];

     }

     ans+=c[e]*b[l];

     for(int i=;i<=n;i++)if(i!=e)c[i]-=c[e]*a[l][i];

     c[e]=-c[e]*a[l][e];

     return ;

 }

 double simplex(void)

 {

     double ans=;

     while(true)

     {

         int e,l;

         for(e=;e<=n;e++)if(c[e]>eps)break;

         if(e>n)return ans;

         double mins=oo;

         for(int i=;i<=m;i++)

             if(a[i][e]>eps&&mins>b[i]/a[i][e])

                 mins=b[i]/a[i][e],l=i;

         if(mins>=oo-eps)return oo;

         pivot(ans,l,e);

     }

     return ans;

 }

 int main()

 {

 //    freopen("a.in","r",stdin);

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)c[i]=read();

     for(int i=;i<=m;i++)

     {

         int s,t;

         scanf("%d%d",&s,&t);

         for(int j=s;j<=t;j++)

         {

             if(j<)j=;if(j>n)break;

             a[i][j]=;

         }

         b[i]=read();

     }

     printf("%d\n",(int)(simplex()+0.5));

     return ;

 }

1061

1197: [HNOI2006]花仙子的魔法

神TM递推题，考虑升维的计算仍然是类似的，就有递推式$f_{[i][j]}=f_{[i-1][j-1]}+f_{[i][j-1]}$ 

#include<cstdio>

typedef long long lnt;

lnt dp[][];

int n,m;

int main()

{

//    freopen("flower.in","r",stdin);

//    freopen("flower.out","w",stdout);

    scanf("%d%d",&m,&n);dp[][]=;

    for(int i=;i<=m;i++)dp[][i]=i*;

    for(int i=;i<=n;i++)

    {

        dp[i][]=;

        for(int j=;j<=m;j++)dp[i][j]=dp[i][j-]+dp[i-][j-];

    }

    printf("%lld\n",dp[n][m]);

    return ;

}

2161: 布娃娃

偏不写扫描线，考虑对于同一种p，询问编号越小越先得到答案，先离散化按p排序建立线段树，询问挂在叶节点上，维护区间最小询问。

按照c从大到小的顺序加入查询，区间-1，若最小值变成0，则说明这个区间是某个p的答案，二分删除这个询问。

易知每个询问最多被删除一次，所以时间复杂度仍为$O(nlog_2n)$ 

 #include<map>

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<algorithm>

 #define Mod 19921228

 #define lll spc<<1

 #define rrr spc<<1|1

 typedef long long lnt;

 struct data{

     lnt add;

     lnt first;

     lnt mod;

     lnt prod;

     void Insert(void)

     {

         scanf("%lld%lld%lld%lld",&add,&first,&mod,&prod);

         return ;

     }

     lnt sta(void)

     {

         return first%mod;

     }

     lnt S(lnt lst,lnt i)

     {

         return (prod*lst+add+i)%mod;

     }

 }P,C,L,R;

 struct pnt{

     int p;

     int l,r;

     int no;

     int c;

     void sta(void)

     {

         no=;

         p=P.sta();

         l=L.sta();

         r=R.sta();

         c=C.sta();

         return ;

     }

     void ch(void)

     {

         if(l>r)std::swap(l,r);

         return ;

     }

 }p[];

 struct trnt{

     int minval;

     int to;

     int h;

     int lzt;

 }tr[];

 int cnt;

 int tot;

 lnt ans;

 int n;

 int a[];

 std::map<int,int>M;

 std::vector<int>v[];

 bool cmp(pnt x,pnt y)

 {

     return x.c>y.c;

 }

 void pushup(int spc)

 {

     tr[spc].minval=std::min(tr[lll].minval,tr[rrr].minval);

     return ;

 }

 void add(int spc,int v)

 {

     tr[spc].minval+=v;

     tr[spc].lzt+=v;

     return ;

 }

 void pushdown(int spc)

 {

     if(tr[spc].lzt)

     {

         add(lll,tr[spc].lzt);

         add(rrr,tr[spc].lzt);

         if(!tr[spc].to)tr[spc].lzt=;

     }

     return ;

 }

 void build(int l,int r,int spc)

 {

     if(l==r)

     {

         tr[spc].h=;

         tr[spc].to=l;

         if(v[l].size())tr[spc].minval=v[l][];

         else tr[spc].minval=0x3f3f3f3f;

         return ;

     }

     int mid=(l+r)>>;

     build(l,mid,lll);

     build(mid+,r,rrr);

     pushup(spc);

     return ;

 }

 void update(int l,int r,int ll,int rr,int spc)

 {

     if(l>rr||ll>r)return ;

     if(ll<=l&&r<=rr)

     {

         add(spc,-);

         return ;

     }

     pushdown(spc);

     int mid=(l+r)>>;

     update(l,mid,ll,rr,lll);

     update(mid+,r,ll,rr,rrr);

     pushup(spc);

     return ;

 }

 void check(int spc,int V)

 {

     if(tr[spc].minval>)return ;

     if(tr[spc].to)

     {

         ans=(ans+V)%Mod;

         tr[spc].h++;

         int i=tr[spc].to;

         if(tr[spc].h>=v[i].size())tr[spc].minval=0x3f3f3f3f;

         else{

             tr[spc].minval=v[i][tr[spc].h]+tr[spc].lzt;

         }

         return ;

     }

     pushdown(spc);

     check(lll,V);

     check(rrr,V);

     pushup(spc);

     return ;

 }

 int main()

 {

     scanf("%d",&n);

     P.Insert(),C.Insert(),L.Insert(),R.Insert();

     p[].sta();

     for(int i=;i<=n;i++)

     {

         p[i].no=i;

         p[i].p=P.S(p[i-].p,i);

         p[i].l=L.S(p[i-].l,i);

         p[i].r=R.S(p[i-].r,i);

         p[i].c=C.S(p[i-].c,i);

         a[++cnt]=p[i].l;

         a[++cnt]=p[i].r;

         a[++cnt]=p[i].p;

     }

     a[++cnt]=p[].l;

     a[++cnt]=p[].r;

     a[++cnt]=p[].p;

     std::sort(a+,a+cnt+);a[]=-;

     for(int i=;i<=cnt;i++)

     {

         if(M.find(a[i])==M.end())M[a[i]]=++tot;

     }

     for(int i=;i<=n;i++)

     {

         p[i].l=M[p[i].l];

         p[i].r=M[p[i].r];

         p[i].p=M[p[i].p];

         v[p[i].p].push_back(i);

     }

     for(int i=;i<=n;i++)p[i].ch();

     build(,tot,);

     std::sort(p+,p+n+,cmp);

     for(int i=;i<=n;i++)

     {

         update(,tot,p[i].l,p[i].r,);

         check(,p[i].c);

     }

     printf("%lld\n",(ans%Mod+Mod)%Mod);

     return ;

 }

相关阅读

目录[+]