信行散记

但行好事，莫问前程

0%

发表于

如果边权 kk​ 在最小生成树中，那么这条边的位置已经在树上被确定了。
如果边权 kk​ 不在最小生成树中，那么这条边的两个端点此时必然属于同一个连通块 Ci，所以
这条边的方案数就是 ∑E(Ci)\sum E(C_i)​，其中 E(Ci)E(C_i)​ 表示连通块 CiC_i​​​​ 中还有多少对点之间没有边，而这就等
于 Ci×(Ci−1)2−E′(Ci)\cfrac{C_i \times (C_i −1)}{2} −E′(Ci)​​，其中 E′(Ci) 是连通块 Ci 中已经连的边数，而我们之前总共连了 k−1k − 1
条边，所以这条边的总方案数就是

(∑Ci×(Ci−1)2)−k+1(\sum{\frac{C_i\times (C_i - 1)}{2}}) - k + 1

根据乘法原理，方案数就是每条边的方案数乘积，而构造方案只需要动态维护当前在同一连通
块 CiC_i 中的还未添加的边，每次从中任选一条作为边权为 k 的边。
考虑如何维护这些边，不难想到用并查集维护连通性，合并两个连通块时将从两边各选一个点
形成的边加入候选集合即可。

阅读全文 »

发表于

离散化不难想到，关键是细节处理。
没有离散化的版本是这样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 1e5 + 10;
int cut[M], l[N], r[N];
int T, n, m, mx;

int main(void)
{
    scanf("%d", &T);
    for (int _ = 1; _ <= T; _++)
    {
        memset(cut, 0, sizeof cut);
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d", l + i, r + i);
            mx = max(mx, r[i]);
            for (int j = l[i] + 1; j < r[i]; j++)
                cut[j]++;
        }
        sort(cut + 1, cut + mx + 1, greater<int>());
        int ans = n;
        for (int i = 1; i <= m; i++)
            ans += cut[i];
        printf("Case #%d: %d\n", _, ans);
    }
}

他甚至没有加差分优化

于是我们只要开若干个数组，存这段位置可以砍断的区间个数个长度，排序后直接模拟。

阅读全文 »

发表于

给两个字符串, A[0], B[0]

然后定义 A[i] = A[i - 1] + B[i - 1], B[i] = A[i - 1] + B[i - 1];
T 个询问

每次求 A[935] 的第 x 个数字

其实这题只要递归做就好了，关键是 $ 2^{935} $ 这个数字太大了……
考场上想到的办法是直接求出使得 $ A,B $ 大小最接近 1e151e15 的一个数，但是有可能出现上一个还没到1e15, 下一个已经是负数了。。就错误了，但是我们可以直接预处理出从 1-935 的字符串长度，太长用 inf 代替，然后直接在函数内部判断大小并递归…

阅读全文 »

发表于

P1965

推个公式，，不复杂的

Ans=(x+m×10k)mod nAns = (x + m \times 10^k) mod\ n

快速幂解决

(就是我不开 long long 只有70分，而题解里都没开 long long … 是我的实现不够好么

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m, k, x;
int ksm(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % n;
        a = a * a % n;
        b >>= 1;
    }
    return res;
}
signed main()
{
    cin >> n >> m >> k >> x;
    cout << (x % n + m % n * ksm(10, k) % n) % n;
    return 0;
}

发表于

P1966

题目大意：
有两个序列A, B, 长度为n
定义分值为 ∑i=1n(Ai−Bi)2\sum\limits^{n}_{i=1} (A_i - B_i)^2
求让 A, B 达到最大分值的最小交换次数

阅读全文 »

发表于

P1981

这道题其实本身很简单。。
以 ‘+’ 分段，然后对于每一个段(只有乘法)做，然后计算时不要忘了时刻 % 10000
我就是加上最后一个数没有 % 10000。。40分

阅读全文 »

发表于

核心：枚举中心点！
由于两点必然有一个中心，我们枚举这个中心就好啦
然后对于每一个点都计算一下贡献.
代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6, M = 3e5;
struct Edge
{
    int e, ne;
    Edge() { e = ne = 0; }
} edge[N];
int head[M], idx = 0;
void add(int a, int b)
{
    idx++, edge[idx].e = b, edge[idx].ne = head[a], head[a] = idx;
}
long long w[M];
int main()
{
    int n;
    scanf("%d", &n);
    int a, b;
    for (int i = 0; i < n - 1; i++)
    {
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    for (int i = 1; i <= n; i++)
        scanf("%lld", &w[i]);
    long long sum = 0, maxn = 0;
    long long he, rmax;
    for (int i = 1; i <= n; i++)
    {
        int u = head[i];
        he = (rmax = w[edge[u].e]) % 10007;
        u = edge[u].ne;
        for (; u != 0; u = edge[u].ne)
        {
            sum = (sum + he * w[edge[u].e]) % 10007;
            maxn = max(maxn, rmax * w[edge[u].e]);
            he = (he + w[edge[u].e]) % 10007;
            rmax = max(rmax, w[edge[u].e]);
        }
    }
    printf("%lld %lld", maxn, (sum * 2) % 10007);
    return 0;
}

解方程这题
秦九韶公式可以加速计算
另外防止爆 long long 模大质数就好了

发表于

P2239

观察一下规律，不难发现：

如果是第 11 行，那么第 jj 列的数字就是 jj
如果是第 nn 列，那么第 ii 行的数字就是 n+i−1n + i − 1
如果是第 n 行，那么第 j 列的数字就是 3×n−2−j+13 \times n - 2 - j + 1
如果是第 1 列，那么第 i 行的数字就是 4×n−4−i+24 \times n - 4 - i + 2
然后

阅读全文 »

发表于

首先 5 分还是很好拿的。只要dfs一下，记录从根到i的最大值和路径权值和，然后对于给出的数a, b, 输出sum[a] + sum[b] - max(mx[a], mx[b])

然后直接讲满分做法吧

阅读全文 »