A.取整
// Problem: A. Equalize Prices Again
// Contest: Codeforces - Codeforces Round 590 (Div. 3)
// URL: https://codeforces.com/contest/1234/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Date:2023-12-04 17:04:01
// Author:hblgzsx
// 借鉴思路：自己
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> a(n);
int sum = 0;
for(auto &x : a)
{
cin >> x;
sum += x;
}
cout << ((sum + n - 1 )/ n)<< "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
B1+B2.STL(模拟)
// Problem: B1. Social Network (easy version)
// Contest: Codeforces - Codeforces Round 590 (Div. 3)
// URL: https://codeforces.com/contest/1234/problem/B1
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Date:2023-12-04 17:08:59
// Author:hblgzsx
// 借鉴思路：自己
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
list<int> q;
map<int, int> vis;
for(int i = 0; i < n; i++)
{
int x;
cin >> x;
if(vis[x] == 0)
{
if(q.size() == k)
{
int f = q.back();
vis[f] = 0;
q.pop_back();
}
q.push_front(x);
vis[x] = 1;
}
// else
// {
// q.remove(x);
// if(q.size() == k) q.pop_back();
// q.push_front(x);
// }
}
cout << q.size() << "\n";
for(auto x : q) cout << x << " ";
cout << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while(t--)
{
solve();
}
return 0;
}
C.思维
// Problem: C. Pipes
// Contest: Codeforces - Codeforces Round 590 (Div. 3)
// URL: https://codeforces.com/contest/1234/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Date:2023-12-04 19:26:03
// Author:hblgzsx
// 借鉴思路：自己
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
int a[2][n + 1];
for(int i = 0; i < 2; i++)
{
string s;
cin >> s;
for(int j = 0; j < n; j++)
{
a[i][j] = s[j] - '0';
}
}
bool flag = true;
int tr = 0;
for(int i = 0; i < n; i++)
{
if(a[tr][i] > 2)
{
tr ^= 1;
if(a[tr][i] < 3)
{
flag = false;
break;
}
}
}
tr &= flag;
if(tr) cout << "YES\n";
else cout << "NO\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
D.二分，数据结构
// Problem: D. Distinct Characters Queries
// Contest: Codeforces - Codeforces Round 590 (Div. 3)
// URL: https://codeforces.com/contest/1234/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Date:2023-12-04 20:02:50
// Author:hblgzsx
// 借鉴思路：自己
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
void solve()
{
string s;
cin >> s;
vector<set<int>> id(26);
for(int i = 0; i < s.size(); i++)
{
id[s[i] - 'a'].insert(i);
}
int q;
cin >> q;
while(q--)
{
int op;
cin >> op;
if(op == 1)
{
int pos;
char c;
cin >> pos >> c;
pos--;
id[s[pos] - 'a'].erase(pos);
s[pos] = c;
id[c - 'a'].insert(pos);
}
else
{
int l, r;
cin >> l >> r;
l--;
int cnt = 0;
for(int i = 0; i < 26; i++)
{
auto it = id[i].lower_bound(l);
if(it != id[i].end() && *it < r) cnt++;
}
cout << cnt << "\n";
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while(t--)
{
solve();
}
return 0;
}
E.数学思维，差分前缀和
// Problem: E. Special Permutations
// Contest: Codeforces - Codeforces Round 590 (Div. 3)
// URL: https://codeforces.com/contest/1234/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Date:2023-12-04 20:17:16
// Author:hblgzsx
// 借鉴思路：自己
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
int n, m;
cin >> n >> m;
vector<int> a(m);
for(auto &x : a)
{
cin >> x;
x--;
}
vector<int> sum(n);
for(int i = 0; i < m - 1; i++)
{
int x = a[i], y = a[i + 1];
if(x > y) swap(x, y);
else if(x == y) continue;
sum[0] += y - x;
sum[x] -= y - x;
sum[x] += y;
sum[x + 1] -= y;
sum[x + 1] += y - x - 1;
sum[y] -= y - x - 1;
sum[y] += x + 1;
sum[y + 1] -= x + 1;
sum[y + 1] += y - x;
sum[n] -= y - x;
}
for(int i = 0; i < n; i++)
{
sum[i + 1] += sum[i];
}
for(int i = 0; i < n; i++)
{
cout << sum[i] << " ";
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while(t--)
{
solve();
}
return 0;
}
F.状态压缩DP
// Problem: F. Yet Another Substring Reverse
// Contest: Codeforces - Codeforces Round 590 (Div. 3)
// URL: https://codeforces.com/contest/1234/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Date:2023-12-05 00:31:15
// Author:hblgzsx
// 借鉴思路：自己
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
void solve()
{
string s;
cin >> s;
int f[1 << 20] = {};
memset(f, 0x80, sizeof f);
f[0] = 0;
//初始化
for(int i = 0; i < s.size(); i++)
{
int mask = 0;
for(int j = i; j < min(i + 20, int(s.size())); j++)
{
if(mask >> (s[j] - 'a') & 1)
{
break;
}
else
{
mask |= 1 << (s[j] - 'a');
f[mask] = j - i + 1;
}
}
}
//动态规划过程
for(int i = 1; i < (1 << 20); i++)
{
for(int j = 0; j < 20; j++)
{
if(i >> j & 1)
{
f[i] = max(f[i], f[i ^ 1 << j]);
}
}
}
//统计答案，某一状态+该状态补集
int ans = 0;
for(int i = 0; i < (1 << 20); i++)
{
ans = max(ans, f[i] + f[((1 << 20) - 1)^i]);
}
cout << ans << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while(t--)
{
solve();
}
return 0;
}
x10664