菜爆了……总共只有一道题会做的……而且也没有短裙好难过

为啥必须得有手机才能注册账号啊喂……歧视么……

\(A\) 解方程

推一下柿子大概就是

\[x-\sqrt{n}=y+z+2\sqrt{yz}\]

如果\(\sqrt{n}\)是无理数，那么就是

\[x=y+z,{n\over 4}=yz\]

那么要满足\(n\)必须是\(4\)的倍数，然后爆搜\({n\over 4}\)的因子，统计答案就行了

如果\(n\)不是无理数，那么

\[x=\sqrt{n}+(y-z)^2\]

这东西一看就是无限解吧……

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=1e5+5;int p[N],vis[N],m;void init(int n=1e5){    fp(i,2,n){        if(!vis[i])p[++m]=i;        for(R int j=1;j<=m&&1ll*i*p[j]<=n;++j){            vis[i*p[j]]=1;            if(i%p[j]==0)break;        }    }}const int P=1e9+7;int st[N],c[N],top,res,sum,n,sqr;void dfs(int x,int s){    if(x==top+1){        if(n/4/s>s)return;        res=(res+1)%P,sum=(sum+s+n/4/s)%P;        return;    }    for(R int i=0,t=1;i<=c[x];++i,t*=st[x])        dfs(x+1,s*t);}void solve(int x){    top=0;    for(R int i=1;1ll*p[i]*p[i]<=x;++i)if(x%p[i]==0){        st[++top]=p[i],c[top]=0;        while(x%p[i]==0)x/=p[i],++c[top];    }    if(x>1)st[++top]=x,c[top]=1;    res=sum=0;    dfs(1,1);}int main(){//  freopen("testdata.in","r",stdin);    init();    int T=read();    while(T--){        n=read(),sqr=sqrt(n);        if(n==0||sqr*sqr==n){puts("infty");continue;}        if(n%4){puts("0 0");continue;}        solve(n/4);        printf("%d %d\n",res,1ll*sum*n/4%P);    }    return 0;}
     
    

\(B\) 旅途

这么傻逼的一个\(dp\)我居然没想出来……

如果没有遍历完所有\(n\)个城市，那么遍历到的城市显然是一条链。我们可以设\(f_{i,j,k}\)表示在第\(i\)天，左边有\(j\)个已经访问过的城市，右边有\(k\)个已经访问过的城市的概率。转移显然

如果遍历完了所有的\(n\)个城市咋办？发现其实不看成环也没问题，直接把访问城市个数对\(n\)取\(\min\)就可以了

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=505,P=1e9+7;inline void Add(R int &x,R int y){(x+=y)>=P?x-=P:0;}inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;    return res;}int f[N][N][N],g[N],T,n,m,k,p,q,res;int main(){//  freopen("testdata.in","r",stdin);    T=read();    while(T--){        n=read(),m=read(),k=read(),p=read(),q=read(),res=0;        fp(i,1,m)fp(j,0,i-1)fp(k,0,i-1)f[i][j][k]=0;        fp(i,1,n)g[i]=0;        f[1][0][0]=1;        fp(i,1,m-1)fp(j,0,i-1)fp(k,0,i-1)            Add(f[i+1][max(j-1,0)][k+1],mul(f[i][j][k],p)),            Add(f[i+1][j+1][max(k-1,0)],mul(f[i][j][k],q)),            Add(f[i+1][j][k],mul(f[i][j][k],100-p-q));        fp(i,0,m-1)fp(j,0,m-1)Add(g[min(i+j+1,n)],f[m][i][j]);        fp(i,1,n)Add(res,mul(g[i],ksm(i,k)));        printf("%d\n",res);    }    return 0;}
     
    

\(C\) 项链与计数

如果一个点对满足条件，说明它们之间存在至少两条边不重复的路径，也就是说明它们在同一个边双里

动态维护边双，看

//minamoto#include
    
     #define R register#define ll long long#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=1e6+5,M=2e6+5;struct eg{int v,nx;}e[N<<1];int head[N],tot;inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}struct EG{int u,v,is;}st[M];int fa[N],ga[N],sz[N],dep[N],q[N];int n,m;ll res,sum;int find(int x){return ga[x]==x?x:ga[x]=find(ga[x]);}inline ll calc(R int x){return 1ll*x*(x-1)>>1;}void bfs(int u){    int h=1,t=0;q[++t]=u,dep[u]=1;    while(h<=t){        u=q[h++];        go(u)if(v!=fa[u])q[++t]=v,dep[v]=dep[u]+1,fa[v]=u;    }}void merge(int u,int v){    u=find(u),v=find(v);    while(u!=v){        if(dep[u]
      
       sz[v]?ga[v]=u:sz[u]
      
     
    

\(D\)

我们设\(f_{i,j,k}\)表示已经完成了\(i\)这个集合的任务，\(A\)结束的时间为\(j\)，\(B\)结束的时间为\(k\)，\(C\)能结束的最早时间是多少。转移的话大概比较显然

虽然看着这东西的复杂度似乎是\(O(T\times 2^6\times 180^2\times 6\times 7)\)……有点炸的样子……不过因为合法的状态不是很多，所以我们只转移合法的就可以过了

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=(1<<6)+5;int sz[N],a[9][9],f[N][205][205],lim;int main(){//  freopen("testdata.in","r",stdin);    int T=read();lim=(1<<6);    fp(i,1,lim-1)sz[i]=sz[i>>1]+(i&1);    while(T--){        fp(i,0,5)fp(j,0,6)a[i][j]=read();        memset(f,0x3f,sizeof(f));f[0][0][0]=0;        fp(i,0,lim-1)fp(j,0,180)fp(k,0,180)            if(f[i][j][k]<=180)                fp(x,0,5)if(i>>x&1^1){                    int s=i|(1<
       
        res||sz[i]==res&&max(max(j,k),f[i][j][k])
       
      
     
    

\(E\)

orz

为了最大化\(LIS\)，修改之后\(LIS\)要么不变要么\(+1\)，一下设原数列的\(LIS\)长度为\(m\)

那么我们先把求\(LIS\)时需要的单调栈给预处理出来，然后分情况讨论

1.\(i\)修改之后\(LIS\)长度\(+1\)，那么我们需要它前面有一个\(a_j\)满足以\(j\)结尾的\(LIS\)长度为\(d\)，后面有一个\(a_k\)满足以\(k\)开头的\(LIS\)长度为\(m-d\)，且有\(a_k>a_j+1\)，那么为了满足修改后的元素最小，我们显然是取把它改成\(a_j+1\)最优

2.如果\(i\)没办法在一个长度为\(m+1\)的数列里，那么改完之后\(LIS\)的长度还是为\(m-1\)。这个也要分情况讨论。我们先假设如果有一个\(LIS\)不包含\(i\)，那么显然它可以取\(0\)

3.如果所有的\(LIS\)都包含\(i\)，那么它只能取满足存在\(a_j\)长度为\(d\)和\(a_k\)长度为\(m-d-1\)的\(a_j+1\)或者\(a_j\)长度为\(d-1\)且\(a_k\)长度为\(m-d\)的\(a_j+1\)了

//minamoto#include
    
     #define R register#define inf 0x3f3f3f3f#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        '9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int K=-1,Z=0;inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}void print(R int x){    if(K>1<<20)Ot();if(x<0)sr[++K]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++K]=z[Z],--Z);sr[++K]='\n';}const int N=1e5+5;int p[N],q[N],len[N],las[N],now[N],a[N],cnt,T,n,ans,mx;multiset
        
         b,c;int main(){//  freopen("testdata.in","r",stdin);    T=read();    while(T--){        n=read();        fp(i,1,n)a[i]=read();        q[0]=inf;fp(i,1,n)q[i]=-1;        ans=0;        fd(i,n,1){            int l=0,r=ans;            while(l<=r){                int mid=(l+r)>>1;                q[mid]>a[i]?(len[i]=mid+1,l=mid+1):r=mid-1;            }            las[i]=q[len[i]],q[len[i]]=a[i],cmax(ans,len[i]);        }        cnt=0,b.clear(),c.clear();        p[0]=-1;fp(i,1,n)p[i]=inf;        if(q[ans]>p[0])++cnt;        if(q[ans]>p[0]+1)b.insert(p[0]);        if(q[ans-1]>p[0]+1)c.insert(p[0]);        mx=0;        fp(i,1,n){            if(q[len[i]]>p[ans-len[i]]+1)b.erase(b.find(p[ans-len[i]]));            if(ans>=len[i]+1&&q[len[i]]>p[ans-len[i]-1]+1)c.erase(c.find(p[ans-len[i]-1]));            if(q[len[i]]>p[ans-len[i]])--cnt;            q[len[i]]=las[i];            if(q[len[i]]>p[ans-len[i]]+1)b.insert(p[ans-len[i]]);            if(ans>=len[i]+1&&q[len[i]]>p[ans-len[i]-1]+1)c.insert(p[ans-len[i]-1]);            if(q[len[i]]>p[ans-len[i]])++cnt;            if(!b.empty())print(ans+1),sr[K]=' ',print((*b.begin())+1);            else if(cnt)print(ans),sr[K]=' ',sr[++K]='0',sr[++K]='\n';            else print(ans),sr[K]=' ',print((*c.begin())+1);            int l=0,r=mx;            while(l<=r){                int mid=(l+r)>>1;                p[mid]
         
          p[now[i]]+1)b.erase(b.find(p[now[i]])); if(ans>=now[i]+1&&q[ans-now[i]-1]>p[now[i]]+1)c.erase(c.find(p[now[i]])); if(q[ans-now[i]]>p[now[i]])--cnt; p[now[i]]=a[i]; if(q[ans-now[i]]>p[now[i]]+1)b.insert(p[now[i]]); if(ans>=now[i]+1&&q[ans-now[i]-1]>p[now[i]]+1)c.insert(p[now[i]]); if(q[ans-now[i]]>p[now[i]])++cnt; } } return Ot(),0;}
         
        
       
      
     
    

