SDUT 2021 Spring Team Contest(for 20) - 10

A - ABB

题意

给一个初始串，在初始串后加上一个字符为一次合法操作，求使初始串变成回文串的最小操作次数。

思路

枚举ii从左到右的位置，如果i ni~n能构成回文串，那么只需要在所给串的后面加上ii，就是所求的字符串，答案为ii；若不存在回文，需要在所给串的后面加上前面n−1n-1个字符，答案为n−1n-1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstring>
using namespace std;
int n;
int main(){
    string a,b;
    cin>>n>>a;
    int res = 1e9;
    for (int i = 0 ; a[i] ;i ++){
        int cnt = 0;
        for (int j = 0; j <= n -1 - i >> 1; j ++)
        if (a[i+j] == a[n-1-j] && i + j < n-1 - j) cnt+=2;
        else if ( i + j == n - j - 1) cnt++;
        else break;
        if (cnt == n - i ){
            cout<<i<<'\n';
            return 0;
        }
    }
    cout<<n-1<<'\n';
}

E - Zeldain Garden

题意

给出两个正整数nn和mm，求区间[n,m]内的约数和

解法一

倍增法求约数个数，求出1——n1——n的所有约数，答案为n∗(1+12+...+1n)n*(1+\frac{1}{2}+...+\frac{1}{n})时间复杂度为O(n∗logn)O(n*logn)

如果暴力求解定会超时

答案y关于x的函数方程为y=nxy = \frac{n}{x}

图像关于点(n,n)(\sqrt{n},\sqrt{n})对称，求一半面积乘上2，再减去n∗n\sqrt{n}*\sqrt{n}得到答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
ll n,m;
ll f(ll x){
    ll res = 0;
    ll t = sqrt((double)x);
    for (ll i = 1; i <= t; i ++) res += x /i;
    res = res *2 - (ll)t*t;
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    cout<<f(m) - f(n-1)<<'\n';
}

解法二

数论分块

我们要求解

∑i=1n⌊ni⌋\sum_{i=1}^n⌊ \frac{n}{i} ⌋

可以发现ni\frac{n}{i}在某区间内是相等的如107\frac{10}{7}，108\frac{10}{8}，109\frac{10}{9}，1010\frac{10}{10}，我们可以通过对ni\frac{n}{i}值相等的区间O(1)O(1)求和

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# include <iostream>
using namespace std;
typedef long long ll;
ll n,m;
ll f(ll x){
    ll l, r;
    ll ans = 0;
    for( l = 1; l <= x; l = r + 1){
        r = x / (x / l);//求区间右端点
		ans += x / l * (r - l + 1);
    }
    return ans;
}
int main(){
    cin>>n>>m;
    cout<<f(m) - f(n-1)<<'\n';
}

H - Ponk Warshall

题意

给一个初始串aa和一个目标串bb，求使aa变成bb的最小操作次数。串中只含有′A′,′C′,′G′,′T′'A','C','G','T'，每次操作可以交换任意两个字符。

思路

枚举操作次数

1.交换一次，使两个字符都移动到目标位置

2.交换两次，使三个字符都移动到目标 位置

3.交换三次，使四个字符都移动到目标位置

代码

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 <iostream>
#include <algorithm>
#include <map>
#include <unordered_map>
using namespace std;
const int N = 1e6 + 7;
map<char,int> q;
int a[4][4];
int n,m;
char s[N],e[N];
int main(){
	q['A'] = 0,q['G'] = 1,q['C'] = 2, q['T'] = 3;
	scanf("%s%s",s,e);
	for (int i = 0; s[i]; i ++)
		if (s[i] != e[i]) 
			a[q[s[i]]][q[e[i]]]++;
	int res = 0;
	for (int i = 0; i < 4; i++)
		for (int j = 0; j< 4; j++){
			int x = min(a[i][j],a[j][i]);
			a[i][j] -= x, a[j][i] -=x;
			res += x;
		}
	for (int i =0 ; i < 4; i++)
		for (int j = 0; j < 4; j++)
			for (int k = 0; k< 4; k++){
				int x = min(min(a[i][j],a[j][k]),a[k][i]);
				a[i][j] -= x, a[j][k] -= x, a[k][i] -= x;
				res += x << 1;
			}
	for (int i = 0; i < 4; i++) res += (a[i][0] * 3);
	printf("%d\n",res);
}