lvti

2206

MagicalJIE
kingY

qaq...
yxc

Ac过家家
Astesia
Bblb
BLOODHOUND
ʰᵛ
Slay3r丶
hjx_0
Sze
Evenesco
The_Acute.

gangben
SolitudeFate

lvti
15小时前

### 状态机

f[i][j][1] : 只考虑前i天， 已经完成 j - 1次交易， 正在进行第j次交易且手中有货（正在买第j次交易的股票，交易才开始）
f[i][j][0] : 只考虑前i天，已经完成j-1次交易，正在进行第j次交易且手中无货（把第j次交易的股票卖掉了，第j次交易完成）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010, M = 110;

int f[N][M][2];
int n, m;
int w[N];

int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
memset(f, -0x3f, sizeof f);
for(int i = 0; i <= n; i ++) f[i][0][0] = 0;

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

int res = 0;
for(int i = 1; i <= m; i ++) res = max(res, f[n][i][0]);
printf("%d\n", res);
return 0;
}


lvti
15小时前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;

int w[N];
int f[N][2];
int t, n;

void solve()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
f[0][0] = 0, f[0][1] = -1;
for(int i = 1; i <= n; i ++)
{
f[i][1] = f[i - 1][0] + w[i];
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
}
printf("%d\n", max(f[n][0], f[n][1]));
}

int main()
{
scanf("%d", &t);
while(t --)
solve();
return 0;
}


lvti
1天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long ll;

struct Node
{
int l, r;
ll sum; // 区间和 考虑当前节点及子节点上的所有标记，当前区间和是多少
} tr[N << 2];
ll a[N];
int n, m;

void pushup(Node &fa, Node &l, Node &r)
{
fa.sum = l.sum + r.sum;
}

void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void pushdown(int u)
{
Node &fa = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
}

void build(int u, int l, int r)
{
if(l == r)
{
tr[u] = {l, r, a[r], 0};
}
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}

void modify(int u, int l, int r, ll v)
{
if(l <= tr[u].l && r >= tr[u].r)
{
tr[u].sum += v * (tr[u].r - tr[u].l + 1);
}
else // 一定要分裂
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, v);
if(r > mid) modify(u << 1 | 1, l, r, v);
pushup(u);
}
}

ll query(int u, int l, int r)
{
if(l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
ll sum = 0;
if(l <= mid) sum += query(u << 1, l, r);
if(r > mid) sum += query(u << 1 | 1, l ,r);
return sum;
}
}

int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
build(1, 1, n);

char op[2];
int l, r;
while(m --)
{
scanf("%s%d%d", op, &l, &r);
if(*op == 'Q')
{
printf("%lld\n", query(1, l, r));
}
else
{
ll d;
scanf("%lld", &d);
modify(1, l, r, d);
}
}
return 0;
}


lvti
1天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010;

int n;
int a[N];
int cnt[N];
int ans[N];

int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i ++) scanf("%d", &a[i]);

for(int i = 0; i < n; i ++)
{
memset(cnt, 0, sizeof cnt);
int t = 0;
for(int j = i; j < n; j ++)
{
int x = a[j];
cnt[x] ++;
if((cnt[x] == cnt[t] && x < t) || cnt[x] > cnt[t])
t = x;
ans[t] ++;
}
}
for(int i = 1; i <= n; i ++)
printf("%d ", ans[i]);
return 0;
}


lvti
1天前

### bfs

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
typedef pair<string, string> PII;
int res = 100;
string res_op;

string A(string s)
{
string t = s;
reverse(t.begin(), t.end());
return t;
}

string B(string s)
{
string t = s.substr(0, 3) + s.substr(5);
t = s[3] + t + s[4];
return t;
}

string C(string s)
{
string t = s;
char tt = t[1];
t[1] = t[6];
t[6] = t[5];
t[5] = t[2];
t[2] = tt;
return t;
}

void bfs(string start, string aim)
{
queue<PII> q;
unordered_map<string, int> mp;
mp[start] ++;
q.push({start, ""});
while(q.size())
{
auto t = q.front(); q.pop();
string ts = t.first, tp = t.second;
if(ts == aim)
{
res = tp.size();
res_op = tp;
return;
}
string tmp = A(ts);
if(!mp[tmp])
{
q.push({tmp, tp + 'A'});
mp[tmp] ++;
}
tmp = B(ts);
if(!mp[tmp])
{
q.push({tmp, tp + 'B'});
mp[tmp] ++;
}
tmp = C(ts);
if(!mp[tmp])
{
q.push({tmp, tp + 'C'});
mp[tmp] ++;
}
}
}

int main()
{
string start = "12345678";
string aim = "00000000";
for(int i = 0; i < 8; i ++)
{
int x;
cin >> x;
aim[i] = (aim[i] + x);
}
bfs(start, aim);
cout << res << endl;
if(res)
cout << res_op << endl;
return 0;
}


lvti
1天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 22;

string word[N];
int g[N][N]; // g[i][j] 第j个单词接到第i个单词后面最小公共部是多长
int used[N]; // used[i] 第i个单词被使用了几次
int n;
char start;
int res = 1;
// 当前龙  龙的最后用的哪个单词
void dfs(string dragon, int u)
{
res = max((int)dragon.size(), res);
for(int i = 1; i <= n; i ++)
{
if(g[u][i] && used[i] < 2)
{
used[i] ++;
dfs(dragon + word[i].substr(g[u][i]), i);
used[i] --;
}
}
}

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

for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
{
for(int k = 1; k < min((int)word[i].size(), (int)word[j].size()); k ++)
{
if(word[i].substr(word[i].size() - k) == word[j].substr(0, k))
{
g[i][j] = k;
break;
}
}
}

