Star 的档案库

Appearance

2026夏组队训练赛第十一场 ​

A. Adjusting Drones ​

cpp
#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << '=' << x << '\n';

void solve() {
    int n, k;
    cin >> n >> k;

    vector<int> cnt(n * 4 + 1);
    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        cnt[x] ++;
    }

    int ans = 0;
    int tmp = 0;
    int base = 0, add = 0;
    for (int i = 1; i <= n * 4; i ++) {
        //debug(tmp);
        if (base == 0) {
            if (cnt[i] > k) base = cnt[i];
        } else {
            tmp ++;
            if (cnt[i]) add += cnt[i] - 1;
            else {
                if (add) add --;
                else {
                    base --;
                    if (base <= k) {
                        base = 0;
                        ans = max(ans, tmp);
                        tmp = 0;
                        add = 0;
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t --) solve();
}

B. Billion Players Game ​

cpp
// #pragma GCC optimize("O2,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define i64 long long
#define db long double
#define pii pair<int,int>
#define tiii tuple<int,int,int>
#define ull unsigned long long
#define vi vector<int>
using ll = long long;
using i128 = __int128;
#define endl '\n'
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vector<int>>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int,vector<int>, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define INF 1e9
#define exp 1e-12
const int N=1e9;
const int mod=998244353;
void slove(){
    int n,l,r;
    cin>>n>>l>>r;
    vi a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    sort(all(a));
    int ans=0;
    for(int i=0;i<n/2;i++){
        int ll=a[i],rr=a[n-i-1];
        if(ll<l&&rr<l)ans+=l*2-ll-rr;
        else if(ll>r&&rr>r)ans+=rr+ll-2*r;
        else ans+=rr-ll;
    }
    if(n%2){
        if(a[n/2]<l)ans+=l-a[n/2];
        else if(a[n/2]>r)ans+=a[n/2]-r;
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("test/2.in","w",stdout);
    //cout<<fixed<<setprecision(10);
    int t=1;
    cin>>t;
    while(t--){
        slove();
    }
    return 0;
}

C. Chamber of Secrets 2 ​

cpp
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    int len = n * m / 2;

    vector<vector<int>> a(n, vector<int> (m));
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            cin >> a[i][j];
        }
    }

    sort(a.begin(), a.end());

    if (n == 1) {
        for (int i = 0; i < m / 2; i ++) cout << a[0][i] << ' ';
        cout << '\n';
        return;
    }

    if (n % 2 == 0) {
        for (int i = 0; i < n; i += 2) {
            for (int j = 0; j < m; j ++) {
                cout << a[i][j] << ' ';
            }
        }
        cout << '\n';
        return;
    }

    vector<int> vis(n);
    int cur = 0;
    vis[cur] = 0;
    for (int _ = 0; _ < n; _ ++) {
        // cout << "cur = " << cur << '\n';
        for (int i = 0; i < m / 2; i ++) cout << a[cur][i] << ' ';
        for (int i = 0; i < n; i ++) if (!vis[i]) {
            bool ok = 1;
            for (int j = 0; j < m / 2; j ++) {
                if (a[cur][j + m / 2] != a[i][j]) {
                    ok = 0;
                    break;
                }
            }
            if (ok) {
                vis[i] = 1;
                cur = i;
                break;
            }
        }
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t --) solve();
}

D. Dungeon Equilibrium ​

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> cnt(1001);
    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        cnt[x] ++;
    }

    int ans = 0;
    for (int i = 0; i <= 1000; i ++) {
        if (cnt[i] >= i) ans += cnt[i] - i;
        else ans += cnt[i];
    }

    cout << ans;
}

E. Expansion Plan 2 ​

cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <complex>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define bit bitset<N>
#define endl '\n'
void pr(vector<int> a) {
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
}
const int mod = 998244353;
const int INF = 1e18;
const int N = 129;
int p[N], p2[N];

void init() {}

