Q.c

1920

Q.c
16小时前
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n, idx = 0;
int a[N], m[N], b[N];
int t[N];

int main()
{
scanf("%d", &n);
memset(m, 0x3f, sizeof m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
m[a[i]] = i;
}
for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
for (int i = 1; i <= n; ++i) {
if (!idx || m[b[i]] > t[idx]) {
if (m[b[i]] == 0x3f3f3f3f) continue;
t[++idx] = m[b[i]];
continue;
}
int l = 1, r = idx, mid;
while (l < r) {
mid = l + r >> 1;
if (t[mid] < m[b[i]]) l = mid + 1;
else r = mid;
}
t[l] = m[b[i]];
}
printf("%d\n", idx);
}


Q.c
17小时前

建议倍增

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int N = 1010;
const double eps = 1e-5;

int n, k;
double a[N], b[N];
double c[N];

bool check(double x)
{
double res = 0;
for (int i = 1; i <= n; ++i) c[i] = a[i] - x * b[i];
sort(c + 1, c + 1 + n);
for (int i = k + 1; i <= n; ++i) res += c[i];
return res >= 0;
}

int main()
{
while (scanf("%d%d", &n, &k), n || k) {
for (int i = 1; i <= n; ++i) scanf("%lf", &a[i]);
for (int i = 1; i <= n; ++i) scanf("%lf", &b[i]);
double l = 0, p = 1;
while (check(l + p)) l += p, p *= 2;
while (fabs(p) > eps) {
if (check(l + p)) l += p;
p /= 2;
}
printf("%.0lf\n", l * 100);
}
return 0;
}


Q.c
2天前
#include <cstdio>

using namespace std;

int n, k;
int a[100010];
long long s[100010];

long long max(long long a, long long b) { return a > b ? a : b; }

int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
int x;
long long t = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &x);
if (x) t += a[i], a[i] = 0;
}
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
long long ans = 0;
for (int i = k, j = 0; i <= n; ++i, ++j) ans = max(s[i] - s[j] + t, ans);
printf("%lld\n", ans);
return 0;
}


Q.c
4天前
#include <cstdio>

using namespace std;

const int N = 210;

int n, l, k;
double p[N];
double f[N][N][N << 1];

inline int min(int a, int b) { return a < b ? a : b; }

int main()
{
scanf("%d%d%d", &n, &l, &k);
for (int i = 0; i < n; ++i) scanf("%lf", &p[i]), p[i] /= 100;

int x;
f[0][0][min(n << 1, n + k)] = 1;
for (int i = 0; i < n; ++i) {
scanf("%d", &x);
for (int j = 0; j <= i; ++j)
for (int size = 0; size <= (n << 1); ++size)
if (size + x >= 0)
f[i + 1][j + 1][min(size + x, n << 1)] += f[i][j][size] * p[i], f[i + 1][j][size] += f[i][j][size] * (1 - p[i]);
}

double ans = 0;

for (int i = l; i <= n; ++i)
for (int j = n; j < N << 1; ++j)
ans += f[n][i][j];

printf("%.6lf\n", ans);

return 0;
}


Q.c
4天前
#include <cstdio>
#include <cstring>

using namespace std;

#define ll long long
const int N = 1e4 + 10;

int n;
int a[N], mu[N];
int idx, v[N], prime[N];
ll cnt[N], C[N];

void get_mu(int n);

int main()
{
get_mu(N - 1);
for (int i = 1; i < N; ++i) C[i] = 1ll * i * (i - 1) * (i - 2) * (i - 3) / 24;
while (~scanf("%d", &n)) {
memset(cnt, 0, sizeof cnt);
int m = 0;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
m = m > a[i] ? m : a[i];
for (int j = 1; j * j <= a[i]; ++j) {
if (a[i] % j) continue;
++cnt[j];
if (j * j != a[i]) ++cnt[a[i] / j];
}
}
ll ans = 0;
for (int i = 1; i <= m; ++i)
ans += 1ll * mu[i] * C[cnt[i]];

printf("%lld\n", ans);
}
return 0;
}
void get_mu(int n)
{
mu[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!v[i]) {
v[i] = i;
prime[++idx] = i;
mu[i] = -1;
}
for (int j = 1; j <= idx && prime[j] * i <= n; ++j) {
v[i * prime[j]] = prime[j];
if (v[i] ^ prime[j])
mu[i * prime[j]] = -1 * mu[i];
else break;
}
}
}


