头像

Yuolhyc


访客:2943

离线:10天前



Yuolhyc
15天前
  1. 很多题目并没有给出数据范围(e.g. LeetCode很多题目就没有)该怎么办?
  2. 面试中想要使用多维vector (e.g. vector<vector<vector<LL>>>),但是经常会感觉初始化很麻烦,需要写很多代码,请问最简单的初始化方式是什么呢?


活动打卡代码 AcWing 320. 能量项链

Yuolhyc
16天前
#include <iostream>

using namespace std;

int n;
const int N = 110, M = N*2;
int w[M];
int f[M][M];

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        int a;
        cin >> a;
        w[i] = w[i+n] = a;
    }

    for (int len=3; len<=n+1; len++) {
        for (int l=1; l+len-1<=n*2; l++) {
            int r = l+len-1;
            for (int k=l+1; k<r; k++) {
                f[l][r] = max(f[l][r], f[l][k]+f[k][r]+w[l]*w[k]*w[r]);
            }
        }
    }

    int ans = 0;
    for (int l=1; l+(n+1)-1<=n*2; l++) {
        int r = l+(n+1)-1;
        ans = max(ans, f[l][r]);
    }
    cout << ans << endl;
}


活动打卡代码 AcWing 1068. 环形石子合并

Yuolhyc
16天前
#include <iostream>
#include <cstring>

using namespace std;

int n;
const int N = 210, M = N*2, INF = 0x3f3f3f3f;
int w[M], s[M];
int f[M][M], g[M][M];

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        int a;
        cin >> a;
        w[i] = w[i+n] = a;
    }

    for (int i=1; i<=2*n; i++) s[i] = w[i] + s[i-1];

    // for (int i=1; i<=2*n; i++) cout << s[i] << " ";
    // cout << endl;

    memset(g, 0x3f, sizeof g);
    memset(f, -0x3f, sizeof f);
    for (int i=1; i<=2*n; i++) {
        f[i][i] = g[i][i] = 0;
    }

    for (int len = 2; len<=n; len++) {
        for (int l=1; l+len-1<=2*n; l++) {
            int r = l+len-1;
            for (int k=l; k<r; k++) {
                f[l][r] = max(f[l][r], f[l][k]+f[k+1][r]+s[r]-s[l-1]);
                g[l][r] = min(g[l][r], g[l][k]+g[k+1][r]+s[r]-s[l-1]);
            }
            // if (len == 36) {
            //     printf("f[%d][%d]=%d\tg[%d][%d]=%d\n", l, r, f[l][r], l, r, g[l][r]);
            // }
        }
    }

    int a=INF, b = -INF;
    for (int l=1; l<=n; l++) {
        int r = l+n-1;
        a = min(a, g[l][r]);
        b = max(b, f[l][r]);
    }
    cout << a << endl;
    cout << b << endl;
}



Yuolhyc
16天前
// f[i][j]: 到达第i个城市,经过j,的所有方案中的最小花销
// f[i][j] = min_k { f[k][j-(1<<k)] + a[k][i] } if (!(j&(1<<i))

#include <iostream>
#include <cstring>

using namespace std;

int n;
const int N = 20;
int g[N][N];
int f[N][1<<N];

int main() {
    cin >> n;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            cin >> g[i][j];

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    for (int j=0; j<(1<<n); j++) { //这个顺序保证遍历到状态j时,j-(1<<k)一定被遍历过
        for (int i=0; i<n; i++) {
            if (j&(1<<i) && (j!=((1<<n)-1) && i!=0)) continue; // 要允许在j=(1<<n)-1时返回原点
            for (int k=0; k<n; k++) {
                if (j&(1<<k)) {
                    f[i][j] = min(f[i][j], f[k][j-(1<<k)] + g[k][i]);
                }
            }
        }
    }

    cout << f[0][(1<<n)-1] << endl;
}


活动打卡代码 AcWing 292. 炮兵阵地

Yuolhyc
17天前
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int n, m;
const int N = 110, M = 11;
int P[N];
int f[2][1<<M][1<<M];
vector<int> state;

int h[1<<M];

int main() {
    cin >> n >> m;
    for (int i=1; i<=n; i++) {
        for (int j=0; j<m; j++) {
            char c;
            cin >> c;
            P[i] <<= 1;
            if (c == 'P') P[i] |= 1;
        }
    }

    for (int j=0; j<(1<<m); j++) {
        bool flag = true;
        for (int p=0; p<m; p++) {
            if ((j>>p & 1) && ((j>>(p+1) &1) || (j>>(p+2)&1))) {
                flag = false;
                break;
            }
        }
        if (flag) state.push_back(j);
    }

    for (int j: state) {
        int w = j;
        int cnt = 0;
        while (w>0) {
            w = w&(w-1);
            cnt++;
        }
        h[j] = cnt;
    }

    memset(f, -0x3f, sizeof f);
    f[0][0][0] = 0;
    for (int i=1; i<=n+2; i++) {
        for (int j: state) {
            for (int k: state) {
                for (int u: state) {
                    if ((u&j)!=0 || (j&k)!=0 || (u&k)!=0) continue;
                    if ((j&P[i-1])==j && (k&P[i])==k) {
                        f[i&1][j][k] = max(f[i&1][j][k], f[i-1 &1][u][j] + h[k]);
                    }
                }
            }
        }
    }

    cout << f[n+2&1][0][0] << endl;
}


活动打卡代码 AcWing 327. 玉米田

Yuolhyc
17天前
#include <iostream>

using namespace std;

int m, n;
const int N = 13, MOD = 1e8;
int fert[N];
int f[N][1<<N];
bool st[1<<N];

struct Edge {
    int j, u;
} edge[1<<N*2];
int ec;

