Codeforces Round 524 (Div. 2)

似乎仍然不是很难。

A

Description

有 $n$ 个人，每个人需要 $2$ 张红纸，$5$ 张绿纸，$8$ 张蓝纸。一次可以买 $k$ 张同一种颜色的纸。问最少需要买几次。

Solution

算一下每种颜色需要几张纸然后除一下向上取整。

Code

#include <iostream>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using std::cin;
using std::cout;
using std::endl;

int main() {
  int n, k;
  cin >> n >> k;
  int a = n * 2, b = n * 5, c = n * 8;
  a = ceil(1.0 * a / k), b = ceil(1.0 * b / k), c = ceil(1.0 * c / k);
  cout << a + b + c << endl;
}

B

Description

有一个序列 $\{a_i\}$，通项公式 $a_i=i\times(-1)^i$，$q$ 个询问，求区间和。

Solution

找规律即可，规律不写了。

Code

#include <iostream>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using std::cin;
using std::cout;
using std::endl;

int main() {
  int q;
  cin >> q;
  while (q--) {
    int x, y;
    cin >> x >> y;
    int len = y - x + 1;
    if (x == y)
      cout << (x & 1 ? -x : x) << endl;
    else {
      int p = len / 2 * (x & 1 ? 1 : -1);
      if (len & 1)
        p += y & 1 ? -y : y;
      cout << p << endl;  
    }
  }
}

C

Description

有一个 $n\times m$ 的国际象棋棋盘（每个格子颜色白或黑），先将一个子矩形染成白色，再将一个子矩形染成黑色，问最后有几个白格子和几个黑格子。$n,m\leq10^9$。

Solution

只算黑色格子即可，乱算一算，最后再把重叠部分算进去。

Code

#include <iostream>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using std::cin;
using std::cout;
using std::endl;

int main() {
  int T;
  cin >> T;
  while (T--) {
    long long n, m;
    cin >> n >> m;
    long long x1, x2, y1, y2, x3, y3, x4, y4;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    long long black = n * m / 2;
    long long dx1 = x2 - x1 + 1, dy1 = y2 - y1 + 1;
    black -= dx1 * dy1 / 2;
    if (dx1 * dy1 % 2)
      if ((x1 + y1) & 1)
        black--;    
    long long dx2 = x4 - x3 + 1, dy2 = y4 - y3 + 1;
    black += dx2 * dy2 / 2;
    if (dx2 * dy2 % 2)
      if ((x3 + y3) % 2 == 0)
        black++;
    long long x5 = std::max(x3, x1), x6 = std::min(x2, x4), y5 = std::max(y1, y3), y6 = std::min(y2, y4);
    if (x5 <= x6 && y5 <= y6) {
      long long dx0 = x6 - x5 + 1, dy0 = y6 - y5 + 1;
      black += dx0 * dy0 / 2;
      if (dx0 * dy0 % 2) {
        if ((x5 + y5) % 2) {
          black++;
        }
      }
    }
    long long white = n * m - black;
    cout << white << " " << black << endl;
  }
}

D

Description

有一个 $2^n\times2^n$ 的正方形，进行 $k$ 次切割操作，每次把一个正方形切成 $4$ 个等大的小正方形。

需要找到一条在切割后正方形边长全部相同且四连通的从左下角到右上角的路径，判断能不能找到，如果能找到，输出这条路径上正方形边长以 $2$ 为底的对数。

$n\leq10^9,k\leq10^{18}$。

Solution

能算出来把一个 $2^n\times 2^n$ 的正方形切成最小的切割次数 $a_n$ 满足递推式 $a_n=4\times a_{n-1}+1$。

显然我们只需要打通一条路就行，其他的随便切。

那么当 $n>31$，肯定无解。

我们可以枚举这条路径上正方形边长，设边长为 $2^i$，那么我们只需要找到可以的最小切割次数和最大切割次数，如果 $k$ 在这两个数的闭区间里，那么一定有解。

