EOJ 1076 染氣球

---

一共有 N 只氣球，小強將 N 只氣球從左到右依次編號為 1、2、3……N，每次給 2 個整數 a，b （a<=b），小強便騎上他的“小飛鴿 ” 牌電動車從氣球 a 開始到氣球 b 依次給每個氣球涂一次顏色。但是 N 次以后小強已經忘記了第 I 個氣球已經涂過幾次顏色了，你能幫他算出每個氣球被涂過幾次顏色嗎？
N <= 100000

dalao解法線段樹，這里用了一種類似dp的解法，實際上是運用了差分數組前綴和。把從a刷到b的操作等價為++dp[a],–dp[b+1]，最后求前綴和就可以得到答案。
可能需要多理解一會兒……不過并不難。

#include<bits/stdc++.h> using namespace std;int dp[100005];int main() {int n, a, b;while (~scanf("%d", &n) && n) {memset(dp, 0, sizeof(dp));for (int i = 0; i < n; ++i) {scanf("%d%d", &a, &b);++dp[a];--dp[b+1];}for (int i = 1; i <= n; ++i) {dp[i] += dp[i-1];printf("%d%c", dp[i], i == n ? '\n' : ' ');}}return 0; }

EOJ 3469/COCI 2016-2017 Contest#6 Savrsen

---

A number is perfect if it is equal to the sum of its divisors, the ones that are smaller than it. For example, number 28 is perfect because 28=1+2+4+7+14.
Motivated by this definition, we introduce the metric of imperfection of number N, denoted with f(N), as the absolute difference between N and the sum of its divisors less than N. It follows that perfect numbers’ imperfection score is 0, and the rest of natural numbers have a higher imperfection score. For example:
f(6)=|6?1?2?3|=0,
f(11)=|11?1|=10,
f(24)=|24?1?2?3?4?6?8?12|=|?12|=12.
Write a programme that, for positive integers A and B, calculates the sum of imperfections of all numbers between A and B: f(A)+f(A+1)+…+f(B).

難點在于求因子。普通方法一個個找因子時間復雜度太高，因此正難則反，采用類似埃氏篩法的方法：對于從1~B的數，我們看它可能是誰的因子并且存入表c中，最后計算結果。
這個方法的時間復雜度看起來也不低，不過實際上，通過計算不難發現：對每個因子d我們循環了B/d次，所以總復雜度約為B/1+B/2+B/3+…+B/B，也就是B*(1+1/2+1/3+…+1/B)，而這個式子約等于BlnB。也就是說，時間復雜度是O(BlogB)。

#include <cstdio> #include <cmath> using namespace std;const int maxn = 1e7 + 1; int c[maxn];int main() {int a, b, i, j;scanf("%d%d", &a, &b);for (i = 1; i < b+1; ++i)for (j = 2*i; j < b+1; j += i)c[j] += i;long long ans = 0;for (i = a; i <= b; ++i) ans += abs(c[i] - i);printf("%lld\n", ans);return 0; }

EOJ 49 素數和排序

---

設 f(x,y) 表示 [x,y] 區間中所有素數的和。
給你 n 組 x,y，把它們按 f(x,y) 從小到大排序，若 f(x,y) 相等，則按 x 從小到大排序，若 f(x,y) 和 x 都相等，則按 y 從大到小排序。
1 ≤ n ≤ 10^5, max{yi} ? min{xi} ≤ 10^6,1 ≤ xi ≤ yi ≤ 10^12 (1≤i≤n).

不能開10^12的數組，但注意到max{yi} ? min{xi} ≤ 10^6這一條件，考慮平移到[min{xi}, max{yi}]區間內，然后再用埃氏篩或歐拉篩，這樣就能得到范圍內的質數。最后預處理前綴和求解。

