「LibreOJ Round

发表于 2020-08-29 更新于 2023-12-07 分类于题解

题目链接:https://loj.ac/problem/535

虽然写几个不同的方法写了三个小时,做这道题收获还是挺大/cy.

题目

$n$个烟火排成一排，从左到右高度分别为$h-1,h-2,...,h-n$ ，这些高度两两不同。
每次 Yoko 可以选择两个相邻的烟火交换，这样的交换可以进行任意多次。每次 Yoko 还可以选择两个不相邻的烟火交换，但这样的交换至多进行一次。
你的任务是帮助 Yoko 用最少次数的交换，使这些烟火从左到右的高度递增。

题解

0分

这个就各显神通了.

17分

好像也没什么好说的,直接暴搜就可以了.

41分

阅读全文 »

link
看完题目很容易想到二分答案,只用考虑怎么检验答案合法.
因为是一颗树的形态,所以在树上$dfs$时候修建赛道就行了. 对当前节点$u$分类讨论一下:
1. 儿子所代表的子树尽量内部修建赛道,因为这样一定不会更劣.
2. 把不能内部修建的最大的路径值返回给$u$,看看它能不能和其他的不能单独修建的路径组合在一起.
这样得到的答案一定是当前最优的,且不会有边被重复使用.
因为不想写平衡树,直接用了$multiset$.

#include<bits/stdc++.h>
using namespace std;

const int N = 5e4 + 5;
int n, m, mid, cnt, tot, head[N];
struct E {
    int nxt, v, w;
}e[N << 1];

void add(int a, int b, int c) {
    e[++tot] = E{head[a], b, c}; head[a] = tot;
    e[++tot] = E{head[b], a, c}; head[b] = tot;
}

#define IT multiset<int>::iterator

int dfs(int u, int fa) {
    multiset<int> s;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v, w = e[i].w;
        if (v == fa) continue;
        int d = dfs(v, u) + w;
        if (d >= mid) cnt++;
        else s.insert(d);
    }
    int mx = 0;
    while (!s.empty()) {
        IT it = s.begin();
        int x = *it;
        s.erase(it);
        IT t = s.lower_bound(mid - x);
        if (t == s.end()) mx = x;
        else s.erase(t), cnt++;
    }
    return mx;
}

int main() {
    freopen("track.in", "r", stdin);
    freopen("track.out", "w", stdout);
    int l = 0, r = 0, ans = 0;
    scanf("%d %d", &n, &m);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w);
        l = min(l, w); r += w;
    }
    while (l <= r) {
        mid = (l + r) >> 1;
        cnt = 0;
        dfs(1, 0);
        if (cnt >= m) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}

LOJ2200 力

发表于 2020-08-29 更新于 2023-12-07 分类于题解

如果把原式化为卷积形式，就可以用$FFT$优化。　　 $E_j=\frac{F_j}{q_j}=\sum\limits_{i=1}^{j-1}\frac{q_i}{(i-j)^2}-\sum\limits_{i=j+1}^{n}\frac{q_i}{(i-j)^2}$
$E_j=\frac{F_j}{q_j}=\sum\limits_{i=0}^{j}\frac{q_i}{(i-j)^2}-\sum\limits_{i=j}^{n}\frac{q_i}{(i-j)^2}$ 令$f(i)=q_i,g(i)=\frac{1}{i^2}$
则原式, $E_j=\sum\limits_{i=0}^{j}f(i)g(j-i)-\sum\limits_{i=0}^{n-j}f(i+j)g(i)$　　左边已经是卷积形式了，考虑右边。　　把右边拆开，$f(j)g(0)+f(j+1)g(1)+...+f(j+(n-j))g(n-j)$.
做一下翻转$f(j)=f'(n-j)$.
$\sum\limits_{i=j}^{n}f(i)g(i-j)=\sum\limits_{i=0}^{n-j}f'(n-(j+i))g(i)$
然后右边也是卷积形式了。　　设$A(x)=\sum\limits_{i=0}^{n}f(i)$,$B(x)=\sum\limits_{i=0}^{n}f'(i)$,$C(x)=\sum\limits_{i=0}^{n}g(i)$.
$E_j$等于$A(x)\cdot C(x)$的第$j$项系数和$B(x)\cdot C(x)$的第$n-j$项系数之差。　　

