Educational Codeforces Round 142

标签：10 Educational ch 142 int Codeforces times le include

- 写在前面
- A
- B
- C
- D
- E
写在最后

写在前面

比赛地址：https://codeforces.com/contest/1792。

我是超级大鸽子咕咕咕

A

当且仅当有两个怪物初始血量为 1 时使用操作 1，否则用操作 2。

//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
//=============================================================
//=============================================================
inline int read() {
	int f = 1, w = 0; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
	for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
	return f * w;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    int n = read();
    int num1 = 0, num2 = 0;
    for (int i = 1; i <= n; ++ i) {
      int h = read();
      num1 += (h == 1);
      num2 += (h != 1);
    }
    int ans = num1 / 2;
    ans += num2 + (num1 % 2 == 1);
    printf("%d\n", ans);
  }
	return 0;
}

B

先把操作 1 全用了。若此时心情大于 1，则再交替使用操作 2、3，直至不能使得心情值保持不变。此时两人心情相同，且进行操作一定会使某人的心情不可逆地降低，此时至多可再进行心情 +1 次操作。

用完操作 1 后，两人的心情值之和无法增加。则应保证在心情值不变的情况下尽可能地多进行操作，并在心情值不得不下降时，使心情值较小的一方的心情尽可能大。则显然按上述的顺序进行操作是最优的。

//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
//=============================================================
//=============================================================
inline int read() {
	int f = 1, w = 0; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
	for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
	return f * w;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    int a[5] = {0}, ans, now;
    for (int i = 1; i <= 4; ++ i) a[i] = read();
    now = ans = a[1];
    
    int maxa = std::max(a[2], a[3]), mina = std::min(a[2], a[3]);
    if (now == 0) {
      if (a[2] || a[3] || a[4]) ++ ans;
      printf("%d\n", ans);
      continue;
    }
    ans += 2 * mina;
    maxa -= mina;

    if (now < maxa) {
      ans += now + 1;
      printf("%d\n", ans);
      continue;
    }
    ans += maxa;
    now -= maxa;
    
    if (now < a[4]) {
      ans += now + 1;
      printf("%d\n", ans);
      continue;
    }
    ans += a[4];
    printf("%d\n", ans);
  } 
	return 0;
}

C

先手玩几组数据找找结论。以下将对元素 \(x,y\) 的一次操作简写为 \((x,y)\)，将元素 \(i\) 位于位置 \(i\) 称为 \(i\) 在有序位置。

一种通用的操作顺序是：

\[\left(\left\lfloor \frac{n}{2} \right\rfloor, n - \left\lfloor \frac{n}{2} \right\rfloor + 1\right) \rightarrow \left(\left\lfloor \frac{n}{2} \right\rfloor - 1, n - \left\lfloor \frac{n}{2} \right\rfloor + 2\right)\rightarrow \dots \rightarrow (1, n) \]

当 1 或 \(n\) 不在有序位置时，必须在最后进行 \((1,n)\) 使得它们有序。
对结论 1 进行扩展，当有任意的数不在有序位置时，都必须在最后进行 \((1,n)\)。因为其他的操作后 \(1\) 和 \(n\) 一定在无序位置。同理，当有除 \(1, n\) 的数不在有序位置时，倒数第二次操作一定是 \((2, n-1)\)；当有除 \(1, 2, n-1, n\) 的数不在有序位置时，倒数第三次操作一定是 \((3, n-2)\)……
综合结论 1、3 考虑，我们仅需找到结论 1 中操作序列中尽量靠后的一个位置，使得这个位置之前的操作对象们都是相对有序的。从该位置开始向后进行操作即可。

实现时记录每个数在排列中的位置，按照数的大小中间向两侧比较位置，检查是否相对有序即可。复杂度 \(O(n)\) 级别。

//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
const int kN = 2e5 + 10;
//=============================================================
int n, a[kN], pos[kN];
//=============================================================
inline int read() {
	int f = 1, w = 0; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
	for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
	return f * w;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read();
    for (int i = 1; i <= n; ++ i) {
      a[i] = read();
      pos[a[i]] = i;
    }
    int lth = 0;
    int i, j;
    if (n % 2) {
      i = j = (n + 1) / 2;
    } else {
      i = n / 2, j = n / 2 + 1;
    }
    for (int fir = n, las = 1; 
         i > 0 && j <= n; -- i, ++ j) {
      if (pos[i] <= pos[j] && pos[i] <= fir && pos[j] >= las) {
        if (i != j) ++ lth;
      } else {
        break;
      }
      fir = pos[i], las = pos[j];
    }
    printf("%d\n", n / 2 - lth);
  }
	return 0;
}

D

