偷了个懒。。。好几次的多校的题没有补。。。
1003.Kanade's sum
Time Limit: 2000 MS
题意：
给出含有n个元素的数组A，A的元素是1~n的任意一个排列，求出任意区间第K的数的和。
思路：
比赛的时候是毫无头绪，后来看了题解，明白了解法。从最小的元素开始考虑，每次在他的范围内向前向后走K个，在这个区间的子区间可以确定里它是第K大的，然后将它删去，在考虑下一个，这样就得到了完美的解法。
然后我用单向链表开始写，WA了好几发，百度了别人的代码，发现是用双向链表写的，感觉双向链表对这道题的好几个点处理的很好。学习了
#include "bits/stdc++.h" using namespace std; const int maxn = 1e6; typedef long long LL; int nex[maxn], pre[maxn]; int L[maxn], R[maxn], pos[maxn]; int N, K; LL get_res(int x) { LL res = 0; int r = 0, l = 0; for (int i = x; i > 0; i = pre[i]) { //减去和前面的距离，这样对于删去节点比较好讨论 L[++l] = i - pre[i]; if (l == K) break; } for (int i = x; i <= N; i = nex[i]) { R[++r] = nex[i] - i; if (r == K) break; } for (int i = 1; i <= l; i++) { if (K - i + 1 <= r) res += (LL)L[i]*R[K-i+1]; } return res; } void del(int x) { pre[nex[x]] = pre[x]; nex[pre[x]] = nex[x]; } int main(int argc, char const *argv[]) { int T; scanf("%d", &T); while (T--) { int a; scanf("%d%d", &N, &K); for (int i = 1; i <= N; i++) {scanf("%d", &a); pos[a] = i;} for (int i = 1; i <= N; i++) {pre[i] = i-1; nex[i] = i+1;} pre[0] = 0; nex[N + 1] = N + 1; LL ans = 0; for (int i = 1; i <= N; i++) { ans += get_res(pos[i])*i; del(pos[i]); } printf("%lld ", ans); } return 0; }
1005RXD and dividing
题意：
给你一棵树，将节点1单独拿出来，把剩下的节点分成K个部分。每个部分挑选若干条边，让包括节点1在内的每个部分都联通的，让边权最小。整棵树的价值就是每部分的价值总和。选择树的划分方式，让整棵树的价值最大。
思路：
没有证明。题解也是这个意思，统计过每条边的次数，让最大的分发肯定是尽量多的经过一个边多次。存在一个分发使得每条边经过最多不过K次。然后判断每条边走过几次。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 1e6 + 10; int tot = 0; int n, k; LL ans; int sz[maxn]; int head[maxn]; struct node { int to, next, val; } ; vector<node> tree[maxn]; int dfs(int u, int fa) { sz[u] = 1; for (int i = 0; i < tree[u].size(); i++) { int v = tree[u][i].to; if (v == fa) continue; sz[u] += dfs(v, u); ans += (LL)min(k, sz[v])*tree[u][i].val; } return sz[u]; } void init() { for (int i = 0; i < maxn; i++) tree[i].clear(); tot = 0; ans = 0; } int main(int argc, char const *argv[]) { while (scanf("%d%d", &n, &k) != EOF) { init(); for (int i = 0; i < n-1; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); node t; t.val = c; t.to = b; tree[a].push_back(t); t.to = a; tree[b].push_back(t); } dfs(1, -1); printf("%lld ", ans); } return 0; }
1008 RXD and math
这道题。。。。暴力找规律。。。。函数公式不会推。。。。抽空要学莫比乌斯函数
#include "bits/stdc++.h" using namespace std; typedef long long LL; const int mod = 1e9+7; inline LL pow_mod(LL x, LL y) { LL base = x; LL res = 1; while (y) { if (y&1) res=res*base%mod; base=base*base%mod; y/=2; } return res; } int main(int argc, char const *argv[]) { LL n, k; int kcase = 0; while (scanf("%lld%lld", &n, &k) != EOF) { n %= mod; printf("Case #%d: %lld ", ++kcase, pow_mod(n,k)); } return 0; }
1011RXD's date
签到题，检查有多少天温度大于35度
#include "bits/stdc++.h" using namespace std; int main(int argc, char const *argv[]) { int n, a; int ans = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a); if (a <= 35) ans++; } printf("%d ", ans); return 0; }