头像

gmm




离线:2020-09-27 09:14


最近来访(4)
用户头像
xiaoxin0523
用户头像
秦时明月汉时光
用户头像
Zrosor_Acw
用户头像
瞳星结

活动打卡代码 AcWing 109. 天才ACM

gmm
2020-08-24 07:59

倍增 + 贪心 + 归并排序优化

//贪心:获取校验值用排序首尾配对
//为了T最小 区间长度最大 所以可以用[1]二分[2]倍增
//二分:可以证明最坏复杂度n^2*logn 
//倍增(朴素):可以证明,二分最坏对应倍增最好n*logn^2(二进制可以组成一切)
//倍增优化(归并排序):由于主要消耗在排序 而倍增本身方便看出只需增广部分排序归并 可以证明复杂度n*logn
//以下倍增+贪心+归并
//有关倍增:这里采用len*2增强 如果不行len/2 知道len==0不可增广
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 5e5+10;
int a[N],b[N],tmp[N];//a存储原本的(不能少) b存储现在归并成功结果 t用于归并
int n,m;
ll t;
bool check(int l,int mid,int r){//对[l,mid)增广到[l,r) 前闭后开 并归并到a中
    for(int i=mid;i<r;i++) b[i] = a[i];
    sort(b+mid,b+r);
    int i = l,j = mid,k = 0;
    while(i<mid && j<r){
        if(b[i]<b[j]) 
            tmp[k++] = b[i++];
        else 
            tmp[k++] = b[j++];
    }
    while(i<mid) tmp[k++] = b[i++];
    while(j<r) tmp[k++] = b[j++];
    ll sum = 0;
    for(int i=0;i<m&&i<k-1;i++,k--)
        sum += 1ll*(tmp[k-1]-tmp[i])*(tmp[k-1]-tmp[i]);
    if(sum<=t){
        for(int i=l;i<r;i++) b[i] = tmp[i-l];
        return true;
    }else
        return false;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m>>t;
        for(int i=0;i<n;i++) cin>>a[i];
        int ans = 0;
        int st = 0,ed = st;
        //左闭右开区间很方便
        while(ed<n){
            int len = 1;
            while(len){
                if(ed+len<=n && check(st,ed,ed+len)){
                    ed += len;
                    if(ed>=n)
                        break;
                    len<<=1;
                }else{
                    len>>=1;
                }
            }
            st = ed;
            ans++;
        }
        cout<<ans<<endl;
    } 
    return 0;
}


活动打卡代码 AcWing 108. 奇数码问题

gmm
2020-08-24 03:12

逆序对统计

