A U193219 混乱的小镇

题目大意:

E小镇是个混乱的地方，一开始每个人自成帮派（即每个人是自己的老大），有时候会发生团体与团体的混战，胜利一方的老大会成为两个帮派的所有人的老大，并将两个帮派合并。

负责治安的警官Eden会记录下每次混战中不同团体的两个人以及胜利者。但需要注意有时候两个人可能属于同一个帮会，此时属于帮会内战，老大是不会发生任何变化的。有时Eden还需要回答来自上司的检查，即询问某个人的老大是谁，Eden想请你写个程序帮帮他。

题解:

并查集模板，数据强度好像比洛谷官方的要大，之前写模板题的路径压缩在这会超时

代码:

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

int a[N];

int find(int x) {
    return x == a[x] ? a[x] : a[x] = find(a[x]);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        a[i] = i;
    }
    while (m--) {
        int o;
        scanf("%d", &o);
        if (o == 0) {
            int x, y;
            scanf("%d%d", &x, &y);
            int c = find(x);
            int d = find(y);
            a[d] = c;
        }
        if (o == 1) {
            int x;
            scanf("%d", &x);
            printf("%d\n", find(x));
        }
    }
    return 0;
}

B P1706 全排列问题

题目大意:

按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

题解:

DFS+回溯直接扫就行了，n的范围很小很小。

也可以用STL内置的全排列函数(std::next_permutation)。

关于std::next_permutation的介绍可以参考这里:

https://en.cppreference.com/w/cpp/algorithm/next_permutation

代码:

DFS+回溯:

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

vector<int> v;
int vis[20];

void dfs(int begin, int n) {
    if (begin == n) {
        for (int i = 0; i < n; i++) {
            printf("%5d", v[i]);
        }
        printf("\n");
        return;
    }
    int l = v.size();
    for (int i = 1; i <= n; i++) {
        int flag = 1;
        for(int j = 0; j < l; j++){
            if(v[j] == i){
                flag = 0;
            }
        }
        if(flag){
            v.push_back(i);
            dfs(begin + 1, n);
            v.pop_back();
        }
    }
    return;
}

int main() {
    int n;
    cin >> n;
    dfs(0, n);
    return 0;
}

STL：

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

vector<int> nums;

int main()
{
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        nums.push_back(i);
    }
    do {
        for(int i = 0; i < n; i++){
            printf("%5d", nums[i]);
        }
        printf("\n");
    } while(std::next_permutation(nums.begin(), nums.end()));
    return 0;
}

C P1102 A-B 数对

题目大意:

给出一串数以及一个数字 C，要求计算出所有 A−B=C 的数对的个数

题解:

先移一下，变成 A - C = B，然后排序之后二分上下界找B的个数就好了。

代码:

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

long long nums[200010];
int main(){
    int n,c;
    cin>>n>>c;
    for(int i = 0; i < n; i++){
        scanf("%lld", &nums[i]);
    }
    long long ans = 0;
    sort(nums, nums + n);
    for(int i = 0; i < n; i++){
        int k = nums[i] - c;
        ans += upper_bound(nums, nums + n, k) - lower_bound(nums, nums + n, k);
    }
    printf("%lld", ans);
}

D U193113 子串和

题目大意:

给一个长度为n的序列，问有多少子串的和为0？

题解:

先算了前缀和。

最开始算完之后双层for遍历，果断超时，毕竟n^2已经十个零了= =

然后转用map去记前缀和相同的个数，因为子串和为0等同于两个前缀和相等

$$b{c} = a{1} + a{2} + ... + a{c}$$

$$b{d} = a{1} + a{2} + ... + a{d}$$

$$b{c} - b{d} = a{d+1} + ... + a{c} = 0$$

$$b{c} - b{d} = 0$$ 等同于 $$b{c} = b{d}$$

然后还要算个排列组合，因为任意两个相同的前缀和都可以代表一段相加为0的子段。

代码:

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

long long a[N];
long long b[N];

long long C(int d, int n){
    long long u = 1;
    for(int i = n - d + 1; i <= n; i++){
        u *= i;
    }
    for(int i = 1; i <= d; i++){
        u /= i;
    }
    return u;
}

map<int, int> m;

int main() {
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
    }
    for(int i = 1; i <= n; i++){
        b[i] = b[i - 1] + a[i];
    }
    long long ans = 0;
    for(int i = 0; i <= n; i++){
        auto it = m.find(b[i]);
        int x = 0;
        if(it != m.end()){
            x = it->second;
            m.erase(it);
        }
        m.insert(make_pair(b[i], x + 1));
    }
    for(auto it = m.rbegin(); it != m.rend(); it++){
        if(it->second > 1){
            ans += C(2, it->second);
        }
    }
    printf("%lld", ans);
    return 0;
}

