知識點:貪心。
注意到任意三根木棍的相等最優解是最長減最小,因此從小到大排序,三個三個取,取最小值。
時間複雜度 \(O(n\log n)\)
空間複雜度 \(O(n)\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[307];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
sort(a + 1, a + n + 1);
ll ans = a[3] - a[1];
for (int i = 3;i <= n;i++) {
ans = min(ans, a[i] - a[i - 2]);
}
cout << ans << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
知識點:構造。
注意到第 \(i\) 行的房間最多明亮值為 \(i\) ,又發現只需要兩側房間安排火把已經滿足一行最大值,因此直接兩側房間 \(1\) 其他都是 \(0\) 。
時間複雜度 \(O(n^2)\)
空間複雜度 \(O(1)\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= i;j++) {
if (j == 1 || j == i) cout << 1 << ' ';
else cout << 0 << ' ';
}
cout << '\n';
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
知識點:貪心,數學。
從小到大,把每一個要刪除的數當作 \(k\) 列舉倍數,如果是要刪除的數花費一次 \(k\) 刪掉,如果已經刪過則無視,如果不是要刪除的數則停止換下一個 \(k\) 。
時間複雜度 \(O(n\log n)\)
空間複雜度 \(O(n)\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int vis[1000007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) {
char c;
cin >> c;
vis[i] = c == '1';
}
ll sum = 0;
for (int i = 1;i <= n;i++) {
if (vis[i] == 1) continue;
for (int j = i;j <= n;j += i) {
if (vis[j] == 1) break;
if (vis[j] == 0) {
vis[j] = 2;
sum += i;
}
}
}
cout << sum << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
知識點:貪心,列舉。
先選擇一個方向直走,比如先走左側,走到不能再走為止,把盡頭的生命值 \(lnw\) 記錄下。
此時考慮回頭,但顯然在左側盡頭回頭不是一定最優的,應該在走左側過程中生命值和最大處回頭才是最優的,因為這樣在走右側時可以走最多的路,因此在走左側的過程中也要記錄左側的生命和最大值 \(lmx\) 。
同理從 \(lmx\) 回頭走右側時,也是走到盡頭記錄右側最大生命值 \(rmx\) 和盡頭生命值 \(rnw\) 。此時從 \(rmx\) 回頭走左側,應該直接從上一次的左側盡頭位置 \(lnw\) 繼續走。
如此來回往復,直到兩側不能繼續走或者到達兩端為止。
時間複雜度 \(O(n)\)
空間複雜度 \(O(n)\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[200007];
bool solve() {
int n, k;
cin >> n >> k;
for (int i = 1;i <= n;i++) cin >> a[i];
int i = k - 1, j = k + 1;
ll lmx = 0, lnw = 0, rmx = 0, rnw = 0;
while (1 <= i && j <= n) {
bool ok = false;
while (1 <= i) {
if (a[k] + lnw + rmx + a[i] < 0) break;
ok = true;
lnw += a[i--];
lmx = max(lmx, lnw);
}
while (j <= n) {
if (a[k] + lmx + rnw + a[j] < 0) break;
ok = true;
rnw += a[j++];
rmx = max(rmx, rnw);
}
if (!ok) break;
}
if (i == 0 || j == n + 1) cout << "YES" << '\n';
else cout << "NO" << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
知識點:構造,數學。
注意到,
猜測一行元素具有線性關係,設 \(i_1\) 行線性係數為 \(k_1\) ,\(i_2\) 行線性係數為 \(k_2\) ,於是有:
根據定理:當 \(k > 0\) 時,若 \(kx \equiv ky \pmod n\) ,則 \(x \equiv y\pmod {\frac{n}{gcd(k,n)}}\) 。
於是有:
因此,只要每行之間的線性係數在 \(\mod n\) 意義下不同餘,且在 \((i,i)\) 處經過 \(b_i\) 即可。
顯然,\(i \in [1,n]\) 時即能保證互不同餘,可以當作係數,因此有公式 \(b_{i,j} = (i \cdot (j-i) + b_i) \mod n\) 。
時間複雜度 \(O(n^2)\)
空間複雜度 \(O(n^2)\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[357][357], b[357];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> b[i];
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
a[i][j] = ((i * (j - i) + b[i]) % n + n) % n;
}
}
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
cout << a[i][j] << ' ';
}
cout << '\n';
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
知識點:記憶化搜尋,線性dp,數學,位運算。
先是一個結論:定義函數 \(parity(a)\) 表示 \(a\) 二進位制位 \(1\) 的個數的奇偶性(奇數返回 \(1\) ,偶數返回 \(0\)),那麼 \(S_i = parity(i)\) 。
證明非常簡單:
有了這個結論,我們就可以對問題進行量化。記原問題答案為 \(f(n,m)\) ,有 \(f(n,m) = \sum_{i = 0}^{m-1} [parity(i) \neq parity(n+i)]\) 。
當 \(m = 0\) 時,顯然有 \(f(n,0) = 0\) 。
當 \(m\) 為奇數時,先對末尾判斷再對 \(m-1\) 討論(偶數討論方便一點),有 \(f(n,m) = f(n,m-1) + [parity(i) \neq parity(n+i)]\) 。
當 \(m\) 為偶數時:
\(n\) 為偶數,有如下關係:
因為偶數末尾總是 \(0\) ,加 \(1\) 不會影響其餘的二進位制位,所以 \(1\) 的數量明確加 \(1\) ,奇偶性一定同時改變。
因為偶數末尾總是 \(0\) ,刪去這個 \(0\) 後,數位奇偶性不變。
那麼有如下公式:
\(n\) 為奇數,有如下關係:
以及,
證明同上。
至此,我們就可以通過記憶化搜尋進行求解了。
時間複雜度 \(O(\log n \log m)\)
空間複雜度 \(O(\log n \log m)\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool check(ll a, ll b) {
return __builtin_parityll(a) != __builtin_parityll(b);
}
map<pair<ll, ll>, ll> mp;
ll f(ll n, ll m) {
if (m == 0) return 0;
if (mp.count({ n,m })) return mp[{n, m}];
if (m & 1) return mp[{n, m}] = f(n, m - 1) + check(m - 1, n + m - 1);
if (n & 1) return mp[{n, m}] = m - f(n / 2, m / 2) - f((n + 1) / 2, m / 2);
else return mp[{n, m}] = 2 * f(n / 2, m / 2);
}
bool solve() {
ll n, m;
cin >> n >> m;
cout << f(n, m) << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
本文來自部落格園,作者:空白菌,轉載請註明原文連結:https://www.cnblogs.com/BlankYang/p/16758490.html