// 枚举以哪个单词开始
for(int i = 1; i <= n; i ++)
if(word[i][0] == start)
{
used[i] ++;
dfs(word[i], i);
used[i] --;
}

cout << res << endl;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 22;

string word[N];
int g[N][N]; // g[i][j] 第j个单词接到第i个单词后面最小公共部是多长
int used[N]; // used[i] 第i个单词被使用了几次
int n;
char start;
int res = 1;
// 当前龙  龙的最后用的哪个单词
void dfs(string dragon, int u)
{
used[u] ++;
res = max((int)dragon.size(), res);
for(int i = 1; i <= n; i ++)
{
if(g[u][i] && used[i] < 2)
dfs(dragon + word[i].substr(g[u][i]), i);
}
used[u] --;
}

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

for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
{
for(int k = 1; k < min((int)word[i].size(), (int)word[j].size()); k ++)
{
if(word[i].substr(word[i].size() - k) == word[j].substr(0, k))
{
g[i][j] = k;
break;
}
}
}

// 枚举以哪个单词开始
for(int i = 1; i <= n; i ++)
if(word[i][0] == start)
dfs(word[i], i);

cout << res << endl;
}


lvti
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 28;

int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};
bool g[N][N];
int n, m;
int res;

void dfs(int x, int y, int cnt)
{
if(cnt == n * m) res ++;
for(int i = 0; i < 8; i ++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || b < 0 || a >= n || b >= m) continue;
if(!g[a][b])
{
g[a][b] = true;
dfs(a, b, cnt + 1);
g[a][b] = false;
}
}
}

int main()
{
int T;
cin >> T;
while(T --)
{
int x, y;
cin >> n >> m >> x >> y;
memset(g, 0, sizeof g);
g[x][y] = true;
res = 0;
dfs(x, y, 1);
cout << res << endl;
}
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 28;

int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};
bool g[N][N];
int n, m;
int res;

bool check()
{
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
if(!g[i][j]) return false;
return true;
}

void dfs(int x, int y)
{
if(check()) res ++;
for(int i = 0; i < 8; i ++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || b < 0 || a >= n || b >= m) continue;
if(!g[a][b])
{
g[a][b] = true;
dfs(a, b);
g[a][b] = false;
}
}
}

int main()
{
int T;
cin >> T;
while(T --)
{
int x, y;
cin >> n >> m >> x >> y;
memset(g, 0, sizeof g);
g[x][y] = true;
res = 0;
dfs(x, y);
cout << res << endl;
}
return 0;
}



lvti
2天前

## dfs

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
char g[N][N];
bool st[N][N];
int n, m;

int dfs(int x, int y)
{
st[x][y] = true;
int cnt = 1;
for(int i = 0; i < 4; i ++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || b < 0 || a >= n || b >= m) continue;
if(st[a][b] || g[a][b] == '#') continue;
cnt += dfs(a, b);
}
return cnt;
}

int main()
{
while(cin >> m >> n, n)
{
int x, y;
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
cin >> g[i][j];
if(g[i][j] == '@') x = i, y = j;
}
}
memset(st, false, sizeof st);
cout << dfs(x, y) << endl;
}
return 0;
}


## bfs

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 22;
typedef pair<int, int> PII;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
char g[N][N];
bool st[N][N];
int n, m;

int bfs(PII start)
{
memset(st, false, sizeof st);
int res = 1;
queue<PII> q;
q.push({start.x, start.y});
st[start.x][start.y] = true;
while(q.size())
{
auto t = q.front(); q.pop();
for(int i = 0; i < 4; i ++)
{
int a = t.x + dx[i], b = t.y + dy[i];
if(a <= 0 || b <= 0 || a > n || b > m) continue;
if(g[a][b] == '#' || st[a][b]) continue;
q.push({a, b});
st[a][b] = true;
res ++;
}
}
return res;
}

int main()
{
while(cin >> m >> n, n && m)
{
PII start;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
cin >> g[i][j];
if(g[i][j] == '@') start = {i, j};
}
}
int res = bfs(start);
cout << res << endl;
}
return 0;
}



lvti
2天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
char g[N][N];
bool st[N][N];
int t, n;
int x1, y1, x2, y2;

bool dfs(int x, int y)
{
st[x][y] = true;
if(g[x][y] == '#') return false; // 特判起点或则终点就是#
if(x == x2 && y == y2) return true;
bool flag = false;
for(int i = 0; i < 4; i ++)
{
int a = x + dx[i];
int b = y + dy[i];
if(a < 0 || b < 0 || a >= n || b >= n) continue;
if(st[a][b] || g[a][b] == '#') continue;
flag |= dfs(a, b);
}
return flag;
}

int main()
{
cin >> t;
while(t --)
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> g[i];
cin >> x1 >> y1 >> x2 >> y2;
memset(st, false, sizeof st);
if(dfs(x1, y1))
puts("YES");
else
puts("NO");
}
return 0;
}


lvti
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 500010;
string s;
char c1, c2;
int f[N]; // f[i] :位置i及前面c1出现的次数
int k;

int main()
{
cin >> k;
cin >> s;
cin >> c1;
cin >> c2;
s = '@' + s;
f[0] = 0;
int len = s.size();
for(int i = 1; i <= len; i ++)
if(s[i] == c1) f[i] = f[i - 1] + 1;
else f[i] = f[i - 1];
ll res = 0;
for(int i = k; i <= len; i ++)
if(s[i] == c2) res += f[i - k + 1];
cout << res << endl;
return 0;
}