头像

VALUE_5




离线:3天前


最近来访(16)
用户头像
Rainbow_0
用户头像
Foraino0267
用户头像
用户头像
瞳星结
用户头像
IntroWonder
用户头像
辛钦大数定律
用户头像
潘潘_the_panda
用户头像
RyanMoriarty
用户头像
Aslan_Thirteen
用户头像
星逐月丶
用户头像
NBxiang
用户头像
chaoxi
用户头像
Lingmutian
用户头像
11616195
用户头像
test886


VALUE_5
5天前

内存超了,有大佬帮看看有什么问题吗,菜鸟感谢

#include<iostream>
using namespace std;
const int N = 2 * 10;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];
int n;

void dfs(int x, int y, int s){ // y, y代表当前格子的坐标,s表示已经放置的皇后个数
    if(y > n) y = 1, x++;
    if(x > n){
        if(s == n){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    cout << g[i][j];
                }
                cout << endl;
            }
            cout << endl;
            return;
        }


    }

    // 不放置皇后,直接到下一个格子
    dfs(x, y + 1, s);

    // 放置皇后
    if(!row[x] && !col[y] && !dg[x + y] && !udg[x + n - y]){
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x + n - y]  = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[x + n - y]  = false;
        g[x][y] = '.';
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            g[i][j] = '.';
        }
    }
    dfs(1, 1, 0);
    return 0;
}



VALUE_5
7天前
// ans = c(2n, n) / (n + 1)
// 等价 ans = 2n! * (n!)^(-1) * (n!)^(-1) * (n + 1)^(-1)
#include<iostream>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int n;
int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL) a * a % p;
    }
    return res;
}
int main(){
    cin >> n;
    int a = 2 * n;
    int b = n;
    int res = 1;
    for(int i = 1; i <= a; i++) res = (LL)res * i % mod;
    for(int i = 1; i <= b; i++) res = (LL)res * qmi(i, mod - 2, mod) % mod * qmi(i, mod - 2, mod) % mod;
    res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 887. 求组合数 III

VALUE_5
7天前

递归一定要先写边界。

//lucas(a, b) = (LL)c(a % p, b % p) * lucas(a / p, b / p) % p;
#include<iostream>
typedef long long LL;
using namespace std;
int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}
int C(int a, int b, int p){
    if(b > a) return 0;
    int res = 1;
    for(int i = 1, j = a; i <= b; i++, j--){
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2, p) % p;
    }
    return res;
}
int lucas(LL a, LL b, int p){
    if(a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
int main(){
    int n;
    cin >> n;
    while(n--){
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}



VALUE_5
7天前

dfw的我来一个map的,也不需要遍历容器。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
unordered_map<string, int> schoolmate;
int n, m;
int cnt;
int main()
{
    cin >> n;
    while(n--){
        string id;
        cin >> id;
        schoolmate[id] = 1;
    }
    cin >> m;
    string max_schoolmate, max_com;
    string max_age_schoolmate ="99999999";
    string max_age_com = "99999999";
    while (m -- ){
        string com_id;
        string age;
        cin >> com_id;
        age = com_id.substr(6, 8);
        if(age < max_age_com){
            max_com = com_id;
            max_age_com = age;
        }
        auto iter = schoolmate.find(com_id);
        if(iter != schoolmate.end()){
            cnt++;
            if(age < max_age_schoolmate){
                max_schoolmate = com_id;
                max_age_schoolmate = age;
            }

        }
    }

    if(cnt){
        cout << cnt << endl;
        cout << max_schoolmate << endl;

    }else{
        cout << cnt << endl;
        cout << max_com << endl;
    }

    return 0;
}


活动打卡代码 AcWing 878. 线性同余方程

VALUE_5
29天前
#include<iostream>
using namespace std;

int a, b, m;
int x, y;
typedef long long LL;
int exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main(){
    int n;
    cin >> n;
    while(n--){
        scanf("%d%d%d", &a, &b, &m);
        int d = exgcd(a, m, x, y);
        if(b % d == 0) printf("%d\n", ((LL)x * b / d) % m );
        else printf("impossible\n");

    }
    return 0;
}


活动打卡代码 AcWing 876. 快速幂求逆元

VALUE_5
29天前
#include<iostream>
using namespace std;

int a, p;
int n;
typedef long long LL;

int qmi(int a, int b, int p){
    int res = 1;
    while(b){
        if(b & 1) res = (LL)res * a % p;
        b = b >> 1;
        a = (LL)a * a % p;
    }
    return res;
}
int main(){
    cin >> n;
    while(n--){
        scanf("%d%d", &a, &p);
        if(a % p == 0){
            cout << "impossible" << endl;
        }else{
           cout << qmi(a, p - 2, p) << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 875. 快速幂

VALUE_5
29天前
#include<iostream>
using namespace std;
int a, b, p;
typedef long long LL;
int qmi(int a, int b, int p){
    int res = 1;
    while(b){
        if(b & 1) res = (LL)res * a % p;
        b = b >> 1;
        a = (LL) a * a % p;
    }
    return res;
}
int main(){
    int n;
    cin >> n;
    while(n--){
        scanf("%d%d%d", &a, &b, &p);
        cout << qmi(a, b, p) << endl;
    }

    return 0;
}



VALUE_5
1个月前

主要是时间复杂度O(sqrt(N))

|:代表整除

假如d | n ,那么 n/d | n,d <= n / d,即d^2 <= n => d <= sqrt(n)

注:d是从小到大枚举

bool is_primes(int n){
    if(n < 2) return false;
    for(int i = 2; i <= n / i; i++){
        if(n % i == 0) return false;
    }
    return true;
}



VALUE_5
1个月前

快速幂

对于a^k % p快速求出结果:

本质是:对底数a的反复平方,因为我们知道任何一个整数都可以使用2进制来表示

例如对于指数k:
k = 2^0 + 2^1 + 2^2......而
a^k = a^(2^x1) * a^(2^x2) * a^(2^x3) * ....
即:a^k = a^(2^x1 + 2^x2 + 2^x3 + …)

a^k = a^(x1x2x3..)(2)




VALUE_5
1个月前
#include<iostream>
using namespace std;
const int N = 1e6 +10;
int primes[N], cnt, phi[N];
bool st[N];
int n, x;

int main(){
    cin >> n;
    phi[1] = 1;
    for(int i = 2; i <= n; i++){
        if(!st[i]){
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0; primes[j] <= n / i; j++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    long long res = 0;

    for(int i = 1; i <= n; i++){
        res += phi[i];
    }
    cout << res << endl;
    return 0;

}