难度:NOI+?

真实毒瘤

Problem A: Travel in Sugar Country

题意:

题解:

神仙dp,我不想再写一遍了,讨论特别多东西。

代码:

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 101
#define Mod 1000000007
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int d[Max],f[Max][30][51][51][2][2],n,m,k,l,r;
il void add(int &x,ll t)
{
    x=(1ll*x+t)%Mod;
}
signed main()
{
    ll w;
    n=read(),m=read(),k=read();
    for(int i=1;i<n;i++) d[i]=(d[i-1]+read())%m;
    f[0][0][0][0][0][0]=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            for(int sp=0;sp<=k;sp++)
                for(int cnt=0;cnt<=k;cnt++)
                    for(int s=0;s<=1;s++)
                        for(int t=0;t<=1;t++)
                        {
                            if(!f[i][j][sp][cnt][s]) continue;
                            w=f[i][j][sp][cnt][s][t];
                            add(f[i+1][j][sp][cnt][s][t],w);
                            if(sp==k) continue;
                            if(s&&t&&!cnt) continue;
                            r=cnt&1?cnt/2+s:cnt/2;
                            l=cnt-r;
                            add(f[i+1][j][sp+1][cnt][s][t],w*(l+r));
                            if((cnt==2&&s&&t)||cnt>2)
                                add(f[i+1][(j+2*d[i])%m][sp+1][cnt-2][s][t],w*max(l*r-min(l,r),1));
                            if(cnt+2<=k)
                                add(f[i+1][(j-2*d[i]+m+m)%m][sp+1][cnt+2][s][t],w);
                            if(!s)
                            {
                                if(l>=1)
                                    add(f[i+1][(j+d[i])%m][sp+1][cnt-1][1][t],w*max(l-t,1));
                                if(cnt+1<=k)
                                    add(f[i+1][(j-d[i]+m)%m][sp+1][cnt+1][1][t],w);
                            }
                            if(!t)
                            {
                                if(r>=1)
                                    add(f[i+1][(j+d[i])%m][sp+1][cnt-1][s][1],w*max(r-s,1));
                                if(cnt+1<=k)
                                    add(f[i+1][(j-d[i]+m)%m][sp+1][cnt+1][s][1],w);
                            }
                        }
    cout<<f[n][0][k][0][1][1]<<'\n';
}

Problem B: 简单的几何题

题意:

你简单你呢。

CJB小姐姐现在正在学几何。现在她遇到了一个问题,有人给了她一块凸多边形的蛋糕,放在她那带有坐标轴的桌子上。由于蛋糕很重,所以蛋糕无法旋转或者移动。CJB有强迫症,她只想吃矩形的蛋糕。所以她想把这样一块凸多边形的蛋糕裁剪成一个矩形。由于CJB有严重的强迫症,她认为不与坐标轴平行的矩形都是肮脏的,所以她想让你帮她裁剪一个面积最大的矩形蛋糕,且这个矩形的每条边均与坐标轴平行。

题解:

三分套三分

代码:

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define il inline
#define Max 100005
#define eps 1e-5
#define db double
#define rg register
using namespace std;
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
char In[Max],*ss=In,*tt=In;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node
{
    db x,y;
    friend bool operator < (node a,node b)
    {
        return a.x<b.x;
    }
}e[Max],a[Max],b[Max];
int n,cnta,cntb,L,R;
db xl,yl,xr,yr,k;
il db dis(node u,node v,db x)
{
    return u.y+(v.y-u.y)*(x-u.x)/(v.x-u.x);
}
il node calc3(db x)
{
    int u=upper_bound(a+1,a+cnta+1,(node){x,0})-a,v=upper_bound(b+1,b+cntb+1,(node){x,0})-b;
    u=min(u,cnta),v=min(v,cntb);
    //if(u==1||v==1) cout<<x<<' ',puts("QWQWQ!!");
    return (node){dis(a[u-1],a[u],x),dis(b[v-1],b[v],x)};
}
il db calc2(db x)
{
    db rx=x+k;
    node ql=calc3(x),qr=calc3(rx);
    yl=max(ql.x,qr.x),yr=min(ql.y,qr.y);
    return yr-yl;
}
il db calc(db x)
{
    k=x;
    db l=e[L].x,r=e[R].x-k;
    //cout<<l<<endl;
    while(r-l>eps)
    {
        db mid=(r-l)/3.0;
        db midl=l+mid,midr=r-mid;
        if(calc2(midl)>calc2(midr)) r=midr;
        else l=midl;
    }
    xl=l,xr=xl+k;
    return calc2((l+r)*0.5)*k;
}
int main()
{
    n=read();
    for(rg int i=1;i<=n;i++) e[i].x=read(),e[i].y=read();
    L=R=1;
    for(rg int i=1;i<=n;i++) 
    {
        if(e[i].x<e[L].x||(e[i].x==e[L].x&&e[i].y<e[L].y)) L=i;
        if(e[i].x>e[R].x||(e[i].x==e[R].x&&e[i].y<e[R].y)) R=i;
    }
    for(rg int i=L;i!=R;i=(i==1?(n):(i-1))) a[++cnta]=e[i];
    a[++cnta]=e[R];
    L=R=1;
    for(rg int i=1;i<=n;i++) 
    {
        if(e[i].x<e[L].x||(e[i].x==e[L].x&&e[i].y>e[L].y)) L=i;
        if(e[i].x>e[R].x||(e[i].x==e[R].x&&e[i].y>e[R].y)) R=i;
    }
    for(rg int i=L;i!=R;i=(i==n?1:(i+1))) b[++cntb]=e[i];
    b[++cntb]=e[R]; 
    db l=0,r=e[R].x-e[L].x;
    //for(int i=1;i<=cnta;i++) cout<<a[i].x<<' '<<a[i].y<<" qwq1\n";
    //for(int i=1;i<=cntb;i++) cout<<b[i].x<<' '<<b[i].y<<" qwq2\n";
    //cout<<r<<" qwq qwq\n";
    while(r-l>eps)
    {
        db mid=(r-l)/3.0;
        db midl=l+mid,midr=r-mid;
        if(calc(midl)>calc(midr)) r=midr;
        else l=midl;
        //cout<<l<<' '<<r<<" midl:"<<midl<<" midr:"<<midr<<' '<<calc(midl)<<' '<<calc(midr)<<"qwqwq\n";
    }
    //cout<<l<<' '<<r<<endl;
    calc((l+r)*0.5);
    //cout<<calc(l)<<endl;
    printf("%.6lf %.6lf %.6lf %.6lf\n",xl,yl,xr,yr);
}

还有一题先咕着,写完再更。