头像

小蓝




离线:1小时前


最近来访(21)
用户头像
yut2020
用户头像
junjun
用户头像
不拼一把怎么行
用户头像
castlecaffe
用户头像
IndexYang
用户头像
j5zslhw
用户头像
广西师范大学漓江学院_第一届ACC决赛
用户头像
Dream_56
用户头像
箫骋
用户头像
hei103
用户头像
月亮人无忧
用户头像
RyanMoriarty
用户头像
bobo2010
用户头像
喵喵酱
用户头像
小朋友没有武德
用户头像
ByteTV
用户头像
zombotany
用户头像
乌搏猿

活动打卡代码 AcWing 3625. 幂次方

小蓝
1天前
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

//const int N =  + 10;
int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = (ll)res * t % p;
        t = (ll)t * t % p;
        k >>= 1;
    }
    return res;
}
ll x, n;
ll mod = 233333;
void solve() {
    cin >> x >> n;
    cout << qmi(x, n, mod);
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
//  cin >> T;
    while(T -- ) {
        solve();
    }
    return 0;
}






小蓝
14天前
最短路径中会包含重复点吗 就是一个点经过了两次
还是包含了重复点就是有负权回路了



小蓝
4个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N][N];
int v[N], w[N];
int n, m;

int main()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for(int i = n; i >= 1; i--) {
        for(int j = 0; j <= m; j++) {
            f[i][j] = f[i + 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    }

    int d = m;
    for(int i = 1; i <= n; i++) {
        if(d >= v[i] && f[i][d] == f[i + 1][d - v[i]] + w[i]) {
            cout << i << " ";
            d -= v[i];
        }
    }

    return 0;
}




小蓝
4个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;
int n, m, root;
int h[N], e[N], ne[N], idx;
int w[N], v[N];
int f[N][N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {

    for(int i = h[u]; ~i; i = ne[i]) {
        int son = e[i];
        dfs(son);
        for(int j = m - v[u]; j >= 0; j--) {
            for(int k = 0; k <= j; k++) {
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
            }
        }
    }
    for(int i = m; i >= v[u]; i--) f[u][i] = f[u][i - v[u]] + w[u];
    for(int i = 0; i < v[u]; i++) f[u][i] = 0;

}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[i] = a, w[i] = b;
        if(c == -1) root = i;
        else add(c, i);
    }

    dfs(root);

    cout << f[root][m];

    return 0;
}




小蓝
4个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 12, M = 1 << 12;
// 表示当前是第i列, 且第i列的状态是j的集合
// 1表示当前列需要填格子, 0表示不需要
long long f[N][M];
bool st[M];
int n, m;

int main() {

    while(cin >> n >> m) {
        if(!n && !m) break;
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for(int i = 0; i < 1 << n; i++) {
            st[i] = true;
            int cnt = 0;
            for(int j = 0; j < n; j++) {
                if(i >> j & 1) {
                    if(cnt & 1) st[i] = false;
                    cnt = 0;
                }else cnt++;
            }
            if(cnt & 1) st[i] = false;
        }

        // 从0到m-1
        for(int i = 1; i <= m; i++) {
            for(int j = 0; j < 1 << n; j++) {   // 枚举第i列的放法
                for(int k = 0; k < 1 << n; k++) {   // 枚举i-1列的放法
                    if((j & k) == 0 && st[j | k]) {
                        f[i][j] += f[i - 1][k];
                    }
                }
            }
        }
        cout << f[m][0] << endl;
    }

    return 0;
}



活动打卡代码 AcWing 1052. 设计密码

