csp-s模拟测试44「D·E·F」

用心出题,用脚造数据

乱搞场

 1 #include<bits/stdc++.h>

 2 #define re register

 3 #define int long long

 4 #define inf 0x7ffffffffffffff

 5 using namespace std;

 6 int n,a[100010],b[100010],ans=inf;

 7 double st,ed;

 8 inline int read(){

 9     re int a=0,b=1; re char ch=getchar();

10     while(ch<'0'||ch>'9')

11         b=(ch=='-')?-1:1,ch=getchar();

12     while(ch>='0'&&ch<='9')

13         a=(a<<3)+(a<<1)+(ch^48),ch=getchar();

14     return a*b;

15 }

16 inline int max(re int x,re int y){if(x>y) return x; return y;}

17 inline int min(re int x,re int y){if(x<y) return x; return y;}

18 inline void dfs(re int x,re int l,re int r,re int ll,re int rr){

19     if(1ll*(r-l)*(rr-ll)>ans) return ;

20     if(x>n){

21         ans=1ll*(r-l)*(rr-ll);

22         ed=clock();

23         if((ed-st)/1e6>=1.99){

24             printf("%lld\n",ans);

25             exit(0);

26         }

27         return ;

28     }

29     dfs(x+1,max(l,a[x]),min(r,a[x]),max(ll,b[x]),min(rr,b[x]));

30     dfs(x+1,max(l,b[x]),min(r,b[x]),max(ll,a[x]),min(rr,a[x]));

31 }

32 signed main(){

33 //    freopen("in.txt","r",stdin);

34     n=read();if(n==1){puts("1");return 0;}

35     for(re int i=1;i<=n;++i){

36         a[i]=read(),b[i]=read();

37         if(a[i]<b[i]) a[i]^=b[i]^=a[i]^=b[i];

38     }

39     st=clock();

40     dfs(1,0,inf,0,inf);

41     printf("%lld\n",ans);

42     return 0;

43 }

随机化

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<algorithm>

 4 #include<cstring>

 5 #include<bits/stdc++.h>

 6 #define reg register

 7 using namespace std;

 8 typedef long long ll;

 9 const int maxn=1e5+5,INF=2e9;

10 inline void read(int &x)

11 {

12     x=0;char c=getchar();

13     while(c<'0'||c>'9') c=getchar();

14     while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();

15 }

16 ll ans;

17 int S,T,n,tot,L[maxn][2],R[maxn][2],L2[2],R2[2],tmp[2],yet[maxn];

18 struct ball{

19     int x[2];

20 }c[maxn];

21 struct wh{

22     int x,id,f;

23     bool friend operator < (const wh a,const wh b) {return a.x<b.x;}

24 }g[maxn<<1];

25 void dfs(int x)

26 {

27     T=clock();

28     if(T-S>1500000) {printf("%lld\n",ans);exit(0);}

29     if(x!=1&&1LL*(L[x-1][1]-L[x-1][0])*(R[x-1][1]-R[x-1][0])>ans) return ;

30     if(x==n+1) {ans=1LL*(L[x-1][1]-L[x-1][0])*(R[x-1][1]-R[x-1][0]);return ;}

31     if(c[x].x[0]>c[x].x[1]) swap(c[x].x[0],c[x].x[1]);

32     for(reg int j=0;j<=1;++j)

33     {

34         L[x][0]=min(L[x-1][0],c[x].x[j]);

35         L[x][1]=max(L[x-1][1],c[x].x[j]);

36         R[x][0]=min(R[x-1][0],c[x].x[j^1]);

37         R[x][1]=max(R[x-1][1],c[x].x[j^1]);

38         dfs(x+1);

39     }

40 }

41 int main()

