周赛9题解

A

按要求输出即可

void solve() {
  int n;
  string s;
  cin >> n >> s;
  cout << (n >= 3200 ? s : "red");
}

为了抢一血没好好看题wa了一发。。。

B

按要求输出，没看数据范围稍微有点写复杂了...算是小小当了一波??

void solve() {
  int k, x;
  cin >> k >> x;
  for (int i = max(-1000000, x - k + 1); i <= min(1000000, x + k - 1); ++i) {
    cout << i << ' ';
  }
}

C

读完题发现个数一样就行，然后因为字符串最多到10所以直接map套string就好了，如果字符串比较长可以map套vector统计一下每个字母出现的个数，不过如果字符串长度小于26显然就更慢了。

void solve() {
  int n;
  cin >> n;
  map mp;
  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    mp[s]++;
  }
  for (auto & i : mp) {
    ll tmp = i.second;
    if (tmp < 2) continue;
    ans += (tmp - 1) * tmp / 2;
  }
  cout << ans;
}

D

裸dfs，遍历一下就好了把父结点的权值加到子结点。

struct Node {
  int to, ne;
} edg[N * 2];
 
int head[N], tot;
ll a[N];
 
void add(int u, int v) {
  edg[++tot].to = v;
  edg[tot].ne = head[u];
  head[u] = tot;
}
 
void dfs(int u, int pa) {
  for (int i = head[u]; i; i = edg[i].ne) {
    int to = edg[i].to;
    if (to == pa) continue;
    a[to] += a[u];
    dfs(to, u);
  }
}
 
void solve() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    add(u, v), add(v, u);
  }
  for (int i = 0; i < m; ++i) {
    int p, x;
    cin >> p >> x;
    a[p] += x;
  }
  dfs(1, 0);
  for (int i = 1; i <= n; ++i) {
    cout << a[i] << ' ';
  }
}

E

挺有趣的但也不难，像是字符串中指定子序列的出现次数之类的题其实做的比较多了，所以贪心匹配比较好想，但显然需要优化，优化的话也是典中典，从后面扫一遍加快模拟就行，这种思路已经是第二次出现在周赛了，上上次的cf也的c我也是这么写的，比推公式要简单很多。

int f[N][26];
 
void solve() {
  string s, t;
  cin >> s >> t;
  int sn = s.size(), tn = t.size();
  s = char(123) + s;
  t = char(123) + t;
  vector ch(30);
  for (int i = sn; ~i; --i) {
    for (int j = 0; j < 26; ++j) {
      f[i][j] = ch[j];
    }
    ch[s[i] - 'a'] = i;
  }
  ll cnt = 0, j = 0;
  for (int i = 1; i <= tn; ++i) {
    int now = t[i] - 'a';
    if (!ch[now]) {
      cout << -1;
      return;
    }
    else {
      if (f[j][now]) {
        j = f[j][now];
      }
      else {
        j = ch[now];
        ++cnt;
      }
    }
  }
  cout << cnt * sn + j;
}

插播一下上上次cf的C因为idea基本一致

Dashboard - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2) - Codeforces

这场其他题我应该不会补。。因为题面真的恶心人，d死活没读懂然后别人一解释题意就秒了

ll n, e, k, a[N], f[N];
 
int npr[N], pr[N];
 
void Shai(int n) {
  for(int i = 2 ;i <= n; ++i) {
    if(!npr[i]) pr[++pr[0]] = i;
    for(int j = 1; j <= pr[0] && i * pr[j] <= n && (npr[i * pr[j]] = pr[j]); ++j)
      if(i % pr[j] == 0) break;
  }
}
 
void solve() {
  cin >> n >> e;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    f[i] = 0;
  }
  for (int i = n; i; --i) {
    if (i + e <= n && a[i + e] == 1) f[i] += f[i + e];
    if (a[i] == 1) ++f[i];
  }
  ll ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (a[i] == 1) {
      ll tmp = f[i];
      if (i + tmp * e <= n && !npr[a[i + tmp * e]]) {
        ans += f[i + tmp * e] + 1;
      }
    }
    else if (!npr[a[i]]) {
      ans += f[i];
    }
  }
  cout << ans << nl;
}

就还是从后往前处理一下就好了，然后就可以按题意模拟算答案了，素数其实暴力判断都能过，不过我还是筛了一下

F

思考了一会儿没想出来怎么数位dp，感觉是个妙妙题就没做了，不过看题解感觉可以补待补题，这种难题不做就永远不会但是我马上应该会总结一下数位dp就放到那时候再补吧（

还是看题解提前补了，因为下次一定就不知道是那一次了（

这道题需要先把 y mod x 转化一下

发现需要 x 和 y 位数相同，最高位同时为 1

然后就把问题转化成了满足 y - x = y ^ x 的对数

对于这个显然如果 y 二进制下为 1 x 为 0 或 1，y 为 0 则 x 比为 0

然后就可以数位dp了

然后这个写法比经典数位dp感觉更妙一点

ll f[N][2][2][2], L, R, ml[N], mr[N];

ll dfs(int d, int fl, int fr, bool lead) {
  if (!d) return 1;
  if (~f[d][fl][fr][lead]) return f[d][fl][fr][lead];
  ll res = 0;
  int lb = fl ? ml[d] : 0, rb = fr ? mr[d] : 1;
  for (int y = 0; y <= rb; ++y) {
    for (int x = lb; x <= y; ++x) {
      if (lead && x != y) continue;
      res = (res + dfs(d - 1, fl & (x == lb), fr & (y == rb), lead && y  == 0)) % mod;
    }
  }
  return f[d][fl][fr][lead] = res;
}

void solve() {
  memset(f, -1, sizeof f);
  ll l, r;
  cin >> l >> r;
  while (l) {
    ml[++L] = l & 1;
    l >>= 1;
  }
  while (r) {
    mr[++R] = r & 1;
    r >>= 1;
  }
  cout << dfs(R, 1, 1, 1) % mod;
}