比赛链接

AtCoder Beginner Contest 161

Problem D. Lunlun Number

通过广搜预处理出所有的答案。

时间复杂度 $O(10^5)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

struct Data {
  long long x; 
  int y, z; 
};

int tot = 0;
long long ans[N];

void prk() {
  queue<Data> q;
  for (int i = 1; i <= 9; i++)
    q.push((Data){i, i, 1}), ans[++tot] = i;
  while (!q.empty()) {
    Data x = q.front();
    q.pop();
    if (x.z == 11)
      break;
    ans[++tot] = x.x * 10 + x.y;
    q.push((Data){ans[tot], x.y, x.z + 1});
    if (x.y - 1 >= 0) {
      ans[++tot] = x.x * 10 + x.y - 1;
      q.push((Data){ans[tot], x.y - 1, x.z + 1});
    }
    if (x.y + 1 <= 9) {
      ans[++tot] = x.x * 10 + x.y + 1; 
      q.push((Data){ans[tot], x.y + 1, x.z + 1});
    }
  }
  sort(ans + 1, ans + 1 + tot);
}

int main() {
  prk();
  int n;
  cin >> n;
  cout << ans[n] << '\n';
  return 0;
}

Problem E. Yutori

第一反应是把这个序列建立成一个图,每个点到 $i+c$ 后面的点连长度为 $1$ 的边,建边用线段树优化。
但很明显自己胡了假的做法,可能是自己思维比较偏,没有想到正解。

考虑贪心出最多能工作多少天,如果 $>k$ 那么每个点都不需要必须选择。

接下来正向贪心和反向贪心处理出每个工作日的最早期限和最晚期限。

因为每一个期限的边界一定是工作日 o,那么如果某一天需要选择,那么期限 $lf_i=rt_i$

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, k, c, tot;
char s[N];
int lf[N], rt[N];

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> k >> c;
  cin >> (s + 1);
  int right = 0; 
  tot = 0;
  for (int i = 1; i <= n; i++) {
    if (s[i] == 'o' && i >= right) 
      lf[++tot] = i, right = i + c + 1;
  }
  if (tot > k)  
    return 0;
  int left = n; 
  for (int i = n, l = 0; i >= 1; i--)
    if (s[i] == 'o' && i <= left)
      left = i - c - 1, rt[tot - (l++)] = i; 
  for (int i = 1; i <= tot; i++)
    if (lf[i] == rt[i])
      cout << lf[i] << '\n';
  return 0; 
}

Problem F. Division or Substraction

又想歪了,没有想到正解。

题目给了两个操作,显然就是提示我们往这个地方思考。

首先如果当前一个数 $x$ 已经不是要判断的 $k$ 的倍数了,那么在之后的操作中一定不会出现第一种操作。

因此操作的次序一定是先进行第一种操作,再进行第二种操作。

那么我们查询 $k$ 是否对于 $x$ 合法存在以下两种情况:

  • $k\mid x$,那么显然我们只能一直除到除不下去为止,接下里就判断 $x$ 对于 $\mod k$ 的余数是否为 $1$ 即可。
  • $k \not \mid x$,那么只能一直 $-k$,答案就是 $x-1$ 的因子个数。

时间复杂度 $\Theta (\sqrt n)$

注意特判 $1$ 的情况。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<ll> div(ll x) {
  vector<ll> res;
  res.push_back(x);
  for (ll i = 2; i * i <= x; i++)
    if (x % i == 0) {
      res.push_back(i);
      if (i * i != x)
        res.push_back(x / i);
    }
  return res; 
}

int main() {
  ll n; 
  cin >> n;
  if (n == 2) {
    cout << 1 << '\n';
    return 0;
  }
  ll ans = div(n - 1).size();
  vector<ll> a = div(n);
  for (int i = 0; i < a.size(); i++) {
    ll t = n; 
    while (t % a[i] == 0)
      t /= a[i];
    if (t % a[i] == 1)
      ans++;
  }
  cout << ans << '\n';
  return 0;
}

后言

  • 简单题简单想,难题仔细慢慢想。
  • 积极挖掘题目的性质,性质一定是突破口。
  • 胡了假题没有关系,仔细思考后看题解一定要了解思路或者科技。
最后修改:2020 年 04 月 10 日 08 : 48 PM
如果觉得我的文章对你有用,请随意赞赏