#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 7;
int dp[2][maxn], q[maxn]; // dp 为滚动数组， q为优先队列辅助数组
#define calc(t,i) (dp[t^1][q[i]]+((k-q[i])/v)*w)
int main() {
    int n, m;
    cin >> n >> m;
    int t = 0;
    for (int i = 1; i <= n; i++) {
        int v, w, s;
        scanf("%d %d %d", &v, &w, &s);
        t ^= 1; //数组滚动
        for (int j = 0; j < v; j++) {
            int l = 1, r = 0;
            for (int k = j ; k <= m; k += v) {
                while (l <= r && (k-q[l])/v > s) l++; // 排除太远的
                if(l<=r) dp[t][k] = max(dp[t^1][k], calc(t,l));
                while (l <= r && dp[t ^ 1][q[r]] - (q[r] - j) / v * w <= dp[t ^ 1][k] - (k - j) / v * w) r--;//消除距离影响
                q[++r] = k;
            }
        }
    }
    cout << dp[t][m] << endl;
    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;
const int N = 1e5 + 5;
int f[N][3];

int main() {
  int n;
  cin >> n;
  f[0][1] = -0x3f3f3f3f3f;
  int x;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    f[i][0] = max(f[i - 1][0], f[i - 1][2]);
    f[i][1] = max(f[i - 1][1], f[i - 1][0] - x);
    f[i][2] = f[i - 1][1] + x;
  }
  cout << max(f[n][0], f[n][2]) << endl;
  return 0;
}

#include <iostream>
#include <cstring>

using namespace std;
const int N = 1e5 + 5;
int f[N][107][2]; // 可以像背包一样省略一维

int main() {
  int n, m;
  cin >> n >> m;
  memset(f, -0x3f, sizeof f);
  for (int i = 0; i <= n; i++) {
    f[i][0][0] = 0;
  }

  int x;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    for (int j = 1; j <= m; j++) {
      f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + x);
      f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - x);
    }
  }
  int res = 0;
  for (int i = 1; i <= m; i++) res = max(res, f[n][i][0]);
  cout << res << endl;
  return 0;
}

#include <cstring>
#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int arr[N], f[N];

// 普通解法 f[i] = max(f[i], f[i - 2] + arr[i])
int main() {
  int t, n;
  cin >> t;
  while (t--) {
    cin >> n;
    memset(f, 0, sizeof f);
    for (int i = 2; i <= n + 1; i++) {
      cin >> arr[i];
      f[i] = max(f[i - 1], f[i - 2] + arr[i]);
    }
    cout << f[n + 1] << endl;
  }
  return 0;
}

#include <cstring>
#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int arr[N], f[N][2];

