Andy2035

$\color{red}{Andy家族}$

2.0万

LHQing

bsbsbsbsbswq
Sergey
liaoyanxu

dushucheng0901

gky

Mr.Yeh
Ethanyyc
study_dream

algorithm.

usaco silver做不出来了，就A了T3。。55555555555555555555555555555555

hhhhusaco银组第一题放弃了没想到T3水到感动哈哈哈哈哈哈

usaco银组惨案

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N];
void q_sort(int q[],int l,int r){
if(l>=r)return;
int i = l-1,j = r+1,x = q[(l+r)/2];
while(i<j){
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j)swap(q[i],q[j]);
}
q_sort(q,l,j),q_sort(q,j+1,r);
}
int n;
int main(){
cin>>n;
for(int i = 0;i<n;++i)cin>>q[i];
q_sort(q,0,n-1);
for(int i = 0;i<n;++i)cout<<q[i]<<" ";
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N];
int quick_sort(int q[],int l,int r,int k){
if(l>=r)return q[l];
int i = l-1,j = r+1,x = q[(l+r)/2];
while(i<j){
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j)swap(q[i],q[j]);
}
int sl = j-l+1;
if(sl>=k)return quick_sort(q,l,j,k);
else return quick_sort(q,j+1,r,k-sl);
}
int k,n;
int main(){
cin>>n>>k;
for(int i = 0;i<n;i++)cin>>q[i];
cout<<quick_sort(q,0,n-1,k);
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N],tmp[N];
void m_sort(int q[],int l,int r){
if(l>=r)return;
int mid = l+r>>1;
m_sort(q,l,mid),m_sort(q,mid+1,r);
int k = 0,i = l,j = mid+1;
while(i<=mid&&j<=r){
if(q[i]<=q[j])tmp[k++] = q[i++];
else tmp[k++] = q[j++];
}
while(i<=mid)tmp[k++] = q[i++];
while(j<=r)tmp[k++] = q[j++];
for(int i = l,j = 0;i<=r;i++,j++)q[i] = tmp[j];
}
int n;
int main(){
cin>>n;
for(int i = 0;i<n;i++)cin>>q[i];
m_sort(q,0,n-1);
for(int i = 0;i<n;i++)cout<<q[i]<<" ";
return 0;
}


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
int q[N],tmp[N];
ll m_sort(int q[],int l,int r){
if(l>=r)return 0;
int mid = l+r>>1;
ll res = m_sort(q,l,mid)+m_sort(q,mid+1,r);
int i = l,j = mid+1,k=0;
while(i<=mid&&j<=r){
if(q[i]<=q[j])tmp[k++] = q[i++];
else{
res+=mid-i+1;
tmp[k++] = q[j++];
}
}
while(i<=mid)tmp[k++] = q[i++];
while(j<=r)tmp[k++] = q[j++];
for(int i = l,j = 0;i<=r;i++,j++)q[i] = tmp[j];
return res;
}
int main(){
int n;cin>>n;
for(int i = 0;i<n;i++)cin>>q[i];
cout<<m_sort(q,0,n-1);
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n,q;
int main(){
cin>>n>>q;
for(int i = 0;i<n;i++)cin>>a[i];
while(q--){
int x;cin>>x;
int l = 0,r = n-1;
while(l<r){
int mid = l+r>>1;
if(a[mid]>=x)r = mid;
else l = mid+1;
}
if(a[l] != x)puts("-1 -1");
else{
cout<<l<<" ";
l = 0,r = n-1;
while(l<r){
int mid  = l+r+1>>1;
if(a[mid]<=x)l = mid;
else r = mid-1;
}
cout<<r<<endl;
}
}
}


#include<bits/stdc++.h>
using namespace std;
int main(){
double x;int f;
cin>>x;
if(x<0)f=1,x = -x;
double l = 0,r = 10000000,mid;
while(l<r){
mid = (l+r)/2;
if(abs(mid*mid*mid-x)<0.0000000001)break;
if(mid*mid*mid<x)l = mid;
else r = mid;
}
printf("%.6lf",!f?mid:-mid);
}


#include<bits/stdc++.h>
using namespace std;
int t = 0;
vector<int> C;
for(int i = 0;i<A.size();i++){
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;
}
int main(){
string a,b;cin>>a>>b;
vector<int> A,B;
for(int i = a.size()-1;i>=0;--i)A.push_back(a[i]-'0');
for(int i = b.size()-1;i>=0;--i)B.push_back(b[i]-'0');
for(int i = C.size()-1;~i;--i)cout<<C[i];
return 0;
}


#include<bits/stdc++.h>
using namespace std;
bool cmp(string a,string b){
if(a.size()!=b.size())return a.size()>b.size();
for(int i = 0;i<a.size();i++)
if(a[i]!=b[i])return a[i]>b[i];
return true;
}
string sub(string a,string b){
if(!cmp(a,b))return "-" + sub(b,a);
vector<int> A,B;
for(int i = a.size()-1;~i;--i)A.push_back(a[i]-'0');
for(int i = b.size()-1;~i;--i)B.push_back(b[i]-'0');
vector<int> C;
for(int i = 0,t = 0;i<A.size();i++){
t = A[i] - t;
if(i<B.size())t -= B[i];
C.push_back((t+10)%10);
t<0?(t=1):(t=0);
}
while(C.size()>1&&C.back()==0)C.pop_back();
string c;
for(int i = C.size()-1;~i;--i)c+=to_string(C[i]);
return c;
}
int main(){
string a,b;cin>>a>>b;
cout<<sub(a,b)<<endl;
return 0;
}


#include<bits/stdc++.h>
using namespace std;
vector<int> mul(vector<int> A,int b){
vector<int> C;
int t = 0;
for(int i = 0;i<A.size()||t;i++){
if(i<A.size())t += A[i] * b;
C.push_back(t%10);
t/=10;
}
while(C.size()>1&&C.back()==0)C.pop_back();
return C;
}
int main(){
string a;int b;
cin>>a>>b;
vector<int> A;
for(int i = a.size()-1;~i;--i)A.push_back(a[i]-'0');
auto C = mul(A,b);
for(int i = C.size()-1;~i;--i)cout<<C[i];
return 0;
}


#include<bits/stdc++.h>
using namespace std;
vector<int> div(vector<int> A,int b,int &r){
vector<int> C;
r = 0;
for(int i = A.size()-1;~i;--i){
r = r*10+A[i];
C.push_back(r/b);
r%=b;
}
reverse(C.begin(),C.end());
while(C.back()==0&&C.size()>1)C.pop_back();
return C;
}
int main(){
string a;int b,r;
cin>>a>>b>>r;
vector<int> A;
for(int i = a.size()-1;~i;--i)A.push_back(a[i]-'0');
auto C = div(A,b,r);
for(int i = C.size()-1;~i;--i)cout<<C[i];
cout<<endl<<r<<endl;
return 0;
}


#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main(){
int n,m;cin>>n>>m;for(int i = 1;i<=n;i++){cin>>a[i];a[i]+=a[i-1];}
while(m--){
int l,r;cin>>l>>r;cout<<a[r]-a[l-1]<<endl;
}
return 0;
}


