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

补题链接 https://codeforces.com/gym/104128
如何评价2022icpc南京站 https://www.zhihu.com/question/572113636

因为本人很菜，今天先补题补到银牌(5题)水平吧

进度(3/13)

I Perfect Palindrome

知识点:回文的性质

猜:将所有元素变成相同字母的代价。如何证明？
循环转还要每次转完都是回文的，可以知道，所有字母都要对应相同。

#include<bits/stdc++.h>

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


void solve()
{
     string x; cin >> x; int len = x.size();
     map<int,int> mp; int res = 0;
     for(int i = 0;i < len;i ++) mp[x[i] - 'a'] ++;
     for(auto k : mp) res = max(res,k.second);
     res = len - res;
     cout << res << endl;
}

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

A Stop, Yesterday Please No More

知识点:逆操作,矩阵,二维差分

首先考虑没有洞的情况。
考虑逆操作，维护边界到达过的最值。最后可以得到没有洞的情况下，剩下的老鼠矩阵。

然后考虑有洞的情况。
这个时候我们只关心剩下的老鼠矩阵在哪些位置停留过。
每次移动，考虑剩下的老鼠矩阵。
枚举左上端点，如果没有重合，说明每一个老鼠和每一个位置都没有对应重合过。
考虑二维查分，维护一下每个位置到达过的老鼠数量。

最后统计格子上数量等于剩下老鼠数量减去要求剩下的老鼠数量的格子数量即可。

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

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

const int N = 1e3 + 10;

int n,m,k;
int l,r,u,d;
int lnow,rnow,unow,dnow;
bool st[N][N];
int mp[N][N];
int res;


void pr()
{
  cout << u << ' ' << d << ' ' << l << ' ' << r << endl;  
}

void init()
{ 
  l = lnow = u = unow = 1;
  r = rnow = m;
  d = dnow = n;
  memset(st,false,sizeof st);
  memset(mp,0,sizeof mp);
  res = 0;
}

void add(int x,int y,int p,int q)
{
  if(st[x][y]) return; st[x][y] = true;
  mp[x][y] ++, mp[p+1][y] --, mp[x][q+1] --, mp[p+1][q+1] ++;
}

void solve()
{
  cin >> n >> m >> k;
  string s;cin >> s;

  init();

  for(int i = 0;i < s.size();i ++)
  {
     if(s[i] == 'U') dnow --, unow--,d = min(d,dnow);
     if(s[i] == 'D') dnow ++, unow++,u = max(u,unow);
     if(s[i] == 'L') lnow ++, rnow++,l = max(l,lnow);
     if(s[i] == 'R') lnow --, rnow--,r = min(r,rnow);
  }
 // pr();
  if(u > d || l > r){
    if(k == 0) cout << n*m << '\n';
    else cout << "0" << endl;
    return;
  }
  int delta = (d - u + 1) * (r - l + 1) - k;

  add(u,l,d,r);
  for(int i = 0;i < s.size();i ++)
  {
     if(s[i] == 'U') u ++,d++;
     if(s[i] == 'D') u --,d--;
     if(s[i] == 'L') l --,r--;
     if(s[i] == 'R') l ++,r++;
     add(u,l,d,r);
  }
  for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++) 
  mp[i][j] += (mp[i-1][j] + mp[i][j-1] - mp[i-1][j-1]);
  for(int i = 1; i <= n;i ++) for(int j = 1; j <= m;j ++)
  if(mp[i][j] == delta) res ++;
  cout << res << endl;
}

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

G Inscryption

知识点: 模拟,贪心,反悔,数学

一开始，我没有想到顺序关系，wa了2发。
后来发现，这题和顺序关系很大，必须按顺序贪心模拟。

#include <bits/stdc++.h>
using namespace std;


int n;

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

inline int gcd(int a,int b) 
{    
    while(b^=a^=b^=a%=b);    
    return a;
}

void solve() {
    scanf("%d", &n);

    int s = 1, c = 1, t = 0;
    bool failed = false;

    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);

        if (x == 1) s++, c++;

        else if (x == -1) {

            if (c > 1) c--;

            else if (t >= 1) t--, s++, c++;

            else failed = true;
        } else {

            if (c > 1) t++, c--;
            else s++, c++;
        }
    }
    if (failed) printf("-1\n");
    else {
        int g = gcd(s, c);
        printf("%d %d\n", s / g, c / g);
    }
}

int main() {
    //fileio();
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}

知乎评价

最后1个队11题，5个队9题，7个队8题，14个队7题，41个队6题，32个队5题，62个队4题，105个队3题，140个队2题，57个队1题。铜线如同预测是3题，银线是5题加上10个4题（其实原本期望能完全收入5题线的），金牌是7题加上10个6题（同样也是期望能完全收入7题线）。冠亚季原本期望至少有一个10题，结果被逆十字打出了n+2，而且HL都无人通过。感觉主要还是这次比赛大家收到的debuff太强了，稍微和预测有一些偏差。

作者：陈靖邦
链接：https://www.zhihu.com/question/572113636/answer/2800844540
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。