头像

baizhiren




离线:2天前


最近来访(9)
用户头像
大吉大利666
用户头像
努力学习鸭
用户头像
夜语声烦
用户头像
我呼吸了
用户头像
Mr.Az
用户头像
thomas_wmy
用户头像
AcWing2AK
用户头像
开着拖拉机去北极


暴力枚举 35ms

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int n;

int r1x, r1y, r2x, r2y;
const int N = 2010;
double d1[N], d2[N];
double d(double x1,  double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double ans = 1e18;
void dfs(int i, double r1, double r2){
    if(r1 * r1 + r2 * r2 >= ans) return;
    if(i > n){
        ans = r1 * r1 + r2 * r2;
    }
    if(d1[i] <= r1 || d2[i] <= r2) dfs(i + 1, r1, r2);
    else{
        dfs(i + 1, d1[i], r2);
        dfs(i + 1, r1, d2[i]);
    } 
}
int main(){
    cin >> n;
    cin >> r1x >> r1y >> r2x >> r2y;
    for(int i = 1; i <= n; i++)
    {
       int x, y;
       cin >> x >> y;
       d1[i] = d(r1x, r1y, x, y);
       d2[i] = d(r2x, r2y, x, y);
    }
   dfs(1, 0, 0);
   cout << (long long)(ans + 0.5);
    return 0;
}



baizhiren
1个月前

比y总写的简单点

思路

一个节点v有m个孩子 k1, k2 … km
记 wi = ski - sv 代表从节点ki到父节点v这段的权值和
则以v为根的子树的权值总和s = wk1 + wk2 … wkm - min(wk1, wk2 … wkm) * (m - 1)
因为重复计算了父节点的值,所以需要扣掉, 而这个值显然越大越好,但是不能超过任何一个wi,否则就违反了权值非负这一个条件

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2 * N, INF = 1e9 + 10;
typedef long long LL;
int h[N], e[M], ne[M], idx;
int s[N];
int n;
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool flag = true;
LL dfs(int u){
    LL ans = 0;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        int cnt = 0;
        int m = INF;
        for(int k = h[j]; ~k; k = ne[k]){
            cnt ++;
            int son  = e[k];
            int w = s[son] - s[u]; 
            if(w < 0)  flag = false;
            m = min(w, m);
            ans += dfs(son) + w;
        }
        if(m != INF)
        ans -= (cnt - 1) * m;
    }
    return ans;
}

int main(){
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i++){
        int a;
        cin >> a;
        add(a, i + 2);
    }
    for(int i = 1; i <= n; i++){
        cin >> s[i];
    }

    LL ans = dfs(1);
    if(flag)
    cout << ans + s[1];
    else
    cout << -1;

}


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

baizhiren
9个月前
#include<stdio.h>
#include<stdlib.h>
void swap(int& a,int& b ){
    int tmp;
    tmp=a;
    a=b;
    b=tmp; 
}
void quick_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]);
        else break;
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

int q[100000+10];
int main(){
    int n;
    scanf("%d",&n);
    for (int i=0;i<n;i++){
        scanf("%d",&q[i]);
    }
    quick_sort(q,0,n-1);
    for (int i=0;i<n;i++){
        printf("%d ",q[i]);
    }
    system("pause");
    return 0;
}