3 wanherun

尚未进行身份认证

今天会有好事发生吗

等级
TA的排名 2w+

bzoj5016 [Snoi2017]一个简单的询问

题目首先,可以确定的是,这一定是一道数据结构的题,但是,题目询问的式子过于复杂,我们要先考虑化简一下。首先,吧get(l,r,x)变成get(r,x)−get(l−1,x)是非常显然的,新的get(n,x),表示1…n有几个x首先,吧get(l,r,x)变成get(r,x)-get(l-1,x)是非常显然的,新的get(n,x),表示1\dots n 有几个xget(l1,r1,x)get(l2,r

2018-03-11 21:26:25

bzoj5018 [Snoi2017]英雄联盟

题目嗯,其实吧,还是算比较显然的dp。 f[i][j]表示前i个英雄,用了j元钱的最多方案数,最后答案就是满足f[n][j]≥m最小的j了。f[i][j]表示前i个英雄,用了j元钱的最多方案数,最后答案就是满足f[n][j]\ge m最小的j了。 转移方法,首先,肯定要枚举i,然后枚举当前买几个皮肤j,再枚举l表示f[i][l]从什么转移过来。注意,每次l的上界是当前买所有皮肤的价格。转移方法,

2018-02-28 19:51:26

WC2018 游记

有到了一年一度的ccf冬令营了,我也有幸参加了这次冬令营。其实去年也是来过的,但无奈暴力写挂了,与

2018-02-12 15:04:09

bzoj4916 神犇和蒟蒻

题目首先,由μ\mu的性质知道,第一问的答案一定为1。考虑第二问。 φ(i2)=iφ(i)\varphi(i^2)=i\varphi(i) 令Φ(i)=∑ni=1iφ(i)\Phi(i)=\sum_{i=1}^{n}i\varphi(i) 则发现 ∑ni=1iΦ([ni])=∑ni=1i∑[ni]j=1jφ(j)\sum_{i=1}^{n}i\Phi([\frac{n}{i}])=\

2018-02-02 10:26:24

loj125 杜教筛

题目由题目猜算法系列。已知f(n)=∑d|ng(d)与g(n)=2n2+3n+5,求∑ni=1f(i)已知f(n)=\sum_{d|n}g(d)与g(n)=2n^2+3n+5,求\sum_{i=1}^{n}f(i) 令F(i)=∑ni=1f(i)F(i)=\sum_{i=1}^{n}f(i) 则发现(前面的系数需要凑一凑) ∑ni=1μ(i)F([ni])=∑ni=1μ(i)∑[ni]j=1f

2018-02-02 10:14:41

bzoj3944 Sum

题目杜教筛第一题。数学推导过程详见这里具体实现的时候要用一个hash表或者map存一下,其实感觉两个东西差不多快。想要提高速度应该调一调M的大小,可以三分试一试呀。#include<bits/stdc++.h>#define ll long long #define M 4500000using namespace std;int prime[M+5],notp[M+5],cnt;ll m

2018-02-02 10:01:53

杜教筛学习笔记

考虑求解以下问题: ∑ni=1μ(i)\sum^{n}_{i=1}\mu(i) ∑ni=1φ(i)\sum^{n}_{i=1}\varphi(i) ∑n(i=1)μ(i)ik\sum^{n}_(i=1)\mu(i)i^k令M(i)=∑ni=1μ(i)M(i)=\sum^{n}_{i=1}\mu(i) 发现 ∑ni=1M([ni])=∑ni=1∑[ni]j=1μ(j)\sum^{n}_

2018-02-01 19:23:21

莫比乌斯函数学习笔记

(1) 定义 e(n)=⟮1 n=10 n≠1e(n)=\lgroup^{1\ n=1}_{0\ n\neq1} I(n)=1I(n)=1 id(n)=nid(n)=n σ0(n)因子个数\sigma_{0}(n) 因子个数 σ1(n)因数和\sigma_{1}(n)因数和 μ(n)莫比乌斯函数\mu(n)莫比乌斯函数 φ(n)欧拉函数\varphi(n)欧拉函数 (2)

2018-02-01 16:07:00

bzoj3529 [Sdoi2014]数表

题目如果不考虑a的限制,这道题就简化了一下。令f(x)f(x)表示x的约数和,g(x)=∑ni=1∑mj=1[gcd(i,j)==x]g(x)=\sum^{n}_{i=1}\sum^{m}_{j=1}[gcd(i,j)==x] 那么,ans=∑ni=1f(i)g(i)ans=\sum^{n}_{i=1}f(i)g(i),由某道题可得g(i)g(i)的表达式。 YY的GCD g(i)=∑i|dμ

2018-02-01 14:17:34

bzoj2440 [中山市选2011]完全平方数

题目首先,直接得出答案貌似不太可能,我们可以先二分一个答案,这样就成了计数问题了,就是求前n个数中,有多少个数没有平方因子。很显然的一点,就是μ\mu值不为0的数有多少个,但是,这样是算不出来的,因为太大了,所以我们就要想一想办法。考虑容斥原理,发现前面的系数刚好为μ\mu值,最后我们只需要算一个求和式子∑x√i=1[xi2]\sum^{\sqrt{x}}_{i=1}[\frac{x}{i^2}]就

2018-02-01 13:36:52

bzoj2820 YY的GCD

题目这肯定要用卷积的,我们来推一推公式。我们先令n=min(n,m)n=min(n,m),m=max(m,n)m=max(m,n)则 ans=∑p∑ni=1∑mj=1gcd(i,j)==pans=\sum^{}_{p}\sum^{n}_{i=1}\sum^{m}_{j=1}gcd(i,j)==p ans=∑p∑[np]i=1∑[mp]j=1gcd(i,j)==1ans=\sum^{}_{p}\s

2018-02-01 11:49:25

poj3683 Priest John's Busiest Day

题目2-sat问题,要求要输出方案。先考虑建模,把每个婚礼都拆成两个部分。对于两个婚礼,A,B,用A,B表示开始,A’,B’表示结束,如果A与B,B’都冲突的话,A就不能选,连向A’,否则只有一个冲突的话,A连B’,A’连B。这样图就建好了,那么如何输出方案呢,一般tarjan后跑一个拓扑序就好了,但是有更好的方案,tarjan相当于就是一个拓扑了,最后只要A与A’谁的强连通分量编号小就选谁就好了。

2018-01-27 08:56:07

loj6157 A^B Problem

题目树上一条路径上边权的异或,显然相当于两个到根的异或再异或起来。 这样,相当于我们每次都知道到根的异或值。这样我们就可以并查集处理了,记录到根的异或值,每次判断一下就好了。#include<bits/stdc++.h>#define N 500000 using namespace std;int T,n,m,x,y,f[N+5],w[N+5],z,flg;int u[N+5],v[N+

2018-01-27 08:38:18

bzoj1467 Pku3243 clever Y

题目扩展BSGS,模数改成任意数了,本质和一般的还是一样的,只是需要把X与K推一推公式让他们互质就好了。具体细节在代码中有体现。#include<bits/stdc++.h>#define ll long longusing namespace std;ll a,b,p;ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}ll BSGS(ll a

2018-01-27 08:24:48

bzoj3331 [BeiJing2013]压力

题目显然,如果两个点之间要有一个必须到达的点,这个点必须是割点。只要我们求出点双联通分量,然后对图重构,在新得到的树上做就好了。我们在树上就可以差分了,最后求一个子树和就好了。#include<bits/stdc++.h>#define N 500000 using namespace std;int first[N+5],nxt[N+5],to[N+5],siz;int First[N+5

2018-01-27 08:17:12

bzoj3337 ORZJRY I

题目哇,好繁琐的一道数据结构题,居然有11个丧心病狂的操作。据说正解是块状链表,但写起来特别麻烦,要接近400行才能写完,而且有些操作比较难维护。这个时候,就要用一些黑科技了,叫odt,,全名是什么我也不太清楚,在处理随机意义下的含区间覆盖操作的数据结构有奇效,大概思路就是用STL把相同值的一串合并在一起算。typedef pairint,int> pii;struct line

2018-01-27 08:08:58

bzoj3028 食物

题目母函数,数学题,大概就是推公式吧。承德汉堡:1+x2+x4+⋯=11−x21+x^2+x^4+\dots=\frac{1}{1-x^2} 可乐:1+x1+x 鸡腿:1+x+x21+x+x^2 蜜桃多:x+x3+x5+⋯=x1−x2x+x^3+x^5+\dots=\frac{x}{1-x^2} 鸡块:1+x4+x8+⋯=11−x41+x^4+x^8+\dots=\frac{1}{1-x^4

2018-01-23 14:01:52

bzoj3969 [WF2013]Low Power

题目看见最大值最小,明显可以看出这是一道二分答案的题。如何判断呢。首先,我们先对原数组排序,这样每次的差最小一定会在两个相邻的数之间。所以排好序之后,判断的时候,只要从前往后扫,只要相邻两个数的差小于二分的答案x,就把它们放入一个电池,然后把剩下的电池依次放入,判断每个时刻是否可行就好了。#include<bits/stdc++.h>#define N 1000005using namespac

2018-01-22 07:53:00

codeforces438 D The Child and Sequence

题目一句话题意:支持区间取模,单点修改,区间求和的数据结构。后两个操作都是可以线段树操作的,但是第一个貌似就特别麻烦了。貌似不可做的样子呀,但是,我们可以发现一个性质如果x>yx>y那么xmody≤x2x\mod y\leq \frac{x}{2}的,这样的话,我们可以维护一下区间最大值,如果小于模数,就直接return,不然暴力做就好了。复杂度可以用势能分析得出是对的,我也不太会,就不多说了//区

2018-01-19 11:09:00

bzoj4320 ShangHai2006 Homework

题目学习了一种新知识,根号分治,也叫bigsmall。其主旨思想就是把每个问题分成大于n  √  \sqrt{n}与小于n  √  \sqrt{n}的来考虑。对于这道题,我们可以对Y分类。记m=n  √  m=\sqrt{n} 1.如果Y≤m Y\leq m,可以用一个数组g[i],表示当前集合中%i最小的数,每次询问是O(1)的,修改是O(m)的。 2.如果Y>m Y>m,我们

2018-01-19 10:28:50

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!