Contestant'. Rank 1357. Rating +14 (+264 -250).
A. LuoTianyi and the Palindrome String
题意
给定一个字符串，输出最长的非回文子串的长度。
思路
很显然，如果整个字符串是回文串，那么我们拿掉一个字符即可，长度为 \(n - 1\)；
如果不是，那么整个字符串就是非回文串，长度为 \(n\)。
当然，如果整个字符串都是由一个字母组成的，那么无法将其变为非回文，无解输出 \(-1\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
string s;
cin >> s;
bool f = false;
int n = s.size();
for(int i=1;i<n;i++){
if(s[0] != s[i]) f = true;
}
if(!f){
cout << -1 << '\n';
return;
}
for(int i=0;i<n/2;i++){
if(s[i] != s[n - i - 1]) f = false;
}
cout << (f ? n - 1 : n) << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}很签到，虽然要绕一下
B. LuoTianyi and the Table
题意
给定一个 \(n \times m\) 的矩阵，以及 \(n \times m\) 个元素组成的序列。将序列中所有元素填入矩阵中，满足下面的式子最大，并输出这个最大值：
\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\left(\max\limits_{1 \le x \le i, 1 \le y \le j}a_{x,y}-\min\limits_{1 \le x \le i, 1 \le y \le j}a_{x,y}\right)\)
思路
思维题。
如果要让最大值减最小值的值最大，那么我们一定会用最大的值减去最小的值。
对于上述式子，我们不难发现，只要满足下面的两种情况，即为最大值：
左上角为最大值，其相邻两个元素为最小值和次小值；
左上角为最小值，其相邻两个元素为最大值和次大值
我们取两者的最大值即可。
时间复杂度：\(O(nm)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n, m;
cin >> n >> m;
vector<int> a(n * m);
for(int i=0;i<n*m;i++) cin >> a[i];
sort(all(a));
if(n > m) swap(n, m);
int ans1 =
(n * (m - 1)) * (a[n * m - 1] - a[0])
+ (n - 1) * (a[n * m - 1] - a[1]);
int ans2 =
(n * (m - 1)) * (a[n * m - 1] - a[0])
+ (n - 1) * (a[n * m - 2] - a[0]);
cout << max(ans1, ans2) << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}偏思维的题捏
C. LuoTianyi and the Show
题意
给定三种操作如下：
坐在当前最左边的人的左边，如果最左边的人左边无位置，那么坐到最右边；
坐在当前最右边的人的右边，如果最右边的人右边无位置，那么坐到最左边；
坐到指定位置
现在，给定 \(n\) 个人的操作，操作用一个数字表征，其中操作 \(1\) 为 \(-1\)，操作 \(2\) 为 \(-2\)，操作 \(3\) 为一个正整数，代表坐到该位置。
如果不可以坐，那么这个人离场。
输出按任意顺序排座后最多能坐多少人。
思路
首先，重复的正整数我们直接筛去，因为不会重叠。
那么，对于第一个数，我们有两个选择：
执行操作 \(3\)，对此我们可以标记操作 \(3\) 的所有下标，并枚举这些下标。既然我们确定了一个点，那么我们只能从这个点开始向左右拓展。 为计算方便，我们可以用 \(pre, suf\) 数组记录前 \(i\) 个数和后 \(n - i + 1\) 个数去掉操作 \(3\) 后有多少空位置。 那么， \(\min(pre[i], cnt_1) + \min(suf[i], cnt_2) + cnt_{12}\) 就是当前位置的答案。
一直执行操作 \(1\) 或操作 \(2\)，并在经过和结束后执行操作 \(3\)，那么，\(\min(\max(cnt_1, cnt_2) + cnt_{12}, m)\) 就是该选择的答案
最后，我们取最大值即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n, m;
cin >> n >> m;
int cnt1 = 0, cnt2 = 0;
vector<bool> st(m + 1);
int cnt = 0;
for(int i=0;i<n;i++){
int cur;
cin >> cur;
if(cur == -1) cnt1 ++;
else if(cur == -2) cnt2 ++;
else if(!st[cur]) st[cur] = true, cnt ++;
}
vector<int> pre(m + 2), suf(m + 2);
for(int i=2;i<=m;i++){
pre[i] = pre[i - 1] + (st[i - 1] ? 0 : 1);
}
for(int i=m-1;i>=1;i--){
suf[i] = suf[i + 1] + (st[i + 1] ? 0 : 1);
}
int ans = min(max(cnt1, cnt2) + cnt, m);
for(int i=1;i<=m;i++){
if(st[i]) ans = max(ans, min(pre[i], cnt1) + min(suf[i], cnt2) + cnt);
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}一开始想着确定两个点，想复杂了
D1. LuoTianyi and the Floating Islands (Easy Version)
题意
给定一棵无根树，给定整数 \(n, k\)，其中 \(n\) 为节点个数，\(k\) 为标记点的个数。确定标记点放置位置后，若某些点满足到所有标记点的距离之和为所有点中最小，那么这些点符合条件。输出符合条件的点的数量的期望。
本题中，\(k_{max} = 3\)。
思路
首先，\(k = 1\) 的时候很显然，标记点能确定的位置有 \(n\) 个，当标记点被确定后，距离最小的点只可能是标记点，因此期望为 \(\frac{n}{n} = 1\)。
由此，\(k = 3\) 的时候也是这样，期望为 \(1\)。
有趣的是，当 \(k\) 为奇数时，期望均为 \(1\)，此处不给出证明。
那么，我们来考虑 \(k = 2\) 的情况：
首先，\(n\) 个点中选 \(2\) 个，很明显分母是 \(C_n^2\)。
其次，如果我们 不考虑方向，那么，对于一条边，我们可以很轻松地通过 \(Dfs\) 求出其某一方向的连通块的点的个数 \(x\)。
那么，这条边就被经过了 \(x(n-x)\) 次。
这是很显然的，但有趣的是这么一求，我们的答案偏小了。
不妨对着样例一模拟一遍，我们不难发现缺少了从 \(2, 3, 4\) 节点向 \(1\) 方向的边，这恰好就是 \(C_n^2\)。
或者说，因为距离为 \(d\) 的两点间算上端点总共有 \(d + 1\) 个点，因而这么计算，起点或者终点对应的距离肯定有一个没被计算。
那么，最后的答案就是 \(\displaystyle{\frac{\sum_{i = 1}^n dp_i(n - dp_i) + C_n^2}{C_n^2}}\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;
int qp(int a, int b) {
int res = 1;
while (b > 0) {
if (b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
int inv(int n) {
return qp(n, mod - 2);
}
void solve(){
int n, k;
cin >> n >> k;
vector<vector<int>> e(n + 1);
for(int i=0;i<n-1;i++){
int u, v;
cin >> u >> v;
e[u].pb(v), e[v].pb(u);
}
if(k % 2 == 1){
cout << 1 << '\n';
return;
}
vector<int> dp(n + 1);
auto dfs = [&](auto self, int c, int p) -> void{
dp[c] = 1;
for(auto x : e[c]){
if(x == p) continue;
self(self, x, c);
dp[c] += dp[x];
}
};
dfs(dfs, 1, 1);
int ans = 0;
for(int i=1;i<=n;i++) ans = (ans + (dp[i] * (n - dp[i]) % mod)) % mod;
ans = (ans + n * (n - 1) / 2 % mod) % mod;
ans = ans * inv(n) % mod;
ans = ans * inv(n - 1) % mod;
ans = ans * 2 % mod;
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}太抽象了