math

<div class="post_brief"><p> 今天几乎讲了一天的算几。或者说能听的只有算几。然后就去做了一道基础题。</p>   刚开始的时候比较naive，把相交的情况想简单了，打算直接上数学，然后悲剧地发现还有其它的不好算交点的情况，于是就去写simpson了。   simpson就是一个估计用的，s = (4 * f(mid) + f(l) + f(r))*(r-l)/6。至于为啥是对的就不知道了。反正比较能用。然后每次直接去扫一遍所有能交的地方，取max就行了，比挨个算交点方便许多。   然后第一次写，代码也比较乱。 #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int maxn = 509; const double pi = asin(1) * 2; const double eps = 1e-6; #define x1 x1 #define x2 x2 #define y1 y1 #define y2 y2 int n; double tht, x[maxn], h[maxn], r[maxn]; double crd[maxn]; double x1[maxn], x2[maxn], y1[maxn], y2[maxn]; bool c[maxn];...

<div class="post_brief"><p> 记得这是高一的时候ty同学和我说的东西了。然后现在才解决，可以打败上帝造题的七分钟，荣登解决时间最长的题目了。</p>   其实也就是一个高斯消元，用电势来列方程。不过高斯消元写得不熟，平时有空都写ds的题去了。以后不能再这样了。   用自己的代码高亮脚本了，虽然还不完善不过还是很开心的。   #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> using namespace std; const int maxn = 109; const double inf = 1e100; const double eps = 1e-8; double x[maxn], a[maxn][maxn], b[maxn][maxn]; int n, m, perm[maxn]; int main() { #ifndef ONLINE_JUDGE freopen(“in.txt”, “r”, stdin); #endif srand(19970911); while (scanf("%d%d", &amp;n, &amp;m) != EOF) { for (int i = 1; i &lt;= n; ++ i) perm[i] = i; if (n &gt; 2) random_shuffle(perm + 2, perm + n); for (int i = 1; i &lt;= n; ++ i) for (int j = 1; j &lt;= n; ++ j) if (i == j) a[i][j] = 0; else a[i][j] = inf; while (m --) { int u, v; double p; scanf("%d%d%lf", &amp;u, &amp;v, &amp;p); u = perm[u]; v = perm[v]; if (u == v) continue; a[u][v] = 1....

