AtCoder Grand Contest 036题解

Myth丶恋晨 2021-10-15 14:59 249阅读 0赞

[传送门][Link 1]

爆炸的比较厉害……果然还是菜啊……

## \\(A\\) ##

我们强制一个点为\\((0,0)\\)，那么设剩下两个点分别为\\((a,b),(c,d)\\)，根据叉积可以计算出面积为\\(ad-bc=S\\)，那么令\\(ad\\)略大于\\(S\\)，然后对于\\(bc\\)暴力枚举一下就行了

ll S,p,a,b,c,d,t; void init(){ if(p*p==S)return a=b=p,void(); a=b=p+1; } int main(){ cin>>S,p=sqrt(S);init(),t=a*b-S; fp(i,1,1e9)if(t%i==0&&t/i<=1e9){c=i,d=t/i;break;} printf("%lld %lld %lld %lld %lld %lld\n",0ll,0ll,a,c,d,b); return 0; }

## \\(B\\) ##

我们考虑记录一个\\(pos\\)，初始为\\(1\\)，每一次找到序列中下一个和它元素值一样的位置，不管他们两个位置之间元素值长什么样子，他们两个之间肯定是要全被删掉的，然后令新的\\(pos\\)为那个一样的位置\\(+1\\)。因为\\(pos\\)的取值最多只有\\(O(n)\\)种，所以最多跑\\(n\\)次就可以找到循环节，找到循环节之后把\\(k\\)取个模就行了，剩下的就可以暴力跑了

//quming #include<bits/stdc++.h> #define R register #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(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<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; typedef long long ll; const int N=5e5+5; int st[N],pk[N],a[N],nxt[N],las[N],xia[N],n,pos,top;ll k; int main(){ scanf("%d%lld",&n,&k); fp(i,1,n)scanf("%d",&a[i]),nxt[las[a[i]]]=i,las[a[i]]=i; fp(i,1,n)nxt[las[a[i]]]=i,las[a[i]]=i; fp(i,1,n-1)xia[i]=i+1;xia[n]=1; st[++top]=1,pk[top]=1,pos=1; do{ ++top,pk[top]=pk[top-1]+(nxt[pos]<=pos)+(nxt[pos]==n); st[top]=pos=xia[nxt[pos]]; }while(st[top]!=st[1]); k-=(k-1)/(pk[top]-1)*(pk[top]-1); R int j=1; // fp(i,1,top)printf("%d %d %d\n",i,st[i],pk[i]); // printf("%lld\n",k); while(j<=top-1&&pk[j+1]<=k)++j; // if(j==top-1)return 0; // fp(i,st[j],n)printf("%d ",a[i]); for(R int i=st[j];i<=n;++i){ if(nxt[i]>i)i=nxt[i]; else printf("%d ",a[i]); } return 0; }

## \\(C\\) ##

比赛的时候我简直就是个\\(zz\\)

首先，最终的序列合法，当且仅当

\\(1.\\max(a\_i)\\leq 2m\\)

\\(2.a\_i\\)为奇数的个数小于等于\\(m\\)个

那么我们只要枚举奇数的个数，把剩下的用隔板法分掉，就能计算出满足条件\\(2\\)的总的序列个数了。然后再减去所有最大值大于等于\\(2m\\)的序列，这个相当于把\\(m-1\\)个数分给\\(n\\)个人并把剩下的\\(2m-1\\)个数分给\\(n\\)个人中的任意一个，把这个方案数减掉就行了

//quming #include<bits/stdc++.h> #define R register #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(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<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; const int P=998244353; inline void upd(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; } const int N=3e6+5; int fac[N],ifac[N],n,m,res,lim; inline int C(R int n,R int m){return m>n?0:1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;} int main(){ scanf("%d%d",&n,&m);lim=m*3+n-1; fac[0]=ifac[0]=1;fp(i,1,lim)fac[i]=mul(fac[i-1],i); ifac[lim]=ksm(fac[lim],P-2);fd(i,lim-1,1)ifac[i]=mul(ifac[i+1],i+1); fp(i,0,m)if((3*m-i)&1^1)upd(res,mul(C(n,i),C(((3*m-i)>>1)+n-1,n-1))); res=dec(res,mul(n,C(m-1+n-1,n-1))); printf("%d\n",res); return 0; }

## \\(D\\) ##

思路的确很巧妙啊

为了方便起见以下从\\(1\\)开始标号

没有负环，意味着我们可以跑一个最短路，记\\(p\_i\\)表示点\\(i\\)到\\(1\\)的最短距离，则对于剩下的每一条边\\((i,j)\\)，都有\\(p\_i+w(i,j)\\geq p\_j\\)

因为所有的\\(0\\)边都不能被删，所以必然有\\(p\_i\\geq p\_\{i+1\}\\)，那么我们定义\\(q\_i=p\_i-p\_\{i+1\}\\)，则\\(q\_i\\geq 0\\)

对于一条长度为\\(1\\)的边\\((i,j)\\)，有\\(p\_i+1\\geq p\_j\\)，即\\(q\_j+q\_\{j+1\}+...+q\_\{i-1\}\\leq 1\\)

对于一条长度为\\(-1\\)的边\\((i,j)\\)，有\\(p\_i-1\\geq p\_j\\)，即\\(q\_i+q\_\{i+1\}+...+q\_\{j-1\}\\geq 1\\)

不难发现，对于所有的\\(q\\)，我们需要考虑的取值只有\\(0\\)和\\(1\\)

