CodeForces - 1469D - Ceil Divisions (思维+数学)

简介: 笔记

Ceil Divisions


题意

3.png

思路

4.png

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
using namespace std;
typedef  long long LL;
typedef pair<int, int>PII;
inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
const int N = 200010;
int n;
int a[N];
vector<int>v;
void solve() {
  cin >> n;
  v.clear();
  int cnt = 0;
  if (n <= 32) {
    for (int i = 3; i < n; ++i) {
      v.push_back(i);
      v.push_back(i + 1);
      cnt++;
    }
    int t = n;
    while (t != 1) {
      //printf("%d %d\n", n, 2);
      v.push_back(n);
      v.push_back(2);
      cnt++;
      t = ceil(double(t / 2.0));
      //cout << "t == " << t << endl;
    }
  }
  else {
    int x = ceil(pow(n, 1.0 / 5.0));
    for (int i = 3; i < n; ++i) {
      if (i != x) {
        //printf("%d %d\n", i, i + 1);
        v.push_back(i);
        v.push_back(i + 1);
        cnt++;
      }
    }
    int t = n;
    while (t != 1) {
      //printf("%d %d\n", n, x);
      v.push_back(n);
      v.push_back(x);
      cnt++;
      t = ceil(double((t * 1.0) / (x * 1.0)));
    }
    t = x;
    while (t != 1) {
      //printf("%d %d\n", x, 2);
      v.push_back(x);
      v.push_back(2);
      cnt++;
      t = ceil(double(t / 2.0));
    }
  }
  cout << cnt << endl;
  for (int i = 0; i < v.size(); ++i) {
    printf("%d ", v[i]);
    if (i & 1)cout << endl;
  }
}
int main() {
  int t; cin >> t;
  while(t--)
    solve();
  return 0;
}
目录
相关文章
|
7月前
|
算法
Plant(快速幂+数学分析(没想到吧,数学无处不在))
Plant(快速幂+数学分析(没想到吧,数学无处不在))
73 0
A. Theatre Square(数学思维)
A. Theatre Square(数学思维)
74 0
|
人工智能
Codeforces1491——C.Pekora and Trampoline(差分思维+树状数组)
Codeforces1491——C.Pekora and Trampoline(差分思维+树状数组)
110 0
Codeforces1491——C.Pekora and Trampoline(差分思维+树状数组)
codeforces319——B. Psychos in a Line(思维+单调栈)
codeforces319——B. Psychos in a Line(思维+单调栈)
103 0
codeforces319——B. Psychos in a Line(思维+单调栈)
CodeForces - 1312D Count the Arrays(思维+组合数学)
CodeForces - 1312D Count the Arrays(思维+组合数学)
129 0
|
人工智能
[Codeforces 1589D] Guess the Permutation | 交互 思维 二分
题意 多组输入:{ 每组给出一个n,有一个长度为n的数列,在开始的时候a i = i ,有三个数i , j , k 数列反转了 [i,j−1] [j,k] 要求出这三个数,可以对系统进行询问 [ l , r ] 区间内 逆序对 的个数,会返回这个值 }
128 0
[Codeforces] 1557 C Moamen and XOR(组合数学)
题意: 用 < 2k的数填充到长度为n的数组中,要使得数组中所有数& >= ^,问方案数 显然,当k == 1的时候,答案为1,只有当所有的数全为1的情况才可以满足题意 对于其他的情况{ 用小于2k的数进行填充,那么说明填充的数字的二进制位数最多可以有k kk位, 从数的个数的角度来说,奇数个1^ 之后的结果是1,偶数个1^ 之后的结果是0,而对于0来讲,不管多少个0,^起来结果都是0 只要有一个0,那么说这一位上&之后就是0,而为了让^为0,那么只能够选择偶数个1 如果某一位上&为1,那么^为1的情况需要讨论n的奇偶性
131 0