Number Guessing
大意
本題為交互題仇矾。
已知一個(gè)隱藏的正整數(shù) P 在一個(gè)已知的區(qū)間 (0, B] 中。每次詢問輸入正整數(shù) Q雌贱，返回 P 與 Q 的大小關(guān)系。一共有不超過 30 次詢問機(jī)會，試求 P 据途。
題目保證正整數(shù) B 不超過 109绞愚。
分析
這個(gè)題就是一個(gè)二分，也沒什么需要注意的細(xì)節(jié)颖医。
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
int T;
int main() {
cin >> T;
while (T--) {
int lo, hi, n;
cin >> lo >> hi >> n;
lo++;
while (lo <= hi) {
int m = lo + hi >> 1;
cout << m << endl;
string s;
cin >> s;
if (s == "CORRECT") break;
if (s == "TOO_SMALL") lo = m + 1;
else hi = m - 1;
}
}
}
Mural
大意
給定一個(gè)長度為 N 的數(shù)組位衩。初始情況下所有數(shù)均可選。
定義一回合為 （依次進(jìn)行）：
- 選擇一個(gè)尚未被選擇或丟棄的數(shù)熔萧，要求與已經(jīng)選擇的任意數(shù)字鄰接糖驴；
- 丟棄一個(gè)尚未被選擇的數(shù)，要求在當(dāng)且數(shù)組的最左邊或最右邊佛致。
第一回合可以開始于任意位置贮缕。
當(dāng)數(shù)組中所有的數(shù)字均被選擇或丟棄時(shí)，游戲結(jié)束晌杰。此時(shí)所有被選擇的數(shù)字之和為這局游戲的得分跷睦。試求最高可能得分。
題目保證 N 不超過 5 × 106 肋演。
分析
不難發(fā)現(xiàn)抑诸，被選擇的數(shù)字永遠(yuǎn)是連續(xù)的且不管如何選擇，總有一半（向上取整）的數(shù)字可以被選爹殊。
所以這個(gè)問題就被轉(zhuǎn)化成了給定長度的連續(xù)和最值問題蜕乡。
代碼
總復(fù)雜度為： O(n)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
const int maxn = 5123456;
int T, n;
char s[maxn];
int main() {
scanf("%d", &T);
FOR(cs, 1, T) {
scanf("%d%s", &n, s + 1);
int len = n + 1 >> 1, ans = 0, now;
FOR(i, 1, len) ans += s[i] - '0';
now = ans;
FOR(i, 2, n - len + 1) {
now = now + s[i + len - 1] - s[i - 1];
chkmax(ans, now);
}
printf("Case #%d: %d\n", cs, ans);
}
}
Kickstart Alarm
大意
給定一個(gè)長度為 N 的正整數(shù)數(shù)組 A 和正整數(shù) K 。
試求：
由于答案可能比較大梗夸，請對 (109 + 7) 取模后輸出层玲。
題目保證 N 不超過 106，K 不超過 104 反症。
分析
原表達(dá)式等價(jià)于：
記：
則有：
代碼
總復(fù)雜度為： O(nlogk) 可以優(yōu)化為 O(n + klogk)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
const int maxn = 1123456;
const int MOD = 1e9 + 7;
int T;
int N, K, x, y, C, D, E1, E2, F;
int a[maxn], s[maxn], inv[maxn];
void gen() {
a[1] = (x + y) % F;
FOR(i, 2, N) {
int nowx = (ll(C) * x + ll(D) * y + E1) % F;
int nowy = (ll(D) * x + ll(C) * y + E2) % F;
x = nowx, y = nowy;
a[i] = (x + y) % F;
}
}
inline int add(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
inline int mul(int a, int b) {
return ll(a) * b % MOD;
}
int pow_mod(int a, int k) {
int ret = 1;
while (k) {
if (k & 1) ret = mul(ret, a);
a = mul(a, a);
k >>= 1;
}
return ret;
}
int solve() {
s[1] = K;
FOR(i, 2, N)
s[i] = add(s[i - 1], mul(add(pow_mod(i, K + 1), MOD - i), inv[i - 1]));
int now = mul(K, N), ans = mul(now, a[1]);
FOR(i, 2, N) {
now = add(now, MOD - s[i - 1]);
now = add(now, mul(N - i + 1, mul(add(pow_mod(i, K + 1), MOD - i), inv[i - 1])));
ans = add(ans, mul(now, a[i]));
}
return ans;
}
int main() {
scanf("%d", &T);
FOR(i, 1, 1e6 + 10) inv[i] = pow_mod(i, MOD - 2);
FOR(cs, 1, T) {
scanf("%d%d%d%d%d%d%d%d%d", &N, &K, &x, &y, &C, &D, &E1, &E2, &F);
gen();
printf("Case #%d: %d\n", cs, solve());
}
}
