Nan97

$\color{red}{不开 long long 见祖宗}$

6945

LiyeeW

konkayy

rushhhhh
xiusike1
simonhan
hnust_xiaoshun

whlbest

Jackyc
D_deBUG
NBxiang

Nan97
4天前
#include <vector>
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << 10, K = 110;

int n, m;
vector<int> state;
int cnt[M];
LL f[N][K][M];
bool check(int a) {
for(int i = 0; i < n; i ++ )
if(a >> i & 1 && a >> i + 1 & 1)
return false;
return true;
}

int count(int a) {
int res = 0;
for(int i = 0; i < n; i ++ )
if(a >> i & 1)
res ++;
return res;
}

int main()
{
cin >> n >> m;
for(int i = 0; i < 1 << n; i ++ )
if(check(i)) {
state.push_back(i);
cnt[i] = count(i);
}

int len = state.size();
for(int i = 0; i < len; i ++ )
for(int j = 0; j < len; j ++ ) {
int a = state[i], b = state[j];
if((a & b) == 0 && check(a | b)) {
}
}

f[0][0][0] = 1;
/*
f[i][j][k]表示前i行有了j个国王并且状态为k的方案数。
f[i][j][k] 可以由 f[i - 1][j - c][head[k]] 转移。
*/
for(int i = 1; i <= n + 1; i ++ )
for(int j = 0; j <= m; j ++ )
for(int a = 0; a < len; a ++ )
int c = cnt[state[a]];
if(j >= c)
f[i][j][a] += f[i - 1][j - c][b];
}
cout << f[n + 1][m][0];

return 0;
}



Nan97
4天前
#include <iostream>
#include <cstring>
#include <algorithm>
#define mod(x) (x)%MOD
using namespace std;

const int N = 55, MOD = 1e9 + 7;

int n;
int f[N][N], ne[N];
string s;

int main() {
cin >> n >> s;
int m = s.size();
s = " " + s;
for(int i = 2, j = 0; i <= m; i ++ ) {
while(j && s[i] != s[j + 1]) j = ne[j];
if(s[i] == s[j + 1]) j ++;
ne[i] = j;
}

f[0][0] = 1;
for(int i = 0; i < n; i ++ )
for(int j = 0; j < m; j ++ )
for(char k = 'a'; k <= 'z'; k ++ ) {
int u = j;
while(u && k != s[u + 1]) u = ne[u];
if(k == s[u + 1]) u ++;
if(u < m)
f[i + 1][u] = mod(f[i][j] + f[i + 1][u]);
}
int res = 0;
for(int i = 0; i < m; i ++ )
res = mod(res + f[n][i]);
cout << res << endl;

}



Nan97
6天前
#define all(a) a.begin(), a.end()
class Solution {
public:
int maxmiumScore(vector<int>& cards, int cnt) {
vector<int> a, b;
for(int x: cards)
if(x & 1) b.push_back(x);
else a.push_back(x);
sort(all(a)); reverse(all(a));
sort(all(b)); reverse(all(b));
int ans = 0; int i = 0, j = 0;
if(cnt & 1) ans += a[i ++];
cnt /= 2;
for(int k = 0; k < cnt; i ++ ) {

if(a[i] + a[i + 1] >= a[j] + a[j + 1]) {
ans += a[i] + a[i + 1];
i += 2;
}
else {
ans += b[j] + b[j + 1];
j += 2;
}
}

}
};


Nan97
7天前


//
const int N = 1 << 12;

class Solution {
public:
int f[N] = {0};
bool check(string p) {
int len = p.size();
for(int i = 0; i <= len - 1 - i; i ++ )
if(p[i] != p[len - 1 - i]) return false;
return true;
}
int maxProduct(string s) {
int n = s.size(), ans = -0x3f3f3f3f;
int px = 1 << n;
for(int i = 0; i < px; i ++ ) {
string res = "";
for(int j = 0; j < n; j ++ )
if(i >> j & 1)
res.push_back(s[j]);
if(check(res))
f[i] = res.size();
}
for(int i = 0; i < px; i ++ )
for(int j = i; j; j = (j - 1) & i)
ans = max(ans, f[j] * f[i - j]);

return ans;
}
};


#### @mrk

class Solution {
public:
int n;
int ans = 0;
string p;
bool inline judge(string x) {
int len = x.size();
for(int i = 0; i <= len - i - 1; i ++ )
if(x[i] != x[len - i - 1]) return false;
return true;
}

void dfs(int u, string a, string b) {
if(u == n) {
int res = (int)a.size() * (int)b.size();
if(res <= ans) return;// 不加就TLE ...
if(judge(a) && judge(b))
ans = max(ans, res);
return;
}
dfs(u + 1, a, b);
dfs(u + 1, a + p[u], b);
dfs(u + 1, a, b + p[u]);
}

int maxProduct(string s) {
n = s.size();
p = s;
dfs(0, "", "");
return ans;
}
};


Nan97
8天前
#define PII pair<int, int>
#define mk make_pair
#define fi first
#define se second

