Yuolhyc

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

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;
}


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;
}


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;
}


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;
}


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;
}


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;
}


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;
}


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;
}