A题：
题意：和题目一样，就是求第k小数。
思路：暴力肯定就sort了，不过数据太大，sort也过不了，那么根据快排，我们可以一次性砍掉一半左右的数据，只需要关心第k小数所在的数据范围就好了。后来才知道还有一个nth_element这个神奇的东西，会把第k个数直接放在k的位置。用法：nth_element(first,nth,last);我发现用这个的时候是把数据存放在a[0]-a[n-1]m排序输出k小数的时候输出的是a[k],也就是经过这个函数之后，数据k是放在a[k]位置，而不是a[k-1].下面是我的ac代码和用了element的代码。
1:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=5e6+5;
const LL mod=1e9+7;
inline int read() {
char ch=getchar();int x=0,f=1;
while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int a[maxn];
int c[maxn];
int find(int r,int k) {
if(r==1) {
return a[r];
}
int low=1,high=r;
int num=a[1];
for(int i=2;i<=r;++i) {
if(a[i]<=num) {
c[low++]=a[i];
}
else {
c[high--]=a[i];
}
}
if(low==k) return num;
else if(low<k) {
for(int i=low+1;i<=r;++i) {
a[i-low]=c[i];
}
return find(r-low,k-low);
}
else {
for(int i=1;i<low;++i) {
a[i]=c[i];
}
return find(low-1,k);
}
}
void solve() {
int n,k;
n=read();
k=read();
for(int i=1;i<=n;++i) {
a[i]=read();
}
cout<<find(n,k)<<"\n";
}
int main() {
// cout<<"Accepted!\n";
int t;
cin>>t;
while(t--) {
solve();
}
return 0;
}2:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=5e6+100;
const LL mod=1e9+7;
int read() {
char ch=getchar();int x=0,f=1;
while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int a[maxn];
int main() {
// cout<<"Accepted!\n";
int t;
cin>>t;
while(t--) {
int n,k;
n=read();
k=read();
for(int i=0;i<n;++i) {
a[i]=read();
}
// cout<<k<<"\n";
nth_element(a,a+k,a+n);
cout<<a[k]<<"\n";
}
return 0;
}B题：
题意：给n个点，问最多选出多少条直线不能平行也不重合。
思路：我刚开始以为一个点用过就不能用了，后来才知道可以重复使用。既然这样那就直接暴力检查任意两条直线就好了，那样就O( )，我们稍微优化一下，运用set的性质，我们把一条直线的斜率放进去就很好的去除了重合和平行，那么还有一个精度问题，我们就不直接使用斜率，而是用分母分子这样一组数来表示，同时我们规定分母一定为正。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const LL mod=1e9+7;
int read() {
char ch=getchar();int x=0,f=1;
while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int gcd_(int a,int b) {return b==0?a:gcd_(b,a%b);}
LL fpow(LL a,LL b) {
LL res=1;
while(b) {
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
int a[205],b[205];
set<pair<int,int> > se;
int main() {
// cout<<"Accepted!\n"
int n;
cin>>n;
for(int i=1;i<=n;++i) {
cin>>a[i]>>b[i];
}
int flag=0;
for(int i=1;i<n;++i) {
for(int j=i+1;j<=n;++j) {
if(b[i]==b[j] ) {
flag=1;
continue;
}
int X=a[i]-a[j],Y=b[i]-b[j];
if(X<0) X=-X,Y=-Y;
int Z=gcd_(X,Y);
X/=Z;
Y/=Z;
se.insert(make_pair(X,Y));
}
}
cout<<se.size()+flag;
return 0;
}
C题：
题意：这个没啥可说的。
思路：不过给的样例数据多了3，，，。直接三分就好了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
int a[maxn];
int s[maxn];
int dis(int x,int y) {
if(x==y) return 0;
return min(abs(s[x]-s[y]),a[1]-abs(s[x]-s[y]));
}
int main() {
// cout<<"Accepted!\n";
int n;
cin>>n;
for(int i=2;i<=n;++i) {
cin>>a[i];
s[i]=s[i-1]+a[i];
}
cin>>a[1];
a[1]+=s[n];
int ans=0;
for(int i=1;i<=n;++i) {
int l=1,r=n;
while(l+1<r) {
int m1=(l+r)>>1,m2=(m1+r)>>1;
if(dis(m1,i)>dis(m2,i)) {
r=m2;
}
else l=m1;
}
ans=max(ans,dis(l,i));
}
cout<<ans;
return 0;
}
D题：
题意：给一组问的数据和回答，让你找一个数，使这些回答尽量多的正确。
思路：离散化加差分，最后前缀和找最大就好了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
set<int> se;
map<int,int> mp;
int main() {
// cout<<"Accepted!\n";
int n;
cin>>n;
int x;
char c;
int res=0,s=0,inf=1e17;
while(n--) {
scanf("%d %c",&x,&c);
if(c=='.') {
se.insert(x);
mp[x]++;
se.insert(x+1);
mp[x+1]--;
}
else if(c=='+') {
se.insert(-inf);
mp[-inf]++;
se.insert(x);
mp[x]--;
}
else {
se.insert(x+1);
mp[x+1]++;
}
}
for(set<int>::iterator it=se.begin();it!=se.end();it++) {
// cout<<*it<<' '<<mp[*it]<<"\n";
s+=mp[*it];
res=max(res,s);
}
cout<<res;
return 0;
}
E题：
题意任意交换两个孩子的位置，让他们从小到大排好序的交换次数。
思路：刚开始以为快排找交换次数，后来发现这是错的。然后我就想直接从第一个孩子开始排，直接把他放到所需的位置，就这样排一遍记录次数。写完提交发现这样是对的。后来通过群友巨巨们了解到，这就是找环的个数，仔细想想就是这样。一个环内所有的人要放到指定位置就是减缓环内元素-1次，那我们也不用记录环内元素个数，就直接记录环的个数，然后减去环的个数就好了。下面是我的ac代码。
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int b[maxn];
map<int,int> mp;
int main() {
int n;
cin>>n;
for(int i=1;i<=n;++i) {
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
for(int i=1;i<=n;++i) {
mp[b[i]]=i;
}
int res=0,pos=1;
while(pos<n) {
if(mp[a[pos]]!=pos) {
int i=mp[a[pos]],temp=a[pos];
a[pos]=a[i];
a[i]=temp;
res++;
}
else {
pos++;
}
}
cout<<res<<"\n";
}
京公网安备 11010502036488号