$\color{seagreen}{\mathcal{kkkk}}$

6.7万

k_415

kerry2023

2022cc
openallzzz
Clean_up_the_stupid_incra

AC不了怎么办

808bass1

Sumiler

Spstar.
21软件一班陈斌

反之， $x < k$， $x!$ 就不能被 $k!$ 整除。

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];
int s[N];

int main() {
scanf("%d", &n);

for (int i = 1; i <= n; i ++ ) {
scanf("%d", &a[i]);
if (a[i] <= 1e5) s[a[i]] ++ ;
}

for (int i = 1; i <= 1e5; i ++ ) {
if (s[i] % (i + 1)) {
printf("%d\n", i);
return 0;
}
s[i + 1] += s[i] / (i + 1);
}

int ans = 1e9;
for (int i = 1; i <= n; i ++ ) ans = min(ans, a[i]);

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

return 0;
}


23天前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];
int f[N], g[10];

string _to_string(int x) {
string res = "";
while (x) res = char(x % 10 + '0') + res, x /= 10;
return res;
}

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

int res = 0;
for (int i = 1; i <= n; i ++ ) {
string t = _to_string(a[i]);
int head = t[0] - '0', tail = t[t.size() - 1] - '0';
f[i] = 1;
f[i] = max(f[i], g[head] + 1);
g[tail] = max(g[tail], f[i]);
res = max(res, f[i]);
}

cout << n - res;

return 0;
}


23天前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 500010;

int n, k;
char a, b, s[N];

int main() {
cin >> k >> s + 1 >> a >> b;

n = strlen(s + 1);
long long ans = 0;
int cnt = 0;
for (int i = k; i <= n; i ++ ) {
if (s[i - k + 1] == a) cnt ++ ;
if (s[i] == b) ans += cnt;
}

cout << ans;

return 0;
}


26天前

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long i64;

const int N = 1e5 + 10;

int n;
int s[N];
int cnt[30][2];

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
for (int i = 1; i <= n; i ++ ) s[i] ^= s[i - 1];

for (int i = 0; i < 30; i ++ ) cnt[i][0] = 1;

i64 ans = 0;
for (int i = 1; i <= n; i ++ ) {
for (int j = 0; j < 30; j ++ ) {
int v = s[i] >> j & 1;
ans += cnt[j][v ^ 1] * (1ll << j);
cnt[j][v] ++ ;
}
}

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

return 0;
}



26天前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n;
char s[N], t[N];

void solve() {
scanf("%s%s", t + 1, s + 1);
n = strlen(s + 1);

int ans = 0;
for (int i = 2; i < n; i ++ )
if (s[i] != t[i] && s[i - 1] == s[i + 1] && s[i - 1] != s[i])
ans ++ , s[i] ^= 1;

if (strcmp(s + 1, t + 1)) ans = -1;
printf("%d\n", ans);
}

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


26天前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

char str[N];
bool st[N];

int main() {
cin >> str + 1;
int ans = 0;
for (int i = 2; str[i]; i ++ ) {
if (st[i - 1]) continue;
if ((str[i] == str[i - 1]) || (str[i] == '?') || (str[i - 1] == '?')) {
ans ++ ;
st[i] = true;
}
}

cout << ans;

return 0;
}


2个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long i64;

const int N = 1510, M = 1210, MOD = 1e9 + 7;

int n, m;
char str[N], nums[M];
int tr[N][10], idx;
bool dar[N];
int q[N], ne[N];
int f[M][N];

void insert() {
cin >> str;
int p = 0;
for (int i = 0; str[i]; i ++ ) {
int v = str[i] - '0';
if (!tr[p][v]) tr[p][v] = ++ idx;
p = tr[p][v];
}
dar[p] = true;
}