小蓝
4个月前
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int n;
char s[55];
int ne[55];
int f[55][55];
// kmp + 状态机DP 用kmp的匹配长度来当状态的点
int main() {
    cin >> n;
    cin >> s + 1;
    int m = strlen(s + 1);
    for(int i = 2, j = 0; i <= m; i++) {
        while(j && s[j + 1] != s[i]) j = ne[j];
        if(s[j + 1] == s[i]) j ++;
        ne[i] = j;
    }

    f[0][0] = 1;
    // 从前i个字符中 且当前已经匹配了长度为j的集合
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < m; j++) {
            // 枚举第i个字符是多少
            for(char c = 'a'; c <= 'z'; c++) {
                int u = j;
                while(u && c != s[u + 1]) u = ne[u];
                if(c == s[u + 1]) u++;
                if(u < m) {
                    f[i][u] = (f[i][u] + f[i - 1][j]) % mod;
                }
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < m; i++) {
        ans = (ans + f[n][i]) % mod;
    }
    cout << ans << endl;

    return 0;
}



活动打卡代码 AcWing 282. 石子合并

小蓝
4个月前
#include<bits/stdc++.h>
using namespace std;

int n;
int a[305];
int f[305][305];
int sum[305];
// 把第i堆到第j堆合并成一堆的集合 最小值
// 集合划分以最后一次合并的下标划分 (从i到j-1)
int main() {
    memset(f, 0x3f, sizeof f);
    cin >> n;
    for(int i = 0; i <= n; i++) f[i][i] = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
    for(int len = 1; len <= n; len++) {
        for(int l = 1; l < n; l++) {
            int j = l + len - 1;
            if(j > n) continue;
            for(int k = l; k <= j - 1; k++) {
                f[l][j] = min(f[l][j], f[l][k] + f[k + 1][j] + sum[j] - sum[l - 1]);
            }    
        }
    }
    cout << f[1][n];    
    return 0;
}



活动打卡代码 AcWing 5. 多重背包问题 II

小蓝
4个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 21000;
int f[N];
int idx;
int n, m;
int v[N], w[N];
// 二进制优化(二进制拼凑) 然后 01背包
int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        int V, W, S;
        cin >> V >> W >> S;
        int t = 1;
        while(S >= t) {
            v[++idx] = t * V;
            w[idx] = t * W;
            S -= t;
            t = t * 2;
        }
        if(S) {
            v[++idx] = S * V;
            w[idx] = S * W;
        }
    }

    for(int i = 1; i <= idx; i++) {
        for(int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout << f[m];

    return 0;
}



活动打卡代码 AcWing 3. 完全背包问题

小蓝
4个月前
#include<bits/stdc++.h>
using namespace std;

int f[1010];
int n, m;
int v, w;
int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> v >> w;
        for(int j = v; j <= m; j++) {
            f[j] = max(f[j - v] + w, f[j]);
        }
    }

    cout << f[m];

    return 0;
}



活动打卡代码 AcWing 1296. 聪明的燕姿

小蓝
4个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n;
int primes[N], idx;
bool st[N];
vector<int> ve;
void oula(int x) {
    for(int i = 2; i <= x; i++) {
        if(!st[i]) primes[idx++] = i;
        for(int j = 0; primes[j] <= x / i; j++) {
            st[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
bool isPrime(int x) {
    for(int i = 2; i <= x / i; i++)
        if(x % i == 0) return false;
    return true;
}

void dfs(int u, int ans, int num) {

    if(num == 1) {
        ve.push_back(ans);
        return;
    }

    if(num - 1 > (u ? primes[u-1] : 0) && isPrime(num - 1)) {
        ve.push_back(ans * (num - 1));
    }

    for(int i = u; primes[i] <= num / primes[i]; i++) {
        int p = primes[i];
        for(int j = 1+p, t = p; j <= num; t = t * p, j = j + t) {
            if(num % j == 0) {
                dfs(i + 1, ans * t, num / j);
            }
        }
    }

}



int main() {
    oula(N - 1);

    while(cin >> n) {
        ve.clear();
        dfs(0, 1, n); 

        cout << ve.size() << endl;
        sort(ve.begin(), ve.end());
        if(ve.size()) {
            for(int i = 0; i < ve.size(); i++) cout << ve[i] << " ";     
            cout << endl;            
        }

    }

    return 0;
}