做题笔记

Orange_qwq · 2022-02-08 13:17:59 · 个人记录

这个屑太菜了，之前写的都不知道是什么 ** 玩意，请大家忽略

2022

2 - 8

P1426（红）

坑：要先判断，再运算。

结果还是调了 10 分钟。

~~upd 2022.10.5： sb 吧，红提还要写那么久 /ruo~~

P7303（橙）

白痴构造题。直接从 1 枚举到 n - 1 按照 1 至 n - 1 的递加数列输出，最后一个输出 k 减掉已经输出的数的总和。

~~upd 2022.10.5： sb 吧，橙题还感觉爽，我看是你脑子坏掉了~~

2 - 9

P8115（橙）

打月赛那天是写出了 80 分，最后一个点 TLE 。

那时候主程序是这样写的（后来发现这样写是错的）：

while (1) {
    cin >> c, cout << c;
    if (c == '}') return 0;

然后我就很疑惑，看了一位大佬的代码，然后算了算我的时间复杂度，感觉我的不会超时啊。。。

加了快读快输，全 WA 。

去问了另一位大佬，发现不能用快读，因为是 ull 类型的，就改了一下，变成最后一个点是 3ms ，但是答案错误。我发现了一个问题，就是如果输入是 {} ，会输出 {0}（感谢 @Liu_Kevin 指出问题 sto LK orz）

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

#define ull unsigned long long
ull x, l, lx;
char ans[200010], c;
int cnt;
const char ta[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};

inline void write(int x) {
    char F[200];
    int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-') ;
    int cnt = 0 ;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]) ;
} 

char* _16(ull a) {
    int num[210], i = 0;
    cnt = 0;
    memset(ans, 0, sizeof(ans));

    while (a > 0)
        num[++i] = a % 16, a /= 16;
    for (; i > 0; --i) ans[cnt++] += ta[num[i]];
    return ans;
} 

ull _l(ull a) {
    ull i = 0;
    while (a) a /= 10, ++i;
    return i;
}

int main() {
    while (1) {
        cin >> c, cout << c;
        if (c == '}') return 0;
        if (scanf("%llu", &x) == 0) continue;

        _16(x);
        l = _l(x), lx = cnt + 2;

        //cout << _16(x).length() << "&" << _l(x) << "&" << _16(x) << "=" << x << " ";

        if (l < lx) printf("%llu", x);
        else {
            printf("0x");
            for (int i = 0; i < cnt; ++i)
                putchar(ans[i]);
        }
    }
}

~~upd 2022.10.5： sb 吧，橙题还要问~~

P1104（橙）

傻逼题我都能 WA 我真牛逼啊。。。

狂改了一阵，感觉没问题了，~~搞死我了~~，还是 RE ，我就一边改成冒泡一边想，还没写完就突然发现我 string 用 scanf 了。。。改成了 cin ，果然没问题了。。。

提交上去。。。最后两个点 WA 。

我再看代码，发现我最后一个判断错了，总是想着年龄大的排前面，结果输入的顺序就也是 < 了。。。然后才 AC。。。

真的是太菜了 /kk

~~upd 2022.10.5： sb 吧，橙题还这么 sb，我看是你脑子坏掉了~~

贴一下代码吧。。。

#include <bits/stdc++.h>
using namespace std;
int n;
struct xxs{
    int y, m, d, t;
    string s;
} a[105];

bool cmp(xxs a, xxs b) {
    if      (a.y != b.y) return a.y < b.y;
    else if (a.m != b.m) return a.m < b.m;
    else if (a.d != b.d) return a.d < b.d;
    else return a.t > b.t;
}

void inp(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        cin >> a[i].s, scanf("%d%d%d", &a[i].y, &a[i].m, &a[i].d), a[i].t = i;
}

int main() {
    inp();
    stable_sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; ++i) cout << a[i].s << endl;
}

P1271（橙）

傻逼桶排。数据太大。直接上代码。

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

int t[1010], x, maxn, n, m;

void inp(void) {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        cin >> x, ++t[x];
}

int main() {
    inp();
    for (int i = 1; i <= n; ++i) 
        if (t[i]) 
            for (int j = 1; j <= t[i]; ++j) cout << i << " ";
}

2 - 10 ~ 2 - 11

P8116（黄）

月赛第二题。数论。

是听了一个大佬讲的才懂的 /kk

我太弱了 /kk

~~就是说，很显然，就是那个很明显的，就可以看出来的东西，例如说题面举的那个 1 ÷ (1 ÷ 3) 就可以看出来，必须是因子。~~

然后我们就知道必须是因子了对吧，那我们就得整除对吧？

我们先设想要判断是否合法的数为 x 。

我们怎么做除法呢？~~很显然除不尽，~~ 例如说 10 进制的，在有小数的情况下，我们是不是把它 *10 然后继续除？但是，这是有限的，因为显示屏只有 k 位， 0 占了一位。所以，我们就可以得到：想要判断 x 是否合法，就判断 b^{k - 1}是否能整除 x 。

所以，只要求出 b^{k - 1} 能整除的所有数的数量就好了对吧？

然后，~~你转念一想~~，这不就是在求 b^{k - 1} 的因子个数吗？！？！

~~而且通过亿点数学技巧~~，这里其实就是求 b 的因子分别 * (k - 1) 。

然后，就可以啦~

整理亿下思路：

求 b 的质因数 -> 求因子个数

思路就出来啦~

对了对了，别忘了开 long long 哦~

放代码：

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

long long b, k, num[200010], ans, n, cnt;
vector <int> v;
const int mod = 998244353;

bool isp(int x) {
    if (x < 2) return 0;
    for (int i = 2; i <= sqrt(x); ++i)
        if (x % i == 0) return 0;
    return 1;
}

void run(void) {
    cin >> b >> k;
    n = b, ans = 1, cnt = 0, v.clear();
    memset(num, 0, sizeof(num));

    for (int i = 2; i <= sqrt(b); ++i) {
        if (!isp(i) || n % i != 0) continue;

        v.push_back(i), cnt++;
        while (n % i == 0) num[i]++, n /= i;
    }

    if (n != 1) v.push_back(n), num[n]++;

    for (int i = 0; i < cnt; ++i) {
        num[v[i]] = (num[v[i]] * (k - 1)) % mod;
        ans = (ans * (num[v[i]] + 1)) % mod;
    }
    cout << ans % mod << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) run();
}

P1177（橙）

~~快排啊孩子~~

~~我竟然不会了快排了~~

额，就是两边从中间搜，然后换换换，然后再分开，重复上面步骤。

void qs(int a[], int l, int r) {
    int i = l, j = r, f = a[(l + r) / 2];
    do {
        while (a[i] < f) ++i;
        while (a[j] > f) ++j;
        if (i <= j)
            swap(a[i], a[j]), ++i, --j;
    } while (i <= j);
    if (l < j) qs(a, l, j);
    if (i < r) qs(a, i, r);
}

wtcl 呜呜呜

2 - 12

P2036（橙）

搜索。

但是比较巧妙。

~~upd 2022.10.5： sb 吧，橙题还不太会写，我看是你脑子坏掉了~~

直接贴代码。

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

int s[15], b[15], n, ans = 0x7fffffff;

void dfs(int i, int x, int y) {
    if (i > n) {
        if (x == 1 && y == 0) return;
        ans = min(ans, abs(x - y));
        return;
    }
    dfs(i + 1, x * s[i], y + b[i]);
    dfs(i + 1, x, y);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) 
        cin >> s[i] >> b[i];
    dfs(1, 1, 0);
    cout << ans;
    return 0;
}

2 - 13

P8152（红）

直接贴代码（数论）。

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

#define ll long long
ll n, k;
const ll mod = 998244353;

int main() {
    scanf ("%d%d", &n, &k);
    printf("%lld", ((n * n * 1ll % mod - 1ll) * k % mod + 1) % mod);
}

2 - 15

P1480（橙）

高精度模拟，高精度除以单精度。

模拟竖式。

就求出商，然后搞搞余数，然后输出，还一边判断前导零。

挺高科技的。

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

long long a, b, s, y, pd;
string aa;

int main() {
    cin >> aa >> b;
    for (int i = 0; i < aa.length(); ++i) {
        a = aa[i] - '0';
        y = y * 10 + a;
        s = y / b;
        y %= b;
        if (pd || s) pd = 1;
        if (pd) cout << s;
    }
}

还是看题解学会的。太弱了 /kk

2 - 16

P2240（黄）

还是看题解的。。。太弱了。。。

其实是二分。

很难想到。（迫真）

就是二分求长度，段数，如果多了就说明可以在长，少了就再短。

这么简单我都不会。。。智商堪忧

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k, ans, a[100010];
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int l = 0, r = 100000010, m;
    while (l + 1 < r) {
        m = (l + r) / 2, ans = 0;
        for (int i = 1; i <= n; ++i) ans += a[i] / m;
        if (ans >= k) l = m;
        else r = m;
    }
    cout << l;
}

--- ## 2 - 19 + [P8143](https://www.luogu.com.cn/problem/P8143)（黄）数论的。月赛题。月赛那天搞了一个暴力都搞错了。。。还调了那个暴力 2h。。。而且调不好 /ll 然后就想应该是排列之类的。但是想不出来。后来看了题解，发现是 $\dfrac{n!}{2}$。~~而且我自己也退不出来~~ 然后还 WA 了好几次，也不知道为什么。 $n!$ 我能理解，但是不知道为什么要 $/2$ 。呜呜呜我还是太弱了这个坑就留着，等我会了在补齐。 $\texttt{upd on 2023.1.18}

当我们改变排列 p 中的一个数时，环的数量也会随之改变，可以理解为奇数个环的情况和偶数个环的情况是成对出现的。

奇数个环和和偶数个环的情况总数为 n 的全排，所以答案就是 \dfrac{n!}{2}。

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int main() {
    long long n, ans = 1ll;
    cin >> n;
    if (n == 1) {
        cout << 0;
        return 0;
    }
    for (int i = 3; i <= n; ++i)
        ans = (ans * i) % mod;
    cout << ans;
}

2 - 20

P1577（黄）

二分。

WA 了好多次，都不知道为什么

其实跟这道题差不多，就是精度的问题。

还有，判断的时候应该是 r - l >= 1e-7 。

并且，转换为 int 类型的表达式也要加括号。

代码：

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

double a[100010], l, r, m;
int n, k;

bool chk(double m) {
    int cnt = 0;
    for (int i = 1; i <= n; ++i) cnt += (int)(a[i] / m);
    return cnt >= k;
}

int main() {
    cin >> n >> k;
    r = 1e9, l = 0;
    for (int i = 1; i <= n; ++i) scanf("%lf", &a[i]);
    while (r - l >= 1e-7) {
        m = (l + r) / 2;
        if (m == 0) break;
        //cout << cnt << " " << l << endl;
        if (chk(m)) l = m;
        else r = m;
    }
    printf("%.6lf", l);
}

2 - 21

P1093（橙）

【】 cmp 毁我青春 /fn

