头像

yuanbin


访客:22328

离线:7个月前


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

yuanbin
10个月前

#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int a[N],n,i,ans,sum;
int main()
{
    cin>>n;
    for (i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    int sm=a[n/2+1];
    for (i=1;i<=n;i++)
        ans=ans+abs(a[i]-sm);
    cout<<ans;
    return 0;
}


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

yuanbin
10个月前
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5e5+100;
int r[N],a[N],n;
long long ans=0;
void msort(int s,int t)
{
    if(s==1&&t==n) ans=0;
    if(s>=t) return;
    int mid=(s+t)/2;
    msort(s,mid);msort(mid+1,t);
    int i=s,j=mid+1,k=s;
    while(i<=mid&&j<=t)
        if(a[i]<=a[j]) r[k++]=a[i++];
        else
        {
            r[k++]=a[j++];
            ans+=mid-i+1;
        }   
    while(i<=mid) r[k++]=a[i++];
    while(j<=t) r[k++]=a[j++]; 
    for(int i=s;i<=t;i++) a[i]=r[i];
} 
int main()
{
    while(cin>>n&&n)
    {
        for(int i=1;i<=n;i++) cin>>a[i];
        msort(1,n);
        cout<<ans<<endl;
    }
    return 0;
}




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

yuanbin
10个月前
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

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]);
            if (!compare(res[r], i)) swap(res[r], res[r + 1]);
        }
        return res;
    }
};




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

yuanbin
10个月前
#include<iostream>
#include<stdio.h>
#include<memory.h>
#include<math.h>
using namespace std;
const int N = 100010 ;
int height[N];
double cpy[N];
double cpy_sum[N];
bool check(double target,int n, int f){

    for(int i =1;i<=n;++i)
        cpy[i] = height[i];

    for(int i =1;i<=n;++i)
        cpy[i] -= target;
    memset(cpy_sum,0,sizeof(cpy_sum));

    double min_left = 1<<30;
    double max_res = -10000000000;
    for(int i = 1;i<=n;++i){
        cpy_sum[i] = cpy[i] +cpy_sum[i-1];

        if(i-f>=0){
            min_left = min(cpy_sum[i-f],min_left);

            max_res = max(max_res,cpy_sum[i]-min_left);
        }
    }

    return max_res >=0.0;

}
int main(){



    int n ,f;
    cin >> n >>  f;
    int sum = 0;
    for(int i = 1;i<=n;++i){
        cin >> height[i];
        sum += height[i];
    }

    double left = 0.0,right = 2000;
    const double eps = 1e-7;

    while(right- left > eps){
        double mid = (left+right)/2.0;
        if(check(mid,n,f))
            left = mid;
        else
            right = mid;
    }

    cout << (int)(right * 1000) <<endl;

    return 0;
}


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

yuanbin
10个月前
#include<iostream>
#include<stdio.h>
#include<set>
using namespace std;
const int N = 1000010;
int heights[N];
set<pair<int,int>> visit;

int main(){
    int n ,p,h,m;
    cin >> n >> p >> h >> m;
    heights[1] = h;

    for(int i = 1,a,b;i<=m;++i){
        cin >> a>>b;
        if(a>b) swap(a,b);
        if(!visit.count({a,b})){
            visit.insert({a,b});
            heights[a+1]--, heights[b]++;
        }
    }

    for(int i =1;i<=n;++i){
        heights[i] += heights[i-1];
        cout <<heights[i]<<endl;
    }

    return 0;
}




活动打卡代码 AcWing 100. IncDec序列

yuanbin
11个月前
#include<iostream>
#include<stdio.h>
#include<memory.h>
using  namespace std;
const int N = 500005;
typedef long long LL;
long long  a[N],b[N];

int main(){
    int n ;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) 
        cin >> a[i];
    memset(b,0,sizeof(b));

    for (int i = 1; i<=n; i ++ ) 
        b[i] = a[i] - a[i-1];

    LL p=0,q=0;
    for(int i =2;i<=n;++i)
        if(b[i]>0)
            p+=b[i];
        else
            q-=b[i];
    cout << max(p,q) <<endl;
    cout <<abs(p-q)+1<<endl;

    return 0;
}


活动打卡代码 AcWing 99. 激光炸弹

yuanbin
11个月前
#include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;
const int MAX = 5005;
int sum[MAX][MAX];

int main(){
    memset(sum,0,sizeof(sum));


    int N,R;
    cin >> N>>R;
    for(int i = 1;i<=N;++i){
        int x,y,v;
        cin >> x>>y>>v;
        sum[x+1][y+1] += v;
    }

    for(int x = 1;x<=5000;++x)
        for(int y=1;y<=5000;++y)
            sum[x][y] += sum[x-1][y] + sum[x][y-1] - sum[x-1][y-1] ;
    int value = 0;
    for(int i = R;i<=5000;++i){
        for(int j = R;j<=5000;++j){
            int cur = sum[i][j] - sum[i-R][j] - sum[i][j-R] + sum[i-R][j-R];
            value = max(cur,value);
        }
    }
    cout << value <<endl;

    return 0;
}


