久违的Rank1
A. 接力比赛
比较显然的 $\operatorname{DP}$,两个 $01$ 背包解决问题
#include<cstdio> #include<cstring> #include<string> #define WR WinterRain #define int long long using namespace std; const int WR=1001000,INF=1e18; struct Lets_Find_A_Good_Student{ int w,v; }a[WR],b[WR]; int n,m,ans; int dp1[WR],dp2[WR]; int sum1[WR],sum2[WR]; int read(){ int s=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=(s<<1)+(s<<3)+ch-48; ch=getchar(); } return s*w; } signed main(){ // freopen("game.in","r",stdin); // freopen("game.out","w",stdout); n=read(),m=read(); memset(dp1,-0x3f,sizeof(dp1)); memset(dp2,-0x3f,sizeof(dp2)); dp1[0]=dp2[0]=0; for(int i=1;i<=n;i++) a[i].w=read(),a[i].v=read(),sum1[i]=sum1[i-1]+a[i].w; for(int i=1;i<=m;i++) b[i].w=read(),b[i].v=read(),sum2[i]=sum2[i-1]+b[i].w; for(int i=1;i<=n;i++){ for(int j=sum1[i];j>=a[i].w;j--){ dp1[j]=max(dp1[j],dp1[j-a[i].w]+a[i].v); } } for(int i=1;i<=m;i++){ for(int j=sum2[i];j>=b[i].w;j--){ dp2[j]=max(dp2[j],dp2[j-b[i].w]+b[i].v); } } for(int i=0;i<=max(sum1[n],sum2[m]);i++) ans=max(ans,dp1[i]+dp2[i]); printf("%lld\n",ans); fclose(stdin); fclose(stdout); return 0; }View Code
B. 树上竞技
按照边去考虑,如果在一条边 $E$ 的两侧分别有 $x$ 和 $m-x$ 个关键点,
不妨令 $x\leqslant m-x$ 那么最后的汇聚点一定在 $m-x$ 这个方向,
这样可以只让 $x$ 条边经过 $E$,代价较小
然后设某条边两侧分别共有 $s$ 和 $n-s$ 个点,容易发现我们需要求
$$\sum\limits_{i=1}^{m-1}\min\{i,m-i\}\times C_{s}^{i}C_{n-s}^{m-i}$$
发现 $\min$ 不是很好处理,考虑把它拆开来,还要加上 $m$ 为偶数的情况,用 $\operatorname{DFS}$ 预处理节点子树大小,原式可以化成
$$ans=\sum\limits_{u=2}^{n}\sum\limits_{i=1}^{\frac{m-1}{2}}i\times C_{size[u]}^{i}C_{n-size[u]}^{m-i}+i\times C_{size[u]}^{m-i}C_{n-size[u]}^{i}+[m\%2==0]\frac{m}{2}\times C_{s}^{\frac{m}{2}}C_{n-s}^{\frac{m}{2}}$$
后面的一小点式子可以暴力硬扫,考虑前面的怎样优化
不妨设 $k=\frac{m}{2}$,发现比较显然地,$\sum\limits_{i=1}^{k}i\times C_{s}^{i}C_{n-s}^{m-i}=s\sum\limits_{i=1}^{k}C_{s-1}^{i-1}C_{n-s}^{m-i}$
不妨令 $f(s)=\sum\limits_{i=1}^{k}C_{s-1}^{i-1}C_{n-s}^{m-i}$,那么答案就是 $\sum\limits_{u=2}^{n}f(size[u])+ f(n-size[u])$
考虑如何求出 $f(s)$,发现它的组合意义是 $n-1$ 个物品里选择了 $m-1$ 个,前面 $s-1$ 个物品中选择了 $k-1$ 个的方案数
如何递推 $f(s)$ ?
不难发现,$f(s)$ 变成 $f(s+1)$ 变少的部分就是前 $s-1$ 个点中选择 $k-1$ 个,选择了 $s$ 为第 $k$ 个点,后面 $n-s-1$ 个点里选择了 $m-k-1$ 个点
这是为什么呢?我们考虑如果没有选择 $s$ 作为第 $k$ 个点
那么前 $s$ 个点中选择 $k-1$ 个点和前 $s-1$ 个点中选择 $k-1$ 个是等价的
所以必须让 $s$ 作为第 $k$ 个点被选择,多出来的方案数根据乘法原理就是 $C_{s-1}^{k-1}C_{n-s-1}^{m-k-1}$
也就是说 $f[s+1]=f[s]+C_{s-1}^{k-1}C_{n-s-1}^{m-k-1}$
统计答案即可
题解好像有点毛病=_=
#include<cstdio> #include<cstring> #include<string> #define WR WinterRain #define int long long using namespace std; const int WR=2001000,INF=1e18,mod=1e9+7; struct Edge{ int pre,to; }edge[WR]; int n,m,ans; int head[WR],tot; int sze[WR]; int f[WR]; int g[WR],ny[WR]; int read(){ int s=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=(s<<1)+(s<<3)+ch-48; ch=getchar(); } return s*w; } int quick_pow(int a,int b){ int base=a,res=1; while(b){ if(b&1) res=res*base%mod; base=base*base%mod; b>>=1; } return res; } void add(int u,int v){ edge[++tot].pre=head[u]; edge[tot].to=v; head[u]=tot; } void dfs(int u,int root){ // printf("%lld %lld\n",u,root); sze[u]=1; for(int i=head[u];i;i=edge[i].pre){ int v=edge[i].to; if(v==root) continue; dfs(v,u); sze[u]+=sze[v]; } } int C(int n,int m){ if(m>n||m<0||n<0) return 0; // printf("%lld %lld\n",n,m); return g[n]*ny[m]%mod*ny[n-m]%mod; } signed main(){ freopen("meeting.in","r",stdin); freopen("meeting.out","w",stdout); g[0]=ny[0]=1; for(int i=1;i<WR;i++) g[i]=g[i-1]*i%mod; ny[WR-1]=quick_pow(g[WR-1],mod-2); for(int i=WR-2;i>=1;i--) ny[i]=ny[i+1]*(i+1)%mod; // for(int i=1;i<=100;i++) printf("%lld\n",ny[i]); n=read(),m=read(); for(int i=1;i<n;i++){ int fa=read(); add(fa,i+1);add(i+1,fa); } dfs(1,0); if(m%2==0){ for(int i=2;i<=n;i++){ ans=(ans+C(sze[i],m/2)*C(n-sze[i],m/2)%mod*(m/2)%mod)%mod; } } int k=(m-1)/2; if(k) f[1]=C(n-1,m-1); for(int i=1;i<n;i++){ f[i+1]=(f[i]-C(i-1,k-1)*C(n-i-1,m-k-1)%mod+mod)%mod; } for(int i=1;i<=n;i++) f[i]=f[i]*i%mod; for(int i=2;i<=n;i++) ans=(ans+f[sze[i]]+f[n-sze[i]])%mod; printf("%lld\n",ans); fclose(stdin); fclose(stdout); return 0; }View Code
C. 虚构推理
题解里说的方法很好,但我直接暴力
首先枚举小时,再枚举分针偏角
找 $\operatorname{lower_bound}$ 然后查询就行
#include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> #define WR WinterRain #define int long long using namespace std; const int WR=1001000; struct Clock{ int h,m,s; }clc[WR]; int n; double mnt[WR],hor[WR]; double ans; int read(){ int s=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=(s<<1)+(s<<3)+ch-48; ch=getchar(); } return s*w; } signed main(){ freopen("unreal.in","r",stdin); freopen("unreal.out","w",stdout); n=read();ans=1e9; for(int i=1;i<=n;i++) clc[i].h=read(),clc[i].m=read(),clc[i].s=read(); for(int i=1;i<=n;i++){ mnt[i]=clc[i].s*0.1+clc[i].m*6.0; hor[i]=clc[i].h%12*30.0+mnt[i]/12.0; } sort(hor+1,hor+n+1); sort(mnt+1,mnt+n+1); for(int i=0;i<=360;i+=30){ for(double j=0;j<=360;j+=0.01){ int tmphor=lower_bound(hor+1,hor+1+n,(i+j/12)>180?i+j/12-180:i+j/12+180)-hor-1; int tmpmnt=lower_bound(mnt+1,mnt+1+n,j>180?j-180:j+180)-mnt-1; int nxthor=tmphor+1,nxtmnt=tmpmnt+1; if(nxthor>n) nxthor=1; if(nxtmnt>n) nxtmnt=1; if(tmphor==0) tmphor=n; if(tmpmnt==0) tmpmnt=n; double reshor1=fabs(hor[tmphor]-(i+j/12)),reshor2=fabs(hor[nxthor]-(i+j/12)); if(reshor1>180.0) reshor1=360.0-reshor1; if(reshor2>180.0) reshor2=360.0-reshor2; double reshor=max(reshor1,reshor2); double resmnt1=fabs(mnt[tmpmnt]-j),resmnt2=fabs(mnt[nxtmnt]-j); if(resmnt1>180.0) resmnt1=360.0-resmnt1; if(resmnt2>180.0) resmnt2=360.0-resmnt2; double resmnt=max(resmnt1,resmnt2); ans=min(ans,max(reshor,resmnt)); } } printf("%.8lf\n",ans); fclose(stdin); fclose(stdout); return 0; }View Code
正解放在下面
这里是zcy大佬的题解
#include<iostream> #include<cstdio> #include<algorithm> #include<deque> using namespace std; const int maxn=5e4+10; const double eps=1e-6; int N,ftop=0;double a[maxn<<1],b[maxn<<1],ans=180,f[maxn]; deque<double>q; int qd(){ int rt=0;char c=getchar(); while(c<'0'||c>'9') c=getchar(); while('0'<=c&&c<='9') rt=(rt<<3)+(rt<<1)+c-48,c=getchar(); return rt; } void _m(double &x,const double &y){x=x-y*((int)x/(int)y);} void change(double l,double r){ if(ftop&&f[ftop]>=l) f[ftop]=r; else f[++ftop]=l,f[++ftop]=r; } bool ask(double l,double r){ if(!ftop) return 0; if(r-l>=30) return 1; l*=12,r*=12;_m(l,360),_m(r,360); if(r<l) r+=360; int t=lower_bound(f+1,f+ftop+1,l)-f; if(t<=ftop&&(!t&1||r>=f[t+1])) return 1; l+=360,r+=360; t=lower_bound(f+1,f+ftop+1,l)-f; if(t<=ftop&&(!t&1||r>=f[t+1])) return 1; return 0; } int calc(double t){ q.clear();ftop=0; for(int i=1;i<=2*N;i++){ q.push_front(b[i]); while(!q.empty()&&q.front()-q.back()>2*t) q.pop_back(); if(q.size()>=N) change(q.front()-t,q.back()+t); } if(!ftop) return 0; q.clear(); for(int i=1;i<=2*N;i++){ q.push_front(a[i]); while(!q.empty()&&q.front()-q.back()>2*t) q.pop_back(); if(q.size()>=N&&ask(q.front()-t,q.back()+t)) return 1; } return 0; } int main(){ freopen("unreal.in","r",stdin); freopen("unreal.out","w",stdout); N=qd(); for(int i=1;i<=N;i++){ int x=qd(),y=qd(),z=qd(); a[i]=(x%12)*30+y/2.0+z/120.0;_m(a[i],360); b[i]=y*6+z/10.0;_m(b[i],360); } sort(a+1,a+N+1);sort(b+1,b+N+1); for(int i=1;i<=N;i++) a[N+i]=a[i]+360,b[N+i]=b[i]+360; for(double x=180;x>=eps;x/=2) if(ans>=x&&calc(ans-x)) ans-=x; printf("%.5lf\n",ans); return 0; }View Code
D. 记忆碎片
不会,贺的
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double db; typedef unsigned long long ull; typedef pair<int,int> pii; const int mod=1e9+7; const ull bs=131; inline int read(){ int x=0,w=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();} return x*w; } int n; int tot; vector<int> S[40005],tmp; map<vector<int>,int> mp; int cnt_edge[40005]; bool mark[1605]; void dfs(int l,int r){ if(!r){ S[++tot]=tmp; mp[S[tot]]=tot; for(int i:S[tot]){ cnt_edge[tot]+=i*(i-1)/2; } return; } if(l>r) return; for(int i=l;i<=r;++i){ tmp.push_back(i); dfs(i,r-i); tmp.pop_back(); } } ll dp[1605][40005]; int main(){ freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); n=read(); for(int i=1;i<n;++i) mark[read()]=1; dfs(1,n); dp[0][1]=1; for(int i=1;i<=n*(n-1)/2;++i){ for(int j=1;j<=tot;++j){ if(!dp[i-1][j]) continue; if(mark[i]){ //树边合并 for(int x=0;x<S[j].size();++x){ for(int y=x+1;y<S[j].size();++y){ tmp.clear(); tmp.push_back(S[j][x]+S[j][y]); for(int z=0;z<S[j].size();++z){ if(z!=x&&z!=y) tmp.push_back(S[j][z]); } sort(tmp.begin(),tmp.end()); int nxt=mp[tmp]; dp[i][nxt]=(dp[i][nxt]+dp[i-1][j]*S[j][x]%mod*S[j][y]%mod)%mod; } } } else{ //非树边随便连一条 dp[i][j]=(dp[i][j]+dp[i-1][j]*(cnt_edge[j]-(i-1))%mod)%mod; } } } printf("%lld\n",dp[n*(n-1)/2][tot]); return 0; }SoyTony大佬的代码
标签:ch,return,2022,int,double,WR,暑假,include,集训 From: https://www.cnblogs.com/WintersRain/p/16599897.html