头像

Andy2035

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




离线:20小时前


最近来访(438)
用户头像
做事要有遗逝感
用户头像
LHQing
用户头像
星河依旧长明
用户头像
bsbsbsbsbswq
用户头像
Sergey
用户头像
liaoyanxu
用户头像
有机物
用户头像
专业打周赛
用户头像
大学才
用户头像
种花家的兔兔
用户头像
dushucheng0901
用户头像
忘打周赛Duck
用户头像
gky
用户头像
桂物骑士
用户头像
垫抽底风
用户头像
Mr.Yeh
用户头像
Ethanyyc
用户头像
study_dream
用户头像
晓月兮清风
用户头像
algorithm.

新鲜事 原文

阅读量2w祭


新鲜事 原文

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


新鲜事 原文

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


新鲜事 原文

usaco银组惨案


新鲜事 原文

开始打银,快躲开,小心别被我打了 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;
vector<int> add(vector<int> &A,vector<int> &B){
    if(A.size()<B.size())return add(B,A);
    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');
    auto C = add(A,B);
    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银组难不难啊


新鲜事 原文

问一下,USACO银组难不难,我刚AK铜组,准备明天打