#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+5; const int maxm = 1e6+5;typedef long long ll; typedef struct fff{ll l, r, sum;} F;F f[maxn]; ll ans[maxm];int cmp(F a, F b) {if (a.sum != b.sum) return a.sum < b.sum;else if (a.l != b.l) return a.l < b.l;return a.r > b.r; }int main() {int n;cin >> n;ll l = 1e12, r = 0;for(int i = 0; i < n; ++i) {scanf("%lld%lld", &f[i].l, &f[i].r);l = min(f[i].l, l);r = max(f[i].r, r);}ll trans = l-1;for(ll i = l; i <= r; ++i)ans[i-trans] = i;if(l == 1) ans[1] = 0;for(int i = 2; i < maxm; ++i) {ll p = l - l%i;if(p < l) p += i;if(p == i) p += i;while(p <= r) {ans[p-trans] = 0;p += i;}}for(ll i = 1; i <= r-l+1; ++i) ans[i] += ans[i-1];for(int i = 0; i < n; ++i)f[i].sum = ans[f[i].r-trans] - ans[f[i].l-trans-1];sort(f, f + n, cmp);for(int i = 0; i < n; ++i)printf("f(%lld,%lld)=%lld\n", f[i].l, f[i].r, f[i].sum);return 0; }

EOJ 2918 Kth-Number

---

Given an array a[1…n] of different integer numbers, what would be the k-th number in a[i…j] segment, if this segment was sorted?
1 <= n <= 10^5

似乎又是線段樹/劃分樹的題，不過還是可以暴力+優化過。記錄好原數組中數的位置，然后排好序。根據k在范圍中的相對位置選擇從后往前/從前往后找。
評測結果：線段樹做法不到0.1s，本做法不到0.55s，應該還算可以接受……

#include <bits/stdc++.h> using namespace std;struct nn{int val, prevpos;}num[100005];int cmp(nn a, nn b) {return a.val < b.val; }int main() {int n, m, i, l, r, k;while (~scanf("%d%d", &n, &m)) {for(i = 1; i <= n; ++i) {scanf("%d", &num[i].val);num[i].prevpos = i;}sort(num+1, num+1+n, cmp);while (m--) {scanf("%d%d%d", &l, &r, &k);int len = r-l+1, mid = len >> 1;if (k > mid) {k = len-k+1;for(i = n; i >= 1; --i)if(num[i].prevpos >= l && num[i].prevpos <= r)if(!(--k)) break;printf("%d\n", num[i].val);}else {for(i = 1; i <= n; ++i)if(num[i].prevpos >= l && num[i].prevpos <= r)if(!(--k)) break;printf("%d\n", num[i].val);}}} }

EOJ 3462（EOJ Monthly 2018.1） 最小OR路徑

---

給定一個有 n 個點和 m 條邊的無向圖，其中每一條邊 ei 都有一個權值記為 wi。
對于給出的兩個點 a 和 b，求一條 a 到 b 的路徑，使得路徑上的邊權的 OR（位或）和最小，輸出這個值。(也就是說，如果將路徑看做邊的集合 {e1,e2,…,ek}，那么這條路徑的代價為 w1 OR w2 OR … OR wk，現在求一條路徑使得其代價最小，輸出這個代價。) 如果不存在這樣的路徑，輸出 ?1。
2 ≤ n ≤ 10^4, 0 ≤ m ≤ 10^6, 0 ≤ ci ≤ 2^62?1
1 ≤ ui,vi,a,b ≤ n, a≠b
可能有重邊和自環。

假設答案二進制位全為1，然后從高到低，如果不影響連通性就置0，最后得到的就是最優方案。（看起來很暴力啊）
判斷連通性可以dfs，不過我覺得并查集好寫一點……

#include <bits/stdc++.h> using namespace std;typedef long long ll; ll x[1000005], y[1000005], w[1000005], f[10005]; int n, m, s, e;ll find(ll u) {return u == f[u] ? u : (f[u] = find(f[u])); }ll check(ll mask) {for(int i = 1; i <= n; ++i) f[i] = i;for(int i = 1; i <= m; ++i)if(!(w[i] & mask))f[find(x[i])] = find(y[i]);return find(s) == find(e); }int main() {cin >> n >> m;for(int i = 1; i <= m; ++i)scanf("%lld%lld%lld", &x[i], &y[i], &w[i]);cin >> s >> e;if(!check(0)) puts("-1");else {ll ans = 0, mask = 0;for(int i = 61; i >= 0; --i) {mask += 1LL<<i;if(!check(mask))ans += 1LL<<i, mask -= 1LL<<i;}cout << ans << endl;}return 0; }

總結

以上是生活随笔為你收集整理的轻量级的巧妙解法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。