4
19
2015
2

2015省选互测#4

开场看A,发现在用完了1-i-1的操作后,每个1<<i的块都必须保证单调增且连续。因为之后这些块之间的相对顺序不会再发生改变。但我不知道这能有什么用,还是只会爆搜。

看B题,这不set+dfs序大水题吗,100分到手。

看C,好有趣的题目啊。DP蛮容易想的,看看能拿几分尼玛在逗我 只有10分

     然后发现每次转移好像都是固定的,构造矩阵就可以O(m^3logn)了。尼玛 只有30分

弃疗了。。。

扭头写B。写完,这么好写 肯定不用拍(爆零前兆)然后去拍了拍T3

于是就去写A了。

下来就哭了if(l&&r)打成if(l&r) 100->0

还没暴力高

难道我有考场上写不对数据结构的debuff?

以后再不对拍就剁手!!!!

 

 

好像前面扯得有点多?接下来再说正经的

B BZOJ3991: [SDOI2015]寻宝游戏题

不说了dfs序+set水题。

C 3992: [SDOI2015]序列统计

上面的算法好像还可以优化?直接用快速幂,而不是矩阵乘法(因为我们可以在O(m^2)的时间由f[i]的答案推出f[2*i],而且可以用O(m^2)的答案合并f[i]和f[j],这样好像可以得到60分?考场上sb了没想到这个性质QAQ)

然后这样我们其实一直没有用到一个条件:m是质数!

质数有什么特殊的东西?保证存在逆元?这里根本用不上逆元啊。还有呢?奇质数一定有原根!

原根的好处通常是可以把mod p意义下的乘法转化成加法,这样我们就可以转化成n个数,每个数可以取0-m-2然后和%m=x的方案数?

怎么做?模仿上面的做法,我们发现我们用fft可以在O(nlogn)的时间内由f[i]的答案推出f[2*i],以及合并f[i]和f[j]。

这样总的复杂度就是O(mlogmlogn)真是一道综合性的好题

A 3990: [SDOI2015]排序

1)首先注意到一个结论如果0--i-1的操作全部用完了,那么长度为2^i的每块内必须是合法(即单调递增且连续),因为我们没有其他操作能改变这些块内元素的相对位置了。

其实我考场上想到了这个性质,但我不知道有什么用QAQ

2)操作的先后顺序是互不影响的。这个感性理解一下应该是显然的。所以我们可以从0-n-1开始枚举我们要进行的操作。到了终点ans+=fac[cnt]其中cnt表示用了多少个操作,然后fac表示阶乘

3)假设当前正在处理第i个操作,那么长度为2^i+1的块不合法的顶多只有2块(否则不可能通过一次合法)

  假如有1块,我们只有一种交换方式。递归下去即可。

  假如有2块,我们有4种交换方式,枚举即可。

然后这样就可以了。复杂度不太好估计。但据说最坏是O(2^(2*n))的。

这种题目真得好好动动脑筋!!!大胆猜想!简化问题(比如2这一步,大大简化了问题)

还有一个小问题是使用vector的时候  a.resize(n)表示给n分配了n个空间0-n-1,这样就可以像数组一样直接访问下标了!

之所以用vector是因为vector可以整体赋值而数组只能用指针但我不会

 

Category: 模拟赛 | Tags: | Read Count: 737
Avatar_small
iwtwiioi 说:
2015年4月20日 16:16

【vector本来就是可以访问下标的【捂脸熊

Avatar_small
zyfzyf 说:
2015年4月20日 18:08

@iwtwiioi: 如果不resize的话,好像必须写a.push_back(x)?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com