1. 词频统计

题目描述

有 m 个单词，n 篇文章，每篇文章包含若干单词。统计每个单词在多少篇文章中出现过，以及在所有文章中总出现次数。

思路:模拟,遍历

使用数组 cnt 来统计每个单词在多少篇文章中出现过，使用数组 tot 来统计每个单词在所有文章中总出现次数,布尔数组 st 来记录单词在当前文章中是否出现过。

最后输出每个单词的cnt和tot即可。

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int cnt[N],tot[N]; //分别用来存储单词在多少篇文章中出现过以及在所有文章中总出现次数
bool st[N]; // 用来判断单词在当前文章中是否出现过


int main(){

    int n,m;
    cin >> n >> m;

    while(n--){
        int k;
        cin >> k;

        memset(st,false,sizeof(st)); //注意每篇文章都要重置st数组,因为我们需要统计每篇文章中单词是否出现过
        while(k--){
            int x;
            cin >> x;
            tot[x]++;
            if(!st[x])
            {
                cnt[x]++;
                st[x] = true;
            }
        }
    }

    for(int i = 1;i<=m;++i){
        cout << cnt[i] << ' ' << tot[i] << endl;
    }

    return 0;
}

2. 相似度计算

题目描述

两个集合的 Jaccard 相似度定义为：

给出两篇文章,每篇文章由若干单词组成,单词之间用空格分隔,单词由大小写字母组成,大小写字母视为同一个字母,隔行输出:

  • 两篇文章中出现单词的交集和并集的大小.

思路:哈希+容斥原理

使用unordered_set来保存两篇文章的单词数量以及a∪b的单词数量,最后根据容斥原理计算出 a∩b的大小以及 a∪b的大小即可.

这里可以使用容斥原理求解 a∩b的大小:

  • 时间复杂度：O(n*logn)
  • 空间复杂度：O(n)

代码

#include <iostream>
#include <cstring>
#include <unordered_set>
#include <algorithm>

using namespace std;

unordered_set<string> a,b,c; //用来保存两篇文章的单词数量以及a∪b的单词数量

int main(){

    int n,m;
    cin >> n >> m;

    string s;
    for(int i = 0;i<n;++i)
    {
        cin >> s;
        for(auto &c:s)c = tolower(c);
        a.insert(s);
        c.insert(s);
    }

    for(int i = 0;i<m;++i)
    {
        cin >> s;
        for(auto &c:s)c = tolower(c);
        b.insert(s);
        c.insert(s);
    }

    cout << a.size() + b.size() - c.size() << '\n'; // 容斥原理,a∩b = a + b - a∪b 
    cout << c.size() << '\n';

    return 0;
}

4.十滴水

题目描述

在一个一维网格水池中，初始有 m 个水坑，每个水坑的权值表示当前水滴数。每次向某个水坑滴入一滴水后，它的权值会加 1。当某个水坑的权值达到 5 时，该水坑会被删除，并且它左右相邻的水坑的权值都会加 1。请输出每次滴入水后，水池中剩余的水坑数。

思路:双向链表

每次处理时，只需要判断当前水坑左右两侧的两个水坑是否需要被删除即可；如果有新的水坑被删除，就继续检查它周围的相邻水坑，直到再也没有水坑需要删除为止。

[!tip]
注意双向链表中节点的删除的方法,r[L],表示L对应的左邻点,l[R],表示R对应的右邻点

在水坑爆炸的过程中，指针可以单向移动，也就是先处理左边，再处理右边，这样可以显著减少重复计算。

代码中先判断 R 再判断 L，再进行更新，从而实现 L 覆盖 R 的效果，保证遍历方向始终是单向的。

  • 时间复杂度：O(m+n)
  • 空间复杂度：O(m)

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

#define x first
#define y second

typedef pair<int,int> PII; //PII.x 表示坐标,PII.y表示权值
const int N = 3e5 + 10;

int l[N],r[N],w[N];
// l[i]记录i的左邻居
// r[i]记录i的右邻居
// w[i]记录i的权值
unordered_map<int,int>pos;

PII p[N];

int c,n,m;


int main(){
    scanf("%d%d%d",&c,&m,&n);
    for(int i = 1;i<=m;++i)scanf("%d%d",&p[i].x,&p[i].y);
    sort(p+1,p+m+1); //题目中的元素大小可能是随机的

    for(int i = 1;i<=m;++i){
        l[i] = i-1;r[i] = i + 1;
        w[i] = p[i].y;
        pos[p[i].x] = i;
    }

    int res = m;
    while(n--)
    {
        // 处理第一次水滴
        int x;
        scanf("%d",&x);
        int k = pos[x];
        w[k]++;

        while(w[k] >= 5)
        {
            res--;
            int nk = 0,L = l[k],R = r[k];
            r[L] = R,l[R] = L;//L-k-R,删除k
            if(R <= m && ++w[R] >= 5)nk = R;
            if(L && ++w[L] >= 5)nk = L;
            k = nk;
        }

        printf("%d\n",res);
    }
    return 0;
}