数字涡旋

可以发现, 可以差成一个__| 形状的东西, 而且是有顺序的, 找到那一行后输出坐标

#include<bits/stdc++.h>

using namespace std;

int op, n, T;

void S(){
  cin >> n;
  op = sqrt(n);
  op += (op * op != n);
  n = op * op - n + 1;
  if(op & 1){
    if(n <= op){
      cout << n << ' ' << op << '\n';
    }
    else{
      cout << op << ' ' << op - (n - op) << '\n';
    }
  }
  else{
    if(n <= op){
      cout << op << ' ' << n << '\n';
    }
    else{
      cout << op - (n - op) << ' ' << op << '\n';
    }
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  freopen("spiral.in", "r", stdin);
  freopen("spiral.out", "w", stdout);
  for(cin >> T; T--; S()){
  }
  return 0;
}

时间复杂度 \(O(T)\)

空间复杂度 \(O(1)\)

潦草急就

如果对于 k 进制下每一位考虑, 可以发现构成了一个循环然后推式子就可以了

从右往左第 \(i\) 位每 \(k^{i - 1}\) 次方一个循环

#include<bits/stdc++.h>

using namespace std;

const int N = 100, mod = 2027;

long long n, oo, y, ok;
long long k, ans[N], bpow[N], cnt, T, s;

void S(){
  cin >> n >> k;
  for(int i = 0; i < k; ++i){
    ans[i] = 0;
  }
  ok = n + 1;
  for(long long i = 1; i <= n; i *= k){
    oo = ok / (i * k) * i, y = (ok % (i * k)) / i;
    ans[0] = (ans[0] + oo), ans[k] = ((ans[k] - oo));
    if(ok % (i * k)){
      if((ok % (i * k)) % i){
        ans[0] = (ans[0] + i), ans[y] = ((ans[y] - i));
        ans[y] = (ans[y] + (ok % (i * k)) % i);
        ans[y + 1] = ((ans[y + 1] - (ok % (i * k)) % i));
      }
      else{
        ans[0] = (ans[0] + i), ans[y] = ((ans[y] - i));
      }
    }
  }
  for(ok = n, n = 0; ok; ok /= k, n++){
  }
  bpow[0] = 1;
  for(int i = 1; i <= n; ++i){
    bpow[i] = 1ll * bpow[i - 1] * k;
  }
  cnt = 0;
  for(int i = 2; i <= n; ++i){
    cnt = (cnt + 1ll * (i - 1) * (1ll * (k - 1) * bpow[n - i]));
  }
  cnt += (n - 1);
  cnt %= mod;
  cout << ((ans[0] - cnt) % mod + mod) % mod << ' ';
  for(int i = 1; i < k; ++i){
    ans[i] = ((ans[i] + ans[i - 1]) % mod + mod) % mod;
    cout << ans[i] << ' ';
  }
  cout << '\n';
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  freopen("write.in", "r", stdin);
  freopen("write.out", "w", stdout);
  for(cin >> T; T--; S()){
  }
  return 0;
}

时间复杂度 \(O(T \cdot (k + log_k n))\)

空间复杂度 \(O(k)\)

取模常数过大, 答案不会爆 long long 所以可以最后再取模

柳暗花明

先把详细取整差掉, 答案肯定小于差后

ans = \(x / 2^{r - l + 1} + a_l / 2^{r - l + 1} + a_{l - 1} / 2^{r - l} + \dots a_r / 2\)

对于答案 \(/ 2^100\) 的答案, 贡献很小, 又有向下取整, 所以不用考虑

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, q, a[N], x, l, r;

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  freopen("curve.in", "r", stdin);
  freopen("curve.out", "w", stdout);
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  cin >> q;
  while(q--){
    cin >> x >> l >> r;
    for(int i = max(l, r - 100); i <= r; ++i){
      x = (x + a[i]) / 2;
    }
    cout << x << '\n';
  }
  return 0;
}

时间复杂度 \(O(n + 100q)\)

空间复杂度 \(O(n)\)

移动硬币

\(w_i \le 1000000\)

考虑取模状态设计的 dij

状态 \((i, sum)\) 表示构成 \(\bmod a_1\) 后为 \(i\) 的最小 \(sum\), 这样, \(sum + k \cdot a_1\) 都可以被构造出来

转移 \((i, sum) \to ((i + a_j) \bmod a_1, sum + a_j)\)

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

struct Node{
  int u;
  long long d;
};

struct Edge{
  int u, w;
};

struct cmp{
  bool operator()(const Node &i, const Node &j){
    return i.d > j.d;
  }
};

priority_queue<Node, vector<Node>, cmp>pq;
int a[100], n;
bool vis[N];
long long dist[N], l, ans;

void dij(){
  for(int i = 1; i < a[1]; ++i){
    dist[i] = l + 1;
  }
  pq.push({0, 0});
  while(pq.size()){
    auto [u, d] = pq.top();
    pq.pop();
    if(vis[u]){
      continue;
    }
    vis[u] = 1;
    for(int i = 1; i <= n; ++i){
      auto v = (u + a[i]) % a[1], w = a[i];
      if(dist[v] > dist[u] + w){
        dist[v] = dist[u] + w;
        pq.push({v, dist[v]});
      }
    }
  }
}

int main(){
  freopen("coin.in", "r", stdin);
  freopen("coin.out", "w", stdout);
  cin >> n >> l;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  sort(a + 1, a + n + 1, [](const int &i, const int &j){  return i > j;});
  dij();
  for(int i = 0; i < a[1]; ++i){
    if(dist[i] <= l){
      ans += (l - dist[i]) / a[1] + 1;
    }
  }
  cout << ans - 1;
  return 0;
}

时间复杂度 \(O(n \cdot a_1 \log_2 a_1)\)

空间复杂度 \(O(a_1 + n)\)