总结
成绩：SOLVE：3，Penalty：5
E
签到题
取 $x − lowbit(x)$ 即可，如果 $x$ 是 2 的整数次幂则无解
C
从左向右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
| void solve()
{
int n;cin>>n;
string a,b;
cin>>a>>b;
int ans=0;
for(int i=0;i<n;i++){
dp[0][i]=0;
dp[1][i]=0;
}
a=' '+a;b=' '+b;
for(int i=1;i<=n;i++){
if(a[i]=='R'){
dp[0][i]=dp[0][i-1]+1;
}
if(b[i]=='R'){
dp[1][i]=dp[1][i-1]+1;
}
int x=dp[0][i],y=dp[1][i];
if(a[i]=='R'){
dp[0][i]=max(dp[0][i],y+1);
}
if(b[i]=='R'){
dp[1][i]=max(dp[1][i],x+1);
}
ans=max({ans,dp[1][i],dp[0][i]});
}
if(ans==0){
cout<<"0";
return ;
}
cout<<ans-1<<'\n';
}
|
H
如果选择的左端点为1，那么利用前缀和记录每一个落点即可
对于左端点非1的点，我们可以转化问题，把1到左端点前面的操作加到终点上，等价于从左端点为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
49
50
| void SINGLE_TEST()
{
int n,x,y;
cin >> n >> x >> y;
string s;
cin >> s;
map<PII, set<int>> mp;
mp[{0,0}].insert(0);
if(x==0&&y==0){
cout<<n*(n+1)/2<<"\n";
return;
}
int tx = 0, ty = 0;
for (int i = 0; i < n; i++) {
if(s[i]=='W'){
ty++;
}else if(s[i]=='A'){
tx--;
}else if(s[i]=='D'){
tx++;
}else{
ty--;
}
mp[{tx,ty}].insert(i+1);
}
ll ans = 0;
for (int i = 0; i < n; i++) {
if(i!=0){
if(s[i-1]=='W'){
y++;
}else if(s[i-1]=='A'){
x--;
}else if(s[i-1]=='D'){
x++;
}else{
y--;
}
}
if(!mp.count({x,y})){
continue;
}
while(!mp[{x,y}].empty()&&*mp[{x,y}].begin()<i){
mp[{x,y}].erase(*mp[{x,y}].begin());
}
if (mp[{x, y}].size()) {
ans += n-*mp[{x,y}].begin()+1;
}
}
cout << ans << "\n";
}
|
B
使用Kruskal解决，关键在于边怎么取
考虑到$\sum k\leqslant10^5$
对于点集个数$\geqslant \sqrt{10^5}$,那么边的条数在最坏的情况下有可能到达$10^5$，那我们不妨直接遍历所有的边
这里可以得出一个结论，因为$k$的总数固定，那么点集个数$\geqslant \sqrt{10^5}$的情况一定不会出现很多，具体的，是$\sqrt{10^5}$次，时间复杂度为$O(n\sqrt{n})$
对于点集个数$< \sqrt{10^5}$,这样的情况可能会出现很多，而且边的个数显然并不会占总的边的个数的大部分，因此，我们不妨用$O(k^2)$处理出所有的边，时间复杂度为$\sum k^2\times \frac{q}{k}=\sum kq$最坏的情况下时间复杂度为$O(n\sqrt{n})$
因此，加上并行的Kruskal，总时间复杂度为$O(n\sqrt{n}+mlogm)$
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
| unordered_map<int, int> mp[N];
void SINGLE_TEST() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
cin >> edges[i][1] >> edges[i][2] >> edges[i][0];
edges[i][1]--;
edges[i][2]--;
if (edges[i][1] > edges[i][2]) swap(edges[i][1], edges[i][2]);
}
sort(edges, edges + m);
for (int i = 0; i < m; i++) {
if (!mp[edges[i][1]].count(edges[i][2])) {
mp[edges[i][1]][edges[i][2]] = i;
}
}
DSU dsu(n);
for (int i = 0; i < n; i++) d[i] = INF;
while (q--) {
int k;
cin >> k;
vector<int> v(k);
for (int i = 0; i < k; i++) {
cin >> v[i];
v[i]--;
ex[v[i]] = 1;
}
ll ans = 0;
int cnt = 0;
if (k <= 300) {
sort(v.begin(), v.end());
vector<int> tmp;
for (auto v1 : v) {
int t = -1;
for (auto v2 : v) {
if (mp[v1].count(v2)) {
tmp.push_back(mp[v1][v2]);
}
}
}
sort(tmp.begin(), tmp.end());
for (auto i : tmp) {
if (dsu.merge(edges[i][1], edges[i][2])) {
ans += edges[i][0];
cnt++;
}
}
} else {
for (int i = 0; i < m; i++) {
if (ex[edges[i][1]] && ex[edges[i][2]]) {
if (dsu.merge(edges[i][1], edges[i][2])) {
ans += edges[i][0];
cnt++;
}
}
}
}
if (cnt < k - 1) ans = -1;
cout << ans << "\n";
for (auto v1 : v) {
dsu.f[v1] = v1;
dsu.siz[v1] = 1;
ex[v1] = 0;
}
}
}
|