洛天依专场QWQ
A. LuoTianyi and the Palindrome String
题意
给定一个回文串，求最长的非回文子串的长度，如果找不出非回文子串则输出-1。
这里的子串指原字符串删去任意几个字符后的字符串，没有要求连续。
思路
可以证明，如果给定的回文串所有字符相同，则没有非回文子串，输出-1。否则，最长非回文子串的长度就为原回文串的长度减1。
代码
void solve() {
string s;
cin >> s;
int cnt = count(s.begin(), s.end(), s[0]);
if(cnt == s.size()) {
cout << -1 << "\n";
} else {
cout << s.size() - 1 << "\n";
}
}
B. LuoTianyi and the Table
题意
给定一个n×m矩阵和n×m个元素，把这几个元素填入矩阵中。要求对于矩阵中的所有点(a,b)与(1,1)组成的子矩阵中，最大值减去最小值的差的和最大。
思路
先求出所有元素的最大值和次大值，以及最小值和次小值。
使得最终答案最大有两种情况，第一，最大值在左上角，最小值和次小值在左上角的两边；第二，最小值在左上角，最大值和次大值在最上角的两边。比较两中情况谁大即可求得最终答案。
还有一点值得注意，最值和次值的位置要根据n和m谁大谁小决定。
代码
void solve() {
int n, m;
cin >> n >> m;
if(n < m) {
swap(n, m);
}
vector<int> v(n * m);
for(int &c : v) {
cin >> c;
}
sort(v.begin(), v.end());
int max1 = v[n*m-1], max2 = v[n*m-2], mix1 = v[0], mix2 = v[1];
ll tmp1 = 1ll * (m - 1) * (n - 1) * (max1 - mix1);
ll tmp2 = 1ll * (n - 1) * (max1 - mix1) + 1ll * (m - 1) * (max2 - mix1);
ll tmp3 = 1ll * (n - 1) * (max1 - mix1) + 1ll * (m - 1) * (max1 - mix2);
cout << tmp1 + max(tmp2, tmp3) << "\n";
}
C. LuoTianyi and the Show
题意
有n个人和m个座位，每个人都有一个值。
“-1”表示这个人坐在已经坐着的人群的最左边，如果还没有任何人坐着，就坐在位置m处，如果1已经被坐了，那么这个人就没有位置了。“-2”与“-1”相反，表示这个人坐在已经坐着的人群的最右边。如果这个值是大于0的正整数a，那么就坐在位置a上，如果位置a已经被坐了，那么这个人就没有位置坐了。
可以安排所有人入座的顺序，求最多可以坐多少人。
思路
如果人群中没有“-1”和“-2”的值，设cnt为出现的不同正值的数量，那么答案为min(cnt, m)。
如果人群中“-1”和“-2”只出现了一个，设cnt1为其中之一出现的数量，cnt2为出现的不同正值的数量，那么答案为min(cnt1+cnt2, m)。
若这“-1”和“-2”两者都出现了，我们可以考虑选择一个的正值，这个正值把所有座位划分为两个部分，一部分用只用“-1”和部分正值，另一部分用“-2”和其余正值。枚举每个正值作为划分点，可以得出最大答案。
代码
void solve() {
int n, m;
cin >> n >> m;
int cnt1 = 0, cnt2 = 0;
set<int> st;
for(int i = 0; i < n; i++) {
int tmp; cin >> tmp;
if(tmp > 0) {
st.insert(tmp); //set自动去重排序
} else {
tmp == -1 ? cnt1++ : cnt2++;
}
}
int ans = min(m, max(cnt1, cnt2) + (int)st.size());
int i = 0, j = st.size() - 1;
for(auto it = st.begin(); it != st.end(); it++, i++, j--) {
int tmp = min(cnt1 + i, *it - 1) + min(cnt2 + j, m - *it) + 1;
ans = max(tmp, ans);
}
cout << ans << "\n";
}