SMU Summer 2023 Contest Round 5
A. Points in Segments
\(\mathcal{O}(n \times m)\) 做法数据范围小,直接把每次的\(l - r\)跑一遍标记一下,最后跑一遍循环统计哪些没有被标记的并且输出就好了
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int n,m;
cin >> n >> m;
vector<int> a(m + 1);
int ans = 0;
for(int i = 0;i < n;i ++){
int x,y;
cin >> x >> y;
for(int j = x;j <= y;j ++){
a[j] = 1;
}
}
for(int i = 1;i <=m;i ++ ){
ans += (a[i] == 0);
}
if(!ans){
cout << 0 << endl;
}else{
cout << ans << endl;
for(int i = 1;i <= m;i ++)
if(!a[i])
cout << i << ' ';
}
return 0;
}
\(\mathcal{O}(n + m)\) 做法数据再大点就可以开个前缀和数组,让每次输入的\(l\)所在的值为1,\(r\)的值为-1,然后跑一遍前缀和,统计为0的个数就行
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> cnt(m + 2);
for (int i = 0; i < n; ++i) {
int l, r;
cin >> l >> r;
++cnt[l];
--cnt[r + 1];
}
for (int i = 1; i <= m; ++i)
cnt[i] += cnt[i - 1];
vector<int> ans;
for (int i = 1; i <= m; ++i) {
if (cnt[i] == 0)
ans.push_back(i);
}
cout << ans.size() << endl;
for (auto it : ans) cout << it << " ";
cout << endl;
return 0;
}
B. Obtaining the String
\(\mathcal{O}(n^3)\) 长度只有50,直接跑暴力了,每次对比s和t是否相同,不同就去s后面找到当前与t相同的,然后从后一个一个交换过来,判断s能不能变成b就看s里每个字符数量和b是不是一样
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int n;
cin >> n;
string s,t;
cin >> s >> t;
if(s == t){
cout << 0 << endl;
return 0;
}
vector<int> numa(100),numb(100);
for(int i = 0;i < s.size();i ++){
numa[s[i] - 'a']++;
numb[t[i] - 'a']++;
}
for(int i = 0;i <= 100;i ++){
if(numa[i] != numb[i]){
cout << -1 << endl;
return 0;
}
}
int ans = 0;
vector<int> res;
for(int i = 0;i < n - 1;i ++){
if(s[i] == t[i]) continue;
for(int j = i + 1;j < n;j ++){
if(s[j] == t[i]){
for(int k = j;k > i;k--){
swap(s[k],s[k - 1]);
ans++;
res.push_back(k);
}
break;
}
}
}
cout << ans << endl;
for(auto i : res)
cout << i << ' ';
return 0;
}
\(\mathcal{O}(n^2)\) 做法就是在后面找到了之后单独拿出来从后跑一遍
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s, t;
cin >> n >> s >> t;
vector<int> ans;
for (int i = 0; i < n; ++i) {
if (s[i] == t[i]) continue;
int pos = -1;
for (int j = i + 1; j < n; ++j) {
if (s[j] == t[i]) {
pos = j;
break;
}
}
if (pos == -1) {
cout << -1 << endl;
return 0;
}
for (int j = pos - 1; j >= i; --j) {
swap(s[j], s[j + 1]);
ans.push_back(j);
}
}
cout << ans.size() << endl;
for (auto it : ans) cout << it + 1 << " ";
cout << endl;
return 0;
}
C. Songs Compression
\(\mathcal{O}(nlog_2n)\) 先把所有歌都压缩,如果还是小于\(m\)的话直接输出-1,否则就将内存的差值从小到大排序,每次从最小的差值开始加,看看能还原多少首歌,最后用总数去减掉还原的就是压缩的个数了
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int n,m;
cin >> n >> m;
vector<PII> a(n);
for(auto& [x,y] : a)
cin >> x >> y;
sort(a.begin(),a.end(),[](PII x,PII y){
return x.first - x.second < y.first - y.second;
});
int ans = 0, now = 0;
for(auto i : a){
now += i.second;
}
if(now > m){
cout << -1 << endl;
return 0;
}
for(auto i : a){
if(i.first - i.second + now <= m){
now += i.first - i.second;
ans ++;
}else
break;
}
cout << n - ans << endl;
return 0;
}
D. Walking Between Houses
\(\mathcal{O}(k)\) 首先$s < k \(和\)s < (n - 1) \cdot k\(这两种情况肯定是不行的,至于为什么,可以自己推导一下,然后就是一个贪心的思想,每次走当前能走的最远距离,即每次能走的距离为\)min(n-1,s-(k-1))$,然后s也要跟着更新
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int n,k,s;
cin >> n >> k >> s;
if(s > (n - 1) * k || s < k){
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl;
int sum = 0, now = 1;
for(; k;k-- ){
int i = min(s - k + 1, n - 1);
s -= i;
if( i + now > n){
cout << now - i << ' ';
now -= i;
}else {
cout << now + i << ' ';
now += i;
}
}
return 0;
}
后面摆了,反正cf分还没到那个段位(\(Orz\)