2024初三集训模拟测试2
T1 大模拟磨了 1 hour,T2 想了 45 mins 弃了(其实就差一点),T3 暴力,T4 暴力都没打。
策略有问题。
-
T1 小P的2048
本来是暑假集训原题。
\(Shadow\) 以 41 秒的成绩直接贺过,
甚至估分于是 miaomiao 来找,喜提换题。
所以 \(Shadow\) 薄纱了。
\(\sqrt{} 8\) 大模拟。
数据好像有同一个点重复赋值情况,直接覆盖即可。
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=10; int n,m; llt a[N][N],ans=0; queue<llt> c[N],ls; inline void Debug(){ For(i,1,n,1){ For(j,1,n,1) printf("%lld ",a[i][j]); puts(""); } } inline bool Mge(){ bool pd=0; For(i,1,n,1){ int nw=0; while(!c[i].empty()){ int x=c[i].front();c[i].pop(); if(!nw) nw=x; else{ if(nw==x) ls.push(nw*2),ans+=nw*2,nw=0,pd=1; else ls.push(nw),nw=x; } } if(nw) ls.push(nw); while(!ls.empty()) c[i].push(ls.front()),ls.pop(); } return pd; } int main(){ int xx1,yy1,vv1,xx2,yy2,vv2; scanf("%d%d%d%d%d%d%d%d",&n,&m,&xx1,&yy1,&vv1,&xx2,&yy2,&vv2); a[xx1][yy1]=vv1,a[xx2][yy2]=vv2; For(i,1,n,1) a[i][0]=a[0][i]=a[i][n+1]=a[n+1][i]=1; int tt=0; while(tt<m){ int d,k;llt v;scanf("%d%d%lld",&d,&k,&v); bool pd=0; if(d==0){ For(j,1,n,1) For(i,1,n,1){ if(a[i][j]) c[j].push(a[i][j]); if(!a[i-1][j]&&a[i][j]) pd=1; } For(j,1,n,1) For_(i,n,1,1) a[i][j]=0; if(Mge()) pd=1; For(j,1,n,1){ int i=0; while(!c[j].empty()) a[++i][j]=c[j].front(),c[j].pop(); } }else if(d==1){ For(j,1,n,1) For_(i,n,1,1){ if(a[i][j]) c[j].push(a[i][j]); if(!a[i+1][j]&&a[i][j]) pd=1; } For(j,1,n,1) For_(i,n,1,1) a[i][j]=0; if(Mge()) pd=1; For(j,1,n,1){ int i=n+1; while(!c[j].empty()) a[--i][j]=c[j].front(),c[j].pop(); } }else if(d==2){ For(i,1,n,1) For(j,1,n,1){ if(a[i][j]) c[i].push(a[i][j]); if(!a[i][j-1]&&a[i][j]) pd=1; } For(j,1,n,1) For_(i,n,1,1) a[i][j]=0; if(Mge()) pd=1; For(i,1,n,1){ int j=0; while(!c[i].empty()) a[i][++j]=c[i].front(),c[i].pop(); } }else{ For(i,1,n,1) For_(j,n,1,1){ if(a[i][j]) c[i].push(a[i][j]); if(!a[i][j+1]&&a[i][j]) pd=1; } For(j,1,n,1) For_(i,n,1,1) a[i][j]=0; if(Mge()) pd=1; For(i,1,n,1){ int j=n+1; while(!c[i].empty()) a[i][--j]=c[i].front(),c[i].pop(); } } if(!pd) break; int cnt=0; For(i,1,n,1) For(j,1,n,1) if(!a[i][j]) cnt++; cnt=1+(k%cnt); For(i,1,n,1) For(j,1,n,1) if(!a[i][j]){cnt--;if(!cnt) a[i][j]=v;} tt++; } printf("%d\n%lld",tt,ans); }
-
T2 子集
\(len=\frac{n}{k}\) 为偶数时显然蛇形构造即可。
考虑为奇数。
前 \(len-3\) 个像偶数时一样构造。
倒第三排顺序构造。
倒第二排从中间开始到最后,再从开始到中间。
可以证明这样构造和是一段连续的数,最后一排补全即可。
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+4; int t,n,k; queue<int> ans[N]; namespace IO{ template<class T> inline void write(T x){ static T st[45];T top=0;if(x<0)x=-x,putchar('-'); do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48); } template<class T> T READ_NONPARAMETRIC_INIT; template<class 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*10+(s^48),s=getchar();} return (pd?(x=-x):x); } } namespace IO{ char NL_C; double NL_F; long double NL_LF; 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<int MAXSIZE=INT_MAX> inline int read(string &c){ c.clear();char s=getchar();int pos=0;while(s<33||s>126) s=getchar(); while(s>=33&&s<=126&&pos<MAXSIZE) c.push_back(s),s=getchar(),pos++;return pos; } inline double read(double &x){scanf("%lf",&x);return x;} inline long double read(long double &x){scanf("%Lf",&x);return x;} template<class T,class... Args> inline void read(T& x,Args&... args){read(x);read(args...);} inline void write(char c){putchar(c);} inline void write(char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);} inline void write(string &c){int len=c.size();For(i,0,len-1,1) putchar(c[i]);} inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);} template<int PRECISION=6> inline void write(double x){printf("%.*lf",PRECISION,x);} template<int PRECISION=6> inline void write(long double x){printf("%.*Lf",PRECISION,x);} template<class T> inline void Write(T x){write(x),putchar(' ');} inline void Write(char c){write(c);if(c!='\n') putchar(' ');} inline void Write(char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');} inline void Write(string &c){write(c);if(c[c.size()-1]!='\n') putchar(' ');} inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');} template<class T,class... Args> inline void write(T x,Args... args){write(x);write(args...);} template<class T,class... Args> inline void Write(T x,Args... args){Write(x);Write(args...);} } using namespace IO; int main(){ #ifndef ONLINE_JUDGE freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif read(t); while(t--){ read(n,k); int len=n/k; if(n==1){puts("Yes\n1");} else if(len==1||(n%2==0&&len%2)) puts("No"); else if(len%2==0){ puts("Yes"); int x=1; while(x<=n){ For(i,1,k,1) ans[i].push(x++); For_(i,k,1,1) ans[i].push(x++); } For(i,1,k,1){ while(!ans[i].empty()) Write(ans[i].front()),ans[i].pop(); puts(""); } }else{ puts("Yes"); int x=1; while(x<=n-k*3){ For(i,1,k,1) ans[i].push(x++); For_(i,k,1,1) ans[i].push(x++); } For(i,1,k,1) ans[i].push(x++); int mid=(k+1)/2; For(i,mid+1,k,1) ans[i].push(x++); For(i,1,mid,1) ans[i].push(x++); ans[mid].push(x++); For_(i,mid-1,1,1) ans[mid+i].push(x++),ans[i].push(x++); For(i,1,k,1){ while(!ans[i].empty()) Write(ans[i].front()),ans[i].pop(); puts(""); } } } }
-
T3 混凝土粉末
\(Momo\) 暴力莫名 84pts ,甚至和没卡常主席树同分
考虑将询问转换:
\(1\to n\) 作为第一维。
\(1\to q\) 的时间维作为第二维。
设询问、修改编号为 \(id\)
对于修改: 在 \((l\to r,id)\) 处加 \(h\)。
对于查询: 查询在 \(x\) 位置上 第一个值 \(\ge h\) 的 \(id\)。
可以考虑主席树在线维护,整体二分或扫描线(主席树常数巨大,卡不过去)。
这里讲扫描线。
将询问离线,在扫到 \(l\) 时在 \(id\) 时加 \(h\),在 \(r\) 时减掉。
查询就变成了在 \(1\to id\) 查询最靠左的满足和 \(\ge h\) 的点。
可以树状数组上二分或二分树状数组(虽然差一个 \(\log\) 但其实差不多)
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=2e6+4; int n,q; struct PR{int t;llt h;}; vector<PR> cq[N]; vector<PR> cc[N]; llt ans[N]; namespace IO{ template<class T> inline void write(T x){ static T st[45];T top=0;if(x<0)x=-x,putchar('-'); do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48); } template<class T> T READ_NONPARAMETRIC_INIT; template<class 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*10+(s^48),s=getchar();} return (pd?(x=-x):x); } } namespace IO{ char NL_C; double NL_F; long double NL_LF; 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<int MAXSIZE=INT_MAX> inline int read(string &c){ c.clear();char s=getchar();int pos=0;while(s<33||s>126) s=getchar(); while(s>=33&&s<=126&&pos<MAXSIZE) c.push_back(s),s=getchar(),pos++;return pos; } inline double read(double &x){scanf("%lf",&x);return x;} inline long double read(long double &x){scanf("%Lf",&x);return x;} template<class T,class... Args> inline void read(T& x,Args&... args){read(x);read(args...);} inline void write(char c){putchar(c);} inline void write(char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);} inline void write(string &c){int len=c.size();For(i,0,len-1,1) putchar(c[i]);} inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);} template<int PRECISION=6> inline void write(double x){printf("%.*lf",PRECISION,x);} template<int PRECISION=6> inline void write(long double x){printf("%.*Lf",PRECISION,x);} template<class T> inline void Write(T x){write(x),putchar(' ');} inline void Write(char c){write(c);if(c!='\n') putchar(' ');} inline void Write(char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');} inline void Write(string &c){write(c);if(c[c.size()-1]!='\n') putchar(' ');} inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');} template<class T,class... Args> inline void write(T x,Args... args){write(x);write(args...);} template<class T,class... Args> inline void Write(T x,Args... args){Write(x);Write(args...);} } using namespace IO; namespace BT{ llt a[N]; static int R=1<<20; inline int lowbit(int x){return x&(-x);} inline void Add(int x,llt t){For(i,x,N-2,lowbit(i)) a[i]+=t;} inline int Get(int p,llt t){ int l=1,r=R; while(l<r){ int mid=(l+r)>>1; if(a[mid]>=t) r=mid; else t-=a[mid],l=mid+1; } return (l>p)?0:l; } } int main(){ #ifndef ONLINE_JUDGE freopen("in_out/in.in","r",stdin); freopen("in_out/out.out","w",stdout); #endif read(n,q); memset(ans,-1,sizeof ans); For(i,1,q,1){ if(read()==1){ int l,r;llt h; read(l,r,h); cq[l].push_back(PR{i,h}); cq[r+1].push_back(PR{i,-h}); }else cc[read()].push_back(PR{i,read<llt>()}); } For(k,1,n,1){ for(PR x:cq[k]) BT::Add(x.t,x.h); for(PR x:cc[k]) ans[x.t]=BT::Get(x.t,x.h); } For(i,1,q,1) if(~ans[i]) write(ans[i],'\n'); }
-
T4
其实不难。
考虑与 \(u\) 相连一条边的贡献,会使与这条边直接相连的终点值减小一个数,其他的子节点加一个值。
考虑将其他子节点的值放到 \(u\) 上,最后同一推。
topu 推即可。
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=2e5+4,M=5e5+4,MOD=998244353; int n,m,r,k,sum,pin[N],pout[N],c[N],ans[N]; queue<int> que; namespace IO{ template<class T> inline void write(T x){ static T st[45];T top=0;if(x<0)x=-x,putchar('-'); do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48); } template<class T> T READ_NONPARAMETRIC_INIT; template<class 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*10+(s^48),s=getchar();} return (pd?(x=-x):x); } } namespace IO{ char NL_C; double NL_F; long double NL_LF; 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<int MAXSIZE=INT_MAX> inline int read(string &c){ c.clear();char s=getchar();int pos=0;while(s<33||s>126) s=getchar(); while(s>=33&&s<=126&&pos<MAXSIZE) c.push_back(s),s=getchar(),pos++;return pos; } inline double read(double &x){scanf("%lf",&x);return x;} inline long double read(long double &x){scanf("%Lf",&x);return x;} template<class T,class... Args> inline void read(T& x,Args&... args){read(x);read(args...);} inline void write(char c){putchar(c);} inline void write(char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);} inline void write(string &c){int len=c.size();For(i,0,len-1,1) putchar(c[i]);} inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);} template<int PRECISION=6> inline void write(double x){printf("%.*lf",PRECISION,x);} template<int PRECISION=6> inline void write(long double x){printf("%.*Lf",PRECISION,x);} template<class T> inline void Write(T x){write(x),putchar(' ');} inline void Write(char c){write(c);if(c!='\n') putchar(' ');} inline void Write(char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');} inline void Write(string &c){write(c);if(c[c.size()-1]!='\n') putchar(' ');} inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');} template<class T,class... Args> inline void write(T x,Args... args){write(x);write(args...);} template<class T,class... Args> inline void Write(T x,Args... args){Write(x);Write(args...);} } using namespace IO; namespace TO{ int hd[N],nt[M],to[M],wt[M],tin[N],tout[N],tot; inline void Add(int u,int v,int w){tin[v]++,tout[u]++,to[++tot]=v,nt[tot]=hd[u],hd[u]=tot,wt[tot]=w;} #define For_to(i,u,v) for(int i=TO::hd[u],v=TO::to[i];i;i=TO::nt[i],v=TO::to[i]) inline void Copy(){memcpy(pin,tin,sizeof tin);} } using TO::wt; using TO::tin; using TO::tout; namespace MT{ inline int Fpw(int a,int b){ int ans=1; while(b){ if(b&1) ans=1ll*ans*a%MOD; a=1ll*a*a%MOD,b>>=1; } return ans; } inline int Inv(int x){return Fpw(x,MOD-2);} } using MT::Inv; int main(){ #ifndef ONLINE_JUDGE freopen("in_out/in.in","r",stdin); freopen("in_out/out.out","w",stdout); #endif read(n,m,r,k); For(i,1,k,1){int u,v,a;read(u,v,a),TO::Add(u,v,a),sum=(a+sum)%MOD;} sum=Inv(sum); For(i,1,m,1) que.push(i),c[i]=1; TO::Copy(); while(!que.empty()){ int u=que.front();que.pop(); int tmp=1ll*c[u]*Inv(tout[u])%MOD; For_to(i,u,v){ c[v]=(c[v]+tmp)%MOD,pin[v]--; if(!pin[v]) que.push(v); } } For(i,1,m,1) que.push(i),ans[i]=1; For(u,1,n,1){ int ot=tout[u]; For_to(i,u,v){ int P=1ll*wt[i]*sum%MOD,tmp=1ll*c[u]*Inv(ot)%MOD*P%MOD,res=1ll*c[u]*Inv(ot-1)%MOD*P%MOD; ans[v]=1ll*(ans[v]-1ll*res+MOD)%MOD; ans[u]=1ll*(ans[u]+1ll*ot*(res-tmp+MOD)%MOD)%MOD; } } TO::Copy(); while(!que.empty()){ int u=que.front();que.pop(); int tmp=1ll*ans[u]*Inv(tout[u])%MOD; For_to(i,u,v){ ans[v]=(ans[v]+tmp)%MOD,pin[v]--; if(!pin[v]) que.push(v); } } For(i,n-r+1,n,1) Write(ans[i]); }