网站空间续费一年多少钱,少儿编程课是学什么的,四川住房建设厅网站,爱站网关键词查询网站Codeforces Round #701 (Div. 2)赛后补题报告(A~D)
A. Add and Divide
原题信息
http://codeforces.com/contest/1485/problem/A
解题思路
对于题目基本有两种方式#xff0c;一种是直接暴力求解#xff0c;第二种是使用函数求导进行严格证明 暴力求解 a1e9a1e^9a1e9不…Codeforces Round #701 (Div. 2)赛后补题报告(A~D)
A. Add and Divide
原题信息
http://codeforces.com/contest/1485/problem/A
解题思路
对于题目基本有两种方式一种是直接暴力求解第二种是使用函数求导进行严格证明 暴力求解 a1e9a1e^9a1e9不难看出操作最多为 50次因为2495629499534213122 ^ 49 562949953421312249562949953421312 直接就超了 那么我们的 bbb最多也就是加50次然后进行向下整除的模拟即可 一定要注意 b0b 0b0这种情况。 函数求导 首先我们设操作次数为yyy进行 b1b 1b1的次数为xxx可以得到的关系式为 yx(logbxa1)y x (log_{bx}a1)yx(logbxa1)其中logbxalog_{bx}alogbxa是整除到1的次数最后 1是让其变为0 下面我们对他进行求导 y′1−lna(lnt)2⋅ty1-\frac{ln{a}}{(lnt)^2\cdot t}y′1−(lnt)2⋅tlna其中tbxt≥2并且t≥btbxt\geq2 并且 t\geq btbxt≥2并且t≥b 查看导函数的零点 (lnt)2⋅tlnat≥2并且t≥b{(lnt)^2\cdot t}lnat\geq2 并且 t\geq b(lnt)2⋅tlnat≥2并且t≥b等式左侧递增右侧为常数lnalnalna即至多有一个零点 倘若有一个零点 可以直接二分求得零点我们在零点零点1 零点-1进行求解得结果。 倘若没有零点 直接就是t≥2并且t≥bt\geq2 并且 t\geq bt≥2并且t≥b取得最小值。
AC代码
首先必须吐嘲一下暴力没往这个向限制求导生疏了整了半天真鸡儿狗 暴力枚举代码
#include bits/stdc.h
using namespace std;typedef long long LL;
const int N 100010;LL a, b;int sol(LL a, LL b, int add)
{b add;if (b 1) return 0x3f3f3f3f;while (a){a / b;add ;}return add;
}int main()
{int T; cin T;while (T -- ){scanf(%lld%lld, a, b);int res 1000;for (int i 0; i 50; i ){res min(res, sol(a, b, i));}cout res endl;}return 0;
} 函数求导代码
#include bits/stdc.h
using namespace std;const int N 100010;
typedef long long LL;
const double esp 1e-5;
LL a, b;int RealDo(LL a, LL b)
{int ret 0;while (a){ret ;a / b;}return ret;
}int Get(LL a, LL b, LL tarb)
{if (tarb 1 || tarb b) return 0x3f3f3f3f;// return (tarb - b) floor(log(a) / log(tarb)) 1;return (tarb - b) RealDo(a, tarb);
}double Cal(LL a, LL b)
{double lga log(a);double l b, r 2e9, mid b;if (lga mid * (log(mid) * log(mid)) ) // 不用加return mid;while (abs(l - r) esp){mid (l r) / 2;if (lga mid * (log(mid) * log(mid))) // 高了r mid;else // 低了l mid;}return mid;
}int sol(LL a, LL b)
{double x Cal(a, b);return min(Get(a, b, x), min(Get(a, b, x 1), Get(a, b, x - 1)));
}int main()
{int t;cin t;while (t -- ){scanf(%lld%lld, a, b);cout sol(a, b) endl;}return 0;
}
B. Replace and Keep Sorted
原题信息
http://codeforces.com/contest/1485/problem/B
解题思路
我们单独考虑端点的可能性已经中间结点不同的次数可以使用前缀和 但是一定要仔细考虑什么时候 1什么时候没有1, 端点是否包括
AC代码
#include bits/stdc.h
using namespace std;const int N 100010;
int n, k, q;
int a[N];
int b[N];int cal(int l, int r)
{if (l r) return k - 1;else{int ret (a[l] - 1) (a[l 1] - a[l] - 1) (k - a[r]) (a[r] - a[r - 1] - 1);if (l r - 1)return ret;elsereturn ret b[r - 1] - b[l]; // l 1 ~ r - 1}
}
int main()
{cin n q k;for (int i 1; i n; i )scanf(%d, a[i]);memset(b, 0, sizeof b);for (int i 2; i n - 1; i )b[i] (a[i] - a[i - 1] - 1) (a[i 1] - a[i] - 1);for (int i 2; i n - 1; i )b[i] b[i - 1];while (q -- ){static int l, r;scanf(%d%d, l, r);// cout res endl \t;cout cal(l, r) endl;}return 0;
}
C. Floor and Mod
原题信息
http://codeforces.com/contest/1485/problem/C
解题思路
C题吐槽一下当时复杂度分析错了O(N)O(\sqrt N)O(N)分析成O(N)O(N)O(N)太绝了 设⌊ab⌋a%bt,tb\lfloor\frac a b\rfloora\%bt, t b⌊ba⌋a%bt,tb 那么at⋅bt(b1)⋅t,A≥a≥1,B≥b≥1at \cdot b t(b1)\cdot t, A\geq a\geq1,B\geq b\geq1at⋅bt(b1)⋅t,A≥a≥1,B≥b≥1
当t1t1t1时ab1,b∈[2,B]ab1,b\in [2, B]ab1,b∈[2,B]当t2t2t2时a2⋅(b1),b∈[3,B]a2\cdot(b1),b\in [3, B]a2⋅(b1),b∈[3,B]…当tititi时ai⋅(b1),b∈[i1,B]ai\cdot(b1),b\in [i 1, B]ai⋅(b1),b∈[i1,B] 此时,i⋅(b1)≤A,b≤B,b≥i1i \cdot (b 1)\leq A, b\leq B, b\geq i1i⋅(b1)≤A,b≤B,b≥i1 ⟹b∈[i1,min(B,⌊Ai⌋−1)]\Longrightarrow b\in [i 1, min(B,\lfloor \frac A i \rfloor-1)]⟹b∈[i1,min(B,⌊iA⌋−1)] 如果⌊Ai⌋−1\lfloor \frac A i \rfloor-1⌊iA⌋−1有前缀和公式的话是可以进行化简为O(1)O(1)O(1)的 最后b∈[i1,min(B,⌊Ai⌋−1)]b\in [i 1, min(B,\lfloor \frac A i \rfloor-1)]b∈[i1,min(B,⌊iA⌋−1)]可以看出来iii的最大值是无法取到1e91e91e9的需要开个根号。
AC代码
#include bits/stdc.h
using namespace std;typedef long long LL;void Sol(LL A, LL B)
{LL a, b, tmp, ret 0;for (int i 1; true; i ){tmp min(B, A / i - 1);// i 1 ~ tmpif (i 1 tmp) break;else ret (tmp - (i 1) 1);}cout ret endl;
}int main()
{int t; cin t;while (t -- ){static LL a, b;scanf(%lld%lld, a, b);Sol(a, b);}return 0;
}
D. Multiples and Power Differences
原题信息
http://codeforces.com/contest/1485/problem/D
解题思路 可恶啊这个题目是一个LCM的板子题没看出来。。。 首先我们对1~16求LCM x我们的 B 数组首先全是x可以满足multiplemultiplemultiple的性质然后我们凑性质三发现可以直接进行隔项加上ai,j4a_{i, j}^4ai,j4而且数据范围小满足性质1
AC代码
#include bits/stdc.h
using namespace std;typedef long long LL;
const int N 510;
int n, m;
int a[N][N];
int b[N][N];int gcd(int x, int y)
{if (y 0) return x;else return gcd(y, x % y);
}int lcm(int x, int y)
{return LL(x) * y / gcd(x, y);
}int main()
{cin n m;for (int i 1; i n; i )for (int j 1; j m; j )scanf(%d, a[i][j]);int x 1;for (int i 1; i 16; i ){x lcm(x, i);}for (int i 1; i n; i )for (int j 1; j m; j )b[i][j] x;for (int i 1; i n; i ){for (int j (i % 2 1 ? 1 : 2); j m; j 2){b[i][j] (a[i][j] * a[i][j]) * (a[i][j] * a[i][j]);}}// outputfor (int i 1; i n; i ){printf(%d, b[i][1]);for (int j 2; j m; j )printf( %d, b[i][j]);puts();}return 0;
}
总结
首先考虑暴力能否直接缩小范围省时间其次考虑复杂度的时候分析准确一些多考虑边界的情况1-1最后题型要把握清楚数据范围小的时候有时候会暴力有时候直接lcm。。。
