leoma

1671

Meteor_7
vvvvae

lyktes

zeng9999jian
wyyang

SayonaraGzm
HollowKnight

Iris_随月浅唱

yxc

zhangshuo2008

leoma
1个月前

#include [HTML_REMOVED]

# include [HTML_REMOVED]

using namespace std;

priority_queue[HTML_REMOVED] l;
priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> r;

int main()
{
int n, w;
scanf(“%d%d”, &n, &w);

for (int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);

if (r.empty() || x >= r.top()) r.push(x);
else l.push(x);

int k = max(1, (int)(i * w / 100.0));

while (r.size() < k) r.push(l.top()), l.pop();
while (r.size() > k) l.push(r.top()), r.pop();

printf("%d ", r.top());
}

return 0;


}


leoma
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n;
int w[N], l[N], r[N], s[N];
int ans;

int dfs1(int u )
{
if (!u) return 0 ;
s[u] = dfs1(l[u]) + dfs1(r[u]) + 1;
return s[u];
}

bool check(int a, int b)
{
if (!a && !b) return true;
if (!a || !b) return false;
if (w[a] != w[b]) return false;
return check(l[a], r[b]) && check(r[a], l[b]);
}

void dfs2(int u)
{
if (!u) return;
if (s[l[u]] == s[r[u]])
if (check(l[u], r[u]))
ans = max(ans, s[u]);
dfs2(l[u]);
dfs2(r[u]);
}

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf ("%d", &w[i]);
for (int i = 1; i <= n; i ++ )
{
scanf("%d%d", &l[i], &r[i]);
if (l[i] == -1) l[i] = 0;
if (r[i] == -1) r[i] = 0;
}

dfs1(1);
dfs2(1);

printf("%d\n", ans);

return 0;
}


leoma
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

const int N = 1000010;

int n, m;
int h[N], e[N], ne[N], idx;
int w[N];
char c[N];
bool st[N];
int stk[N], top;

void add(int a, int b)  // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs1(int u){
if (!c[u]) return w[u];
if (c[u] == '!') w[u] = !dfs1(e[h[u]]);
else
{
int a = e[h[u]], b = e[ne[h[u]]];
if (c[u] == '&') w[u] = dfs1(a) & dfs1(b);
else w[u] = dfs1(a) | dfs1(b);
}
return w[u];
}

void dfs2(int u)
{
st[u] = true;
if (!c[u]) return;
if (c[u] == '!') dfs2(e[h[u]]);
else
{
int a = e[h[u]], b = e[ne[h[u]]];
if (c[u] == '&')
{
if (w[a]) dfs2(b);
if (w[b]) dfs2(a);
}
else
{
if (!w[a]) dfs2(b);
if (!w[b]) dfs2(a);
}
}
}

int main()
{
string s;
getline(cin, s);
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
memset(h, -1, sizeof h);
m = n;
for (int i = 0; i < s.size(); i ++ )
{
if (s[i] == ' ') continue;
if (s[i] == 'x')
{
int j = i + 1, x = 0;
while (j < s.size() && isdigit(s[j])) x = x * 10 + s[j ++ ] - '0';
stk[ ++ top] = x;
i = j;
}
else if (s[i] == '!')
{
c[ ++ m] = s[i];
stk[ ++ top] = m;
}
else
{
c[ ++ m] = s[i];
stk[ ++ top] = m;
}
}

int res = dfs1(m);
dfs2(m);

int Q;
cin >> Q;
while (Q -- )
{
int x;
cin >> x;
if (st[x]) cout << (res ^ 1) << endl;
else cout << res << endl;
}

return 0;
}


leoma
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m, K, S, T;
int c[N], cg[N][N];
int g[N][N], d[N][N];
int ans = INF;
int path[N], top;

void dfs(int u, int dist)
{
if (dist + d[S][u] >= ans) return;
if (u == S) ans = dist;
else
{
for (int i = 1; i <= n; i ++ )
if (g[i][u] < INF)
{
bool flag = true;
for (int j = 0; j < top; j ++ )
if (cg[path[j]][c[i]])
{
flag = false;
break;
}
if (flag)
{
path[top ++ ] = c[i];
dfs(i, dist + g[i][u]);
top -- ;
}
}
}
}

int main()
{
cin >> n >> K >> m >> S >> T;
for (int i = 1; i <= n; i ++ ) cin >> c[i];
for (int i = 1; i <= K; i ++ )
for (int j = 1; j <= K; j ++ )
cin >> cg[i][j];
for (int i = 1; i <= K; i ++ ) cg[i][i] = 1;
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; i ++ ) g[i][i] = 0;

while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}

memcpy(d, g, sizeof d);
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

path[top ++ ] = c[T];
dfs(T, 0);
if (ans == INF) ans = -1;
cout << ans << endl;

return 0;
}


leoma
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m, K, S, T;
int c[N], cg[N][N];
int g[N][N], d[N][N];
int ans = INF;
int path[N], top;

