传送门
A Points in Segments
直接把给出区间上的每一个放入set里，最后输出不在set里面的就行
//
// Author : north_h
// File : B.cpp
// Time : 2023/7/21/11:51
// _ _ _
// _ __ ___ _ __| |_| |__ | |__
//| '_ \ / _ \| '__| __| '_ \ | '_ \
//| | | | (_) | | | |_| | | | | | | |
//|_| |_|\___/|_| \__|_| |_|___|_| |_|
// |_____|
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.begin(),a.end()
#define int128 __int128
#define endl '\n'
const int N = 10010;
const int M = 110;
const int MOD = 998244353;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;
using namespace std;
inline 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() {
vector<int> ans;
int n, m;
cin >> n >> m;
set<int> st;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
for (int j = l; j <= r; j++)st.insert(j);
}
cout << m - st.size() << endl;
for (int i = 1; i <= m; i++) {
if (!st.count(i))cout << i << ' ';
}
cout << endl;
}
int main() {
IOS;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
B Obtaining the String
因为数据范围很小，直接暴力的交换字母就行了，可以直接使用swap函数我还写复杂了，比赛时一直不敢使用暴力
//
// Author : north_h
// File : B.cpp
// Time : 2023/7/21/11:51
// _ _ _
// _ __ ___ _ __| |_| |__ | |__
//| '_ \ / _ \| '__| __| '_ \ | '_ \
//| | | | (_) | | | |_| | | | | | | |
//|_| |_|\___/|_| \__|_| |_|___|_| |_|
// |_____|
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.begin(),a.end()
#define int128 __int128
#define endl '\n'
const int N = 10010;
const int M = 110;
const int MOD = 998244353;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;
using namespace std;
inline 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 aa[26],bb[26];
int vis[N];
void solve() {
int n;
cin >> n;
string a, b;
cin >> a >> b;
for (int i = 0; i < n; i++) {
aa[a[i] - 'a']++;
bb[b[i] - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (aa[i] != bb[i]) {
cout << -1 << endl;
return;
}
}
vector<int> ans;
string temp ;
for (int i = 0, j = 0; i < n; i++, j++) {
if (a[i] != b[j]) {
for (int k = i + 1; k < n; k++) {
if (a[k] == b[j]) {
for (int x = k; x >=i+1; x--) {
a[x] = a[x - 1];
}
a[i] = b[j];
for (int x = k - 1; x >= i; x--)
ans.push_back(x);
break;
}
}
//cout<<a<<' '<<b<<endl;
}
}
//cout<<a<<' '<<b<<endl;
cout << ans.size() << endl;
for (auto i: ans)cout << i + 1 << ' ';
cout << endl;
}
int main() {
//IOS;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
C Songs Compression
很简单，将两首歌曲的差值排序，贪心的去做，注意特判为0的情况下，最可气的，数组开小了TLE，导致我一直我从下手修改，原来数组开小了，不一定会RE，还有许多其他情况
//
// Author : north_h
// File : C.cpp
// Time : 2023/7/21/12:38
// _ _ _
// _ __ ___ _ __| |_| |__ | |__
//| '_ \ / _ \| '__| __| '_ \ | '_ \
//| | | | (_) | | | |_| | | | | | | |
//|_| |_|\___/|_| \__|_| |_|___|_| |_|
// |_____|
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.begin(),a.end()
#define int128 __int128
#define endl '\n'
const int N = 10010;
const int M = 110;
const int MOD = 998244353;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;
using namespace std;
inline 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, m;
scanf("%d%d", &n, &m);
ll sum = 0;
ll sum1 = 0;
vector<int> bb(n);
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
bb[i] = a - b;
sum += a;
sum1 += a - b;
}
if(sum<=m){
cout<<0<<endl;
return ;
}
sort(bb.begin(),bb.end(), greater<int>());
for (int i = 0; i < n; i++) {
if (sum - bb[i] <= m) {
cout << i + 1 << endl;
return;
}
sum -= bb[i];
}
cout<<-1<<endl;
}
int main() {
//IOS;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
D Walking Between Houses
我的做法是，每次都去走最大的距离，直到当剩下的总距离小于剩下的总步数时，在上一步走的时候，就只能走能让剩下的距离等于总步数的距离，然后后面的就
//
// Author : north_h
// File : D.cpp
// Time : 2023/7/21/15:45
// _ _ _
// _ __ ___ _ __| |_| |__ | |__
//| '_ \ / _ \| '__| __| '_ \ | '_ \
//| | | | (_) | | | |_| | | | | | | |
//|_| |_|\___/|_| \__|_| |_|___|_| |_|
// |_____|
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define int long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.begin(),a.end()
#define int128 __int128
#define endl '\n'
const int N = 10010;
const int M = 110;
const int MOD = 998244353;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;
using namespace std;
void solve() {
int n, k, s;
cin >> n >> k >> s;
int len=k;
if ((n - 1) * k < s || k > s) {
cout << "NO" << endl;
return;
}
vector<int> ans;
bool ok=true;
while (len--) {
if (s - (n - 1) > k - 1&&ok) {
if (!ans.size()||ans.back() == 1 )ans.push_back(n);
else ans.push_back(1);
s -= (n - 1);
k--;
} else if (s - (n - 1) <= k - 1&&ok) {
k--;
int x=s-k;
s = k;
ok=false;
if(!ans.size())ans.push_back(1+x);
else if (ans.back() == 1)ans.push_back(1 + x);
else ans.push_back(n - x);
} else {
if(!ans.size())ans.push_back(1);
else if (ans.back() == 1)ans.push_back(ans.back() + 1);
else if (ans.back() == n)ans.push_back(ans.back() - 1);
else ans.push_back(ans.back() + 1);
}
}
cout << "YES" << endl;
for (auto i: ans)cout << i << ' ';
}
int32_t main() {
IOS;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
E1 Stars Drawing (Easy Edition)
这个简单版本直接就暴力的每次就去判断就行，复杂度时O(n^3)，数据时100，妥妥能过
/*
Author : north_h
File : D.cpp
Time : 2023/7/21/7:36
_ _ _
_ __ ___ _ __| |_| |__ | |__
| '_ \ / _ \| '__| __| '_ \ | '_ \
| | | | (_) | | | |_| | | | | | | |
|_| |_|\___/|_| \__|_| |_|___|_| |_|
|_____|
*/
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define int128 __int128
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.end()
#define endl '\n'
const int N = 10010;
const int M = 1100;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;
using namespace std;
int n, m;
char g[M][M];
bool vis[M][M];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int dfs(int x,int y) {
int res = 0;
int row=min(abs(x-1),abs(n-x));
int col=min(abs(y-1),abs(m-y));
for (int i = 1; i <= min(row, col); i++) {
bool ok=true;
for (int j = 0; j < 4; j++) {
int xx = x + dx[j] * i;
int yy = y + dy[j] * i;
if (g[xx][yy] == '.'){
ok=false;
break;
}
}
if(ok) {
for (int j = 0; j < 4; j++) {
int xx = x + dx[j] * i;
int yy = y + dy[j] * i;
vis[xx][yy] = true;
}
res++;
}
else return res;
}
return res;
}
void solve() {
vector<int> ans;
int stars = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] == '*') {
stars++;
if (dfs(i, j)) {
vis[i][j]=true;
int cnt = dfs(i, j);
ans.push_back(i);
ans.push_back(j);
ans.push_back(cnt);
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (vis[i][j])stars--;
}
}
if (stars)cout << -1 << endl;
else {
cout<<ans.size()/3<<endl;
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << ' ';
if ((i + 1) % 3 == 0)cout << endl;
}
}
}
int main() {
IOS;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
E2 Stars Drawing (Hard Edition)
这个就不行了，得用前缀和来优化成O(n^2)
京公网安备 11010502036488号