首页 > 其他 > 详细

CSPS模拟75&76

时间:2019-10-17 13:07:52      阅读:50      评论:0      收藏:0      [点我收藏+]

感觉自己还是太菜了。。。

最近考试一直想不出来正解。难受(然而蒟蒻的博客没人看也要不来小猪peiqi的图)

模拟75:血炸。。。

考场上推了快两个小时的T1式子,然后心态炸裂,然后我也不知道自己干了什么,反正T1瞎打了一发,没过小样例

然后康T3,qj了部分分,不会打暴力,瞎码了一发,没过小样例。然后赶紧开T2,然后码了半天读入然后qj掉部分分

然后就没有然后了,然后考试就结束了,然后我就垫底了。然后改题该了一天。。。

注意考试时间和考试心态,不能慌

题确实挺好

T1:正解为凸包,然后卡精,把输入的a和b取倒数得到z=Ax+By,然后维护一个左下凸包就可以了。

技术分享图片
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<vector>
  7 #define N 300050
  8 //#define double long double
  9 using namespace std;
 10 const double eps=0;
 11 vector<int>v[N];
 12 struct node{int a,b,id;}q[N];
 13 bool cmp(const node &x,const node &y)
 14 {
 15     return x.a==y.a?x.b>y.b:x.a>y.a;
 16 }
 17 inline int read()
 18 {
 19     int s=0;char c=getchar();
 20     while(c<0||c>9)c=getchar();
 21     while(c>=0&&c<=9)s=s*10+c-0,c=getchar();
 22     return s;
 23 }
 24 bool check(double a,double b)
 25 {
 26     double k;
 27     if(a>b)k=a-b;
 28     else k=b-a;
 29     return b<eps;
 30 }
 31 inline double work1(double x1,double x2,double x3,double y1,double y2,double y3)
 32 {
 33     return (y1-y2)*(x3-x2)/y2/y1/x2/x3;
 34 }
 35 inline double work2(double x1,double x2,double x3,double y1,double y2,double y3)
 36 {
 37     return (x2-x1)*(y2-y3)/y2/y3/x2/x1;
 38 }
 39 int n;
 40 int ans[N];
 41 priority_queue<int>qq;
 42 int d[N],ba;
 43 int main()
 44 {
 45 //    freopen("da.in","r",stdin);
 46     n=read();
 47     for(int i=1;i<=n;++i)
 48     {
 49         q[i].a=read();
 50         q[i].b=read();
 51         q[i].id=i;
 52     }
 53     sort(q+1,q+n+1,cmp);
 54     int ma2=0,ma1=0;
 55     for(int i=1;i<=n;++i)
 56     {
 57         if(q[i].b>ma2)
 58         {
 59             ma2=q[i].b;ma1=q[i].a;
 60             ans[++ans[0]]=i;
 61         }
 62         else if(q[i].b==ma2)
 63         {
 64             if(ma1==q[i].a)ans[++ans[0]]=i;
 65         }
 66     }
 67     for(int i=1,t,p;i<=ans[0];++i)
 68     {
 69         double a1,a2,a3,b1,b2,b3;
 70         double x1,x2,x3,y1,y2,y3;
 71         t=ans[i];
 72         a1=1.0/q[t].a;b1=1.0/q[t].b;
 73         x1=q[t].a;y1=q[t].b;
 74         if(!ba){
 75             d[++ba]=t;
 76             continue;
 77         }
 78         while(ba>1)
 79         {
 80             a2=1.0/q[d[ba]].a;
 81             b2=1.0/q[d[ba]].b;
 82             x2=q[d[ba]].a;y2=q[d[ba]].b;
 83             if(a1>a2&&b1>b2)break;
 84             if(x1==x2&&y1==y2){v[d[ba]].push_back(q[t].id);break;}
 85             a3=1.0/q[d[ba-1]].a;
 86             b3=1.0/q[d[ba-1]].b;
 87             x3=q[d[ba-1]].a;y3=q[d[ba-1]].b;
 88             if(check(work1(x1,x2,x3,y1,y2,y3),work2(x1,x2,x3,y1,y2,y3)))
 89             {
 90                 d[++ba]=t;break;
 91             }
 92             if(work1(x1,x2,x3,y1,y2,y3)-work2(x1,x2,x3,y1,y2,y3)>eps)
 93             {
 94                 --ba;
 95             }
 96             else
 97             {
 98                 d[++ba]=t;break;
 99             }
100         }
101         if(ba==1)
102         {
103             d[++ba]=t;
104         }
105     }
106     for(int i=1;i<=ba;++i)
107     {
108         qq.push(-q[d[i]].id);
109         for(int j=0;j<v[d[i]].size();++j)
110         {
111             qq.push(-v[d[i]][j]);
112         }
113     }
114         
115     while(!qq.empty()){
116         printf("%d ",-qq.top());
117         qq.pop();
118     }
119     return 0;
120 }
View Code