Q.c
6天前
#include <cstdio>

using namespace std;

const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int T;
int n, m;
int jc[N], jcinv[N], d[N];

int qpow(int base, int k);

int main()
{
jc[0] = jcinv[0] = 1;
for (int i = 1; i < N; ++i) {
jc[i] = 1ll * jc[i - 1] * i % mod;
jcinv[i] = qpow(jc[i], mod - 2);
}
d[0] = 1, d[1] = 0;
for (int i = 2; i < N; ++i)
d[i] = 1ll * (d[i - 2] + d[i - 1]) % mod * (i - 1) % mod;

scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
printf("%d\n", 1ll * jc[n] * jcinv[m] % mod * jcinv[n - m] % mod * d[n - m] % mod);
}

return 0;
}
int qpow(int base, int k)
{
base = base % mod; int res = 1;
while (k) {
if (k & 1) res = 1ll * res * base % mod;
base = 1ll * base * base % mod;
k >>= 1;
}
return res;
}


Q.c
6天前
#include <cstdio>
#include <algorithm>

using namespace std;

struct cmp
{
bool operator()(int a, int b)
{
return a > b;
}
};

int n;
int a[1010];
int f[60];
long long ans;

int insert(int);

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
sort(a + 1, a + 1 + n, cmp());
for (int i = 1; i <= n; ++i) {
ans += insert(a[i]);
}
printf("%lld\n", ans);

return 0;
}
int insert(int x)
{
int tmp = x;
for (int i = 30; i >= 0; --i)
if ((x >> i) & 1) {
if (f[i]) x ^= f[i];
else {
f[i] = x;
return 0;
}
}
return tmp;
}


Q.c
6天前
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;

#define ll long long

struct PII
{
int to; ll w;
};

int n, m;
vector<PII> v[50010];
vector<ll> a;
ll f[64];
bool vis[50010];
ll dis[50010];

void dfs(int now);

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int st, ed; ll w;
scanf("%d%d%lld", &st, &ed, &w);
v[st].push_back({ed, w});
v[ed].push_back({st, w});
}
memset(vis, 0, sizeof vis);
dis[1] = 0;
dfs(1);
memset(f, 0, sizeof f);
for (int i = 1; i <= a.size(); ++i)
for (int j = 60; j >= 0; --j)
if ((a[i] >> j) & 1) {
if (!f[j]) {
f[j] = a[i];
break;
}
a[i] ^= f[j];
}
ll ans = dis[n];
for (int i = 60; i >= 0; --i) {
if (!((ans >> i) & 1)) ans ^= f[i];
}
printf("%lld\n", ans);
return 0;
}
void dfs(int now)
{
vis[now] = 1;
for (unsigned int i = 0; i < v[now].size(); ++i) {
int to = v[now][i].to; ll w = v[now][i].w;
if (vis[to]) a.push_back(dis[now] ^ dis[to] ^ w);
else {
dis[to] = dis[now] ^ w;
dfs(to);
}
}
}


Q.c
6天前
#include <map>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 310;

map<string, int> mp;
int n, m;
int f[N][N];

