心得技巧
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧

Noip模拟66 2021.10.3

发布时间：2022-07-04 发布网站：脚本宝典
脚本宝典收集整理的这篇文章主要介绍了Noip模拟66 2021.10.3，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

T1 接力比赛

思路就是直接做背包$dp$，然后看看容量相同的相加的最大值。

考虑如何在$dp$过程中进行优化

注意到转移方程的第二维枚举容量没有必要从容量总和开始枚举

那么我们便转移边统计前缀和，从前缀和到当前容量做转移就行

复杂度$???$，可以过

Noip模拟66 2021.10.3

Noip模拟66 2021.10.3

 1 #include<bITs/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 namespace AE86{
 5     inline int read(){
 6         int x=0,f=1;char ch=getchar();
 7         while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 8         while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
 9     }inline void write(int x,char opt='n'){
10         char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11         do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12         for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=1e3+1;
15 int n,m,ans,f[1000005],sm[NN],g[1000005],tot;
16 struct node{int w,v;}p[NN];
17 namespace WSN{
18     inline short main(){
19         freoPEn("game.in","r",stdin);
20         freopen("game.out","w",stdout);
21         n=read(); m=read();
22         memset(f,-0x3f,sizeof(f));
23         memset(g,-0x3f,sizeof(g));
24         f[0]=g[0]=0;
25         for(int i=1;i<=n;i++)
26             p[i].w=read(),p[i].v=read(),sm[i]=sm[i-1]+p[i].w;
27         tot=max(tot,sm[n]);
28         for(int i=1;i<=n;i++)
29             for(int j=sm[i];j>=p[i].w;j--)
30                 f[j]=max(f[j],f[j-p[i].w]+p[i].v);
31         memset(sm,0,sizeof(sm));
32         for(int i=1;i<=m;i++)
33             p[i].w=read(),p[i].v=read(),sm[i]=sm[i-1]+p[i].w;
34         tot=max(tot,sm[m]);
35         for(int i=1;i<=m;i++)
36             for(int j=sm[i];j>=p[i].w;j--)
37                 g[j]=max(g[j],g[j-p[i].w]+p[i].v);
38         for(int i=0;i<=tot;i++){
39             ans=max(ans,f[i]+g[i]);
40         } write(ans);
41         return 0;
42     }
43 }
44 signed main(){return WSN::main();}
View Code

&nbsp;

T2 树上竞技

考场上以为是道数据结构加$dp$套路题，结果是道纯计数

考虑每条边做的贡献，设一条边左边有$s$个点，右边则有$n-s$

那么中心点，也就是所有点都要走到的那个点一定出在 点数多的一侧

也就是这条边会做$min(i,m-i)$次贡献，$i$是左边要选的点的个数。

那么答案可以写成$ans=sum _{u=2}^{n} sum_{i=1}^{m-1} C_{siz[u]}^{i} *C_{n-siz[u]}^{m-i}*min(i,m-i)$

考虑把$min$干掉，柿子内部化简为$sum_{i=1}^{frac{m-1}{2}} C_{s}^{i} *C_{n-s}^{m-i}*i+C_{n-s}^{i}*C_{s}^{m-i}*i$

当然如果$m$是偶数还要加上特殊的没进行考虑的$C_{s}^{frac{m}{2}}*C_{n-s}^{frac{m}{2}}* frac{m}{2}$

题解柿子错了

然后这样或者不去掉$min$可获得$40$。

偶数的那部分可以直接暴力，我们继续化简$ sum_{i=1}^{k} C_{s}^{i} *C_{n-s}^{m-i}*i$一部分

设$G[s]=sum_{i=1}^{k} C_{s}^{i} *C_{n-s}^{m-i}*i=s*sum_{i=1}^{k} C_{s-1}^{i-1} *C_{n-s}^{m-i}$

那么答案为$ans=sum_{u=2}^{n}G[siz[u]]+G[n-siz[u]]$

考虑$frac{G[s]}{s}$的组合含义，从$n-1$个物品中选择$m-1$个物品，至少有$k$个物品在前$s$个物品内的方案

考虑$G$之间的递推性，可以感性理解，画一个数轴自己挪一挪分界点就出来了，$G[s]-G[s+1]=C_{s-1}^{k-1}*C_{n-s-1}^{m-k-1}$

Noip模拟66 2021.10.3

Noip模拟66 2021.10.3

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 namespace AE86{
 5     inline int read(){
 6         int x=0,f=1;char ch=getchar();
 7         while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 8         while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
 9     }inline void write(int x,char opt='n'){
10         char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11         do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12         for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=1e6+1,mod=1e9+7;
15 int n,m,h[NN],v[NN],ans;
16 int siz[NN],fa[NN],G[NN];
17 struct SNOW{int to,next;}e[NN<<1];int head[NN],rp;
18 inline void add(int x,int y){
19     e[++rp]=(SNOW){y,head[x]};head[x]=rp;
20     e[++rp]=(SNOW){x,head[y]};head[y]=rp;
21 }
22 inline void DFs1(int f,int x){
23     siz[x]=1;
24     for(int i=head[x];i;i=e[i].next){
25         int y=e[i].to ; if(y==f) continue;
26         dfs1(x,y); siz[x]+=siz[y];
27     }
28 }
29 inline int qmo(int a,int b,int ans=1){
30     int c=mod; a%=c;for(;b;b>>=1,a=a*a%c) if(b&1) ans=ans*a%c;
31     return ans;
32 }
33 inline void PRe(){
34     h[0]=h[1]=1; v[0]=v[1]=1;
35     for(int i=2;i<NN;++i) h[i]=h[i-1]*i%mod;
36     v[NN-1]=qmo(h[NN-1],mod-2);
37     for(int i=NN-2;i>=2;--i) v[i]=v[i+1]*(i+1)%mod;
38 }
39 inline int C(int n,int m){
40     if(n<;m||n<0||m<0) return 0;
41     return h[n]*v[n-m]%mod*v[m]%mod;
42 }
43 namespace WSN{
44     inline short main(){
45         freopen("meeting.in","r",stdin);
46         freopen("meeting.out","w",stdout);
47         n=read();m=read(); pre();
48         for(int i=2;i<=n;++i)
49             fa[i]=read(),add(fa[i],i);
50         dfs1(0,1);
51         if(m%2==0)    for(int i=2;i<=n;i++)
52             ans=(ans+C(siz[i],m/2)*C(n-siz[i],m/2)%mod*(m/2)%mod)%mod;
53         int k=(m-1)>>1; if(k) G[1]=C(n-1,m-1);
54         for(int i=1;i<n;i++) G[i+1]=(G[i]-C(i-1,k-1)*C(n-i-1,m-k-1)%mod+mod)%mod;
55         for(int i=1;i<=n;i++) G[i]=G[i]*i%mod;
56         for(int i=2;i<=n;i++)
57             ans=(ans+G[siz[i]]+G[n-siz[i]])%mod;
58         write(ans);
59 
60         return 0;
61     }
62 }
63 signed main(){return WSN::main();}
View Code

 

T3 虚构推理

水过的，直接枚举一天的所有时间然后找最大值的最小值即可，跑的比正解快仅有$400ms$

不懂为啥能$zhe$快。

正解是二分，二分出一个角度，$check$的时候找有无区间覆盖，

区间是指每一个输入指针加减验证的角度得出的一段可能值域

那么对于区间的交可以用柯朵莉树

Noip模拟66 2021.10.3

Noip模拟66 2021.10.3

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 #define wsn double
 4 using namespace std;
 5 namespace AE86{
 6     inline int read(){
 7         int x=0,f=1;char ch=getchar();
 8         while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 9         while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
10     }inline void write(int x,char opt='n'){
11         char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
12         do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
13         for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
14 }using namespace AE86;
15 const int NN=50005;
16 int n;
17 wsn a[NN],b[NN],ans=1e9;
18 inline wsn abs(wsn a,wsn b){
19     a=fabs(a-b); return a>180 ? 360-a:a;
20 }
21 inline wsn calc(wsn x,wsn s[]){
22     int i=lower_bound(s+1,s+n+1,x>180?x-180:x+180)-s,j=i-1;
23     if(i>n) i=1; if(j==0) j=n;
24     return max(abs(s[i],x),abs(s[j],x));
25 }
26 namespace WSN{
27     inline short main(){
28         freopen("unreal.in","r",stdin);
29         freopen("unreal.out","w",stdout);
30         n=read();
31         for(int i=1,h,m,s;i<=n;i++){
32             h=read(),m=read(),s=read();
33             b[i]=s*0.1+m*6.0;
34             a[i]=(h%12)*30.0+b[i]/12.0;
35         }
36         sort(a+1,a+n+1); sort(b+1,b+n+1);
37         for(int h=0;h<360;h+=30)
38             for(wsn m=0;m<360;m+=0.01)
39                 ans=min(ans,max(calc(h+m/12,a),calc(m,b)));
40         printf("%.10lfn",ans);
41         return 0;
42     }
43 }
44 signed main(){return WSN::main();}
View Code

 

T4 记忆碎片

咕咕咕

 

脚本宝典总结

以上是脚本宝典为你收集整理的Noip模拟66 2021.10.3全部内容，希望文章能够帮你解决Noip模拟66 2021.10.3所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
标签：c++javaphppythonsortwhilewhile优化优化程序员程序员
猜你在找的心得技巧相关文章
其他相关热搜词更多
phpjavapython程序员loadpost-format-gallerydivString参数开发ListcapMapClass工具安装SQL数据库资源this
全站导航更多
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧JavaScriptASP.NETPHP编程正则表达式AJAX相关ASP编程JSP编程编程10000问CSS/HTMLFlexvbsDOS/BAThtahtcpythonperl游戏相关VBA远程脚本ColdFusionMsSqlMysqlmariadboracleDB2mssql2008mssql2005SQLitePostgreSQLMongoDB星外虚拟主机华众虚拟主机Linuxwin服务器FTP服务器DNS服务器Tomcatnginxzabbix云和虚拟化bios系统安装系统系统进程Windows系列LINUXRedHat/CentosUbuntu/DebianFedoraSolaris红旗Linux建站经验微信营销网站优化网站策划网络赚钱网络创业站长故事alexa域名photoshop教程摄影教程Fireworks教程CorelDraw教程Illustrator教程Painter教程Freehand教程IndesignSketch笔记本主板内存CPU存储显卡显示器光存储鼠标键盘平板电脑安全教程杀毒防毒安全设置病毒查杀脚本攻防入侵防御工具使用业界动态Exploit漏洞分析
最新心得技巧教程
热门心得技巧教程