\(F\)

计蒜几盒的精度是真的难受啊……

首先，如果我们能算出\(g[s]\)表示\(s\)这个集合的木棒能组成的最大面积，那么我们就可以直接\(3^n\)的\(dp\)求得答案

所以怎么算最大面积呢……

首先我们把\(s\)这个集合里的木棒按升序排序，记为\(a_1,a_2,...,a_m\)，根据三角形不等式，它们能构成多边形当且仅当

\[a_m<{1\over 2}\sum_{i=1}^ma_i\]

然后现在问题是如何最大化面积

有一个结论是面积最大当且仅当所有的顶点在同一个圆上，证明如下（然而我并看不懂就是了）

然后我们现在就是需要二分这个圆的半径，这个要分两种情况讨论，圆心在多边形内和多边形外。

如果在多边形内，那么我们看看当前所有木棒覆盖的圆心角是否大于\(\pi\)，如果是的话我们需要增大半径，否则要缩小半径

如果在多边形外，我们看看\(a_1,...,a_{m-1}\)的木棒覆盖的圆心角和\(a_m\)覆盖的圆心角的大小之比。如果\(a_m\)覆盖的圆心角更大，我们需要增大半径，否则减少半径

然后就直接暴力子集\(dp\)就可以了

//minamoto#include
    
     #define R register#define inf 0x3f3f3f3f#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        '9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=15,M=(1<<12)+5;const double Pi=acos(-1.0),eps=1e-15;inline int sgn(R double x){return x<-eps?-1:x>eps;}inline double sqr(R double x){return x*x;}int a[N],b[N],p[M],st[N][N],top[N];double d[M],g[M];int n,lim,tot,ans,cnt;bool ck1(double mid){    double s=0;    fp(i,1,tot-1)s+=asin(b[i]*0.5/mid);    return sgn(s-asin(b[tot]*0.5/mid))>0;}bool ck2(double mid){    double s=0;    fp(i,1,tot)s+=asin(b[i]*0.5/mid);    return sgn(Pi-s)>0;}int main(){//  freopen("testdata.in","r",stdin);    int T=read();    while(T--){        n=read();fp(i,0,n-1)a[i]=read();        sort(a,a+n),lim=(1<
        
         >j&1)?b[++tot]=a[j],cnt+=a[j]:0;            if(tot<3||cnt-b[tot]<=b[tot])continue;            cnt=0;            double Ri=0;            if(!ck2(b[tot]*0.5)){                for(R double l=b[tot]*0.5,r=10000,mid=(l+r)*0.5;++cnt<70;mid=(l+r)*0.5)                    ck2(mid)?Ri=r=mid:l=mid;                fp(j,1,tot)g[i]+=sqrt(sqr(Ri)-sqr(b[j])*0.25)*b[j]*0.5;            }else{                for(R double l=b[tot]*0.5,r=10000,mid=(l+r)*0.5;++cnt<70;mid=(l+r)*0.5)                    ck1(mid)?Ri=r=mid:l=mid;                fp(j,1,tot-1)g[i]+=sqrt(sqr(Ri)-sqr(b[j])*0.25)*b[j]*0.5;                g[i]-=sqrt(sqr(Ri)-sqr(b[tot])*0.25)*b[tot]*0.5;            }        }        fp(i,0,lim-1)d[i]=0;        d[0]=1;        fp(i,0,lim-1)if(sgn(d[i])>0)            for(R int s=(lim-1)^i,j=s;j;j=(j-1)&s)                if(sgn(g[j])&&cmax(d[i|j],d[i]*g[j]))p[i|j]=i;        ans=1,tot=0,d[0]=0;        fp(i,1,lim-1)sgn(d[i]-d[ans])>0?ans=i:0;        printf("%.10lf\n",d[ans]);        for(;ans;ans=p[ans])if(sgn(g[ans^p[ans]])>0){            top[++tot]=0;            for(R int i=0,t=ans^p[ans];i
         
          >i&1)?st[tot][++top[tot]]=i:0; } printf("%d\n",tot); fp(i,1,tot){ printf("%d ",top[i]); fp(j,1,top[i])printf("%d%c",a[st[i][j]]," \n"[j==top[i]]); } } return 0;}