2023年9月28日
好尴尬啊，好尴尬啊，怎么就想不到呢？今天的C、D思路都是来源于知乎大佬。
【----->此篇博客解析<-----】
Acwing1275 最大数
题目理解
线段树，板子题。但是需要转化！！
- 每次添加一个数，看作在
flag + 1的位置上，修改一个数 - 然后
query是求l 到 flag的最大值 - 所以
pushup的操作就是最大值
代码实现
ll m, p;
ll flag = 0;
struct Node
{
int l, r;
ll val;
}tr[N * 4];
void pushup(int u){tr[u].val = max(tr[u << 1].val, tr[u << 1 | 1].val);}
void build(int u, int l,int r)
{
if(l == r) tr[u] = {l, r, 0};
else{
tr[u] = {l , r};
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
ll query(int u, ll l, ll r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].val;
ll val = LLONG_MIN;
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid) val = query(u << 1, l, r);
if(r > mid) val = max(query(u << 1 | 1, l, r), val);
return val;
}
void modify(int u, int a, ll val)
{
if(tr[u].l == tr[u].r) tr[u].val = val;
else{
int mid = (tr[u].l + tr[u].r) >> 1;
if(a <= mid) modify(u << 1, a, val);
else modify(u << 1 | 1, a, val);
pushup(u);
}
}
ll q = 0;
int main() {
cin >> m >> p;
build(1, 1, m);
while(m -- )
{
string op;
ll l;
cin >> op >> l;
if(op == "A"){
flag++;
modify(1, flag, (l + q) % p);
}else{
q = query(1, flag - l + 1, flag);
cout << q << endl;
}
}
return 0;
}
Acwing241 楼兰图腾
题目理解
树状数组板子题。
- 左边比它小的数乘右边比它小的数
- 左边比他大的数乘右边比它大的数
- 两个求和
代码实现
const int N = 200000 + 10;
ll tr[N], s[N];
ll n;
ll low[N], hig[N];
ll lowbit(ll a){return a & -a;}
ll add(ll a, ll v){for(int i = a; i <= N; i += lowbit(i)) tr[i] += v;}
ll sum(ll a)
{
ll val = 0;
for(int i = a; i ; i -= lowbit(i)) val += tr[i];
return val;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> s[i];
// 前面有多少个
for(int i = 1; i <= n; i++)
{
int b = s[i];
hig[i] = sum(n) - sum(b);
low[i] = sum(b - 1);
add(b, 1);
}
memset(tr, 0, sizeof tr);
ll resl = 0, resr = 0;
for(int i = n; i >= 1; i--)
{
int b = s[i];
resr += hig[i] * (sum(n) - sum(b));
resl += low[i] * (sum(b - 1));
add(b, 1);
}
cout << resr << " " << resl;
return 0;
}
Acwing1270 数列区间最大值
题目理解
就是线段树板子！pushup是操作最大值
代码实现
#include <iostream>
#include <algorithm>
#include <climits>
#include <unordered_map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
ll qmi(ll a, ll b){
ll res = 1;
while(b)
{
if(b & 1) res = res * a % Mod;
a = a * a % Mod;
b >>= 1;
}
return res;
}
ll inv(ll p){ return qmi(p, Mod - 2);}
ll mo(ll p){ return (p % Mod + Mod) % Mod;}
const int N = 1e5 + 10;
int n, m;
int w[N];
struct Node
{
int l, r;
int val;
}tr[N * 4];
void pushup(int u)
{
tr[u].val = max(tr[u << 1].val, tr[u << 1 | 1].val);
}
void build(int u, int l,int r)
{
if(l == r) tr[u] = {l, r, w[r]};
else{
tr[u] = {l, r};
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
int query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].val;
int mid = (tr[u].l + tr[u].r) >> 1;
int val = INT_MIN;
if(l <= mid) val = query(u << 1, l, r);
if(r > mid) val = max(val, query(u << 1 | 1, l, r));
return val;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
build(1, 1, n);
while(m -- )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query(1, l, r));
}
return 0;
}
Div.3 Round891 A Array Colorinig
题目理解
只要奇数的个数是偶数即可。
代码实现
void solve()
{
int n;
cin >> n;
int cnt = 0;
for(int i = 1; i <= n; i++)
{
int b;
cin >> b;
if(b%2) cnt++;
}
if(cnt % 2) cout << "NO" << endl;
else cout << "YES" << endl;
return;
}
Div.3 Round891 B Maximum Rounding
题目理解
从左往右扫，可以进位就把后面的都变0，前面的加一，然后开始往前扫，能进位就进！
特判当j == 0的时候，因为第一个的前面没有会SF
代码实现
void solve()
{
string s;
cin >> s;
int flag = INT_MAX;
for (int i = 0; i < s.size(); i++)
{
if (s[i] >= '5')
{
flag = i;
s[i] = '0';
if (i - 1 == -1)
{
cout << 1;
string str(s.size(), '0');
cout << str << endl;
return;
}
s[i - 1]++;
for (int j = i - 1; j >= 0; j--)
if (s[j] >= '5')
{
flag = i;
s[j] = '0';
if (j - 1 == -1)
{
cout << 1;
string str(s.size(), '0');
cout << str << endl;
return;
}
s[j - 1]++;
}
break;
}
}
if (s[0] >= '5' || s[0] == '0')
{
cout << 1;
string str(s.size(), '0');
cout << str << endl;
}
else
{
for (int i = 0; i < s.size(); i++)
if (i < flag)
cout << s[i];
else
cout << 0;
cout << endl;
}
return;
}
Div.3 Round891 C Assembly via Minimums
题目理解
这个题，完全没想到！哦不对，想到20%,可惜。我们来看下大佬的思路。博客链接放到了最顶上。
自己理解
- 因为那个出现的次数，所以我们就可以按照次数进行放置
- 用到了优先队列，就是可以排个序，其实我们也能全读进去然后排序
- 最重要的就是从小到大的出现次数为
n - 1 \ n - 2 \ n - 3 ...这个
代码实现
const int N = 1e3 + 10;
void solve()
{
int n;
priority_queue<int, vector<int>, greater<int>> q;
cin >> n;
for(int i = 1; i <= n * (n - 1) / 2; i++)
{
int t;
cin >> t;
q.push(t);
}
for(int i = 1; i < n; i++)
{
int t = q.top();
int w = n - i;
while(w--) q.pop();
if(i != n - 1)
cout << t << " ";
else
cout << t << " " << t;
}
cout << endl;
return;
}
Div.3 Round891 D Strong Vertices
题目理解！大佬思路！！
代码实现
const int N = 2e5 + 10;
int a[N], b[N];
void solve()
{
int n;
pair<int, int> q[N];
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++)
cin >> b[i];
for(int i = 1; i <= n; i++)
q[i].y = i, q[i].x = a[i] - b[i];
sort(q + 1, q + 1 + n);
int m = q[n].x;
vector<int> vec;
for(int i = 1; i <= n; i++)
if(q[i].x == m)
vec.push_back(q[i].y);
cout << vec.size() << endl;
for(int i = 0; i < vec.size(); i++) cout << vec[i] << " ";
cout << endl;
return;
}