void solve() {
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    vi sum4(n+1);
    for(int i=0;i<n;i++){
        sum4[i+1]=sum4[i]+(s[i]=='4');
    }
    while(q--){
        int l,r,x,y;
        cin>>l>>r>>x>>y;
        x=abs(x),y=abs(y);
        int s4=sum4[r]-sum4[l-1];
        int s8=r-l+1-s4;
        x-=s8,y-=s8;
        if(max(0ll,x)+max(0ll,y)>s4)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

F. Factory Table ​

cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 110;
typedef long long LL;
LL a[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    a[0] = 0x3f3f3f3f;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        int t = 0;
        for (int i = 2; i <= n; ++i) if (a[i] <= a[i - 1]) t++;
        if (t == 0) {
            LL d = a[2] - a[1];
            cout << max(d, a[n] / d) << '\n';
        }
        else if (t == 1) {
            for (int i = 2; i <= n; ++i) {
                if (a[i] <= a[i - 1]) {
                    cout << a[i - 1] / (a[i] - 1) << '\n';
                    break;
                }
            }
        }
        else {
            LL d = 0;
            for (int i = 1, cur = 0; i <= n; ++i) {
                if (a[i] <= a[i - 1]) cur = 1;
                else cur++;
                d = max(d, (LL)cur);
            }
            cout << d << '\n';
        }
    }
    return 0;
}

G. Git Gud ​

cpp
// #pragma GCC optimize("O2,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define i64 long long
#define db long double
#define pii pair<int,int>
#define tiii tuple<int,int,int>
#define ull unsigned long long
#define vi vector<int>
using ll = long long;
using i128 = __int128;
#define endl '\n'
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vector<int>>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int,vector<int>, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define INF 1e9
#define exp 1e-12
const int N=1e9;
const int mod=998244353;
void slove(){
    const int n=2.5e5;
    cout<<n<<endl;
    for(int i=1;i<=n;i*=63){
        for(int j=i;j<i*63;j+=i){
            for(int k=(n-j)/(i*63)*(i*63)+j;k>0;k-=i*63)cout<<k<<" "<<i<<endl;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        slove();
    }
    return 0;
}

J. Jewels Building ​

cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <complex>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define bit bitset<N>
#define endl '\n'
void pr(vector<int> a) {
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
}
const int mod = 998244353;
const int INF = 1e18;
const int N = 129;
int p[N], p2[N];

void init() {}

void solve() {
    int n, m;
    cin >> n >> m;
    vi a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    vvi dp(n + 1, vi(m + 1));
    dp[0][0] = 1;
    vi p(m+1,INF);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!dp[i][j]&&p[j]>i)
                continue;
            if (a[i] == b[j])
                dp[i + 1][j + 1] = 1;
            p[j+1]=min(p[j+1],i+b[j]);
        }
    }
    if (dp[n][m]||(p[m]<=n))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

L. LFS ​

cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int MOD = 1000000007;
const int N = 500010;

int pos[N][26], p[N];
LL ps[N][26];
LL freq[N], res[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    for (int i = 1; i <= n; ++i) {
        // cout << '\n';
        memcpy(pos[i], pos[i - 1], sizeof(int) * 26);
        memcpy(ps[i], ps[i - 1], sizeof(LL) * 26);
        pos[i][s[i - 1] - 'a'] = i;
        ps[i][s[i - 1] - 'a']++;
    }
    vector<pair<int, int>> qs(q);
    for (auto &[l, r] : qs) cin >> l >> r;
    for (int i = 0; i < q; ++i) {
        auto &[l, r] = qs[i];
        for (int j = 0; j < 26; ++j) {
            freq[i] = max(freq[i], ps[r][j] - ps[l - 1][j]);
        }
    }
    for (int len = 25; len; --len) {
        for (int i = 1; i <= n; ++i) {
            int &ls = pos[i - 1][s[i - 1] - 'a'];
            if (ls == 0 || i + len > n) p[i] = ls;
            else {
                bool flg = true;
                for (int j = 0; j <= len; ++j) {
                    if (s[ls + j - 1] != s[i + j - 1]) {
                        flg = false;
                        break;
                    }
                }
                if (flg) p[i] = p[ls];
                else p[i] = ls;
            }
        }
        for (int i = 0; i < q; ++i) {
            if (res[i]) continue;
            auto &[l, r] = qs[i];
            for (int j = 0; j < 26; ++j) {
                if (pos[r][j] + len <= r && pos[r][j] >= l && freq[i] == ps[r][j] - ps[l - 1][j] && p[pos[r][j]] < l) {
                    res[i] = len;
                    break;
                }
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << res[i] + 1 << '\n';
    }
    return 0;
}

其他没做的题

  • Hyper Smawk Bros
  • Isaac’s Queries
  • Keygen 3