T2:注意输入。。。正解为Gauss消元,把答案矩阵的系数消掉,则最后等式右面就是答案的相反数

证明为啥可以直接进行高斯消元,首先答案行可以表示为每个已知行乘以一个系数相加得到。那么感性理解一下,考虑每个已知方程的贡献,当它下传时,下面的方程其实已经

累积了该方程的贡献,而题目又保证有解,所以考虑完每个方程后最后答案方程的系数一定会被消完

技术分享图片
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<cmath>
  7 #define N 300
  8 #define ull unsigned long long
  9 using namespace std;
 10 int n;
 11 ull p=13331;
 12 ull po[N];
 13 ull lsh[190050];
 14 int ls;
 15 int a[N];
 16 int pd[N];
 17 double c[N][N],cc[N];
 18 struct node{
 19     ull ha;
 20     int t;
 21     double x;
 22 }b[N][N];
 23 void init()
 24 {
 25     sort(lsh+1,lsh+ls+1);
 26     ls=unique(lsh+1,lsh+ls+1)-lsh-1;
 27     for(int i=1;i<=n;++i)
 28     {
 29         for(int j=1;j<a[i];++j)
 30         {
 31             b[i][j].t=lower_bound(lsh+1,lsh+ls+1,b[i][j].ha)-lsh;
 32             c[i][b[i][j].t]=b[i][j].x;
 33         }
 34         cc[i]=b[i][a[i]].x;
 35     }
 36     cc[n]=0;
 37 }
 38 double ks[N];
 39 void pr()
 40 {
 41     for(int i=1;i<=n;++i)
 42     {
 43         for(int j=1;j<=ls;++j)
 44             printf("%.1lf  ",c[i][j]);
 45         printf("%.1lf\n",cc[i]);
 46     }
 47     puts("");
 48 }
 49 void Gauss()
 50 {
 51     const int nn=n-1;
 52     int ts=1;
 53 //    pr();
 54     //while(1)
 55     for(int o=1;o<=3;++o)
 56     {
 57         for(int i=1,t;i<=ls&&ts<n;++i)
 58         {
 59             if(!c[n][i])continue;
 60             t=ts;
 61             for(int j=t+1;j<n;++j){
 62                 if(fabs(c[j][i])>fabs(c[t][i])){
 63         //            printf("i:%d j::::%d\n",i,j);
 64                     for(int k=1;k<=ls;++k)
 65                         swap(c[t][k],c[j][k]);
 66                     swap(cc[t],cc[j]);
 67                 }
 68             }
 69             if(!c[t][i])continue;
 70             for(int j=1;j<=n;++j)
 71             {
 72                 if(!c[j][i]||j==t)continue;
 73                 double p=c[j][i]/c[t][i];
 74                 for(int k=1;k<=ls;++k)
 75                     c[j][k]-=c[t][k]*p;
 76                 cc[j]-=cc[t]*p;
 77             }
 78             ++ts;
 79 //            pr();
 80         }
 81         int ok=1;
 82         for(int i=1;i<=ls;++i){if(c[n][i])ok=0;}
 83         if(ok)break;
 84 //        pr();
 85     }
 86     if(fabs(cc[n])<0.0000000001){puts("0.0");return;}
 87     printf("%.1lf\n",-cc[n]);
 88 //    pr();
 89 }
 90 int main()
 91 {
 92 //    freopen("knight2.in","r",stdin);
 93     scanf("%d",&n);++n;
 94     for(int i=1,j,pd;i<=n;++i)
 95     {
 96         double x;char c;
 97         j=0;pd=1;
 98         while(1){
 99             ++j;
100             scanf("%lf",&x);
101             b[i][j].x=x*pd;
102             c=getchar();
103             while(c<A||c>Z)c=getchar();
104             while(c!= ){
105                 b[i][j].ha=b[i][j].ha*p+c;
106                 c=getchar();
107             }
108             lsh[++ls]=b[i][j].ha;
109             while(c!==&&c!=+&&c!=H)c=getchar();
110             if(c===)pd=-1;
111             else if(c==H)
112             {
113                 ++j;if(i==n)break;
114                 while(c!==)c=getchar();
115                 scanf("%lf",&b[i][j].x);
116                 break;
117             }
118         }
119         a[i]=j;
120     }
121     init();
122     Gauss();
123 }
View Code

