题目列表
A.ABBA
题意：Solution
思路：Code
const int N = 1000010;
int n, q, a[N], ans[N];
vector<pair<int,int>> qu[N];
struct node {
int val;
} seg[N * 4];
void update(int id) {
seg[id].val = min(seg[id * 2].val, seg[id * 2 + 1].val);
}
void change(int id, int l, int r, int pos, int val) {
if (l == r) {
seg[id].val = val;
} else {
int mid = (l + r) / 2;
if (pos <= mid) change(id * 2, l, mid, pos, val);
else change(id * 2 + 1, mid + 1, r, pos, val);
update(id);
}
}
int search(int id, int l, int r, int d) {
if (l == r) return l;
int mid = (l + r) / 2;
if (seg[id * 2].val < d) return search(id * 2, l, mid, d);
else return search(id * 2 + 1, mid + 1, r, d);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i] = min(a[i], n + 1);
}
scanf("%d", &q);
for (int i = 1; i <= q;i++) {
int l, r;
scanf("%d%d", &l, &r);
qu[r].push_back({l, i});
}
for (int r = 1; r <= n; r++) {
change(1, 0, n + 1, a[r], r);
for (auto que : qu[r]) {
ans[que.second] = search(1, 0, n + 1, que.first);
}
}
for (int i = 1; i <= q; i++) {
printf("%d\n", ans[i]);
}
}
D. Short Enough Task
Solution
思路:Code
void solve() {
ll n, k;
cin >> n >> k;
long double ans = n;
if (k == 1) {
cout << fixed << setprecision(10) << (long double)(1 + n)*(long double)n/ 2.0 << endl;
} else {
long double tmp = 1;
for (int i = 1; i <= n && i <= 1e6; ++i) {
if((i&1)){
tmp*=k;
}
ans += ( ((n - i) * 1.0) / tmp);
}
cout << fixed << setprecision(10) << ans << endl;
}
}
F.Just Another Sequence Problem
Solution
思路:Code
const int N = 2010;
/* dp[i][j]代表最后一块是i->j*/
dp[i][j] = dp[k][i]
ll dp[N][N];
void solve() {
int n;
cin >> n;
vector a(n + 1), pre(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
for (int i = 2; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
dp[i][j]=INT_MIN;
for (int k = 1; k <= i - 1; ++k) {
dp[i][j] = max(dp[i][j], dp[k][i - 1] + (pre[i - 1] - pre[k - 1]) * (pre[j] - pre[i - 1]));
}
}
}
ll ans =0;
for (int i = 1; i <= n; ++i) {
ans = max(ans, dp[i][n]);
}
cout << ans << '\n';
}