2019.7.26 NOIP 模拟赛
2024-08-24 22:25:21
这次模拟赛真的,,卡常赛。
The solution of T1:
std是打表,,考场上sb想自己改进匈牙利然后wei了(好像匈牙利是错的。
大力剪枝搜索。代码不放了。
这是什么神仙D1T1,爆蛋T1,好像A了它或拿分的就几个人,,
The solution of T2:
题解是这么写的:和八皇后很像,八皇后是x+y和x-y来判重,这里就k1x+k2y来判重。
从各个点引出直线,带入原点检验方程即可。
注:
x/y = Δx/Δy
x*Δy = Δx*y
下面代码用了这个原理,省去了gcd(或除法)的时间复杂度或精度问题
Code:
#include <cstdio> #include <map> #include <algorithm> using namespace std; ; map <long long,int> M[N]; map <long long,int> T; int n,m,i,j,k,q,tx,ty,s,num; int x[N],y[N],dx[N],dy[N]; bool pd; ?a:gcd(b,a%b);} int main() { freopen("laser.in","r",stdin); freopen("laser.out","w",stdout); scanf("%d",&n); ;i<=n;i++) { scanf("%d%d",&tx,&ty); ) tx=-tx,ty=-ty; y[i]=-tx,x[i]=ty; tx=abs(y[i]),ty=abs(x[i]),k=gcd(tx,ty); y[i]=y[i]/k,x[i]=x[i]/k; ;j<i;j++) if ((x[i]==x[j]) && (y[i]==y[j])) { i--,n--; break; } } scanf("%d",&m); ;i<=m;i++) { scanf("%d%d",&tx,&ty); ;j<=n;j++) M[j][1LL*tx*x[j]+1LL*ty*y[j]]++; T[tx*()+ty]++; } scanf("%d",&q); ;i<=q;i++) { s=; scanf("%d%d",&tx,&ty); ;j<=n;j++) s=s+M[j][1LL*tx*x[j]+1LL*ty*y[j]]; s=s-(n-)*T[tx*()+ty]; printf("%d\n",s); } ; }
T2
所以,我只拿了60分。神tmD1T2
The solution of T3:
剪枝细节,,一堆的。不过和D1T3难度低一点吧。
考虑用 SPFA 迭代计算到达每个点存活且残余的最大 HP。(请注意加粗字体,旁边的大佬ldl因此 100->90 )
考虑到 SPFA 本 身是一个广搜的过程,自然也可以类似广搜地统计最少时间。因此,直接跑 SPFA 即可。时间复杂度 O(EAns)。
Code:
#include <cstdio> #include <algorithm> using namespace std; ],next[],dist[],first[]; ],d[],g[],h[],p[],r[]; int i,k,m,n,x,y,z,head,tail,sum_edge; int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); scanf("%d%d%d",&n,&m,&k); ;i<=n;i++) scanf("%d",&r[i]); ;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); sum_edge++,edge[sum_edge]=y,next[sum_edge]=first[x],dist[sum_edge]=z,first[x]=sum_edge; sum_edge++,edge[sum_edge]=x,next[sum_edge]=first[y],dist[sum_edge]=z,first[y]=sum_edge; } d[]=p[]=k; tail++,g[tail]=,h[tail]=; ;head<=tail;head++) { if (g[head]==n) { printf("%d\n",h[head]); ; } ]) for (i=head;i<=tail;i++) d[g[i]]=p[g[i]],b[g[i]]=; ;i=next[i]) if ((d[g[head]]>dist[i]) && (min(d[g[head]]-dist[i]+r[edge[i]],k)>p[edge[i]])) { p[edge[i]]=min(d[g[head]]-dist[i]+r[edge[i]],k); if (! b[edge[i]]) tail++,g[tail]=edge[i],h[tail]=h[head]+,b[edge[i]]=; } } printf("-1\n"); ; }
代码是老师的
这题我莫名从60/70 -> 30???
神tmT1T2
最新文章
- ORA-12154:TNS:无法解析指定的连接标识符
- 通过sqlserver发送邮件
- 通过jquery获取ul中第一个li的属性
- 使用ELK(Elasticsearch + Logstash + Kibana) 搭建日志集中分析平台实践--转载
- RabbitMQ 一二事(3) - 订阅模式(微信公众号模式)的应用
- mysql的常用函数
- Form_Form Builder本地部署运行的实现(案例)
- [翻译]Python——十年语言之冠
- Jsp页面里引入一个javascript文件,在jsp的onclick里怎么添加脚本文件里的方法
- 【JAVA】使用Eclipse依赖生成jar包时,避免最外层同时生成资源文件的配置。
- ASP.NET自定义控件组件开发 第五章 模板控件开发
- Android4.2.2源码目录结构分析
- cmd 执行Dcpromo错误:在该 SKU 上不支持 Active Directory 域服务安装向导,Windows Server 2008 R2 Enterprise 配置AD(Active Directory)域控制器
- HashMap 学习 (JDK8)
- LDAP &; Implentation
- Android开发属性动画
- 【添加tomcat里lib下的jar包】eclipse中The project cannot be built until build path errors are resolved
- 一步步创建第一个Docker App —— 4. 部署应用
- Pythonic版二分查找
- C#中的静态常量(const)和动态常量(static和readonly)用法和区别
热门文章
- web开发jsp页面遇到的一系列问题
- java_第一年_JavaWeb(4)
- java_第一年_JDBC(2)
- 4、、多变量线性回归(Linear Regression with Multiple Variables)
- Centos7.6替换自带的jre安装jdk
- BZOJ 1040 [ZJOI2008]骑士 (基环树+树形DP)
- elasticsearch 基础 —— Query String
- 从零开始的PHP生活Day1
- CodeForces - 343D 树链剖分
- Sass--混合宏的不足