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

ydc的博客

 
 
 

日志

 
 

SDOI Round2 Day1  

2015-05-16 18:20:22|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
最近有幸膜到了贵省的题目,感觉自己生活非常无聊,就来更一发博客骗访问量。

我没有任何代码实现
纯属BB
每道题不保证算法正确,纯属抢占题解市场

听说题意是这样的
T1:
给一个数组a,操作有两种,一种是将数组a区间±1,一种是查询一段区间的ΣF(A[i]+1)*F(A[i]-1)的和
F[1]=1,F[2]=2,F[n]=F[n-1]+a*F[n-2]+b,n>2
n<=300000

窝来说一种会被卡常数的做法
首先F[n]能看做一个矩阵的若干次方,这个矩阵的逆矩阵可以用F[n-2]=(F[n]-b-F[n-1])/a推,或者强行高斯消元逆矩阵
所以就是区间*一个矩阵
所以线段树维护矩阵就好了
不过n这么大,似乎会被卡常数的样子?
(ydc个逗逼,滚粗了)
T2:
一个n个点m条边的无向图,n<=1000,m<=5000,给定k,对于每对i,j,判断能否有i到j的包含k个点的简单路径(i,j也算)
k<=7

如果k=4的话,暴力复杂度不会超过O(m^2)……有没有更紧的上界我不知道,我也不知道极限情况下会是多少
反正看起来能过的样子
那就先折半吧
dp[i][j][k]为i~j经过k个点的方案数(为什么要求方案数而不是记个bool呢,因为方案数可减,便于后面的容斥)

取极限情况k=7
枚举一条i->a->b->x的路径,i能否到j,就是看能否有x到j不经过i,a,b
也就是dp[x][j][4]-不合法的
人脑容斥
先是x走一步到i,a,b的情况
那就是(x,i有边)*dp[i][j][3],a,b类似
可以直接算
然后是x走两步到i,中间不经过a,b的情况(走两步到a,b类似),方案数要乘以dp[i][j][2],注意dp[i][j][2]=(i,j)有边,dp[i][j][1]无意义
那么只要算x走两步到i,中间不经过a,b的方案数就可以了
继续容斥
就是dp[x][i][2]-(x->a->i这条路径是否合法)-(x->b->i这条路径是否合法)
然后……啊……没了
时间复杂度是O(四个点的路径个数)
T3:
有totS个长度为n的字符串和totT个长度为m的字符串
2|n+m
取一个长度为n的字符串和一个长度为m的字符串,问有多少方案拼起来后得到的字符串的左半与右半循环同构

假设n>m
把左边串第i个串的前[(n+m)/2]位拿出来当新的串
翻倍,把每个(n+m)/2长的循环串记下来,去重
假设有一个串的开头,等于第i个串的右边n-(n+m)/2部分,就砍掉这部分,在B串里查询有几个这样的串
时间复杂度就是O(n*tots+m*totT)了
  评论这张
 
阅读(539)| 评论(3)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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