void dfs(int u, int dist)
{
if (dist + d[S][u] >= ans) return;
if (u == S) ans = dist;
else
{
for (int i = 1; i <= n; i ++ )
if (g[i][u] < INF)
{
bool flag = true;
for (int j = 0; j < top; j ++ )
if (cg[path[j]][c[i]])
{
flag = false;
break;
}
if (flag)
{
path[top ++ ] = c[i];
dfs(i, dist + g[i][u]);
top -- ;
}
}
}
}

int main()
{
cin >> n >> K >> m >> S >> T;
for (int i = 1; i <= n; i ++ ) cin >> c[i];
for (int i = 1; i <= K; i ++ )
for (int j = 1; j <= K; j ++ )
cin >> cg[i][j];
for (int i = 1; i <= K; i ++ ) cg[i][i] = 1;
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; i ++ ) g[i][i] = 0;

while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}

memcpy(d, g, sizeof d);
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

path[top ++ ] = c[T];
dfs(T, 0);
if (ans == INF) ans = -1;
cout << ans << endl;

return 0;
}



leoma
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;

int n, m, r, c;
int w[N][N];
int f[N][N];
int rw[N][N], cw[N];
int q[N];

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

int main()
{
cin >> n >> m >> r >> c;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
cin >> w[i][j];

int res = 1e8;
for (int i = 0; i < 1 << n; i ++ )
if (get_count(i) == r)
{
for (int j = 0, k = 0; j < n; j ++ )
if (i >> j & 1)
q[k ++ ] = j;
for (int j = 0; j < m; j ++ )
{
cw[j] = 0;
for (int k = 1; k < r; k ++ )
cw[j] += abs(w[q[k]][j] - w[q[k - 1]][j]);
}
for (int j = 0; j < m; j ++ )
for (int k = j + 1; k < m; k ++ )
{
rw[j][k] = 0;
for (int u = 0; u < r; u ++ )
rw[j][k] += abs(w[q[u]][j] - w[q[u]][k]);
}

memset(f, 0x3f, sizeof f);
for (int j = 0; j < m; j ++ )
{
f[j][1] = cw[j];
for (int k = 2; k <= c; k ++ )
for (int u = 0; u < j; u ++ )
f[j][k] = min(f[j][k], f[u][k - 1] + cw[j] + rw[u][j]);
res = min(res, f[j][c]);
}
}
cout << res << endl;

return 0;
}


leoma
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 500;

void mul(int c[], int a[], int b[])
{
static int tmp[N];
memset(tmp, 0, sizeof tmp);
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
if (i + j < N)
tmp[i + j] += a[i] * b[j];

for (int i = 0, t = 0; i < N; i ++ )
{
t += tmp[i];
c[i] = t % 10;
t /= 10;
}
}

void qmi(int k)
{
int res[N] = {1};
int a[N] = {2};

while (k)
{
if (k & 1) mul(res, res, a);
mul(a, a, a);
k >>= 1;
}

res[0] -- ;
for (int i = 0, k = N - 1; i < 10; i ++ )
{
for (int j = 0; j < 50; j ++, k -- )
printf("%d", res[k]);
puts("");
}
}

int main()
{
int p;
cin >> p;
cout << (int)(p * log10(2)) + 1 << endl;

qmi(p);

return 0;
}


leoma
1个月前
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 40;

int n;
LL C[N][N];

int main(){
cin >> n;
for (int i = 0 ; i <= n * 2 ; i ++ )
for (int j = 0 ; j <= i ; j ++ )
if (!j) C[i][j] = 1;
else    C[i][j] = C[i-1][j] + C[i-1][j-1];

cout << C[n*2][n] / (n+1) << endl;

return 0;
}


leoma
1个月前
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
PII q[N];
int f[N], g[N], h[N];

int main(){
scanf("%d", &n);
for (int i = 1 ; i <= n ; i ++ ) scanf("%d", &q[i].y);
for (int i = 1 ; i <= n ; i ++ ) scanf("%d", &q[i].x);
sort(q+1, q+1+n, greater<PII>());

for (int i = 1 ; i <= n ; i ++ ){
f[i] = f[i-1] + q[i].x;
g[i] = max(g[i-1], q[i].y);
}

for (int i = n ; i ; i -- ) h[i] = max(h[i+1], q[i].x + q[i].y * 2);

for (int i = 1 ; i <= n ; i ++ )    printf("%d\n", max(f[i] + g[i] * 2, f[i-1] + h[i]));

return 0;
}


leoma
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int m, n, k, l, d;
int row[N], col[N];

void work(int a[], int n, int k)
{
int id[N];
for (int i = 0; i < n - 1; i ++ ) id[i] = i + 1;
sort(id, id + n - 1, [&](int x, int y) {
return a[x] > a[y];
});
sort(id, id + k);
for (int i = 0; i < k; i ++ )
cout << id[i] << ' ';
puts("");
}

int main()
{
cin >> m >> n >> k >> l >> d;
while (d -- )
{
int x, y, p, q;
cin >> x >> y >> p >> q;
if (x > p) swap(x, p);
if (y > q) swap(y, q);
if (x == p) col[y] ++ ;
else row[x] ++ ;
}

work(row, m, k);
work(col, n, l);

return 0;
}