2024初三年前集训测试3
其实题还行。
-
夕景昨日（T1）：
只要有不重合两段和相等，就可以分别取反
考虑最多构造 20 个，使其（按 \(2^0,2^1...2^n\) 构造最优）。
所以小于 20 暴力，大于 20 YES 即可
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; int n,a[N],c[N],ans; mt19937 rnd(time(0)); map<int,bool> ck; inline bool check(){ int sum=0; For(i,1,n,1) if(c[i]) sum+=a[i]; if(ck[sum]==1) return 1; ck[sum]=1; return 0; } void dfs(int t){ if(t>n){ if(check()) ans=1; }else{ c[t]=1;dfs(t+1); c[t]=0;dfs(t+1); } } int main(){ scanf("%d",&n); For(i,1,n,1) scanf("%d",a+i); if(n<=20){ dfs(1); puts((ans)?"Yes":"No"); }else puts("Yes"); } -
透明答案（T2）：
打表找规律，在 \(n\equiv 1 \pmod 3\) 时 \(BOB\)，否则 \(Ayano\)
CODE
#include<bits/stdc++.h> using namespace std; const int N=1003; int dp[N][N][3],n; bool dfs(int x,int y,int t){ if(dp[x][y][t]!=-1) return dp[x][y][t]; dp[x][y][t]=0; if (t==2){ if(x>0) dp[x][y][t]=(!dfs(x-1,y+1,0)||dp[x][y][t]); dp[x][y][t]=(!dfs(x+1,y,0)||!dfs(x,y,0)); }else{ if(y>0) dp[x][y][t]=(!dfs(x,y-1,t+1)||!dfs(x+1,y-1,t+1)||dp[x][y][t]); if(x>0) dp[x][y][t]=(!dfs(x-1,y,t+1)||dp[x][y][t]); } return dp[x][y][t]; } int main(){ #ifndef ONLINE_JUDGE freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif memset(dp,-1,sizeof dp),dp[0][0][0]=dp[0][0][1]=dp[0][0][2]=0; scanf("%d",&n); puts(!(dfs(0,n-1,0))?"Ayano":"Bob"); } -
界外科学（T3）
数据被 D 的最惨的一集。不能说是水，只能说和没有一样。甚至直接输出 \(b_i\) 的和就可过。meet in middle
用 trie 树合并即可。
巨难调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=50,R=3e5+4; const llt INF=0x3f3f3f3f3f3f3f3f; int n,m,a[2][N],b[2][N],p[2],cnt[2]; llt ans=-INF; bool ls[N]; namespace IO{ int READ_NONPARAMETRIC_INIT; 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> inline T read(T &x=READ_NONPARAMETRIC_INIT){ 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<typename T,typename... Args> inline void read(T& x,Args&... args){read(x);read(args...);} inline void write(const char c){putchar(c);} inline void write(const 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(' ');} inline void Write(const char c){write(c);if(c!='\n') putchar(' ');} inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') 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; struct E{int ox;llt sm;}qa[2][R]; void dfs(int id,int t){ if(t>p[id]){ int ox=0; llt sum=0; For(i,1,p[id],1) if(ls[i]==1) ox^=a[id][i],sum+=b[id][i]; qa[id][++cnt[id]]={ox,sum}; }else{ ls[t]=0; dfs(id,t+1); ls[t]=1; dfs(id,t+1); } } class TRIE{ private: static const int T=40; int t[R*N][3],tot_=1; llt ma[R*N]; int f[N],cm[N]; llt get(int rt,int i,int nw){ if(!i) return ma[rt]; else if(!rt||(f[i]^nw)>cm[i]) {return -INF;} else if((f[i]^nw)==cm[i]) return max(get(t[rt][0],i-1,0),get(t[rt][1],i-1,1)); else return ma[rt]; } public: TRIE(){For(i,0,N-1,1) ma[i]=-INF;} inline void Fj(int x,int *a){For(i,1,T,1) a[i]=x%2,x/=2;} inline void In_m(int x){Fj(x,cm);} inline void Add(int x,llt v){ Fj(x,f+1);int rt=1; For_(i,T,0,1){ ma[rt]=max(ma[rt],v); if(!t[rt][f[i]]) t[rt][f[i]]=++tot_; rt=t[rt][f[i]]; } } inline llt Get(int x){Fj(x,f);return get(1,T,0);} }tr; int main(){ #ifndef ONLINE_JUDGE freopen("in_out/in.in","r",stdin); freopen("in_out/out.out","w",stdout); #endif int n;read(n,m); p[0]=n/2,p[1]=n-p[0]; For(i,1,p[0],1) read(a[0][i]); For(i,1,p[1],1) read(a[1][i]); For(i,1,p[0],1) read(b[0][i]); For(i,1,p[1],1) read(b[1][i]); dfs(0,1),dfs(1,1); tr.In_m(m); For(i,1,cnt[0],1) tr.Add(qa[0][i].ox,qa[0][i].sm); int a; For(i,1,cnt[1],1) ans=max(ans,qa[1][i].sm+(a=tr.Get(qa[1][i].ox))); write(ans); } -
回忆补时（T4）
100 pts 李超线段树，不会没改。
60 pts 直接枚举两遍最大（最小）贪心即可。
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; const llt INF=0x3f3f3f3f3f3f3f3f; int n,q; llt ma[N],mi[N]; struct FAC{ llt k,b; inline void Rd(){scanf("%lld%lld",&k,&b);} inline llt T(llt x){return 1ll*x*k+b;} }c[N]; int main(){ scanf("%d",&n); For(i,1,n,1) c[i].Rd(); scanf("%d",&q); For(i,1,q,1){ llt x;scanf("%lld",&x); llt lma=-INF,lmi=INF,ans=-INF,pos; For(i,1,n,1) if(c[i].T(x)>lma) lma=c[i].T(x),pos=i; For(i,1,n,1) if(pos!=i) ma[i]=lma; ma[pos]=-INF; For(i,1,n,1) if(i!=pos&&c[i].T(x)>ma[pos]) ma[pos]=c[i].T(x); For(i,1,n,1) if(c[i].T(x)<lmi) lmi=c[i].T(x),pos=i; For(i,1,n,1) if(pos!=i) mi[i]=lmi; mi[pos]=INF; For(i,1,n,1) if(i!=pos&&c[i].T(x)<mi[pos]) mi[pos]=c[i].T(x); For(i,1,n,1) ans=max({ans,c[i].T(ma[i]),c[i].T(mi[i])}); printf("%lld\n",ans); } }
我怎么越写越短