刷题记录（好题）

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;
}