E U193234 矩形覆盖

题目大意:

给出二维平面上的n个边与坐标轴平行的矩形，求被它们覆盖过的地方总面积。

0<=x1,y1,x2,y2<=100000

题解:

还不会做，看标签好像是离散化，等会了再来填坑。

之前好像有遇见过类似的但是是求最后一次覆盖的是第几个矩形....应该不太一样。顺便一说好像Leetcode上喜欢出这种，没记错有好几道= =

F P1824 进击的奶牛

题意:

x轴上N个点中选择c个点，问每两个点的最小距离最大时候的值(= =反正就是最小情况的最大值)

题解:

易得具有单调性，考虑二分答案。

代码:

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

int nums[100010];
int m, l, r;

int main() {
    int n, c;
    cin>>n>>c;
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    sort(nums, nums + n);
    l = 0;
    r = nums[n - 1] - nums[0] + 10;
    for (int i = 0; i < 100; i++) {
        m = l + ((r - l) >> 1);
        int les = nums[0] + m, ct = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] >= les) {
                les = nums[i] + m;
                ct++;
            }
        }
        if (ct >= c) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    printf("%d", r);
}

G P1396 营救

题意:

一个无向图，要求求出s点到t点的路径中每一个线段的最大值最小的情况是多少。

题解：

emmmmm

开始想的是最短路径魔改，写了个dijk发现好像不是很好改，然后又写了个最小生成树，生成完之后再dfs从起点沿着树的路径到扫到终点就好了。

最开始偷懒用二维数组来标记数是否经过某个线段，然后果断MEL了，然后又改了用vector存才过的...

代码:

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

int n, m, s, t, u, v, total;

struct edge {
    int start, to;
    int val;

    bool operator<(edge b) {
        return val < b.val;
    }
} bian[20010];
int f[20010];
int x[20010];
long long ans = 0;
vector<int> vis[20010];

int find(int x) {
    return x == f[x] ? f[x] : f[x] = find(f[x]);
}

inline void kruskal() {
    for (int i = 1; i <= m; i++) {
        u = find(bian[i].start);
        v = find(bian[i].to);
        if (u == v) continue;
        vis[bian[i].start].push_back(bian[i].to);
        vis[bian[i].to].push_back(bian[i].start);
        f[u] = v;
        total++;
        if (total == n - 1) break;
    }
}

void dfs(int q, int mx, int from) {
    if (q == t) {
        ans = mx;
        return;
    }
    if (ans != 0) {
        return;
    }
    while (!vis[q].empty()) {
        int v = vis[q].back();
        if (v != from) {
            for (int j = 1; j <= m; j++) {
                if ((bian[j].start == q && bian[j].to == v) || (bian[j].to == q && bian[j].start == v)) {
                    dfs(v, max(mx, bian[j].val), q);
                    break;
                }
            }
        }
        vis[q].pop_back();

    }
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &bian[i].start, &bian[i].to, &bian[i].val);
    }
    sort(bian + 1, bian + m + 1);
    kruskal();
    dfs(s, -1, s);
    printf("%lld", ans);
}

H P1144 最短路计数

题目大意:

给出一个N个顶点M条边的无向无权图，顶点编号为1到N。问从顶点1开始，到其他每个点的最短路有几条。

题解:
其实写个dijk就好了，如果d[e.to] > d[v] + 1那么e.to的路径数就等于v的路径数，如果d[e.to] == d[v] + 1那么e.to的路径数就要加上v的路径数。(此时已确定要进行松弛操作)

代码:

#include<bits/stdc++.h>
#define MAXV 2000010
#define INF 0x3f3f3f3f
using namespace std;

struct edge{
    int to,cost;
};

int n;
vector<edge> G[MAXV];
int d[1000010];
int nums[1000010];
typedef pair<int, int> P;
const int mod = 100003;

void dijk(int s){
    priority_queue<P, vector<P>, greater<P> > que;
    memset(d, INF, sizeof(d));
    d[s] = 0;
    nums[s] = 1;
    que.push(P(0, s));
    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(d[v] < p.first) continue;
        for(int i = 0; i < G[v].size(); i++){
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                nums[e.to] = nums[v];
                que.push(P(d[e.to], e.to));
            } else if(d[e.to] == d[v] + e.cost){
                nums[e.to] += nums[v];
                nums[e.to] %= mod;
            }
        }
    }
}

int main(){
    int n,m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++){
        int u,v;
        scanf("%d%d", &u, &v);
        G[u].push_back({v,1});
        G[v].push_back({u,1});
    }
    dijk(1);
    for(int i = 1; i <= n; i++){
        printf("%d\n", nums[i]);
    }
    return 0;
}

后面还有两题暂时都不会做，摆烂