[数据结构与算法]2022寒假题集总结

Labeling Balls（poj3687）

一道拓扑排序的题，一开始我是正向建边的，但是一直wa，后来想明白了正向建边无法满足题目字典序最小的要求，比如有一个条件是 4比2小 ，正向建边的做法得出的结果是1 4 2 3 但是 1 3 4 2 的字典序显然更小且符合条件。这道题虽然比较简单，但是这种小细节如果思考不全面还是比较容易犯错误的。

//由于题目的数据量比较小，所以算法的复杂度为O(n*n)
//可以将入度为0的点搞一个集合(set)，优化到O(nlogn)
#include <iostream>
#include <vector>
#define fre(f) freopen(f ".in", "r", stdin), freopen(f ".out", "w", stdout)
const int N = 205;
using namespace std;

int ind[N], ans[N];
bool vis[N];
vector<int> v[N];

void init()
{
    for (int i = 0; i < N; i++)
    {
        ind[i] = 0;
        v[i].clear();
        vis[i] = 0;
    }
}

int main()
{
    // fre("A");
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        bool sign = 1;
        int n, m, x, y;
        cin >> n >> m;
        init();
        while (m--)
        {
            cin >> x >> y;
            ind[x]++;
            v[y].push_back(x);
        }
        for (int i = n; i >= 1; i--)
        {
            bool flag = 0;
            for (int j = n; j >= 1; j--)
            {
                if (vis[j]) continue;
                if (ind[j] == 0)
                {
                    vis[j] = 1;
                    ans[j] = i;
                    for (int k = 0; k < v[j].size(); k++)
                        ind[v[j][k]]--;
                    flag = 1;
                    break;
                }
            }
            if (!flag)
            {
                sign = 0;
                break;
            }
        }
        if (sign)
            for (int i = 1; i <= n; i++)
                cout << ans[i] << ' ';
        else
            cout << "-1";
        cout << endl;
    }
    return 0;
}

Popular Cows

一道图论较难的题 对我而言是这样
用到了tarjan算法和缩点的思想。
tarjan算法套模板就行。建图选中链式前向星或者邻接表都可以，邻接表更好写。
正向建图，如果这幅图中存在出度为0的点且唯一（这里的点是指缩点后的集合），那么这个点就是答案。这题的缩点比较简单，将同一个强连通分量里的点放到一个集合里就行。

#include <algorithm>
#include <cstring>
#include <iostream>
#include <stack>
#include <vector>
#define mem(a, v) memset(a, v, sizeof(a))
const int N = 1e4 + 5;
using namespace std;

int out[N], dfn[N], low[N], cnt[N], f[N], t = 1, ans = 0;
bool vis[N];
stack<int> s;
vector<int> g[N];

