AcWing 786. 第k个数 快速选择
wr:
x不一定在边界上。
if (i < j) swap(q[i], q[j]);
reflection
边界问题：只能花时间debug，比赛的时候没时间推.
nth_element(a+1,a+1+k,a+n); cout<<a[k];
快速选择复杂度： 等比数列求和，O(n)
应用：区间第k大也是这个写法
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)1e6+5;
int a[maxn];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
//debug(j-l+1),debug(x);rep(i,l,r)cout<<a[i]<<' ';cout<<endl;
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int kth(int q[],int l,int r,int x){
if (l >= r) return q[l];
int i = l - 1, j = r + 1, t = q[l];
while (i < j)
{
do i ++ ; while (q[i] < t);
do j -- ; while (q[j] > t);
if (i < j) swap(q[i], q[j]);
}
int sl=j-l+1;
if(x<=sl)return kth(q,l,j,x);
else return kth(q,j+1,r,x-sl);
}
int main(){
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,k;cin>>n>>k;
rep(i,1,n)scanf("%d",&a[i]);
cout<<kth(a,1,n,k);
}
/*
4
3 3 1 5
1 3 3 5
10
49 59 88 37 98 97 68 54 31 3
*/
AcWing 788. 逆序对的数量 第一次写排序
wr
k=1
逆序对的定义是左比右大，枚举右边<=改成<，每个数a[j]对答案的贡献是mid-i+1
1e5*1e5/2 >1e9
reflection:
自己做，好好分析加A题经验其实没啥问题
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
#define int long long
const int maxn=(int)1e6+5;
int a[maxn],tmp[maxn];
int merge_sort(int q[],int l,int r){
//debug(l),debug(r);
if(l>=r){
//debug(q[l]);
return 0;
}
int mid=l+r>>1;
int ret1=merge_sort(q,l,mid);
int ret2=merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=l;
int ret=0;
while(1){
while(i<=mid and j<=r and q[i]<=q[j])tmp[k++]=q[i++];
while(j<=r and i<=mid and q[j]<q[i])tmp[k++]=q[j++],ret+=max(mid-i+1,0ll);
if(i>mid or j> r)break;
}
while(i<=mid)tmp[k++]=q[i++];
while(j<=r)tmp[k++]=q[j++];
rep(i,l,r){q[i]=tmp[i];}
ret+=ret1+ret2;
//debug(ret);rep(i,l,r){q[i]=tmp[i];cout<<q[i]<<' ';}cout<<endl;
return ret;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;cin>>n;for(int i=1;i<= n;i++)cin>>a[i];
cout<<merge_sort(a,1,n);
//for(int i=1;i<= n;i++)cout<<a[i]<< ' ';
}
/*
*/
AcWing 790. 数的三次方根
wr
1 eps要多一位
2 -x 不一定-
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(6);
const int maxn=(int)1e6+5;
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
double x;cin>>x;
double l=min(-x,x),r=max(-x,x);
while(abs(r-l)>1e-7){
//debug(l),debug(r);
double mid=(l+r)/2;
if(mid*mid*mid>=x)r=mid;
else l=mid;
}
fix
cout<<l<<endl;
}
/*
三分法求min
f:目标函数
l:区间下界
r:区间上界
max_step:最大迭代次数
template <class fun>
double oneThirdIterate(fun f,double l,double r,int max_step){
double ml,mr;
rep(it,1,max_step){
ml=(2*l+r)/3,mr=(l+2*r)/3;
if(f(ml)>f(mr))l=ml;
else r=mr;
}
return l;
}
*/
AcWing 789. 数的范围
reflection
整数二分的本质是
对于定义在整数域上的bool函数check，且存在分界点使得左右两边函数值不同。 找出左边的最大值或右边的最小值。
如果check是左0右1，对应于最后一个x使得check(x)==0和第一个x:check(x)==1。
对应的写法：if(check(mid))r=mid-1;else l=mid+1; 这样搜到最后r是左半边的右边界（包括r），l是右半边的左边界。
我是这么理解的，考虑循环的最后几步，如果右半边的左边界为L，最终mid会搜到L，执行r=L-1,然后l会不断变大到L,此时mid依然=l+r>>1=L-1,但是l>r 离开循环。
今天的新理解：本质上属于两头双指针算法，类似快排的快速分左右操作，一直保证r的右边（不包括r）是满足check的，l的左边是不满足check的，一步一步向中间移动，最终找出边界
如果左1，就反之。
eg 升序数列的
lower_bound, 大于等于x的第一个数。
upper_bound 大于x的第一个数。
check(y) return y>x;
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)1e6+5;
int a[maxn];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,q;cin>>n>>q;rep(i,1,n)cin>>a[i];
rep(i,1,q){
int x;cin>>x;
int l=1,r=n;
while(l<=r){
int mid=l+r>>1;
if(a[mid]>=x)r=mid-1;
else l=mid+1;
}
int left=l;
l=1,r=n;
while(l<=r){
int mid=l+r>>1;
if(a[mid]>x)r=mid-1;
else l=mid+1;
}
int right=r;//r==l-1
if(a[left]!=x)cout<<-1<<' '<<-1<<endl;
else cout<<left-1<<' '<<right-1<<endl;
/* if(lower_bound(a+1,a+1+n,x)-a-1==n||*lower_bound(a+1,a+1+n,x)!=x )cout<<-1<<' '<<-1<<endl;
else cout<<lower_bound(a+1,a+1+n,x)-a-1<<' '<<upper_bound(a+1,a+1+n,x)-a-2<<endl; */
}
}
AcWing 794. 高精度除法
reflection:
vectror 比较是字典序
高精度乘直接乘b维护t
除法后面加0，模，reverse
减除乘有前导零
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)1e6+5;
//倒着存在vector,只存正数
typedef vector<int> vi;
bool cmp(vi a,vi b){
if(a.size()!=b.size())return a.size()<b.size();
int i;
for( i=a.size()-1;i>=0 and a[i]==b[i];i--);
return a[i]<b[i];
}
vi add( vi a, vi b){
vi c;
int t=0;
for(int i=0;i<a.size()||i<b.size();i++){
if(i<a.size())t+=a[i];
if(i<b.size())t+=b[i];
c.push_back(t%10);
t/=10;
}
if(t)c.push_back(t);
return c;
}
vi mns(vi a,vi b){ //a,b>=0
int t=0;
vi c;
for(int i=0;i<a.size();i++){
t=a[i]-t;
if(i<b.size())t-=b[i];
c.push_back((t+10)%10);
if(t<0)t=1;else t=0;
}
while(c.size()>1&&c.back()==0)c.pop_back();
return c;
}
vi mul(vi a,int b){//b>=0
int t=0;
vi c;
for(int i=0;i<a.size()||t;i++){
if(i<a.size())t+=b*a[i];
c.push_back(t%10);
t/=10;
}
while(c.size()>1&&c.back()==0)c.pop_back();
return c;
}
vi divide(vi a,int b,int &r){
vi c;
r=0;
for(int i=a.size()-1;i>=0;i--){
r=r*10+a[i];
//debug(r);
c.push_back(r/b);
r%=b;
}
reverse(c.begin(),c.end());
while(c.size()>1&&c.back()==0)c.pop_back();
return c;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
string s1,s2;int B;
cin>>s1>>B;
vi a,b;
for(int i=s1.size()-1;i>=0;i--)a.push_back(s1[i]-'0');
//for(int i=s2.size()-1;i>=0;i--)b.push_back(s2[i]-'0');
vi c;int r;
c=divide(a,B,r);
for(int i=c.size()-1;i>=0;i--)cout<<c[i];cout<<endl;
cout<<r<<endl;
}
AcWing 796. 子矩阵的和
reflection
每一步严谨的话是不会错的
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)1e3+5;
int sum[maxn][maxn];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,m,q;
cin>>n>>m>>q;
rep(i,1,n)rep(j,1,m){
cin>>sum[i][j];
}
rep(i,1,n)rep(j,1,m){
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+sum[i][j];
}
rep(i,1,q){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]<<endl;
}
}
/*
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
*/
AcWing 798. 差分矩阵
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)1e3+5;
int sum[maxn][maxn],a[maxn][maxn];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,m,q;
cin>>n>>m>>q;
rep(i,1,n)rep(j,1,m){
cin>>a[i][j];
}
rep(i,1,q){
int x1,y1,x2,y2,v;
cin>>x1>>y1>>x2>>y2>>v;
sum[x1][y1]+=v;
sum[x1][y2+1]-=v;
sum[x2+1][y1]-=v;
sum[x2+1][y2+1]+=v;
}
rep(i,1,n)rep(j,1,m){
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+sum[i][j];
}
rep(i,1,n)
{
rep(j,1,m){
cout<<sum[i][j]+a[i][j]<<' ';
}
cout<<endl;
}
}
AcWing 799. 最长连续不重复子序列
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)1e6+5;
int a[maxn];
int main(){
int n;cin>>n;rep(i,1,n)cin>>a[i];
int ans=0;
set<int> s;
for(int i=1,j=1;i<=m;i++){
while(j<i and s.count(a[i]))s.erase(a[j]),j++;
s.insert(a[i]);
ans=max(ans,i-j+1);
}
cout<<ans<<endl;
}
AcWing 800. 数组元素的目标和
wr:j=m not n
题目所求没读完
也叫滑窗
本质是将n^2的区间 通过单调性 2n次遍历
单调性指对于区间(i,j) i大，j不减，
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)1e6+5;
int a[maxn],b[maxn];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,m,x;
cin>>n>>m>>x;
rep(i,1,n)cin>>a[i];
rep(j,1,m)cin>>b[j];
int ans=0;
for(int i=1,j=m;i<=n;i++){//for i
while(j<=1 and a[i]+b[j]>x)j--;//j 单调变化
if(a[i]+b[j]==x){cout<<i-1<<' '<<j-1<<endl;return 0;}
}
//cout<<ans<<endl;
}
AcWing 802. 区间和
wr:
+=c[i] not ++
前缀和 rep(i,1,v.size()) not i,1,n
没考虑询问端点 不在v里
reflection
从来没记住过 v.erase(unique(v.begin(),v.end()),v.end())
强制在线怎么做？map动态开点
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)1e6+5;
vector<int> v;
int cnt[maxn],x[maxn],c[maxn],L[maxn],R[maxn];
int id(int x){
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
rep(i,1,n){
cin>>x[i]>>c[i];
}
rep(i,1,m)cin>>L[i]>>R[i];
rep(i,1,n)v.push_back(x[i]);
rep(i,1,m)v.push_back(L[i]),v.push_back(R[i]);
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
rep(i,1,n){
cnt[id(x[i])]+=c[i];
}
rep(i,1,v.size())cnt[i]+=cnt[i-1];
rep(i,1,m){
int l=L[i],r=R[i];
int ll=id(l),rr=id(r);
cout<<cnt[rr]-cnt[ll-1]<<endl;
}
}
AcWing 803. 区间合并
wr
== not =
初始化 和循环 多余的-1
reflection:
写循环，
每一轮干一件事
第一个or最后一个可以不同，用边界简化
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)1e6+5;
typedef pair<int,int> pii;
int merge(vector<pii> seg){
int ret=0;int st=-1,ed=0;
sort(seg.begin(),seg.end());
for(auto item:seg){
if(st==-1){
st=item.first,ed=item.second;
ret++;
continue;
}
if(item.first<=ed) ed=max(ed,item.second);
else{st=-1;
st=item.first,ed=item.second;
ret++;
}
}
return ret;
}
int merge1(vector<pii> seg){
int ret=0;int st=-2e9,ed=-2e9;
vector<pii> res;
sort(seg.begin(),seg.end());
for(auto item:seg){
if(ed<item.first){
if(st!=-2e9)res.push_back({st,ed});
st=item.first,ed=item.second;
}
else ed=max(ed,item.second);
}
if(st!=-2e9)res.push_back({st,ed});
return res.size();
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;cin>>n;
vector<pii> seg;
rep(i,1,n){
int l,r;cin>>l>>r;
seg.push_back({l,r});
}
cout<<merge1(seg)<<endl;;
}
