SMU Spring 2023 Trial Contest Round 1（6/8）
A. Prepend and Append
只需考虑给定字符串两端是否符合10或01即可，双指针从两端模拟即可。
#include <iostream>
using namespace std;
void solution(){
int n;cin >> n;
string s;cin >> s;
int l = 0,r = n - 1;
while (l < r){
if ((s[l] == '1' && s[r] == '0') || (s[l] == '0' && s[r] == '1')){
l++,r--;
}else
break;
}
cout << r - l + 1 << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int _ = 1;cin >>_;
while (_--)
solution();
}
B. Distinct Split
考虑从正逆做两次前缀和统计不同字符即可
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
const int N = 2e5 + 7;
using namespace std;
int pos[N],nev[N];
char a[N];
void solution(){
int n;cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n + 5; ++i)pos[i] = 0,nev[i] = 0;
set<int> sv;
for (int i = 1; i <= n; ++i){
sv.insert(a[i]);
if (sv.empty() || sv.size() > pos[i - 1]){
pos[i] = pos[i - 1] + 1;
}else
pos[i] = pos[i - 1];
}
sv.clear();
for (int i = n; i >= 1; --i){
sv.insert(a[i]);
if (sv.empty() || sv.size() > nev[i + 1]){
nev[i] = nev[i + 1] + 1;
}else
nev[i] = nev[i + 1];
}
int res = 0;
for (int i = 1;i <= n;i++){
res = max(res,pos[i] + nev[i + 1]);
}
cout << res << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int _ = 1;cin >>_;
while (_--)
solution();
}
C. Negatives and Positives
选择两个相邻的元素取反，可以当成任选两个数字取反，故只需要统计负数出现的次数，当负数次数为偶数时，可以将全体数字为正，为偶数时需要减去绝对值最小的数。
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
const int N = 2e5 + 7;
#define ll long long
using namespace std;
int pos[N],nev[N];
int a[N];
void solution(){
int n;cin >> n;
ll sum = 0;
int pn = 0;
int mi = 1e9;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (a[i] < 0)pn++;
sum += abs(a[i]);
mi = min(mi,abs(a[i]));
}
if (pn == 0){
cout << sum << endl;
return;
}
if (pn % 2 == 0){
cout << sum << endl;
}else{
cout << sum - 2 * mi << endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int _ = 1;cin >>_;
while (_--)
solution();
}
D. Range Update Point Query
考虑在取值范围内的所以a，可以发现在有限次数内可以将此元素固定，故用set维护未固定的数，可以考虑用二分寻找。
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <vector>
const int N = 2e5 + 7;
#define ll long long
using namespace std;
int pos[N],nev[N];
int a[N];
vector<int> op[N];
int ovo(int t){
int sum = 0;
while (t){
sum += t % 10;
t /= 10;
}
return sum;
}
int cnt[N];
void solution(){
int n,k;cin >> n >> k;
set<int> d;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (a[i] > 9)d.insert(i);
}
for (int i = 1;i <= k;++i){
int t;cin >> t;
if (t == 1){
int l,r;cin >> l >> r;
while (!d.empty()){
auto it = d.lower_bound(l);
if (it == d.end() || *it > r)break;
a[*it] = ovo(a[*it]);
l = *it + 1;
if (a[*it] < 10)d.erase(it);
}
}else{
int x;
cin >> x;
cout << a[x] << endl;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int _ = 1;cin >>_;
while (_--)
solution();
}
E. Dima and Guards
寻找满足条件的值即可，注意答案相加为n
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <vector>
const int N = 2e5 + 7;
#define ll long long
using namespace std;
void solution(){
int cs;cin >> cs;
int res = 1e9;
int fir,sec;
int in = -1;
for (int i = 1;i <= 4;i++){
int a,b,c,d;cin >> a >> b >> c >> d;
if (min(a,b) + min(c,d) < res && min(a,b) + min(c,d) <= cs){
res = min(a,b) + min(c,d);
fir = min(a,b),sec = min(c,d);
in = i;
}
}
if (res == 1e9)cout << -1 << endl;
else
cout << in << " " << cs - sec << " " << sec << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int _ = 1;//cin >>_;
while (_--)
solution();
}
F. Dima and To-do List
考虑以1到k-1为开头可以包含全部情况，故用统计以1到k- 1为开头的能量，最后k个即为所以可能性的答案，取最小即可。
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
using namespace std;
#define ll long long
const int N = 2e5 + 7;
const int mod = 10007;
int a[N];
int s[N];
void solve(){
int n,k;cin >> n >> k;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = n + 1;i <= 2 * n;++i)
a[i] = a[i - 1];
for (int i = 1;i <= n;i++){
if (i < k){
s[i] = a[i];
}else
s[i] = s[i - k] + a[i];
}
int res = 1e9;
int in = -1;
for (int i = n;i > n - k;i--){
if (s[i] <= res){
in = k - (n - i + 1) + 1;
res = s[i];
}
}
cout << in << endl;
}
int main() {
ios::sync_with_stdio(false);
cout.tie(nullptr),cin.tie(nullptr);
int _ = 1; //cin >> _;
while (_--){
solve();
}
}
G. Dima and Salad
可得以上公式，即可以考虑当满足上式的情况下有
最大即可，故对于每个i有选与不选两种可能，考虑01背包
，考虑可能为负值，故对数组偏移位。答案为
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
using namespace std;
#define ll long long
const int N = 2e5 + 7;
const int mod = 10007;
int a[N];
int b[N];
int v[N];
int f[105][N];
void solve(){
int n,k;cin >> n >> k;
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)
v[i] = a[i] - k * b[i];
int m = 1e5;
const int bl = 2e5;
memset(f,-127,sizeof(f));
f[0][bl] = 0;
for (int i = 1; i <= n; ++i)
for (int j = m; j >= -m; --j){
f[i][j + bl] = max(f[i][j + bl],max(f[i - 1][j + bl],f[i - 1][j - v[i] + bl] + a[i]));
}
int res = -1;
if (f[n][bl])res = f[n][bl];
cout << res << endl;
}
int main() {
ios::sync_with_stdio(false);
cout.tie(nullptr),cin.tie(nullptr);
int _ = 1; //cin >> _;
while (_--){
solve();
}
}
H. Dima and Trap Graph
对答案左端点进行模拟，对边以r从大到小排序（因为我们需要尽可能的使区间大），当左端点固定时，模拟右端点，当1与n相通时即可break输出答案。考虑用并查集来判断相同情况即可。
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 3e3 + 7;
const ll mod = 1e9 + 7;
struct Node{
int x,y,l,r;
bool operator < (const Node&a)const{
return r > a.r;
}
}edge[N];
int f[N];
int find(int a){return f[a] == a ? a:f[a] = find(f[a]);}
void meger(int a,int b){
int x = find(a),y = find(b);
if (x != y){
f[x] = y;
}
}
void solve(){
int n,m;cin >> n >> m;
for (int i = 1; i <= m; ++i){
cin >> edge[i].x >> edge[i].y >> edge[i].l >> edge[i].r;
}
int res = 0;
sort(edge + 1,edge + 1 + m);
for (int i = 1;i <= m;i++){
for (int j = 1; j <= n; ++j)
f[j] = j;
for (int j = 1; j <= m; ++j){
if (edge[j].l > edge[i].l)continue;
meger(edge[j].x,edge[j].y);
if (find(1) == find(n)){
res = max(edge[j].r - edge[i].l + 1,res);
break;
}
}
}
if (res)cout <<