AtCoder Beginner Contest 162
ABCD全暴力
E数学题看不懂,感性理解
F线性dp,非常基础我不会,寄
E - Sum of gcd of Tuples (Hard)
看了题解发现好多做法都是推一堆式子,我实在看不懂(卷积莫反啥啥的呜呜呜)
然后看见这个感觉比较好感性理解:
(来自洛谷题解)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 7;
ll n, k, f[N], ans;
ll qmi(ll a, ll k, ll p){
ll res = 1;
while(k){
if(k & 1)
res = (ll)res * a % p;
a = (ll)a * a % p;
k >>= 1;
}
return res;
}
int main () {
cin >> n >> k;
for (int i = k; i >= 1; i--) {
f[i] = qmi (k / i, n, mod);
for (int j = i + i; j <= k; j += i) {
(f[i] += - f[j] + mod) %= mod;//容斥
}
}
for (int i = 1; i <= k; i++) (ans += 1ll * i * f[i]) %= mod;
cout << ans;
}
//存在多少个{a1,a2,...,an}使得gcd=x
//则所有数都为x的倍数,共(k/x)^n个
F - Select Half
线性dp,分奇偶讨论。
转移:对于 \(a_i\) 放,都是 \(dp_i=a_i+dp_{i-2}\)
到偶数位时:\(a_i\) 不放,则前面的局面固定了,只能时 \(i\) 之前奇数位的和,可以画个图
到奇数位时:\(a_i\) 不放,则转化为 \(i-1\) 的子问题, \(i-1\) 为偶数,即方案为 \(dp_{i-1}\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
ll a[N], n;
ll f[N], s[N]; //奇数位前缀和
int main () {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i-1];
if (i & 1) s[i] += a[i];
}
for (int i = 2; i <= n; i++) {
if (i & 1) f[i] = max (f[i-2] + a[i], f[i-1]);
else f[i] = max (f[i-2] + a[i], s[i-1]);
}
cout << f[n];
}
//妙妙dp,分奇偶讨论,线性地推
- Beginner AtCoder Contest 162beginner atcoder contest 162 atcoder regular contest 162 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 315