Codeforces Global Round 21 A

A和B无讲解
A NIT orz!

代码实现

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;

int main(){

cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);

int T;
cin >> T;
while(T--){
      int n, z;
      cin >> n >> z;
      int res = 0;
      for(int i = 1; i <= n; i++){
         int x;
         cin >> x;
         res = max(res, x | z);
      }
      cout << res << &#39;\n&#39;;
}

}
B NIT Destroys the Universe

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;
int a[maxn];

int main(){

cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);

int T;
cin >> T;
while(T--){
      int n, cnt0 = 0;
      cin >> n;
      for(int i = 1; i <= n; i++){
         int x;
         cin >> x;
         cnt0 += (x == 0);
         a = x;
      }
      if (cnt0 == n) cout << 0 << &#39;\n&#39;;
      else{
         for(int i = 1; i <= n; i++){
            if (!a) continue;
            int j = i;
            while(j + 1 <= n && a[j + 1]) j++;
            if (j - i + 1 + cnt0 == n) cout << 1 << &#39;\n&#39;;
            else cout << 2 << &#39;\n&#39;;
            break;
         }
      }
}

}
C Fishingprince Plays With Array

题意

给出两个序列和和一个数,每次可以把序列中一个的倍数拆成个,或者把连续个相同的数变成一个数字,问能否通过操作使得和相同
分析

我们把所有能拆的数字全部拆开,然后比较两个序列是否相等即可.注意由于可能拆出的段非常多,所以要把值相同的若干个值缩成一个区间.
代码实现

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;

int main(){

cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);

int T;
cin >> T;
while(T--){
      int n, m, k;
      cin >> n >> m;
      vector<pair<LL, LL> > a, b;
      for(int i = 1; i <= n; i++){
         LL x;
         cin >> x;
         LL cnt = 1;
         while(x % m == 0) cnt *= m, x /= m;
         if (a.empty() || a.back().first != x) a.push_back({x, cnt});
         else a.back().second += cnt;
      }
      cin >> k;
      for(int i = 1; i <= k; i++){
         LL x;
         cin >> x;
         LL cnt = 1;
         while(x % m == 0) cnt *= m, x /= m;
         if (b.empty() || b.back().first != x) b.push_back({x, cnt});
         else b.back().second += cnt;
      }
      cout << (a == b ? &#34;Yes&#34; : &#34;No&#34;) << &#39;\n&#39;;
}

}
D Permutation Graph

题意

给出一个排列,如果满足和分别是区间内的最小值和最大值,则之间有边,问从号点走到号点至少需要多少步.
分析

从样例给的图来看似乎到了每个点之后贪心地走向最远的点一定是更优的(但是我不太会证明).我们当然希望每次尽可能跨过尽可能长的区间.
我的做法是这样的,分治去做,用线段树或者ST表预处理之后每次求得当前区间的最大值和最小值位置分别为和(如果就交换一下位置),然后我们指定其中一条路径就是,然后递归区间和.
这样为什么是对的呢,因为我们发现我们求出和后,左边的路径是不可能连到右边的点的,因为是最小值或者最大值,如果路径区间跨过了,那么一定有一个端点不是最值(因为一定是一个最值),同理,右边的路径也不可能连到左边的点.所以直接从连到一定是最优的.
最多递归层,每层长度为,总时间复杂度为(线段树)或者(ST表)
代码实现

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn = 2.5e5 + 5, INF = 0x3f3f3f3f;
int a[maxn], pos[maxn];

struct Node{
int l, r, minv, maxv;
}tr[maxn * 4];
int n, m, p;

void pushup(int u){
tr.minv = min(tr[u << 1].minv, tr[u << 1 | 1].minv);
tr.maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
}

void build(int u, int l, int r){
tr.l = l, tr.r = r;
if (l == r){
      tr.minv = tr.maxv = a[r];
      return;
}
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}

int query_min(int u, int l, int r){
if (tr.l >= l && tr.r <= r) return tr.minv;
int mid = tr.l + tr.r >> 1;
int v = INF;
if (l <= mid) v = query_min(u << 1, l, r);
if (r > mid) v = min(v, query_min(u << 1 | 1, l, r));
return v;
}

int query_max(int u, int l, int r){
if (tr.l >= l && tr.r <= r) return tr.maxv;
int mid = tr.l + tr.r >> 1;
int v = 0;
if (l <= mid) v = query_max(u << 1, l, r);
if (r > mid) v = max(v, query_max(u << 1 | 1, l, r));
return v;
}

int solve(int l, int r){
if (l + 1 == r) return 1;
if (l >= r) return 0;
int maxv = query_max(1, l, r);
int minv = query_min(1, l, r);
int L = pos[maxv], R = pos[minv];
if (L > R) swap(L, R);
return solve(l, L) + 1 + solve(R, r);
}

int main(){

cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);

int T;
cin >> T;
while(T--){
      int n;
      cin >> n;
      for(int i = 1; i <= n; i++) cin >> a, pos[a] = i;
      if (n == 1){
         cout << 0 << &#39;\n&#39;;
         continue;
      }
      build(1, 1, n);
      cout << solve(1, n) << &#39;\n&#39;;
}

}
E Placing Jinas

题意

给出一个不增序列,满足的格子是白色的.初始在有一个玩偶,每次操作可以删除上的一个玩偶,然后在和各生成一个玩偶,问想要白色区域没有任何玩偶至少需要多少次操作.
分析

首先我们打个表观察一下如果所有都相等每个点需要移动多少次.

我们发现第第行第列需要移动的次数为(如果对组合数比较敏感的话应该是能发现的),我们要求每个点的移动次数其实就是求一个矩形框内的和.比如样例中要求的是到这个矩阵的和.

然后我们可以发现(应该也可以公式推导吧...)左上角在的矩形的和等于这个矩形右下角的数字减一(蓝色圈出的数,打表发现的).所以我们可以求一个矩形内需要的总步数.
但是实际上是不相等的,但是我们可以根据的值把原图形拆成一个一个小矩形,然后利用前缀和的性质求解每个矩形对答案的贡献,就可以求得答案,复杂度是的
代码实现

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 5, mod = 1e9 + 7;
int a[maxn];
LL fact[maxn], invfact[maxn];

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

void init(){
fact[0] = invfact[0] = 1;
for(int i = 1; i < maxn; i++) fact = (LL)fact[i - 1] * i % mod;
invfact[maxn - 1] = qpow(fact[maxn - 1], mod - 2, mod);
for(int i = maxn - 2; i; i--)
      invfact = (LL)invfact[i + 1] * (i + 1) % mod;
}

inline LL C(int a, int b){
if (a < b) return 0;
return fact[a] * invfact % mod * invfact[a - b] % mod;
}

int main(){

cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);

init();
int n;
cin >> n;
n++;
for(int i = 1; i <= n; i++) cin >> a;
while(n && !a[n]) n--;
if (!n){
      cout << 0 << &#39;\n&#39;;
      return 0;
}
vector<pair<int, int> > p;
for(int i = 1; i <= n; i++){
      int j = i;
      while(j + 1 <= n && a[j + 1] == a) j++;
      p.push_back({i, j});
      i = j;
}
LL res = 0;
for(auto [l, r] : p)
      res = (res + C(r + a[l], a[l]) - C(l + a[l] - 1, a[l]) + mod) % mod;
cout << res << &#39;\n&#39;;

}

本文使用 Zhihu On VSCode 创作并发布