A. Prepend and Append
如果两段字符不同就可以删掉,如果不能删了就是最初的字符串
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
string s;
cin >> n >> s;
int l = 0, r = n - 1;
while (l <= r && s[l] != s[r]) l++, r--;
cout << (r - l + 1) << "\n";
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
B. Distinct Split
维护前缀集合和后缀集合即可
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, res = 0, va = 0, vb = 0;
string s;
cin >> n >> s;
map<char, int> b, a;
a[s[0]]++;
for (int i = 1; i < n; i++) b[s[i]]++;
for (auto [k, v]: a)
if (v > 0) va++;
for (auto [k, v]: b)
if (v > 0) vb++;
res = max( res , va + vb );
for( int i = 1 ; i < n-1 ; i ++ ){
a[ s[i] ] ++;
if( a[ s[i] ] == 1 ) va ++;
b[ s[i] ] --;
if( b[ s[i] ] == 0 ) vb --;
res = max( res , va + vb );
}
cout << res << "\n";
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
C. Negatives and Positives
如果先操作i
,然后操作i+1,i+2,i+3,...,i+k
,实际上等价于任意选两个数取反,所以要做的就是把正数和负数分开,如果负数是偶数就全部转换成正数,如果是奇数,就先尽可能的把小的负数转成正数,然后考虑吧最大的负数和最小的正数同时取反是否更优即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
void solve() {
int n = read(), res = 0;
vector<int> a, b;
for (int x; n; n--) {
x = read();
if (x >= 0) a.push_back(x);
else b.push_back(x);
}
sort(a.begin(), a.end()), sort(b.begin(), b.end());
for (auto i: a) res += i;
if (b.size() & 1) {
for (int i = 0; i < b.size() - 1; i++)
res -= b[i];
if (!a.empty()) res += max(b.back(), -2 * a.front() - b.back());
else res += b.back();
} else for (auto i: b) res -= i;
cout << res << "\n";
return;
}
int32_t main() {
for (int t = read(); t; t--) solve();
return 0;
}
D. Range Update Point Query
实际上对于一个数,操作不了多少次就会变成操作无效的数。所以可以维护懒标记的方式记录被操作次数,当实际询问的时候才去操作。
然后考虑懒标记的维护实际上就是区间修改、单点修改、单点查询,用树状数组维护一下就好了
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) ( x & -x )
const int N = 2e5 + 5;
int n , q;
int a[N], b[N];
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
int getVal(int x) {
int ans = 0;
for (int i = x; i; i -= lowbit(i)) ans += b[i];
return ans;
}
void add(int x, int val) {
for (int i = x; i <= n; i += lowbit(i))
b[i] += val;
return;
}
void update(int l, int r, int v) {
add(l, v), add(r + 1, -v);
return;
}
int modify(int x) {
int ans = 0;
while (x) ans += x % 10, x /= 10;
return ans;
}
void solve() {
n = read(), q = read();
fill( b , b+1+n , 0 );
for (int i = 1; i <= n; i++) a[i] = read();
for (int op, l, r, x, t; q; q--) {
op = read();
if (op == 1) l = read(), r = read(), update(l, r, 1);
else {
l = read(), x = getVal(l);
update( l , l , -x );
while (x--) {
t = modify(a[l]);
if (t == a[l]) break;
a[l] = t;
}
printf("%d\n" , a[l] );
}
}
return;
}
int32_t main() {
for (int t = read(); t; t--) solve();
return 0;
}
E. Dima and Guards
这个其实就是求最小值就好了,注意一定要花 n 元而不是最多花 n 元
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
int n , ans = -1, x , y ;
cin >> n;
for( int a , b , c , d , i = 1 ; i <= 4 ; i ++ ){
cin >> a >> b >> c >> d;
a = min( a , b ) , c = min( c , d );
if( a + c <= n ) {
ans = i , x = a , y = n - x;
break;
}
}
if( ans == -1 ) cout << "-1\n";
else cout << ans << " " << x << " " << y << "\n";
return 0;
}
F. Dima and To-do List
根据\(i\mod k\)分一下类,然后求和取最小值即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
int32_t main() {
int n = read() , k = read() , ans = 1, ansV = INT_MAX;
vector<int> f(k , 0 );
for( int i = 1 , x ; i <= n ; i ++ ) x = read() , f[i%k] += x;
for( int i = 1 ; i <= k ; i ++ )
if( f[i%k] < ansV ) ans = i , ansV = f[i];
cout << ans << "\n";
return 0;
}
G. Dima and Salad
\[\frac{\sum a_i}{\sum b_i} = k\\
\sum a_i - k\times \sum b_i = 0\\
\sum(a_i-kb_i)=0
\]
这样可以转化为\(v_i=a_i-kb_i,w_i=a_i\)的零一背包问题,只是背包的容量是\(0\),且\(v_i\)有正有负
把\(v_i\)按照正负分类后再分别求背包,f[i]
表示\(\sum v = i\)时\(\sum w\)的最大值,g[i]
表示\(\sum v=-i\)时\(\sum w\)的最大值,所以答案就是max( f[i] + g[i] )
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
int32_t main() {
int n = read(), k = read(), m = 1e4;
vector<int> v(n + 1), w(n + 1);
for (int i = 1; i <= n; i++) w[i] = read();
for (int i = 1, x; i <= n; i++)
x = read(), v[i] = w[i] - x * k;
vector<int> f(m + 1, INT_MIN) , g(m+1 , INT_MIN);
f[0] = g[0] = 0;
for (int i = 1; i <= n; i++) {
if (v[i] >= 0) {
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
} else {
v[i] *= -1;
for (int j = m; j >= v[i]; j--)
g[j] = max(g[j], g[j - v[i]] + w[i]);
}
}
int res = 0;
for( int i = 0 ; i <= m ; i ++ )
res = max( res , f[i] + g[i] );
if( res == 0 ) cout << "-1\n";
else cout << res << "\n";
return 0;
}
H. Dima and Trap Graph
(u,l,r)
表示到达u
时所能携带数的区间。然后做一个搜索加剪枝即可。
剪枝如下:
- 最优性剪枝,如果当前区间小于已知解,停止搜索。
- 记忆化,用
set
维护每个点被访问时的区间,如果重复出现,停止搜索。
很怪 dfs会 tle,但bfs跑的飞快。
#include<bits/stdc++.h>
using namespace std;
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
int32_t main() {
int n = read() , res = 0;
vector<vector<tuple<int, int, int>>> e(n + 1);
vector<set<pair<int, int>>> vis(n + 1);
for (int u, v, l, r, m = read(); m; m--)
u = read(), v = read(), l = read(), r = read(), e[u].emplace_back(v, l, r), e[v].emplace_back(u, l, r);
vis[1].emplace(1, 1e6);
queue<tuple<int, int, int> > q;
q.emplace(1, 1, 1e6);
while (!q.empty()) {
auto [u, l, r] = q.front();
q.pop();
if (u == n) {
res = max(res, r - l + 1);
continue;
}
int lt, rt;
for (auto [v, lk, rk]: e[u]) {
lt = max(l, lk), rt = min(r, rk);
if (lt > rt || rt - lt + 1 <= res) continue;
if (vis[v].emplace(lt, rt).second == false) continue;
q.emplace(v, lt, rt);
}
}
if (res == 0) cout << "Nice work, Dima!";
else cout << res;
return 0;
}
- Contest Spring Round Trial 2023contest spring round trial contest spring round 2023 contest summer round 2023 2023 contest summer round educational codeforces contest round codeforces contest round https beginner atcoder contest round trial regionals contest online 2023 programming regional contest 2023