最小切割次数怎么算呢？我们只切最边上的路径，第一次切 $1$ 次，第二次切 $3$ 次，第三次切 $7$ 次……，所以最小切割次数 $mi_i=\sum_{j=1}^{n-i}mi_j$。

最大切割次数怎么算呢？我们先切成最小的方块，然后减去多切的。最多切割次数 $f_i=a_n-a_i\times(2^{n-i+1}-1)$。

就这样。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using std::cin;
using std::cout;
using std::endl;

typedef long long ll;

ll a[40], mi[40], mx[40];


int solve(int n, ll k) {
  for (int i = 0; i < n; i++) {
    if (a[n] - a[i] * ((1ll << (n - i + 1)) - 1) >= k && mi[n - i - 1] <= k)
      return i;
  }
  return -1;
}

int main() {
  int T;
  cin >> T;
  for (int i = 1; i <= 31; i++)
    a[i] = 4 * a[i - 1] + 1;
  for (int i = 0; i <= 31; i++)
    mi[i] = (1ll << (i + 1)) - 1 + mi[i - 1];
  while (T--) {
    long long n, k;
    cin >> n >> k;
    if (n > 31) {
      cout << "YES" << " " << n - 1 << endl;
      continue;
    }
    if (k > a[n]) {
      cout << "NO" << endl;
      continue;
    }
    int ans = solve(n, k);
    if (ans == -1)
      cout << "NO" << endl;
    else
      cout << "YES" << " " << ans << endl;
  }
}

E

Description

$n\times m$ 的字符矩阵，求满足一下条件子矩形个数：将每一行重新排列后满足每一行和每一列都是回文串。$n\leq250$。

Solution

每一行的要求可以很好判断，因为可以随便重排，满足至多只有一个字符出现两次即可。然后把每一行当成一个字符做 manacher，就行了。复杂度 $O(nm^2|\sum|)$，能过。如果比较每一行用 hash 来判断，那就可以优化到 $O(nm^2)$。

shr 神说可以用组合数暴力算，我不懂，他 tql。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 510;

char s[maxn][maxn];

int n, m, cnt[maxn][30], odd[maxn], d[maxn];
long long ans = 0;

inline bool cmp(int a, int b)
{
    if (odd[a] > 1 || odd[b] > 1)
        return false;
    for (int i = 0; i < 26; i++)
        if (cnt[a][i] != cnt[b][i])
            return false;
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", s[i] + 1);
    for (int l = 1; l <= m; l++)
    {
        memset(cnt, 0, sizeof(cnt)), memset(odd, 0, sizeof(odd));
        for (int r = l; r <= m; r++)
        {
            for (int i = 1; i <= n; i++)
            {
                char ch = s[i][r] - 'a';
                cnt[2 * i - 1][ch]++;
                if (cnt[2 * i - 1][ch] & 1)
                    odd[2 * i - 1]++;
                else
                    odd[2 * i - 1]--;
            }
            memset(d, 0, sizeof(d));
            cnt[2 * n + 1][0] = -1;
            for (int i = 1, l = 0, r = 0; i <= 2 * n; i++)
            {
                if (odd[i] > 1)
                    continue;
                if (i <= r)
                    d[i] = std::min(r - i + 1, d[l + r - i]);
                while (cmp(i - d[i], i + d[i]))
                    d[i]++;
                if (i + d[i] >= r)
                    r = i + d[i] - 1, l = i - d[i] + 1;
                ans += d[i] / 2;
            }
        }
    }
    cout << ans << endl;
}

F

Description

有 $n$ 个集合，$k$ 条线段，每条线段由 $l,r,p$ 描述，分别表示其左端点，右端点，所在集合。

$m$ 个询问，每次给出 $a,b,x,y$，问编号在 $[a,b]$ 之间所有的集合是否都存在一条满足 $x\leq l\leq r\leq y$ 的线段。

$n,m\leq10^5$，$k\leq3\times10^5$，强制在线。

