牛客寒假算法基础集训营4下

void solve() {
  int n = 1; cin >> n;
    cout << n << endl;
}

pass

思路：（欧拉降幂）
  1. 长度为n的数组，有2^n-1个非空子序列，枚举必然超时。显然，对序列a 排个序对答案是不影响的。
  2. 由于求的是所有子序列的最大值与最小值乘积的乘积，所以我们可以单独考虑最大值与最小值的贡献。

int qmi(int a, int k, int p = mod) {
    int res = 1;
    while(k) {
        if(k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}
int n, a[N];
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        ans = ans * qmi(a[i], qmi(2, i - 1, mod - 1)) % mod;
        ans = ans * qmi(a[i], qmi(2, n - i, mod - 1)) % mod;
    }
    cout << ans << endl;
}

思路：
  1. dp[i][j]：前i张牌，消耗总和mod k 的余数为j时的最大威力是多少
  2. 每个卡选和不选
  f[i][j] = f[i - 1][j], 不选
  f[i][j] = max(f[i][j], b + f[i - 1][(k + j - a % k) % k]), 选

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll f[1010][1010];
int n, k;
int main() {
    cin >> n >> k;
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        int a, b; cin >> a >> b;
        for (int j = 0; j < k; j++) {
            f[i][j] = f[i - 1][j];
            f[i][j] = max(f[i][j], b + f[i - 1][(k + j - a % k) % k]);
        }
    }
    if(f[n][0] <= 0) cout << -1 << endl;
    else cout << f[n][0] << endl;
    return 0;
}

思路：无语了！！！，map超时？？？（用unordered_map吧，害）
  1. 经典题：记录每个质因子的最大次幂
  2. 答案：所有质因子的最大幂次的乘积

const int N = 3e4 + 10;
const int mod = 1000000007;
/*---------------------------------------------------------------------------------------------------------------------------*/
ll qmi(ll a, ll b){ if(!b) return 1ll; if(b&1) return a*qmi(a*a%mod, b>>1)%mod; return qmi(a*a%mod, b>>1)%mod;}
/*---------------------------------------------------------------------------------------------------------------------------*/
unordered_map<int, int> mp;
int prime[N], cnt; 
bool st[N];
void init() {
    for (int i = 2; i <= N; i++) {
        if(!st[i]) prime[cnt++] = i;
        for (int j = 0; prime[j] <= N / i; j++) {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}
void func(int x) {
  // 遍历比合数x小的所有质数
    for (int i = 0; prime[i] < x && i < cnt; i++) {
        int now = x, s = 0;
        while(now % prime[i] == 0) now /= prime[i], s++;
        mp[prime[i]] = max(mp[prime[i]], s); // 存所有质因子的最高次
    }
}
void solve() {
    init(); // 线筛
    int l, r; cin >> l >> r;
    for (int i = l; i <= r; i++) {
        if(st[i]) func(i); // 如果是合数
    }
    if(mp.empty()) { puts("-1"); return; }
    int ans = 1;
    for (auto &[k, v]: mp) ans = ans * qmi(k, v) % mod; // ans
    cout << ans << endl;
}

思路：
  思维题，见代码。

void solve() {
  cin >> n;
    int x = n;
    n <<= 31;
    cout << (x | n) << endl;
}