#include <bits/stdc++.h>
using namespace std;

typedef complex<double> cp;
const int N = 8e5 + 5;
const double pi = acos(-1.0);
int n, l, len, rev[N];
cp a[N], b[N], c[N];

void fft(cp *a, int n, int inv) {
    for (int i = 1; i < n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int k = 1; k < n; k <<= 1) {
        cp wn(cos(pi / k), inv * sin(pi / k));
        for (int i = 0; i < n; i += k * 2) {
            cp w(1, 0);
            for (int j = 0; j < k; j++, w *= wn) {
                cp x = a[i + j], y = w * a[i + j + k];
                a[i + j] = x + y, a[i + j + k] = x - y;
            }
        }
    }
    if (inv < 0) for (int i = 0; i < n; i++) a[i] /= n;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &a[i]);
        b[n - i] = a[i];
        c[i] = 1.0 / i / i;
    }
    len = 1;
    while (len <= n * 2) len <<= 1, l++;
    for (int i = 0; i < len; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
    fft(a, len, 1), fft(b, len, 1), fft(c, len, 1);
    for (int i = 0; i < len; i++) {
        a[i] = a[i] * c[i];
        b[i] = b[i] * c[i];
    }
    fft(a, len, -1); fft(b, len, -1);
    for (int i = 1; i <= n; i++) {
        printf("%lf\n", a[i].real() - b[n - i].real());
    }
    return 0;
}

LOJ6216 雪花挂饰

发表于 2020-08-29 更新于 2023-12-07 分类于题解

题目链接

从$n$片雪花里面选$i$个的方案数是$\tbinom{n}{i}$个.
根据Cayley定理,$i$个有标号的点形成无根树的方案数是$i^{i-2}$.
所以选择$i$片雪花时的方案数是$\tbinom{n}{i}i^{i-2}$.
对于一个区间答案是$\sum\limits_{i=l}^{r}\tbinom{n}{i}i^{i-2}$.
因为询问较多可以用前缀和优化.
$ans_{l,r}=(sum[r]-sum[l-1)\ mod\ P=(sum[r]\ mod\ P+sum[l-r]\ mod\ P)\ mod\ P$.
时间复杂度$O(nlogn)$.

//CCCCCCCCCCCCCCCOrz
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int MOD, n, T, sum[N], fac[N], ifac[N];

int C(int n, int m) {
    return fac[n] * 1ll * ifac[m] % MOD * ifac[n - m] % MOD;
}
int fpow(int a, int b) {
    int ans = 1;
    for (; b; b >>= 1, a = a * 1ll * a % MOD) if (b & 1) ans = ans * 1ll * a % MOD;
    return ans;
}

int main() {
    scanf("%d%d%d",&n, &T, &MOD);
    fac[0] = ifac[0] = ifac[1] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * 1ll * i % MOD;
    for (int i = 2; i <= n; i++) ifac[i] = (MOD - MOD / i) * 1ll * ifac[MOD % i] % MOD;
    for (int i = 2; i <= n; i++) ifac[i] = ifac[i - 1] * 1ll * ifac[i] % MOD;
    for (int i = 2; i <= n; i++) sum[i] = (sum[i - 1] * 1ll + fpow(i, i - 2) * 1ll * C(n, i)) % MOD;
    while(T--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", (sum[r] - sum[l - 1] + MOD) % MOD);
    }
    return 0;
}

LOJ10202 樱花

发表于 2020-08-29 更新于 2023-12-07 分类于题解

题目

求不定方程
\[\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}\]
的正整数解$(x,y)$的个数。

题解

因为正整数$x,y$，所以$x,y>n!$。
设$x=n!+a$，$y=n!+b$。$a,b>0$。
可以把式子化为$a\times b=(n!)^2$。
只要将$(n!)^2$分解一下，约数个数是$\prod_{i=1}^{k} q_i+1$。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, P = 1e9 + 7;
int a, b, n, fac, cnt[N], prime[N], vis[N], tot;

void pri(int n) {
	vis[1] = 1;
    for(int i = 2; i <= n; i++) {
    	if(!vis[i]) prime[++tot] = i;
    	for(int j = 1; j <= tot && i * prime[j] <= n; j++) {
    	    vis[prime[j] * i] = 1;
    	    if(i % prime[j] == 0) break;	
    	}
    }
}
void calc(int x) {
	for(int i = 1; prime[i] * prime[i] <= x; i++) {
        while(x % prime[i] == 0) {
        	x /= prime[i];
        	cnt[prime[i]]++;
        }
	}
	if(x != 1) cnt[x] += 1;
}

