传送门

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)