找个下午打了场CF，结果被某uranus吊打......一千多名，过弱。
T1，一眼二分了，后来发现题解是O(1)的hhh
T2，题意精炼一下就是让你找一个串的循环节个数，直接n²枚举.....
T3，给你一个ab串，你依次考虑每个前缀，选择reverse这个前缀或者不操作。输出方案使得最后的字典序最小。
手玩一下就能发现，一定能构造出最小字典序，所有a都在b前面。
具体操作是每个整段的结尾字符那里翻转。
T4，给你10个1e5的排列，你需要从每个中提取连续的一段，使得这十段相同。求方案数。
考虑KMP(????)，就是我们线性的扫描第一个串，把它分成若干段十个串都相同的段，这样每段都可以拿公式计算。
第一次交的时候一个中间变量没开long long挂了，太SB了。
T5，题意有点长......就是给你n个人，你要把这n个人两两组队(就是n(n-1)/2次)各一次，每次解决两个任务a，b。
每个人解决a，b问题都有个代价。组队时一人解决一道题，会自动选择总代价最小的解决方案，代价累加到两个人身上。
问你这么多次下来每个人的总代价。
把式子min(A + b, B + a)变形一下：min(b - a, B - A) + a + A
然后就比较显然了.....显然可以用前缀和但是我SB的用了树状数组，不过复杂度一样。
贴个考场代码吧。
#include <bits/stdc++.h>
inline void read(int &x) {
x = ;
char c = getchar();
while(c < '' || c > '') {
c = getchar();
}
while(c >= '' && c <= '') {
x = (x << ) + (x << ) + c - ;
c = getchar();
}
return;
}
typedef long long LL;
const int N = ;
LL xi[N], yi[N], dt[N], X[N], ans[N];
int n, pos[N];
struct TA {
LL ta[N];
inline void add(int i, LL v) {
for(; i <= n; i += i & (-i)) {
ta[i] += v;
}
return;
}
inline LL getsum(int i) {
LL ans = ;
for(; i > ; i -= i & (-i)) {
ans += ta[i];
}
return ans;
}
inline LL ask(int l, int r) {
if(r < l) {
return ;
}
if(l <= ) {
return getsum(r);
}
return getsum(r) - getsum(l - );
}
}cnt, sum;
int main() {
int m;
scanf("%d%d", &n, &m);
LL tot = ;
for(int i = ; i <= n; i++) {
scanf("%lld%lld", &xi[i], &yi[i]);
dt[i] = yi[i] - xi[i];
X[i] = dt[i];
tot += xi[i];
}
std::sort(X + , X + n + );
int xx = std::unique(X + , X + n + ) - X - ;
for(int i = ; i <= n; i++) {
int p = std::lower_bound(X + , X + xx + , dt[i]) - X;
pos[i] = p;
cnt.add(p, );
sum.add(p, dt[i]);
}
for(int i = ; i <= n; i++) {
int p = pos[i];
ans[i] += sum.ask(, p) - dt[i];
ans[i] += cnt.ask(p + , n) * dt[i];
ans[i] += tot - xi[i] + xi[i] * (n - );
}
for(int i = , x, y; i <= m; i++) {
scanf("%d%d", &x, &y);
ans[x] -= std::min(xi[x] + yi[y], xi[y] + yi[x]);
ans[y] -= std::min(xi[x] + yi[y], xi[y] + yi[x]);
}
for(int i = ; i <= n; i++) {
printf("%lld ", ans[i]);
}
return ;
}
AC代码
当时境况比较尴尬，写出来时发现比赛刚结束68s......
第一次交很SB的把long long用%d输出了。
最后1104名......F题听说很有趣，以后来填。
F 题意：给定n个数，从中选出尽量少的数，使得gcd为1。
不存在方案输出-1。n，值域<=300000。
解：正解是：有个结论，如果存在合法解，那么一定有一组合法解的个数不超过7。不会证...
然后设f[i][j]表示选i个数，gcd为j的方案数。
f[i][j] = C(sumj, i) - ∑f[i][j * d]
然后求出一个最小的i使得f[i][1] > 0即可。
#include <cstdio>
#include <algorithm> typedef long long LL;
const int N = , lm = ;
const LL mo[] = {, (LL)(1e9 + )}; int sum[N], bin[N], n;
LL f[][N], nn[N], invn[N], inv[N], MO; inline LL C(int n, int i) {
return nn[n] * invn[i] % MO * invn[n - i] % MO;
} inline int cal(int turn) {
MO = mo[turn];
for(int i = ; i <= lm; i++) {
nn[i] = nn[i - ] * i % MO;
inv[i] = (MO - inv[MO % i]) * (MO / i) % MO;
invn[i] = invn[i - ] * inv[i] % MO;
}
for(int i = ; i <= ; i++) {
for(int j = lm; j >= ; j--) {
if(sum[j] < i) {
continue;
}
f[i][j] = C(sum[j], i);
for(int k = ; k * j <= lm; k++) {
f[i][j] = (f[i][j] - f[i][j * k] + MO) % MO;
}
//printf("f %d %d = %d \n", i, j, f[i][j]);
}
}
for(int i = ; i <= ; i++) {
if(f[i][]) {
return i;
}
}
return -;
} int main() {
nn[] = inv[] = invn[] = ;
nn[] = inv[] = invn[] = ;
int n;
scanf("%d", &n);
for(int i = , x; i <= n; i++) {
scanf("%d", &x);
bin[x]++;
}
for(int i = ; i <= lm; i++) {
for(int j = ; j * i <= lm; j++) {
sum[i] += bin[i * j];
}
} int a = cal(), b = cal();
int ans = std::min(a, b);
if(ans == -) {
printf("%d", std::max(a, b));
}
else {
printf("%d", std::min(a, b));
}
return ;
}
AC代码
反演+二分解法：
首先二分答案，然后用反演求:选出k个，gcd为1的方案数。如果大于0就可行。
#include <bits/stdc++.h> const int N = , MO = ; int p[N], top, miu[N], bin[N], fac[N], inv[N], invn[N];
bool vis[N]; inline int C(int n, int m) {
if(m > n || n < || m < ) return ;
return 1ll * fac[n] * invn[m] % MO * invn[n - m] % MO;
} inline void getp(int n) {
miu[] = ;
for(int i = ; i <= n; i++) {
if(!vis[i]) {
p[++top] = i;
miu[i] = -;
}
for(int j = ; j <= top && i * p[j] <= n; j++) {
vis[i * p[j]] = ;
if(i % p[j] == ) {
miu[i * p[j]] = ;
break;
}
miu[i * p[j]] = -miu[i];
}
}
return;
} inline int check(int k) {
int ans = ;
for(int i = ; i < N; i++) {
(ans += miu[i] * C(bin[i], k)) %= MO;
ans = (ans + MO) % MO;
}
return ans;
} int main() {
getp(N - );
inv[] = fac[] = invn[] = ;
inv[] = fac[] = invn[] = ;
for(int i = ; i < N; i++) {
fac[i] = 1ll * fac[i - ] * i % MO;
inv[i] = 1ll * inv[MO % i] * (MO - MO / i) % MO;
invn[i] = 1ll * invn[i - ] * inv[i] % MO;
}
int n;
scanf("%d", &n);
for(int i = , x; i <= n; i++) {
scanf("%d", &x);
bin[x]++;
}
for(int i = ; i < N; i++) {
for(int j = i << ; j < N; j += i) {
(bin[i] += bin[j]) %= MO;
}
} int l = , r = n + ;
while(l < r) {
int mid = (l + r) >> ;
if(check(mid)) {
r = mid;
}
else {
l = mid + ;
}
}
if(r == n + ) printf("-1\n");
else printf("%d\n", r);
return ;
}
AC代码