ywt51

3.2万

153775183@qq.com
huangbq
konjac_xm

acwing_52955

JcWing

02_4
Java不是瓜哇

zhuxiaorui

ywt51
49分钟前
//区间的个数是确定的，n的阶加，每个区间的核心数是确定的，找到后在对应数组下标记录
#include <bits/stdc++.h>
using namespace std;

const int N = 5010;
int cnt[N], res[N], bk[N];
int n, a[N];

int main() {
cin >> n;
for (int i = 0; i < n; ++ i) cin >> a[i];

for (int i = 0; i < n; ++ i) {
int cnt[N] = {};
for (int j = i, h = 0; j < n; ++ j) {
cnt[a[j]]++;
if (cnt[a[j]] > cnt[h] || cnt[a[j]] == cnt[h] && a[j] < h) h = a[j];
res[h]++;
}
}

for (int i = 1; i <= n; ++ i)
cout <<res[i] << ' ';
return 0;
}


ywt51
1小时前
#include <bits/stdc++.h>
using namespace std;

const int N = 1E3+10;
int a[N], n;

int main() {
cin >> n;
int res = 0;
for (int i = 1; i <= n; ++ i) cin >> a[i];

for (int i = 2; i <= n-1; ++ i)
if (a[i] > a[i-1] && a[i] > a[i+1] ||
a[i] < a[i-1] && a[i] < a[i+1])
res++;
cout << res;
return 0;
}


ywt51
3天前
##### 算法1：双重循环(暴力枚举) $O(n^2)$
#include <bits/stdc++.h>
using namespace std;

string a, b;

int main() {
getline(cin, a);
getline(cin, b);

a = " " + a + " ";
b = " " + b + " ";

//统一格式
for (int i = 0; i < a.size(); ++ i) a[i] = toupper(a[i]); //tolower()
for (int i = 0; i < b.size(); ++ i) b[i] = toupper(b[i]);

int p = -1, cnt = 0;
for (int i = 0; i < b.size(); ++ i) {
if (b[i] == a[0]) { //开头相等-进入遍历
int j = 0;
while (b[i+j] == a[j]) j++;
if (j == a.size()) {
if (p == -1) p = i;
cnt ++;
}
// bool f = 1; //for循环遍历，标记
// for (int j = 0; j < a.size(); ++ j)
//     if (b[i+j] != a[j]) {
//         f = 0;
//         break;
//     }
// if (f) {
//     if (p == -1) p = i;
//     cnt ++;
// }
}
}
if (cnt) cout << cnt << " " << p;
else cout << -1;
return 0;
}

##### 算法2：调用库函数-双重循环() $O(n^2)$
#include <bits/stdc++.h>
using namespace std;

string a, b;

int main() {
getline(cin, a);
getline(cin, b);
a = " " + a + " ";
b = " " + b + " ";

//统一格式
for (int i = 0; i < a.size(); ++ i) a[i] = toupper(a[i]); //tolower()
for (int i = 0; i < b.size(); ++ i) b[i] = toupper(b[i]);

//利用find函数查找 找不到，返回的是2的64次方-1，内存中64位全部是1，就是-1
int p = b.find(a), cnt = 0, st;

if (p != -1) {
st = p; //记录第一次出现的位置
cnt++;
while ((p = b.find(a, p+1)) != -1) cnt++;
cout << cnt << ' ' << st;
} else {
cout << -1;
}
return 0;
}

##### 算法3：把连续不含空格的单词拼接起来，判断是否相等() $O(n^2)$
#include <bits/stdc++.h>
using namespace std;

string a, b;

int main() {
getline(cin, a);
getline(cin, b);

//统一格式
for (int i = 0; i < a.size(); ++ i) a[i] = toupper(a[i]); //tolower()
for (int i = 0; i < b.size(); ++ i) b[i] = toupper(b[i]);

b = b + ' ';//确保最后能走到else中 判断是否相等

string t = "";
int p  = -1, cnt = 0;
for (int i = 0; i < b.size(); ++ i) {
if (b[i] != ' ') t += b[i]; //连续字符就拼接起来
else { //是空格
if (t == a) {
cnt++;
if (cnt == 1) p = i - a.size();
}
t = "";
}
}
if (p != -1) cout << cnt << ' ' << p;
else cout << p;
return 0;
}


ywt51
4天前
##### 算法1：双指针-扫描连续段() $O(n)$
//最大值就是最大平均值， 找最大值连续出现的长度
#include <bits/stdc++.h>
using namespace std;

const int N = 1E5+10;
int a[N], n, T;

