初中信息奥赛模拟测试
终于是肯给 hzoi2024 整场模拟赛了。
题其实并不是很难。
但很有价值。
-
ZEW 的游戏 (T2)
显然是直接求斜率。
注意判 \(0\)。
因为绝对值小于 \(1000\)，可以直接用小数。
正经应该是写个分数存，也不难实现。
小数：
CODE
#include<bits/stdc++.h> using namespace std; const int N=405; int n; int cx[N],cy[N]; unordered_set<double> c; inline double get(int xa,int ya,int xb,int yb){ if(xa-xb==0) return 10000000000.0; return (ya-yb)*1.0/(xa-xb); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&cx[i],&cy[i]); for(int j=1;j<i;j++) c.insert(get(cx[i],cy[i],cx[j],cy[j])); } cout<<c.size(); }分数：
CODE
#include<bits/stdc++.h> using namespace std; typedef long long llt; typedef unsigned long long ull; #define For(i,a,b,c) for(register int $L=a,$R=b,$C=c,$D=(0<=$C)-($C<0),i=$L;i*$D<=$R*$D;i+=$C) const int N=202,INF=0x3f3f3f3f; set<pair<int,int> > c; int cx[N],cy[N]; 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> inline void read(T &x){ 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; } } 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; inline pair<int,int> get(int xa,int ya,int xb,int yb){ int x=xa-xb,y=ya-yb,gd=__gcd(x,y); if(x==0) return make_pair(INF,1); return make_pair(y/gd,x/gd); } int main(){ #ifndef ONLINE_JUDGE freopen("in_out/in.in","r",stdin); freopen("in_out/out.out","w",stdout); #endif int n;read(n); For(i,1,n,1){ read(cx[i],cy[i]); For(j,1,i-1,1) c.insert(get(cx[i],cy[i],cx[j],cy[j])); } cout<<c.size(); } -
ZEW 学分块 (T3)
可以二分答案。
虽然理论复杂度爆炸，但实际没卡到。
正经做是双指针。
枚举二三块的边界，贪心维护一下一二块。
前缀和要开
longlong实际上也没卡CODE
#include<bits/stdc++.h> using namespace std; const int N=5e6+5; int n,cu[N]; long long qsum[N],ans=0x3f3f3f3f; inline long long Dis(int x,int y){ return qsum[y]-qsum[x]; } signed main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",cu+i),qsum[i]=qsum[i-1]+cu[i]; int p=0; for(int i=1;i<=n;i++){ while(p<=i&&abs(Dis(p,i)-Dis(0,p))>=abs(Dis(p+1,i)-Dis(0,p+1))) p++; ans=min(ans,max(Dis(0,p),max(Dis(p,i),Dis(i,n)))); } printf("%lld",ans); } -
ZEW 玩 thd (T4)
背包。
显然是在最后补刀。
考虑在第 \(i\) 个时人最多攻击几下，为容量。
最少补的下数为代价。
因为最后一下打掉 \(i\) 的话会使塔少攻击一次。
所以代价加一。
转移显然。
因为容量是不确定的，最后要求 \(max\)，因为可能没有转移到。
CODE
#include<bits/stdc++.h> using namespace std; typedef long long llt; typedef unsigned long long ull; #define For(i,a,b,c) for(register int $L=a,$R=b,$C=c,$D=(0<=$C)-($C<0),i=$L;i*$D<=$R*$D;i+=$C) const int N=202,W=2e5+3; int dp[W],p,q,n,w[N],v[N],wt[N],t; 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> inline void read(T &x){ 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; } } 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; int main(){ #ifndef ONLINE_JUDGE freopen("in_out/in.in","r",stdin); freopen("in_out/out.out","w",stdout); #endif read(p,q,n); wt[0]=1; For(i,1,n,1){ int h; read(h,v[i]);h--; wt[i]=wt[i-1]+(h/q+1); w[i]=(h%q/p+2); } For(i,1,n,1) For(j,wt[i],w[i],-1) dp[j]=max(dp[j],dp[min(wt[i-1],j-w[i])]+v[i]); int ans=0; For(i,1,wt[n],1) ans=max(ans,dp[i]); printf("%d",ans); }