1.词频统计

简单题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>

using namespace std;

const int N=110;
int n,m;
int cnt[N];//记录每个单词出现的次数
int cn[N];//记录每个单词所出现的文章的个数
int flag[N]; 

int main()
{
	cin>>n>>m;
	int count1,num;
	
	for(int i=1;i<=n;i++)
	{
		cin>>count1;
		for(int j=1;j<=count1;j++)
		{
			cin>>num;
			if(!flag[num])
			{
				cn[num]++;
				flag[num]=1; 
			}
			cnt[num]++;
		}
		memset(flag,0,sizeof(flag));
	}
	
	for(int i=1;i<=m;i++)
	{
		cout<<cn[i]<<" "<<cnt[i]<<'\n';
	}
	
	return 0;
}

相似度计算

直接开set,没什么好说的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>

using namespace std;

const int N=1e4+10;
int cn,cnt;//cn记录交集的单词数,cnt记录并集的单词数
int n,m; 
string word1[N],word2[N];
set<string>bin,jiao,words1,words2;

int main()
{
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
	{
		cin>>word1[i];
		for(int j=0;j<word1[i].length();j++)
		{
			if(word1[i][j]>='A'&&word1[i][j]<='Z')
			{
				word1[i][j]=word1[i][j]-'A'+'a';
			}
		}
		bin.insert(word1[i]);
		words1.insert(word1[i]);
	}
	
	for(int i=1;i<=m;i++)
	{
		cin>>word2[i];
		for(int j=0;j<word2[i].length();j++)
		{
			if(word2[i][j]>='A'&&word2[i][j]<='Z')
			{
				word2[i][j]=word2[i][j]-'A'+'a';
			}
		}
		bin.insert(word2[i]);
		words2.insert(word2[i]);
	}
	
	for(set<string>::iterator it=words2.begin();it!=words2.end();it++)
	{
		if(words1.find(*it)!=words1.end())cn++;
	}
	
	cout<<cn<<'\n'<<bin.size();
	
	return 0;
}

3.化学方程式配平

根据题意写代码就行了，这么简单的题我当时居然没拿100分，有点气人

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<bit/stdc++.h>

using namespace std;

void gauss(double a[][50], int x, int y, int hang, int lie)
{
    if (x >= hang || y >= lie)
        return;
    bool flag = true; // 用于判断第一列是否为空
    int idx = 0;//用于标记找到的第一个元素不为0的行号
    for (int i = x; i < hang; i++)
    {
        if (a[i][y] != 0)
        {
            flag = false;
            idx = i;
            break;
        }
    }
    if (flag == true)
        gauss(a, x, y + 1, hang, lie);
    else {
        //idx不为0时，需要将这一行与第一行换位置
        if (idx != 0)
        {
            for (int i = 0; i < lie; i++)
                swap(a[idx][i], a[x][i]);
        }
        //对下面行中所有第一项不为0的行进行减操作
        for (int i = idx + 1; i < hang; i++)
        {
            for (int j = y+1; j < lie; j++)
                a[i][j] -= a[i][y] / a[x][y] * a[x][j];
            a[i][y] = 0;
        }
        gauss(a, x + 1, y + 1, hang, lie);
    }
}

void solve()
{
    double a[50][50], cnt, q, k = 0, N = 0, flag = 0;//二维数组a模拟矩阵
    string thing;//存储每一个方程式
    set <string> s;//存储出现过的元素，并对其去重
    map<string, int> b;//存储某个物质中某个元素所对应的序号，即在矩阵中的行数

    memset(a, 0, sizeof(a));

    cin >> cnt;

    for (int i = 0; i < cnt; i++)//创建矩阵
    {
        cin >> thing;
        q = 0;
        string temp = "";
        while (q < thing.length())
        {
            temp = "";
            while (q < thing.length() && isalpha(thing[q]))
            {
                temp.push_back(thing[q]);
                q++;
            }
            s.insert(temp);
            int x = 0;
            while (q < thing.length() && isdigit(thing[q]))
            {
                x = x * 10 + thing[q] - '0';
                q++;
            }


            if (!b.count(temp))//如果没出现过，则为其编号
            {
                b[temp] = k++;
            }
            a[b[temp]][i] = x;
        }
    }

    /*for (int i = 0; i < s.size(); i++)
    {
        for (int j = 0; j < cnt; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }*/

    //cout << '\n' << '\n';

    gauss(a, 0, 0, s.size(), cnt);//高斯消元

    /*for (int i = 0; i < s.size(); i++)
    {
        for (int j = 0; j < cnt; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }*/

    for (int i = 0; i < s.size(); i++)
    {
        flag = 0;
        for (int j = 0; j < cnt; j++)
        {
            if (a[i][j] != 0)
            {
                N++;
                flag = 1;
                break;
            }
        }
        if (flag == 0)
            break;
    }

    if (N < cnt)
        cout << "Y" << '\n';
    else
        cout << "N" << '\n';
}


int main()
{
    int n;
    cin >> n;
    while (n--)
        solve();
    return 0;
}

4.十滴水

关心水滴的坐标大小关系，并不关心其具体值是多少。所以，直接用set 存下所有的坐标，每次用 lowerbound 查找目标水滴，然后再将其左右两端进行更新。如果有多个待删水滴，则使用一个优先队列，按照下标排序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>

using namespace std;

//题目大体思路：用一个结构体来存储有水滴的格子的序号跟水滴数
//用set存储该结构体，之后每进行一次操作便将操作的结点在set中删除，并依次向左和向右执行操作
//在考虑哪些水滴会炸裂时，用优先队列存储水滴数大于等于5的点，方便每次都是最左边的点先裂开，且能够对所有的点进行处理，不会遗漏

struct node {
	int x, w;
	bool operator < (const node& a)const {
		return x < a.x;
	}
	bool operator == (const node& a)const {
		return x == a.x && w == a.w;
	}
};

int main()
{
	int c, m, n;
	cin >> c >> m >> n;

	set<node>s;

	for (int i = 1; i <= m; i++)
	{
		int x, w;
		cin >> x >> w;

		s.insert({ x,w });

	}

	for (int i = 1; i <= n; i++)
	{
		int p;
		cin >> p;

		auto it = s.lower_bound({ p,0 });//找到要裂开的点
		auto temp = *it;
		s.erase(it);
		temp.w++;
		s.insert(temp);

		set<int>ans;//用于存储要裂开的点

		if (temp.w >= 5)ans.insert(temp.x);

		while (!ans.empty())
		{
			auto it = s.lower_bound({*ans.begin(),0});
			ans.erase(ans.begin());
			if (it != s.begin())
			{
				auto it1 = it ;
				it1--;
				auto temp = *it1;
				s.erase(it1);
				temp.w++;
				s.insert(temp);
				if (temp.w >= 5)ans.insert(temp.x);
			}
			auto it2 = it;
			it2++;
			if (it2 != s.end())
			{
				auto temp = *it2;
				s.erase(it2);
				temp.w++;
				s.insert(temp);
				if (temp.w >= 5)ans.insert(temp.x);
			}
			s.erase(it);
		}
		cout << s.size() << endl;
	}
	return 0;
}