2025省选模拟8
题目来源： 2024省选联测10
\(T1\) HZTG5836. 小幸运 \(18pts\)
-
将坐标扩大 \(2\) 倍后答案只可能为整数，证明显然。
-
二分答案， \(check\) 时考虑 \(2-SAT\) 。
-
将一个点可能构成的等腰直角三角形划分成如下四个部分，最终仅能选择相邻的两个。不妨两条对角线上的取值分开考虑，然后进行合并。
-
现在就只需要解决判断两个三角形是否相交的问题了。
-
容易想到的思路是根据两个三角形相交必然有两条边相交，枚举 \(3^{2}\) 种匹配情况进行判断某两条线段是否有交点，需要特判斜率不存在的情况。因本题 相交 定义的特殊性，需要适当调整边界是否取到的情况。
点击查看代码
const ll dx[4][2]={{1,0},{1,0},{-1,0},{-1,0}},dy[4][2]={{0,-1},{0,1},{0,-1},{0,1}}; ll dfn[510],low[510],ins[510],col[510],x[2][3],y[2][3],tot,scc_cnt,n,w,h; pair<ll,ll>a[510]; stack<ll>s; vector<ll>e[510]; void add(ll u,ll v) { e[u].push_back(v); } void tarjan(ll x) { tot++; dfn[x]=low[x]=tot; ins[x]=1; s.push(x); for(ll i=0;i<e[x].size();i++) { if(dfn[e[x][i]]==0) { tarjan(e[x][i]); low[x]=min(low[x],low[e[x][i]]); } else { if(ins[e[x][i]]==1) { low[x]=min(low[x],dfn[e[x][i]]); } } } if(dfn[x]==low[x]) { scc_cnt++; ll tmp=0; while(x!=tmp) { tmp=s.top(); ins[tmp]=0; col[tmp]=scc_cnt; s.pop(); } } } bool out_of_bounds(ll x,ll y,ll op,ll mid) { for(ll i=0;i<=1;i++) { if(x+dx[op][i]*mid<0||x+dx[op][i]*mid>w||y+dy[op][i]*mid<0||y+dy[op][i]*mid>h) return true; } return false; } bool line_cross(ll x1,ll y1,ll x2,ll y2,ll _x1,ll _y1,ll _x2,ll _y2) { if(x1==x2&&_x1==_x2) { if(x1!=_x1) return false; if(y1>y2) swap(y1,y2); if(_y1>_y2) swap(_y1,_y2); return ((y1<_y2&&_y2<y2)||(y1<_y1&&_y1<y2)); } if(x1==x2||_x1==_x2) { if(_x1==_x2) { swap(x1,_x1); swap(y1,_y1); swap(x2,_x2); swap(y2,_y2); } double _k=1.0*(_y2-_y1)/(_x2-_x1),_b=_y1-_x1*_k,y=_k*x1+_b; return (_x1<x1&&x1<_x2&&min(y1,y2)<y&&y<max(y1,y2)); } double k=1.0*(y2-y1)/(x2-x1),b=y1-x1*k,_k=1.0*(_y2-_y1)/(_x2-_x1),_b=_y1-_x1*_k; if(k==_k) return false; double x=(_b-b)/(k-_k); return (min(x1,x2)<x&&x<max(x1,x2)&&min(_x1,_x2)<x&&x<max(_x1,_x2)); } bool triangle_cross(ll x1,ll y1,ll op1,ll x2,ll y2,ll op2,ll mid) { for(ll i=0;i<=1;i++) { x[0][i]=x1+dx[op1][i]*mid; y[0][i]=y1+dy[op1][i]*mid; } x[0][2]=x1; y[0][2]=y1; for(ll i=0;i<=1;i++) { x[1][i]=x2+dx[op2][i]*mid; y[1][i]=y2+dy[op2][i]*mid; } x[1][2]=x2; y[1][2]=y2; for(ll i=0;i<=2;i++) { for(ll j=0;j<=2;j++) { if(line_cross(x[0][i],y[0][i],x[0][(i+1)%3],y[0][(i+1)%3], x[1][j],y[1][j],x[1][(j+1)%3],y[1][(j+1)%3])==true) { return true; } } } return false; } bool check(ll mid) { for(ll i=1;i<=8*n;i++) e[i].clear(); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(ins,0,sizeof(ins)); memset(col,0,sizeof(col)); tot=scc_cnt=0; while(s.empty()==0) s.pop(); for(ll i=1;i<=n;i++) { for(ll j=0;j<=3;j++) { add(i+j*n,i+(3-j)*n+4*n); add(i+j*n+4*n,i+(3-j)*n); if(out_of_bounds(a[i].first,a[i].second,j,mid)==true) add(i+j*n,i+j*n+4*n); } } for(ll i=1;i<=n;i++) { for(ll j=i+1;j<=n;j++) { for(ll u=0;u<=3;u++) { for(ll v=0;v<=3;v++) { if(triangle_cross(a[i].first,a[i].second,u, a[j].first,a[j].second,v,mid)==true) { add(i+u*n,j+v*n+4*n); add(j+v*n,i+u*n+4*n); } } } } } for(ll i=1;i<=8*n;i++) if(dfn[i]==0) tarjan(i); for(ll i=1;i<=4*n;i++) if(col[i]==col[i+4*n]) return false; return true; } int main() { #define Isaac #ifdef Isaac freopen("lucky.in","r",stdin); freopen("lucky.out","w",stdout); #endif ll l=0,r=1000000000,ans=0,mid,i; cin>>n>>w>>h; w*=2; h*=2; for(i=1;i<=n;i++) { cin>>a[i].first; a[i].first*=2; } for(i=1;i<=n;i++) { cin>>a[i].second; a[i].second*=2; } while(l<=r) { mid=(l+r)/2; if(check(mid)==true) { ans=mid; l=mid+1; } else { r=mid-1; } } cout<<ans<<endl; return 0; }
\(T2\) HZTG5837. 山河入梦来 \(20pts\)
-
部分分
- \(20pts\) ：枚举全排列。
点击查看代码
int l[100010],r[100010],p[100010],s[2]; int main() { #define Isaac #ifdef Isaac freopen("river.in","r",stdin); freopen("river.out","w",stdout); #endif int t,n,op,i,j; scanf("%d",&t); for(;t>=1;t--) { s[0]=s[1]=0; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]); for(i=1;i<=n;i++) p[i]=i; do { for(i=1;i<=n;i++) { if(!(l[i]<=p[i]&&p[i]<=r[i])) break; } if(i==n+1) { op=0; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { if(p[j]<p[i]) op^=1; } } s[op]++; } }while(next_permutation(p+1,p+1+n)); if(s[0]==s[1]) printf("tie\n"); if(s[0]>s[1]) printf("pp\n"); if(s[0]<s[1]) printf("xx\n"); } return 0; } -
正解
- 定义 \(a_{i}=[l_{i},r_{i}]\) 后只需要求出行列式的正负性即可，但我不会行列式。
- 对于第 \(i,j(i \ne j)\) 行，当 \(p_{i},p_{j} \in (\{ l_{i},r_{i} \} \bigcap \{ l_{j},r_{j} \})\) 时交换 \(p_{i},p_{j}\) 至多增加 \(1\) /减少 \(1\) 个逆序对，即只会改变逆序对的奇偶性。此时这种选择对最终结果的取值没有影响。
- 证明考虑 \((i,j)\) 内元素产生的逆序对数量不变，分讨大小情况即可。
- 观察到对于同一个左端点 \(l\) 的若干个右端点 \(r_{1} \le r_{2} \le \dots \le r_{k}\) ，类似上述分析得到只有 \(\begin{cases} p_{r_{1}}=l \\ \forall i \in [2,k],r_{1}<p_{r_{i}} \le r_{i} \end{cases}\) 时才可能对答案产生影响，否则可以与上面的进行交换从而对最终结果不产生影响。使用可并堆加速堆的合并。
- 最后对构造出来的 \(\{ p \}\) 再求一遍逆序对，判断奇偶性即可。
- 构造 \(\{ p \}\) 的过程本质上是在顺次考虑 \(i\) 填到何处时才可能对答案产生影响，而这本身就具有唯一性。
- 更新过程中若 \(k=0 \lor r_{2}=r_{1}\) 时输出
tie。前者是因为无法构造出一种合法的 \(\{ p \}\) ，后者分析同上。
点击查看代码
int p[100010]; struct BIT { int c[100010]; int lowbit(int x) { return (x&(-x)); } void clear() { memset(c,0,sizeof(c)); } void add(int n,int x,int val) { for(int i=x;i<=n;i+=lowbit(i)) c[i]+=val; } int getsum(int x) { int ans=0; for(int i=x;i>=1;i-=lowbit(i)) ans+=c[i]; return ans; } }B; struct Heap { int root[100010]; struct Leftist_Tree { int ls,rs,val,d; }tree[100010]; #define lson(rt) (tree[rt].ls) #define rson(rt) (tree[rt].rs) void clear() { memset(root,0,sizeof(root)); memset(tree,0,sizeof(tree)); } void build_rt(int rt,int val) { lson(rt)=rson(rt)=0; tree[rt].val=val; tree[rt].d=1; } int merge(int rt1,int rt2) { if(rt1==0||rt2==0) return rt1+rt2; if(tree[rt1].val>tree[rt2].val) swap(rt1,rt2); rson(rt1)=merge(rson(rt1),rt2); if(tree[lson(rt1)].d<tree[rson(rt1)].d) swap(lson(rt1),rson(rt1)); tree[rt1].d=tree[rson(rt1)].d+1; return rt1; } void del(int &rt) { rt=merge(lson(rt),rson(rt)); } int query(int rt) { return tree[rt].val; } }T; int main() { #define Isaac #ifdef Isaac freopen("river.in","r",stdin); freopen("river.out","w",stdout); #endif int t,n,l,r,ans,flag,i; scanf("%d",&t); for(;t>=1;t--) { ans=flag=0; B.clear(); T.clear(); scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d%d",&l,&r); p[i]=i; T.build_rt(i,r); T.root[l]=T.merge(T.root[l],i); } for(i=1;i<=n&&flag==0;i++) { if(T.root[i]==0) flag=1; r=T.query(T.root[i]); p[T.root[i]]=i; T.del(T.root[i]); if(T.root[i]!=0&&T.query(T.root[i])==r) flag=1; T.root[r+1]=T.merge(T.root[r+1],T.root[i]); } for(i=n;i>=1;i--) { ans=(ans+B.getsum(p[i]-1))%2; B.add(n,p[i],1); } if(flag==1) printf("tie\n"); else if(ans%2==0) printf("pp\n"); else printf("xx\n"); } return 0; }
\(T3\) HZTG5838. 遇见 \(0pts\)
总结
- \(T1\) 以为只能朝上、朝右放，还口胡了个判断两个三角形相交时只取三个端点判是否在另一个三角形内部。在过掉大样例后以为直接切了，遂没再管。