那么我们设\\(f\_\{j,i\}\\)表示考虑完了\\(q\_1\\)到\\(q\_i\\)，且上一个为\\(1\\)的是\\(q\_i\\)，再上一个为\\(1\\)的是\\(q\_j\\)，此时最小花费是多少。转移的时候，枚举下一个为\\(1\\)的位置\\(q\_k\\)，则需要删掉的边是，长度为\\(1\\)，且满足\\(r>k,i<l\\leq j\\)的\\((r,l)\\)，或者长度为\\(-1\\)，且满足\\(j<l<r\\leq k\\)的\\((l,r)\\)，这两个都可以用前缀和预处理，总的复杂度即为\\(O(n^3)\\)，不过跑不满

//quming #include<bits/stdc++.h> #define R register #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(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<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; typedef long long ll; const int N=505;const ll inf=0x3f3f3f3f3f3f3f3f; ll sa[N][N],sb[N][N],f[N][N];int n,a[N][N]; int main(){ scanf("%d",&n); fp(i,1,n)fp(j,1,n)if(i!=j)scanf("%d",&a[i][j]); fp(i,1,n)fp(j,i+1,n+1){ sa[i][j]=sa[i][j-1]; fp(k,i,j-1)sa[i][j]+=a[k][j]; } fp(i,1,n)fd(j,n,i+1){ sb[i][j]=sb[i][j+1]; fp(k,1,i)sb[i][j]+=a[j][k]; } memset(f,0x3f,sizeof(f)); f[0][0]=0; fp(i,0,n)fp(j,i,n)if(f[i][j]<inf) fp(k,j+1,n+1)cmin(f[j][k],f[i][j]+sa[j+1][k]+sb[j][k+1]-sb[i][k+1]); R ll res=inf; fp(i,0,n)cmin(res,f[i][n+1]); printf("%lld\n",res); return 0; }

## \\(E\\) ##

代码看起来好长啊不写了……

## \\(F\\) ##

思路很妙啊……

首先容斥，那么我们现在就需要计算至少\\(k\\)个位置满足\\(i+p\_i<n^2\\)，且所有位置都满足\\(i+p\_i<(2n)^2\\)的方案数

定义\\(f(i)\\)表示最小的\\(a\\)使得\\(i^2+a^2\\geq n\\)，\\(g(i)\\)表示最小的\\(a\\)使得\\(i^2+a^2\\geq (2n)^2+1\\)，那么假设我们现在已经选出了\\(k\\)个数使其满足\\(i+p\_i<n^2\\)，那么对于每一个数，它的取值范围都可以表示成\\(p\_i<h(i)\\)，其中\\(h(i)=f(i)\\)或者\\(g(i)\\)

然后我们把所有的\\(h\\)给\\(sort\\)一下，此时的方案数就是\\(\\prod\\limits\_\{i=0\}^\{2n-1\}(h\_i-i)\\)

然后我们考虑所有的\\(f(i)(0\\leq i<n)\\)和\\(g(i)(0\\leq i<n)\\)和\\(g(i)(n\\leq i<2n)\\)，分别记为\\(A,B,C\\)三类，不难发现\\(B\\)类永远大于\\(A\\)类和\\(C\\)类。且由于\\(f\\)和\\(g\\)都不降，我们把三类数合起来排个序，记\\(fpos(i)\\)表示排序后\\(f(i)\\)在数组中的位置，则有\\(f(0)>f(1)>...>f(n-1)\\)恒成立，对\\(g\\)也如此

那么现在问题转化成从\\(0\\)到\\(n-1\\)中，每一个数可以选择\\(f(i)\\)或者\\(g(i)\\)，如果选了\\(f(i)\\)可以对\\(k\\)这一维\\(+1\\)，对于一个选的方案贡献数为\\(\\prod\\limits\_\{i=0\}^\{2n-1\}(h\_i-i)\\)，求总的贡献

那么\\(dp\\)，设\\(dp\_\{i,j\}\\)表示考虑完了\\(f,g\\)排序之后的前\\(i\\)个数，且选了\\(f\\)的有\\(j\\)个，此时的贡献总和。如果该位置是\\(A\\)类或\\(C\\)类我们可以直接计算出它前面有多少个数来计算贡献，如果是\\(B\\)类，我们可以根据此时的\\(k\\)来计算它的贡献

所以只要枚举\\(k\\)即可，复杂度\\(O(n^3)\\)

//quming #include<bits/stdc++.h> #define R register #define fi first #define se second #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(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<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; int P; inline int up(R int x){return x<0?x+P:x;} inline void upd(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; } typedef pair<int,int> pi; const int N=505; pi st[N];int c[N],a[N],dp[N],top,n,res; inline int f(R int x,R int y){R int r=0;while(r<(n<<1)&&r*r+y*y<x*x)++r;return r;} inline int g(R int x,R int y){R int r=0;while(r<(n<<1)&&r*r+y*y<=x*x)++r;return r;} int main(){ scanf("%d%d",&n,&P); fp(i,0,n-1)st[++top]=pi(f(n,i),-i); fp(i,n,(n<<1)-1)st[++top]=pi(g(n<<1,i),1); fp(i,0,n-1)c[i]=g(n<<1,i); sort(st+1,st+1+top); fp(k,0,n){ memset(dp,0,(k+1)<<2); dp[0]=1; int s1=0,s2=0; fp(p,1,top)if(st[p].se==1){ fp(i,0,s2)dp[i]=mul(dp[i],up(st[p].fi-s1-i)); ++s1; }else{ fd(i,s2,0){ upd(dp[i+1],mul(dp[i],up(st[p].fi-s1-i))); dp[i]=mul(dp[i],up(c[-st[p].se]-(n+k+s2-i))); } ++s2; } upd(res,(k&1)?P-dp[k]:dp[k]); } printf("%d\n",res); return 0; }

转载于:https://www.cnblogs.com/yuanquming/p/11234845.html

[Link 1]: https://atcoder.jp/contests/agc036