本来不想打的，结果看着看着自己就打进去了（笑哭）
A.第k小数
记得上课讲过。这道题卡排序（但听说有人排序过了？？）
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x * f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=(ans*a)%mod;
a=a*a%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
const int maxn=5e6+10;
int t,n,k;
int a[maxn];
int quick(int l,int r,int k){
int i=l,j=r,x=a[i];
while(i<j){
while(i<j&&a[j]>x){
j--;
}
if(i<j){
a[i++]=a[j];
}
while(i<j&&a[i]<x){
i++;
}
if(i<j){
a[j--]=a[i];
}
}
a[i]=x;
if(i==k) return a[i];
else if(k<i) return quick(l,i-1,k);
else return quick(i+1,r,k);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
clock_t c1 = clock();
//===========================================================
t=read();
while(t--){
n=read(),k=read();
rep(i,1,n){
a[i]=read();
}
int ans=quick(1,n,k);
write(ans);
putchar('\n');
}
//===========================================================
std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}还有一种利用stl的方法，也可以过。
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=(ans*a)%mod;
a=a*a%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
const int maxn=5e6+100;
int a[maxn];
int t,n,k;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
clock_t c1 = clock();
//===========================================================
read(t);
while(t--){
read(n),read(k);
rep(i,1,n) read(a[i]);
nth_element(a+1,a+k,a+n+1);
write(a[k]);
putchar('\n');
}
//===========================================================
std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}B.不平行的直线
一道练stl的题，要注意处理下横坐标相等的情况就行了，剩下的set去重即可。
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=(ans*a)%mod;
a=a*a%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
struct Point{
ll x,y;
Point(int xx,int yy){
x=xx,y=yy;
}
};
vector<Point> da;
int n;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
clock_t c1 = clock();
//===========================================================
read(n);
rep(i,1,n){
int x,y;
read(x),read(y);
da.push_back(Point{x,y});
}
set<double> s;
int flag=0;
rep(i,0,n-1){
rep(j,0,n-1){
if(i==j) continue;
if(da[i].x==da[j].x){
flag=1;
}
else s.insert((double)(da[i].y-da[j].y)/(da[i].x-da[j].x));
}
}
write(s.size()+flag);
//===========================================================
std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}C.丢手绢
因为对于一个小朋友，顺时针遍历所有小朋友的过程中，他和某一个小朋友的距离是一个凸函数，所以，考虑对每一个小朋友三分，求距离他最远的小朋友，然后取所有答案的最大值即可。
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=(ans*a)%mod;
a=a*a%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
const int maxn=100000+10;
ll a[maxn];
int s;
ll sum[maxn];
int n;
int cal(int x,int y){
if(y<x) swap(x,y);
return min(abs(sum[y]-sum[x]),abs(s-abs(sum[y]-sum[x])));
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
clock_t c1 = clock();
//===========================================================
read(n);
rep(i,1,n) read(a[i]);
rep(i,1,n){
sum[i]=sum[i-1]+a[i];
}
s=sum[n];
int ans=0;
rep(i,1,n){
int l=1,r=n;
int res=0;
while(l<=r){
int lm=l+(r-l)/3,rm=r-(r-l)/3;
int lv=cal(i,lm),rv=cal(i,rm);
if(lv<rv){
l=lm+1;
res=rv;
}
else{
r=rm-1;
res=lv;
}
}
ans=max(res,ans);
}
write(ans);
//===========================================================
std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}D.二分
题目写着二分，实际考虑的是差分+离散化。参考校门外的数，每次读入之后，根据符号得到，定区间的左右坐标，然后，扫描一遍就行了。
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=(ans*a)%mod;
a=a*a%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
const int maxn=200000+100;
ll n;
struct node{
ll pos,val;
}da[maxn];
ll cnt;
vector<ll> a;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
clock_t c1 = clock();
//===========================================================
read(n);
rep(i,1,n){
ll pp;
char op;
read(pp),cin>>op;
if(op=='.'){
da[cnt++]={pp,1};
da[cnt++]={pp+1,-1};
}
if(op=='-'){
da[cnt++]={pp+1,1};
da[cnt++]={INT_MAX,-1};
}
if(op=='+'){
da[cnt++]={pp,-1};
da[cnt++]={-INT_MAX,1};
}
}
sort(da,da+cnt,[](const node&a,const node&b){
return a.pos==b.pos?a.val<b.val:a.pos<b.pos;
});
ll pos=0;
ll ans=0;
rep(i,0,cnt-1){
pos+=da[i].val;
ans=max(ans,pos);
}
write(ans);
//===========================================================
std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}E.交换
map乱搞题，但就是不会Orz。。我们可以想到，最小的交换次数，其实就是每次都归位一个数。这时候，可能会想到直接数有多少个数位置不对就行，但是，这并不行，例如：1 4 3 2 5，4和2交换一次，就归位了两个数了，所以可以通过模拟过程来消除这种情况。注意，归位后还需要更新map的值！
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=(ans*a)%mod;
a=a*a%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
const int maxn=100000+10;
int n;
int a[maxn];
int b[maxn];
int c[maxn];
int flag[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
clock_t c1 = clock();
//===========================================================
read(n);
map<int,int> mark;
rep(i,1,n){
read(a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
rep(i,1,n){
mark[a[i]]=i;
}
ll cnt=0;
rep(i,1,n){
if(a[i]!=b[i]){
cnt++;
int p1=i,p2=mark[b[i]];
swap(a[i],a[p2]);
mark[a[i]]=i;
mark[a[p2]]=p2;
}
}
write(cnt);
//===========================================================
std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}另外，也可以运用一个找循环的做法做出来。
大佬博客：https://blog.csdn.net/lfb637/article/details/86653121
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=(ans*a)%mod;
a=a*a%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
const int maxn=100000+10;
int n;
int a[maxn];
int b[maxn];
int c[maxn];
int flag[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
clock_t c1 = clock();
//===========================================================
read(n);
map<int,int> mark;
rep(i,1,n){
read(a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
rep(i,1,n){
mark[b[i]]=i;
}
int flag[maxn]={0};
ll cnt=0;
rep(i,1,n){
if(!flag[i]){
int j=i;
while(!flag[j]){
flag[j]=1;
j=mark[a[j]];
}
cnt++;
}
}
write(n-cnt);
//===========================================================
std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}
京公网安备 11010502036488号