活动打卡代码 AcWing 318. 划分大理石

yuanbin
11个月前
#include<iostream>
#include<stdio.h>
#include<memory.h>
#include<math.h>
using namespace std;
const int MAX = 2000000;
bool dp[7][MAX];

int main(){
    while(true){

        int number[7];
        for(int i = 1;i<=6;++i)
            cin >> number[i];
        int sum = 0;

        for(int i = 1 ;i<=6;++i)
            sum += number[i]*i;
        if(!sum) break;

        if(sum % 2 == 1){
            cout <<"Can't" <<endl;
            continue;
        }

        int half_sum = sum/2;
        memset(dp,false,sizeof(dp));
        dp[0][0] = true;

        for(int i = 1;i<=6;++i){
            int maxdepth = 0;
            int s=  number[i];
            while(s){
                maxdepth +=  1;
                s = s >> 1;
            }
            for(int v = 0;v<=half_sum;++v){
                dp[i][v] = dp[i-1][v];

                for(int k = 0;k<maxdepth && v-(int)pow(2,k)*i>=0;++k){
                    dp[i][v] = dp[i][v] | dp[i][v-(int)pow((int)2,k)*i];
                }
            }
        }

        if(dp[6][half_sum])
            cout << "Can" <<endl;
        else
            cout <<"Can't" <<endl;
    }



    return 0;
}


活动打卡代码 AcWing 322. 消木块

yuanbin
11个月前
#include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;

const int N = 205;

int a[N], last[N], pre[N], f[N][N][N];
int dp(int l,int r, int k){
    if(l>r) return 0;
    if(f[l][r][k]) return f[l][r][k];

    if(a[r-1]^a[r]) f[l][r][k] = max(f[l][r][k], dp(l,r-1,0)+(k+1)*(k+1));

    for(int i = pre[r];i>=l;i = pre[i])
        f[l][r][k] = max(f[l][r][k],dp(l,i,k+1)+dp(i+1,r-1,0));

    return f[l][r][k];
}

int main(){
    int t;
    cin >> t;
    int num = 1;
    while(t--){
        int n;
        cin >> n;
        memset(last,0,sizeof(last));
        memset(a,0,sizeof(a));
        memset(pre,0,sizeof(pre));
        memset(f,0,sizeof(f));

        for(int i = 1;i<=n;++i){
            cin >> a[i];
            pre[i] = last[a[i]];
            last[a[i]] = i;
        }
        int res = dp(1,n,0);
        cout<<"Case "<<num++<< ": "<< res <<endl;

    }


    return 0;
}


活动打卡代码 AcWing 321. 棋盘分割

yuanbin
11个月前
#include<iostream>
#include<stdio.h>
#include<memory.h>
#include<math.h>
using namespace std;
int matrix[20][20];
int sum[20][20];
int dp[10][10][10][10][20];
const int inf = 100000000;


int qry(int x1, int x2,int y1, int y2){
    return sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
}


int area(int x1,int x2, int y1, int y2, int t){
    if(dp[x1][x2][y1][y2][t] != 0)
        return dp[x1][x2][y1][y2][t];

    if(t == 1) 
        return qry(x1,x2,y1,y2) * qry(x1,x2,y1,y2);

    if( x1 == x2 && y1 == y2)
        return inf;
    int ans = inf;

    for(int x = x1;x<x2;++x){
        int row1 = area(x1,x,y1,y2,1)+area(x+1,x2,y1,y2,t-1);
        int row2 = area(x1,x,y1,y2,t-1)+area(x+1,x2,y1,y2,1);
        int res = min(row1,row2);
        ans = min(res,ans);
    }

    for(int y = y1;y<y2;++y){
        int col1 = area(x1,x2,y1,y,1)+area(x1,x2,y+1,y2,t-1);
        int col2 = area(x1,x2,y1,y,t-1)+area(x1,x2,y+1,y2,1);
        int res= min(col1,col2);
        ans = min(ans,res);
    }

    dp[x1][x2][y1][y2][t] = ans;
    return ans;
}


int main(){
    memset(dp,0,sizeof(dp));
    memset(sum,0,sizeof(sum));

    int n ;
    cin >> n;
    for(int i = 1;i<=8;++i){
        for(int j = 1;j<=8;++j){
            cin >> matrix[i][j];
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i][j];
        }
    }


    double avg = (double)sum[8][8]/n;

    int fang = area(1,8,1,8,n);


    double res = sqrt( (double)(fang-n*avg*avg )/n );
    printf("%.3f\n",res);

    return 0;
}