void tarjan(int x)
{
    dfn[x] = low[x] = ++t;
    s.push(x);
    vis[x] = 1;
    for (int i = 0; i < g[x].size(); i++)
    {
        int y = g[x][i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        if (vis[y])
            low[x] = min(low[x], low[y]);
    }
    if (low[x] == dfn[x])
    {
        ans++;
        int top;
        while (s.size())
        {
            top = s.top();
            s.pop();
            vis[top] = 0;
            f[top] = ans; //将同一个强连通分量里的点放入一个集合中，达到缩点的效果（将一个强连通分量看成一个点）
            cnt[ans]++;   //记录这个集合的点数
            if (top == x) break;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m, x, y;
    mem(out, 0), mem(dfn, 0), mem(low, 0), mem(cnt, 0), mem(vis, 0);
    cin >> n >> m;
    while (m--)
    {
        cin >> x >> y;
        g[x].push_back(y);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= n; i++) //计算出度
    {
        for (int j = 0; j < g[i].size(); j++)
        {
            int k = g[i][j];
            if (f[i] == f[k]) continue; //因为将强连通分量看作一个点，因此在同一个强连通分量里的两个点就略过
            out[f[i]]++;
        }
    }
    int sum = 0, outs = 0;
    for (int i = 1; i <= ans; i++)
    {
        if (out[i] == 0)
        {
            outs++;
            sum = cnt[i];
        }
    }
    if (outs == 1) //如果有多个出度为0的点，就不符合条件
        cout << sum;
    else
        cout << 0;
    return 0;
}

POJ-1011 Sticks 一道经典的剪枝题

2021年的寒假就做到了这道题，那时刚接触算法，看了一天的题解才把这题过了。如今再次遇到这题依然被卡了 就记录一下吧

#include <algorithm>
#include <cstring>
#include <iostream>
#define mem(a, v) memset(a, v, sizeof(a))
#define fre(f) freopen(f ".in", "r", stdin)
using namespace std;

int stick[100], n, ans;
bool vis[100];
bool cmp(int a, int b) { return a > b; }

bool dfs(int s, int rest, int cnt)
{
    if (rest == 0) rest = ans, s = 0;
    if (cnt == n) return 1;
    int last = -1;
    for (int i = s; i < n; i++)
    {
        if (stick[i] == last || vis[i] || stick[i] > rest) continue;
        vis[i] = 1;
        if (dfs(i + 1, rest - stick[i], cnt + 1)) return 1;
        vis[i] = 0;
        //剪枝：跳过长度一样的棍子
        last = stick[i];
        //剪枝：如果在构建新的棍子时第一根棍子就用不上了 那么后面这根棍子也是用不上的 所以直接退出
        if (rest == ans) return 0;
    }
    return 0;
}

int main()
{
    while (cin >> n && n)
    {
        mem(vis, 0);
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> stick[i];
            sum += stick[i];
        }
        sort(stick, stick + n, cmp);
        for (int i = stick[n - 1]; i <= sum; i++)
        {
            //剪枝：初始棍子的长度必须是长度和的因子
            if (sum % i) continue;
            ans = i;
            if (dfs(0, ans, 0))
            {
                cout << ans << endl;
                break;
            }
        }
    }
    return 0;
}

POJ - 3630 Phone List trie树（字典树的应用）

第一次做字典树的题，用动态内存分配的方法总是超时，改用静态数组就过了。因此下次做这类题还是用静态数组比较好。
主要判断两个：1、前缀不能包含某个字符串 2、自己不能被某个字符串的前缀包含

#include <cstdio>
#include <cstring>
#define N 100005
#define mem(a, v) memset(a, v, sizeof(a))
#define fre(f) freopen(f ".in", "r", stdin)
using namespace std;

int next[N][10], sz;
bool sign[N]; //记录是否为字符串的最后一个位置

int main()
{
    int T, n;
    char s[20];
    scanf("%d", &T);
    while (T--)
    {
        mem(next, 0);
        mem(sign, 0);
        sz = 0;
        scanf("%d", &n);
        bool flag = 1;
        while (n--)
        {
            scanf("%s", s);
            if (flag)
            {
                int len = strlen(s), it = 0;
                bool tmp = 0;
                for (int i = 0; i < len; i++)
                {
                    char c = s[i];
                    if (next[it][c - '0'] == 0) //不能被某个字符的前缀包含
                    {
                        tmp = 1;
                        next[it][c - '0'] = ++sz;
                    }
                    it = next[it][c - '0'];
                    if (sign[it]) flag = 0; //前缀不能包含某个字符串
                }
                sign[it] = 1;
                if (!tmp) flag = 0;
            }
        }
        if (flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

Arrays Sum （CodeForces - 1408B）

这题理解错了题意，其实是一道很简单的题。每次都可以出现k个不同的数字，而不是一共出现k个不同的数字，那么每次都可以消除k-1个数字。然后再特判一下就好了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e2 + 5;
int vis[maxn], a[maxn];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        memset(vis, 0, sizeof(vis));
        int n, k, sum = 0;
        cin >> n >> k;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            if (vis[a[i]] == 0) //统计出现了几个不同的数字
            {
                vis[a[i]] = 1;
                sum++;
            }
        }
        if (k == 1 && sum > 1)
            cout << -1 << endl;
        else if (sum <= k)
            cout << 1 << endl;
        else
        {
            if ((sum - k) % (k - 1) == 0)
                cout << 1 + (sum - k) / (k - 1) << endl;
            else
                cout << 2 + (sum - k) / (k - 1) << endl;
        }
    }
    return 0;
}

H - Welfare State （CodeForces - 1198B）

思路都在代码注释里了，个人感觉是一道比较好的题

//无需每次都更新 只要将所有的改变进行合并即可
#include <algorithm>
#include <cstring>
#include <iostream>
#define maxn 200005
#define mem(a) memset(a, 0, sizeof(a))
#define fre(f) freopen(f ".in", "r", stdin)
using namespace std;

//last[i]表示最后一次改变balance是在第i次救济之前
//maxp[i]表示第i次救济之后中最大的一次救济
int last[maxn], payoff[maxn], maxp[maxn], balance[maxn];

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, q, cnt = 1; //cnt记录出现了几次payoff
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> balance[i], last[i] = cnt;
    cin >> q;
    while (q--)
    {
        int op, x, y;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y;
            last[x] = cnt;
            balance[x] = y;
        }
        else
        {
            cin >> x;
            payoff[cnt] = x;
            cnt++;
        }
    }
    maxp[cnt - 1] = payoff[cnt - 1];
    for (int i = cnt - 2; i >= 0; i--)
        maxp[i] = max(payoff[i], maxp[i + 1]);
    for (int i = 1; i <= n; i++)
    {
        balance[i] = max(balance[i], maxp[last[i]]);
        cout << balance[i] << ' ';
    }
    return 0;
}

