此篇属于CodeForces比赛题解集合链接

比赛地址
https://codeforces.com/contest/1825

cn场 洛天依哇哇哇

补题！今天补完！

A

找最大的不是回文串的子串长度。
一想，只可能是len - 1 或者 -1

#include<bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;
int T;


string s;

void solve()
{
   cin >> s;
   bool f = false;
   for(int i = 0;i < s.size();i ++)
   if(s[i] != s[0]) f = true;
   if(!f) {cout << "-1" << endl;return;}
   int len = s.size(); cout << len - 1 << endl;
}

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  T = 1;
  cin >> T;
  while(T--)
  solve();
}

B

统计所有以（zero point）为起点的子矩阵 中 最大值与最小值的差 的sum。

我们只需要找到最大的 delta 和 第二大的 delta 放在开头 贪一下就出来了。

具体看代码。

咕咕咕咕

#include<bits/stdc++.h>
#define int long long

using namespace std;
void fileio()
{
  //#ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  //#endif
}

int n,m;
const int N = 1e4 + 10;
int a[N];
void solve()
{
   cin >> n >> m; int len = n * m;
   for(int i = 0;i < len;i ++) cin >>a[i]; sort(a, a + len);
   int maxdel = a[len - 1] - a[0];
   int semaxdel = 0; //int zeropoint = 0;
   if(a[len - 2] - a[0] < a[len - 1] - a[1]) semaxdel = a[len-1] - a[1];
   else semaxdel = a[len-2] - a[0];
   int cntf = 0; int cnts = 0;
   if((n-1)*m < (m-1)*n) cntf = (m-1)*n, cnts = n-1;
   else cntf = (n-1)*m, cnts = m-1;
   cout << maxdel*cntf + semaxdel * cnts << endl;
   return;
}

signed main()
{
    //fileio();
    ios::sync_with_stdio(false);
      cin.tie(0);
    int tc = 1; cin >> tc;
    for(int i = 0;i < tc;i ++)solve();
}

C

第一种坐法 坐在最左的人的左边，没有人就坐在最右边
第二种坐法 坐在最右的人的右边，没有人就坐在最左边
第三种坐法 直接坐在 xi 位置上

你可以调整人的入场顺序，尽量让最多的人入座

我们会发现，第一个人很关键。
第一个人如果是第一种坐法，第二种就没法坐了。反之也对。

我们枚举第一个人是上面的三种坐法。

其中第三种坐法需要更深入的讨论。

第三种的讨论使用差分数组，左右差分一下就好。

咕咕咕咕，看代码，不懂的可以私我。

#include<bits/stdc++.h>
#define int long long
#define debug cout << "debug" << endl

using namespace std;
void fileio()
{
  //#ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  //#endif
}

int n,m;
const int N = 1e5 + 10;
int l[N],r[N];
int logs[N];

void pr()
{
    for(int i = 1;i <= m;i ++) cout << l[i] << ' '; cout << endl;
    for(int i = 1;i <= m;i ++) cout << r[i] << ' '; cout << endl;
}

void solve()
{
    //debug;
    cin >> n >> m; 
    for(int i = 0;i < m + 5;i ++) l[i] = r[i] = logs[i] = 0; 
    l[0] = -1; r[m+1] = -1;
    int lcnt = 0; int rcnt = 0;int midcnt = 0;int res = 0;
    set<int> pos;// pr();
   for(int i = 0;i < n;i ++)
   {
     int x; cin >> x;
     if(x == -1) lcnt ++;
     if(x == -2) rcnt ++;
     if(x > 0) pos.insert(x), logs[x] = -1;
   }
   midcnt = pos.size();
  // pr();
   for(int i = 1;i <= m;i ++) l[i] += (l[i-1] + 1 + logs[i-1]);
   for(int i = m;i >= 1;i --) r[i] += (r[i+1] + 1 + logs[i+1]);  //pr();
   for(int i : pos){

        int lres = min(lcnt,l[i]); int rres = min(rcnt,r[i]);
        res = max(res, lres + rres + midcnt);
        //cout << i << " ** " << res << endl;
   } 
    res = max(res,lcnt + midcnt); res = max(res, rcnt + midcnt);
    res = min(res,m);
    cout << res  << endl;
}

signed main()
{
    //fileio();
    ios::sync_with_stdio(false);
      cin.tie(0);
    int tc = 1; cin >> tc;
    for(int i = 0;i < tc;i ++)solve();
}

D1

题意看的有点懵。

有n个岛，连成一棵树，选了k个岛屿。取遍所有k个岛屿的情况。

对于每个情况，再取遍 n 个岛屿，对于每个岛屿，计算距离k个岛屿的距离和。

每个情况下， 好岛就是距离和最小的岛屿。

求平均每个情况有多少好岛？ 然后moudle 一下。

懵！一脸懵b

好在 k 只有 1 2 3 这几种情况

k == 1 的话 每种情况，好岛就是自己 所以答案是1
k == 3 的话 在树上选的那三个岛 一定能找出一条链来，然后可以证明 好岛就是中间那个岛。
k == 2 怎么办？ 不会，寄
但我好像有懂了： k == 2 的话，直接将两个点连起来，路上的所有的岛都是好岛。
ok，那怎么求全部的好岛？

那么我们反过来，对于给定一个岛，它是好岛的情况有多少？就是要在树上枚举经过它的区间。

这个区间要经过这个岛，一想，我去，就是这个岛是根结点，然后它的所有子树的大小 siz(i) 乘起来

然后一看，要枚举每个点为顶点，再扫一遍，n方，寄

看看题解，这个dfs，绝杀哇，直接解决这个问题，绝杀，还有这个公式，稍微推一下，绝杀

#include<bits/stdc++.h>
#define int long long

using namespace std;
void fileio()
{
  //#ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  //#endif
}
const int mod = 1e9 + 7;

int quick_pow(int a,int b)
{
    int res = 1;
    while(b)
    {
        if(b&1) res = res % mod * a % mod;
        a = a % mod * a % mod, b >>= 1;
    }
    return res;
}

const int N = 2e5 + 10;

vector<int> g[N];
int n,k;
int siz[N],w[N];

void dfs(int u,int fa)
{
    siz[u] = 1;
    for(int i : g[u])
    {
        if(i != fa){
            dfs(i, u);
            siz[u] += siz[i];
            w[u] += siz[i]*siz[i]%mod;
            w[u] %= mod;
        }
    }
     (w[u]+=(n-siz[u])*(n-siz[u])%mod)%=mod; //  逆根方向 // 绝杀
}

void solve()
{
   cin >> n >> k;
   for(int i = 1;i < n;i ++){
    int u,v; cin >> u >> v; g[u].push_back(v);g[v].push_back(u);
   }
   if(k & 1){ cout << 1 << endl; return;}
   dfs(1,0); int res = 0;
   for(int i = 1;i <= n;i ++)
   {
      res += (((n-1)*(n-1)%mod-w[i]+mod)%mod)*quick_pow(2,mod-2)%mod;
      res %= mod;
   }
   cout << (res%mod*quick_pow(n*(n-1)/2%mod,mod-2)%mod + 2)%mod << endl;

}

signed main()
{
    fileio();
    ios::sync_with_stdio(false);
      cin.tie(0);
    int tc = 1; //cin >> tc;
    for(int i = 0;i < tc;i ++)solve();
}