```cpp bool cmp(xxs a, xxs b) { if (a.d != b.d) return a.d > b.d; if (a.a != b.a) return a.a > b.a; return a.id < b.id; } ``` ## 2 - 23 + [P8109](https://www.luogu.com.cn/problem/P8109)（黄）贪心。看了半天题面，终于弄明白是，，，， ~~其实我什么都不明白~~ 但是就是求每一组数 $a_i,b_i$ 的最小值的和。因为已经是排好序的了，就不用排序。然后队伍太多了气球不够也不行，队伍少但气球多也没用。就变成了求最小值了。只有 $4$ 个测试点， $10$ 行搞定。 ```cpp #include <bits/stdc++.h> using namespace std; int n, a[100010], b[100010], ans; int main() { cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) cin >> b[i]; for (int i = 1; i <= n; ++i) ans += min(a[i], b[i]); cout << ans; } ``` ## 3 - 2 + [P1056](https://www.luogu.com.cn/problem/P1056)（黄）应该是桶排。。。看不出是贪心诶（就是说，思路比较明显，桶排每行或每列之间，求出 ~~xxs~~ 交头接耳最多的，然后就输出就好了。为什么不边处理边输出？因为考虑到编号从小到大的顺序，所以得记录下去然后在统计。还有每行每列之间要搞清楚，同一列的要看行，同一行的要看列。 ```cpp #include <bits/stdc++.h> using namespace std; int m, n, k, l, d; int x[1010], y[2010], t1[1010], t2[1010]; void inp(void) { cin >> m >> n >> k >> l >> d; int x1, y1, x2, y2; for (int i = 1; i <= d; ++i) { cin >> x1 >> y1 >> x2 >> y2; if (x1 == x2) x[min(y1, y2)]++; else y[min(x1, x2)]++; } } void run(void) { int maxn, org; for (int i = 1; i <= k; ++i) { maxn = -1; for (int j = 1; j <= m; ++j) if (maxn < y[j]) maxn = y[j], org = j; y[org] = 0; t2[org] = 1; } for (int i = 1; i <= l; ++i) { maxn = -1; for (int j = 1; j <= n; ++j) if (maxn < x[j]) maxn = x[j], org = j; x[org] = 0; t1[org] = 1; } } void out(void) { for (int i = 1; i <= m; ++i) if (t2[i]) cout << i << " "; cout << endl; for (int i = 1; i <= n; ++i) if (t1[i]) cout << i << " "; } int main() { inp(); run(); out(); } ``` $\texttt{upd on 2023.1.18}$ R 君马蜂对我影响深刻啊，，，不过为啥只有这一题是写的 R 君的马蜂 /youl ## 3 - 9 + [P1094](https://www.luogu.com.cn/problem/P1094) （橙）贪心。考虑到最少的分组情况，而且最多就是两个，可以想到等差数列求和，就是最大的加最小的、第二大的加第二小的……这样子分。所以就可以从最大开始枚举，搞个坐标 $l$ 表示从左边开始加的，然后就很简单了。 ```cpp #include <bits/stdc++.h> using namespace std; int w, n, a[100010], ans, cnt, l, r; int main() { cin >> w >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; sort(a + 1, a + 1 + n); l = 1; for (int i = n; i >= l && a[i] != -1; --i) { ++ans; if (a[i] + a[l] <= w) { a[l] = -1; ++l; } } cout << ans; } ``` + [P1097](https://www.luogu.com.cn/problem/P1097)（橙）思路很简单，但写法要记住（写法格式是看题解的……） ```cpp #include <bits/stdc++.h> using namespace std; int n, t; set <int> a; map <int, int> b; int main() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> t; a.insert(t); b[t]++; } set<int>::iterator it; for (it = a.begin(); it != a.end(); ++it) cout << *it << " " << b[*it] << endl; } ``` ## 3 - 12 + [P2639](https://www.luogu.com.cn/problem/P2639)（橙） + [P2925](https://www.luogu.com.cn/problem/P2925)（橙） 0 - 1 背包双倍经验。在这里不挂代码，挂上 0 - 1 背包的模板。（滚动数组版） ```cpp #include <bits/stdc++.h> using namespace std; int n, V, v[35], w[35], dp[20010]; int bag(void) { for (int i = 1; i <= n; ++i) for (int j = V; j >= 0; --j) if (j - v[i] >= 0) dp[j] = max(dp[j], dp[j - v[i]] + w[i]); return V - dp[V]; } int main() { cin >> V >> n; for (int i = 1; i <= n; ++i) cin >> v[i], w[i] = v[i]; cout << bag(); } ``` [具体 0 - 1 背包模板问题](https://www.luogu.com.cn/problem/P1049) ## 3 - 13 ~ 4 - 24 咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕 ## 4 - 25 + [AT2642](https://www.luogu.com.cn/problem/AT2642)（绿）根据机房大佬的说法，这是一道绿皮红。 ~~确实~~ 排列组合 + 分类讨论。 + $n$ 和 $m$ 相差大于 $2$ 时，输出 $0$。 + $n != m$ 时，$n! * m! * 2

n = m$ 时，$n! * m!

代码

#include <bits/stdc++.h>
using namespace std;
long long a, b, n, m;
const long mod = 1e9 + 7;
int main() {
    cin >> n >> m;
    if (abs((double)n - m) > 1) {
        cout << 0;
        return 0;
    }
    a = 1ll, b = 1ll;
    for (int i = 1; i <= n; ++i) a = a * i % mod;
    for (int i = 1; i <= m; ++i) b = b * i % mod;
    a %= mod, b %= mod;
    a = a * b % mod;
  // 疯狂取模
  // 怕越界（
    if (n == m) a = a * 2 % mod;
    cout << a;
    return 0;
}

5 - 1

P2367（黄）

按照差分的套路来就好，但有细节要注意：

都说了是差分，那就别忘记差分！！！
单点标记：f[x] += z, f[y + 1] -= z;
因为f[i] = a[i] - a[i - 1]，所以 a[i] = a[i - 1] + f[i];
ans = min(ans, a[i]); 是 a[i]！！！！！！（Orange 日常脑残）

代码

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

int n, q, x, y, z, a[5000010], f[5000010], ans;

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i], f[i] = a[i] - a[i - 1];
    while (q--) {
        cin >> x >> y >> z;
        f[x] += z, f[y + 1] -= z;
    }
    ans = 0x3fffffff;
    for (int i = 1; i <= n; ++i) {
        a[i] = a[i - 1] + f[i];
        ans = min(ans, a[i]);
    }
    cout << ans;
}

~~（马蜂逐渐难看）~~

P3397（橙）

二维差分 + 前缀和。

可以算是二维差分的模板题吧。

如图

前缀和：f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];（直接前缀和因为他本来是 0）

代码

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

int n, m, a, b, c, d, f[1010][1010];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> a >> b >> c >> d;
        ++f[a][b], ++f[c + 1][d + 1];
        --f[c + 1][b], --f[a][d + 1];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
            cout << f[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

%老师说我代码很漂亮

P1947（橙）

~~抄题面代码的~~

extern "C" int Seniorious(int);

extern "C" int Chtholly(int n, int OvO) {
    int ans = 1;
    for (int l = 1, r = n, mid = (l + r) >> 1; l <= r; mid = (l + r) >> 1) 
        if (Seniorious(mid) >= 0) r = (ans = mid) - 1;
        else l = mid + 1;
    return ans;
}

5 - 2

P3078（黄）

差分思维题。

比较难想。

一开始的时候，想了半个多钟头的差分想不出来，然后看了题解，把贪心的看明白了，差分的反而没看明白……然后去问了一位巨佬 _edge_，最后才懂了的 /youl

wtcl /kk

先是差分，然后每次就可以消一个正数的 1 ，加一个负数的 1。到最后应该就变成若干个正数和若干个 0，把正数都给消掉就可以了。

记得开 ll （

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

long long n, a[100010], f[100010], ans, s;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], f[i] = a[i] - a[i - 1];
    for (int i = 1; i <= n; ++i) {
        ans += f[i];
        if (f[i] < 0) s += f[i];
    }
    ans += -s;
    // sto edge orz
    // %%%%%%%%%%%
    cout << ans;
    return 0;
}

P4552 （绿）

还是差分思维题。

做法：

差分。
分别统计正数、负数。
取正数、负数绝对值大的作为最少操作次数。
正数、负数的差的绝对值 + 1 就是最终能得到的结果总数。

为什么？

差分不用说了吧
正数、负数，理论上是应该能够相互抵消的，但为了使他成为所有数的值一样，咱就固定第一个数，然后后面的数去加和减。
取绝对值大的作为最少操作次数也不用说了吧，，，，
差 +1 就是说你最后剩下的可以和前面第一个数抵消也可以和最后一个数抵消。

代码：

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

#define ll long long int
ll n, ans, s, a[100010], f[100010];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], f[i] = a[i] - a[i - 1];
    for (int i = 2; i <= n; ++i) {
        if (f[i] > 0) ans += f[i];
        else s += f[i];
    }
    s = -s;
    cout << max(ans, s) << endl << abs(ans - s) + 1;
    return 0;
}

P5542（黄）

二维差分。

套上去就好了。

但有要注意的地方：

他涂的是点，所以标记时不用 +1。

然后就没有然后了。

\texttt{Code}

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

#define ll long long
ll n, k, s[1010][1010], f[1010][1010], ans, a, b, c, d;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a >> b >> c >> d;
        ++a, ++b, ++c, ++d;
        ++f[a][b], ++f[c][d];
        --f[c][b], --f[a][d];
    }
    for (int i = 1; i <= 1001; ++i) 
        for (int j = 1; j <= 1001; ++j) {
            f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
            if (f[i][j] == k) ++ans;
        }
    cout << ans;
    return 0;
}

P2434（黄）

有多种解法。

1. 直接搞

参照第一篇题解的做法，用两个桶弄头和尾，采用叠加计数的方法搞。

2. 使用结构体

新建结构体存头和尾，然后遍历，把尾搞到最大，然后没有了就输出尾，然后继续找头。

3. 差分

连续的区间，连续的不等于 0，于是就可以做啦~

于是就出现了一个坑点：单点会抵消成 0。

没关系，特判一下就好啦~

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

#define M 1000010
int n, x, y, t, f[M], a[M], b[M];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x >> y;
        ++f[x], --f[y];
        ++a[x], ++b[y];
    }
    for (int i = 1; i < M; ++i) {
        f[i] += f[i - 1];
        if (f[i] > 0 && !t) cout << i << " ", t = 1;
        else if (f[i] <= 0 && t) cout << i << endl, t = 0;
        else if (!f[i] && !t && b[i]) cout << i << " " << i << endl;
    }
    return 0;
}

5 - 3

P8318（红）

坑人的倒推题目。

注意：特别且显然地，当 x=y，新的 x 就等于原来的 x 的两倍或平方。

然后要注意倒推。

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

#define ll long long int
int n, m;
ll a[1010], b[1010], x[210], y[210], _[210];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) cin >> _[i] >> x[i] >> y[i];
   // 看好了，下面要倒推
    for (int i = m; i >= 1; --i) {
        if (_[i] == 1) {
            if (x[i] != y[i]) a[x[i]] -= a[y[i]];
            else a[x[i]] /= 2; // 坑点 * 1
        } else {
            if (x[i] != y[i]) a[x[i]] /= a[y[i]];
            else a[x[i]] = sqrt(a[x[i]]); // 坑点 * 2
        }
    }
    for (int i = 1; i <= n; ++i) cout << a[i] << " ";
    return 0;
}

P8284（橙）

数学构造。

一开始是想着一个一个质数往后弄，然后看了看题解，结果发现 a_{n-1} = \gcd(a_n) = a_n，所以数列 a 全部数字都相同。

所以如果 k \le n 就输出 Impossible，否则就全输出 5 or more，然后从 1 开始输出随便搞搞就过了。（雾）

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

int n, k, t;

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> k;
        if (n > k) {
            cout << "Impossible" << endl;
            continue;
        }
        cout << "5 or more" << endl;
        for (int i = 1; i <= 5; ++i) {
            for (int j = 1; j <= n; ++j) cout << i << " ";
            cout << endl; 
        } 
    }
    return 0;
}

P1191（绿）

垂线法 + 枚举。

//https://www.luogu.com.cn/problem/P1191
#include <bits/stdc++.h>
using namespace std;

int n, a[200][200];
long long ans, t, s[200];
char c;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> c;
            if (c == 'W') ++a[i][j], ++s[j];
            else s[j] = 0; 
        }
        for (int j = 1; j <= n; ++j) {
            t = s[j];
            for (int k = j; k <= n; ++k) {
                if (!s[k]) break;
                t = min(t, s[k]);
                ans += t;
            }
        }
    }
    cout << ans;
    return 0;
}

P4387（黄）

突然感觉我好菜我自己切了一道黄题 /youl

每入栈一个数，然后就出栈。

最后判断一下。

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

int n, a[100010], b[100010], l;
stack <int> s;

int _(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    l = 1;
    while (!s.empty()) s.pop();
    for (int i = 1; i <= n; ++i) {
        s.push(a[i]);
        while (s.top() == b[l]) {
            s.pop(), ++l;
            if (s.empty()) break;
        }
    }
    return s.empty();
}

int main() {
    int t;
    cin >> t;
    while (t--) 
        cout << (_() == 1 ? "Yes" : "No") << endl;
    return 0;
}

阴间函数名别在意 /youl

5 - 4

P8319（黄）

质数筛。。。

首先要明确一个重点信息：约分不算在操作次数内。