42 {

43     srand(time(NULL));

44     S=clock();

45 //    freopen("ans.in","r",stdin);

46 //    freopen("b.out","w",stdout);

47     read(n);

48     for(reg int i=1;i<=n;++i)

49     {

50         read(c[i].x[0]),read(c[i].x[1]);

51         g[++tot]=(wh){c[i].x[0],i,0};

52         g[++tot]=(wh){c[i].x[1],i,1};

53     }

54     reverse(c+1,c+n+1);

55     sort(g+1,g+tot+1);

56     ans=1e18;ans+=5;

57     int l=1,r=tot,k=0;

58     memset(yet,0xFF,sizeof(yet));

59     while(k<n)

60     {

61         while(yet[g[l].id]!=-1) ++l;

62         yet[g[l].id]=g[l].f;++k;

63         if(k==n) break;

64         while(yet[g[r].id]!=-1) --r;

65         yet[g[r].id]=g[r].f;++k;

66     }

67     L[0][0]=R[0][0]=L2[0]=R2[0]=INF;

68     for(reg int i=1;i<=n;++i)

69     {

70         L2[0]=min(L2[0],c[i].x[yet[i]]);

71         L2[1]=max(L2[1],c[i].x[yet[i]]);

72         R2[0]=min(R2[0],c[i].x[yet[i]^1]);

73         R2[1]=max(R2[1],c[i].x[yet[i]^1]);

74     }

75     ans=1LL*(L2[1]-L2[0])*(R2[1]-R2[0]);

76     dfs(1);

77     printf("%lld\n",ans);

78     return 0;

79 }

clock

垃圾zzn当然什么也不会啦,乱搞什么也没打

D

考试时想到正解,没打,觉得这仅仅是个简单的剪枝,没想到啊

题意

求$(r-l+1)*gcd(a[l],a[l+1],.....,a[r])$最大值

题解

垃圾zzn没打正解,类正解多$log$用来二分了,常数较小

$gcd$总需要求,求次数太多了

考虑二分,维护$gcd$从$mid$前缀和后缀和

这样你就有$50$分了

考虑$gcd$变化次数小于是维护单调队列,很简单

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define ll long long

 4 #define A 333333

 5 ll a[A],suml[A],sumr[A],dll[A],dlr[A];

 6 ll ans=0,n;

 7 ll gcd(ll x,ll y){

 8     if(y==0) return x;

 9     return gcd(y,x%y);

10 }

11 void solve(ll l,ll r){

12     if(l==r) return ;

13     ll mid=(l+r)>>1,rnow=mid+1,lnow=mid;

14     suml[lnow]=a[lnow],sumr[rnow]=a[rnow];

15     dll[0]=0,dlr[0]=0;

16     while(lnow>l){

17         lnow--;

18         suml[lnow]=gcd(suml[lnow+1],a[lnow]);

19         if(suml[lnow]!=suml[lnow+1])

20             dll[++dll[0]]=lnow+1;

21     }

22     dll[++dll[0]]=l;

23     while(rnow<r){

24         rnow++;

25         sumr[rnow]=gcd(sumr[rnow-1],a[rnow]);

26         if(sumr[rnow]!=sumr[rnow-1])

27             dlr[++dlr[0]]=rnow-1;

28     }

29     dlr[++dlr[0]]=r;

30     for(ll lh=1;lh<=dll[0];lh++)

31         for(ll rh=1;rh<=dlr[0];rh++){

32             ll nowl=dll[lh],nowr=dlr[rh];

33             ll g=gcd(suml[nowl],sumr[nowr]);

34 //            printf("nowl=%lld nowr=%lld =%lld\n",dll[lh],dlr[rh],g*(nowr-nowl+1));

35             if(g==1) break;

36             ans=max(ans,g*(nowr-nowl+1));

37         }

38     ans=max(ans,gcd(suml[l],sumr[r])*(r-l+1));

39     solve(l,mid);solve(mid+1,r);

40 }

41 //10 10 101 10 10

42 int main(){

43 //    freopen("da.in","r",stdin);

44 //    freopen("ans.sol","w",stdout);

45     scanf("%lld",&n);

46     for(ll i=1;i<=n;i++){

47         scanf("%lld",&a[i]);

48     }

49     solve(1,n);

50     printf("%lld\n",ans);

51 }

E

这个题真的很迷

题解

垃圾zzn考试时打的第二个贪心,然后只有$60$分,事实上单纯第一个贪心就可以$100$分,数据特别水,第一个贪心明明连样例都过不去

没遇到数据这么水的,

正确性垃圾zzn当然不会验证啦

