题面：http://codeforces.com/contest/798/problems
A. Mike and palindrome
题意：给定一个长度不超过15的字符串要求你修改一个字符，问是否能使之成为一个回文串
解法：暴力
如果修改一个字符串会使得它变为一个回文串，则必然不修改前反转字符串有且仅有两个字符不同。举个例子对于字符串$abca$，反转后变为$acba$第2位和第3位的字符不相同。
所以只要反转比一下就可以了。
但是还有个特殊情况，如果回文串的长度为奇数，比如aacaa，这种情况下只需要修改中间字符即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
const int maxn = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string s, t;
cin >> s;
t = s;
reverse(t.begin(), t.end());
int cnt = 0;
for(int i = 0; i < s.length(); i++)
if(s[i] != t[i]) cnt++;
if(cnt == 2 || (cnt == 0 && s.length() % 2))
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
B. Mike and strings
题意：给定$n$个字符串，每次操作可以将头部的一个字符移至末尾，问要想将所有字符串变成相同的最少需要几次操作。若不能做到则输出-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
using namespace std;
const int maxn = 2e5 + 10;
string a[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, len, ans = INT_MAX;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a[i];
if(i == 0) len = (int)a[0].length();
else if(a[i].length() != len)
{
cout << -1 << endl;
return 0;
}
}
for(int i = 0; i < n; i++)
{
int temp = 0;
for(int j = 0; j < n; j++)
{
if(j == i) continue;
int k;
for(k = 0; k < len; k++)
{
string t = a[j].substr(k) + a[j].substr(0, k);
if(t == a[i])
{
temp += k;
break;
}
}
if(k == len)
{
cout << -1 << endl;
return 0;
}
}
ans = min(ans, temp);
}
cout << ans << endl;
return 0;
}
C. Mike and gcd problem
题意：给定一个序列，长度为$n$，每次可以做一个操作，将任意相邻的两个数$a_i,a_{i+1}$替换为$a_i-a_{i+1},a_i+a_{i+1}$。问经过多少次操作可以将使得原序列中所有数的最大公约数不等于1。
解法：考虑每次操作所带来的影响，对于两个奇数，操作以后会变为两个偶数，最大公约数满足了要求。而对于一奇一偶，只需要一次操作变为两奇再一次操作就会变为两偶。
但还有一个特殊情况，对于3 9 15这类都为奇数但最大公约数大于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
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
int gcd(int a, int b)
{
if(!b) return a;
return gcd(b, a % b);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, g = 1;
cin >> n;
cout << "YES" << endl;
for(int i = 0; i < n; i++)
{
cin >> a[i];
if(i == 0) g = a[i];
else
g = gcd(g, a[i]);
}
if(g > 1)
cout << 0 << endl;
else{
int cnt = 0;
for(int i = 0; i < n - 1; i++)
{
if(a[i] % 2)
{
if(a[i + 1] % 2)
cnt++;
else
cnt += 2;
a[i + 1] = 2;
}
}
if(a[n - 1] % 2) cnt+= 2;
cout << cnt << endl;
}
return 0;
}
D. Mike and distribution
题意：给定$a,b$两个序列，分别有$n$个数，现在要在其中选$\lfloor \frac{n}2 \rfloor + 1$个下标，使得选出来下标的$a_i$和$b_i$的值不小于$a$和$b$所有元素和的一半。
解法：贪心 思维
对于二维的贪心我们可以先让它变成其中一维有序，这样只需要重点考虑另一维
对于本题而言，我们先将设定元祖$[a_i,b_i,idx]$，先将这些元祖按$a_i$从大到小的序列排好序
对于奇数个数的序列，首先取第一个元祖，对于剩下的$\frac{n}2$个，两个两个考虑，每次取两个中$b$值较大的那一个，容易发现这样对于$b$序列一定满足要求，因为对于每个元素都有一个比它大的元素被取了。而对于$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
37
38
39
40
41
42
43
44
45
46
47
using namespace std;
const int maxn = 2e5 + 10;
struct node{
ll a, b;
int idx;
}p[maxn];
bool cmp(const node& a, const node& b)
{
return a.a > b.a;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> p[i].a;
for(int i = 1; i <= n; i++)
{
cin >> p[i].b;
p[i].idx = i;
}
sort(p + 1, p + 1 + n, cmp);
vector<int> ans;
ans.push_back(p[1].idx);
for(int i = 2; i <= n - 1; i += 2)
{
if(p[i].b > p[i + 1].b)
ans.push_back(p[i].idx);
else
ans.push_back(p[i + 1].idx);
}
if(n % 2 == 0)
ans.push_back(p[n].idx);
cout << ans.size() << endl;
for(auto idx: ans)
cout << idx << ' ';
cout << endl;
return 0;
}
解法2:玄学解法（随机）
STL中有个叫做random_shuffle的东西，将所有元素随机排列。只需要把1-n的序列random_shuffle一下取前$\lfloor \frac{n}2 \rfloor + 1$看满不满足条件就可以。
也就跑了400多ms嘛/笑哭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
using namespace std;
const int maxn = 2e5 + 10;
ll a[maxn], b[maxn];
ll suma, sumb;
int idx[maxn];
int n;
bool solve(int *p)
{
ll prea = 0, preb = 0;
for(int i = 1; i <= n / 2 + 1; i++)
{
prea += a[p[i]];
preb += b[p[i]];
}
return 2 * prea >= suma && 2 * preb >= sumb;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
suma += a[i];
}
for(int i = 1; i <= n; i++)
{
cin >> b[i];
sumb += b[i];
}
for(int i = 1; i <= n; i++)
idx[i] = i;
while(1)
{
random_shuffle(idx + 1, idx + 1 + n);
if(solve(idx))
{
cout << n / 2 + 1 << endl;
for(int i = 1; i <= n / 2 + 1; i++)
cout << idx[i] << ' ';
cout << endl;
break;
}
}
return 0;
}