20220906三道模拟题
第一道没有什么技术含量,也没有什么算法,只要注意不出一些小失误就可以了。
第二题看到数据范围之后开始犯难,感觉想到的几种写法都无法拿到满分,其中有想到二分的正解思路,但因为没想明白如何打开区间所以最终沉没了。
正解就是二分第k个数的值,看小于它的数的个数是否小于k-1(此时这个数有可能是第k个数,因为相同的数可能有很多个),然后继续二分。(其实这个思路还是很好想的)
第三题花了很长时间理解题意。首先就是要缩点,缩点后就变成了一个有向无环图,那么答案就是在这个修改过的图上找最长链(拓扑排序更新最长链长度和个数)。
三道题写完感觉其实难度还好,只是模拟时自己还是比较急,也不是比较稳,代码水平也不是很强,所以稍稍翻车。
第二题code:
#include<bits/stdc++.h> using namespace std; const int N=1e5+1; struct node{ int l, r; friend bool operator < (node A,node B) { if(A.l==B.l) return A.r>B.r; return A.l<B.l; } }a[N]; int n,k; bool check(int x){ int cnt=0; for(int i=1;i<=n;i++){ if (a[i].l<=x) cnt+=min(x,a[i].r)-a[i].l+1; } return cnt>=k; } int main() { freopen("thekth.in","r",stdin); freopen("thekth.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&a[i].l,&a[i].r); } scanf("%d",&k); int l=-1e9,r=1e9,ans=0; while(l<=r){ int mid=(l+r)>>1; if(check(mid)){ ans=mid; r=mid-1; } else l=mid+1; } printf("%d\n",ans); return 0; }标签:总结,node,return,int,个数,20220906,mid From: https://www.cnblogs.com/LZMiiu/p/16663994.html