代码也懒的放了

F

题解

0分算法

直接暴力$dp$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define ll long long

 4 ll f[2][2019][2019],w[2019];

 5 ll a,b,n,q;

 6 int main(){

 7     scanf("%lld%lld%lld%lld",&n,&q,&a,&b);

 8     memset(f,0x7f,sizeof(f));

 9     for(ll i=1;i<=q;i++)

10         scanf("%lld",&w[i]);

11     f[1][a][w[1]]=abs(b-w[1]);

12     f[1][w[1]][b]=abs(a-w[1]);

13     for(ll i=2;i<=q;i++){

14         memset(f[i&1],0x7f,sizeof(f[i&1]));

15         for(ll j=1;j<=n;j++){

16         f[i&1][j][w[i]]=min(f[i&1][j][w[i]],f[(i-1)&1][j][w[i-1]]+abs(w[i]-w[i-1]));//w[i-1]移动到w[i]

17         f[i&1][w[i]][w[i-1]]=min(f[i&1][w[i]][w[i-1]],f[(i-1)&1][j][w[i-1]]+abs(j-w[i]));//j移动到w[i]

18         f[i&1][w[i]][j]=min(f[i&1][w[i]][j],f[(i-1)&1][w[i-1]][j]+abs(w[i]-w[i-1]));//w[i-1]移动到w[i]

19         f[i&1][w[i-1]][w[i]]=min(f[i&1][w[i-1]][w[i]],f[(i-1)&1][w[i-1]][j]+abs(j-w[i]));//j移动到w[i]

20         }

21     }

22     ll ans=0x7fffffff;

23     for(ll j=1;j<=n;j++){

24         ans=min(ans,min(f[q&1][j][w[q]],f[q&1][w[q]][j]));

25     }

26     printf("%lld\n",ans);

27 }

30分算法

有一维一定是$w[i]$

考虑去掉一维

$f[i][j]=f[i-1][j]+abs(w[i]-w[i-1])$另一个指针从$w[i-1]$移动到$w[i]$

$f[i][w[i-1]]=f[i-1][j]+abs(j-w[i])$从$j$移动到$w[i]$

#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll f[2][2019],w[2019];

ll a,b,n,q;

int main(){

    scanf("%lld%lld%lld%lld",&n,&q,&a,&b);

    memset(f,0x7f,sizeof(f));

    for(ll i=1;i<=q;i++)

        scanf("%lld",&w[i]);

    f[1][a]=abs(b-w[1]);

    f[1][b]=abs(a-w[1]);

    for(ll i=2;i<=q;i++){

        memset(f[i&1],0x7f,sizeof(f[i&1]));

        for(ll j=1;j<=n;j++){

        f[i&1][j]=min(f[i&1][j],f[(i-1)&1][j]+abs(w[i]-w[i-1]));

        f[i&1][w[i-1]]=min(f[i&1][w[i-1]],f[(i-1)&1][j]+abs(j-w[i]));

        f[i&1][j]=min(f[i&1][j],f[(i-1)&1][j]+abs(w[i]-w[i-1]));

        f[i&1][w[i-1]]=min(f[i&1][w[i-1]],f[(i-1)&1][j]+abs(j-w[i]));

        }

    }

    ll ans=0x7fffffff;

    for(ll j=1;j<=n;j++){

        ans=min(ans,min(f[q&1][j],f[q&1][j]));

    }

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

}

100分算法

两个转移式子

$f[i][j]=f[i-1][j]+abs(w[i]-w[i-1])$

$f[i][w[i-1]]=f[i-1][j]+abs(j-w[i])$

发现第一个式子就是区间加,第二个式子单点赋值

单点赋值赋的就是$min$,有个$abs$怎么办维护$f-j$最小值和$f+j$最小值

        memset(askmin,0x7f,sizeof(askmin));

        seg_min(1,1,w[i],2);//p[i]比当前点大,那么取p[i]-l

        seg_min(1,w[i],n,1);//p[i]比当前值小,取l-p[i]

    //    printf("ask=%lld %lld\n",askmin[1],askmin[2]);

        askmin[1]-=w[i];

        askmin[2]+=w[i];

        ll nowmin=min(askmin[1],askmin[2]);

