有无 AI 鉴定

友情提示：竞赛组委会邮箱 [email protected]

CQ-S00030

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    freopen("crystal.in","r",stdin);
    freopen("crystal.out","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    long long m;
    if(!(cin>>n>>m))return 0;
    vector<long long>a(n);
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    vector<long long>prefix(n+1,0);
    for(int i=0;i<n;i++){
        prefix[i+1]=prefix[i]+a[i];
    }
    int max_k=0;
    int left=0;
    for(int right =0;right<n;++right){
        long long k=right-left+1;
        long long cost=k*a[right]-(prefix[right+1])-prefix[left];
        while (cost>m && left <= right){
            left++;
            k=right-left+1;
            if (left<=right){
                cost=k*a[right]-(prefix[right+1]-prefix[left]);
            }
        }
        if (left <=right){
            max_k=max(max_k,right-left+1);
        }
    }
    cout<<max_k;
    return 0;



}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF=(ll)4e18;
int main(){
    freopen("subway.in","r",stdin);
    freopen("subway.out","w",stdout);
    ll c,n,m,d,q;
    if(fscanf(fi,"%lld %lld %lld %lld %lld",&c,&n,&m,&d,&q)!=5){ fclose(fi); fclose(fo); return 0; }
    vector<ll> w(m+1);
    for(ll v=1;v<=m;v++) fscanf(fi,"%lld",&w[v]);
    // lines: lists of (station, t)
    vector<vector<pair<ll,ll>>> line(n+1);
    // atStation[v] = list of (line, t)
    vector<vector<pair<ll,ll>>> atSt(m+1);
    for(ll i=1;i<=n;i++){
        ll k; fscanf(fi,"%lld",&k);
        for(ll j=0;j<k;j++){ ll a,t; fscanf(fi,"%lld %lld",&a,&t); line[i].push_back({a,t}); atSt[a].push_back({i,t}); }
    }
    // W[i][j] min transfer cost
    vector<vector<ll>> W(n+1, vector<ll>(n+1, INF));
    for(ll i=1;i<=n;i++) W[i][i]=0;
    for(ll v=1;v<=m;v++){
        auto &L=atSt[v];
        for(ll x=0;x<(ll)L.size();x++)
            for(ll y=x+1;y<(ll)L.size();y++){
                ll i=L[x].first, ti=L[x].second;
                ll j=L[y].first, tj=L[y].second;
                ll val=ti+tj;
                if(val<W[i][j]) W[i][j]=val;
                if(val<W[j][i]) W[j][i]=val;
            }
    }
    for(ll k=1;k<=n;k++){
        vector<ll> &Wk=W[k];
        for(ll i=1;i<=n;i++){
            if(W[i][k]>=INF) continue;
            ll wik=W[i][k];
            vector<ll> &Wi=W[i];
            for(ll j=1;j<=n;j++){
                if(Wk[j]>=INF) continue;
                ll v=wik+Wk[j];
                if(v<Wi[j]) Wi[j]=v;
            }
        }
    }
    for(ll r=0;r<q;r++){
        ll x,y; fscanf(fi,"%lld %lld",&x,&y);
        ll best=INF;
        for(auto &p1: atSt[x]){
            ll i=p1.first, ti=p1.second;
            for(auto &p2: atSt[y]){
                ll j=p2.first, tj=p2.second;
                if(W[i][j]>=INF) continue;
                ll val=ti+W[i][j]+tj;
                if(val<best) best=val;
            }
        }
        if(best>=INF) best=0; // should not happen (connected)
        fprintf(fo,"%lld\n", w[x]+w[y]+best);
    }
    fclose(fi); fclose(fo);
    return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    freopen("migrate.in","r",stdin);
    freopen("migrate.out","w",stdout);

    long long c,t;
    if(fscanf(fi,"%lld %lld",&c,&t)!=2){ fclose(fi); fclose(fo); return 0; }
    while(t--){
        long long n,d;
        if(fscanf(fi,"%lld %lld",&n,&d)!=2) break;
        vector<long long> x(n);
        for(long long i=0;i<n;i++) if(fscanf(fi,"%lld",&x[i])!=1) return 0;
        vector<int> r(n);
        { int j=0; for(int i=0;i<n;i++){ if(j<i)j=i; while(j+1<n && x[j+1]-x[i]<=d) j++; r[i]=j; } }
        long long ans=0;
        vector<int> ways(n,0), suf(n+1,0);
        for(int u=0;u<n;u++){
            ways[u]=1;
            int prevL=u, prevR=u;
            int nextR=r[u];
            if(nextR<=prevR){ continue; }
            for(int v=prevR+1; v<=nextR; v++) ways[v]=1;
            prevL=prevR; prevR=nextR;
            while(prevR<n-1){
                int nn=r[prevR];
                if(nn<=prevR) break;
                int s=0;
                for(int y=prevR; y>prevL; y--){ s+=ways[y]; if(s>3)s=3; suf[y]=s; }
                int a=prevL+1;
                for(int v=prevR+1; v<=nn; v++){
                    while(a<=prevR && r[a]<v) a++;
                    int val = (a<=prevR)? suf[a] : 0;
                    if(val>3) val=3;
                    ways[v]=val;
                    if(val==2) ans++;
                }
                prevL=prevR; prevR=nn;
            }
        }
        fprintf(fo,"%lld\n",ans);
    }
    fclose(fi); fclose(fo);
    return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
static const int INF=1000000000;
int n; vector<vector<int>> adj;
vector<int> stamp, par_, order_, h_, inc_, U_;
int curstamp=0;
int R;

int gcomp(const vector<int>& nodes, int rt){
    ++curstamp;
    for(int v: nodes) stamp[v]=curstamp;
    order_.clear();
    for(int v: nodes) par_[v]=-2;
    par_[rt]=-1;
    vector<int> st; st.push_back(rt);
    while(!st.empty()){
        int a=st.back(); st.pop_back();
        order_.push_back(a);
        for(int b: adj[a]) if(stamp[b]==curstamp && par_[b]==-2){ par_[b]=a; st.push_back(b); }
    }
    for(int idx=(int)order_.size()-1; idx>=0; idx--){
        int a=order_[idx];
        int mx=0; long long tot=1;
        for(int b: adj[a]) if(stamp[b]==curstamp && par_[b]==a){
            if(1+h_[b]>mx) mx=1+h_[b];
            long long add = (h_[b]<=R-1)?0:(long long)INF;
            if(inc_[b]<add) add=inc_[b];
            tot+=add; if(tot>INF) tot=INF;
        }
        h_[a]=mx; inc_[a]=(int)tot;
    }
    U_[rt]=-1;
    for(int idx=0; idx<(int)order_.size(); idx++){
        int a=order_[idx];
        int best1=-1,best2=-1;
        for(int b: adj[a]) if(stamp[b]==curstamp && par_[b]==a){ int val=1+h_[b]; if(val>best1){best2=best1;best1=val;} else if(val>best2) best2=val; }
        for(int b: adj[a]) if(stamp[b]==curstamp && par_[b]==a){
            int val=1+h_[b];
            int sib=(val==best1)?best2:best1;
            int cand=U_[a];
            if(sib>cand) cand=sib;
            if(0>cand) cand=0;
            U_[b]=1+cand;
        }
    }
    int best=INF;
    for(int a: order_) if(U_[a]<=R && inc_[a]<best) best=inc_[a];
    return best;
}

int main(){
    freopen("hub.in","r",stdin);
    freopen("hub.out","w",stdout);

    int c,t;
    if(fscanf(fi,"%d %d",&c,&t)!=2){ fclose(fi); fclose(fo); return 0; }
    while(t--){
        int k;
        if(fscanf(fi,"%d %d",&n,&k)!=2) break;
        adj.assign(n+1, vector<int>());
        vector<pair<int,int>> edges;
        for(int i=0;i<n-1;i++){ int u,v; fscanf(fi,"%d %d",&u,&v); adj[u].push_back(v); adj[v].push_back(u); edges.push_back({u,v}); }
        stamp.assign(n+1,0); par_.assign(n+1,-2); h_.assign(n+1,0); inc_.assign(n+1,0); U_.assign(n+1,0);
        curstamp=0;
        vector<int> allnodes(n); for(int i=0;i<n;i++) allnodes[i]=i+1;
        // binary search R in [0,n]
        int lo=0, hi=n, ansR=n;
        while(lo<=hi){
            R=(lo+hi)/2;
            int f=gcomp(allnodes,1);
            // 2-block
            vector<int> mark(n+1,0);
            for(auto &e: edges){
                int u=e.first,v=e.second;
                // component of u avoiding v
                vector<int> X,Y;
                { ++curstamp; vector<int> st; st.push_back(u); stamp[u]=curstamp; X.push_back(u);
                  while(!st.empty()){ int a=st.back(); st.pop_back(); for(int b: adj[a]) if(b!=v && stamp[b]!=curstamp){ stamp[b]=curstamp; st.push_back(b); X.push_back(b);} } }
                { int save=curstamp; ++curstamp; vector<int> st; st.push_back(v); stamp[v]=curstamp; Y.push_back(v);
                  while(!st.empty()){ int a=st.back(); st.pop_back(); for(int b: adj[a]) if(b!=u && stamp[b]!=curstamp){ stamp[b]=curstamp; st.push_back(b); Y.push_back(b);} } (void)save; }
                int gx=gcomp(X,u), gy=gcomp(Y,v);
                long long s=(long long)gx+gy; if(s<f) f=(int)min<long long>(s,INF);
            }
            if(f<=k){ ansR=R; hi=R-1; } else lo=R+1;
        }
        fprintf(fo,"%d\n",ansR);
    }
    fclose(fi); fclose(fo);
    return 0;
}