void build() {
int hh = 0, tt = -1;
for (int i = 0; i <= 9; i ++ )
if (tr[0][i]) q[ ++ tt] = tr[0][i];

while (hh <= tt) {
int t = q[hh ++ ];
for (int i = 0; i <= 9; i ++ ) {
int &p = tr[t][i];
if (!p) p = tr[ne[t]][i];
else {
ne[p] = tr[ne[t]][i];
dar[p] |= dar[ne[p]];
q[ ++ tt] = p;
}
}
}
}

i64 dfs(int pos, int u, int lead, int limit) {
if (!pos || dar[u]) return !dar[u];
if (!limit && !lead && ~f[pos][u]) return f[pos][u];
int up = limit ? nums[pos] - '0' : 9; i64 res = 0;
for (int i = 0; i <= up; i ++ )
res = (res + dfs(pos - 1, (lead && !i) ? 0 : tr[u][i], lead && !i, limit && i == up)) % MOD;
return limit ? res : (lead ? res : f[pos][u] = res);
}

int main() {
cin >> nums + 1 >> m;
while (m -- ) insert();
build();
int len = strlen(nums + 1);
reverse(nums + 1, nums + len + 1);
memset(f, -1, sizeof f);
cout << dfs(len, 0, 1, 1) - 1;
return 0;
}


2个月前

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long i64;

int len;
int nums[20];
i64 f[20][10];

i64 dfs(int pos, int mod, int limit) {
if (!pos) return !!mod;
if (!limit && ~f[pos][mod]) return f[pos][mod];
int up = limit ? nums[pos] : 9; i64 res = 0;
for (int i = 0; i <= up; i ++ )
if (i != 9) res += dfs(pos - 1, (mod + i) % 9, limit && i == up);
return limit ? res : f[pos][mod] = res;
}

i64 calc(i64 x) {
len = 0;
memset(f, -1, sizeof f);
while (x) nums[ ++ len] = x % 10, x /= 10;
return dfs(len, 0, 1);
}

void solve(int C) {
i64 l, r;
scanf("%lld%lld", &l, &r);
printf("Case #%d: %lld\n", C, calc(r) - calc(l - 1));
}

int main() {
int _, C = 0; scanf("%d", &_);
while (_ -- ) solve( ++ C);
return 0;
}


2个月前

最小值是最快变成 $0$ 的，如果第一个元素是最小值则先手必败，否则后手必败

若第一个元素是最小值且不是 $0$ (是 $0$ 直接输了，没必要讨论)：
• 则先手 $Alice$ 减 $1$ 后，不管与谁交换值，交换后都比之前大， 由于第一个元素不是 $0$ , 所以交换后轮到 $Bob$ 也必然不是 $0$。而 $Bob$ 只需要做一件事，不断将最小值扔回给 $Alice$ ， 则 $Alice$ 必然最先达到 $0$， 必败。
若第一个元素不是最小值
• 则 $Alice$ 在减 $1$ 后， 直接选择最小值扔给 $Bob$，转变为 $Bob$ 先手拿到最小值，则转变上面那种情况，必败。
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

void solve() {
scanf("%d", &n);
int minv = 2e9;
for (int i = 1; i <= n; i ++ ) {
scanf("%d", &a[i]);
if (a[i] < minv) minv = a[i];
}
puts(a[1] == minv ? "Bob" : "Alice");
}

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


2个月前

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];
int tr[N], ans[N];

int add(int x, int v) {
for (; x <= n; x += x & -x) tr[x] += v;
}

int query(int x) {
int res = 0;
for (; x; x -= x & -x) res += tr[x];
return res;
}

int kth(int l, int r, int k) {
if (l == r) return r;
int mid = l + r >> 1;
int cnt = query(mid) - query(l - 1);
if (cnt >= k) return kth(l, mid, k);
return kth(mid + 1, r, k - cnt);
}

int main() {
cin >> n;
for (int i = 2; i <= n; i ++ ) cin >> a[i];

for (int i = 1; i <= n; i ++ ) add(i, 1);

for (int i = n; i > 1; i -- ) {
a[i] ++ ;
ans[i] = kth(1, n, a[i]);