A. Turtle and Good Strings
思路：题意大致为把一个字符串分成若干段，要求每两段，前一段的首字符不能等于后的一段的尾字符，给你一个字符串，能不能构造出合法方案。观察到，分的段数越小，越有助于我们判断。所以，不妨分成两段，问题转化为判断首尾字符是否相等。
代码：
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define pii pair<int, int>
#define debug(x) cout << "x = " << x << endl;
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 5e5 + 5, P = 13331;
void solve()
{
int T = 1;
cin >> T;
while (T--)
{
string s;
int n;
cin >> n >> s;
if (s[0] != s[n - 1])
cout << "yes" << endl;
else
cout << "no" << endl;
}
}
signed main()
{
ios;
solve();
return 0;
}
B. Turtle and Piggy Are Playing a Game 2
思路：题意可以转化成，为了最大化最后剩下的数，每次先手能删除当前最大的数，每次后手能删除当前最小的数。 所以答案是原序列的第 $$\lfloor \frac {n}{2} \rfloor + 1$$ 小的数。
代码：
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define pii pair<int,int>
#define debug(x) cout<<"x = "<<x<<endl;
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 5e5 + 5,P = 13331;
int a[N],n;
void solve() {
int T = 1;
cin>>T;
while(T --) {
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> a[i];
sort(a + 1, a + 1 + n);
int cnt = n - 1,l;
if(cnt&1)
{
l = cnt / 2 + 1;
}
else
{
l = r = cnt / 2;
}
cout << a[l + 1] << endl;
}
}
signed main() {
ios;
solve();
return 0;
}
C. Turtle and Good Pairs
思路：既然题目让我们最大化好对的数量，那我们不让去分类讨论一下那些 $$(i,j)$$ 是好对。
- 若 $$S_i=S_j$$，那么 $$(i,j)$$ 是一个好对。
- 若 $$S_i \neq S_j$$ ，且 $$\exists k \in [i,j)$$ 使得 $$S_k \neq S_i \and S_k \neq S_j$$，那么 $$(i,j)$$ 是一个好对。
不妨把 $$S$$ 划分成若干个由相同字符组成的连续段，那么如果 $$(i,j)$$ 为好对，则 $$i$$ 所在的连续段和 $$j$$ 所在的连续段必然不相邻。令 $$m$$ 为字符串 $$S$$ 连续段的数量，$$a_i$$ 为第 $$i$$ 段的长度，那么好对数量应为 $$\frac{n(n-1)}{2}-\sum_{i=1}^{m-1}a_ia_{i+1}$$，问题转化为令 $$\sum_{i=1}^{m-1}a_i*a_{i+1}$$ 最小。我们只需这样构造，令每一个字符不等于上一个字符，当只剩余一个字符时，全放在字符串最后即可。
代码：
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define pii pair<int, int>
#define debug(x) cout << "x = " << x << endl;
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 5e5 + 5, P = 13331;
struct node
{
int id, num;
bool operator<(const node &u) const
{
return num < u.num;
}
};
int n;
void solve()
{
int T = 1;
cin >> T;
while (T--)
{
node a[26];
cin >> n;
char c;
for (int i = 0; i < 26; i++)
a[i].id = i, a[i].num = 0;
for (int i = 0; i < n; i++)
{
cin >> c;
a[c - 'a'].num++;
}
sort(a, a + 26);
int st = 0, ed = 25;
while (a[st].num == 0)
st++;
int cnt = 0;
while (cnt < n)
{
if (cnt % 2 == 0)
{
if (a[ed].num == 0)
{
ed--;
}
cout << (char)('a' + a[ed].id);
a[ed].num--;
cnt++;
}
else
{
if (a[st].num == 0)
{
st++;
}
cout << (char)('a' + a[st].id);
a[st].num--;
cnt++;
}
}
cout << endl;
}
}
signed main()
{
ios;
solve();
return 0;
}
D1. Turtle and a MEX Problem (Easy Version)
思路：思路很好想到，设 $$u_i$$ 为序列 $$i$$ 最小的没有出现的非负整数，$$v_i$$ 为序列 $$i$$ 次小的没有出现的非负整数，容易发现 $$x$$ 经过若干次操作，最大值为 $$\max(\sum^n_{i=1}v_i,x)$$。不让设 $$\sum^n_{i=1}v_i$$ 为 $$k$$，则最后的答案为 $$\sum_{i=0}kk+\sum_{i=k+1}mi$$，因为 $$m \leq 10^9$$，所以后面那一段需要用等差数列求和公式。（赛时脑抽了，没注意到...）
代码：
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define pii pair<int, int>
#define debug(x) cout << "x = " << x << endl;
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 5e5 + 5, P = 13331;
map<int, int> mp;
void solve()
{
int T = 1;
cin >> T;
while (T--)
{
int mx = 0, n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int l;
cin >> l;
mp.clear();
for (int j = 1, x; j <= l; j++)
{
cin >> x;
mp[x] = 1;
}
bool f = false;
for (int j = 0; j <= l + 2; j++)
{
if (mp[j] == 0)
{
if (!f)
f = true;
else
{
mx = max(mx, j);
break;
}
}
}
}
int cnt1 = min(mx, m) + 1, cnt2 = max(m - mx, (int)0);
int ans = cnt1 * mx + (mx + 1 + m) * cnt2 / 2;
cout << ans << endl;
}
}
signed main()
{
ios;
solve();
return 0;
}
D2. Turtle and a MEX Problem (Hard Version)
待补......
标签：cnt,cout,int,ios,968,Codeforces,long,Div,define From： https://www.cnblogs.com/zc-study-xcu/p/18380997