<div class="post_brief"><p> 决心写一道usaco之外的题，于是就挑中了这道。</p>   为啥这编辑器有BUG，每次按回车要向下跳？   发现可以预处理DP。f_i表示第i个数被砍完需要最少多少刀。对于每一个i，设p_i是它的质因子里最大的一个在给定集合里的，那么它可以转移到(i+1,i+p_i)这个范围。然后f_i显然不减，所以用单调队列之类的玩意。   然后卡着时间限制过了。不知道前面那些秒跑的人是怎么搞的。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 10000009; const int maxm = 100009; int k[maxn], f[maxn], n, m, q, p[maxm], v[maxm]; void pre(int n) { sort(p, p + m); memset(k, 0, sizeof(k)); for (int i = 0; i < m; ++ i) if (!i || p[i] != p[i - 1]) for (int j = 0; j <= n; j += p[i]) k[j] = p[i];...

多组询问，硬根号。yy了一下午，在去80MSWC的时候的病历上打了若干草稿，最后硬yy出来了。 其实拿LaTeX来当公式编辑器蛮好的。 然后d(a)函数可以线性筛，讨论一下是不是倍数就行了。 发现数论真的好神奇。 lofter的html源码好讨厌啊。 #include <cstdio> #include <cstring> #include <algorithm>   using namespace std;   #define _l (long long int)   const int maxn = 10000009; const int maxq = 10009; const int mod = 1e8 + 9;   int pn[maxn], tp, d[maxn]; bool pr[maxn]; int q, m[maxq], n[maxq], t;   #define incm(_a_,_b_) { \     _a_+=_b_; \     if (_a_>=mod||_a_<=-mod) \         _a_%=mod; \     if (_a_<0) \         _a_+=mod; \ }   void pre(int n) {...

充分证明我已经学傻了。把ONLINE_JUDGE打成ONLINE_JUGE还WA了若干次。然后开了个10^10的数组直接CE还想了好久是怎么回事。 10^10大概会TLE，真正的数据大概只有10^9。 做法比较简单直接容斥+剪枝，反正凑起来的几个数不会很多。 #ifndef ONLINE_JUGE #include <cstdio> #include <algorithm> using namespace std; typedef long long dint; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif const int maxa = 2048; const dint maxn = 10000000000LL; //const dint maxn = 100000LL; int e, t; dint l, r, s, a[maxa], ans; bool g[maxa]; void pre() { t = 0; for (int l = 1; l <= 10; ++ l) for (int j = 0; j < (1 << l); ++ j) {...

的确比较奇妙。 有一个奇妙的玩意是fib[gcd(i, j)] == gcd(fib[i], fib[j])。(fib[1] = fib[2] = 1) 然后就比较可搞了。 线性筛处理每个数的因子个数和因子和。开一点变量然后推一下就出来了。 然后要注意fib[2]也可以整除所有奇数，包括1。表示在这上面坑了2次提交。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define _l (long long int) const int maxn = 10000009; const int mod = 1000000007; int tp, pn[maxn], sa[maxn], sb[maxn], b[maxn], c[maxn]; bool pr[maxn]; void pre(int n) { memset(pr, 0, sizeof(pr)); tp = 0; sa[1] = 1; sb[1] = 1; b[1] = 1; c[1] = 0; for (int i = 2; i <= n; ++ i) { if (!...

yy了一个sqrt的玩意，不过因为n在变所以没有保障啊。 肯定不是正解了。 1s的题跑了1.3s居然AC，好厉害。 #include <cstdio> typedef long long dint; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif dint calc(dint n, dint k) { if (n <= 1) return k; for (dint i = 1, j; i <= k; i = j + 1) { if (n <= i) return k; j = (n - 1) / ((n - 1) / i); if (j > k) j = k; n = ((n - 1) / i + 1) * j; } return n;...

orz jason_yu提醒了我一句“最简单的优化”，才想起来。 如果d合法的话那么b/d-(a-1)/d>0。然后用整除优化到sqrt就可过。虽然比较慢。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() { int t, a, b, c, d, s, e; scanf("%d", &t); while (t --) { scanf("%d%d%d%d", &a, &b, &c, &d); -- a; -- c; s = 1; e = min(b, d); for (int i = 1, j; i <= e; i = j + 1) { j = min(b / (b / i), d / (d / i)); if (a / i) j = min(j, a / (a / i)); if (c / i)...

新年第一题哈哈。虽然没有成功拿到fb。 所谓阶乘进制数么。略水。只不过加一减一啥的得小心些。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #define pow2(x) (1<<(x)) #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif const int maxn = 21; dint fac[maxn]; int n, k, t, x[maxn]; dint a; void sovPerm() { t = 0; for (int i = n; i; -- i) { int r = (a - 1) / fac[i - 1] + 1, c = 0; a -= (r - 1) * fac[i - 1];...

解锁成就：半夜过题。（其实是因为在搞bsd） 仔细看下题推一下发现第n维中m维元素的个数为2^(n-m)*C(n,m)。 然后组合数好像得nlogn用逆元？恭喜tle。 然后yy了一个用线性筛的办法，只是素数用快速幂，这样大约可以降低复杂度，然后就能过了。好神奇。 代码好长TT。 #include <cstdio> #include <cstring> #define _l (long long int) const int maxn = 10000009; int tp, pn[maxn], inv[maxn]; bool pr[maxn]; int n, mod, s, c, p; int modPow(int a, int x) {     int s = 1;     for (; x; x >>= 1, a = _l a * a % mod)         if (x & 1)             s = _l s * a % mod;     return s;...