int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
int mx = -1, res = 0;
for (int i = 0; i < n; ++ i) {
scanf("%d", &a[i]);
mx = max(mx, a[i]);
}
//1. 变量记录的方式
int len = 0;
for (int i = 0; i < n; ++ i) {
if (a[i] == mx) len++; //连续相等就累加
else len = 0; //最大值中断了，清零，从新计数
res = max(res, len);
}

//2. 双指针扫描的方式
// for (int i = 0; i < n; ++ i)
//     if (a[i] == mx) {
//         int j = i;
//         while (a[j] == mx && j < n) j++;
//         res = max(res, j-i);
//         i = j;
//     }
printf("%d\n", res);
}
return 0;
}

##### 算法2：变量维护最大值及其连续长度() $O(n)$
#include <bits/stdc++.h>
using namespace std;

int n, T, x;

int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
int res = 1, mx = -1, len = 0; //len记录当前最大值连续长度 mx最大值 res最大长度
while (n--) {
scanf("%d,", &x);
if (x > mx) mx = x, res = len = 1; //值最大优先，值最大的前提下 长度多
else if (x == mx) len++, res = max(res, len);
else len = 0;
}
printf("%d\n", res);
}
return 0;
}


ywt51
5天前
##### 算法1：贪心-区间分组(476ms) $O(nlogN)$
//每个区间必然属于某一个组，对每一个组看是否能加入之前的组，之前组的右端点小于 该区间的左端点可加入
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1E5+10;
PII a[N];
int n;

int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++ i) scanf("%d%d", &a[i].first, &a[i].second);
sort(a, a+n);

priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < n; ++ i)
if (heap.empty() || heap.top() >= a[i].first) heap.push(a[i].second);
else {
heap.pop();
heap.push(a[i].second); //更新该区间的最靠右的右端点
}
printf("%d", (int)heap.size());
return 0;
}

##### 算法2：离散化-差分(1041ms) $O(nlogN)$
//离散化-差分，求前缀和，被覆盖最多的就是最小组数
#include <bits/stdc++.h>
using namespace std;

map<int, int> mp;
int n, res;

int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++ i) {
int l, r;
scanf("%d%d", &l, &r);
mp[l] ++;
mp[r+1] --;
}
int s = 0; //求前缀和，过程中维护出最大值
for (auto [k, v] : mp) {
s += v;
res = max(res, s);
}
printf("%d", res);
return 0;
}


ywt51
6天前
##### 算法1：贪心-区间选点-排序(结构体存储) $O(nlogN)$
//转换：雷达放那可以覆盖当前小岛，转换到某一个区间；
//问题抽象：给定若干区间，最少选择多少个点，使得每个区间上至少有一个点；
//知识应用：同模板905题，区间选点
//贪心策略：
//1. 将所有区间按右端点排序；时间瓶颈在排序，NlogN，数据范围可以到10万级别
//   按左端点排序也可以，倒着扫描或者维护出右端点的最小值
//2. 依次扫描每个线段，
//   情况1，上次选择的点不在当前区间，则选择当前区间右端点，更有可能覆盖后面的；
//   情况2，上次选择的点在区间内，则当前区间已经被覆盖，直接看下一个区间
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
struct node{
double l, r;
bool operator< (const node& t) const{
return r < t.r; //按照右端点排序
}
}a[N];
int n, d, res;

int main() {
cin >> n >> d;
for (int i = 0, x, y; i < n; ++ i) {
cin >> x >> y;
if (y > d) { //y坐标大于了雷达半径 无法覆盖
cout << -1;
return 0;
}
double len = sqrt(d*d - y*y);
a[i] = {x - len, x + len};
}
sort(a, a+n);
double last = -2e9;
for (int i = 0; i < n; ++ i)
if (a[i].l > last) {
last = a[i].r;
res++;
}
cout << res;
return 0;
}

##### 算法2：贪心-区间选点-排序(pair存储) $O(nlogN)$
#include <bits/stdc++.h>
using namespace std;

typedef pair<double, double> PDD;
const int N = 1010;
PDD a[N];
int n, d;

int main() {
cin >> n >> d;
for (int i = 0, x, y; i < n; ++ i) {
cin >> x >> y;
if (y > d) {
cout << -1;
return 0;
}
double len = sqrt(d*d - y*y); //勾股定理计算出长度
a[i] = {x+len, x-len}; //按照右端点排序，所有右端点放在first位置
}
sort(a, a+n);
int cnt = 0;
double last = -2e9;
for (int i = 0; i < n; ++ i)
if (a[i].second > last) {
cnt ++;
last = a[i].first;
}
cout << cnt;
return 0;
}