对于两个长度为 \(m\) 的排列 \(p,q\)，定义一种运算 \(p\cdot q = r\)。运算结果 \(r\) 也是一个长度为 \(m\) 的排列，且满足：\(r_i = q_{p_i}\)。对于排列 \(p\) 定义其魅力值为满足 \(p_1 = 1, p_2 = 2, \dots, p_k = k\) 的最大的下标 \(k\)。特别地，若 \(p_1\not= 1\)，\(p\) 的魅力值为 0。
\(t\) 组数据，每组数据给定 \(n\) 个长度为 \(m\) 的排列 \(a_1\sim a_n\)。对于所有 \(a_i (i\in [1, n])\)，求 \(a_i\cdot a_j (j\in [1, n])\) 的魅力值的最大值。
\(1\le t\le 10^4\)，\(1\le n\le 5\times 10^4\)，\(1\le m\le 10\)，\(\sum n\le 5\times 10^4\)。
2S，256MB。

凭什么卡我 bitset 暴力啊（恼

发现定义的这个运算和矩阵乘法相当相似，不满足交换律，且满足结合律，证明可自己手玩。于是考虑矩阵乘法那一套：定义单位排列 \(A = (1, 2, \dots, m)\)；对于排列 \(p\)，将满足 \(p\cdot q = A\) 的排列 \(q\) 定义为排列 \(p\) 的逆排列，记作 \(p^{-1}\)。

再回到题目所求，若 \(p\cdot q = (1, 2, \dots, k, \dots)\) 的魅力度为 \(k\)，考虑变换一下：

\[\begin{aligned} p\cdot q\cdot q^{-1} &= (1, 2, \cdots, k, \cdots)\cdot q^{-1}\\ p \cdot A&= (1, 2, \cdots, k, \cdots)\cdot q^{-1} \end{aligned}\]

上式等价于 \(p\) 和 \(q\) 的逆排列最长公共前缀为 \(k\)。

综上，考虑求得排列 \(a_1\sim a_n\) 的逆排列，查询 \(a_i\) 的答案时在所有逆排列上匹配最长公共前缀即可。使用 Trie 即可简单实现。总复杂度 \(O(nm)\) 级别。

或者更加具体地，还可以从实际意义考虑逆排列的含义：\(q^{-1}_{i}\) 即排列 \(q\) 中 \(i\) 的位置。如果从等号右边往左边理解，上式的另一种解释是处理出每个排列中 \(1\sim m\) 的位置并按顺序组成一个新的排列 \(q^{-1}\)，求这个新的排列与所有原排列的最长公共前缀。

注意清空 Trie 时要全部清空，并且数组开大点。两个错误叠起来 RE 变 WA 真是把我鲨了。

//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 5e4 + 10;
const int kM = 11;
//=============================================================
int n, m, a[kN][kM], inv[kN][kM];
//=============================================================
inline int read() {
	int f = 1, w = 0; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
	for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
	return f * w;
}
namespace Trie {
  const int kNode = kN << 3;
  int num, tr[kNode][11];
  void Init() {
    for (int i = 0; i <= num; ++ i) {
      memset(tr[i], 0, sizeof (tr[i]));
    }
    num = 0;
  }
  void Insert(int id_) {
    int now = 0;
    for (int i = 1; i <= m; ++ i) {
      int x = inv[id_][i];
      if (!tr[now][x]) tr[now][x] = ++ num;
      now = tr[now][x];
    }
  }
  int Query(int id_) {
    int now = 0, ret = 0;
    for (int i = 1; i <= m; ++ i) {
      int x = a[id_][i];
      if (!tr[now][x]) break;
      ++ ret;
      now = tr[now][x];
    }
    return ret;
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read(), m = read();
    Trie::Init();
    for (int i = 1; i <= n; ++ i) {
      for (int j = 1; j <= m; ++ j) {
        a[i][j] = read();
        inv[i][a[i][j]] = j;
      }
      Trie::Insert(i);
    }
    for (int i = 1; i <= n; ++ i) {
      printf("%d ", Trie::Query(i));
    }
    printf("\n");
  }
	return 0;
}

E

\(t\) 组数据，每组数据给定参数 \(n, m_1, m_2\)。对于 \(m_1\times m_2\) 的约数 \(d\)，记满足 \(\exist 1\le x, y\le n, d = x\times y\) 的最小的 \(x\) 为 \(x_d\)，求上述 \(x_d\) 的个数，并输出所有 \(x_d\) 的异或和。
\(1\le t\le 10\)，\(1\le n, m_1, m_2\le 10^9\)。
2.5S，256MB。

写了个 \(O(m)\) 的质因数分解我是超级大啥b。

前置知识：约数个数的上界估计：https://www.cnblogs.com/ubospica/p/10392523.htm、https://blog.csdn.net/VFleaKing/article/details/88809335。
省流版：\(10^{18}\) 内的数约数至多有 \(103680\approx 10^5\) 个。

于是考虑先对 \(m_1, m_2\) 进行质因数分解，再暴力凑出 \(m_1\times m_2\) 的所有约数，问题变为对每一个约数 \(d\) 求得一组满足上述条件的 \((x,y)\)，且满足 \(x\) 尽可能地小，则 \(y\) 应当是满足 \(y\le n\) 的最大的 \(d\) 的约数。如果我们可以求得每个约数 \(d\) 对应的 \(y\)，那么只需检测 \(x = \frac{d}{y} \le n\) 是否成立即可判断 \(d\) 是否对答案有贡献。

