NOIP 2014 提高组 题解
NOIP 2014 提高组 题解
No 1. 生活大爆炸版石头剪刀布
http://www.luogu.org/problem/show?pid=1328
这是道大水题,我都在想怎么会有人错了,没算法,直接模拟,别读错题.
][]={{,,,,}, {,,,,}, {,,,,}, {,,,,}, {,,,,}}; int n,na,nb; ],b[]; int s1,s2; int main() { ios_base::sync_with_stdio(); cin>>n>>na>>nb; ;i<=na;i++) { cin>>a[i]; } ;i<=nb;i++) { cin>>b[i]; } ,f2=; ;i<=n;i++) { f1++; f2++; ; ; ) s1++; ) s2++; } cout<<s1<<' '<<s2<<endl; ; }
No 2. 联合权值
http://www.luogu.org/problem/show?pid=1351
同样是水题,用加法结合律.
首先,距离为2的两点,必有一个节点与他们都相连.
第一个要求最大值,对于每个点,预处理出相邻的边中权值最大的两条边,枚举每个点,计算这两个值的乘积,求个最大值即可.
第二个,要求距离为2的点对的权值之和,那么,我们先确定某点对中间的那个点,设为p,并预处理出p与其相邻的点距离之和d,则与其相邻的某点q,在中心点为p的距离为二的一条路径上的权值之和为d(q,p)*d(m1,p)+d(q,p)*d(m2,p)+...+d(q,p)*d(mi,p)=d(q,p)*(d-d(q,p)) 其中mi为与p相邻的除q以外的点,共i个.
最后求和即可.
long long n; ; ]; ]; long long mx; long long ans; vector<]; ],m2[]; int main() { scanf("%lld",&n); ;i<n;i++) { long long a,b; scanf("%lld %lld",&a,&b); e[a].pb(b); e[b].pb(a); } ;i<=n;i++) { scanf("%lld",&w[i]); } ;i<=n;i++) { ;j<(long long)e[i].size();j++) { sum[i]+=w[e[i][j]]%MOD; if(w[e[i][j]]>m1[i]) { m2[i]=m1[i]; m1[i]=w[e[i][j]]; } else if(w[e[i][j]]>m2[i]) { m2[i]=w[e[i][j]]; } } } ;i<=n;i++) { mx=max(mx,m1[i]*m2[i]); } printf("%lld ",mx); ;i<=n;i++) { ;j<(long long)e[i].size();j++) { ans=ans+(w[e[i][j]])*(sum[i]-w[e[i][j]]); ans=ans%MOD; } } printf("%lld\n",ans); ; }
No 3. 飞扬的小鸟
http://www.luogu.org/problem/show?pid=1941
dp
dp
dp
其实这题真心不难
不明白为何有许多人不会做........
我们用dp(i,j)表示鸟儿飞到第i根柱子的j高度处所用的最少跳跃步数.
Obviously,不跳,摔落比较好,所以先处理它.
明显的,dp[i+1][j-y[i]]=min(dp[i+1][j-y[i]],dp[i][j]).
当鸟儿跳的时候,要是到顶了不能继续跳,所以要分个类:
1.到顶了
dp[i][m]=min(dp[i][m],dp[i][j]+1)
dp[i+1][m]=min(dp[i+1][m],dp[i][j]+1)
2.没到顶
dp[i][j+x[i]]=min(dp[i][j+x[i]],dp[i][j]+1);
dp[i+1][j+x[i]]=min(dp[i+1][j+x[i]],dp[i][j]+1);
于是就可以写程序了...
][]; ],r[]; ]; ],y[]; int ans; int n,m,k; int main() { ios_base::sync_with_stdio(); cin>>n>>m>>k; ;i<;i++) { l[i]=; r[i]=m; } ;i<n;i++) { cin>>x[i]>>y[i]; } ;i<k;i++) { int t1,t2,t3; cin>>t1>>t2>>t3; l[t1]=t2+; r[t1]=t3-; has[t1]=; } ;i<=n;i++) { has[i]+=has[i-]; } ;i<=n;i++) { ;j<=m;j++) { dp[i][j]=inf; } } ;i<=n;i++) { ;j<=m;j++) { dp[i][j]=inf; } for(int j=l[i];j<=r[i];j++) { if(dp[i][j]<inf) { ans=i; if(j>y[i]) { dp[i+][j-y[i]]=min(dp[i+][j-y[i]],dp[i][j]); } } } for(int j=l[i];j<=m;j++) { if(dp[i][j]<inf) { if(m<j+x[i]) { dp[i][m]=min(dp[i][m],dp[i][j]+); dp[i+][m]=min(dp[i+][m],dp[i][j]+); } else { dp[i][j+x[i]]=min(dp[i][j+x[i]],dp[i][j]+); dp[i+][j+x[i]]=min(dp[i+][j+x[i]],dp[i][j]+); } } } } if(ans==n) { ans=inf; for(int i=l[n];i<=r[n];i++) { ans=min(ans,dp[n][i]); } cout<<<<endl<<ans<<endl; } else { cout<<<<endl<<has[ans]<<endl; } ; }
先写day1 以后有时间再写day 2.........
最新文章
- 分布式系统理论进阶 - Paxos变种和优化
- 使用Maven来写j2ee项目
- smbclient提示NT_STATUS_INSUFFICIENT_RESOURCES
- JavaScript笔记——引用类型之Object类型和Function类型
- javascript: detect mobile devices or browser
- IOS8修改状态栏颜色
- CentOs 设置静态IP 方法 dhcp的配置
- 张恭庆编《泛函分析讲义》第二章第4节 $Hahn$-$Banach$ 定理习题解答
- 无责任Windows Azure SDK .NET开发入门篇三[使用Azure AD 管理用户信息--3.5 Delete删除用户]
- ndk文件操作问题及小结
- java中调用js脚本
- mysql用存储过程插入百万条数据, 及查询优化
- 简单RPC框架-业务线程池
- tomcat默认日志路径更改
- 基于Windows服务器,从0开始搭建一个基于RTSP协议的直播平台
- ado.net的简单数据库操作(三)——简单增删改查的实际应用
- outlook2013 关闭时最小化到任务栏的完美解决方法
- sql排列组合
- Docker bridge-utils 工具简单部署
- 基于canvas的电子始终
热门文章
- arcgis api for js入门开发系列九热力图效果
- selenium webDriver给隐藏域赋值 input hidden set value
- laravel blade模板介绍
- 第一个spark+scala程序
- CSS 从入门到忘记
- npm 的用法
- Hadoop启动方式
- AngularJs学习笔记2-控制器、数据绑定、作用域
- bootstrap栅栏系统css中的col-xs-*、col-sm-*、col-md-* 的意义以及 bootstrap一个标签中,同时有 col-xs , col-sm , col-md , col-lg的理解
- 基于封装通用的EF CRUD 的操作