ywt51
6天前
##### 算法1：数组维护前k个商品编号() $O(NKlogK)$
//只排序前k个商品编号，统计每个商品访问次数，50000 * 10 * 3  操作*排序
#include <bits/stdc++.h>

using namespace std;

const int N = 5E4+10;
int cnt[N], a[14], n, m;

int main() {
scanf("%d%d", &n, &m);
int k = 0;
for (int i = 0, id; i < n; ++ i) {
scanf("%d", &id);
if (i) {
printf("%d: ", id);
for (int j = 0; j < k; ++ j) printf("%d ", a[j]);
printf("\n");
}
cnt[id]++;
bool f = 1; //查看一下id是否已经在a数组中, 默认不在，需要加进去
for (int j = 0; j < k; ++ j)
if (a[j] == id)
f = 0;
if (f) a[k++] = id; //k记录数量
sort(a, a+k, [](int x, int y){ //匿名函数-lambda表达式
if (cnt[x] != cnt[y]) return cnt[x] > cnt[y];
return x < y;
});
k = min(k, m); //最多m个，k当前实际有的
}

return 0;
}

##### 算法2：set-map维护() $O(nlogm)$
//set维护次数-商品，次数负数表示，map正常存储商品-次数；次数更新时，set要删除
//常数比较大
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
set<PII> s; //默认是升序排序，小的在前，
map<int, int> cnt;
int n, m;

int main() {
scanf("%d%d", &n, &m);
for (int i = 0, id; i < n; ++ i) {
scanf("%d", &id);
if (i) {
printf("%d: ", id);
int j = 0;
for (auto item : s) {
if (++j > m) break;
printf("%d ", item.second);
}
printf("\n");
}
if (!cnt[id]) { //没有出现，就加入进去
cnt[id] = 1;
s.insert({-1, id});
} else {
s.erase({-cnt[id], id}); //删除原有的次数
cnt[id] = cnt[id] + 1;
s.insert({-cnt[id], id}); //重新插入
}

}
return 0;
}


ywt51
6天前
##### 算法1：模拟-字符串-操作-map(枚举) $O(n)$
#include <bits/stdc++.h>
using namespace std;

const int N = 15;
int n;
string a[N];
unordered_map<string, int> mp;

int main() {
cin >> n;
for (int i = 0; i < n; ++ i) cin >> a[i];
for (int i = 0; i < n; ++ i) {
string x, y;
int m, t;
cin >> x >> m >> t;
if (!t) continue;  //t为0，跳过，发给0个人，细节，不然有除0错误
mp[x] -= m/t * t; //x减去要发出去的钱
for (int i = 0; i < t; ++ i) {
cin >> y;
mp[y] += m/t; //y加上收到的钱
}
}
for (int i = 0; i < n; ++ i)
cout << a[i] << ' ' << mp[a[i]] << endl;
return 0;
}


ywt51
6天前
##### 算法2：模拟-字符串转换() $O(1)$
//字符串处理，转换为数字
#include <bits/stdc++.h>
using namespace std;

string a, b;

int main() {
cin >> a >> b;
int x = 1, y = 1;
for (int i = 0; i < a.size(); ++ i) x *= (a[i] - 'A' + 1);
for (int i = 0; i < b.size(); ++ i) y *= (b[i] - 'A' + 1);

if (x%47 == y%47) cout << "GO";
else cout << "STAY";
return 0;
}

##### 算法1：封装成函数-字符串转换(暴力枚举) $O(1)$
//字符串处理，转换为数字
#include <bits/stdc++.h>
using namespace std;

string a, b;
int get(string s) {
int res = 1; //最多6个字符，每个字母都是z, 就是26的6次方，3亿 不会超int
for (int i = 0; i < s.size(); ++ i)
res = res * (s[i] - 'A' + 1);
return res % 47;
}
int main() {
cin >> a >> b;
if (get(a) == get(b)) cout << "GO";
else cout << "STAY";
return 0;
}


ywt51
6天前
##### 算法1：循环(枚举) $O(n)$
//计算出左右两边回到当前点距离2倍的最小值
#include <bits/stdc++.h>
using namespace std;

int n;
int main() {
cin >> n;
for (int i = 1; i <= n; ++ i) {
int l = abs(i-1) * 2, r = abs(n-i) * 2;
cout << max(l, r) << endl;
//cout << max(i-1, n-i) * 2 << endl;
}
return 0;
}