YZH__12345-CSDN博客

原创 [bzoj2226][Spoj 5971] LCMSum

Orz w_yqts 转换成欧拉函数..#include <bits/stdc++.h>using namespace std;#define ll long long#define N 1000001int pn,pr[N],phi[N],flag[N];ll f[N];inline void solve(){ ll res=0LL; int n; scan

2018-01-11 11:35:19 285

原创 [bzoj2286][Sdoi2011]消耗战

虚树模板题.. Orz w_yqts#include <bits/stdc++.h>using namespace std;#define inf (1LL<<60)#define ll long long#define N 666666ll dp[N],v[N];int num,to[N],Next[N],head[N],len[N];int num1,to1[N],Next1[N

2018-01-11 07:50:53 319 1

原创 [bzoj4804]欧拉心算

Orz w_yqts 裸的反演..#include <bits/stdc++.h>using namespace std;#define ll long long#define N 10000001ll f[N];bool flag[N];int pn,pr[N];void init(){ flag[1]=1;f[1]=1LL; for (int i=2;i<N;+

2018-01-10 18:58:42 692

原创 [bzoj2724][Violet 6]蒲公英

http://www.docin.com/p-679227660.html 可以用冰点文库下载.. 用分块+可持久化线段树统计答案.. 有点毒瘤..#include <bits/stdc++.h>using namespace std;#define N 40005struct lisan{ int x,y;}b[N];bool cmpli(lisan x,lisan y)

2018-01-10 16:36:15 344

原创 [bzoj2824][AHOI2012]铁盘整理

冒泡排序强无敌 Orz w_yqts 爆搜剪枝#include <cstdio>#include <algorithm>using namespace std;short a[51],b[51],n,tot,l,r;inline void rotate(int l,int r){ while (l<r) swap(a[l++],a[r--]);}bool dfs(int d

2018-01-10 13:58:20 439

原创 [bzoj3545][ONTAK2010]Peaks

线段树合并 Orz w_yqts 在dalao指导下AC了…Orz WA的原因可能是在merge中如果a,b都是叶子会无法统计#include <bits/stdc++.h>using namespace std;#define N 2333333inline int read(){ char ch=getchar(); int x=0,f=1; while

2018-01-10 12:48:10 305

原创 [bzoj2938][Poi2000]病毒

Orz w_yqts trie图dalao 建完自动机判断是否能跑出环(不能经过有价值的点或后缀)#include <bits/stdc++.h>using namespace std;#define N 66666char s[N];int trie[N][2],point[N],tottrie;int danger[N],instk[N];int q[N],vis[N];void

2018-01-09 20:21:02 338

原创 [bzoj5020][THUWC 2017]在美妙的数学王国中畅游

Orz w_yqts lct+泰勒展开#include <bits/stdc++.h>using namespace std;#define db double#define N 666666#define m 20struct lct{ int c[2],f,rev; db s[m],v[m];}tr[N];db C[m][m];int top,stk[N];

2018-01-09 15:46:45 448

原创 [bzoj5142][Usaco2017 Dec]Haybale Feast

Orz w_yqts 在某王姓dalao的指导下暂时卡到rank1……Orz 二分答案#include <cstdio>#define ll long long#define N 100001inline int read(){ char ch=getchar(); int x=0; while ('0'>ch || ch>'9') ch=getchar();

2018-01-04 15:14:46 836 2

原创 [bzoj4407]于神之怒加强版

http://blog.csdn.net/w_yqts/article/details/78970490 Orz w_yqts#include using namespace std;#define ll long long#define p 1000000007#define N 5000005inline int read(){ char ch=getchar();

2018-01-04 14:30:26 339

原创 [bzoj1584][Usaco2009 Mar]Cleaning Up 打扫卫生

Orz w_yqts 卡了18次,终于rank1了… f[i]表示以i为结尾的最小代价 f[i]最大为i(每个点单独一段) f[i]=min{f[j]+cnt(j+1~i)^2} 若cnt(j+1~i)^2>i就可以退出了. 若存在相同数字可以用链表删除. 大概是O(n^3/2)的.#include <cstdio>#define N 40005inline int read()

2018-01-03 13:34:34 299

原创 [bzoj2733][HNOI2012]永无乡

Orz w_yqts 线段树合并裸题每合并一次减少一个节点,所以复杂度可以接受#include <bits/stdc++.h>using namespace std;#define N 100005struct node{ int s,l,r;}tr[2333333];int f[N],rt[N],a[N],id[N];int n,trsz;inline int fin

2017-12-26 11:22:08 284 1

原创 [bzoj3514] Codechef MARCH14 GERALD07加强版

