首页 > 其他分享 >2022 China Collegiate Programming Contest (CCPC) Guilin Site

2022 China Collegiate Programming Contest (CCPC) Guilin Site

时间：2022-11-03 16:34:39浏览次数：86  
标签：return Contest int Guilin Site const modint define first

2022 China Collegiate Programming Contest (CCPC) Guilin Site

A Lily

签到题。

直接暴力，求一下对于每个点附近是不是有L，没有就.

C. Array Concatenation

分析

思路1：

可以发现，复制一个 \(reverse\) 版的操作只有第一次执行有用，因为执行一次之后数组就变成回文串了，此时操作1和操作2是等效的；因此只需要枚举操作2执行的位置即可；

不妨令数组的二阶前缀和为 \(T\), 前缀和为 \(S\)，那么对于执行一次操作1后数组的二阶前缀和 \(T'\) , 前缀和 \(S'\)，数组长度 \(n'\) 有：

\(T'= 2 T + n S, S’ = 2 S, n'=2n\)

维护一个数组反的二阶前缀和 \(H\), 那么对于执行一次操作2后有：

\(T' = T + n \times S + H\)

考虑初始的数组二阶前缀和为 \(T_0\)，前缀和为\(S_0\), 数组长度为\(n_0\)，那么执行 \(k\) 次操作1后，数组的二阶前缀和 \(T_k\) 有

\(T_k = 2^kT_0 + 2^{k-1}(2^k-1)n_0S_0\)

可以顺序维护操作的结果，对于执行一次操作二后直接求出最后的结果，求出 \(ans\)

时间复杂度为 \(O(klogk)\)

思路2：

对于维护的逆序二阶前缀和 \(H_0\), 执行 \(x\) 次操作1后有：

\(H_x = 2^xH_o+2^{k-1}(2^k-1)n_0S_0\)

由思路1：\(T_x = 2^xT_0 + 2^{x-1}(2^x-1)n_0S_0\)

那么此时执行操作2有：

\(T_{x+1} = 2^x(T_0+H_0)+2\times 2^{x-1}(2^x-1)n_0S_0 + 2^{x}\times 2^{x} n_0S_0=2^x(T_0+H_0) + 2^{x + 1 - 1}(2^{x+1}-1)n_0S_0\)

因此只要执行了操作2，都有：

\(T_k=2^{k-1}(T_0+H_0) + 2^{k-1}(2^k-1)n_0S_0\)

而没有执行操作2，都有：

\(T_k = 2^kT_0 + 2^{k-1}(2^k-1)n_0S_0\)

因此只需要比较这两个即可。

AC_code

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

#define pb push_back
#define eb emplace_back
#define maxe max_element
#define mine min_element
#define ay2 array<int, 2>
#define ay3 array<int, 3>
#define PII pair<int, int>
#define SZ(a) ((int)a.size()) 
#define all(v) v.begin(), v.end()
#define Rep(i, a, b) for (int i(a); i < b; ++ i ) 
#define rep(i, a, b) for (int i(a); i <= b; ++ i ) 
#define dec(i, a, b) for (int i(b); i >= a; -- i ) 

#ifdef LOCAL
#include <debugger>
#else
#define debug(...) 42
#endif

template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }

// mt19937 rnd(random_device{}()); 
mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x) { return mrand() % x;}

constexpr int INF = 0x3f3f3f3f;
constexpr ll inf = 1E18;
constexpr int P = 1E9 + 7;



constexpr int MOD =  1E9 + 7;

inline int mod(int x) {return x >= MOD ? x - MOD : x;}

inline int ksm(int a, int b) {
  int ret = 1; a = mod(a);
  for(; b; b >>= 1, a = 1LL * a * a % MOD) if(b & 1) ret = 1LL * ret * a % MOD;
  return ret;
}

