门户网站内容建设,王也个人资料,户县微网站建设,河北邢台地图Problem - D - Codeforces 思路#xff1a;
滑动窗口思想#xff0c;一个数组记录起始点#xff08;记录出现过的次数#xff09;#xff0c;另一个数组记录截至点#xff08;记录出现过的次数#xff09;#xff0c;从0开始遍历#xff0c;设定一个长度为d的滑动窗口…Problem - D - Codeforces 思路
滑动窗口思想一个数组记录起始点记录出现过的次数另一个数组记录截至点记录出现过的次数从0开始遍历设定一个长度为d的滑动窗口用一个数记录滑动窗口内次数的总和当边界d时进行最大值最小值比较滑动窗口每次移动总和都会发生变化因此可以来判断出最大和最小值比较完之后要减去原来起始点的次数值因为此时起始点已经来到了r-d1也就是往右移动了一位.
#define _CRT_SECURE_NO_WARNINGS 1
#includebits/stdc.h
#includestdio.h
#includeunordered_map
#includeunordered_set
#includeiostream
#includealgorithm
#includecstring
#includevector
#includequeue
#includemap
#includecmath
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;vectorlla(n1);vectorllb(n1);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;mapint, int mp;vectorint a(n);vector ve(n, vectorint());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;}mapint, int mp1;vector Ve(n, vectorint());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
#includebits/stdc.h
#includestdio.h
#includeunordered_map
#includeunordered_set
#includeiostream
#includealgorithm
#includecstring
#includevector
#includequeue
#includemap
#includecmath
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;
};
vectoredge a[N];
int n, m, w[N], cnt[N], dis;
bool f[N];
bool spfa() {queueintq;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;
}