线段树优化一下

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define ll long long

 4 ll w[1010101],askmin[4];

 5 ll a,b,n,q;

 6 struct tree{

 7     ll l,r,f,minn[4];

 8 }tr[1010101];

 9 void up(ll x){

10     for(ll i=1;i<=3;i++)

11         tr[x].minn[i]=min(tr[x<<1].minn[i],tr[x<<1|1].minn[i]);

12 }

13 void down(ll x){

14     tr[x<<1].f+=tr[x].f;

15     tr[x<<1|1].f+=tr[x].f;

16     for(ll i=1;i<=3;i++)

17         tr[x<<1].minn[i]+=tr[x].f,tr[x<<1|1].minn[i]+=tr[x].f;

18     tr[x].f=0;

19 }

20 void built(ll x,ll l,ll r){//printf("builx=%lld\n",x);

21     tr[x].l=l,tr[x].r=r;

22     if(l==r){

23         if(l==a||l==b){

24             tr[x].minn[3]=abs(a+b-l-w[1]);

25 //            printf("tr3=%lld\n",tr[x].minn[3]);

26             tr[x].minn[1]=tr[x].minn[3]+l;

27             tr[x].minn[2]=tr[x].minn[3]-l;

28         }

29         else tr[x].minn[1]=tr[x].minn[2]=tr[x].minn[3]=0x7ffffffffff;

30         return ;

31     }

32     ll mid=(l+r)>>1;

33     built(x<<1,l,mid);

34     built(x<<1|1,mid+1,r);

35     up(x);

36 }

37 void seg_min(ll x,ll l,ll r,ll zl){

38 //    printf("l=%lld r=%lld\n",l,r);

39     if(tr[x].l>=l&&tr[x].r<=r){

40 //        printf("tr[%lld].minn[%lld]=%lld l=%lld r=%lld\n",x,zl,tr[x].minn[zl],tr[x].l,tr[x].r);

41         askmin[zl]=min(askmin[zl],tr[x].minn[zl]);

42         return ;

43     }

44     down(x);

45     ll mid=(tr[x].l+tr[x].r)>>1;

46     if(mid>=l) seg_min(x<<1,l,r,zl);

47     if(mid<r) seg_min(x<<1|1,l,r,zl);

48     up(x);

49 }

50 void add(ll x,ll point,ll val){

51     if(tr[x].l==tr[x].r){

52         tr[x].minn[3]=min(tr[x].minn[3],val);

53         tr[x].minn[1]=tr[x].minn[3]+tr[x].l;

54         tr[x].minn[2]=tr[x].minn[3]-tr[x].l;

55         return ;

56     }

57     down(x);

58     ll mid=(tr[x].l+tr[x].r)>>1;

59     if(point<=mid) add(x<<1,point,val);

60     else add(x<<1|1,point,val);

61     up(x);

62 }

63 int main(){

64     scanf("%lld%lld%lld%lld",&n,&q,&a,&b);

65     for(ll i=1;i<=q;i++)

66         scanf("%lld",&w[i]);

67     built(1,1,n);

68     for(ll i=2;i<=q;i++){

69         memset(askmin,0x7f,sizeof(askmin));

70         seg_min(1,1,w[i],2);//p[i]比当前点大,那么取p[i]-l

71         seg_min(1,w[i],n,1);//p[i]比当前值小,取l-p[i]

72     //    printf("ask=%lld %lld\n",askmin[1],askmin[2]);

73         askmin[1]-=w[i];

74         askmin[2]+=w[i];

75         ll nowmin=min(askmin[1],askmin[2]);

76     //    printf("nowmin=%lld\n",nowmin);

77         tr[1].f+=abs(w[i]-w[i-1]);

78         for(ll j=1;j<=3;j++)

79             tr[1].minn[j]+=abs(w[i]-w[i-1]);

80         add(1,w[i-1],nowmin);

81     }

82     printf("%lld\n",tr[1].minn[3]);

83 }

巴特西

csp-s模拟测试44「D·E·F」

D

题意

题解

E

这个题真的很迷

题解

F

题解

最新文章

热门文章