template<int MOD> 
struct modint {
  int x;
  modint() {x = 0; }
  modint(int y) {x = y;}
  inline modint inv() const { return modint{ksm(x, MOD - 2)}; }
  explicit inline operator int() { return x; }
  friend inline modint operator + (const modint &a, const modint& b) { return modint(mod(a.x + b.x)); }
  friend inline modint operator - (const modint &a, const modint& b) { return modint(mod(a.x - b.x + MOD)); }
  friend inline modint operator * (const modint &a, const modint& b) { return modint(1ll * a.x * b.x % MOD); }
  friend inline modint operator / (const modint &a, const modint& b) { return modint(1ll * a.x * b.inv().x % MOD); }
  friend inline modint operator + (const modint &a, const int& b) { return modint(mod(a.x + b)); }
  friend inline modint operator - (const modint &a, const int& b) { return modint(mod(a.x - b + MOD)); }
  friend inline modint operator * (const modint &a, const int& b) { return modint(1ll * a.x * b % MOD); }
  friend inline modint operator / (const modint &a, const int& b) { return modint(1ll * a.x * ksm(b, MOD - 2) % MOD); } 
  friend inline modint operator - (const modint &a) { return modint(mod(MOD - a.x)); }
  friend inline modint& operator += (modint &a, const modint& b) { return a = a + b; }
  friend inline modint& operator -= (modint &a, const modint& b) { return a = a - b; }
  friend inline modint& operator *= (modint &a, const modint& b) { return a = a * b; }
  friend inline modint& operator /= (modint &a, const modint& b) { return a = a / b; }
  friend inline modint& operator += (modint &a, const int& b) { return a = a + b; }
  friend inline modint& operator -= (modint &a, const int& b) { return a = a - b; }
  friend inline modint& operator *= (modint &a, const int& b) { return a = a * b; }
  friend inline modint& operator /= (modint &a, const int& b) { return a = a / b; }
  friend auto &operator >> (istream &i, modint &a) {return i >> a.x; }
  friend auto &operator << (ostream &o, const modint &z) { return o << z.x; }
  inline bool operator == (const modint &b) { return x == b.x; }
  inline bool operator == (const int &b) { return x == b; }
  inline bool operator != (const modint &b) { return x != b.x; }
  inline bool operator != (const int &b) { return x != b; }
  inline bool operator < (const modint &a) { return x < a.x; }
  inline bool operator < (const int &b) { return x < b; }
  inline bool operator <= (const modint &a) { return x <= a.x; }
  inline bool operator <= (const int &b) { return x <= b; }
  inline bool operator > (const modint &a) { return x > a.x; }
  inline bool operator > (const int &a) { return x > a; }
  inline bool operator >= (const modint &a) { return x >= a.x; }
  inline bool operator >= (const int &a) { return x >= a; }
  operator int() const {
    return x;
  }
  // inline void
};

typedef modint<MOD> mint;

inline mint ksm(mint a, int b, mint ret = 1) {
  for (; b; b >>= 1, a = a * a) if (b & 1) ret = ret * a; 
  return ret;
}

const int N = 2e5 + 10;
int n, m;
ll a[N], sa[N], ssa[N];
ll b[N], sb[N], ssb[N];
mint fact[N + 1], infact[N + 1], inv[N + 1];

void init() {
  fact[0] = 1; for(int i = 1; i <= N; ++ i ) { fact[i] = fact[i - 1] * i; }
  infact[N] = ksm(fact[N], MOD - 2); for(int i = N - 1; i >= 0; -- i ) infact[i] = infact[i + 1] * (i + 1);
  inv[0] = inv[1] = 1; for(int i = 2; i <= N; ++ i) inv[i] = inv[MOD % i] * (MOD - MOD / i);
}

mint C(int a, int b) {
  if (a < b) return 0;
  return fact[a] * infact[b] * infact[a - b];
}