为了让操作次数最大，那就要保证中间没有约分，即分子在 1 到 x-1 的区间内都要与 x 互质，所以 x 必须是个质数，也就是说，答案是 n 以内的最大质数。

普通筛法没法过，只能用质数筛。

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

#define M 2000010
long long cnt, p[M], n, ans;
bool ip[M];

void GP(void){
    for (int i = 2;i <= M; ++i) {
        if (!ip[i]) p[++cnt] = i;
        for (int j = 1; j <= cnt && i * p[j] <= M; ++j) {
            ip[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}

int main() {
    int t;
    cin >> t;
    GP();
    while (t--) {
        cin >> n;
        ans = 0;
        for (int i = n; i >= 2; --i)
            if (!ip[i]) {
                ans = i;
                break;
            }
        cout << ans << endl;
    } 
    return 0;
}

P1969（橙）

P3078 的双倍经验。

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

int n, h[100010], f[100010], a, b;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i], f[i] = h[i] - h[i - 1];
    for (int i = 1; i <= n; ++i) {
        a += f[i];
        if (f[i] < 0) b -= f[i];
    }
    cout << a + b;
    return 0;
}

P3197（黄）

数学。

然后我不会，看了题解。

顺便复习了一下快速幂。

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

#define ll long long
ll ans, m, n;
const ll p = 100003;

ll ksm(ll a, ll b) {
    ll cnt = 1;
    while (b) {
        if (b & 1) cnt = cnt * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return cnt;
}

int main() {
    cin >> m >> n;
    ans = (ksm(m, n) % p + p - m * ksm(m - 1, n - 1) % p) % p;
    cout << ans % p;
    return 0;
}

5 - 5

P1605（橙）

是个人都会做的 dfs。

事实证明我是 sb。

交了 5 次才过。。。

就因为没有函数内定义变量。。。然后变量被刷掉了

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

int n, m, t, sx, sy, fx, fy, ans, _, __;
int v[10][10];
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

void dfs(int x, int y) {
    if (x < 1 || y < 1 || x > n || y > m) return;
    if (x == fx && y == fy) {
        ++ans; 
        return;
    }
    // cout << p << " " << q <<endl;
    for (int i = 1; i <= 4; ++i) {
        int p = x + dx[i], q = y + dy[i];
        if (!v[p][q]) 
            v[p][q] = 1, dfs(p, q), v[p][q] = 0;
    }
}

int main() {
    cin >> n >> m >> t >> sx >> sy >> fx >> fy;
    while (t--) {
        cin >> _ >> __;
        v[_][__] = 1;
    }
    v[sx][sy] = 1;
    dfs(sx, sy);
    cout << ans;
    return 0; 
}

5 - 8

P2947（黄）

单调栈模板。

P1901（黄）

单调栈。

左边扫一遍，右边扫一遍，然后加起来就好了。

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

#define M 1000010
long r[M], top, a[M], st[M], n, l[M], anss[M], v[M], ans;

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

    for (int i = 1; i <= n; ++i) {
        while (top > 0 && a[st[top]] <= a[i]) --top;
        anss[st[top]] += v[i];
        st[++top] = i;
    }
    top = 0;
    for (int i = n; i >= 1; --i) {
        while (top > 0 && a[st[top]] <= a[i]) --top;
        anss[st[top]] += v[i];
        st[++top] = i;
    }

    for (int i = 1; i <= n; ++i) ans = max(ans, anss[i]);
    cout << ans;
    return 0;
}

5 - 9

P2788（红）

每日降智。

5 - 10

P2422（绿）

区间和可以用前缀和。

然后找最小值用单调栈。

大体思路是找出每个数在哪个最长的区间内总是为最小值，然后搞一搞就好了。

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

int n, a[100010], l[100010], r[100010], st[100010], top;
long long ans, t, sum[100010];

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

    for (int i = n; i >= 1; --i) {
        while (top > 0 && a[i] <= a[st[top]]) --top;
        r[i] = top == 0 ? n + 1 : st[top];
        st[++top] = i;
    }
    top = 0;
    for (int i = 1; i <= n; ++i) {
        while (top > 0 && a[i] <= a[st[top]]) --top;
        l[i] = top == 0 ? 0 : st[top];
        st[++top] = i;
    }
    ans = -1;
    for (int i = 1; i <= n; ++i) {
        t = a[i] * (sum[r[i] - 1] - sum[l[i]]);
        ans = max(ans, t);
    }
    cout << ans;
    return 0;
}

5 - 11

P1160（黄）

同机房大佬：哇，上来就是个黄，膜拜大佬，快教我回滚莫队、网络流吧。

我：不，大佬先教我单调队列吧。

（实力反差）

我多少年没写链表了。。。

左右不分了都。。。。

看题解调的，还调了好久，上下不分左右不分

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

struct xxx{
    int l, r, t;
} a[100010];
int n, m, k, p, x;

void _(int i, int s, int t) {
    if (t == 0) {
        a[s].r = i;
        a[s].l = a[i].l;
        a[i].l = s;
        a[a[s].l].r = s;
    }
    if (t == 1) {
        a[s].r = a[i].r;
        a[s].l = i;
        a[i].r = s;
        a[a[s].r].l = s;
    }
}

int main() {
    cin >> n;
    a[0].l = a[0].r = 0;
    _(0, 1, 1);
    for (int i = 2; i <= n; ++i) 
        cin >> k >> p, _(k, i, p);
    cin >> m;
    while (m--) 
        cin >> x, a[x].t = 1;
    for (int i = a[0].r; i; i = a[i].r) 
        if (!a[i].t) cout << i << " ";
    return 0;
}

5 - 12

P1886（黄）
P2032（黄）

单调队列。

跟单调栈差不多，只是多了个出队头。

先出队头，再出队尾。

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

#define ll long long
int n, m;
ll a[1000010], q[1000010], l, r;

void min_q(void) {
    l = 1, r = 0;
    for (int i = 1; i <= n; ++i) {
        if (i >= m) while (l <= r && q[l] <= i - m) ++l;
        while (l <= r && a[i] <= a[q[r]]) --r;
        q[++r] = i;
        if (i >= m) cout << a[q[l]] << " ";
    }
}

void max_q(void) {
    l = 1, r = 0;
    for (int i = 1; i <= n; ++i) {
        if (i >= m) while (l <= r && q[l] <= i - m) ++l;
        while (l <= r && a[i] >= a[q[r]]) --r;
        q[++r] = i;
        if (i >= m) cout << a[q[l]] << " ";
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    min_q();
    cout << endl;
    max_q();
    return 0;
}

（单调队列模板）

5 - 15

P1823 （蓝）

单调栈。

本来是想搜左边和右边，然后枚举一下的。~~结果完美挂掉~~

结果发现也不对，于是坚决的重写了。

还有个很坑的：高度相同要算进去。

于是还得弄一个桶。

按照正常套路来，加上一个重复的就好了。

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

#define M 500010
int n, top;
long long a[M], ans, s[M], t[M];

void ddz(void) {
    for (int i = n; i >= 1; --i) {
        while (top > 0 && a[s[top - 1]] <= a[i]) {
            if (a[i] == a[s[top - 1]]) t[i] = t[s[top - 1]] + 1;
            ans += t[s[top - 1]] + 1;
            --top;
        }
        if (top > 0) ++ans;
        s[top++] = i;
    }
}

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

    ddz();
    cout << ans;
    return 0;
}

阴间函数名 *2。（

P3467 （绿）

说实话，题目说了啥我也不知道。

单调栈，然后减掉。

我真不知道题目在写啥。

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

long long n, s[250010], x, a[250010], ans, top;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> x >> a[i];
    for (int i = n; i >= 1; --i) {
        while (top > 0 && s[top] > a[i]) --top;
        if (s[top] == a[i]) ++ans;
        s[++top] = a[i];
    }
    cout << n - ans;
    return 0;
}

P1241 （绿）

比较水的一题，水绿了属于是。

根据题意，扫一遍右括号，打标记，然后残余的就输出整个。

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

int a[110];
string s;

int main() {
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == ')') {
            for (int j = i - 1; j >= 0; --j)
                if (s[j] == '(' && !a[j]) {
                    a[i] = a[j] = 1;
                    break;
                } 
                else if (s[j] == '[' && !a[j]) break;
        }
        if (s[i] == ']') {
            for (int j = i - 1; j >= 0; --j)
                if (s[j] == '[' && !a[j]) {
                    a[i] = a[j] = 1;
                    break;
                }
                else if (s[j] == '(' && !a[j]) break;
        }
    }
    for (int i = 0; i < s.length(); ++i) {
        if (!a[i]) {
            if (s[i] == '(' || s[i] == ')') cout << "()";
            else cout << "[]";
        } else cout << s[i];
    }
    return 0;
}

5 - 17

P1440 （黄）

单调队列。

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

#define ll long long
#define M 2000010
int n, m;
ll a[M], q[M], l, r;

void min_q(void) {
    l = 1, r = 0;
    for (int i = 1; i <= n; ++i) {
        printf("%lld\n", a[q[l]]);
        if (i - q[l] + 1 > m && l <= r) ++l;
        while (l <= r && a[i] < a[q[r]]) --r;
        q[++r] = i;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    min_q();
    return 0;
}

5 - 18

P1571 （橙）

map。

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

long n, m, a[100010], b[100010];
map <int, int> mp;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) cin >> b[i], mp[b[i]]++;
    for (int i = 1; i <= n; ++i) 
        if (mp[a[i]]) cout << a[i] << " ";
    return 0;
}

P1950 （蓝）

P1191 矩形的双倍经验。（？）

用 P1191 的代码交，WA 20分

数组开小了。改大了，WA + TLE 50分。