C - Boolean Expressions （POJ - 2106）

一道比较麻烦的题，需要考虑较多的情况，对思维也有一点要求。对括号的处理比较关键

#include <iostream>
#define maxn 10005
using namespace std;

int pos;
char str[maxn];
bool cal()
{
    ++pos;
    if (str[pos] != '(') //计算普通值
    {
        if (str[pos] == '!')
            return !cal();
        else if (str[pos] == 'V')
            return 1;
        else if (str[pos] == 'F')
            return 0;
    }
    else //计算括号
    {
        bool res;
        ++pos;
        if (str[pos] == '!')
            res = !cal();
        else if (str[pos] == 'V')
            res = 1;
        else if (str[pos] == 'F')
            res = 0;
        else if (str[pos] == '(')
        {
            --pos;
            res = cal();
        }
        ++pos;
        while (true)
        {
            if (str[pos] == '|')
                res |= cal();
            else if (str[pos] == '&')
                res &= cal();
            else if (str[pos] == ')')
                return res;
            ++pos;
        }
    }
}
int main()
{
    str[0] = '(';
    char temp[maxn];
    int t = 1;
    while (cin.getline(temp, maxn))
    {
        //去掉空格
        int index = 0;
        for (int i = 0; temp[i] != '\0'; i++)
            if (temp[i] != ' ') str[++index] = temp[i];
        str[++index] = ')';

        pos = -1;
        for (int i = 0;; i++)
        {
            if (str[i] == 0)
            {
                str[i] = ')';
                str[i + 1] = 0;
                break;
            }
        }
        cout << "Expression " << t++ << ": ";
        if (cal())
            cout << "V\n";
        else
            cout << "F\n";
    }
    return 0;
}

Connected Components? （CodeForces - 920E）

题目的意思是给一个完全图去掉一些边，然后找出有几个连通集，以及每个连通集的大小。自己的做法给卡了挺久，看了别人的代码后想明白了（换了一种做法）。
思路在代码注释中体现了。

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#define maxn 200005
using namespace std;

vector<int> g[maxn], ans;
set<int> s1, s2;
//先找与v连接的那一圈点，然后再找与那一圈点连接的点，不断重复
void bfs(int v)
{
    queue<int> q;
    int cnt = 1;
    s1.erase(v);
    q.push(v);

    while (q.size())
    {
        v = q.front();
        q.pop();
        for (int a : g[v]) //所有与v点没有连边的点都去除，暂时存放到s2中，s1中剩下的点肯定与v相连
        {
            if (s1.count(a))
            {
                s2.insert(a);
                s1.erase(a);
            }
        }
        cnt += s1.size();
        for (int a : s1) //然后将与v相连的点全部入队
            q.push(a);
        // s1清空并将s2中的点转移回s1中
        s1 = s2;
        s2.clear();
        //进行下一轮循环，查找剩下的点是否还有相连的
    }
    ans.push_back(cnt);
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m;
    int x, y;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        s1.insert(i);
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
    {
        if (s1.count(i))
            bfs(i);
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (int a : ans)
        cout << a << " ";
    return 0;
}