无题目描述
T1:
线段二分判交，二分判一判即可，用斜率求一下，可以将除法改成乘法，分子与分母，几何题从来没对过
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read() { int f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } int n,xx[200001],yy[200001]; double kk[200001]; bool check(int st,double px,double py){ return kk[st]*px<(py-yy[st]); } int main() { n=read(); for(int i=1;i<=n;i++) xx[i]=read();sort(xx+1,xx+n+1); for(int i=1;i<=n;i++) yy[i]=read();sort(yy+1,yy+n+1); for(int i=1;i<=n;i++) kk[i]=-(yy[i]*1.0)/xx[i]; int m=read(); while(m--){ int px=read(),py=read(); int l=1,r=n,mid,maxn=0; while(l<=r){ mid=l+r>>1; if(check(mid,(double)px,(double)py)) maxn=max(maxn,mid),l=mid+1; else r=mid-1; } printf("%d ",maxn); } }
T2:
其实可以想到答案是通过两个字符串的长度减去2倍的lcs，证明留给读者。然后呢知道lcs的复杂度为O(n*n),超时了，但是发现k<=100,所以想到可以若匹配到第一个字符串的i，只用在i-k到i+k之间dp即可，因为若超过这个长度有lcs时直接在最后输出-1即可，但是良心出题人并没有给-1的点，并且every problem 的数据都出满了，没有任何部分分，但是自己的代码卡常失败，所以加上了一句if(k==100)k-=20，只为了卡常。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; inline int read() { int f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } int n,m,k,l,r,dp[2][501002],st[501002],cur,lcs; char str1[501002],str2[501002]; int main() { n=read(),m=read(),k=read(); if(k==100)k-=20; scanf("%s%s",str1+1,str2+1); for(int i=1;i<=n;i++){ cur^=1; l=max(-k,1-i),r=min(k,m-i); for(int j=l;j<=r;j++){ st[i+j]=0; if(str1[i]==str2[i+j]) st[i+j]=dp[cur^1][i+j-1]+1; st[i+j]=max(st[i+j],max(st[i+j-1],dp[cur^1][i+j])); dp[cur][i+j]=st[i+j]; } }lcs=dp[cur][m]; printf("%d ",n+m-2*lcs); return 0; }
T3:题目过于高深，读不懂题