void solve() {

  fact[0] = 1;

  Rep(i, 1, N) fact[i] = (fact[i - 1] * 2) % P;

  cin >> n >> m;
  rep(i, 1, n) cin >> a[i];
  rep(i, 1, n) sa[i] = (sa[i - 1] + a[i]) % P;
  rep(i, 1, n) ssa[i] = (ssa[i - 1] + sa[i]) % P;
  rep(i, 1, n) b[i] = a[n - i + 1];
  rep(i, 1, n) sb[i] = (sb[i - 1] + b[i]) % P;
  rep(i, 1, n) ssb[i] = (ssb[i - 1] + sb[i]) % P;
  
  mint S = sa[n], T1 = ssa[n], T2 = ssb[n];

  mint _n = n;
  mint ans = fact[m] * T1 + fact[m - 1] * (fact[m] - 1) * S * _n;

  rep (i, 1, m) {
    mint _T = T1 + T2 + S * _n;
    mint _S = S;
    mint __n = _n;
    S *= 2;
    _n *= 2;
    mint nm = m - i;
    mint ret = _T;
    // cout << ret << "\n";
    if (nm != 0) {
      ret = fact[nm] * _T + fact[nm - 1] * (fact[nm] - 1) * S * _n;
    }
    ans = max(ans, ret);
    S = _S;
    _n = __n;
    T1 =  T1 * 2 + S * _n;
    T2 = T2 * 2 + S * _n;
    S *= 2;
    _n *= 2;
  }
  cout << ans;


  
  
}

int main() {
  ios::sync_with_stdio(false); 
  cin.tie(nullptr); 
  int T = 1;// cin >> T;
  while (T --) solve();
  return 0;
}

E Draw a triangle

分析

我们设\(\vec{AB} = (u,v),\vec{AC} = (x,y)\)，其中AB已知，而AC未知，我们利用叉乘计算三角形面积。

求三角形面积\(S = \frac{1}{2}|\vec{AB}\times\vec{AC}|\)，我们可也得到一个式子\(S = \frac{1}{2}|uy-vx|\)，则式子内部是一个我们很熟悉的二元的不定方程了，根据裴蜀定理，该式子的最小值为gcd(u,v)。因此我们的问题转化了，变为求\(uy-vx=gcd(u,v)\)的一组合法解。

但是，这里有一些问题，可能对不定方程了解不够好的人不太友善。我们注意到说uy-vx，中间是个减法，我们可以按照uy+vx去进行计算，最后将答案中的x取反即是uy-vx的一个解。

#include <bits/stdc++.h>
#define fi first    
#define se second    
#define endl '\n'
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using ll = long long;
using namespace std;
const int N = 1e5 + 10,M = N*2;
   
template <class T>
T exgcd(T a, T b, T& x, T& y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    T d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

//ay - bx = d;
//y = y3 - y1 x = x3 - x1
void solve() {
    ll x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
    ll a = x2 - x1,b = y2 - y1;
    ll x,y;
    exgcd(a,b,y,x);
    x = -x;
    cout<<x + x1<<" "<<y + y1<<'\n';
}
 
int main() 
{
    ios;
    int T=1;
    cin>>T;

    while(T -- ) {
        solve();
    }
 
    return 0;
}

G. Group Homework

题意

在树上找到两条简单路径，最大化两条路径上的不被重复经过的点的权值和。

分析

首先两条路径可以分为两种情况，相交和不相交

  • 两条路径不相交

    问题转化为断开某一条边，求分开的两个树的最长带权直径的和的最大值
    此时需要求出以每个点为根树的所有儿子的最长链、次长链、次次长链，用 pair<ll, int> h[u][0/1/2] 来表示，两维分别表示路径和以及所在的儿子，通过换根 \(DP\) 可以解决这个问题。

    对于以某一个点为根的树的直径可以分为两种情况：包不包含根节点。

    对于断开某一条链 u ->v，假设 \(u\) 是 \(v\) 的父亲，其实可以想象成 \(u\) 把 \(v\) 这个儿子舍弃后的最长直径。

    不妨设 \(u\) 两种情况的最大值为 dp[u] ，

    • 包含当前节点的直径

      这个非常容易求出，对于 \(u\) ，只需要找到儿子不是 \(v\) 的前二大链长，然后加上 \(u\) 的权值即可，设这个值为 g[u] 。 \(v\) 同理。

    • 不包含当前节点的直径

      由于 \(v\) 是 \(u\) 的儿子，那么 \(v\) 的子树中不包含 \(u\) 的直径可以通过 树形 \(DP\) 求出，设这个值为 F[u] ；
      下面考虑 \(u\) ，如果 \(u\) 的父亲 \(fa\) 不是 \(0\)，那么 dp[u] 是可以从 dp[fa]​ 转移过来的； 它还可以从 F[u] 中转移而来，由于 F[u] 是可能从 \(v\) 转移过来，因此我们需要记录 最大和次大， 即 f[u][0/1] 。

  • 两条路径相交

    首先是个结论，两条路径最多只有一个交点。那么考虑枚举交点 \(u\) ，然后找到 \(u\) 所有儿子 \(v\) 的前 4 长链即可，可以利用 h[v] 来解决。

AC_code

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

#define pb push_back
#define eb emplace_back
#define maxe max_element
#define mine min_element
#define ay2 array<int, 2>
#define PII pair<int, int>
#define FUCK debug("fuck")
#define SZ(a) ((int)a.size()) 
#define all(v) v.begin(), v.end()
#define Rep(i, a, b) for (int i(a); i < b; ++ i ) 
#define rep(i, a, b) for (int i(a); i <= b; ++ i ) 
#define dec(i, a, b) for (int i(b); i >= a; -- i ) 

#ifdef LOCAL
#include <debugger>
#else
#define debug(...) 42
#endif

template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }

// mt19937 rnd(random_device{}()); 
mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x) { return mrand() % x;}

constexpr int INF = 0x3f3f3f3f;
constexpr ll inf = 1E18;
// constexpr int N = 2E5 + 10;

void solve() {
  int n; cin >> n;
  vector<ll> w(n + 1);
  rep(i, 1, n) cin >> w[i];
  vector<vector<int>> son(n + 1);
  for (int i = 1; i < n; i++ ) {
    int u, v; cin >> u >> v;
    son[u].push_back(v), son[v].push_back(u);
  } 

  ll ans = 0;
  
  vector h(n + 1, vector<pair<ll, int> > (3));
  //h[i][j] 表示 以 i 为根的子树的最长链 or 次长链 的 权值和 和 编号
  //需要换根

  vector<ll> f(n + 1); //子树的最长带权直径 两种的最大值

  vector<ll> dp(n + 1);
  //表示除了点 u 的子树中的点所构成的最长带权直径，那么考虑这个直径的构成方式，两种取个最大值。
  vector g(n + 1, vector<pair<ll, int> > (2));
  vector F(n + 1, vector<pair<ll, int> > (2));
  

  /**
   * 以 1 为根的子树中，u 的子树中的最长带权直径长度
   * 并且此时的直径是由 不包含 u 的路径(即由 u 的子树中的点)构成。
   * g[u][0] 表示最长直径和这个值所在的儿子的编号， g[u][1] 为次长。
  */

  function<void(int, int)> dfs = [&] (int u, int fa) {
    for (int &v: son[u]) if (v != fa) {

      dfs (v, u);

      if (h[v][0].first >= h[u][0].first) {
        h[u][2] = h[u][1];
        h[u][1] = h[u][0];
        h[u][0] = {h[v][0].first, v};
      } else if (h[v][0].first >= h[u][1].first) {
        h[u][2] = h[u][1];
        h[u][1] = {h[v][0].first, v};
      } else if (h[v][0].first >= h[u][2].first) {
        h[u][2] = {h[v][0].first, v};
      } 

      ll mx = max(f[v], g[v][0].first);
      if (f[v] >= F[u][0].first) {
        F[u][1] = F[u][0];
        F[u][0] = {f[v], v};
      } else if (f[v] >= F[u][1].first) {
        F[u][1] = {f[v], v};
      }
      if (mx >= g[u][0].first) {
        g[u][1] = g[u][0];
        g[u][0] = {mx, v};
      } else if (mx >= g[u][1].first) {
        g[u][1] = {mx, v};
      }

    }

    chkmax(f[u], w[u] + h[u][0].first + h[u][1].first);

    h[u][0].first += w[u];
    h[u][1].first += w[u];
    h[u][2].first += w[u];

    chkmax(ans, g[u][0].first + g[u][1].first);
  };
  
  dfs(1, 0);

  function<void(int, int)> DFS = [&] (int u, int fa) {
    
    for (int &v: son[u]) if (v != fa) {
      ll now = h[u][0].second == v ? h[u][1].first : h[u][0].first;
      now += w[v];
      if (now >= h[v][0].first) {
        h[v][2] = h[v][1];
        h[v][1] = h[v][0];
        h[v][0] = {now, u};
      } else if (now >= h[v][1].first) {
        h[v][2] = h[v][1];
        h[v][1] = {now, u};
      } else if (now >= h[v][2].first) {
        h[v][2] = {now, u};
      }

      DFS(v, u);
    }
  };

  DFS(1, 0);

  function<void(int, int)> dfs1 = [&] (int u, int fa) {
    if (son[u].empty()) return ;
    vector<pair<ll, pair<int, int> > > a;
    /////////////////////////// 选当前点 u 的四条链，需要保证链不是从 u 转移过来的
    for (int &v: son[u]) {
      if (h[v][0].second != u) {
        a.push_back(make_pair(h[v][0].first, make_pair(h[v][0].second, v)));
      } else {
        a.push_back(make_pair(h[v][1].first, make_pair(h[v][1].second, v)));
      }
      // if (v != fa) chkmax(dp[v], dp[u]);
    }
    
    sort(all(a), greater<pair<ll, pair<int, int> > >());

    int m = min(SZ(a), 4); ll now = 0;
    Rep(i, 0, m) now += a[i].first;

    chkmax(ans, now);
    /////////////////////////// 选当前点的四条链


    ///////////////////////////选当前点 和 三条链
    chkmin(m, 3);
    now = w[u];
    Rep(i, 0, m) {
      now += a[i].first;
    } 
    chkmax(ans, now);
    
    ///////////////////////////选当前点 和 三条链
    //需要知道以 u 为根的树中，每个儿子的子树中的最大直径，取前二大
    
    // g[u][0], g[u][1],   all(f[v])  以及从父亲那边转移过来的 取前2大
    //父亲那边转移过来的假设是dp[u]

    if (fa) {
      ll now = 0; int cnt = 0;
      Rep(i, 0, 3) if (cnt < 2 && h[u][i].second != fa) {
        now += h[u][i].first - w[u];
        ++ cnt;
      }
      now += w[u];

      ll Now = 0; int Cnt = 0;
      Rep(i, 0, 3) if (Cnt < 2 && h[fa][i].second != u) {
        Now += h[fa][i].first - w[fa];
        ++ Cnt;
      }
      Now += w[fa];
      chkmax(ans, Now + now);
    }



    vector<ll> tmp{g[u][0].first, g[u][1].first};

    if (fa) {
      auto [val0, idx0] = h[fa][0];
      auto [val1, idx1] = h[fa][1];
      auto [val2, idx2] = h[fa][2];
      set<int> s{idx0, idx1, idx2}; 
      vector<ll> fuck;
      auto flag = s.count(u);
      if (!flag) {
        tmp.push_back(val0); tmp.push_back(val1);
        fuck.push_back(val0); fuck.push_back(val1);
      } else {
        Rep(i, 0, 3) {
          auto [val, idx] = h[fa][i];
          if (idx != u) {
            tmp.push_back(val);
            fuck.push_back(val);
          }
        }
      }
      sort(all(fuck), greater<ll>());
      //父亲的儿子的子树中的最大直径
      dp[u] = max(dp[fa], g[fa][0].second == u ? g[fa][1].first : g[fa][0].first);
      //父亲和父亲的另外两个儿子组成的链
      chkmax(dp[u], fuck[0] + fuck[1] - (fuck[0] != 0 && fuck[1] != 0) * w[fa]);

      ll mx = F[u][0].first + F[u][1].first;
      chkmax(mx, max(g[u][0].first, F[u][0].first) + dp[u]);
      if (g[u][0].second != F[u][0].second) {
        chkmax(mx, g[u][0].first + F[u][0].first);
      } else {
        chkmax(mx, g[u][0].first + F[u][1].first);
        chkmax(mx, g[u][1].first + F[u][0].first);
      }
      chkmax(ans,  mx);

    }

    for (int &v: son[u]) if (v != fa) {
      dfs1(v, u);
    }
    
  };

  dfs1(1, 0);

  cout << ans << "\n";
}
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(nullptr); 
  int T = 1; //cin >> T;
  while (T --) solve();
  return 0;
}