Solution

看到强制在线，像是能用线段树维护的信息，我们想到主席树（）（）（）

以上扯淡，分析一下，如果直接存线段的信息会发现集合信息很难维护。

我们考虑存集合并转化一下要求的东西。

如果一个集合满足要求，那么它左端点大于等于 $l$ 的线段中右端点最小值必定小于等于 $y$。

如果多个集合呢？就是这些集合上面这个东西的最大值小于等于 $y$。

那么我们线段树里维护的东西就确定了：叶子中是这个集合中 $r$ 的最小值，非叶子结点是它所管辖区间中上述值的最大值。

那么怎么满足线段树中只有左端点大于等于 $l$ 的线段呢？我们用一棵主席树，把线段按照 $l$ 从大到小插入进去就行了。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

const int maxn = 1e5 + 10;
const int maxk = 3e5 + 10;

int root[maxk], n, m, k, inf = 1 << 30;

struct Tree
{
    static const int maxn = ::maxn << 6;
    int ls[maxn], rs[maxn], tot, mx[maxn];
    Tree()
    {
        for (int i = 0; i < maxn; i++)
            mx[i] = inf;
    }
    int clone(int k)
    {
        tot++;
        mx[tot] = mx[k], ls[tot] = ls[k], rs[tot] = rs[k];
        return tot;
    }
    inline void push_up(int k) { mx[k] = std::max(mx[ls[k]], mx[rs[k]]); }
    int build(int l, int r, int k)
    {
        if (!k)
            k = ++tot, mx[tot] = inf;
        if (l == r)
        {
            mx[k] = inf;
            return k;
        }
        int mid = (l + r) / 2;
        ls[k] = build(l, mid, ls[k]), rs[k] = build(mid + 1, r, rs[k]);
        push_up(k);
        return k;
    }
    int modify(int l, int r, int x, int y, int k)
    {
        k = clone(k);
        if (l == r)
        {
            mx[k] = std::min(mx[k], y);
            return k;
        }
        int mid = (l + r) / 2;
        if (x <= mid)
            ls[k] = modify(l, mid, x, y, ls[k]);
        else
            rs[k] = modify(mid + 1, r, x, y, rs[k]);
        push_up(k);
        return k;
    }
    int query(int l, int r, int x, int y, int k)
    {
        if (x <= l && y >= r)
            return mx[k];
        int res = 0, mid = (l + r) / 2;
        if (x <= mid)
            res = std::max(res, query(l, mid, x, y, ls[k]));
        if (y > mid)
            res = std::max(res, query(mid + 1, r, x, y, rs[k]));
        return res;
    }
} t;

struct Segment
{
    int l, r, p;
    bool operator<(const Segment &b) const { return l > b.l; }
} a[maxk];

int tot;

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= k; i++)
        scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].p);  
    std::sort(a + 1, a + 1 + k);
    root[0] = t.build(1, n, root[0]);
    for (int i = 1; i <= k; i++)
        root[i] = t.modify(1, n, a[i].p, a[i].r, root[i - 1]);
    while (m--)
    {
        int p, q, x, y;
        scanf("%d%d%d%d", &p, &q, &x, &y);
        int pos = std::upper_bound(a + 1, a + 1 + k, (Segment){x, 0, 0}) - a - 1;
        int ans = t.query(1, n, p, q, root[pos]);
        puts(ans <= y ? "yes" : "no");
        fflush(stdout);
    }
}

A¶

Description¶

Solution¶

Code¶

B¶

Description¶

Solution¶

Code¶

C¶

Description¶

Solution¶

Code¶

D¶

Description¶

Solution¶

Code¶

E¶

Description¶

Solution¶

Code¶

F¶

Description¶

Solution¶

Code¶

A

Description

Solution

Code

B

Description

Solution

Code

C

Description

Solution

Code

D

Description

Solution

Code

E

Description

Solution

Code

F

Description

Solution

Code