想不到吧
$21$场$CF$竟然是暑假作业
upd on 7.15
$\texttt{CodeForces EDU 47}$
$\texttt{A}$
直接模拟…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1000 + 5;
int n, m;
int c[N], a[N];
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &c[i]);
}
for(int i = 1; i <= m; i++) {
scanf("%d", &a[i]);
}
int pos = 1, buy = 0;
for(int i = 1; i <= n; i++) {
if(c[i] > a[pos]) continue;
else {
pos++;
buy++;
if(pos > m) {
printf("%d\n", buy);
return 0;
}
}
}
printf("%d\n", buy);
return 0;
}
|
$\texttt{B}$
首先很显然的一点就是由于有一点限制，$0$和$2$的相对顺序肯定不会变。
那就先把所有$1$拎出来，放到第一个$2$前面，就做完了。
注意特判没有$2$和没有$1$的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <cstdio>
#include <cstdlib>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
string t;
int main() {
cin >> t;
int cnt = 0;
for(int i = 0; i < t.size(); i++) {
if(t[i] == '1') ++cnt;
}
if(cnt == t.size()) return cout << t, 0;
for(int i = 0; i < t.size(); i++) {
if(t[i] == '0') putchar('0');
else if(t[i] == '2') {
for(int r = 1; r <= cnt; r++) putchar('1');
for(int j = i; j < t.size(); j++) {
if(t[j] != '1') putchar(t[j]);
}
return 0;
}
}
if(cnt) {
for(int r = 1; r <= cnt; r++) putchar('1');
}
return 0;
}
|
$\texttt{C}$
首先观察到$x$并没有什么用，影响在$d$的正负性。
如果$d$是正的，那显然就要从两端开始“染色”，这样总的$d$的份数是最多的。
而当$d$是负的时，就要从中间开始染，直观理解一下就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <cstdio>
#include <cstdlib>
#include <vector>
#include <iostream>
#include <iomanip>
using namespace std;
typedef long long ll;
int n, m, t, d;
ll sum;
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) {
scanf("%d%d", &t, &d);
if(d >= 0) {
sum += 1ll * t * n;
sum += 1ll * (1ll * (n - 1) * n / 2) * d;
}
else {
sum += 1ll * t * n;
if(n % 2 == 1) sum += 1ll * (n / 2) * (n / 2 + 1) * d;
else {
sum += 1ll * (n / 2) * (n / 2 + 1) / 2 * d;
sum += 1ll * (n / 2 - 1) * (n / 2) / 2 * d;
}
}
}
cout << fixed << setprecision(15) << (double)(sum) / (double)(n) << endl;
return 0;
}
|
$\texttt{D}$
很显然对于一个$n$个点的图，最多能够连$\sum_{i = 2} ^ {n} \varphi(i)$条边。打个表发现这玩意在$n=570$左右的时候就超过$1e5$了，而此时需要枚举的数的个数也是可接受的级别，意味着如果$m$是$1e5$级别的话暴力是能过的。
构造方案也很显然，先连$n-1$条边，第$i$条边连$i$和$i+1$.之后再找互质的随便连就行。
如果连不够或者连多了就输出Impossible.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
int n, m;
int main() {
scanf("%d%d", &n, &m);
vector < pair <int, int> > edge;
if(m < n - 1) {
puts("Impossible");
return 0;
}
for(int i = 2; i <= n; i++) {
edge.push_back({i - 1, i});
}
for(int i = 3; i <= n; i++) {
for(int j = 1; j < i - 1; j++) if(__gcd(i, j) == 1) {
if(edge.size() == m) goto end;
edge.push_back(make_pair(j, i));
if(edge.size() == m) goto end;
}
}
end:;
if(edge.size() != m) {
puts("Impossible");
return 0;
}
puts("Possible");
for(int i = 0; i < edge.size(); i++)
printf("%d %d\n", edge[i].first, edge[i].second);
return 0;
}
|
$\texttt{E}$
毒 瘤 D P
问题等价于给一个$01$串标$01$，每个串有对应价值，求价值之和。
DP过程比较麻烦…这里把手稿放上来好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| 1 3 3 7
1 3 3 7
0 0 0
1 3 3 1
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
dp[i][0] / dp[i][1]:
1~i 末尾填0/1的总和
dp[1][0] = a[1] + a[2]
dp[1][1] = a[1] + a[1]
目标: dp[i - 1][0] + dp[i - 1][1]
对于dp[i][0]:
1) 上一个取的是1: dp[i - 1][1] + 2 ^ (i - 2) * (a[2])
2) 上一个取的是0: dp[i - 1][0] + ?
?=\sum_{j = 1} ^ {i - 2} 2 ^ (i - j - 2) * a[j + 2] + a[i + 1]
1 2 3 4 5 6
1 0 0 0 0
1 2 3 4 5
对于dp[i][1]:
1) 上一个取的是0: dp[i - 1][0] + 2 ^ (i - 2) * a[1]
2) 上一个取的是1: dp[i - 1][1] + 2 ^ (i - 2) * a[1]
|
发现瓶颈在于问号处的计算。
然后发现可以记忆化搜索，就做完了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1000000 + 5;
const ll mod = 998244353;
ll qpow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
ll dp[N][2], n, a[N], sum[N];
ll sum1(ll i) {
if(sum[i] != -1) return sum[i];
if(i == 2 || i == 3) {
ll ans = 0;
for(int j = 1; j <= i - 2; j++)
ans = (ans + qpow(2, i - j - 2) * a[j + 2] % mod) % mod;
return sum[i] = ans;
}
ll t = sum1(i - 1);
return sum[i] = (2 * t + a[i]) % mod;
}
int main() {
memset(sum, -1, sizeof(sum));
scanf("%lld", &n);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
if(n == 1) {
printf("%lld\n", a[1]);
return 0;
}
dp[1][0] = (a[1] + a[2]) % mod;
dp[1][1] = (a[1] + a[1]) % mod;
for(int i = 2; i <= n - 1; i++) {
dp[i][0] = (dp[i - 1][1] + qpow(2, i - 2) * a[2] % mod) % mod;
dp[i][0] = (dp[i][0] + dp[i - 1][0] + sum1(i) + a[i + 1]) % mod;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] + qpow(2, i - 1) * a[1] % mod) % mod;
}
printf("%lld\n", (dp[n - 1][0] + dp[n - 1][1]) % mod);
return 0;
}
|
$\texttt{F}$
不会DSU。咕咕咕
$\texttt{G}$
霍尔定理待学习。咕咕咕
upd on 7.16
$\texttt{CodeForces EDU 48}$
$\texttt{A}$
直接模拟。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 200000 + 10;
int n, m, a[N];
int left = 0;
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if(left + a[i] < m) {
left += a[i];
printf("0 ");
}
else {
a[i] -= (m - left);
int cnt = 1;
cnt += a[i] / m;
left = a[i] % m;
printf("%d ", cnt);
}
}
return 0;
}
|
$\texttt{B}$
预处理一下前缀和，然后直接减就可以。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1000 + 5;
int n, m, q, pre[N];
char c[N], t[N];
int main() {
scanf("%d%d%d", &n, &m, &q);
scanf("%s", (c + 1));
scanf("%s", (t + 1));
for(int i = m; i <= n; i++) {
bool f = 1;
for(int j = i - m + 1; j <= i; j++)
if(c[j] != t[j - i + m]) {
f = 0;
break;
}
pre[i] = pre[i - 1] + (int)f;
}
while(q--) {
int l, r;
scanf("%d%d", &l, &r);
if(r - l + 1 < m) puts("0");
else printf("%d\n", pre[r] - pre[l + m - 2]);
}
return 0;
}
|
$ \texttt{C}$
形状肯定是先走$S$形，再直走，再回来。
后面的直走可以通过计算二阶前缀和和二阶后缀和得到，前面的直接加就可以。
细节还是很多的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 300000 + 5;
ll a[2][N], pre[2][N], suf[2][N], ipre[2][N], isuf[2][N];
int n;
int main() {
scanf("%d", &n);
ll sum1 = 0;
for(int i = 0; i < 2; i++)
for(int j = 1; j <= n; j++)
scanf("%lld", &a[i][j]), sum1 += a[i][j];
for(int i = 0; i < 2; i++)
for(int j = 1; j <= n; j++) {
pre[i][j] = pre[i][j - 1] + a[i][j];
ipre[i][j] = ipre[i][j - 1] + pre[i][j];
}
for(int i = 0; i < 2; i++) {
for(int j = n; j >= 1; j--) {
suf[i][j] = suf[i][j + 1] + a[i][j];
isuf[i][j] = isuf[i][j + 1] + suf[i][j];
}
}
bool isup = 0;
ll sum = 0, mx = -1e15;
for(int i = 1; i <= n; i++) {
if(isup == 0) {
sum += 1ll * (2 * i - 1) * a[0][i];
sum += 1ll * (2 * i) * a[1][i];
mx = max(mx, sum +
isuf[1][i + 1] + 2ll * i * suf[1][i + 1]
+ (ipre[0][n] - ipre[0][i]) - pre[0][i] * 1ll * (n - i) + (n + i) * suf[0][i + 1]);
isup = 1;
}
else if(isup == 1) {
sum += 1ll * (2 * i) * a[0][i];
sum += 1ll * (2 * i - 1) * a[1][i];
mx = max(mx, sum +
isuf[0][i + 1] + 2ll * i * suf[0][i + 1]
+ (ipre[1][n] - ipre[1][i]) - pre[1][i] * 1ll * (n - i) + (n + i) * suf[1][i + 1]);
isup = 0;
}
}
sum = 0;
for(int i = 1; i <= n; i++) sum += i * a[0][i];
for(int i = n; i >= 1; i--) sum += (n + (n - i + 1)) * a[1][i];
mx = max(mx, sum);
printf("%lld\n", mx - sum1);
return 0;
}
|
$\texttt{D}$
毒瘤构造。
只填最后一行和最后一列就可以。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 100 + 5;
int n, m;
int a[N], b[N], c[N][N], axor, bxor;
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]), axor ^= a[i];
for(int i = 1; i <= m; i++) scanf("%d", &b[i]), bxor ^= b[i];
if(axor != bxor) return puts("NO"), 0;
puts("YES");
for(int i = 1; i <= n - 1; i++) c[i][m] = a[i];
for(int i = 1; i <= m - 1; i++) c[n][i] = b[i];
c[n][m] = (a[n] ^ (bxor ^ b[m]));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
printf("%d%c", c[i][j], (j == m) ? '\n' : ' ');
return 0;
}
|
upd on 7.17
$ \texttt{E}$
我觉得$E$比$C,D$都简单，但是第一眼没瞪出来
相似一波，找出来两个边界，再对Fence预处理一波前缀和硬算就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 400000 + 10;
ll sy, a, b, pre[N], l[N], r[N];
int n, q;
double mpoint(ll x, ll y, ll xx, ll yy) {
if(x == xx) return xx;
double k = (double)(yy - y) / (double)(xx - x);
return (double)(k * x - y) / k;
}
int main() {
scanf("%lld%lld%lld", &sy, &a, &b);
scanf("%d", &n);
vector <pair <ll, ll> > v;
for(int i = 1; i <= n; i++) {
scanf("%lld%lld", &l[i], &r[i]);
v.push_back(make_pair(l[i], r[i]));
}
for(int i = 2; i <= n; i++)
v.push_back(make_pair(r[i - 1], l[i]));
v.push_back(make_pair(0ll, l[1]));
v.push_back(make_pair(r[n], 1000000000ll));
sort(v.begin(), v.end());
for(int i = 1; i < v.size(); i++) {
if(i & 1) pre[i] = pre[i - 1] + v[i].second - v[i].first;
else pre[i] = pre[i - 1];
}
scanf("%d", &q);
while(q--) {
ll x, y;
scanf("%lld%lld", &x, &y);
double aa = mpoint(x, y, a, sy), bb = mpoint(x, y, b, sy);
#define to(x) (double)((x)/(bb-aa)*(double)(b-a))
int lb = 0, rb = 2 * n, ans1 = -1, ans2 = -1;
while(lb <= rb) {
int mid = (lb + rb) >> 1;
if(bb >= (double)v[mid].first) ans1 = mid, lb = mid + 1;
else rb = mid - 1;
}
lb = 0, rb = 2 * n;
while(lb <= rb) {
int mid = (lb + rb) >> 1;
if(aa <= (double)v[mid].second) ans2 = mid, rb = mid - 1;
else lb = mid + 1;
}
if(ans1 == ans2) {
if(ans1 % 2 == 1) printf("%.15lf\n", (double)(b - a));
else printf("%.15lf\n", 0.000);
}
else if(ans1 == ans2 + 1) {
if(ans1 % 2 == 1) printf("%.15lf\n", to(bb - (double)v[ans1].first));
else printf("%.15lf\n", to((double)v[ans2].second - aa));
}
else {
double res = 0;
if(ans1 % 2 == 1) res += (bb - (double)v[ans1].first);
if(ans2 % 2 == 1) res += ((double)v[ans2].second - aa);
res += (double)(pre[ans1 - 1] - pre[ans2]);
printf("%.15lf\n", to(res));
}
}
return 0;
}
|
$\texttt{F}$
毒瘤题，还是BledDest的做法比较好懂。
因为我们新增的两条路径长度最小值为$min(dis1[x]+disn[y]+z,disn[x]+dis1[y]+z)$。
然后我们忽略$z$,不难发现我们要找两个没有边连接的$x,y$，最大化$min(dis1[x]+disn[y],disn[x]+dis1[y])$。
然后这玩意更改一下就可以用$set$维护了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <algorithm>
#define MP make_pair
using namespace std;
typedef long long ll;
const int N = 300000 + 5;
int n, m, nd[N];
ll dis[2][N];
vector <pair <int, int> > g[N];
void dfs(int id, int u, int pre, ll sum) {
dis[id][u] = sum;
for(int i = 0; i < g[u].size(); i++) {
int v = g[u][i].first;
if(v == pre) continue;
dfs(id, v, u, sum + g[u][i].second);
}
}
bool cmp(int x, int y) {
return dis[0][x] - dis[1][x] < dis[0][y] - dis[1][y];
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back(MP(v, w));
g[v].push_back(MP(u, w));
}
dfs(0, 1, 1, 0);
dfs(1, n, n, 0);
for(int i = 1; i <= n; i++) nd[i] = i;
sort(nd + 1, nd + n + 1, cmp);
set < pair <ll, int> > select;
select.clear();
ll mx = -1e15;
int px = -1, py = -1;
for(int i = 1; i <= n; i++) select.insert(MP(dis[1][nd[i]], nd[i]));
for(int pos = 1; pos <= n; pos++) {
select.erase(MP(dis[1][nd[pos]], nd[pos]));
int x = nd[pos];
vector <int> upd;
for(int i = 0; i < g[x].size(); i++) {
pair <ll, int> fd = MP(dis[1][g[x][i].first], g[x][i].first);
set < pair <ll, int> > :: iterator it = select.find(fd);
if(it != select.end()) {
upd.push_back(g[x][i].first);
select.erase(it);
}
}
if(!select.empty()) {
set <pair <ll, int> > :: iterator it = select.end();
--it;
int y = ((*it).second);
if(dis[0][x] + dis[1][y] > mx) {
mx = dis[0][x] + dis[1][y];
}
}
for(int i = 0; i < upd.size(); i++) {
select.insert(MP(dis[1][upd[i]], upd[i]));
}
}
while(m--) {
ll c;
scanf("%lld", &c);
printf("%lld\n", min(mx + c, dis[0][n]));
}
return 0;
}
|
$\texttt{G}$
不会高深的质因数分解算法，超集和忘了，咕咕咕。
$\texttt{Codeforces EDU 49}$
$\texttt{A}$
直接做。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int t, n;
char s[100 + 10];
int ok[30];
void color(char x) {
if(x > 'a') ++ok[x - 1 - 'a'];
if(x < 'z') ++ok[x + 1 - 'a'];
}
void solve() {
scanf("%d", &n);
scanf("%s", (s + 1));
for(int i = 1; i <= n / 2; i++) {
color(s[i]);
color(s[n - i + 1]);
if(*max_element(ok, ok + 26) < 2) {
puts("NO");
memset(ok, 0, sizeof(ok));
return ;
}
memset(ok, 0, sizeof(ok));
}
puts("YES");
}
int main() {
scanf("%d", &t);
while(t--) solve();
return 0;
}
|
$\texttt{B}$
推一波公式就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long ll;
ll n, q;
int main() {
scanf("%lld%lld", &n, &q);
while(q--) {
ll x, y;
scanf("%lld%lld", &x, &y);
if(x % 2 == y % 2) {
ll ans = (x - 1) / 2;
if((x - 1) % 2) ++ans;
ll now = ans * ((n + 1) / 2);
if((x - 1) % 2) --ans;
now += ans * (n / 2);
if(y % 2) printf("%lld\n", now + (y + 1) / 2);
else printf("%lld\n", now + y / 2);
}
else {
ll now = n * n / 2;
if(n % 2) ++now;
ll ans = (x - 1) / 2;
if((x - 1) % 2) ++ans;
now += ans * ((n) / 2);
if((x - 1) % 2) --ans;
now += ans * ((n + 1) / 2);
if(y % 2) printf("%lld\n", now + (y + 1) / 2);
else printf("%lld\n", now + y / 2);
}
}
return 0;
}
|
$\texttt{C}$
发现这玩意本质上是要最小化$\frac{a}{b}+\frac{b}{a}$
先把存在$a=b$的情况判掉
否则这玩意就是个拉钩函数，即$a/b$越接近1函数值越小，所以$sort$一遍之后挨个试就可以。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1000000 + 5;
int T;
int n, a[N], pool[N / 100];
void solve() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]), pool[a[i]] = 0;
for(int i = 1; i <= n; i++) ++pool[a[i]];
vector <pair <int, int> > v;
for(int i = 1; i <= n; i++) {
if(pool[a[i]] >= 2) {
v.push_back(make_pair(a[i], pool[a[i]]));
pool[a[i]] = 0;
}
}
sort(v.begin(), v.end());
int m = unique(v.begin(), v.end()) - v.begin();
ll fx = 0x3f3f3f3f, fy = 1, pos = -1;
for(int i = 0; i < m; i++) {
if(v[i].second >= 4) {
printf("%d %d %d %d\n", v[i].first, v[i].first, v[i].first, v[i].first);
return ;
}
if(i > 0) {
if((v[i - 1].first * v[i - 1].first + v[i].first * v[i].first) * fy
< v[i - 1].first * v[i].first * fx)
fx = v[i - 1].first * v[i - 1].first + v[i].first * v[i].first,
fy = v[i - 1].first * v[i].first,
pos = i;
}
}
printf("%d %d %d %d\n", v[pos - 1].first, v[pos - 1].first, v[pos].first, v[pos].first);
}
int main() {
scanf("%d", &T);
while(T--) solve();
return 0;
}
|
$\texttt{D}$
不难发现在这样的图上，最后一定会走到一个环上，所以一定要找环上最小的点放Trap.
非递归比较直观。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
const int N = 200000 + 5;
int c[N], a[N], n, vis[N];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
ll res = 0;
for(int i = 1; i <= n; i++) if(!vis[i]) {
set <int> st;
int p = i;
vis[i] = 1;
st.insert(i);
bool f = 0;
while(1){
p = a[p];
if(vis[p] && !st.count(p)) {
f = 1;
break;
}
vis[p] = 1;
if(st.count(p)) break;
st.insert(p);
}
if(!f) {
int np = a[p], ans = 0x3f3f3f3f;
while(np != p) {
ans = min(ans, c[np]);
np = a[np];
}
ans = min(ans, c[p]);
res += ans;
}
}
printf("%lld\n", res);
return 0;
}
|
$\texttt{E}$
设$dp(i,j,k1)$为前$i$行，目前$j$行是一样的，目前最长连续$k1$行是一样的。
转移的话把$j+1$和$1$和$k$取$\text{max}$.
然后可以看做是两个毫不相关的方案横竖叠在一起，很显然是一一对应的。
于是就可以直接拿$dp$的结果算。最后要$/2$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 500 + 5;
const int MOD = 998244353;
int n, k, dp[2][N][N], sum[N];
int add(int& x, int y) {
x += y;
if(x >= MOD) x -= MOD;
}
int main() {
scanf("%d%d", &n, &k);
dp[0][0][0] = 1;
for(int i = 0; i < n; i++) {
for(int j = 0; j <= n; j++)
for(int k1 = 0; k1 <= n; k1++)
dp[(i + 1) % 2][j][k1] = 0;
for(int j = 0; j <= i; j++)
for(int k1 = 0; k1 <= i; k1++) {
add(dp[(i + 1) % 2][1][max(k1, 1)], dp[i % 2][j][k1]);
add(dp[(i + 1) % 2][j + 1][max(k1, j + 1)], dp[i % 2][j][k1]);
}
}
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
add(sum[j], dp[n % 2][i][j]);
int res = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
if(i * j < k) res = (res + 1ll * sum[i] * sum[j] % MOD) % MOD;
}
printf("%d\n", 1ll * res * 499122177ll % MOD);
return 0;
}
|