Codeforces Round #361 (Div. 2)

5/5

这场打得真的不太好，可以说是GG了，然而题解还是要补上~~

 

题A Mike and Cellphone

题意：给你一个数字键盘，然后给你划过的串，然后问你存不存在同样的手势但是不一样的串，也就是这个串表示的手势是否唯一？

题解：这道题其实可以枚举出所有可能的唯一的手势情况，然后直接判断。但是这样很费时间去推导。既然数据量小，那么我们就可以枚举所有的偏移情况，也就是给定一个移动的向量，看模拟移动之后是否存在一个合法的串，如果有就说明不唯一，否则就唯一。显然这个向量（x，y）的x和y是在[-3,3]之间。因此，这道题本质上可以说是模拟题。

 

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

#define lson l, m, rt*2
#define rson m + 1, r, rt*2+1
#define xx first
#define yy second

typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;

int main() {
//  freopen("case.in", "r", stdin);
  int n;
  cin >> n;
  string s;
  cin >> s;
  for (int i = -3; i <= 3; i++)
    for (int j = -3; j <= 3; j++) if (i != 0 || j != 0) {
//      cout << i << ' ' << j << endl;
      bool ok = 1;
      for (int k = 0; k < n; k++) {
        int r, c;
        if (s[k] == '0') r = 3, c = 1;
        else r = (s[k] - '1') / 3, c = (s[k] - '1') % 3;
        r += i;
        c += j;
        if (!((r == 3 && c == 1) || (r >= 0 && r <= 2 && c >= 0 && c <= 2))) ok = 0;
      }
      if (ok) { puts("NO"); return 0; }
    }
  puts("YES");
  return 0;
}

 

题B Mike and Shortcuts

题意：给你1~n的门，然后可以花费|di - di+1|到达目的地，然后给你一个捷径，代表这个点可以花费一个能量到达，最后问你1到所有点的最短距离。

题解：这道题很简单，实际上就是一个最短路，每个点有三个门，左边、右边、捷径。然后就是类似spfa的找最短路。

 

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

const int maxn = 2e5 + 10, inf = 1 << 30;
int d[maxn], t[maxn], inq[maxn], n;
queue<int> q;

void go_que(int u, int v) {
  if (v < 1 || v > n) return;
  if (d[v] > d[u] + 1) {
    d[v] = d[u] + 1;
    if (!inq[v]) {
      q.push(v);
      inq[v] = 1;
    }
  }
}

int main() {
//  freopen("case.in", "r", stdin);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%d", t + i);
    d[i] = inf;
  }
  q.push(1);
  inq[1] = 1;
  d[1] = 0;
  while (!q.empty()) {
    int x = q.front(); q.pop();
    inq[x] = 0;
    go_que(x, t[x]);
    go_que(x, x + 1);
    go_que(x, x - 1);
  }
  for (int i = 1; i <= n; i++) {
    printf("%d ", d[i]);
  }
  puts("");
}

 

题C Mike and Chocolate Thieves

题意：给定一个m，然后问你存不存m个满足的只有4个元素的序列，使得每个相邻元素之间的倍数是k（k > 1），如果存在输出最大的数n，否则输出-1?

题解：这个数n越大，显然个数越多，利用单调性，我们二分一个答案n，然后计算n有多少个？怎么计算呢？显然个数有(n / 8) + (n / 27) + (n / 64)……

 

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

typedef long long ll;
const int maxn = 1e5 + 100;


ll get_num(ll x) {
  ll ret = 0;
  for (int i = 2; ; i++) {
    ll tmp = 1ll * i * i * i;
    if (tmp > x) break;
    ret += x / tmp;
  }
  return ret;
}

int main() {
//  freopen("case.in", "r", stdin);
  ll m;
  cin >> m;
  ll L = 7, R = 1e16;
  while (R - L > 1) {
    ll M = (L + R) / 2;
    if (get_num(M) >= m) R = M; else L = M;
  }
  if (get_num(R) == m) cout << R << endl;
  else cout << -1 << endl;
  return 0;
}

 

题D Friends and Subsequences

题意：给你两个数组a和b，个数均为n个，然后让你数有多少对[l,r]使得a里面元素的最大值和b里面元素的最小值相等。

