2024初三集训模拟测试1

所以正解和一行 −1 等分

1. T1 edit：

   考 getline 正确使用

2. 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]));}

3. T3 score：

   发现值域很小，直接枚举平均数。

   将所有数减掉平均数，就变成了序列中选区间和为 0。

   前缀和，变成了选序列中值一样两个数的方案，桶维护即可。

   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);}

4. T4 city

   首先先并查集一下将点分成一些连通块。

   发现最小加边要最大化单点个数，最大加边就要最大化最大连通块点的个数。

   所以从大到小合并，求最小最大加边。

   对于块之间的边最少不加，最多每个点向对面连单向边，也就是 size1×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。

   然后就被我错解肆意水过：

   

   后来直接不改了，反正正解能过不是，觉得只要不太离谱就不会挂。

   

   😅😅😅😥😥😥😶😶😶😇😇😇😅😅😅😥😥😥😶😶😶😇😇😇😅😅😅😥😥😥😶😶😶😇😇😇