T3:把老司机按照x排序,第一问即为最长上升子序列。

第二问考虑如何构造,发现最优情况下所有的老司机构成森林,扫描到当前老司机,考虑接在哪个lsj后面,

则可以倍增法对符合条件的lsj求lca,顺便维护一下覆盖的链的最值即可。

技术分享图片
  1 #include<bits/stdc++.h>
  2 #define N 100050
  3 #define LL long long
  4 using namespace std;
  5 const LL inf=200000000;
  6 int n,k;
  7 LL b[N],c[N];
  8 int dp[N];
  9 struct node{LL x,a;int id;}q[N];
 10 bool cmp(const node &c,const node &d){return c.x<d.x;}
 11 inline int check(const LL t)
 12 {
 13     for(int i=1;i<=n;++i)b[i]=q[i].x*2+t*q[i].a;
 14     int ret=1;c[1]=b[1];
 15     for(int i=2,po;i<=n;++i)
 16     {
 17         if(b[i]>c[ret])
 18         {
 19             c[++ret]=b[i];
 20             continue;
 21         }
 22         if(b[i]<c[1]){
 23             c[1]=b[i];
 24         }
 25         else{
 26             po=lower_bound(c+1,c+ret+1,b[i])-c;
 27             c[po]=b[i];
 28         }
 29     }
 30     return ret;
 31 }
 32 int fa[N][22],mn[N][22];
 33 int rt[N],tot;
 34 int lc[N*30],rc[N*30],mi[N*30];
 35 inline int getmin(const int xx,const int yy)
 36 {
 37     int x=xx,y=yy,mx=xx,my=yy;
 38     for(int i=18;~i;--i)
 39     {
 40         if(fa[x][i]==fa[y][i])continue;
 41         mx=min(mx,mn[x][i]);
 42         my=min(my,mn[y][i]);
 43         x=fa[x][i];y=fa[y][i];
 44     }
 45 //    printf("xx:%d yy:%d mx:%d my:%d x:%d y:%d\n",xx,yy,mx,my,x,y);
 46     if(mx<my)return xx;
 47     return yy;
 48 }
 49 inline int upd(int x,int y)
 50 {
 51     if(!x||!y)return x|y;
 52     return getmin(x,y);
 53 }
 54 void add(int &g,int l,int r,int pos,int id)
 55 {
 56     if(!g)g=++tot;
 57     if(l==r){mi[g]=id;return;}
 58     const int m=l+r>>1;
 59     if(pos<=m)add(lc[g],l,m,pos,id);
 60     else add(rc[g],m+1,r,pos,id);
 61     mi[g]=upd(mi[lc[g]],mi[rc[g]]);
 62 }
 63 int ask(int g,int l,int r,int pos)
 64 {
 65     if(!g)return 0;
 66     if(r<pos)return mi[g];
 67     if(l>=pos)return 0;
 68     const int m=l+r>>1;
 69     return upd(ask(lc[g],l,m,pos),ask(rc[g],m+1,r,pos));
 70 }
 71 int ks[N];
 72 inline void getans(int ans)
 73 {
 74     const LL t=1ll*ans*ans;
 75     for(int i=1;i<=n;++i)c[i]=b[i]=q[i].x*2+t*q[i].a;
 76     sort(c+1,c+n+1);
 77     for(int j=1;j<=n;++j)b[j]=lower_bound(c+1,c+n+1,b[j])-c;
 78     int ret=1;c[1]=b[1];dp[1]=1;
 79     add(rt[1],1,n,b[1],q[1].id);
 80     for(int i=2,po;i<=n;++i)
 81     {
 82         if(b[i]>c[ret])
 83         {
 84             c[++ret]=b[i];dp[i]=ret;
 85             fa[q[i].id][0]=ask(rt[ret-1],1,n,b[i]);
 86             mn[q[i].id][0]=fa[q[i].id][0];
 87             for(int j=1;j<=17;++j)
 88             {
 89                 fa[q[i].id][j]=fa[fa[q[i].id][j-1]][j-1];
 90                 mn[q[i].id][j]=min(mn[q[i].id][j-1],mn[fa[q[i].id][j-1]][j-1]);
 91             }
 92             add(rt[dp[i]],1,n,b[i],q[i].id);
 93         }
 94         else
 95         {    
 96             if(b[i]<c[1])dp[i]=1;
 97             else dp[i]=lower_bound(c+1,c+ret+1,b[i])-c;
 98             c[dp[i]]=b[i];
 99             fa[q[i].id][0]=ask(rt[dp[i]-1],1,n,b[i]);
100             mn[q[i].id][0]=fa[q[i].id][0];
101             for(int j=1;j<=17;++j)
102             {
103                 fa[q[i].id][j]=fa[fa[q[i].id][j-1]][j-1];
104                 mn[q[i].id][j]=min(mn[q[i].id][j-1],mn[fa[q[i].id][j-1]][j-1]);
105             }
106             add(rt[dp[i]],1,n,b[i],q[i].id);
107         }
108 //        printf("i:%d b:%lld dp:%d\n",i,b[i],dp[i]);
109 //        printf("%d %d\n",fa[q[i].id][0],q[i].id);
110     }
111     int an=0;
112     for(int i=n;i>=1;--i)
113         if(dp[i]==k)an=upd(an,q[i].id);
114 //    printf("an:%d\n",an);
115 //    an=5;
116     while(an){
117         ks[++ks[0]]=an;
118         an=fa[an][0];
119     }
120     sort(ks+1,ks+ks[0]+1);
121     for(int i=1;i<=ks[0];++i)
122     {
123         printf("%d\n",ks[i]);
124     }
125 }
126 int main()
127 {
128 //    freopen("da.in","r",stdin);
129     //freopen("my.out","w",stdout);
130     scanf("%d%d",&n,&k);
131     if(k==1){puts("86400\n-1\n");return 0;}
132     for(int i=1;i<=n;++i)
133         scanf("%lld%lld",&q[i].x,&q[i].a),q[i].id=i;
134     sort(q+1,q+n+1,cmp);
135     int l=0,r=86400+1,mid;
136     while(l+1<r)
137     {
138         mid=l+r>>1;
139         if(check(1ll*mid*mid)>=k)l=mid;
140         else r=mid;
141     }
142     cout<<l<<endl;
143 //    cout<<check(1ll*l*l)<<endl;
144     if(check(1ll*l*l)>k+1){puts("-1");return 0;}
145     getans(l);
146     return 0;
147 }
View Code