int main() {
    cin >> m >> n;
    for (int i=1; i<=m; i++) {
        for (int j=0; j<n; j++) {
            int a;
            cin >> a;
            fert[i] <<= 1;
            fert[i] |= a;
        }
    }

    for (int j=0; j<(1<<n); j++) {
        st[j] = true;
        int cnt = 0;
        for (int p=0; p<n; p++) {
            if (j>>p & 1) {
                cnt++;
                if (cnt > 1) st[j] = false;
            } else cnt = 0;
        }
    }

    for (int j=0; j<(1<<n); j++) {
        for (int u=0; u<(1<<n); u++) {
            if ((u&j)==0 && st[j]) {
                edge[ec++] = {j, u};
                // printf("u=%d j=%d\n", u, j);
            }
        }
    }

    f[0][0] = 1;
    for (int i=1; i<=m; i++) {
        for (int e=0; e<ec; e++) {
            int j = edge[e].j, u = edge[e].u;
            if ((j&fert[i])==j) {
                f[i][j] = (f[i][j] + f[i-1][u]) % MOD;
            }
        }
    }

    int ans = 0;
    for (int j=0; j<(1<<n); j++) ans = (ans + f[m][j]) % MOD;
    cout << ans << endl;
}


活动打卡代码 AcWing 1064. 骑士

Yuolhyc
18天前
#include <iostream>

using namespace std;

int n, k;
const int N = 12, K = N*N;
typedef long long LL;
LL f[N][K][1<<N];
bool st[1<<N];
struct Edge {
    int j, u;
} edge[1<<N*2];
int ec;
int h[1<<N];

int bitCnt(int x) {
    int res = 0;
    while (x>0) {
        x = x&(x-1);
        res++;
    }
    return res;
}

int main() {
    cin >> n >> k;
    f[0][0][0] = 1;

    for (int j=0; j<(1<<n); j++) {
        st[j] = true;
        int cnt = 0;
        for (int p=0; p<n; p++) {
            if ((j>>p)&1) {
                cnt++;
                if (cnt > 1) st[j] = false;
            } else cnt = 0;
        }
    }

    for (int j=0; j<(1<<n); j++) {
        for (int u=0; u<(1<<n); u++) {
            if ((u&j)==0 && (u<<1 & j)==0 && (u>>1 & j)==0 && st[j])
                edge[ec++] = {j,u};
        }
    }

    for (int j=0; j<(1<<n); j++) h[j] = bitCnt(j);

    for (int i=1; i<=n; i++) {
        for (int c=0; c<=k; c++) {
            for (int e=0; e<ec; e++) {
                int j = edge[e].j, u = edge[e].u;
                int bc = h[j];
                if (c < bc) continue;
                f[i][c][j] += f[i-1][c-bc][u];
            }
        }
    }

    LL ans = 0;
    for (int j=0; j<(1<<n); j++) {
        ans += f[n][k][j];
    }
    cout << ans << endl;
}


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

Yuolhyc
19天前
#include <iostream>
#include <unordered_map>
#include <cstring>

using namespace std;

int n;
const int N = 55, MOD = 1e9 + 7;
char T[N];
int f[N][N];
int ne[N];
typedef long long LL;
unordered_map<LL, int> mp;

LL pack(int a, char c) {
    return ((LL)a << 32) | c;
}

int main() {
    cin >> n >> T+1;
    int len = strlen(T+1);

    ne[1] = 0;
    for (int i=2, j=0; i<=len; i++) {
        while (j>0 && T[i]!=T[j+1]) j = ne[j];
        if (T[i] == T[j+1]) j++;
        ne[i] = j;
    }

    for (int j=0; j<=len; j++) {
        for (char c='a'; c<='z'; c++) {
            int u = j;
            while (u>0 && c!=T[u+1]) u = ne[u];
            if (c == T[u+1]) u++;
            mp[pack(j, c)] = u;
        }
    }

    f[0][0] = 1;
    for (int i=1; i<=n; i++) {
        for (int j=0; j<len; j++) {
            for (char c='a'; c<='z'; c++) {
                int u = mp[pack(j, c)];
                f[i][u] = (f[i][u] + f[i-1][j]) % MOD;
            }
        }
    }
    int ans = 0;
    for (int j=0; j<len; j++) ans = (ans + f[n][j]) % MOD;
    cout << ans << endl;
}


活动打卡代码 AcWing 1058. 股票买卖 V

Yuolhyc
19天前
#include <iostream>
#include <cstring>

using namespace std;

int n;
const int N = 100010, INF = 0x3f3f3f3f;
int s[N];
int f[3], g[3];

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) cin >> s[i];

    f[0] = 0, f[1] = f[2] = -INF;

    for (int i=1; i<=n; i++) {
        memcpy(g, f, sizeof f);
        f[0] = max(g[0], g[2]);
        f[1] = max(g[1], g[0]-s[i]);
        f[2] = g[1] + s[i];
    }

    cout << max(f[0], f[2]) << endl;
}


活动打卡代码 AcWing 1057. 股票买卖 IV

Yuolhyc
19天前
#include <iostream>
#include <cstring>

using namespace std;

int n, k;
const int N = 100010, K = 110;
int s[N];
int f[K][2];

int main() {
    cin >> n >> k;
    for (int i=1; i<=n; i++) cin >> s[i];

    memset(f, -0x3f, sizeof f);
    f[0][1] = 0;

    int ans = 0;
    for (int i=1; i<=n; i++) {
        for (int j=k; j>=1; j--) {
            f[j][0] = max(f[j][0], f[j-1][1]-s[i]);
            f[j][1] = max(f[j][1], f[j][0]+s[i]);
            ans = max(ans, f[j][1]);
            ans = max(ans, f[j][0]);
        }
    }

    cout << ans << endl;
}