本文共 4786 字，大约阅读时间需要 15 分钟。

好不太容易AK，不能不写题解。

A-第k小数

做法：nth_element的应用，去年寒假牛客训练营出过一次。

#pragma GCC optimize(2)#include
   
    #define ll long long#define maxn 1005#define inf 1e9#define pb push_back#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)using namespace std;inline ll read(){	ll x=0,w=1; char c=getchar();	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}	return w==1?x:-x;}const int N=5e6+10;int a[N],n,k;int main(){    int _;cin>>_;while(_--)    {        n=read(),k=read();        rep(i,0,n-1) a[i]=read();        nth_element(a,a+k-1,a+n);        printf("%d\n",a[k-1]);    }}
   

B-不平行的直线

做法:将所有直线斜率求出，然后去重即可。

#pragma GCC optimize(2)#include
   
    #define ll long long#define maxn 1005#define inf 1e9#define pb push_back#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)using namespace std;inline ll read(){	ll x=0,w=1; char c=getchar();	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}	return w==1?x:-x;}int gcd(int a,int b) { return b?gcd(b,a%b):a;}vector
    
     
       >G;int n;const int N=2e2+10;int x[N],y[N];int main(){    n=read();    rep(i,1,n) x[i]=read(),y[i]=read();    rep(i,1,n)    {        rep(j,i+1,n){            int fz=y[i]-y[j],fm=x[i]-x[j];            int gc=gcd(fz,fm);            fz/=gc,fm/=gc;            if(fm<0) fz=-fz,fm=-fm;            G.push_back(make_pair(fz,fm));        }    }    sort(G.begin(),G.end());    G.erase(unique(G.begin(),G.end()),G.end());    printf("%d\n",G.size());}
     
    
   

C-丢手绢

做法:将原数组扩大两倍，然后同时枚举起点、终点，二分找尽量对两端最远的点即可。

#pragma GCC optimize(2)#include
   
    #define ll long long#define maxn 1005#define inf 1e9#define pb push_back#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)using namespace std; inline ll read(){    ll x=0,w=1; char c=getchar();    while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}    while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}    return w==1?x:-x;} const int N=2e5+10;int n;ll a[N],sum[N],x[N];int main(){    n=read();    //++n;    rep(i,1,n) a[i]=read();    for(int i=1,j=n+1;i<=n;++i,++j) a[j]=a[i];    //rep(i,1,2*n) printf("%d ",a[i]);    //puts("");//    //n=2*n;    rep(i,1,2*n) sum[i]=sum[i-1]+a[i];    int id1=1,id2=n+1;    ll ans=0;    while(id1<=n)    {        int l=id1,r=id2-1;        while(l<=r)        {            int mid=l+r>>1;            ll t1=sum[id2-1]-sum[mid];            ll t2=sum[mid]-sum[id1-1];            //printf("id1:%d id2:%d mid:%d t1:%lld t2:%lld\n",id1,id2,mid,t1,t2);             if(t1>t2){                ans=max(ans,t2);                l=mid+1;            }            else{                r=mid-1;                ans=max(ans,t1);            }        }        ++id1,++id2;    }    printf("%lld\n",ans);}
   

D-二分

做法：枚举当前这个人说的是真话。如果是+ 那就定这个答案数 是 v-1.

如果当前这个人是-  那就定这个答案数 是 v+1 

已经知道了最初的数了，就对+号和-号分开判断  简单的二分判断有多少个是正确的即可。

#pragma GCC optimize(2)#include
   
    #define ll long long#define maxn 1005#define inf 1e9#define pb push_back#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)using namespace std;inline ll read(){    ll x=0,w=1; char c=getchar();    while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}    while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}    return w==1?x:-x;}const int N=1e5+10;int X[N],Y[N],lx,ly,n;map
    
     mp;struct node{    int v;    char s[2];}a[N];int cal(int v){    int res=mp[v],id;    id=upper_bound(X+1,X+1+lx,v)-X;    //printf("v:%d id:%d %d\n",v,id,lx-id+1);    res+=lx-id+1;    id=lower_bound(Y+1,Y+1+ly,v)-Y;    //printf("v:%d id:%d %d\n",v,id,id-1);    res+=id-1;    //puts("");    return res;}int main(){    n=read();    rep(i,1,n)    {        a[i].v=read();cin>>a[i].s;        if(a[i].s[0]=='.')mp[a[i].v]++;        else if(a[i].s[0]=='+') X[++lx]=a[i].v;        else if(a[i].s[0]=='-') Y[++ly]=a[i].v;    }    sort(X+1,X+1+lx);    sort(Y+1,Y+1+ly);    int ans=max(ans,max(lx,ly));    rep(i,1,n)    {        int res;        if(a[i].s[0]=='.') res=cal(a[i].v);        else if(a[i].s[0]=='+') res=cal(a[i].v-1);        else res=cal(a[i].v+1);        ans=max(ans,res);        //printf("v:%d res:%d\n",a[i].v,res);    }    printf("%d\n",ans);}/*50 +1 -2 -3 -4 +*/
    
   

E-交换

做法：置换群的水题了。

#pragma GCC optimize(2)#include
   
    #define ll long long#define maxn 1005#define inf 1e9#define pb push_back#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)using namespace std;inline ll read(){	ll x=0,w=1; char c=getchar();	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}	return w==1?x:-x;}const int N=1e5+10;int n,fa[N],vis[N];struct node{    int v,id;}a[N];bool cmp(node a,node b){    return a.v
   

转载地址：https://ccsudeer.blog.csdn.net/article/details/106364091 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！