ahsofnu模拟赛思考题solution_第1页
ahsofnu模拟赛思考题solution_第2页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

提高组（请选手务必仔细阅读本页内容1秒秒5PascalPascalCC++PascalPascalfpcfpcfpcCgccseq.c–ogccset.cgccsubgraph.cC++g++seq.cppg++set.cpp–og++subgraph.cppC/C++main()int0NOILinux【问题描述

n的非负整数序列a1a2a3an，每次操作可以选择相邻的两个数ai,ai1，删去它们，然后在这个位置一个数max(ai,ai1)，此次操的代价定义为max(aiai11【数据规模30%n50%n100%的数据，1n10000000

【数据规模OJ3050犇有这种做法愿意的==考虑更优秀的做法：算法1： 先把左右两部分合起来然后再与这个值合并== 的问题就是区间查询最大值，这个无论是用线段树还是用ST算法之类的都没问题。。当然这个时间复杂度O(nlogn)，得分要看常数。：算法2从左往右读入序列，用一个单调栈，当新加进去的数>栈顶：素也是要合并的。。时间复杂度O(nAC3：（标程的做y<=x。然后呢这些数合并起来，再与x合并，那么这个代价就是x了这下子做法就出来了==答案就 max(ai,ai1)，时间复杂度O(n)（果然本弱出的题很弱，找的题也很弱是不是【问题描述

给定三个正整数lrk，构造一个整数集合S1、对于Sx，均有lxr2、1|S|3、集合S【数据规模20%T20且rl16。10%k1。30%l,r对于100%的数据保证有1lr1012,1 每个测试点中所有测试数据的k值总和不超过106【问题分析题目来源 1，S={2t,2t+1,2t+2,2t+3}0所以对于取值范围足够大的情况，只要考虑k≤4的情形就好了=k=1k=2S={2t,2t+1}k=30对于一个位，三个数中要有偶数个数该位上为 考虑最高的1出现2次的位，则三个数一定为如下形式：1x1x 考虑下一位，如果三个数这个位上均为0（即10 1000），那我们就替换成011xx010xx001xx即可（这样子的方案一定可以取到）。 01时间复杂度O(Tlogr（果然本弱出的题很弱，找的题也很弱是不是【问题描述

给定一张无向图，每个点都有一个非负整数点权wi12、第一类的两个不同的点u,v之间有连边当且仅当(wuxorwvmod213、第二类的两个不同的点u,v之间有连边当且仅当(wuxorwv)mod20，或者(wuorwv在二进制表示下有奇数个1。【数据范围20%的数据，有ab20a200b200。a5b1500i100%的数据，满足：1T5ab10w231i【问题分析 20分的做法不用本弱讲了吧==233（2333接下来计算第二部分最多能有多少个点==看来还要再挖一些性质。。or1xor连边的==那么问题就转化为求最大完全二分图==求这个二分图补图的最大点独时间复杂度理论上是O(

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论