$ \sum{i=0}^{n-1}\sum{j=i}^{n-1}\mid Ai - Aj \mid $
小学生在上课
题目大意：给你一个正整数N，问你1 ~ (n-1) 所有在模N下的逆的和（只计算存在的）。
分析： 1、首先，一个数a在模N下存在逆当且仅当 gcd(a, N) = 1 2、易证，不同的数在模N下的逆不同 3、一个数在模N下的逆是它本身 4、因此，令A={与N互质的数} B = {A里每一个数在模N下的逆}，易证 A = B 5、所以只需求1-(n-1)中与N互质的数的和 6、因为gcd（a, N）= 1 gcd（N-a， N） 7、因此 时间复杂度为O(sqrt(N)) 另：不懂ϕ（N）的自己去查 欧拉函数#include#include int main(){ int T,n,i; scanf("%d",&T); while(T--) { scanf("%d",&n); long long ans = n; for(i = 2;i <= sqrt(n);i ++) { if(n % i == 0) { ans *= i - 1; n /= i; while(n % i == 0) { ans *= i; n /= i; } } } if (n>1) ans *= n - 1; ans /= 2; printf("%lld\n",ans); } return 0;}
小学生森林
每次O(log)的去交换行和列就可以了，然后最后再看看那个位置是什么。
如果没看懂的话，那就仔细看看代码吧～
#include#include #include #include #include #include
小学生放假了
这题N^2M的dp应该是显然的……算了还是说下吧，先将Ci从大到小排序。f[i][j]表示前i个小学生还剩下j个商品可以设定价格，可以得到的最多的收入，f[i][j] = max(f[k][j – 1] + Ck * (i – k) | 0 <= k < i)，这个dp应该很好理解。
现在的思路很简单，就是把转移优化到O(1)，这怎么做呢？
经过观察可以发现，每个f[i][j]的决策g[i][j]在两维上都是单调不减的，即 g[i][j] <= g[i][j + 1]，g[i][j] <= g[i + 1][j]。然后就有利用二维决策单调性的O(NM)算法了：对于每个f[i][j]计算决策的时候，只枚举[g[i – 1][j], g[i][j + 1]]之间的决策，可以证明这个复杂度是O(NM)的
#include#include using namespace std;const int N=10005,M=2005;int n,m,g[N][M];long long f[N][M],c[N];int main(){#ifndef ONLINE_JUDGE freopen("ch.in","r",stdin); freopen("ch.out","w",stdout);#endif scanf("%d%d",&n,&m); for(int i=0;i
小学生的游戏
这个题目一看就是矩阵快速幂吧……
算法1：容易发现步长是以M为循环节的。构造M个转移矩阵，先把M个转移矩阵乘起来得到A，再计算A^(N / M)，最后再乘上前N % M个转移矩阵，得到答案。这种算法是O(M^4)的，对于M=200的数据还是过不了的……
算法2：上面这种算法把M个转移矩阵乘起来这一步太浪费时间，所以我们考虑直接构造转移M个格子的矩阵A，构造这个矩阵是O(M^3)的，然后再用上面的算法就可以了（前M个格子的数可能要特殊处理） AC算法：虽然算法2已经达到了O(M^3logN)的复杂度，但由于常数较大还是过不了本题……怎么办呢？？？只能优化矩阵乘法了。我们发现如果一个矩阵的某些项为0，根本没有必要乘这么多次，于是如果碰到一个值为0的项就直接跳过第三重循环（具体看AC程序）。事实证明，这样优化了大约2~5倍的时间，常数小的程序已经能在1秒内跑出结果了！ 4ms 算法：AC这题的都用的是4ms 算法……由于我实在是太弱了，真心不会这种算法啊……#include#include #include #include #include #include #include #include #include #include #include
5、小学生的旅行
题意大意：给一个N个点，M条边的无向连通图，再给你K个权值，问这些权值中，可以从u走到v时经过的边值都不大于这个权值的有多少个。其中这些权值会修改。 分析： 1、首先，如果从u走到v的所有路径中，最大边最小的边权为l，那么，所有不小于l的权值都符合，所有小于l的权值都不符合。 2、因此，可以把题目分为两步，首先求出从u走到v的所有路径中最大边最小的边权l，再求有多少个权值不小于l。 3、取出原图中的所有点，将边从小到大排序，一次加入这个新图，当使u， v恰好连通时的边权就是要求的L。停止加边。 4、证明：从u走到v，可以只经过不比L大的边，因为新图中u可以走到v，而且图中的所有边权不大于L。去掉边权为L的边，得到的图中u无法到v， 因此不存在L’， 从u走到v，可以只经过不比L’大的边，其中L’<L。 因此L是原图中从u走到v的所有路径中，最大边最小的边权。 5、如果在加边的过程中，不添加在同一连通块中的两个点之间的边，使整个 图连通后，这个图是原图的最小生成树，对任意两点u，v，从u走到v的唯 一路径上的最大边就是原图中从u走到v的所有路径中，最大边最小的边权。 （因为L一定在这条路径上，且这条路径上的其它边都小于L） 6、所以先求出最小生成树，再通过倍增，可以在O(logN)的时间求出从u走到v的所有路径中，最大边最小的边权。 7、至于如何在一组数中查找有多少个，其大小不小于l，还会动态修改这些数的权值，可以用平衡树做，但是考虑到本题中l≤200000，可以用数组a[i]表示权值为i的数有多少个，所有比lmax大的数可以看成lmax，然后用平衡树/树状数组来维护，可以做到O(log(lmax))的查询和修改 总复杂度为O(MlogM + QlogN + Qlog(lmax))#include#include #include #include #include #define pb push_backusing namespace std;const int W=200100;struct edge{int x, y, d;}E[W];int mx[W][18], anc[W][18], uni[W], t[W], dep[W], a[W];int N, M, K, Q;vector nxt[W], c[W];int lowbit(int x){return x & (-x);}void add(int x, int d){ for (; x <= 200001; x += lowbit(x)) a[x] += d;}int getsum(int x){ int sum=0; for (; x > 0; x -= lowbit(x)) sum += a[x]; return sum;}void Read(){ scanf("%d%d%d%d", &N, &M, &K, &Q); for (int i=1; i <= M; i++) { scanf("%d%d%d", &E[i].x, &E[i].y, &E[i].d); E[i].d++; } for (int i=1; i <= K; i++) { scanf("%d", &t[i]); t[i]++; if (t[i] >= 200001) t[i]=200001; add(t[i], 1); }}bool cmp(const edge &A, const edge &B){return A.d < B.d;}int Uni(int x){ if (uni[x] == x) return x; return uni[x]=Uni(uni[x]);}void Init(){ for (int i=1; i <= N; i++) uni[i]=i; for (int i=1; i <= M; i++) { int x=E[i].x, y=E[i].y; x=Uni(x); y=Uni(y); if (x == y) continue; uni[x]=y; nxt[E[i].x].pb(E[i].y); nxt[E[i].y].pb(E[i].x); c[E[i].x].pb(E[i].d); c[E[i].y].pb(E[i].d); }}void Build(int x, int fa, int D){ dep[x]=D; anc[x][0]=fa; for (int i=1; i <= 17; i++) { if (dep[x] - (1 << i) < 1) break; anc[x][i]=anc[anc[x][i - 1]][i - 1]; mx[x][i]=max(mx[x][i - 1], mx[anc[x][i - 1]][i - 1]); } for (int i=0; i < (int)nxt[x].size(); i++) { int y=nxt[x][i]; if (y == fa) continue; mx[y][0]=c[x][i]; Build(y, x, D + 1); }}int Find(int u, int v){ int sum=0; if (dep[u] < dep[v]) swap(u, v); for (int i=17; i >= 0; i--) if (dep[u] - (1 << i) >= dep[v]) { sum=max(sum, mx[u][i]); u=anc[u][i]; } if (u == v) return sum; for (int i=17; i >= 0; i--) if (dep[u] - (1 << i) >= 1 && anc[u][i] != anc[v][i]) { sum=max(max(sum, mx[u][i]), mx[v][i]); u=anc[u][i], v=anc[v][i]; } sum=max(max(sum, mx[u][0]), mx[v][0]); return sum;}void Solve(){ while (Q--) { int ope; scanf("%d", &ope); if (ope == 1) { int x, p; scanf("%d%d", &x, &p); p++; add(t[x], -1); t[x]=p; if (t[x] >= 200001) t[x]=200001; add(t[x], 1); } else { int u, v; scanf("%d%d", &u, &v); int val=Find(u, v); printf("%d\n", K - getsum(val - 1)); } }}int main(){ Read(); sort(E + 1, E + 1 + M, cmp); Init(); Build(1, 0, 1); Solve(); return 0;}