// 状态机解法 0表示不选，1表示选。
// 有0->0，0->1, 1-> 0
// f[i,0] = max(f[i-1, 0], f[i-1, 1])
// f[i, 1] = f[i - 1, 0] + arr[i]
int main() {
  int t, n;
  cin >> t;
  while (t--) {
    cin >> n;
    memset(f, 0, sizeof f);
    for (int i = 2; i <= n + 1; i++) {
      cin >> arr[i];
      f[i][0] = max(f[i - 1][0], f[i - 1][1]);
      f[i][1] = f[i - 1][0] + arr[i];
    }
    cout << max(f[n + 1][0], f[n + 1][1]) << endl;
  }
  return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 2.5e4 + 5;

int arr[N];
bool st[N];
int main(){
    int t, n;
    cin >> t;
    while (t --){
        memset (st, false, sizeof st);

        cin >> n;
        for (int i = 0; i < n; i ++) {
            cin >> arr[i];
        }
        sort(arr, arr + n);

        int res = 0;
        st[0] = true;
        for (int i = 0; i < n; i ++){ 
            if (!st[arr[i]]) res ++;
            for (int j = arr[i]; j <= arr[n - 1]; j ++){
                st[j] |= st[j - arr[i]];
            }
        }

        cout << res << endl;
    }
    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 11;

int f[N][10];

void init()
{
    for (int i = 0; i <= 9; i ++ ) f[1][i] = 1;

    for (int i = 2; i < N; i ++ )
        for (int j = 0; j <= 9; j ++ )
            for (int k = 0; k <= 9; k ++ )
                if (abs(j - k) >= 2)
                    f[i][j] += f[i - 1][k];
}

int dp(int n)
{
    if (!n) return 0;

    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0;
    int last = -2;
    for (int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for (int j = i == nums.size() - 1; j < x; j ++ )
            if (abs(j - last) >= 2)
                res += f[i + 1][j];

        if (abs(x - last) >= 2) last = x;
        else break;

        if (!i) res ++ ;
    }

    // 特殊处理有前导零的数
    for (int i = 1; i < nums.size(); i ++ )
        for (int j = 1; j <= 9; j ++ )
            res += f[i][j];

    return res;
}

int main() {
    init();

    int l, r;
    cin >> l >> r;
    cout << dp(r) - dp(l - 1) << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 12, M = 105;
int f[N][N][M];
int a, b, p;

int mod(int x, int y) {
    return (x % y + y) % y;
}

void init(){
    memset(f, 0, sizeof f);
    for (int i = 0; i <= 9; i ++) f[1][i][i % p] ++;

    for (int i = 2; i < N; i ++){
        for (int j = 0; j <= 9; j ++) {
            for (int k = 0; k < p; k ++){
                for (int x = 0; x <= 9; x ++) {
                    f[i][j][k] += f[i - 1][x][mod(k - j, p)];
                }
            }
        }
    }
}

int dp(int x){
    vector<int> nums;
    while (x) nums.push_back(x % 10), x /= 10;

    int res = 0, last = 0; // last 前面位数的和
    for (int i = nums.size() - 1; i >= 0; i --) {
        int x = nums[i];
        for (int j = 0; j < x; j ++) {
            res += f[i + 1][j][mod(-last, p)];
        } 
        last += x;
        if (!i && last % p == 0) res ++; 
    }
    return res;
}

int main(){

    while (cin >> a >> b >> p)init(),cout << dp(b) - dp(a) << endl;
    return 0;
}

递归生成码
因为这一层是由上一层递推来的，所以直接递归处理
1. 如果k 小于 $2^{n-1}$, 说明是第一个方式构成，直接+0
2. 否则就去找k-$2^{n-1}$大，因为倒序所以是找$2^{n-1}$ - (k - $2^{n-1}$) - 1 ==> $2^n$ - k - 1

#include <iostream>

using namespace std;
typedef unsigned long long ULL;

string f(ULL n, ULL k){
    if (!n) return "";
    if ( (1ull << n - 1) > k) return "0" + f(n - 1, k);
    unsigned long long  t = (1ull << n) - k - 1; 
    if (n == 64) t = -k -1;// 移出去了，可能会出现异常是0或1不确定，特判一下
    return "1" + f(n - 1, t);
}

int main(){
    ULL n, k;
    cin >> n >> k;
    cout << f(n, k) << endl;
    return 0;
}

异或转换

代码参考 霁

#include <iostream>

using namespace std;

int main(){
    unsigned long long n, k;
    cin >> n >> k;
    unsigned long long ge = k ^ (k >> 1);
    while (~--n) {
        cout << (ge >> n & 1 );
    }
    return 0;
}

直接动态规划o(nm)

f[i][j] = f[i - 1][j] + f[i][j - 1]， 当i，j不同时为奇数时;

#include <iostream>

using namespace std;
int f[35][35];
int main(){
    int n, m;
    cin >> n >> m;
    f[0][1] = 1;
    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j++){
            if (j & 1 | i & 1)
                f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

#include <iostream>

using namespace std;
const int N = 1005;
int phi[N], primes[N], tot;
bool st[N];
void get_phi(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[tot++] = i;
            phi[i] = i - 1;
        }

        for (int j = 0; primes[j] * i <= n; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }
}

long long phi_sum[N];
void get_phi_sum(int n) {
    for (int i = 1; i <= n; i++) phi_sum[i] += phi_sum[i - 1] + phi[i];
}

int main() {
    int t, n, cnt = 1;
    scanf("%d", &t);
    get_phi(1000), get_phi_sum(1000);
    while (t--)
    {
        scanf("%d", &n);
        printf("%d %d %lld\n", cnt++, n, phi_sum[n] * 2 + 1);
    }


    return 0;
}