2024初三集訓(xùn)模擬測試1

~~所以正解和一行 \(-1\) 等分~~

upd 2.20 終于重測了

T1 edit：

語法題。

考 getline 正確使用

T2 game：

簡單 \(dp\)

也可以貪心，見 The_Shadow_Dragon。

注意初始化。

CODE

#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using ull=unsigned long long;
#define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
const int N=1e5+3;
int n,a[N];
llt dp[N][3];

int main(){
#ifndef ONLINE_JUDGE
    freopen("in_out/in.in","r",stdin);
    freopen("in_out/out.out","w",stdout);
#else
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
#endif
    scanf("%d",&n);
    For(i,1,n,1) scanf("%d",a+i);
    sort(a+1,a+1+n,greater<int>());
    dp[1][1]=a[1];dp[1][0]=-0x3f3f3f3f3f3f3f3f;
    For(i,2,n,1){
        dp[i][0]=dp[i-1][1];
        dp[i][1]=max(dp[i-1][0],dp[i-1][1])+a[i];
    }
    printf("%lld",max(dp[n][0],dp[n][1]));
}

T3 score：

發(fā)現(xiàn)值域很小，直接枚舉平均數(shù)。

將所有數(shù)減掉平均數(shù)，就變成了序列中選區(qū)間和為 \(0\)。

前綴和，變成了選序列中值一樣兩個數(shù)的方案，桶維護(hù)即可。

CODE

#include<bits/stdc++.h>
using namespace std;
typedef long long llt;
typedef unsigned long long ull;
#define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
const int N=1e5+3,R=1e7;
int to[(R<<1)+3],a[N],ma,n;
llt ans;

namespace IO{
    template<typename T> inline void write(T x){
        static T st[45];T top=0;if(x<0)x=~x+1,putchar('-');
        do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48);
    }
    template<typename T> T READ_NONPARAMETRIC_INIT;
    template<typename T = int> inline T read(T &x=READ_NONPARAMETRIC_INIT<T>){
        char s=getchar();x=0;bool pd=false;while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
        while('0'<=s&&s<='9'){x=(x<<1)+(x<<3)+(s^48),s=getchar();}if(pd) x=-x; return x;
    }
}
namespace IO{
    template<> inline char read(char &c){c=getchar();while(c<33||c>126) c=getchar();return c;}
    template<int MAXSIZE=INT_MAX> inline int read(char* c){
        char s=getchar();int pos=0;while(s<33||s>126) s=getchar();
        while(s>=33&&s<=126&&pos<=MAXSIZE) c[pos++]=s,s=getchar();c[pos]='\0';return pos;
    }
    template<typename T,typename... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
    template<> inline void write(char c){putchar(c);}
    template<> inline void write(char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
    template<typename T> inline void Write(T x){write(x),putchar(' ');}
    template<> inline void Write(char c){write(c),putchar(' ');}
    template<> inline void Write(char *c){write(c),putchar(' ');}
    template<typename T,typename... Args> inline void write(T x,Args... args){write(x);write(args...);}
    template<typename T,typename... Args> inline void Write(T x,Args... args){Write(x);Write(args...);}
}
using namespace IO;
inline void Cnt(int arg){
    int qs=0;to[R]=1;
    For(i,1,n,1){
        qs+=a[i]-arg;
        ans+=to[qs+R]++;
    }
    qs=0;
    For(i,1,n,1){
        qs+=a[i]-arg;
        to[qs+R]--;
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in_out/in.in","r",stdin);
    freopen("in_out/out.out","w",stdout);
#else 
    freopen("score.in","r",stdin);
    freopen("score.out","w",stdout);
#endif 
    read(n);
    For(i,1,n,1) ma=max(ma,read(a[i]));
    For(i,1,ma,1) Cnt(i);
    write(ans);
}

T4 city

首先先并查集一下將點分成一些連通塊。

發(fā)現(xiàn)最小加邊要最大化單點個數(shù)，最大加邊就要最大化最大連通塊點的個數(shù)。

所以從大到小合并，求最小最大加邊。

對于塊之間的邊最少不加，最多每個點向?qū)γ孢B單向邊，也就是 \(size1\times size2\) 的。

判斷完直接加邊即可。

CODE

#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using ull=unsigned long long;
#define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
const int N=5e5+3;
int n,m,cx,q,bs;
llt ma,mi;
vector<int> c[N];
class FIND{
private:
    int f[N];
public:
    FIND(){For(i,1,N-2,1) f[i]=i;}
    inline int Get(int x){return f[x]==x?x:f[x]=Get(f[x]);}
    inline void Uni(int a,int b){int fa=Get(a),fb=Get(b); if(fa!=fb) f[fb]=fa;}
}fd;
bool cmp(vector<int> a,vector<int> b){return a.size()>b.size();}

int main(){
    freopen("city.in","r",stdin);
    freopen("city.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&cx,&q);
    For(i,1,q,1){
        int a,b;scanf("%d%d",&a,&b);
        fd.Uni(a,b);
    }
    For(i,1,n,1) c[fd.Get(i)].push_back(i);
    sort(c+1,c+1+n,cmp);
    For(i,1,n,1){
        if(c[i].empty()) break;
        bs++;
    }
    int lcbs=bs,csum=0;
    For(i,2,lcbs,1){
        if(bs<=cx) break;
        int len=c[i].size();
        For_(j,len-1,0,1) c[1].push_back(c[i][j]),c[i].pop_back();
        bs--;
    }
    if(bs!=cx){puts("-1");return 0;}
    sort(c+1,c+1+n,cmp);
    For(i,1,bs,1){
        int sz=c[i].size();
        ma+=1ll*sz*(sz-1);
        mi+=((sz<=1)?0:sz);
    }
    if(m<mi||m>ma) {puts("-1");return 0;}
    For(k,1,bs,1){
        int len=c[k].size();
        if(len<=1) continue;
        printf("%d %d\n",c[k][len-1],c[k][0]);
        For(i,1,len-1,1) printf("%d %d\n",c[k][i-1],c[k][i]);
    }
    For(k,1,bs,1){
        if(mi>=m) return 0;
        int len=c[k].size();
        For(i,0,len-2,1){
            For(j,0,len-1,1){
                if(i==j||i+1==j) continue;
                printf("%d %d\n",c[k][i],c[k][j]);
                mi++;
                if(mi>=m) return 0;
            }
        }
        For(j,1,len-2,1){
            printf("%d %d\n",c[k][len-1],c[k][j]);
            mi++;
            if(mi>=m) return 0;
        }
    }
}

這題其實就是頭圖的題，所以我和 wkh2008 整了份 SPJ。

然后就被我錯解肆意水過：