直接暴力枚举 \(y\) 的复杂度是无法承受的。考虑子集 DP。记 \(f_{d}\) 表示满足 \(y\le n\) 的 \(d\) 的最大的约数。对于 \(d\le n\)，显然有 \(f_{d} = d\)；对于 \(d>n\)，考虑枚举 \(d\) 的质因子 \(p\)，有：

\[f_{d} = \max_{p|d} f_{\frac{d}{p}} \]

\(m_1\times m_2\) 的质因子的数量级只有 \(10\) 左右，DP 复杂度并不高。处理出 DP 值后累计有贡献的 \(f_{d}\) 即可。总复杂度约为 \(O(t(\sqrt{m_1 + m_2} + 10 \times \operatorname{d}(m_1\times m_2)))\) 级别。

DP 时要注意实现，虽然出题人没卡，但直接用 map 让 \(d\) 作 \(f\) 的下标跑的相当慢。应当令 \(d\) 的编号作 \(f\) 的下标，转移时使用二分查找 \(f_{\frac{d}{p}}\) 即可。

//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
#define LL long long
const int kN = 1e5 + 1e4 + 10;
//=============================================================
int n, m1, m2, sz, ans1, f[kN];
LL ans2;
std::vector <int> p, c;
std::vector <LL> d;
//=============================================================
inline int read() {
	int f = 1, w = 0; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
	for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
	return f * w;
}
void Init() {
  sz = ans1 = 0; ans2 = 0ll;
  p.clear(), c.clear(), d.clear();

  n = read(), m1 = read(), m2 = read();
  int temp1 = m1, temp2 = m2;
  for (int i = 2; i * i <= m1 || i * i <= m2; ++ i) {
    if (temp1 % i == 0 || temp2 % i == 0) {
      ++ sz;
      p.push_back(i), c.push_back(0);
      while (temp1 % i == 0) temp1 /= i, c[sz - 1] ++;
      while (temp2 % i == 0) temp2 /= i, c[sz - 1] ++;
    }
  }
  if (temp1 > temp2) std::swap(temp1, temp2);
  if (temp1 > 1) ++ sz, p.push_back(temp1), c.push_back(1);
  if (temp2 > 1 && temp1 == temp2) ++ c[sz - 1];
  if (temp2 > 1 && temp1 != temp2) ++ sz, p.push_back(temp2), c.push_back(1);
}
void Dfs(int lth_, LL d_) {
  if (lth_ == sz) {
    d.push_back(d_);
    return ;
  }
  Dfs(lth_ + 1, d_);

  LL x = 1ll;
  for (int i = 1; i <= c[lth_]; ++ i) {
    x *= p[lth_];
    Dfs(lth_ + 1, d_ * x);
  }
}
void DP(LL id_) {
  LL d_ = d[id_];
  if (d_ <= n) {
    f[id_] = d_;
    return ;
  }
  f[id_] = 0;
  for (int i = 0; i < sz; ++ i) {
    if (d_ % p[i]) continue;
    for (int l = 0, r = id_ - 1; l <= r; ) {
      int mid = (l + r) >> 1;
      if (d[mid] == d_ / p[i]) {
        f[id_] = std::max(f[id_], f[mid]);
        break;
      } else if (d[mid] < d_ / p[i]) {
        l = mid + 1; 
      } else {
        r = mid - 1;
      }
    }
  }
}
//=============================================================
int main() {
//  freopen("1.txt", "r", stdin);
  int t = read();
  while (t --) {
    Init();
    Dfs(0, 1);
    std::sort(d.begin(), d.end());
    for (int i = 0, dnum = d.size(); i < dnum; ++ i) {
			DP(i);
      if (f[i] && d[i] / f[i] <= n) {
        ++ ans1, ans2 ^= d[i] / f[i];
      }
    }
    printf("%d %lld\n", ans1, ans2);
  }
}

写在最后

D 另一种理解中的的反向考虑。
质因数分解是 \(O(\sqrt{m})\) 的。
\(10^{18}\) 内的数约数至多有 \(103680\approx 10^5\) 个。
10^9 内的数质因子至多有 \(10\) 个（\(2\times 3\times 5\times 7\times 11\times 13\times 17\times 19\times 23\times 29 = 6,469,693,230\)）。

最近 CF 一场连着一场还要学车还要抽空学杀软文化课防止挂科……走一步看一步吧你妈的，今晚还有场 Div3，现在手里屯了三套题没补完，我真是超级大鸽王。

标签：10,Educational,ch,142,int,Codeforces,times,le,include
From： https://www.cnblogs.com/luckyblock/p/17069405.html

Educational Codeforces Round 142

写在前面

A

B

C

D

E

写在最后

相关文章

赞助商

阅读排行