Number Guessing
大意
本题为交互题。
已知一个隐藏的正整数 P 在一个已知的区间 (0, B] 中。每次询问输入正整数 Q，返回 P 与 Q 的大小关系。一共有不超过 30 次询问机会，试求 P 。
题目保证正整数 B 不超过 109。
分析
这个题就是一个二分，也没什么需要注意的细节。
代码
#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
大意
给定一个长度为 N 的数组。初始情况下所有数均可选。
定义一回合为 （依次进行）：
- 选择一个尚未被选择或丢弃的数，要求与已经选择的任意数字邻接；
- 丢弃一个尚未被选择的数，要求在当且数组的最左边或最右边。
第一回合可以开始于任意位置。
当数组中所有的数字均被选择或丢弃时，游戏结束。此时所有被选择的数字之和为这局游戏的得分。试求最高可能得分。
题目保证 N 不超过 5 × 106 。
分析
不难发现，被选择的数字永远是连续的且不管如何选择，总有一半（向上取整）的数字可以被选。
所以这个问题就被转化成了给定长度的连续和最值问题。
代码
总复杂度为： 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
大意
给定一个长度为 N 的正整数数组 A 和正整数 K 。
试求：
由于答案可能比较大，请对 (109 + 7) 取模后输出。
题目保证 N 不超过 106，K 不超过 104 。
分析
原表达式等价于：
记：
则有：
代码
总复杂度为： O(nlogk) 可以优化为 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());
}
}