题解：这里我们观察到这个最大值-最小值是单调的，所以对于下标为i的起点，得到最大值-最小值的结果是：（负数） 0 0 0 （正数），所以我们利用二分搜索可以得到lower_bound和upper_bound，然后这个长度即为以i为起点的区间个数。利用rmq，复杂度可以做到O（nlogn）。

 

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

#define lson l, m, rt*2
#define rson m + 1, r, rt*2+1
#define xx first
#define yy second

typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;

const int maxn = 2e5 + 100, maxm = 30;
int v[2][maxn], dp[2][maxn][maxm];
int n;

void rmq_init() {
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < n; j++) {
      dp[i][j][0] = v[i][j];
    }

  for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 0; i + (1 << j) - 1 < n; i++) {
      dp[0][i][j] = max(dp[0][i][j - 1], dp[0][i + (1 << (j - 1))][j - 1]);
      dp[1][i][j] = min(dp[1][i][j - 1], dp[1][i + (1 << (j - 1))][j - 1]);
    }
  }
}

int query(int index, int L, int R) {
  int k = 0;
  while(1 << (k + 1) <= R - L + 1) k++;
  if (index == 0) return max(dp[0][L][k], dp[0][R - (1 << k) + 1][k]);
  else return min(dp[1][L][k], dp[1][R - (1 << k) + 1][k]);
}

int main() {
//  freopen("case.in", "r", stdin);

  cin >> n;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < n; j++) {
      scanf("%d", &v[i][j]);
    }
  rmq_init();
  ll res = 0;
  for (int i = 0; i < n; i++) {
    int L = i, R = n - 1;
    int ansL = -1, ansR = -1;
    while (L <= R) {
      int M = (L + R) / 2;
      int tmp = query(0, i, M) - query(1, i, M);
      if (tmp >= 0) {
        ansL = M; R = M - 1;
      } else L = M + 1;
    }
    L = i, R = n - 1;
    while (L <= R) {
      int M = (L + R) / 2;
      int tmp = query(0, i, M) - query(1, i, M);
      if (tmp <= 0) {
        ansR = M; L = M + 1;
      } else R = M - 1;
    }
    if (ansL != -1 && ansR != -1) res += (ansR - ansL + 1);
  }
  cout << res << endl;

  return 0;
}

 

题E Mike and Geometry Problem

题意：给你n个区间，任选k个区间，问你这k个区间相交的长度之和是多少？

题解：对于一段区间如果已知有x次相交，如果x >= k说明有C（x，k）个线段可以得到这个相交区间，所以先用map来离散表示区间，然后枚举每个区间，对于相交个数x，如果大于k的话，那么答案贡献就是C（x，k）*（区间的长度），这个做法类似于edu的一个题目，详见CF官方题解。

 

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

#define lson l, m, rt*2
#define rson m + 1, r, rt*2+1
#define xx first
#define yy second

typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;

const int maxn = 2e5 + 100, mod = 1e9 + 7;
map<int,int> mp;
ll f[maxn], c[maxn];

ll quick(ll a, ll b, ll c) {
  ll ret = 1;
  while (b) {
    if (b & 1) ret = ret * a % c;
    b = b / 2;
    a = a * a % mod;
  }
  return ret;
}

void init() {
  f[0] = 1;
  for (int i = 1; i < maxn; i++) f[i] = f[i - 1] * i % mod;
  for (int i = 0; i < maxn; i++) c[i] = quick(f[i], mod - 2, mod);
}

ll C(int n, int k) {
  if (n < k) return 0ll;
  return (f[n] * c[k] % mod) * c[n - k] % mod;
}

int main() {
//  freopen("case.in", "r", stdin);

  init();
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    mp[l]++;
    mp[r + 1]--;
  }
  ll res = 0;
  int last = mp.begin() -> first, sum = 0;
  for (map<int,int>::iterator it = mp.begin(); it != mp.end(); it++) {
    int x = it->first, y = it->second;
//    cout << sum << endl;
//    cout << x << ' ' << last << endl;
    if (sum >= k) {
      res += C(sum, k) * (x - last) % mod;
      res %= mod;
    }
    last = x;
    sum += y;
  }
  cout << res << endl;

  return 0;
}