刷题记录（好题）

Problem - D - Codeforces
思路：

滑动窗口思想，一个数组记录起始点（记录出现过的次数），另一个数组记录截至点（记录出现过的次数），从0开始遍历，设定一个长度为d的滑动窗口，用一个数记录滑动窗口内次数的总和，当边界>d时，进行最大值最小值比较（滑动窗口每次移动总和都会发生变化，因此可以来判断出最大和最小值），比较完之后要减去原来起始点的次数值（因为此时起始点已经来到了r-d+1，也就是往右移动了一位）.

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<stdio.h>
#include<unordered_map>
#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
const int N = 2e6 + 10;
void solve()
{
	ll n, d, k;
	cin >> n >> d >> k;
	vector<ll>a(n+1);
	vector<ll>b(n+1);
	while (k--)
	{
		ll x, y;
		cin >> x >> y;
		a[x]++;
		b[y]++;
	}
	ll mi = 1e9, mx = 0;
	ll mmi, mxx;
	ll l;
	for (int r = 1, now = 0; r <= n; r++)//滑动窗口更新最大值最小值
	{
		now += a[r];
		if (r >= d)
		{
			l = r - d + 1;
			if (now < mi)
			{
				mi = now;
				mmi = l;
			}
			if (now > mx)
			{
				mx = now;
				mxx = l;
			}
			now -= b[l];//此时已往右移动了一位，所以需要减去（因为now记录的是滑动窗口里的值）
		}
	}
	cout << mxx << " " << mmi << "\n";
	return;
}
int main()
{	
	IOS;
	ll t;
	cin >> t;
	while(t--)
	solve();
	return 0;
}

Problem - C - Codeforces
思路：

利用两个嵌套的vector,第一个预处理数组里的数字，第二个预处理字符串，（先判断当前数据出现次数，若未出现过则将i对其进行赋值，并以i为小标存入vector中，若出现则以其一共出现过的次数为小标存入vector中）

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n;
    cin >> n;
    map<int, int> mp;
    vector<int> a(n);
    vector ve(n, vector<int>());
    for (int i = 0; i < n ; i ++) {
        cin >> a[i];
        if (!mp.count(a[i])) {
            mp[a[i]] = i;
            ve[i].push_back(i);
        } else {
            ve[mp[a[i]]].push_back(i);
        }
    }
     int m;
    cin >> m;
    while (m--) {
        string s;
        cin >> s;
 
        if (s.size() != n) {
            cout << "NO\n";
            continue;
        }
         map<int, int> mp1;
        vector Ve(n, vector<int>());
        for (int i = 0; i < s.size(); i ++) {
            if (!mp1.count(s[i])) {
                mp1[s[i]] = i;
                Ve[i].push_back(i);
            } else {
                Ve[mp1[s[i]]].push_back(i);
            }
        }
         cout << (Ve == ve ? "YES\n" : "NO\n");
    }
 
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
     return 0;
}

P3385 【模板】负环 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

cnt数组记录经过点的个数，w数组记录1到各个点的最短距离，用spfa来求最短距离，每进行一次赋值后对cnt数组进行+1，若cnt数组的个数>=n即说明经过了n个或以上个点（因为cnt只有找到最小值后进行赋值时才能+1，所以说明绝对存在负权边，即负环，因为经过它之后权又变小了）

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<stdio.h>
#include<unordered_map>
#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
const int N = 2e6 + 10;
struct edge{
	int id, dis;
};
vector<edge> a[N];
int n, m, w[N], cnt[N], dis;
bool f[N];
bool spfa() {
	queue<int>q;
	q.push(1);
	w[1] = 0;
	while (!q.empty()) {
		int u = q.front();q.pop();
		f[u] = 0;
		for (int i = 0; i < a[u].size(); i++) {
			int v = a[u][i].id;
			dis = w[u] + a[u][i].dis;
			if (dis < w[v]) {
				w[v] = dis;
				cnt[v] = cnt[u] + 1;
				if (cnt[v]>=n) {
					return 1;
				}
				if (!f[v]) {
					q.push(v);
					f[v] = 1;
				}
			}
		}
	}
	return 0;
}
void solve() {
	memset(w, 0x7f, sizeof(w));
	memset(cnt, 0, sizeof(cnt));
	memset(f, 0, sizeof(f));
	cin >> n >> m;
	int u, v, d;
		for (int i = 1; i <= m; i++)
		{
			cin >> u >> v >> d;
			a[u].push_back({ v,d });
			if (d >= 0)
			{
				a[v].push_back({ u,d });
			}
		}
		if (spfa())cout << "YES\n";
		else {
			cout << "NO\n";
		}
		for (int k = 1; k <= n; k++)
		{
			a[k].clear();
		}
}
int main(){	
	IOS;
	ll t;
	cin >> t;
	while(t--)
	solve();
	return 0;
}