//归并排序统计逆序对 
//由于n数码问题只能改变偶数个逆序对(0不能计入 否则改变奇数个) 所以只有逆序对数目均为奇/偶才可以TAK
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;//数据范围
const int N = 3e5+10;
int a[N],c[N];
ll merge_sort(int q[N],int l,int r){
    //终止条件
    if(l>=r) return 0;
    int mid = (l+r)>>1;
    ll res = merge_sort(q,l,mid) + merge_sort(q,mid+1,r);
    int i = l,j = mid + 1,idx = 0;
    while(i<=mid && j<=r){
        if(q[i]<q[j]) c[idx++] = q[i++];
        else{
            c[idx++] = q[j++];
            res += mid - i + 1;
        }
    }
    while(i<=mid) c[idx++] = q[i++];
    while(j<=r) c[idx++] = q[j++];
    for(int i=l,j=0;i<=r;i++) q[i] = c[j++];
    return res;
}
int main(){
    int n,num,idx;
    while(cin>>n){
        idx = 0;
        for(int i=0;i<n*n;i++){
            cin>>num;
            if(num) a[idx++] = num;
        }
        ll res1 = merge_sort(a,0,n*n-2);
        idx = 0;
        for(int i=0;i<n*n;i++){
            cin>>num;
            if(num) a[idx++] = num;
        }
        ll res2 = merge_sort(a,0,n*n-2);
        if(res1%2 == res2%2) cout<<"TAK"<<endl;
        else cout<<"NIE"<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 107. 超快速排序

gmm
2020-08-24 02:44

逆序对统计

//归并排序统计逆序对
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;//数据范围
const int N = 5e5+10;
int a[N],c[N];
ll merge_sort(int q[N],int l,int r){
    //终止条件
    if(l==r) return 0;
    int mid = (l+r)>>1;
    ll res = merge_sort(q,l,mid) + merge_sort(q,mid+1,r);
    int i = l,j = mid + 1,idx = 0;
    while(i<=mid && j<=r){
        if(q[i]<q[j]) c[idx++] = q[i++];
        else{
            c[idx++] = q[j++];
            res += mid - i + 1;
        }
    }
    while(i<=mid) c[idx++] = q[i++];
    while(j<=r) c[idx++] = q[j++];
    for(int i=l,j=0;i<=r;i++) q[i] = c[j++];
    return res;
}
int main(){
    int n;
    while(true){
        cin>>n;
        if(n==0) break;
        for(int i=0;i<n;i++) cin>>a[i];
        cout<<merge_sort(a,0,n-1)<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 106. 动态中位数

gmm
2020-08-24 02:26

对顶堆动态中位数(问题拆解简化思想)

//对顶堆维护动态中位数(需要先控制元素大小关系:上面的小根堆大于下面的大根堆全部元素;之后调整堆大小:下面的比上面的大1/0)
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        int num,n,tmp;
        cin>>num>>n;
        cout<<num<<" "<<n/2+1<<endl;
        priority_queue<int> max_hp;//下
        priority_queue<int,vector<int>,greater<int>> min_hp;//上
        int cnt = 0;
        for(int i=1;i<=n;i++){
            cin>>tmp;
            max_hp.push(tmp);
            //调整数字大小关系
            if(min_hp.size() && min_hp.top()<max_hp.top()){
                int a = min_hp.top(),b = max_hp.top();
                min_hp.pop(),max_hp.pop();
                min_hp.push(b),max_hp.push(a);
            }
            //调整堆大小关系
            if(max_hp.size()>min_hp.size()+1){
                min_hp.push(max_hp.top());
                max_hp.pop();
            }
            if(i%2){
                cout<<max_hp.top()<<" ";
                if(++cnt%10==0) cout<<endl;
            }
        }
        if(cnt%10) cout<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 105. 七夕祭

gmm
2020-08-24 02:01

贪心+破环成链(枚举断点破环)+前缀和+中位数+排序

//贪心+破环成链(枚举断点破环)+前缀和+中位数+排序
//问题转换 原题->行列无关->虽然交换会受到相同位置受阻影响但是但仍然等价于“纸牌交换”->环形糖果传递->中位数仓库选址问题
//小心数据范围
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
int n,m;
int r[N],c[N],f[N];
ll calc(int nums[N],int n){
    int avg = nums[0]/n;
    ll res = 0;
    for(int i=1;i<=n;i++)//预处理前缀和
        f[i] = f[i-1]+nums[i]-avg;
    sort(f+1,f+n+1);
    for(int i=1;i<=n;i++){
        res += abs(f[i]-f[(n+1)/2]);//中位数
    }
    return res;
}
int main(){
    int t,x,y;
    cin>>n>>m>>t;
    for(int i=0;i<t;i++){
        cin>>x>>y;
        r[x]++,c[y]++;
    }
    for(int i=1;i<=n;i++) r[0]+=r[i];
    for(int i=1;i<=m;i++) c[0]+=c[i];
    if(r[0]%n && c[0]%m){
        cout<<"impossible"<<endl;
    }else if(c[0]%m){
        cout<<"row "<<calc(r,n)<<endl;
    }else if(r[0]%n){
        cout<<"column "<<calc(c,m)<<endl;
    }else{
        cout<<"both "<<calc(r,n)+calc(c,m)<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

gmm
2020-08-23 15:07

中位数+排序

//寻找中位数 + 排序
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n;
int xs[N];
int main(){
    cin>>n;
    ll res = 0;
    for(int i=0;i<n;i++) cin>>xs[i];
    sort(xs,xs+n);
    for(int i=0,j=n-1;i<j;i++,j--) 
        res += xs[j]-xs[i];
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 103. 电影

gmm
2020-08-23 15:01

哈希 + 枚举

#include<iostream>
#include<cstring>
#include<unordered_map>
#include<algorithm>
// #pragma G++ optimize (3)
// #pragma Gcc optimize (3)
using namespace std;
const int N = 2e6+10;
struct Mov{
    int b,c,id;    
}mov[N];
int ch[N];
unordered_map<int,int> mp;
/*
inline bool cmp(Mov x,Mov y){
    if(mp[x.b]!=mp[y.b]) return mp[x.b]<mp[y.b];
    else return mp[x.c]<mp[y.c];
}
*/

int main(){
    int n,m,x;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        mp[x] ++;
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>mov[i].b;
        mov[i].id = i;
    }
    for(int i=1;i<=m;i++) cin>>mov[i].c;
    //也可以直接枚举搜索
    //排序超时
    /*
    sort(mov+1,mov+m+1,cmp);
    cout<<mov[m].id<<endl;
    */
    int mx = 0,mxc = 0;
    int res = 0;
    for(int i=1;i<=m;i++) 
        if(mp[mov[i].b]>mx) 
            mx = mp[mov[i].b];
    for(int i=1;i<=m;i++) 
        if(mp[mov[i].b]==mx)
            if(mp[mov[i].c]>=mxc){
                mxc = mp[mov[i].c];
                res = i;
            }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 113. 特殊排序

gmm
2020-08-23 13:46

二分 + 交互式问题

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
//朴素二分查找 n^2 -> nlogn 
//满足传递性
class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res;
        res.push_back(1);
        for(int i=2;i<=N;i++){
            int l = 0,r = res.size()-1;
            //找到小于当前节点的临界点
            while(l<r){
                int mid = (l+r+1)>>1;
                if(compare(res[mid],i)) l = mid;
                else r = mid - 1;
            }
            res.push_back(i);
            for(int j=res.size()-2;j>r;j--) swap(res[j],res[j+1]);
            //可能没找到 此时r为0 找到了则不需要交换
            if(!compare(res[r],i)) swap(res[r],res[r+1]);
        }
        return res;
    }
};


活动打卡代码 AcWing 102. 最佳牛围栏

gmm
2020-08-23 13:21

二分+ 前缀和双指针

//二分 + 前缀和双指针判断
#include<iostream>
#include<cstring>
using namespace std;
const double eps = 1e-6;
const int N = 1e5+10;
double sum[N],nums[N];
int n,m;
bool check(double avg){
    sum[0] = 0;
    for(int i=1;i<=n;i++) sum[i] = sum[i-1]+nums[i]-avg;
    //双指针
    double mins = 0;
    for(int i=0,j=m;j<=n;i++,j++){
        mins = min(mins,sum[i]);
        if(sum[j]-mins>=0)
            return true;
    }
    return false;
}

int main(){
    cin>>n>>m;
    double l = 1000,r = 0;
    for(int i=1;i<=n;i++) cin>>nums[i],l = min(l,nums[i]),r = max(r,nums[i]);
    while(r-l>eps){
        double mid = (l+r)/2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout<<int(r*1000)<<endl;
    return 0;
}


活动打卡代码 AcWing 101. 最高的牛

gmm
2020-08-23 09:59

差分+set

//简单差分 注意重复问题判断 用hash/set
#include<iostream>
// #include<unordered_set>
#include<set>//pair无法hash??
#include<algorithm>
using namespace std;
const int N = 1e4+10;
int b[N];
set<pair<int,int>> st;
int main(){
    int l,r;
    int n,p,h,m;
    cin>>n>>p>>h>>m;
    b[1] = h;
    for(int i=0;i<m;i++){
        cin>>l>>r;
        if(l>r) swap(l,r);
        if(st.count({l,r})==0){
            st.insert({l,r});
            //l+1 r-1
            b[l+1]--,b[r]++;
        }
    }
    for(int i=2;i<=n;i++) b[i] += b[i-1];
    for(int i=1;i<=n;i++) cout<<b[i]<<endl;
    return 0;
}