class Solution {
public:
int dx[8] = {0, 0, -1, -1, -1, 1, 1, 1}, dy[8] = {-1, 1, -1, 0, 1, -1, 0, 1};
int n, m;
vector<string> bk;
queue<PII> q;
int check(int sx, int sy) {
int ans = 0;
while(!q.empty()) q.pop();
bk[sx][sy] = 'X';
q.push(mk(sx, sy));
while(q.size()) {
PII t = q.front(); q.pop();
for(int i = 0; i < 8; i ++ ) {
int ex = -1, ey = -1;
int p = 1;

for(;;) {
int a = t.fi + dx[i] * p, b = t.se + dy[i] * p;

if(a < 0 || a >= n || b < 0 || b >= m) break;

if(bk[a][b] == 'O') p ++;
else if(bk[a][b] == 'X') {
ex = a, ey = b;
break;
}
else break;// 卡了一个小时
}

if(ex == -1 && ey == -1) continue;

for(int j = 1; j < p; j ++ ) {
int a = t.fi + dx[i] * j, b = t.se + dy[i] * j;
bk[a][b] = 'X';
ans ++;
q.push(mk(a, b));
}
}
}
return ans;
}

int flipChess(vector<string>& g) {
n = g.size(), m = g[0].size();

for(int i = 0; i < n; i ++ )
for(int j = 0; j < m; j ++ ) {
if(g[i][j] == '.') {
bk = g;
}
}

}
};



Nan97
8天前
const int N = 1e4 + 10;
class Solution {
public:

int cnt[N] = {0};
int minimumSwitchingTimes(vector<vector<int>>& s, vector<vector<int>>& t) {
int ans = 0;
int n = s.size(), m = s[0].size();
int mx = -0x3f3f3f3f;

for(int i = 0; i < n; i ++ )
for(int j = 0; j < m; j ++ )
cnt[s[i][j]] ++, cnt[t[i][j]] --;

for(int i = 0; i < N; i ++ )
if(cnt[i] > 0) ans += cnt[i];
return ans;
}
};


Nan97
11天前

#define PII pair<int, int>
#define x first
#define y second

class Solution {
public:
int findMaximizedCapital(int k, int w, vector<int>& income, vector<int>& need) {
priority_queue<int, vector<int> , less<int> > heap;
int n = need.size();
vector<PII> a;
for(int i  = 0; i < n; i ++ )
a.push_back({need[i], income[i]});
sort(a.begin(), a.end());
int idx = 0;
for(int i = 0; i < k; i ++ ) {
while(idx < n && a[idx].x <= w) {
heap.push(a[idx].y);
idx ++;
}
if(heap.size()) {
int t = heap.top(); heap.pop();
w += t;
}
else break;
}
return w;
}
};


Nan97
12天前

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7
const int INF =  0x3f3f3f3f;
class Solution {
public:
int rand10() {
int l = INF, r = INF;
while(l > 6) l = rand7();
while(r > 5) r = rand7();
return (l & 1) * 5 + r;
}
};


Nan97
12天前
#include <bits/stdc++.h>

using namespace std;

const int N = 510, M = 5e4 + 10, INF = 0x3f3f3f3f;

int n, m;
int g[N][N], d[N];
bool st[N];

int dijkstra() {
memset(d, 0x3f, sizeof d);
d[1] = 0;
for(int i = 0; i < n; i ++ ) {
int t = 0;
for(int j = 1; j <= n; j ++ )
if(!st[j] && (!t || d[t] > d[j]))
t = j;
st[t] = true;
for(int j = 1; j <= n; j ++ )
d[j] = min(d[j], d[t] + g[t][j]);
}
return d[n];
}

int main()
{
cin >> m >> n;
getchar();
memset(g, 0x3f, sizeof g);
for(int t = 0; t < m; t ++) {
string res; getline(cin, res);
stringstream ssin(res);
vector<int> p;

while(ssin >> res)
p.push_back(stoi(res));
int len = p.size();
for(int i = 0; i < len; i ++ )
for(int j = i + 1; j < len; j ++ ) {
int l = p[i], r = p[j];
// printf("%d %d\n", l, r);
g[l][r] = 1;
}
// cout << "len = " << len << endl;
}
// for(int i = 1; i <= n; i ++ ) {
//     for(int j = 1; j <= n; j ++ ) {
//         printf("g[%d][%d] = %d ", i, j, g[i][j]);
//     }
//     puts("");
// }
// dijkstra();
// cout << d[1] << endl << g[1][3] << endl;
// cout << d[3] << endl << d[6] << endl << d[7] << endl;
int t = dijkstra();
if(t == INF) puts("NO");
else printf("%d\n", t - 1);
return 0;
}


Nan97
13天前
#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int a[N];
int f[N][3];

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

int n; cin >> n;
for(int i = 1; i <= n; i ++ ) cin >> a[i];
// 0表示未持有股票
// 1表示持有股票z
// 2 表示冷冻期
memset(f, -0x3f, sizeof f);
f[0][0] = 0;
int mx = -INF;
// for(int i = 0; i <= n; i ++ ) f[i][0] = 0;
for(int i = 1; i <= n; i ++ ) {
f[i][0] = max(f[i - 1][2], f[i - 1][0]);
f[i][1] = max(f[i - 1][0] - a[i], f[i - 1][1]);
f[i][2] = f[i - 1][1] + a[i];
mx = max({f[i][0], f[i][1], f[i][2], mx});
}
cout << mx << endl;
// for(int i = 0; i < n; i ++ )

return 0;
}