Codeforces Round #825 (Div. 2)
B. gcd&lcm
C1. 简单DP
C2. DP+线段树+二分答案
D. 思维
A. Make A Equal to B
题意：
对于每个样例，输入n代表数组a和数组b的长度，两个数组都只包含0和1。
可以进行两种操作，一是讲ai变为1-ai，二是将数组a按照你想的方式重新排列。
输出让数组a完全与数组b相同最小需要多少次。
分析：
答案是数组a和数组b不同的位置数cnt和两个数组中1的个数的差的绝对值加1中小的那一个
AC代码：
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 <bits/stdc++.h>
using namespace std;
int t, n, cnt;
int ar[105], br[105];
int suma[105], sumb[105];
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
cnt = 0;
for(int i = 1; i <= n; ++i)
{
scanf("%d", &ar[i]);
suma[i] = suma[i - 1] + ar[i];
}
for(int i = 1; i <= n; ++i)
{
scanf("%d", &br[i]);
if(ar[i]^br[i]) ++cnt;
sumb[i] = sumb[i - 1] + br[i];
}
printf("%d\n", min(cnt, abs(suma[n] - sumb[n]) + 1));
}
return 0;
}
|
B. Playing with GCD [gcd & lcm]
题意：
对于每个样例输入一个n，代表数组长度，之后输入数组a，让构造一个数组b，满足ai = gcd（bi，bi+1）（1<=i<=n）。存在数组b输出YES，不存在输出NO。
分析：
让a0 = 1， an+1 = 1，bi = lcm（ai-1，ai），之后遍历一遍数组b，看ai是否都等于gcd（bi，bi+1)即可。
AC代码：
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, n;
ll ar[100050];
ll ans[100050];
bool flag;
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a%b);
}
ll lcm(ll a, ll b)
{
return a / gcd(a, b) * b;
}
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
flag = false;
for(int i = 1; i <= n; ++i) scanf("%lld", &ar[i]);
ar[0] = ar[n + 1] = 1;
for(int i = 1; i <= n + 1; ++i)
{
ans[i] = lcm(ar[i - 1], ar[i]);
}
for(int i = 1; i <= n; ++i)
{
if(gcd(ans[i], ans[i + 1]) != ar[i])
{
flag = true;
break;
}
}
if(flag) printf("NO\n");
else printf("YES\n");
}
return 0;
}
|
C1. Good Subarrays (Easy Version) [简单dp]
题意：
对于每个样例，输入一个n，之后输入一个长度为n的数组。求有多少对(l,r)满足以下条件：
截取数组ar[l~r]，把这个数组当成一个新的数组br，下标从1开始，br[i]>=i对所有的1<=i<=r-l+1都成立。
分析：
dp
dp[i]表示当r取i时可截取的区间最长是多少。
dp[0] = 0
dp[i] = min(dp[i-1] + 1, ar[i])
AC代码：
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, n;
ll ar[200050];
ll dp[200050];
ll ans;
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%lld", &ar[i]);
dp[0] = 0;
ans = 0;
for(int i = 1; i <= n; ++i)
{
dp[i] = min(dp[i - 1] + 1, ar[i]);
ans += dp[i];
}
printf("%lld\n", ans);
}
return 0;
}
|
C2. Good Subarrays (Hard Version) [dp+线段树+二分答案]
update at 2022/10/21
klee知道了捏
题意：
$q$次询问，每次询问输入$p,x$,之后将 $a_p=x$ ,对于每次询问输出和$C1$一样的东西，每次询问独立（询问完后数组复原)。
分析：
同样需要做dp，对原数组的dp记为$dp[i]$,更改后的的数组的dp记为$ddp[i]$，$ans=\sum_{1}^{n}{ddp[i]}$。
显然对于$1<=i<=p-1$满足$ddp[i]=dp[i]$,这部分结果可以通过前缀和来维护。
之后，我们假设$q$是位置$p$之后第一个$ddp[q] = a[q]$的位置($q$可能不存在），对于$p<=i<q$,可以发现满足$ddp[i] = ddp[i - 1] + 1(p + 1 <=i < p)$,那么$\sum_{p}^{q-1}{ddp[i]}$就可以通过等差数列求和求出。
对于$\sum_{q}^{n}{ddp[i]}$,我们定义数组$track[i]=\sum_{j=i}^{n}{dp[j]}$ if $dp[i]=a[i]$(就是假设$dp[i] = a[i]$,之后再确定$dp[j]$$(i+1<=j<=n)$的dp数组后缀和)，那么$\sum_{q}^{n}{ddp[i]} = track[q]$,预处理$track[i]$数组即可。
即ans分为三部分$(1,p-1),(p,q-1),(q,n)$。
对于$track[i]和q$的确定都需要用到二分答案。以求$q$为例,对于$p<=i<q$的点画出其$i-ddp[i]$的函数图像可以发现这些点都在一条斜率为1的直线$y=x + d(ddp = i + d)$上，由于点$(p,ddp[p])$在直线上，故截距$d = ddp[p] - p$,而点$q$就是区间$(p + 1, n)$内第一个满足$ar[i] - i <= ddp[p] - p$的点（画出$i-a[i]$的图像，求一条过点$(i,a[i])$切斜率为1的直线，求第一条截距小于等于$ddp[p]-p$的直线）。这个过程可以通过线段树维护区间最小值+二分答案确定。
AC代码：
时限3s，写了2651ms，std只有（1325ms和374ms），震惊！（自我感觉写的常数并不大捏)
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f;
ll n, m, x, p, q;
ll ar[200050];
ll d[200050];
ll dp[200050], ddp;
ll sum[200050];
ll track[200050];
ll ne[200050];
ll ans, dd;
struct node
{
ll l, r;
ll mi;
}tree[800050];
void pushup(int p)
{
tree[p].mi = min(tree[p<<1].mi, tree[p<<1|1].mi);
}
void build(ll p, ll l, ll r)
{
tree[p].l = l, tree[p].r = r;
if(l == r)
{
tree[p].mi = d[l];
return ;
}
ll mid = (l + r) >> 1;
build(p<<1, l, mid);
build(p<<1|1, mid + 1, r);
pushup(p);
}
ll query(ll p, ll l, ll r)
{
if(l <= tree[p].l && tree[p].r <= r) return tree[p].mi;
ll res = inf;
ll mid = (tree[p].l + tree[p].r) >> 1;
if(l <= mid) res = min(res, query(p<<1, l, r));
if(mid < r) res = min(res, query(p<<1|1, l, r));
return res;
}
ll binary_find(ll ql, ll qr, ll d)
{
if(query(1, ql, qr) > d) return n + 1;
ll res;
ll l = ql, r = qr, mid;
while(l <= r)
{
mid = (l + r) >> 1;
if(query(1, ql, mid) <= d)
{
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
return res;
}
int main()
{
scanf("%lld", &n);
for(int i = 1; i <= n; ++i) scanf("%lld", &ar[i]);
dp[0] = 0;
for(int i = 1; i <= n; ++i)
{
dp[i] = min(dp[i - 1] + 1, ar[i]);
d[i] = ar[i] - i;
sum[i] = sum[i - 1] + dp[i];
}
build(1, 1, n);
track[n] = ar[n];
ne[n] = n + 1;
for(int i = n - 1; i > 0; --i)
{
ne[i] = binary_find(i + 1, n, d[i]);
if(ne[i] == n + 1) track[i] = (ar[i] + ar[i] + n - i) * (n - i + 1) / 2;
else
{
track[i] = track[ne[i]];
track[i] += (ar[i] + ar[i] + ne[i] - 1 - i) * (ne[i] - i) / 2;
}
}
scanf("%d", &m);
while(m--)
{
scanf("%lld%lld", &p, &x);
ddp = min(dp[p - 1] + 1, x);
q = binary_find(p + 1, n, ddp - p);
ans = sum[p - 1];
if(q == n + 1)
{
ans += (ddp + ddp + n - p) * (n - p + 1) / 2;
}
else
{
ans += (ddp + ddp + q - p - 1) * (q - p) / 2;
ans += track[q];
}
printf("%lld\n", ans);
}
return 0;
}
|
D. Equal Binary Subsequences
题意：
对于每个样例，先输入一个n，之后输入一个长度为2*n的01串s。
你可以进行一个操作，选组一个数组b,满足1<=b1<b2<b3<...<bm<=2*n,之后让s[b1]=s[bm],s[b2]=s[b1],s[b3]=s[b2],s[b4]=s[b3]依次类推。
在此之后讲串s分成两个串，要求两个串当中的任意两个字符在原串中的相对位置不变，并且两个串完全相同。
先输出m，再输出数组b，最后输出被分成的两个串中任意一个串的每一个字符在操作完后的原串对应的下标。（输出任意一种满足要求的答案就可）
分析：
操作不会改变01串中0和1的数量，故0和1的数量都必须是偶数。否则答案不存在
考虑将01串分成n组，每组两个字符第i组s[2*i-1,2*i]。
n组中，假设完全相同的两个组有x个，不同的组有y个。x和y均为偶数，因为1的数量是偶数，而2*x+y表示1的数量，故y是偶数。对这y个组，一个组选择字符0，另一个字符选择字符1，交替选择，作为数组b，由于y是偶数，所以进行一次操作后这y个组也会变成相同的。之后输出2*n内的奇数或者偶数即可。
AC代码：
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
| #include <bits/stdc++.h>
using namespace std;
int t, n;
string s;
int sum;
vector<int> x, y;
int br[100050];
int p[100050];
int main()
{
cin >> t;
while(t--)
{
cin >> n;
cin >> s;
s = " " + s;
sum = 0;
x.clear();
for(int i = 1; i <= 2 * n; ++i) if(s[i] == '1') ++sum;
if(sum&1)
{
cout << -1 << '\n';
continue;
}
for(int i = 1; i <= 2 * n; i += 2) if(s[i] != s[i + 1]) x.push_back(i);
for(int i = 0; i < x.size(); ++i)
{
if(i&1)
{
if(s[x[i]] == '1') br[i] = x[i];
else br[i] = x[i] + 1;
}
else
{
if(s[x[i]] == '0') br[i] = x[i];
else br[i] = x[i] + 1;
}
}
cout << x.size() << '\n';
for(int i = 0; i < x.size(); ++i) cout << br[i] << ' ';
if(x.size() != 0) cout << '\n';
for(int i = 1; i <= 2 * n; i += 2) cout << i << ' ';
cout << '\n';
}
return 0;
}
|