void gauss(void);
int exgcd(int a, int b, int &x, int &y);
int main()
{
mp["MON"] = 1, mp["TUE"] = 2, mp["WED"] = 3, mp["THU"] = 4, mp["FRI"] = 5, mp["SAT"] = 6, mp["SUN"] = 7;
while (scanf("%d%d", &n, &m), n || m) {
memset(f, 0, sizeof f);

for (int i = 1; i <= m; ++i) {
int x; string a, b;
scanf("%d", &x);
cin >> a >> b;
f[i][n + 1] = (mp[b] - mp[a] + 1) % 7;
for (int j = 1; j <= x; ++j) {
int tmp;
scanf("%d", &tmp);
(++f[i][tmp]) %= 7;
}
}
gauss();
}

return 0;
}
int exgcd(int a, int b, int &x, int &y)
{
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int z = x; x = y; y = z - y * (a / b);
return d;
}
void gauss(void)
{
int r, c;
for (r = 1, c = 1; c <= n; ++c) {
int t = r;
for (int i = r + 1; i <= m; ++i)
if (f[i][c] && (!f[t][c] || f[i][c] > f[t][c])) t = i;
if (!f[t][c]) continue;
for (int i = 1; i <= n + 1; ++i) swap(f[r][i], f[t][i]);
for (int i = 1; i <= m; ++i) {
if (i == r || !f[i][c]) continue;
int tmp = f[i][c];
for (int k = 1; k <= n + 1; ++k)
f[i][k] = (f[i][k] * f[r][c] - f[r][k] * tmp) % 7;
}
++r;
}
for (int i = r + 1; i <= m; ++i)
if (f[i][n + 1] % 7) {
puts("Inconsistent data.");
return;
}
if (r < n) {
puts("Multiple solutions.");
return;
}
for (int i = 1; i <= n; ++i) {
int x, y;
int d = exgcd(f[i][i], 7, x, y);
if (f[i][n + 1] % d) {
puts("Inconsistent data.");
return;
}
else if (i < n) printf("%d ", ((x * f[i][n + 1] / d - 3) % 7 + 7) % 7 + 3);
else printf("%d\n", ((x * f[i][n + 1] / d - 3) % 7 + 7) % 7 + 3);
}
}


Q.c
10天前
#include <vector>
#include <cstdio>

using namespace std;

#define ll long long
const int mod = 1e7 + 7;

inline int Add(ll a, int b) { a += b; return a >= mod ? a - mod : a; }

struct Matrix
{
#define Ma Matrix
int r, c;
vector<vector<int>> unit;

Ma() {}
Ma(int r, int c) : r(r), c(c)
{
unit.resize(r);
for (int i = 0; i < r; ++i) unit[i].resize(c);
}
Ma(int r, int c, int num) : r(r), c(c)
{
unit.resize(r);
for (int i = 0; i < r; ++i) {
unit[i].resize(c);
for (int j = 0; j < c; ++j) unit[i][j] = i == j ? num : 0;
}
}

Ma operator*(const Ma &b) const
{
Ma New(r, b.c);
for (int i = 0; i < r; ++i)
for (int k = 0; k < c; ++k) {
int tmp = unit[i][k];
for (int j = 0; j < b.c; ++j) New.unit[i][j] = Add(New.unit[i][j], 1ll * tmp * b.unit[k][j] % mod);
}
return New;
}
Ma operator^(int k)
{
Ma base = *this; Ma res(r, r, 1);
while (k) {
if (k & 1) res = res * base;
base = base * base;
k >>= 1;
}
return res;
}
#undef Ma
};

int n, m, len;
Matrix ans, base;

inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
void MakeMa(void);
void MulMa(void);
void Print(Matrix a);

int main()
{
while (~scanf("%d%d", &n, &m)) {
++n, ++m;
ans = Matrix(1, n + 1);
base = Matrix(n + 1, n + 1, 1);

MakeMa();
MulMa();

printf("%d\n", ans.unit[0][n - 1]);
}

return 0;
}
void MakeMa(void)
{
ans.unit[0][0] = 23, ans.unit[0][n] = 3;
for (int i = 1; i < n; ++i) scanf("%d", &ans.unit[0][i]);
base.unit[n][n] = 1;
for (int i = 0; i < n; ++i) base.unit[n][i] = 1;
for (int i = 0; i < n; ++i) base.unit[0][i] = 10;
for (int j = 1; j < n; ++j)
for (int i = 1; i <= j; ++i) base.unit[i][j] = 1;
}
void MulMa(void)
{
int k = m - 1;
ans = ans * (base ^ k);
}
void Print(Matrix a)
{
for (int i = 0; i < a.r; ++i)
for (int j = 0; j < a.c; ++j) printf("%d%c", a.unit[i][j], j == a.c - 1 ? '\n' : ' ');
return;
}