2d前缀和

#include<bits/stdc++.h>
using namespace std;
int s[1010][1010];
int n,m,q;
int main(){
cin>>n>>m>>q;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++){cin>>s[i][j];s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];}
while(q--){
int a,b,c,d;cin>>a>>b>>c>>d;
cout<<s[c][d]-s[c][b-1]-s[a-1][d]+s[a-1][b-1]<<endl;
}
return 0;
}


1d差分

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int d[N];
int main(){
int n,m;cin>>n>>m;
for(int i = 1;i<=n;i++){
int x;cin>>x;d[i]+=x;d[i+1]-=x;
}
while(m--){
int a,b,c;
cin>>a>>b>>c;
d[a]+=c,d[b+1]-=c;
}
for(int i = 1;i<=n;i++){d[i] += d[i-1];cout<<d[i]<<" ";}
return 0;
}


2d差分

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int d[N][N];
int n,m,q;
void insert(int h,int i,int j,int k,int c){
d[h][i]+=c,d[h][k+1]-=c,d[j+1][i]-=c,d[j+1][k+1]+=c;
}
int main(){
cin>>n>>m>>q;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++){
int x;cin>>x;insert(i,j,i,j,x);
}
while(q--){
int h,i,j,k,c;
cin>>h>>i>>j>>k>>c;
insert(h,i,j,k,c);
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
d[i][j] += d[i-1][j] + d[i][j-1] -d[i-1][j-1];cout<<d[i][j]<<" ";}
puts("");
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int main(){
int n,res = 0;cin>>n;
for(int i = 0;i<n;i++)cin>>a[i];
map<int,int> s;
for(int i = 0,j=0;i<n;i++){
s[a[i]]++;
while(s[a[i]]>1)s[a[j++]]--;
res = max(res,i-j+1);
}
cout<<res;
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],b[N];
int main(){
int n,m,x;
cin>>n>>m>>x;
for(int i = 0;i<n;i++)cin>>a[i];
for(int j = 0;j<m;j++)cin>>b[j];
for(int i = 0,j=m-1;i<n;i++){
while(~j&&b[j]+a[i]>x)j--;
if(b[j]+a[i]==x){
cout<<i<<" "<<j<<endl;
break;
}
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 100010;
int a[N],b[N];
int main(){
cin>>n>>m;
for(int i = 0;i<n;i++)cin>>a[i];
for(int j = 0;j<m;j++)cin>>b[j];
int i = 0,j = 0;
while(i<n&&j<m){
if(a[i]==b[j])i++;
j++;
}
if(i==n)puts("Yes");
else puts("No");
return 0;
}


#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
while(n--){
int res = 0;
int x;cin>>x;
while(x)x-=x&(~x+1),res++;
printf("%d ",res);
}
}


#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
void merge(vector<pii> &segs){
sort(segs.begin(),segs.end());
vector<pii> res;
int st = -2e9,ed = -2e9;
for(auto seg:segs){
if(ed<seg.first){
if(st!=-2e9)res.push_back({st,ed});
st = seg.first,ed = seg.second;
}
else ed = max(ed,seg.second);
}
if(st!=-2e9)res.push_back({st,ed});
segs = res;
}
int main(){
int n;
vector<pii> segs;
cin>>n;
for(int i = 0;i<n;i++){
int l,r;cin>>l>>r;
segs.push_back({l,r});
}
merge(segs);
cout<<segs.size()<<endl;
return 0;
}


cao T1 15 min

USACO银组难不难啊