[数据结构与算法]广西师范大学计算机学院第九次周赛题解

小淞学前缀和

本题考查 $vector$ 的运用, 给出的数据范围 $n,m$ 均在 $1$~$100000$, 如果开二维数组就爆内存了, 然后 $n$ × $m$ 又小于 $100000$, 故我们可以考虑使用动态数组, 即 $vector$, 然后注意这里是会爆 $int$ 的, $100000$ × $100000$ = $10^{12}$, 因为数据量较大所以要用 $scanf$, 或者关闭同步

#include<bits/stdc++.h>

#define int long long 

using namespace std;

signed main()
{
    int n, m, q;
    
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> q;
    
    vector<vector<int>>s(n + 1, vector<int>(m + 1, 0));
    
    for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) cin >> s[i][j], s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    
    while(q -- )
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << '\n';
    }
    
}

小淞买食品

考点: 优先队列

想要尽可能的买最多的食品即每次都买最便宜的食品, 因为每买一个食品后, 该食品价格会翻倍, 所以要再次进行排序, 我们可以用到优先队列进行自动排序, 即可求解

#include<bits/stdc++.h>
 
using namespace std;
int n, x, t;
int  main()
{
     cin >> n >> x;
	 int num = 0, ans = 0;
     priority_queue<int,vector<int>, greater<int>>heap;
	 for(int i = 1; i <= n; i ++ ) cin >> num, heap.push(num);

	while(x)
	{
		int res = heap.top();
		if(x >= res) ans ++, x -= res;
		else break;
		heap.pop();
		heap.push(res * 2);
	}
	cout << ans << '\n';
    
    
}

小淞玩游戏

考察:双指针和 $map$
因为要计算当前单词和之前相同单词的距离, 我们可以考虑使用双指针, 记录位置, 通过 $map$ 记录与当前距离小于等于 $k$ 的相同单词的数量, 枚举每一个单词, 如果当前单词与左指针距离超过了 $k$, 那么左指针指向的单词出现次数减 $1$, 并且指针右移, 因为他已经超出了我们的范围, 然后计算与当前单词距离小于等于 $k$ 的相同单词的数量, 然后当前单词出现次数加 $1$

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int data = 10, n, k, l, r;
string word[N];
long long ans;
map<string,int>cnt;
signed main(){
	cin >> n >> k;
	for(int i = 1; i <= n; i ++) cin >> word[i];
	l = 1;
	for(int i = 1; i <= n; i ++)
	{
		while(i - l > k + 1) // 距离超过了k, 这个单词就不能与其他单词获得积分
		{
			cnt[word[l]]--; //出现次数--
			l++;  //指针右移
		}
		ans += cnt[word[i]]; // 记录答案
		cnt[word[i]] ++;  //当前单词出现次数+1
	}
	cout << ans << '\n';
}

小淞学英语

考察: $map$

利用 $map$ 记录每个单词的出现次数即可, 每次查询时将单词转为相反形式即可

#include<bits/stdc++.h>
using namespace std;
int n, k;
string word[100010];
map<string, int>s;
signed main()
{
	cin >> n >> k;
	string str;
	for(int i = 1; i <= n; i ++ ) cin >> str, s[str] ++;

	for(int i = 1; i <= k; i ++ )
	{
		cin >> str;
		for(int j = 0; j < (int)s.size(); j ++ )
		{
			if(str[j] >= 'a' && str[j] <= 'z') str[j] = toupper(str[j]);
			else str[j] = tolower(str[j]); 
		}
		cout << s[str] << '\n';
	}
}

小淞学数学

考察:对顶堆

对顶堆模板题,

当大根堆为空或者该数小于等于大根堆的堆顶元素时,插入大根堆, 否则插入小根堆, 当大根堆数量比小根堆多 $2$ 时, 取出一个,放入小根堆, 当小根堆数量比大根堆数量多 $1$ 时, 取出一个放入大根堆, 所以当元素个数为奇数时, 大根堆数量是比小根堆多 $1 的, 每次取出小根堆的堆顶元素即可

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int T;                                                      //T为数据集个数
    cin >> T;
    while (T -- )
    {
        int  n;
        cin >> n;

        priority_queue<int> down;                               //大根堆
        priority_queue<int, vector<int>, greater<int>> up;      //小根堆
        int cnt = 0;                                            //用于分隔输出,每十个数一行
        for (int i = 1; i <= n; i ++ )
        {
            int x;
            cin >> x;
            if (down.empty() || x <= down.top()) down.push(x);  //下面为空或x小于下方堆顶,则将x插入大根堆
            else up.push(x);
            //如果有偶数个数,上面和下面一样多,如果有奇数个数,则下面比上面多一个
            if (down.size() > up.size() + 1) up.push(down.top()), down.pop();   //下面多了挤一个放上面
            if (up.size() > down.size()) down.push(up.top()), up.pop();         //上面多了挤一个放下面
            if (i % 2 != 0)                                     //每插入奇数个数就输出一次中位数
                cout << down.top() << ' ';
        }
       cout << '\n';
    }
}

小淞看电视

考察: $bitset$ 和 动态规划

问题分析: 因为总时长要为 $3600$ 的倍数, 用数组存显然不太合适, 我们可以考虑用 $STL$ 中的 $bitset$, 每次选择一部动画片就将其左移 $w[i]$, 不选择则不操作, 然后求按位或一下即可, 这个类似于动态规划的思想, 选择该动画片和不选择该动画片, 然后对于 $3600$ 的倍数, 我们每次将其 右移 3600 则可以达到取模的效果, 然后只选某一个动画片也是合法的

#include<bits/stdc++.h>
const int N = 5e5 + 10;
using namespace std;
typedef pair<int, int>PII;
int n, w[N], T;
int main()
{
	ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
	cin >> T;
	while(T --)
	{
        cin >> n;
    	for(int i = 1; i <= n; i ++ ) cin >> w[i], w[i] %= 3600;
    
    	//找3600的倍数 
        bitset<3600 * 2> f;
    	for(int i = 1; i <= n; i ++ ) 
    		f |= (f << w[i]) | ((f << w[i]) >> 3600), f[w[i]] = 1;
    	if(f[0] ) cout << "YES\n";
    	else cout << "NO\n";
	}
}

完结撒花??ヽ(°▽°)ノ?

阅读世界，共赴山海

423全民读书节，邀你共读