L. Largest Unique Wins

分析

纳什均衡：对于某个选手，无论他怎么更换操作都不会使他的得分期望更优。

那么只需要让大于他选择的数都有两个人选择，有两种情况：

  1. 他选的数只有他自己选，那么他的得分期望是1，无需更换；
  2. 他选的数有两个人选：
    1. 如果没有人获胜，那么他的得分期望是0，如果他选择别的数字，那么会使和他选一样数的人获胜，使他的得分期望降到-1；
    2. 如果有人获胜，那么他的得分期望是-1，如果他选择别的数字，那么和他选一样数的人会获胜，他的得分期望不会更优；

那么只需要 \(m, m, m-1,m-1 \dots\) 这样选即可

当 \(n \ge 2m\) 所有人都不会赢，所以保证每个数都有两个人选，其余的随便选即可

AC_code

#include <bits/stdc++.h>
#include <iomanip>
#include <ios>
#include <set>
#define int long long
using namespace std;
#define all(x) (x).begin(),(x).end()
typedef long long LL;
typedef pair<int, int> PII;

void solve() {
    int n, m; cin >> n >> m;
    int t = m;
    for(int i = 1; i <= n; i ++){
        if(!t){
            for(int j = 1; j <= m; j ++){
                if(j == 1){
                    cout << "1.0000000000 ";
                }
                else cout << "0.0000000000 ";
            }
            continue;
        }
        for(int j = 1; j <= m; j ++){
            if(j == t){
                cout << "1.0000000000 ";
            }
            else cout << "0.0000000000 ";
        }
        if(i % 2 == 0) t --;
        cout << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

M. Youth Finale

题意

给定一个排列 \(a\) ， \(q\) 次操作，求出每次操作后的冒泡排序的次数，对 \(10\) 取模。

操作有两种：

  1. 将整个数组翻转
  2. 将第一个数字放到最后一个位置

分析

首先考虑如果每次询问独立，应该怎么算？ 假设操作前的答案为 ans

  1. 将整个序列翻转，原来的正序对变为逆序对，逆序对变为正序对，那么操作后的逆序对数是 \(n \times (n - 1) / 2 - ans\) 。
  2. 由于序列是一个排列，那么把一个数字 \(x\) 从开头移除，减少的逆序对数就是 \(x - 1\)，然后放到末尾，增加的逆序对数就是 \(n - x\)。

发现两种操作都是可以 \(O(1)\) 计算的，并且只需要知道开头和末尾的数字，以及序列的方向。因此我们可以用数组模拟一个双端队列，模拟操作即可。

AC_code

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

#define pb push_back
#define eb emplace_back
#define maxe max_element
#define mine min_element
#define ay2 array<int, 2>
#define ay3 array<int, 3>
#define PII pair<int, int>
#define SZ(a) ((int)a.size()) 
#define all(v) v.begin(), v.end()
#define Rep(i, a, b) for (int i(a); i < b; ++ i ) 
#define rep(i, a, b) for (int i(a); i <= b; ++ i ) 
#define dec(i, a, b) for (int i(b); i >= a; -- i ) 


constexpr int N = 5E6 + 10;
constexpr int mid = 1E6 + 10;
int n, m;
int q[N];

class fenwick {
public:
  vector<int> fenw;
  int n;
  fenwick(int _n): n(_n) {
    fenw.resize(n);
  }
  void modify(int x, int v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
  int get(int x) {
    int v = 0;
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
  int get(int l, int r) {
    return get(r) - get(l - 1);
  }
};

void solve() {
  cin >> n >> m;
  
  rep(i, 1, n) cin >> q[i + mid];
  int hh = 1 + mid, tt = n + mid;
  int flag = 1; // left

  string s; cin >> s;

  fenwick fen(n + 20);

  ll ans = 0;

  rep(i, 1, n) {
    ans += fen.get(n + 1) - fen.get(q[i + mid]);
    fen.modify(q[i + mid], 1);
  }

  vector<int> res(m);

  ll sum = 1ll * n * (n - 1) / 2;

  cout << ans << "\n";

  Rep(i, 0, m) {
    if (s[i] == 'S') {
      if (flag) {
        int now = q[hh ++ ];
        q[++ tt] = now;
        ans -= now - 1;
        ans += n - now;
      } else {
        int now = q[tt --];
        q[-- hh] = now;
        ans -= now - 1;
        ans += n - now;
      }
      res[i] = ans % 10;
    } else if (s[i] == 'R') { 
      flag ^= 1;
      ans = sum - ans;
      res[i] = ans % 10;
    } else {
      assert(false);
    }
  }
  Rep(i, 0, m) {
    cout << res[i];
  }


}

int main() {
  ios::sync_with_stdio(false); 
  cin.tie(nullptr); 
  int T = 1; //cin >> T;
  while (T --) solve();
  return 0;
}

标签：return,Contest,int,Guilin,Site,const,modint,define,first
From： https://www.cnblogs.com/aitejiu/p/16854907.html

相关文章

  • AtCoder Regular Contest 065
    ARC064C,E都是简单题，D猜结论也没啥意思，就不写了。ARC065还是比较好的。D-Connectivity给定\(n\)个点的无向图，有两组连边，互相独立。询问每个点通过两组连边都......
  • AtCoder Regular Contest 136 D Without Carry
    AtCoder传送门洛谷传送门一眼。将\(a\)中每个数用前导零补到\(6\)位，题目相当于问所有\(i,j\)，\(a_i\)的每一位加\(a_j\)的这一位都不超过\(9\)的\((i,j)\)......
  • The 2021 ICPC Asia Shanghai & Shenyang Regional Contest
    赛前练习。上海站沈阳站[L]分析：容斥+树形DP。但是一开始想DP是\(O(n^3)\)的，于是想用NTT优化成\(O(n^2logn)\)，但是还是T了。后来看题解，发现没有注意到转移时只......
  • Sitemap的重要性
    网站地图的使用方法网站地图文件使用最多的是向搜索引擎提交网站的网址列表。像百度在站长工具中，可以把自己的网站的sitemap.xml的网站地图URL提交上去，这样百度的蜘蛛就可以......
  • 2022 Shanghai Collegiate Programming Contest
    比赛链接：https://codeforces.com/gym/103931A.AnotherA+BProblem题意：给定一个等式和等式每个位置对应的颜色。如果颜色是绿色，那答案的这一位也要是这个字符。如果......
  • Atcoder Beginner Contest 273(A~E+G)
    E场上想麻烦了，调根号分治浪费了点时间；F涉及后缀数组，还没有系统学；G场上没来的及看，也沾点数学，估计场上也想不到（不好，不好。赛时A神笔数组求和；B迷你模拟；C分别找到奇......
  • 2022 China Collegiate Programming Contest (CCPC) Guilin Site
    比赛链接2022ChinaCollegiateProgrammingContest(CCPC)GuilinSiteC.ArrayConcatenation给定一个长度为\(n\)的数组\(b_i\)，有两种操作变换：\(b^{\prime}=\l......
  • [Leetcode Weekly Contest]317
    链接：LeetCode[Leetcode]2455.可被三整除的偶数的平均值给你一个由正整数组成的整数数组nums，返回其中可被3整除的所有偶数的平均值。注意：n个元素的平均值等于n个......
  • The 2021 ICPC Asia Shenyang Regional Contest
    The2021ICPCAsiaShenyangRegionalContest我们按难易程度来，E,F<B,J<H,I,L,ME.EdwardGaming,theChampion直接输出edgnb子字符串数量。F.EncodedStringsI分......
  • Team Extra Contest 2022-10-21补题
    D.38parrots线段树#include<bits/stdc++.h>usingnamespacestd;#defineIOSios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)#definerep(a,b......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99