模拟76:集训时间已过1/3(莫名紧张

T1:构造题,找规律,发现n=a*b显然可以直接构造,n>a*b必然无解,n==a+b-1必然有解,且两个序列共用一个数,n<a+b-1必然无解

剩下的情况按照类似n==a+b-1构造即可

技术分享图片
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #define N 100050
  6 using namespace std;
  7 int n,a,b;
  8 int ans[N];
  9 void work1()
 10 {
 11     puts("Yes");
 12     int al=0;
 13     for(int i=n+1-a;i>=1;i-=a)
 14     {
 15         for(int j=i;j<i+a;++j)
 16         ans[j]=++al;
 17     }
 18     for(int i=1;i<=n;++i)
 19         printf("%d ",ans[i]);
 20     puts("");
 21     return;
 22 }
 23 int dp[N],f[N];
 24 inline bool judge()
 25 {
 26     int an1=0,an2=0;
 27     for(int i=1;i<=n;++i)
 28     {
 29         dp[i]=f[i]=1;
 30         for(int j=1;j<i;++j)
 31         {
 32             if(ans[j]<ans[i])
 33             {
 34                 f[i]=max(f[i],f[j]+1);
 35             }
 36             else
 37             {
 38                 dp[i]=max(dp[i],dp[j]+1);
 39             }
 40         }
 41         an1=max(an1,f[i]);
 42         an2=max(an2,dp[i]);
 43     }
 44     return an1==a&&an2==b;
 45 }
 46 void work2()
 47 {
 48     for(int i=1;i<=n;++i)ans[i]=i;
 49     int ok=0;
 50     do{
 51         if(judge()){ok=1;break;}
 52     }while(next_permutation(ans+1,ans+n+1));
 53     if(!ok){puts("No");return;}
 54     puts("Yes");
 55     for(int i=1;i<=n;++i)printf("%d ",ans[i]);
 56     puts("");
 57 }
 58 void work3()
 59 {
 60     int al=n;
 61     for(int i=1;i<a;++i)
 62         ans[i]=i;
 63     for(int i=a+1;i<=n;++i)
 64     {
 65         ans[i]=al;--al;
 66     }
 67     puts("Yes");
 68     for(int i=1;i<=n;++i)printf("%d ",ans[i]);
 69     puts("");
 70 }
 71 void work4()
 72 {
 73     int al=n-(a+b-1)+1,i,j;
 74     for(i=al;i<al+a-1;++i)
 75         ans[i]=i-al+1;
 76     
 77 //    for(int j=1;j<=n;++j)printf("%d ",ans[j]);puts("");
 78     for(j=n;j>n-b;--j)
 79         ans[i++]=j;
 80     int fr=a,to=n-b,aa=a-1,bb=b-1,k;
 81 //    printf("aa:%d bb:%d\n",aa,bb);
 82     i=n-(a+b-1);
 83 //    printf("i:%d fr:%d to:%d\n",i,fr,to);
 84     while(1)
 85     {
 86     //    printf("i:%d\n",i);
 87         k=max(i-bb+1,1);
 88         for(int j=1;j<=bb;++j)
 89         {
 90             ans[k]=to;
 91             if(fr==to)break;
 92             --to;++k;
 93         }
 94         i-=bb;
 95         if(i<=0)break;
 96     //    if(fr==to)break;//&&ans[k]==to
 97         --aa;
 98         k=max(i-aa+1,1);
 99         for(int j=1;j<=aa;++j)
100         {
101             ans[k]=fr;
102             if(fr==to)break;
103             ++fr;++k;
104         }
105         i-=aa;
106         if(i<=0)break;
107 //        if(fr==to)break;
108         --bb;
109     }
110     puts("Yes");
111     for(int i=1;i<=n;++i)printf("%d ",ans[i]);
112     puts("");
113 }
114 void work()
115 {
116     if(n<=10){work2();return;}
117     if(1ll*a*b==n){work1();return;}
118     if(1ll*a*b<n){puts("No");return;}
119     if(a+b>n+1){puts("No");return;}
120     if(a+b==n+1){work3();return;}
121     work4();return;
122 }
123 int main()
124 {
125     int T;scanf("%d",&T);
126     while(T--)
127     {
128         scanf("%d%d%d",&n,&a,&b);
129         work();
130     }
131 }
View Code

T2:结论题。子任务一:暴力跑背包,二:单调队列优化多重背包,三:暴搜

结论:排序后考虑每个物品的一半和前面所有物品的sum的关系,看有没有断档即可。(摘自DeepinC的blogs

技术分享图片
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define N 100050
 6 using namespace std;
 7 int a[N];
 8 int n,an;
 9 inline void work4()
10 {
11     long long l=(a[1]+1)/2,r=a[1],sum=0;
12     for(int i=2;i<=n;++i)
13     {
14         if((a[i]+1)/2>r+1)
15         {
16             sum+=r-l+1;
17             l=(a[i]+1)/2;
18         }
19         r+=a[i];
20     }
21     sum+=r-l+1;
22     cout<<sum<<endl;
23 }
24 int main()
25 {
26     scanf("%d",&n);
27     for(int i=1;i<=n;++i)scanf("%d",&a[i]);
28     sort(a+1,a+n+1);
29     work4();return 0;
30 }
View Code

T3:考试时一直没想出来怎么搞掉限制,然后skyh大声地在纸上写AK,然后就拼命想正解,然后就想到了,然后就没时间打了,然后skyh就AK了。。。

我们发现先序遍历有很多优美的性质,然后考虑yy它,因为序列递增,把限制拍到序列上,dp[i][j]表示以i为根,子树大小为j的方案数,利用先序遍历和中序遍历的性质进行转移

对每个点记录它后面的中序限制在它前面的最大的点,和它后面的中序限制在它后面的最小的点然后就可以kx地转移了,注意子树大小为1也需要转移

技术分享图片
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define N 450
 6 const int mod=1000000007;
 7 using namespace std;
 8 int a[N];
 9 int n,m,ok;
10 int dp[N][N],f[N][N];
11 void init()
12 {
13     ok=1;
14     for(register int i=400;i;--i){
15         f[i][0]=f[i][1]=1;
16         for(register int j=2;j<=400;++j)
17             for(register int k=0;k<j;++k)
18                 (f[i][j]+=1ll*f[i+1][k]*f[i+1][j-k-1]%mod)%=mod;
19     }
20 }
21 inline void work1()
22 {
23     if(!ok){init();}
24     cout<<f[400-n+1][n]<<endl;
25 }
26 struct node{int x,y;}ed[N][N];
27 int pre[N],las[N];
28 inline void work2()
29 {
30     memset(dp,0,sizeof(dp));
31     dp[n][1]=dp[n][0]=dp[n+1][0]=1;
32     for(int i=n-1;i;--i)
33     {
34         dp[i][0]=1;
35         for(int j=1;j+i-1<=n;++j)
36         {
37             dp[i][j]=0;
38             for(int k=max(pre[i]-i,0);k<las[i]-i&&k<j;++k)
39             {
40                 dp[i][j]+=1ll*dp[i+1][k]*dp[i+k+1][j-k-1]%mod;
41                 if(dp[i][j]>=mod)dp[i][j]-=mod;
42             }
43 //            printf("dp[%d][%d]:%d\n",i,j,dp[i][j]);
44         }
45     }
46     cout<<dp[1][n]<<endl;
47 }
48 int main()
49 {
50 //    freopen("sample.in","r",stdin);
51     int T;scanf("%d",&T);
52     while(T--)
53     {
54         scanf("%d%d",&n,&m);
55         if(!m){work1();continue;}
56         for(int i=1;i<=n;++i)las[i]=n+1,pre[i]=0;
57         for(int i=1,x,y;i<=m;++i){
58             scanf("%d%d",&x,&y);
59             if(y>x)las[x]=min(las[x],y);
60             pre[y]=max(pre[y],x);
61         }
62         int ok=0;
63         for(int i=1;i<=n;++i)
64         {
65             if(pre[i]>=las[i]){
66                 ok=1;break;
67             }
68         }
69         if(ok){puts("0");continue;}
70         work2();
71     }
72 }
View Code

ps:RP守恒,不要太飘

pps:做难题,填坑

 

CSPS模拟75&76

原文:https://www.cnblogs.com/loadingkkk/p/11691278.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!