裸题,Orz w_yqts lct维护最小生成树加边时弹出标号最小的边并记录询问n-(l~r中小于l的数个数),可持久化线段树维护#include <bits/stdc++.h>using namespace std;#define N 666666struct lct{ int c[2],f,to,v,rev;}tr[3666666];struct node{

2017-12-25 18:45:58 395 1

原创 [bzoj4176]Lucas的数论

Orz w_yqts Orz xudyh Orz popoqqq 求∑nx=1∑ny=1d(ij)\sum_{x=1}^n\sum_{y=1}^nd(ij) n<=109n<=10^9首先证明d(nm)=∑i|n∑j|m[gcd(i,j)=1]d(nm)=\sum_{i|n}\sum_{j|m}[gcd(i,j)=1] 若有n=n′∗pk1,m=m′∗pk2n=n'*p^{k1},m=m'

2017-12-08 15:57:24 594

原创 [bzoj3512]DZY Loves Math IV

给定n,m，求模10^9+7的值。听说是杜教筛裸题… 可能是我太鶸了.感觉好难啊.. Orz w_yqts Orz xudyh (i,j)=gcd(i,j)(i,j)=gcd(i,j) s(i,j)=∑i=1mφ(ni)s(i,j)=\sum_{i=1}^mφ(ni) ans=∑i=1ns(i,m)ans=\sum_{i=1}^n s(i,m) 对于n%p=0,有φ(n*p)=φ(

2017-12-07 17:51:56 524

原创 [bzoj3944]Sum

Orz w_yqts Orz xudyh 杜教筛模板题给定积性函数f(x) 函数s(x)为f(x)的前缀和 f(x)满足Σf(d)=g(x),d为x的约数,g(x)的前缀和可以在较短时间内算出. 求s(n) 从枚举约数到枚举倍数,将离散变为连续… 上面的j枚举的就是倍数,i是当前倍数可以支持的约数,不难发现,可以支持的约数是连续的. 预处理前n^(2/3),后面直接用map记

2017-12-06 15:49:05 376 1

原创 [bzoj3112][Zjoi2013]防守战线

裸题… 对偶一下直接跑单纯形…… Orz w_yqts#include <bits/stdc++.h>using namespace std;#define inf 1000000000#define eps (1e-9)#define db double#define N 100005db a[1005][10005],b[N],v,c[N];int m,n;inline vo

2017-12-01 14:35:57 427

原创 [bzoj1061][Noi2008]志愿者招募

裸题… 直接跑单纯形 Orz w_yqts#include <bits/stdc++.h>using namespace std;#define inf 10000000000.0#define eps (1e-9)#define db double#define N 1005#define M 10005db A[M][N],b[M],c[N],v;int n,m;inl

2017-11-30 15:16:57 441 1

原创 [bzoj1148][CTSC2007]挂缀pendant

大意:给定若干个任务,每个任务只能在给定时刻c[i]前开始,时长w[i],求最多能完成的任务. 可以看成: 有若干区间,给出长度len[i]和左端点l[i]的限制,选出尽量多使其互不重叠. 右端点限制r[i]=l[i]+len[i] 对于i < j,若r[i] < r[j]:如果j区间可以放置于i前,那么j区间一定也可以放置于i之后; 但是如果j区间不能放置于i前,j区间可能还是可以放置于

2017-11-17 13:53:35 353

原创 [NOIP2017][luogu3959]宝藏treasure

Orz w_yqts n<=12,状压.起点自定.每条边的贡献为层数*边权.每个点的连边不需要在意,只关注它对状态产生的贡献.(对于每个状态预处理,复杂度为O(2^n*n)).从小到大枚举层数,然后枚举初始状态,再枚举转移后状态.由于预处理,复杂度为O(3^n*n).(枚举转移的状态时,顺便统计每个新增点的贡献,而这个已经预处理完了)总体来说是O(2^n*n+3^n*n)的考场上只写了O(2^n*

2017-11-16 18:30:41 469

原创 [HNOI2001][luogu1128][bzoj1225] 求正整数

题目大意:求最小的x,使x的不同约数个数为给定值设x=π(p[i]^mi[i]) 其约数个数n=π(mi[i]+1) 于是爆搜n的组成方式 ps:用指数存储比高精度高到不知哪里去了 Orz w_yqts#include <bits/stdc++.h>using namespace std;#define eps (1e-9)int pr[17]={0,2,3,5,7,11,13,1

2017-11-14 16:54:39 369

原创 [NOIP2017][luogu3953]逛公园

大意:给定有向图G,求1->n的长度<=最短距离+K的路径方案数先求起点到每个点和每个点到终点的最短路,排除掉不可能到达的点防止其干扰(dis[i]+pdis[i]>dis[n]+K) 然后每条边的边权更新为len[x->y]+dis[x]-dis[y] (走这条边浪费的时间) 现在只需要统计浪费的时间不超过K的方案长度为0的边用拓扑序转移,长度>0的直接转移……(dp[x][j]->d

2017-11-14 11:40:20 465

原创 [bzoj1941]k-d tree 模板

在w_yqts 的指导下学习了kdtree…… http://blog.csdn.net/silangquan/article/details/41483689 听说这东西很优秀……Orz 但看起来就像一个暴力剪枝.#include <cstdio>#include <algorithm>using namespace std;#define inf 1000000000#define

2017-10-31 07:18:05 400

原创 [bzoj1112][POI2008]砖块Klo

http://www.lydsy.com/JudgeOnline/problem.php?id=1112 每次可以使任意一柱砖高度+1或-1，代价为1 求使任意一个长度为K的区间内砖的高度相同的最小代价只要动态维护中位数就可以了… 维护中位数可以用两个堆… n1为堆1大小,n2为堆2大小 s1为堆1和,s2为堆2和每次移动区间后维护abs(n1,n2)<2就能保证中位数的准确性了……

2017-09-28 11:53:29 310

原创 [bzoj2006][NOI2010]超级钢琴

http://www.lydsy.com/JudgeOnline/problem.php?id=2006 题目大意选择k个不同的区间使它们的和最大首先，我们可以把所有区间都丢到堆里，每次取出最大值但这显然是要爆炸的。。。然后，可以轻易发现一个明显的性质…(很明显吗…)(Orz w_yqts) 有若干三元组(x,l,r) l-x+1<=L,r-x+1<=r t(x,

2017-09-06 19:09:29 257 1

原创 [bzoj2154]Crash的数字表格

http://www.lydsy.com/JudgeOnline/problem.php?id=2154 Orz w_yqts 首先,lcm(i,j)=i*j/gcd(i,j) 显然,ans=ΣΣlcm(i,j) 为了方便，我们令n< m 于是…… PS:%为mod PSS:sum(x)=1+2+…+x PSSS:有多个*的地方请多加mod和long long 嗯..应该没

2017-09-04 18:28:09 333

原创 [bzoj3687]简单题

http://www.lydsy.com/JudgeOnline/problem.php?id=3687 首先，对于每个和如果出现次数超过1，只会产生0次或1次的贡献，因为x^x=0… 所以只需记出现次数and 1… f[i]表示和为i的集合出现次数and 1.. 对于每个新的数x都会使f[i+x]^=f[i]. 所以用bitset会比较优越 Orz w_yqts#include <bi

2017-09-03 20:57:47 319

原创 [bzoj4742][Usaco2016 Dec]Team Building

http://www.lydsy.com/JudgeOnline/problem.php?id=4742 dp[i][j][k]表示fJ前i只,FP前j只,各选了k只的方案数初值:dp[i][j][0]=1 方程: dp[i][j][k]=(dp[i-1][j][k]+dp[i][j-1][k]-dp[i-1][j-1][k]+(a[i]>b[j])*f[i-1][j-1][k-1])mo

2017-09-03 19:20:22 363

原创 [bzoj4010][HNOI2015]菜肴制作

题面http://www.lydsy.com/JudgeOnline/problem.php?id=4010题干给定n个点，m条边的有向图。求一个排列p使对于所有x->y有p[x]< p[y] 且序号小的值尽量靠前题解乍一看是求字典序最小的拓扑序列其实并不是。。可能是我太鶸了,其他dalao就不这么觉得… Orz w_yqts 这里有一个反例.. 请不要吐槽为什么图片这么丑…

2017-09-03 18:20:55 337

原创 [bzoj2005][luogu1447][noi2010]能量采集

Description栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植物种得非常整齐，一共有n列，每列有m棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标(x, y)来表示，其中x的范围是1至n，表示是在第x列，y的范围是1至m，表示是在第x列的第y棵。由于能量汇

2017-09-03 17:08:22 480

原创 [bzoj1054][HAOI2008]移动玩具

http://www.lydsy.com/JudgeOnline/problem.php?id=1054无聊时想练一下构图又懒得打广搜…… 发现状态只有2^16种于是根据相邻状态连边（最多只有2^22条边（极有可能不到））然后直接跑最短路即可代码如下#include <bits/stdc++.h>using namespace std;#define N 100005#defi

2017-05-27 16:31:00 1910

蒟蒻YZH的博客