int main() {
	cin >> n; pri(n);
	for(int i = 1; i <= n; i++) calc(i);
	int ans = 1;
    for(int i = 1; i <= n; i++) {
        ans = ans * 1ll * (cnt[i] * 2 + 1) % P;
    }
    cout << ans <<'\n';
    return 0;
}

LOJ2958「COCI 2009.10」ALADIN

发表于 2020-08-29 更新于 2023-12-07 分类于题解

类欧几里得算法例题

上午学了类欧,来做道例题练习一下.

题目

懒得说了,链接在上面...

题解

根据题意,每次做$1$操作的时候都是区间覆盖,所以原来的值和新的值没有关系.
假设现在覆盖了区间$l,r$,怎么快速求出区间和呢?
设$n=l-r+1$,
即求
$\ \ \ \ \sum\limits_{i=0}^ni\cdot A\bmod B$
$=\sum\limits_{i=0}^{n}i\cdot A-\left\lfloor\frac{i\cdot A}{B}\right\rfloor \cdot B$
$=A\cdot\sum\limits_{i=0}^ni-B\cdot\sum\limits_{i=0}^n\left\lfloor\frac{i\cdot A}{B}\right\rfloor$

观察发现,左边就是一个等差数列,考虑右边怎么做.
也就是这个式子 $ f(a,b,c,n)={i=0}^n $, 只不过是$b=0$的情况.
$ f(a,b,c,n)={i=0}^n $
$=\sum\limits_{i=0}^n\left\lfloor \frac{\left(\left\lfloor\frac{a}{c}\right\rfloor c+a\bmod c\right)i+\left(\left\lfloor\frac{b}{c}\right\rfloor c+b\bmod c\right)}{c}\right\rfloor$
$=\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor+(n+1)\left\lfloor\frac{b}{c}\right\rfloor+ \sum\limits_{i=0}^n\left\lfloor\frac{\left(a\bmod c\right)i+\left(b\bmod c\right)}{c} \right\rfloor$ $=\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor +(n+1)\left\lfloor\frac{b}{c}\right\rfloor+f(a\bmod c,b\bmod c,c,n)$

现在只用考虑$a<c,b<c$的情况.
把式子变化一下, 因为想消去$i$,所以增加一个变量, $f(a,b,c,n)=\sum\limits_{i=0}^{n} \sum\limits_{j=0}^{\left\lfloor\frac{ai+b}{c} \right\rfloor -1} 1$
交换求和符号.
$\sum\limits_{j=0}^{\left\lfloor \frac{an+b}{c} \right\rfloor-1} \sum\limits_{i=0}^n\left[j<\left\lfloor \frac{ai+b}{c} \right\rfloor\right]$

因为$j<\left\lfloor \frac{ai+b}{c} \right\rfloor\Leftrightarrow j+1\leq \left\lfloor \frac{ai+b}{c} \right\rfloor\Leftrightarrow j+1\leq \frac{ai+b}{c}\Leftrightarrow cj+c\leq ai+b\Leftrightarrow \left\lfloor\frac{cj+c-b-1}{a}\right\rfloor<i$

所以
$\ \ \sum\limits_{j=0}^{\left\lfloor \frac{an+b}{c} \right\rfloor-1} \sum\limits_{i=0}^n\left[\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor<i\right]$
$=\sum\limits_{j=0}^{\left\lfloor \frac{an+b}{c} \right\rfloor-1}n-\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor$
$=\left\lfloor \frac{an+b}{c} \right\rfloor\times n-f(c,c-b-1,a,\left\lfloor \frac{an+b}{c} \right\rfloor-1)$
发现$a,c$也恰好是交换的,是可以像欧几里得算法那样递归处理.

阅读全文 »

widsnoy's blog

「LibreOJ Round

题目

题解

0分

17分

41分

LOJ2952 赛道修建

LOJ2200 力

LOJ6216 雪花挂饰

LOJ10202 樱花

题目

题解

代码

LOJ2958「COCI 2009.10」ALADIN

题目

题解