注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

我的集训队作业草稿  

2014-09-21 16:50:09|  分类: 集训队作业 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
以下是第一部分

先上官方版
http://pan.baidu.com/s/1hqvKx5y
求校对,求帮忙指出错别字or算法错误T_T

由于上面那份废话连篇,这里放简单题解
T1:简单题。答案显然可以二分,判定就是模拟这个操作,我们用个优先队列就可以O(n log^2 n)了。这是我的第一眼想法,事实上还有O(n log n)的做法,我没去管了
T2:简单题。找直径,找中心,没了。
T3:我不会做的题T_T。二分答案。A[i]表示钱为i要变成i+1/G,那个分数规划函数的期望值。如果i=R,A[i]就是变成R的期望值。然后分i<1,1<=i<R,i=R三种情况转移,时间复杂度O(TnRG*logAns)。还是看官方版的作业吧

然后是第二部分……首先我会做学校里另外四个人的12题
泛做题放这里只是草稿,不是正式的,为了防止忘记怎么做

319E Ping Pong
有一个区间集合
两个区间[a,b],[c,d],若c<a<d或者c<b<d,则a向b连一条有向边
要求支持
1、动态插入一个区间(保证每个区间长度严格大于前面的区间)
2、询问两点连通性

简单题解
有边要么是a包含b,要么是非包含相交
假设只考虑非包含相交,我们要做的是维护每个区间向左、右最多延伸的数组L,R
用线段树把区间拆成log n段,在对应的这些节点上存vector,将线段插入进去
要求L,R的话,我们在线段树里查询包含了左端点或者右端点的所有线段,用并查集并起来并维护L,R。
被他包含的自然就不会访问到
这样会存在一个问题,就是这个做法会把包含它的线段给考虑进来。
由于题目保证插入的区间长度严格大于前面的区间长度,我们知道不会有这种情况的发生,所以这个做法就能恰好过滤掉包含它的与它包含的,留下的就是和他非包含相交的所有线段。用并查集并起来,一个集合最后会是一条大线段。最后会判断一个线段是否能到另一个线段,就是判断他们是否属于同一个集合或者a所对应的大线段是否可以到达b
复杂度O(n log n)

306B
n个区间要你删除最多的区间使得区间并等于原区间并

简单题解
转化为留下最少的区间
记录R[i]表示以i为左端点最远的右端点,maxv[i]表示前缀最大值
贪心法则是从左往右扫过去,如果i被应被覆盖且未被覆盖,则now=i,之后不断执行now=maxv[R[now]+1]之类的事情……也就是每次跳到能跳到的最远的
复杂度O(n+m)

316D3
刚开始是1~n的排列,你每次能交换两个数。每个位置有交换次数上界,此上界保证非1即2。求有多少排列能交换得到
简单题解
排列转化为拆成若干个循环
容易证明等价于要你拆成若干个循环,每个循环里1的个数不超过2
枚举有几个单独的1。然后进行组合计数,时间复杂度是O(n)的

261D
给长度为n的序列,问这个序列重复t次以后的LIS。
n,maxb≤10^5,n*maxb≤2*10^7,t≤10^9。(翻译是直接从Saffah那里抄来的)
简单题解
我刚开始发现结论t<=min(n,maxb)……结果刚刚才竟然一点用都没用上T_T
dp[i][j]表示LIS长度为i,结尾是j,用到的最小的下标
转移很容易
只要找最大的i使得存在j满足dp[i][j]<=n*t即可

267C
给出一个n个点的带权无向图,满足对于任意一个大小为k的顶点集合S,恰好有一个点与S每一个点都有边。令这个点为v(S),并且对S进行操作的代价是S中每个点与v(S)的边权之和。现在求对于一个大小为k的子集操作代价的期望。
n<=2000
简单题解:
我简直觉得是用傻逼做法水过得
考虑算贡献
i->j的一条为c[i][j]的边,假设i的度数是deg[i],贡献就是C(deg[i]-1,k-1)
于是就是ΣΣc[i][j]C(deg[i]-1,k-1)/C(n,k)(要求i,j有边)
这样子的话样例2发现有精度误差……我算出来是13.9999999999998什么的,我就加了个1e-10,过了样例
WA on test 21
我就加了个1e-3,水掉了
被lyy给D了!他告诉我说k只能等于1,2,n-1,n。
跪烂了
(lyy刚才说他不会出数据卡我啦啦啦)

剑哥哥竟然换题了233
换成了360D
不过http://ydcydcy1.blog.163.com/blog/static/216089040201310239321650/

267 C
要你跑一个1~n的网络流,满足起点到任意一个点的任意一条路径的流量之和是一样的。求最大流以及一种方案
n<=100,边数<=5000
简单题解
设起点到每个点的流量之和是x[i]
对于起点,x[i]=0;其余的除了终点以外的点,能用流量平衡列方程
假设最大流是1,可以再列个方程
解出所有x,然后我们找到最小的c[i]/abs(x[a[i]]-x[b[i]])就是答案了……换句话说是每条边的流量同时乘以这个数
时间复杂度O(n^3)

妈呀不想写题解了
  评论这张
 
阅读(740)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017