NOIp2018集训test-9-4

老张让我们2.5h考NOI%你题，喵喵喵？

因为今（我）天（实）的（在）题（太）鬼（弱）畜（了）了，我还只改了t1。

Problem A. reorder

考试的时候大家都写了最长不降子序列，然后全员10分，就很开心。

考虑中间一段不降的序列不变，然后剩余的一部分往前放一部分往后方，答案就是n-这段序列的长度

调一下第2组数据，发现直接求最长不降子序列是错的，因为可能在最长不降子序列中间有一部分没有被选的数，权值是在最长不降子序列的最小值和最大值之间的。

所以正确的答案只能是这样的

中间一段不降序列，其余点都在这一段最高点上面或者最低点下面(可以共线)

排序之后双指针扫就好了

注意直接扫会漏掉的部分，红色的部分要通过二分求出

一开始我只二分了下面没有二分上面，但是题目数据是用脚造的，就过了，wys大佬告诉我之后，我随手造了一组数据就把之前的代码×了

9

1 1 4 2 3 4 4 5 5

改过后的代码

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int N=1e6+;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n;

 vector<int>vc[N],vc2[N];

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

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

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 struct node {

     int a,pos;

     friend bool operator <(const node&A,const node&B) {

         return A.a>B.a||(A.a==B.a&&A.pos>B.pos);

     }

 }p[N];

 #define ANS

 int main() {

 #ifdef ANS

     freopen("reorder.in","r",stdin);

     freopen("reorder.out","w",stdout);

 #endif

     read(n);

     For(i,,n) {

         read(p[i].a); p[i].pos=i;

         vc[p[i].a].push_back(i);

     }

     Rep(i,n,) vc2[p[i].a].push_back(n-i+);

     sort(p+,p+n+);

     int ans=n;

     for(int l=,r=;l<=n;) {

         while(r+<=n&&p[r+].pos<p[r].pos) r++;

         int ll=l,rr=r;

         if(ll->=) {

             int tt=lower_bound(vc2[p[l-].a].begin(),vc2[p[l-].a].end(),n-p[l].pos+)-vc2[p[l-].a].begin();

             ll=ll-tt;

         }

         if(r+<=n) {

             int tt=lower_bound(vc[p[r+].a].begin(),vc[p[r+].a].end(),p[r].pos)-vc[p[r+].a].begin();

             rr=r+tt;

         }

         ans=min(ans,n-(rr-ll+));

         l=r+; r=l;

     }

     printf("%d\n",ans);

     Formylove;

 }

 /*

 9

 1 1 4 2 3 4 4 5 5

 */

其实这个仍然漏掉了一种情况，就是在仅有两排的情况下，其实是可以这样选的，

需要枚举中间的分界线，我一开始以为这种情况可以某一块选完来等价替代，就把wys大佬和我自己糊弄到了，但是lyc巨佬发现，因为点的密度不同，所以是不能替换的。这部分代码我懒得写了。

-----------------------------------------9-20upd-----------------------------------------

Problem B. path

题解是spfa转移凸包，虽然我并不知道这个复杂度怎么证明。但是llj巨强无比，自适应辛普森水过了这道题。

平常自适应辛普森是eps递归减小的，但是这里这样的话会炸，所以一直用的同一个eps。

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int N=,M=;

 typedef long long LL;

 typedef long double db;

 using namespace std;

 int n,m,s,t,x[M],y[M];

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

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

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 int ecnt,fir[N],nxt[M],to[M];

 db val[N];

 void add(int u,int v) {

     nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v;

     nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u;

 }

 queue<int>que;

 db dis[N];

 int vis[N];

 #define inf 1e18

 #define EPS 1e-5

 int dcmp(db x) { return fabs(x)<=EPS?:(x>?:-); }

 db spfa() {

     que.push(t);

     For(i,,n) dis[i]=inf;

     dis[s]=;

     que.push(s);

     while(!que.empty()) {

         int x=que.front();

         que.pop(); vis[x]=;

         for(int i=fir[x];i;i=nxt[i]) {

             if(dcmp(dis[to[i]]-dis[x]-val[i])>) {

                 dis[to[i]]=dis[x]+val[i];

                 if(!vis[to[i]]) {

                     vis[to[i]]=;

                     que.push(to[i]);

                 }

             }

         }

     }

     return dis[t];

 }

 double f(double a) {

     For(i,,m) {

         val[i*]=a*x[i]+(1.0-a)*y[i];

         val[i*-]=val[i*];

     }

     return spfa();

 }

 double sim(double x,double y) {

     double mid=((x+y)/2.0);

     return  (y-x)/6.0*(f(x)+4.0*f(mid)+f(y));

 }

 double calc(double l,double r) {

     double mid=((l+r)/2.0);

     double tp=sim(l,mid)+sim(mid,r),tpp=sim(l,r);

     if(dcmp(tp-tpp)==) return tp+(tp-tpp)/15.0;

     else return calc(l,mid)+calc(mid,r);

 }

 /*

 double calc(double l,double r) {

     double mid=((l+r)/2.0);

     db ls=f(l),rs=f(r),ms=f(mid);

     if(fabs(ls+rs-ms*2.0)<=EPS) return ms*(r-l);

     else return calc(l,mid)+calc(mid,r);

 }

 */

 #define ANS

 int main() {

 #ifdef ANS

     freopen("path.in","r",stdin);

     freopen("path.out","w",stdout);

 #endif

     read(n); read(m); read(s); read(t);

     For(i,,m) {

         int u,v;

         read(u); read(v);

         add(u,v);

         read(x[i]); read(y[i]);

     }

     db ans=calc(,);

     printf("%Lf\n",ans);

     Formylove;

 }

巴特西

NOIp2018集训test-9-4

最新文章

热门文章