wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

[poj1201][Intervals]

poj1201_差分约束题目大意：给定n个区间，[ai,bi]这个区间至少选选出ci个整数，求一个集合z，满足每个区间的要求，输出集合z的大小。思路: 既然是区间，想到用前缀和。用sum[i]表示前i个元素中选的数量。对于每一个条件[ai,bi]中至少选ci个，就转化为了sum[bi]...

差分约束

2018-09-11

0 410

[noip][2016]

Day1T1 思路：非常简单的一个模拟代码： #include<cstdio> #include<iostream> using namespace std; const int N=1e5+100; int a[N],n,m,cr[N]; char s[N][5...

noip

2018-09-08

0 419

[noip][2016]

Day1T1 思路：非常简单的一个模拟代码： #include<cstdio> #include<iostream> using namespace std; const int N=1e5+100; int a[N],n,m,cr[N]; char s[N][5...

noip

2018-09-08

0 562

[noip][2017]

Day1T1 30分思路：倒着枚举答案z，用扩展欧几里得求解，如果能找到两个非负整数x,y使得ax+by=z则继续枚举，直到无解为止 100分：最适用与考场上的做法，根据30分思路打表找规律。 30分代码: #include<cstdio> #include<ios...

noip

2018-08-29

0 556

[noip][2017]

Day1T1 30分思路：倒着枚举答案z，用扩展欧几里得求解，如果能找到两个非负整数x,y使得ax+by=z则继续枚举，直到无解为止 100分：最适用与考场上的做法，根据30分思路打表找规律。 30分代码: #include<cstdio> #include<ios...

noip

2018-08-29

0 393

[luogu2822][组合数问题]

题目链接题解: 对于上面和下面的式子进行分解质因数，然后看看上面的质因数个数减去下面的质因数个数能不能达到k的质因数的要求即可。分解质因数的时候用对于阶乘分解质因数的常用方法:比如要求1999！中能分解出多少个5，那么就把1999不断的除以5，并且把得到的数相加即可。原因显然。但是上面...

数论

2018-08-25

0 512

[luogu2822][组合数问题]

题目链接题解: 对于上面和下面的式子进行分解质因数，然后看看上面的质因数个数减去下面的质因数个数能不能达到k的质因数的要求即可。分解质因数的时候用对于阶乘分解质因数的常用方法:比如要求1999！中能分解出多少个5，那么就把1999不断的除以5，并且把得到的数相加即可。原因显然。但是上面...

数论

2018-08-25

0 475

关于gcd的四道题

T1:bzoj2705 题目描述：给定一个n求\(\sum\limits_{i=1}^ngcd(i,n)\) 因为n太大，所以O(n)的做法肯定不行，然后就去想根号的方法。 \[\sum\limits_{i=1}^{n}gcd(i,n)\]\[=\sum\limits_{k|n}k*\su...

数论

2018-08-25

0 393

关于gcd的四道题

T1:bzoj2705 题目描述：给定一个n求\(\sum\limits_{i=1}^ngcd(i,n)\) 因为n太大，所以O(n)的做法肯定不行，然后就去想根号的方法。 \[\sum\limits_{i=1}^{n}gcd(i,n)\]\[=\sum\limits_{k|n}k*\su...

数论

2018-08-25

0 448

[luogu1967][货车运输]

题目链接题意：其实题目的意思就是问从x到y权值最小的路的权值最大能是多少。思路：首先可以先把这张图变成一棵树。因为那些更小的点肯定是不跑更优秀，而且题目没有要求路程，所以生成一棵树，只要能保证在同一个图里面的点能够连通即可。又因为他要使最小权值最大，所以可以只留下那些权值更大的边。所...

最近公共祖先最小生成树

2018-08-21

0 467