哦哦，吸氧，AC 了。。。。。 ```cpp #include <bits/stdc++.h> using namespace std; int n, a[1010][1010], m; long long ans, t, s[1010]; char c; int main() { cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> c; if (c == '.') ++a[i][j], ++s[j]; else s[j] = 0; } for (int j = 1; j <= m; ++j) { t = s[j]; for (int k = j; k >= 1; --k) { if (!s[k]) break; t = min(t, s[k]); ans += t; } } } cout << ans; return 0; } ``` + [P1565](https://www.luogu.com.cn/problem/P1565) （蓝）极大矩阵（？）但是太弱了，不会，，，，，前缀和 + 枚举 + $ \texttt{-O2}$ 过了。。。 ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long ll a[210][210], s[210][210], ans, t, m, n; int main() { cin >> n >> m; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> a[i][j], s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) for (int k = i; k <= n; ++k) for (int l = j; l <= m; ++l) { if (s[k][l] + s[i - 1][j - 1] - s[k][j - 1] - s[i - 1][l] > 0) t = (ll) (k - i + 1) * (l - j + 1); if (t >= ans) ans = t; } cout << ans << endl; return 0; } ``` ## 5 - 22 ### R.I.P ### 致敬袁老 ### 愿您在天，看我们丰衣足食 ------------------ ---------------- + [P5743](https://www.luogu.com.cn/problem/P5743) （红）？？？？？ + [P3612](https://www.luogu.com.cn/problem/P3612) （橙）大地龟 ```cpp char f(ll k, ll m, ll x) { if (k == 0) return s[x - 1]; if (x <= m / 2) return f(k - 1, m / 2, x); else if (x == m / 2 + 1) return f(k - 1, m / 2, m / 2); else if (x > m / 2 + 1) return f(k - 1, m / 2, x - (m / 2 + 1)); } ``` 这是递归部分。 $k$ 为字符串 $s$ 需要翻转的次数，$m$ 是目前翻转出来的字符串长度，$x$ 是第几个。 ~~迷信地加上了两个 `else`~~ ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long string s; char f(ll k, ll m, ll x) { if (k == 0) return s[x - 1]; if (x <= m / 2) return f(k - 1, m / 2, x); else if (x == m / 2 + 1) return f(k - 1, m / 2, m / 2); else if (x > m / 2 + 1) return f(k - 1, m / 2, x - (m / 2 + 1)); } int main() { ll n, k = 0, l; cin >> s >> n; l = s.length(); for (; l < n; l *= 2, ++k); // 翻转 cout << f(k, l, n); return 0; } ``` + [P5461](https://www.luogu.com.cn/problem/P5461) （黄）又用递归做了一次。纯模拟递归。 ```cpp #include <bits/stdc++.h> using namespace std; int n = 1, a[1050][1050], N; void inp(void) { cin >> N; for (int i = 1; i <= N; ++i) n *= 2; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) a[i][j] = 1; } void f(int t, int x, int y) { if (t == 2) { a[x][y] = 0; return; } for (int i = x; i <= x + t / 2 - 1; ++i) for (int j = y; j <= y + t / 2 - 1; ++j) a[i][j] = 0; f(t / 2, x, y + t / 2); f(t / 2, x + t / 2, y); f(t / 2, x + t / 2, y + t / 2); } int main() { inp(); f(n, 1, 1); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) cout << a[i][j] << " "; cout << endl; } return 0; } ``` ## 5 - 28 + [P2786](https://www.luogu.com.cn/problem/P2786) （黄）这题终于过了…… map…… 就是很坑…… 要考虑到 `单词 + 标点 + 单词` 的情况…… ```cpp while (cin >> a) { s = ""; for (int i = 0; i < a.length(); ++i) { if (a[i] != ' ' && a[i] != ',' && a[i] != '.' && a[i] != '!' && a[i] != '?') s += a[i]; else ans = (ans % p + m[s] % p) % p, s = ""; } ans = (ans % p + m[s] % p) % p; } ``` ## 6 - 4 要期殁烤逝了呜呜呜 /ll + [AT882](https://www.luogu.com.cn/problem/AT882) （橙）？？？ ```cpp #include <bits/stdc++.h> using namespace std; int l, r, a, ans; map <int, int> t; int main() { cin >> l >> r; for (int i = 1; i <= l; ++i) cin >> a, t[a]++; for (int i = 1; i <= r; ++i) { cin >> a; if (t[a]) ++ans, --t[a]; } cout << ans << endl; return 0; } ``` ## 6 - 5 期殁烤逝…… + [P2982](https://www.luogu.com.cn/problem/P2982) （蓝）树…… 有点恶心…… 大体思路： 1. 差分 + 前缀和 2. dfs 序每走一个过去，会影响到他的子树，所以就…… ```cpp #include <bits/stdc++.h> using namespace std; int lowbit(int x) { return (-x) & x; } int cnt, l[100010], r[100010], n, a, b, tr[100010]; vector < int > tree[100010]; void dfs(int i, int fa) { l[i] = ++cnt; for (int k = 0; k < tree[i].size(); ++k) { int ch = tree[i][k]; if (ch == fa) continue; dfs(ch, i); } r[i] = cnt; } // l 到 r 表示 i 的子树范围 void add (int x, int k) { for (int i = x; i <= n; i += lowbit(i)) tr[i] += k; } int sum(int x) { int s = 0; for (int i = x; i; i -= lowbit(i)) s += tr[i]; return s; } int main() { cin >> n; for (int i = 1; i < n; ++i) { cin >> a >> b; tree[a].push_back(b); tree[b].push_back(a); } dfs(1, 0); for (int i = 1; i <= n; ++i) { cin >> a; cout << sum(l[a]) << endl; add(l[a] + 1, 1), add(r[a] + 1, -1); } return 0; } ``` + [P3368](https://www.luogu.com.cn/problem/P3368) （黄）模板题。 ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long ll n, m, tr[500010], t, a, l, r, k; ll lowbit(ll x) { return (-x) & x; } void add(ll x, ll k) { for (ll i = x; i <= n; i += lowbit(i)) tr[i] += k; } ll sum(ll x) { ll s = 0; for (ll i = x; i; i -= lowbit(i)) s += tr[i]; return s; } int main() { cin >> n >> m; for (int i = 1; i <= n; ++i) { cin >> a; add(i, a - t); t = a; } while (m--) { cin >> a; if (a == 1) cin >> l >> r >> k, add(l, k), add(r + 1, -k); else cin >> a, cout << sum(a) << endl; } return 0; } ``` + [P1219](https://www.luogu.com.cn/problem/P1219) （黄）呃呃呃这题……~~之前做过~~ 按照题意模拟即可。 ```cpp // 2022.6.5 #include<bits/stdc++.h> using namespace std; #define MAXN 200 int a[MAXN], n, ans; int l[MAXN], z[MAXN], f[MAXN]; void dfs(int x) { if (x > n) { ans++; if (ans <= 3) { for (int i = 1; i <= n; ++i) printf("%d ",a[i]); cout << endl; } return; } for (int i = 1; i <= n; ++i) { if (l[i] == 0 && z[x + i] == 0 && f[x - i + 10] == 0) { a[x] = i; l[i] = 1, z[x + i] = 1, f[x - i + 10] = 1; dfs(x + 1); l[i] = 0, z[x + i] = 0, f[x - i + 10] = 0; } } } int main(){ cin >> n; dfs(1); cout << ans; return 0; } ``` + [P1238](https://www.luogu.com.cn/problem/P1238) （黄）这题不同于普通 dfs 之处：要把路线标记好，要不然回溯时就没有了。坑点：顺序 ```cpp #include<bits/stdc++.h> using namespace std; int n, m, fx, fy, sx, sy, a[20][20]; int v[20][20], ans, _[420][3], cnt; const int dx[] = {0, -1, 0, 1}; const int dy[] = {-1, 0, 1, 0}; void dfs(int x, int y) { if (x == sx && y == sy) { for (int i = 1; i <= cnt; ++i) printf("(%d,%d)->", _[i][1], _[i][2]); printf("(%d,%d)\n", x, y); ++ans; return; } v[x][y] = 1; //printf("(%d,%d)->", x, y); _[++cnt][1] = x, _[cnt][2] = y; for (int i = 0; i < 4; ++i) { int xx = x + dx[i], yy = y + dy[i]; if (!a[xx][yy] || v[xx][yy] || xx < 1 || yy < 1 || xx > n || yy > m) continue; dfs(xx, yy); } v[x][y] = 0; --cnt; } int main(){ cin >> n >> m; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> a[i][j]; cin >> fx >> fy >> sx >> sy; dfs(fx, fy); if (!ans) cout << -1; return 0; } ``` + [P1157](https://www.luogu.com.cn/problem/P1157) （橙） dfs 做法： ```cpp #include <bits/stdc++.h> using namespace std; int n, r, a[50]; void dfs(int x, int y) { if (x == r + 1) { for (int i = 1; i <= r; ++i) cout << setw(3) << a[i]; cout << endl; return; } for (int k = y; k <= n; ++k) a[x] = k, dfs(x + 1, k + 1); } int main() { cin >> n >> r; dfs(1, 1); return 0; } ``` ## 6 - 6 ~ 7 - 1 玛卡巴卡了，，，，期末考试咕掉了（ ## 7 - 3 ~ 7 - 4 详见： + [初赛知识点整理](https://www.luogu.com.cn/blog/chensi26/chu-sai-zhi-shi-dian-zheng-li) + [图论学习笔记](https://www.luogu.com.cn/blog/chensi26/tu-lun-xue-xi-bi-ji) + [%你赛 1](https://www.luogu.com.cn/blog/chensi26/post-202272) + [%你赛 2](https://www.luogu.com.cn/blog/chensi26/post-202273-202274-mu-ni-sai) ## 7 - 5 + [P5960](https://www.luogu.com.cn/problem/P5960) （绿）建图（反着建），跑 SPFA，如果有负环就是无解，蒟蒻跑的是最短路，就输出最小解。 ```cpp #include <bits/stdc++.h> using namespace std; #define inl inline struct edge { int x, y, w, nxt; } e[100010]; int he[100010], dis[100010], cnt[100010], inq[100010], n, m, tot; inl void add(int u, int v, int d) { e[++tot] = (edge) {u, v, d, he[u]}; he[u] = tot; } queue < int > q; inl int spfa(int s) { for (int i = 1; i <= n; ++i) dis[i] = 1e9; memset(cnt, 0, sizeof cnt); memset(inq, 0, sizeof inq); //tot = 0; dis[s] = 0; for (int i = 1; i <= n; ++i) q.push(i), inq[i] = 1, ++cnt[i]; while (!q.empty()) { int tmp = q.front(); q.pop(); inq[tmp] = 0; for (int i = he[tmp]; ~i; i = e[i].nxt) { int to = e[i].y; if (dis[to] > dis[tmp] + e[i].w) { dis[to] = dis[tmp] + e[i].w; if (!inq[to]) { inq[to] = 1; q.push(to); ++cnt[to]; if (cnt[to] >= n + 1) return 0; } } } } return 1; } int main() { int x, y, z; memset(he, -1, sizeof he); scanf ("%d%d", &n, &m); for (int i = 1; i <= m; ++i) { cin >> x >> y >> z; add(y, x, z); //if (z >= 0) add(y, x, z); } if (spfa(0)) for (int i = 1; i <= n; ++i) printf("%d%c", dis[i], i < n ? ' ' : '\n'); else puts("NO"); return 0; } ``` （因为刚才几交不上去怀疑敏感词汇所以打了空格） + [P3378](https://www.luogu.com.cn/problem/P3378) （橙）板子题，直接搞。 ```cpp #include <bits/stdc++.h> using namespace std; priority_queue < int, vector < int > , greater < int > > a; int opt, x; int main() { int t; cin >>t; while (t--) { cin >> opt; if (opt == 1) cin >> x, a.push(x); else if (opt == 2) cout << a.top() << endl; else a.pop(); } return 0; } ``` + [P1593](https://www.luogu.com.cn/problem/P1593) （蓝）数学题（？ + [P4147](https://www.luogu.com.cn/problem/P4147) （蓝）垂线法。 ~~用的是 P1950 的代码改的~~ 然后取一下最大，乘一下 $j - k - 1$，$ans$ 取最大值就好了。 ```cpp #include <bits/stdc++.h> using namespace std; int n, a[1010][1010], m; long long ans, t, s[1010]; char c; int main() { cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> c; if (c == 'F') ++a[i][j], ++s[j]; else s[j] = 0; } for (int j = 1; j <= m; ++j) { t = s[j]; for (int k = j; k >= 1; --k) { if (!s[k]) break; t = min(t, s[k]); ans = max(ans, t * (j - k + 1)); } } } // cout << ans << endl; cout << ans * 3ll; return 0; } ``` + [P1775](https://www.luogu.com.cn/problem/P1775) （黄） dp。 ```cpp for (int l = 2; l <= n; ++l) for (int i = 1; i <= n - l + 1; ++i) { int j = i + l - 1; for (int k = i; k < j; ++k) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]); } ``` 枚举左右端点，枚举中间的 $k$，，，，（怎么说呢~~我看题解学的~~） $l$ 表示枚举的区间长度，$i$ 表示左端点，$j$ 表示右端点，$k$ 表示区间的值。 $l$ 从 $2$ 开始，因为最少是左右两个合并；$i \le n- l + 1$，是因为右边要留一个区间给右端点；$j = i + l - 1$ 是右端点；然后就没有然后了。 ```cpp #include <bits/stdc++.h> using namespace std; int dp[310][310], a[310], n, s[310]; int main() { memset(dp, 0x3f, sizeof dp); cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; s[i] = s[i - 1] + a[i]; dp[i][i] = 0; } for (int l = 2; l <= n; ++l) for (int i = 1; i <= n - l + 1; ++i) { int j = i + l - 1; for (int k = i; k < j; ++k) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]); } cout << dp[1][n]; return 0; } ``` ## 7 - 6 咕咕咕 ## 7 - 7 + [P1584](https://www.luogu.com.cn/problem/P1564) （黄）有点贪心吧。。。 ~~看题解的~~ 首先只有两种。于是可以想想： + 砍，于是比上一个多 $1$。 + 不砍，于是和上一个一样。于是有了前提：连续的一段一样且小于 $m$。如果连续的一段不一样呢？不用担心，总会有的，因为枚举的终点会相等，$-1$ 之后就会是上一个。所以，初始化 $dp$ 时，记得第 $0$ 个要弄成 $0$。 ```cpp #include <bits/stdc++.h> using namespace std; int n, m, a[2600], sum[2600], dp[2600]; int main() { memset(dp + 1, 0x3f, sizeof(dp)); scanf ("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); if (a[i] == 1) sum[i] = sum[i - 1] + 1; else sum[i] = sum[i - 1] - 1; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= i; ++j) if (abs(sum[i] - sum[j - 1]) == i - j + 1 || abs(sum[i] - sum[j - 1]) <= m) dp[i] = min(dp[i], dp[j - 1] + 1); } printf("%d", dp[n]); return 0; } ``` ## 7 - 30 呜呜呜咕咕咕了好多天八月应该会准时更了 /kk ------ ## 8 - 16 咕了这么久，终于更了…… + [P2010](https://www.luogu.com.cn/problem/P2010) （橙）本来打算暴力模拟，后来想了几分钟，发现枚举后面的月份和日期就好了。 ```cpp #include <bits/stdc++.h> using namespace std; const int nf[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int n, m, ans; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= 12; ++i) for (int j = 1; j <= nf[i]; ++j) { int _x = ((j % 10) * 1000 + (j / 10) * 100 + (i % 10) * 10 + (i / 10)) * 10000 + i * 100 + j; if (_x >= n && _x <= m) ++ans; } printf("%d", ans); return 0; } ``` ## 9 - 21 咕咕咕，Orange 终于来更新啦！qwq（whk 太多了，这还是在机房更的 + [P2301](https://www.luogu.com.cn/problem/P2301) （黄）起先还想不出来……太弱了 /kk 有考虑过 dp，但是就是想不出来 /kk 然后看了题解，发现他的 $f(i,j)$ 是定义为到第 $i$ 个木棍时已经选了 $j$ 组木棍的最小值。（太妙了然后因为同一根不能选两次，所以就是选和不选： $$f(i,j)=\min(f(i-2,j-1)+\texttt{相邻两个的差的平方},f(i-1,j))$$ ```cpp #include <bits/stdc++.h> using namespace std; int a[2010], b[2010], f[2010][510], n, m, ans = 0x3ffff; int main() { memset(f, 0x3f, sizeof f); scanf("%d%d", &m, &n); for (int i = 1; i <= m; ++i) scanf("%d", &a[i]); sort(a + 1, a + m + 1); for (int i = 2; i <= m; ++i) b[i] = (a[i] - a[i - 1]) * (a[i] - a[i - 1]); for (int i = 0; i <= m; ++i) f[i][0] = 0; for (int i = 2; i <= m; ++i) for (int j = 1; j <= n; ++j) f[i][j] = min(f[i - 1][j], f[i - 2][j - 1] + b[i])/*, cout << f[i][j] << " "*/; for (int i = 2; i <= m; ++i) ans = min(ans, f[i][n])/*, cout << f[i][n] << " "*/; printf("%d", ans); return 0; } ``` ## 9 - 22 + [CF1398C](https://www.luogu.com.cn/blog/365825/solution-cf1398c) （黄） ---- 咕咕咕了几天呢。 ----- ## 9 - 28 + [P2420](https://www.luogu.com.cn/problem/P2420) （黄）全靠刷水题过日子。黄色的题都快要不会了（悲就是异或和，没了。 ```cpp #include <bits/stdc++.h> using namespace std; struct node { int ne, to, va; } e[300010]; int n, q, cnt, he[200010], di[200010]; bool v[200010]; void add(int u, int v, int d) { e[++cnt].to = v; e[cnt].ne = he[u]; e[cnt].va = d; he[u] = cnt; } void dfs(int i, int d) { di[i] = d; v[i] = 1; for (int k = he[i]; k; k = e[k].ne) if (!v[e[k].to]) dfs(e[k].to, d ^ e[k].va); } int main() { scanf("%d", &n); int u, v, d; for (int i = 1; i < n; ++i) { scanf("%d%d%d", &u, &v, &d); add(u, v, d), add(v, u, d); } dfs(1, 0); scanf("%d", &q); while (q--) scanf("%d%d", &u, &v), printf("%d\n", di[u] ^ di[v]); return 0; } ``` ## 9 - 30 + [P1512](https://www.luogu.com.cn/problem/P1512) （绿）博弈论。 ~~话说怎么只有两个测试点~~ ```cpp #include <bits/stdc++.h> using namespace std; int a, b, c; int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%d%d", &a, &b, &c); if ((b == 1 && c == 30) || (b == 9 && c == 30) || !((b + c) & 1)) puts("YES"); else puts("NO"); } return 0; } ``` ## 10 - 1 ~~GD 终于出分了~~ + [P2602](https://www.luogu.com.cn/problem/P2602) （蓝）数位 dp 模板题。 ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long ll a, b, _10[25], f[25], ca[25], cb[25], num[25], len, _2, l, r; ll f__k__f(ll x, ll cnt[]) { memset(num, 0, sizeof num); memset(cnt, 0, sizeof cnt); len = 0; while (x) num[++len] = x % 10, x /= 10; for (int i = len; i; --i) { _2 = 0; for (int j = 0; j <= 9; ++j) cnt[j] += f[i - 1] * num[i]; for (int j = 0; j < num[i]; ++j) cnt[j] += _10[i - 1]; for (int j = i - 1; j; --j) _2 = _2 * 10 + num[j]; cnt[num[i]] += _2 + 1; cnt[0] -= _10[i - 1]; } } int main() { scanf("%lld%lld", &l, &r); _10[0] = 1; for (int i = 1; i <= 20; ++i) f[i] = f[i - 1] * 10 + _10[i - 1], _10[i] = 10 * _10[i - 1]; f__k__f(r, ca), f__k__f(l - 1, cb); // for (int i = 0; i <= 9; ++i) printf("%lld ", cnt[1][i]); for (int i = 0; i <= 9; ++i) printf("%lld ", ca[i] - cb[i]); return 0; } ``` --------------------------------- 又咕咕咕了几天~ --------------------------------------------------- ## 10 - 5 + [P6146](https://www.luogu.com.cn/problem/P6146) （绿）有点偏于数学题。（？）先将所有线段按左端点升序排序。设 $f_i$ 表示前 $i$ 条线段的所有子集的复杂度之和。设该线段左边有 $x$ 个并。当不选这一条线段的时候，复杂度为 $f_{i-1}$。选的时候，考虑每一条线段是否有贡献。 1. 该线段不与左边的任何一个并相交。则会贡献新的复杂度 $2^x$。可以用快速幂解决。 1. 相交了。那就是 $0$ 啦！(？所以递推式子为 $f_i = f_{i-1}+f_{i-1}+2^x$。 $x$ 怎么求？简单的前缀和，右端点比他小的就是了。 sto myx orz 以增加 rp。模拟赛 rp++！ ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long int n; ll s[200010], f[100010]; const ll p = 1e9 + 7; struct node { int l, r; } a[100010]; bool myxAKIOI(node _x, node _y) { return _x.l < _y.l; } ll FP(ll _a, ll _x) { ll res = 1; for (; _x; _a = _a * _a % p, _x >>= 1) if (_x & 1) res = res * _a % p; return res; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%lld %lld", &a[i], &a[i].r), ++s[a[i].r]; for (int i = 1; i <= n << 1; ++i) s[i] += s[i - 1]; sort(a + 1, a + n + 1, myxAKIOI); /* sto myx orz */ for (int i = 1; i <= n; ++i) f[i] = (2ll * f[i - 1] + FP(2ll, s[a[i].l - 1])) % p; printf("%lld", f[n]); return 0; } ``` --------------- 咕咕咕了好多天呢。 ## 10 - 11 + [P2205](https://www.luogu.com.cn/problem/P2205) （蓝）感觉没有蓝（吧）。简单扫描线 ```cpp #include <bits/stdc++.h> using namespace std; struct node { int l, v; bool operator < (const node &x) const { return l < x.l; } } a[200010]; int n, m, t, ans, cnt; int main() { scanf("%d %d", &n, &m); char c; for (int i = 1, _len; i <= n; ++i) { cin >> _len >> c; if (c == 'R') a[++cnt] = (node) {t, 1}, a[++cnt] = (node) {t += _len, -1}; else a[++cnt] = (node) {t, -1}, a[++cnt] = (node) {t -= _len, 1}; } sort(a + 1, a + cnt + 1); t = a[1].v; for (int i = 2; i <= cnt; t += a[i++].v) if (t >= m) ans += a[i].l - a[i - 1].l; printf("%d", ans); return 0; } ``` + [P2070](https://www.luogu.com.cn/problem/P2070) （绿）上一道题双倍经验。把 $m$ 改成 $2$。 -------------------- 咕咕咕咕咕咕咕咕 ------------------ ## 10 - 19 + [P1908](https://www.luogu.com.cn/problem/P1908)（黄）排序，树状数组解决顺序问题 ```cpp #include <bits/stdc++.h> using namespace std; int tr[500010], n, r[500010]; long long ans; struct node { int x, id; bool operator < (const node& T) const { return x == T.x ? id < T.id : x < T.x; } } a[500010]; void add(int x, int y) { for (; x <= n; x += x & -x) tr[x] += y; } int sum(int x) { int res = 0; for (; x; x -= x & -x) res += tr[x]; return res; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i].x), a[i].id = i; sort(a + 1, a + n + 1); for (int i = 1; i <= n; ++i) r[a[i].id] = i; for (int i = 1; i <= n; ++i) add(r[i], 1), ans += i - sum(r[i])/*, puts("qwq")*/; printf("%lld", ans); return 0; } ``` ----------------------------------------------------- 又咕咕咕了好久了捏。 CSP 就这样炸了 /kel /kel /kel ---------------------------------- ## 11 - 4 + [P3434](https://www.luogu.com.cn/problem/P3434) （蓝）简单模拟（虽然一开始还是不理解？）能掉就往下掉，~~不能掉就算了~~ ```cpp #include <bits/stdc++.h> using namespace std; int n, m, tot, a[300010], b[300010], c[300010]; int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", a + i); for (int i = 1; i <= m; ++i) scanf("%d", b + i); c[1] = a[1], tot = n; for (int i = 2; i <= n; ++i) c[i] = min(c[i - 1], a[i]); for (int i = 1; i <= m; ++i) { while (c[tot] < b[i] && tot) --tot; --tot; if (!tot) return puts("0"), 0; } printf("%d", tot + 1); return 0; } ``` ------ ## 11 - 30 咕咕咕，好久没有更新了捏 whk 太多了 /ll /ll + [UVA1619](https://www.luogu.com.cn/problem/UVA1619) （蓝）看兄弟学校的已经毕业的学长写的悬线法写的。就是悬线法（妈呀，学校键盘好难打）救命啊，交了 $6$ 发才过 /kk /kk 原因是用来临时统计的 $x$ 没开 `ll`。不开 `ll` 见祖宗！！！！ ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long ll ans, ansl, ansr, s[100010], n, a[100010], l[100010], r[100010]; int main() { int t = 0; while (scanf("%lld", &n) != EOF) { ans = 0, ansl = ansr = 1; for (int i = 1; i <= n; ++i) scanf("%ld", a + i), l[i] = r[i] = i, s[i] = s[i - 1] + a[i]; for (int i = 1; i <= n; ++i) while (l[i] > 1 && a[i] <= a[l[i] - 1]) l[i] = l[l[i] - 1]; for (int i = n; i; --i) while (r[i] < n && a[i] <= a[r[i] + 1]) r[i] = r[r[i] + 1]; for (int i = 1; i <= n; ++i) { ll x = a[i] * (s[r[i]] - s[l[i] - 1]); if (x > ans || (x == ans && (r[i] - l[i] + 1 < ansr - ansl + 1))) ansl = l[i], ansr = r[i], ans = x; } if (t ++) puts(""); printf("%lld\n%lld %lld\n", ans, ansl, ansr); } return 0; } ``` ## 12 - 21 + [P1809](https://www.luogu.com.cn/problem/P1809) （绿） ~~看了一下题解~~ 然后知道了问啥前年那一道 CSP-J 的选择题过河问题我会错了。这**是有两个方法的啊…… ```cpp #include <bits/stdc++.h> using namespace std; int n, a[100010]; long long ans; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", a + i); sort(a + 1, a + n + 1); while (n > 3) { ans += min(a[1] * 2 + a[n] + a[n - 1], a[1] + a[2] * 2 + a[n]); n -= 2; } if (n == 2) ans += a[2]; if (n == 3) ans += a[1] + a[2] + a[3]; printf("%lld", ans); return 0; } ``` ## 12 - 24 平安夜！ + [P8650](https://www.luogu.com.cn/problem/P8650) （绿） [P3719](https://www.luogu.com.cn/problem/P3719) （绿）双倍经验！递归！学到了学到了。 P8560 代码： ```cpp #include <bits/stdc++.h> using namespace std; int _(int x) { char c; while (scanf("%c", &c) == 1) { if (c == 'x') ++x; if (c == '(') x += _(0); if (c == ')') return x; if (c == '|') return max(x, _(0)); } return x; } int main() { printf("%d", _(0)); } ``` ## 12 - 25 圣诞快乐！！/qq + [CF20C](https://www.luogu.com.cn/problem/CF20C) （黄） ** dij 初值赋太小 + 优先队列结构体用了 `int`，见祖宗了。 + [P1938](https://www.luogu.com.cn/problem/P1738) （绿）看了题解。太妙了，学到了。他把每一个分离出来插进去，这样就可以避免重复了。 ```cpp #include <bits/stdc++.h> using namespace std; int n; string s; set < string > S; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { cin >> s; string c = ""; for (int j = 0; j < s.length(); ++j) { if (s[j] == '/') S.insert(c); c += s[j]; } S.insert(c); printf("%d\n", S.size() - 1); } return 0; } ``` # 2023 Happy new year!! ~~gu gu gu~~ ## 1 - 9 + [CF567E](https://www.luogu.com.cn/problem/CF567E) （蓝）求一条边是否必定会被经过，要看路径条数和长度。然后就是乱搞了，他不一定被经过的话，那么它的路径条数乘起来就不一致，可以用这个来判断。然后知道他不一定被经过了，就要使经过这条路的最短路径比当前的最短路少 $1$，即答案为经过这条路的最短路径减去最短路长度再 $-1$。如果答案 $\le 1$，就输出 $\texttt{NO}$ 了。既然要知道最短路径，而且要知道到每一个点的最短路径，而且还要知道他接起来的最短路径，所以我们就可以知道，我们要求从起点开始的单源最短路，和从终点开始的单源最短路，用 $\text{dijstra}$ 即可。（病句然后就是有一点点关于传参的问题，这一点蒟蒻也不太清楚，是看题解这样做的，下面代码中 `cnt` 是直接搞进去的，没有传地址，但他是有改变数组里的值，~~我也很奇怪啊~~，哪位大佬能告诉这个蒟蒻 QwQ upd on 2023.2.3 感谢 @jzcrq：数组作形参时本来就是传址的。如果想要传值的话可以把数组丢到一个 `struct` 里传。 ```cpp #include <bits/stdc++.h> using namespace std; #define N 100010 #define ll long long struct node1 { int u, v, d; } e[N << 1]; int he1[N], to1[N << 1], co1[N << 1], ne1[N << 1], tot1; int he2[N], to2[N << 1], co2[N << 1], ne2[N << 1], tot2; int n, m, s, t; bool vis[N]; ll dis[3][N], cnt[3][3][N]; const ll Mod0 = 1e9 + 7; const ll Mod1 = 998244353; struct node2 { int p; ll di; bool operator < (const node2 &T) const { return di > T.di; } }; void add_edge(int u, int v, int d, int i) { e[i].u = u; e[i].v = v; e[i].d = d; } void add1(int u, int v, int d) { to1[++tot1] = v; co1[tot1] = d; ne1[tot1] = he1[u]; he1[u] = tot1; } void add2(int u, int v, int d) { to2[++tot2] = v; co2[tot2] = d; ne2[tot2] = he2[u]; he2[u] = tot2; } void dij(int S, int *he, int *ne, int *co, int *to_, ll *di, ll cnt[2][N]) { for (int i = 1; i <= n; ++i) di[i] = 1e15; memset(vis, 0, sizeof vis); di[S] = 0, cnt[0][S] = cnt[1][S] = 1; priority_queue < node2 > q; q.push((node2) {S, 0}); while (!q.empty()) { node2 tmp = q.top(); q.pop(); ll x = tmp.p; if (vis[x]) continue; vis[x] = 1; for (int i = he[x]; i; i = ne[i]) { ll y = to_[i]; if (di[y] > di[x] + co[i]) { di[y] = di[x] + co[i]; cnt[0][y] = cnt[0][x]; cnt[1][y] = cnt[1][x]; q.push((node2) {(int)y, di[y]}); } else if (di[y] == di[x] + co[i]) { cnt[0][y] = (cnt[0][y] + cnt[0][x]) % Mod0; cnt[1][y] = (cnt[1][y] + cnt[1][x]) % Mod1; } } } } int main() { scanf("%d %d %d %d", &n, &m, &s, &t); for (int i = 1, u, v, d; i <= m; ++i) { scanf("%d %d %d", &u, &v, &d); add_edge(u, v, d, i); add1(u, v, d); add2(v, u, d); } dij(s, he1, ne1, co1, to1, dis[0], cnt[0]); dij(t, he2, ne2, co2, to2, dis[1], cnt[1]); for (int i = 1; i <= m; ++i) { int x = e[i].u, y = e[i].v, d = e[i].d; if (dis[0][x] + d + dis[1][y] == dis[0][t] && (cnt[0][0][x] * cnt[1][0][y]) % Mod0 == cnt[0][0][t] && (cnt[0][1][x] * cnt[1][1][y]) % Mod1 == cnt[0][1][t]) puts("YES"); else { ll _ = dis[0][t] - dis[0][x] - dis[1][y]; if(_ <= 1) puts("NO"); else printf("CAN %lld\n", d - _ + 1); } } } ``` + [P2886](https://www.luogu.com.cn/problem/P2886) （蓝）假设我有一个矩阵 $A$。$A$ 为 $n \times n$ 的矩阵。然后这个矩阵是一个邻接矩阵，存了一张无向图。我把矩阵乘一遍自己，得到了 $A^2$。可以自己手摸一下，得到了 $A^2_{u,v}$ 表示点 $u$ 到 $v$ 经过两条边的路径条数。我再乱乘几次，得到了 $A^x$。那么 $A^x$ 的意义就是各个点到各个点经过 $x$ 条边的路径条数。现在我要改一下乘法的规则。设 $B$ 为答案矩阵。设 $B_{u,v} = \min \limits_{i = 1}^{n}\{A_{u,i} + A_{i, v}\}$。得到的是啥捏？想一想意义，是点到点的路径去最小值，所以上述的 $B$ 矩阵意义为各个点到各个点经过两条边的最短路。 ~~啊哈哈~~，那我再多运算几次，设 $A^y$ 为运算 $y$ 次的结果矩阵。那么，$A^y$ 的意义就是各个点到各个点经过 $y$ 条边的最短路啦！于是这个题就能做了。矩阵快速幂。但是数据范围到 $1000$ 呢。怎么办，好像会超时诶，，，重新读题。连通图，最多 $100$ 条边，那不就最多 $101$ 个点吗？！！离散化！ ~~因为调代码，还写了个 `print()` 函数~~ ```cpp #include <bits/stdc++.h> using namespace std; int n, m, st, en, tot; map < int, int > lsh; struct MapG { int g[210][210]; MapG operator * (const MapG &T) const { MapG C; memset(C.g, 0x3f, sizeof C.g); for (int k = 1; k <= tot; ++k) for (int i = 1; i <= tot; ++i) for (int j = 1; j <= tot; ++j) C.g[i][j] = min(C.g[i][j], g[i][k] + T.g[k][j]); return C; } void print(MapG T) { for (int i = 1; i <= tot; ++i, puts("")) for (int j = 1; j <= tot; ++j) printf("%d ", T.g[i][j]); puts("qwq"); } } G, A; int main() { memset(G.g, 0x3f, sizeof G.g); scanf("%d %d %d %d", &n, &m, &st, &en); for (int i = 1, u, v, d, _u, _v; i <= m; ++i) { scanf("%d %d %d", &d, &u, &v); _u = lsh[u] ? lsh[u] : (lsh[u] = ++tot); _v = lsh[v] ? lsh[v] : (lsh[v] = ++tot); G.g[_u][_v] = G.g[_v][_u] = d; } A = G, --n; for (; n; G = G * G, n >>= 1/*, G.print(G)*/) if (n & 1) A = A * G; printf("%d", A.g[lsh[st]][lsh[en]]); return 0; } ``` ## 1 - 10 + [P3366](https://www.luogu.com.cn/problem/P3366) （橙）最小生成树模板题。橙题还 WA，我退役吧。。 ```cpp #include <bits/stdc++.h> using namespace std; #define N 5010 #define M 200010 struct node { int u, v, d; bool operator < (const node &T) const { return d < T.d; } } e[M]; int n, m, ans, cnt, tot, fa[N]; int find(int x) { return fa[x] == x ? fa[x] : (fa[x] = find(fa[x])); } void kruskal(void) { for (int i = 1; i <= tot; ++i) { int x = find(e[i].u), y = find(e[i].v); if (x == y) continue; fa[x] = y; ans += e[i].d; if (++cnt == n - 1) break; } } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) fa[i] = i; while (m--) { int u, v, d; scanf("%d %d %d", &u, &v, &d); e[++tot] = (node) {u, v, d}; } sort(e + 1, e + tot + 1); kruskal(); if (cnt == n - 1) printf("%d", ans); else puts("orz"); return 0; } ``` + [CF449B](https://www.luogu.com.cn/problem/CF449B) （蓝） ~~可爱的小水蓝~~ 简单题，700 AC 祭。但是细节要注意一下，统计最短路能遍历到几次而不是最短路条数。（这个写调了好久 /kk） ```cpp #include <bits/stdc++.h> using namespace std; #define inl inline struct edge{ int to, di, ne; } e[800010]; struct xxxx { int s, y; bool operator < (const xxxx &T) const { return s == T.s ? y < T.y : s < T.s; } } ki[100010]; int he[100010], tot, cnt[100010], n, m, dis[100010], k, ans; bool vis[100010];; inl void add(int u, int v, int d) { ++tot; e[tot].di = d; e[tot].to = v; e[tot].ne = he[u]; he[u] = tot; } struct node{ int d, p; bool operator < (const node &x) const { return x.d < d; } }; priority_queue < node > q; inl void dij(int s) { dis[s] = 0; cnt[1] = 1; q.push((node){0, s}); while (!q.empty()) { node tmp = q.top(); q.pop(); int x = tmp.p; if (vis[x]) continue; vis[x] = 1; for (int i = he[x]; i; i = e[i].ne) { int y = e[i].to; if (dis[y] > dis[x] + e[i].di) { dis[y] = dis[x] + e[i].di; cnt[y] = 1; if (!vis[y]) q.push((node) {dis[y], y}); } else if (dis[y] == dis[x] + e[i].di) ++cnt[y]; } } } int main() { scanf("%d %d %d", &n, &m, &k); for (int i = 1; i <= n; ++i) dis[i] = 0x3fffffff; for (int i = 1, u, v, d; i <= m; ++i) scanf("%d %d %d", &u, &v, &d), add(u, v, d), add(v, u, d); for (int i = 1; i <= k; ++i) scanf("%d %d", &ki[i].s, &ki[i].y), add(1, ki[i].s, ki[i].y), add(ki[i].s, 1, ki[i].y); dij(1); for (int i = 1; i <= k; ++i) { if (dis[ki[i].s] < ki[i].y) ++ans; if (dis[ki[i].s] == ki[i].y && cnt[ki[i].s] > 1) ++ans, --cnt[ki[i].s]; } printf("%d", ans); return 0; } ``` ## 1 - 11 + [P4180](https://www.luogu.com.cn/problem/P4180) （紫）首先你要明白，次小生成树一定是找一条比最小生成树大的边换掉。然后问题就变成了找哪一条原来没选的边换掉最短边，而且最小。然后，怎么求树上两点路径之间的最小值和严格次小值边权？首先我们要知道 LCA。然后我们要知道这个最小值和次小值。接着我们要倍增，利用 LCA 求出这个最小值和次小值。最后，换边，求最小值。没了。 ```cpp #include <bits/stdc++.h> using namespace std; #define N 100010 #define M 300010 #define pb push_back #define ll long long const int INF = 2e9 + 10; const ll LL_INF = 1e15; struct node { int u, v, d; bool operator < (const node &T) const { return d < T.d; } } e[M]; struct Tree { int id, v; }; int n, m, cnt, tot, fa[N], f[N][30], dep[N], mx1[N][30], mx2[N][30]; ll sum, ans; bool vis[M]; vector < Tree > tree[N]; int Find(int x) { return fa[x] == x ? fa[x] : (fa[x] = Find(fa[x])); } void Kruskal(void) { sort(e + 1, e + tot + 1); int _cnt = 0; for (int i = 1; i <= tot; ++i) { int _x = Find(e[i].u), _y = Find(e[i].v); if (_x == _y) continue; fa[_x] = _y; vis[i] = 1; sum += e[i].d; tree[e[i].u].pb((Tree) {e[i].v, e[i].d}); tree[e[i].v].pb((Tree) {e[i].u, e[i].d}); if (++_cnt == n - 1) break; } } void dfs_to_lca(int x, int fa) { dep[x] = dep[fa] + 1; f[x][0] = fa; for (int i = 1; i <= 18; ++i) f[x][i] = f[f[x][i - 1]][i - 1]; for (Tree i : tree[x]) { int to = i.id; if (to != fa) mx1[to][0] = i.v, dfs_to_lca(to, x); } } void pre_for_val(void) { for (int i = 1; i <= 18; ++i) for (int j = 1; j <= n; ++j) { int _s[4] = {mx1[j][i - 1], mx1[f[j][i - 1]][i - 1], mx2[j][i - 1], mx2[f[j][i - 1]][i - 1]}; sort(_s, _s + 4); mx1[j][i] = _s[3]; int k; for (k = 2; ~k; --k) if (_s[k] != _s[k + 1]) break; mx2[j][i] = k < 0 ? -INF : _s[k]; } } int get_max(int x, int lca, int val) { ll res = 0; for (int i = 18; ~i; --i) { if (dep[f[x][i]] < dep[lca]) continue; if (mx1[x][i] == val) res = max(res, (ll)mx2[x][i]); else res = max(res, (ll)mx1[x][i]); x = f[x][i]; } return res; } int LCA(int a, int b) { if (dep[a] < dep[b]) swap (a, b); for (int i = 18; i >= 0; --i) if (dep[f[a][i]] >= dep[b]) a = f[a][i]; if (a == b) return a; for (int k = 18; k >= 0; --k) if (f[a][k] != f[b][k]) a = f[a][k], b = f[b][k]; return f[a][0]; } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) fa[i] = i; for (int i = 1, u, v, d; i <= m; ++i) { scanf("%d %d %d", &u, &v, &d); if (u != v) e[++tot] = (node) {u, v, d}; } Kruskal(); dfs_to_lca(1, 0); pre_for_val(); ans = LL_INF; for (int i = 1; i <= m; i++) { if (vis[i]) continue; int x = e[i].u, y = e[i].v, z = e[i].d, lca = LCA(x, y); int lmx = get_max(x, lca, z), rmx = get_max(y, lca, z); if (max(lmx, rmx) != z) ans = min(ans, sum + z - max(lmx, rmx)); } printf("%lld", ans); return 0; } /* 4 6 1 2 1 1 3 3 1 4 10 1 2 5 2 2 2 1 1 4 */ ``` 注意自环，因为自环不是树。 + [[ABC284E] Count Simple Paths](https://www.luogu.com.cn/problem/AT_abc284_e) （灰） [题解](https://www.luogu.com.cn/blog/365825/solution-at-abc284-e) + [P1550](https://www.luogu.com.cn/problem/P1550) （绿）搞一个超级源点，然后搞搞就行了。 ## 1 - 12 + [SP30669](https://www.luogu.com.cn/problem/SP30669) （黄） sb 题。 - [P1144](https://www.luogu.com.cn/problem/P1144) （黄） sb 题。 ## 1 - 13 + [P2024](https://www.luogu.com.cn/problem/P2024) （蓝）带权并查集。在找父亲的时候合并一下边权（点指向根的边权），然后判断一下。 ```cpp #include <bits/stdc++.h> using namespace std; int f[100010], va[100010], n, m, ans; #define AnsCon { ++ans; continue; } int find(int x) { if (x == f[x]) return x; int f_x = f[x]; f[x] = find(f[x]); va[x] = (va[x] + va[f_x]) % 3; return f[x]; } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) f[i] = i; int opt, x, y; for (int i = 1; i <= m; ++i) { scanf("%d %d %d", &opt, &x, &y); if (x > n || y > n || opt == 2 && x == y) AnsCon; int fx = find(x), fy = find(y); if (opt == 1) { if (fx == fy && va[x] != va[y]) AnsCon; if (fx != fy) f[fx] = fy, va[fx] = (3 - va[x] + va[y]) % 3; } if (opt == 2) { if (fx == fy && ((va[x] - va[y] + 3) % 3 != 1)) AnsCon; if (fx != fy) f[fx] = fy, va[fx] = (3 - va[x] + va[y] + 1) % 3; } } printf("%d", ans); return 0; } ``` + [P2294](https://www.luogu.com.cn/problem/P2294) （蓝）带权并查集 /oh 可以理解为前缀和。如果不是同一个根就合并，如果是同一个根但是矛盾了就是 `false`。然后注意方向，因为方向这个屑调了一个小时。。 ```cpp #include <bits/stdc++.h> using namespace std; int n, m, f[1010], val[1010]; int find(int x) { if (f[x] == x) return x; int _ = find(f[x]); val[x] += val[f[x]]; return f[x] = _; } int main() { int TTT; scanf("%d", &TTT); while (TTT--) { scanf("%d %d", &n, &m); memset(val, 0, sizeof val); for (int i = 0; i <= n; ++i) f[i] = i; bool fl = 0; int u, v, d; while (m--) { scanf("%d %d %d", &u, &v, &d); --u; if (find(u) != find(v)) val[f[v]] = val[u] - val[v] - d, f[f[v]] = f[u]; else if (val[u] - val[v] != d) fl = 1; } puts(fl ? "false" : "true"); } } ``` ## 1 - 14 + [P1196](https://www.luogu.com.cn/problem/P1196) （绿）带权并查集，要注意方向。 ```cpp #include <bits/stdc++.h> using namespace std; #define N 30010 int f[N], a[N], c[N], m; int find(int x) { if (f[x] == x) return x; int _ = find(f[x]); a[x] += a[f[x]]; return f[x] = _; } int main() { scanf("%d", &m); for (int i = 1; i <= 30000; ++i) f[i] = i, c[i] = 1; char opt; int i, j; while (m--) { cin >> opt >> i >> j; int fi = find(i), fj = find(j); if (opt == 'M') { a[fi] += c[fj], f[fi] = fj; c[fj] += c[fi], c[fi] = 0; } else { if (fi != fj) puts("-1"); else printf("%d\n", abs(a[i] - a[j]) - 1); } } return 0; } ``` ## 1 - 16 + [P3388 割点](https://www.luogu.com.cn/problem/P3388) （绿） ## 1 - 18 + [P2169](https://www.luogu.com.cn/problem/P2169) （蓝）缩点 + 最短路（这个屑用 topo 算最短路）要注意边权问题，这个东西调了好久 /lb 感谢 @[xxasmcd](https://www.luogu.com.cn/user/237437) 指出错误。 ```cpp #include <bits/stdc++.h> using namespace std; #define N 200010 #define M 1000010 struct Edge { int u, v, ne, d; } e1[M << 1], e2[M << 1]; int n, m, dfn[N], low[N], _tim, p[N], sd[N], tot1, he1[N], tot2, he2[N], inq[N], dis[N]; bool vis[N]; stack < int > st; void add1(int u, int v, int d) { e1[++tot1] = (Edge) {u, v, he1[u], d}; he1[u] = tot1; } void add2(int u, int v, int d) { e2[++tot2] = (Edge) {u, v, he2[u], d}; he2[u] = tot2; ++inq[v]; } void tarjan(int x) { dfn[x] = low[x] = ++_tim; st.push(x); vis[x] = 1; for (int i = he1[x]; i; i = e1[i].ne) { int y = e1[i].v; if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]); else if (vis[y]) low[x] = min(low[x], dfn[y]); } if (dfn[x] == low[x]) for (int y = st.top(); y; y = st.top()) { st.pop(); sd[y] = x; vis[y] = 0; if (x == y) break; } } int topo(void) { queue < int > Q; for (int i = 1; i <= n; ++i) { if (sd[i] == i && !inq[i]) Q.push(i); dis[i] = INT_MAX / 2; } dis[sd[1]] = 0; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = he2[x]; i; i = e2[i].ne) { int y = e2[i].v; dis[y] = min(dis[y], dis[x] + e2[i].d); if (--inq[y] == 0) Q.push(y); } } return dis[sd[n]]; } int main() { scanf("%d %d", &n, &m); for (int i = 1, u, v; i <= m; ++i) scanf("%d %d %d", &u, &v, p + i), add1(u, v, p[i]); for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i); for (int i = 1; i <= m; ++i) { int x = sd[e1[i].u], y = sd[e1[i].v]; if (x != y) add2(x, y, e1[i].d); } printf("%d", topo()); } ``` ## 1 - 29 + [P3469](https://www.luogu.com.cn/problem/P3469) （蓝）以下是 1 - 18 写的笔记，，，首先对图进行 dfs，得到生成树。然后对每个节点 $i$ 的儿子 $C_i$ 进行讨论。假设要删掉的节点是 $i$。 1. $C_i$ 无法追溯到 $i$ 的父亲及以上。那么将 $i$ 断开之后，以 $C_i$ 为根的子树就和其他的节点不连通了，答案 $ans_i$ 要加上 $C_i$ 的子树大小 $size_{C_i}$ 与其他子树的大小 $n-size_{C_i}$。即 $ans_i \Leftarrow ans_i + size_{C_i} \times (n-size_{C_i})$。同时，令 $sum$ 为该类儿子的总数，$sum \Leftarrow sum + size_{C_i}$。 2. $C_i$ 能够追溯到 $i$ 之上。删去 $i$ 之后，$C_i$ 还是与 $i$ 的子树外的连通块连通。则这个连通分量的大小是 $n - sum - 1$。则 $ans_i \Leftarrow ans_i + (n - sum - 1) \times sum$。然后就是计算 $i$ 点对答案的贡献了。$ans_i \Leftarrow ans_i + 2 \times (n - 1 )$。怀疑这东西重复算了？没关系，这东西本来就要重复算，因为题目是要求“有序数对”。然后我就写挂了，，，然后看了题解改了亿下，，， upd on 2024.9.18 之前写的有亿点乱，重新整理了一下。分类讨论。考虑对第 $i$ 个节进行讨论。设第 $i$ 个节点的儿子为 $C_i$。记以 $i$ 为根的子树大小为 $siz_i$。 + $i$ 不是割点。有环，把 $i$ 删边后只有 $i$ 独立在外面，所以这时候答案是 $2\times (n-1)$。 + $i$ 是割点。对每个儿子进行讨论。 + $C_i$ 是割点。将 $i$ 删边后子树 $C_i$ 独立出去，这一部分的贡献是子树 $C_i$ 的大小 $siz_{C_i}$乘上其他部分的大小 $n-siz_{C_i}$。即 $ans_i \leftarrow ans_i + siz_{C_i} \times (n-siz_{C_i})$。（乘法原理）同时，令 $sum$ 为该类儿子的子树大小总和，$sum \leftarrow sum + size_{C_i}$。 + $C_i$ 不是割点。将 $i$ 删边后 $C_i$ 还和其他的部分连着，没有独立出去。然后现在这个图被分成了几块：点 $i$，连通块 $n - sum - 1$，还有独立出去的儿子的子树们。别忘了还有一部分答案没有算。连通块 $n-sum-1$ 与节点 $i$ 的贡献还没算。$ans_i \leftarrow ans_i + (n - sum - 1) \times (sum+1) +n-1$。 $sum+1$ 为除了连通块之外的点，$n-1$ 为 $i$ 独立出去的贡献。 ```cpp #include <bits/stdc++.h> using namespace std; #define N 100010 #define ll long long struct node { int to, ne; } e[1000010]; int n, m, low[N], dfn[N], _tim, tot, he[N]; ll ans[N], siz[N]; bool cut[N]; void add(int u, int v) { e[++tot] = (node) {v, he[u]}; he[u] = tot; } void Tarjan(int x, int fa) { dfn[x] = low[x] = ++_tim; siz[x] = 1; int sons = 0, sum = 0; for (int i = he[x]; i; i = e[i].ne) { int y = e[i].to; if (!dfn[y]) { Tarjan(y, x); low[x] = min(low[x], low[y]); siz[x] += siz[y]; if (low[y] >= dfn[x]) { ++sons; ans[x] += (ll)siz[y] * (ll)(n - siz[y]) * 1ll; sum += siz[y]; if (x != 1 || sons > 1) cut[x] = 1; } } else low[x] = min(low[x], dfn[y]); } if (cut[x]) ans[x] += (ll)(n - sum - 1) * (sum + 1ll) * 1ll + n - 1; else ans[x] = 2ll * (n - 1); } int main() { scanf("%d %d", &n, &m); for (int i = 1, u, v; i <= m; ++i) { scanf("%d %d", &u, &v); add(u, v), add(v, u); } Tarjan(1, 1); for (int i = 1; i <= n; ++i) printf("%lld\n", ans[i]); return 0; } ``` ## 2 - 12 + [CF edu 题](https://codeforces.com/edu/course/2/lesson/7/2/practice/contest/289391/problem/H) 最大生成树，然后算一下就行了。 ## 2 - 15 + [SP18155](https://www.luogu.com.cn/problem/SP18155) （蓝）数学题。考虑每一个 $a_i$ 对于答案的贡献，总共被加了 $2 \times i − n − 1$ 次然后就没了。 ```cpp #include <bits/stdc++.h> using namespace std; long long n, ans, a[10010]; int main() { int t; scanf("%d", &t); while (t--){ scanf("%lld",&n); ans = 0; for (int i = 1; i <= n; ++i) scanf("%lld", a + i); for (int i = 1; i <= n; ++i) ans += a[i] * (i * 2 - 1 - n); printf("%lld\n", ans); } return 0; } ``` ## 3 - 25 好久没更了。 2 月就写了 7 题，废了。 3 月到目前为止只写了 7 题，其中 2 题为学长的比赛。吃枣药丸。 + [CF432D](https://www.luogu.com.cn/problem/CF432D) （蓝） kmp。累加满足的。乱搞。 ```cpp #include <bits/stdc++.h> using namespace std; int len, d[100010], nxt[100010], ans; bool v[100010]; string s; void kmp(void) { int j = 0; for (int i = 2; i <= len; ++i) { while (j && s[i] != s[j + 1]) j = nxt[j]; if (s[i] == s[j + 1]) ++j; nxt[i] = j; } } void dfs(int x) { if (x == 0) return; ++ans; v[x] = 1; dfs(nxt[x]); } int main() { cin >> s; len = s.length(); s = " " + s; kmp(); for (int i = 1; i <= len; ++i) d[i] = 1; for (int i = len; i; --i) d[nxt[i]] += d[i]; dfs(len); printf("%d\n", ans); for (int i = 1; i <= len; ++i) if (v[i]) printf("%d %d\n", i, d[i]); return 0-0; } ``` 0-0 可爱。 ## 4 - 26 好久没写题了。无语。的，whk。 + [P2015](https://www.luogu.com.cn/problem/P2015) （绿）树形 dp。然后就是说这题反着来，算 dp 值的时候是加上去， ```cpp #include <bits/stdc++.h> using namespace std; #define N 30010 struct node { int to, ne, val; } e[N << 1]; int n, q, he[N], tot, siz[N], f[110][N]; void add(int u, int v, int d) { e[++tot] = (node) { v, he[u], d }; he[u] = tot; } void dfs1(int x, int fa) { siz[x] = 1; for (int i = he[x]; i; i = e[i].ne) { int y = e[i].to; if (y == fa) continue; dfs1(y, x); siz[x] += siz[y]; } } void dfs2(int x, int fa) { for (int i = he[x]; i; i = e[i].ne) { int y = e[i].to; if (y == fa) continue; dfs2(y, x); for (int j = min(siz[x], q); j; --j) for (int k = 0; k <= min(j - 1, siz[y]); ++k) f[x][j] = max(f[x][j], f[x][j - k - 1] + f[y][k] + e[i].val); } } int main() { scanf("%d %d", &n, &q); for (int i = 1, u, v, d; i < n; ++i) { scanf("%d %d %d", &u, &v, &d); add(u, v, d), add(v, u, d); } dfs1(1, 0); dfs2(1, 0); printf("%d", f[1][q]); return 0; } ``` 然后就是看了下题解发现其实可以并成一个 dfs。 ## 5 - 13 + [P1064](https://www.luogu.com.cn/problem/P1064) （绿）首先，显然 dp。其次，有什么一组一组的，组里还有什么主件附件的。分组背包。然后就，搞一个 vector，把处理好的东西塞进去，作为一大组一大组，首先组内背包，然后组别背包，然后就是记不太清当时怎么想的，虽然就是一个多小时前。 ```cpp #include<bits/stdc++.h> using namespace std; struct node { int v, w; } zu[70]; struct node2 { int vi, pi, qi, num; } a[70]; int dp1[32010], dp2[32010], n, m, cnt; vector < node > b[70]; bool cmp(node2 _1, node2 _2) { return (_1.num < _2.num || (_1.num == _2.num && _1.qi < _2.qi)); } int main() { scanf("%d %d", &n, &m); n /= 10; for (int i = 1; i <= m; ++i) { scanf("%d %d %d", &a[i].vi, &a[i].pi, &a[i].qi); if (!a[i].qi) a[i].num = ++cnt; else a[i].num = a[a[i].qi].num; a[i].pi *= a[i].vi; } sort(a + 1, a + m + 1, cmp); for(int i = 1; i <= m; ++i) if (!a[i].qi) zu[a[i].num].v = a[i].vi / 10, zu[a[i].num].w = a[i].pi; else { node x; x.v = a[i].vi / 10, x.w = a[i].pi; b[a[i].num].push_back(x); } for (int i = 1; i <= cnt; ++i) { for (int j = zu[i].v; j <= n; ++j) dp2[j] = dp1[j - zu[i].v] + zu[i].w; for (int k = 0; k < b[i].size(); ++k) { node _ = b[i][k]; for (int j = n; j >= _.v + zu[i].v; --j) dp2[j] = max(dp2[j], dp2[j - _.v] + _.w); } for (int j = zu[i].v; j <= n; ++j) dp1[j] = max(dp1[j], dp2[j]); } printf("%d", dp1[n]); return 0; } ``` 思路清奇，一看题解整个人都蒙了。 ## 7 - 16 终于更了呜呜呜已经一个半月没写题了吃枣药丸 + [P5543](https://www.luogu.com.cn/problem/P5543) （绿） `D` 染反色点，`S` 染同色点，有矛盾就直接 $0$ 然后结束。比较简单，但是这个菜鸡弄了快两个钟头自己搞出来的，震惊 ```cpp #include <bits/stdc++.h> using namespace std; #define M 100010 struct node { int to_, dis, nex; } e[M << 1]; int n, m, vis[M], he[M], ans, col[M], cnt; void add(int u, int v, int d) { e[++cnt] = (node) { v, d, he[u] }; he[u] = cnt; } void dfs(int x, int fa) { // printf("%d %d////\n", x, col[x]); vis[x] = 1; for (int i = he[x]; i; i = e[i].nex) { int y = e[i].to_, cos = e[i].dis; if (y == fa) continue; if (!vis[y]) { col[y] = cos ? 3 - col[x] : col[x]; dfs(y, x); } else { if ((cos && col[x] == col[y]) || ((!cos) && col[x] != col[y])|| (col[x] != 1 && col[x] != 2)) { puts("0"); exit(0); } } } } int main() { scanf("%d %d", &n, &m); char str; for (int i = 1, u, v; i <= m; ++i) { cin >> str >> u >> v; if (str == 'S') add(u, v, 0), add(v, u, 0); if (str == 'D') add(u, v, 1), add(v, u, 1); } for (int i = 1; i <= n; ++i) { if (!vis[i]) { col[i] = 2; dfs(i, 0); ++ans; } } printf("1"); for (int i = 1; i <= ans; ++i) printf("0"); return 0; } /* 4 3 S 1 2 S 3 4 D 2 3 */ ``` ## 7 - 24 + [CF862B](https://www.luogu.com.cn/problem/CF862B) （绿）二分染色，算出两个点集的数量，相乘，减去 $n - 1$. ```cpp #include <bits/stdc++.h> using namespace std; #define N 100010 #define ll long long int n, vis[N], tot, he[N]; ll cnt1, cnt2; struct node { int to_, nxt; } e[N << 1]; void add(int u, int v) { e[++tot] = (node) {v, he[u]}; he[u] = tot; } void dfs(int x, int fa) { // printf("%d %d %d\n", x, fa, vis[x]); for (int i = he[x]; i; i = e[i].nxt) { int y = e[i].to_; if (y == fa) continue; vis[y] = 1 - vis[x]; dfs(y, x); } } int main() { scanf("%d", &n); for (int i = 1, u, v; i < n; ++i) { scanf("%d %d", &u, &v); add(u, v), add(v, u); } memset(vis, -1, sizeof vis); vis[1] = 1; dfs(1, 0); for (int i = 1; i <= n; ++i) if (vis[i] == 1) ++cnt1; else ++cnt2; printf("%lld", cnt1 * cnt2 - n + 1); return 0; } /* 5 1 2 2 3 3 4 4 5 */ ``` + [P1063](https://www.luogu.com.cn/problem/P1063) （绿）和合并石子有点像，然后要注意加上的 $m \times r \times n$（就因为这个调了 1h+ ```cpp #include <bits/stdc++.h> using namespace std; int n, ans, a[210], f[210][210], b[210]; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[n + i] = a[i]; for (int i = 1; i < n * 2; ++i) b[i] = a[i + 1]; for (int p = 1; p < n; ++p) { for (int i = 1; i < 2 * n - p; ++i) { int j = i + p; for (int k = i; k < j; ++k) { f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + a[i] * a[k + 1] * a[j + 1]); // printf("%d %d %d %d//", i, j, k, f[i][j]); } } // puts(""); } for (int i = 1; i <= n; ++i) ans = max(ans, f[i][i + n - 1])/*, printf("%d ", f[i][i + n - 1])*/; // puts(""); printf("%d", ans); return 0; } /* 4 2 3 5 10 */ ``` + [ATabc288f](https://www.luogu.com.cn/problem/AT_abc288_f) （蓝）很厉害的方程。~~无话可说，去看题解吧~~ ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long ll n, ans, sum; const ll p = 998244353; string s; int main() { cin >> n >> s; sum = 1; for (ll i = 1; i <= n; ++i) { ans = (ans * 10 % p + sum * (s[i - 1] - '0') % p) % p; sum = (sum + ans) % p; } cout << ans % p; return 0 - 0; } ``` + [P2057](https://www.luogu.com.cn/problem/P2657) （蓝）数位 dp 拜谢 Leonid 拜谢 ldh081122 ```cpp #include <bits/stdc++.h> using namespace std; int l, r, f[15][15][3][3], a[15]; int dfs(int pos, int x, bool zero, bool lim) { if (!pos) return 1; if (~f[pos][x][zero][lim]) return f[pos][x][zero][lim]; int up = lim ? a[pos] : 9, res = 0; for (int i = 0; i <= up; ++i) if (zero || abs(i - x) >= 2) res += dfs(pos - 1, i, zero & (i == 0), lim & (i == up)); if (!lim) f[pos][x][zero][lim] = res; return res; } int run(int num) { int tot = 0, res = 0; memset(a, -1, sizeof a); memset(f, -1, sizeof f); while (num) a[++tot] = num % 10, num /= 10; return dfs(tot, 0, 1, 1); } int main() { scanf("%d %d", &l, &r); printf("%d", run(r) - run(l - 1)); return 0; } ``` ## 8 - 16 + [P1439](https://www.luogu.com.cn/problem/P1439) （绿）其实就是最长上升子序列 ```cpp #include <bits/stdc++.h> using namespace std; #define N 100010 int n, a[N], b[N], f[N], ans; map < int, int > mp; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", a + i), mp[a[i]] = i; for (int i = 1; i <= n; ++i) scanf("%d", b + i); memset(f, 0x3f, sizeof f); f[0] = 0; for (int i = 1; i <= n; ++i) { if (mp[b[i]] > f[ans]) f[++ans] = mp[b[i]]; else f[lower_bound(f + 1, f + ans + 1, mp[b[i]]) - f] = min(mp[b[i]], f[lower_bound(f + 1, f + ans + 1, mp[b[i]]) - f]); } printf("%d", ans); return 0; } ``` 咕咕咕咕