A. LuoTianyi and the Palindrome String
题意：给一个回文串，求最长的非回文子串的长度
Solution
判一下回文串是不是由相同的字母组成的，如果是的那么无解，如果不是答案就是len-1
void solve()
{
string s;cin>>s;
int len=s.length();
int sum=1;
for(int i=1;i<s.length();i++)
{
if(s[i]==s[0])sum++;
}
if(sum==len)cout<<"-1\n";
else cout<<len-1<<"\n";
}
B. LuoTianyi and the Table
题意：给一个大小为n*m的数组，将其排列成一个矩阵a，令
\[sum=\sum_{i=1}^{n}\sum_{j=1}^{n}(\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}) \]求sum最大值
Solution
有两种情况，一种是把最大值放第一个，然后把最小的两个放在它相邻的位置，另一种是把最小的放在第一个，把两个最大的放在它相邻的位置
每种情况最大/最小的两个值交换又会得到一种答案，求出来取大即可
void solve()
{
int n,m;cin>>n>>m;
for(int i=1;i<=n*m;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n*m);
int maxx1=a[n*m];
int maxx2=a[n*m-1];
int minn1=a[1];
int minn2=a[2];
int ans1=max((a[n*m]-a[1])*(m-1)*n+(a[n*m]-a[2])*(n-1),(a[n*m]-a[1])*(n-1)*m+(a[n*m]-a[2])*(m-1));
int ans2=max((a[n*m]-a[1])*(m-1)*n+(a[n*m-1]-a[1])*(n-1),(a[n*m]-a[1])*(n-1)*m+(a[n*m-1]-a[1])*(m-1));
cout<<max(ans1,ans2)<<"\n";
}
C. LuoTianyi and the Show
题意：有n个人坐m个座位，有三种坐法
1.坐在最左边的人的左边，如果第1个座位有人了，那么就离开，如果现在没有任何人坐在座位上，就选择第m个座位
2.坐在最右边的人的右边，如果第m个座位有人了，那么就离开，如果现在没有任何人坐在座位上，就选择第1个座位
3.选第x个座位，如果有人了则离开
重新进座顺序，求入座人数的最大值
Solution
分情况讨论
令答案为ans
第一种坐法人数为cnt1
第二种坐法人数为cnt2
第三种坐法的不同座位数设为num
通过题意我们可以发现，如果我们将第一种/第二种坐法放在第一位，那么第二种/第一种坐法的人必须离开了，因为它们其中一个放在第一位必定会导致第m个/第1个座位有人，此时答案有
\[ans=\max(\min(cnt1+num,m),\min(cnt2+num,m)) \]再考虑把第三种坐法放在第一位，假设第一位是x，那么后续的第一种坐法只能出现在x左边，第二种坐法只能出现在x右边
令x左边的第三种选法的人数为l，右边为r此时答案为
\[ans=\max(ans,\min(cnt1+l,x-1)+min(cnt2+r,m-x)+1) \]void solve()
{
int n,m;cin>>n>>m;
int cnt1=0,cnt2=0,cnt0=0;
set<int>st;
int l=1e18,r=-1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==-1)cnt1++;
else if(a[i]==-2)cnt2++;
else
{
st.insert(a[i]);
l=min(l,a[i]);
r=max(r,a[i]);
cnt0++;
}
}
int ans=max(min(cnt2+st.size(),m),min(cnt1+st.size(),m));
int now=1;
int len=st.size();
for(auto it:st)
{
int ll=it-1,rr=m-it;
int res=min(cnt1+now-1,ll)+min(cnt2+len-now,rr)+1;
ans=max(res,ans);
now++;
}
cout<<ans<<"\n";
}
D.LuoTianyi and the Floating Islands
题意：给出一个大小为n的树，假设上面有k个关键点，定义到k个关键点距离之和最小的点为good点，求good点的个数的期望
Solution
选出k个关键点，有C(n,k)种选法
对于奇数的情况，答案为1，我们考虑good点左右两边的关键点个数分别为l和r，那么当它移动时，距离会变化|l-r|，显然当l=r时距离最小，因为l≠r时它一定会可以变得更小，而奇数有且仅有一个点满足。
同时可以发现这样的good点会产生一条链，这样就有C(n,k)条链，因为点的个数=链的长度+1，所以答案就是(链的长度+C(n,k))/(C(n,k))
那么我们统计一下链的贡献，考虑当前子树的大小为x，那么可以从当前子树中选取k/2个，从其它n-x个点选取k/2个，得到的就是这个子树根节点和子树父节点之间的边的贡献
void dfs(int x,int pre)
{
dp[x]=1;
for(auto it:e[x])
{
if(it==pre)continue;
dfs(it,x);
dp[x]+=dp[it];
}
ans=(ans+C(dp[x],k/2)*C(n-dp[x],k/2)%mod)%mod;
}
void solve()
{
cin>>n>>k;
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
if(k&1)
{
cout<<"1\n";
return;
}
dfs(1,0);
cout<<((ans*ksm(C(n,k),mod-2))%mod+1)%mod<<"\n";
}