abc183 51nod

2020.11.15写下我atcoder第一次和开始刷51nod的第一篇blog

51nod:3143 整装待发!
这个题会卡精度好恶心，主要是切比雪夫距离和曼哈顿距离之间的转换
将一个点(x,y)的坐标变为(x+y,x−y)后,原坐标系中的曼哈顿距离 = 新坐标系中的切比雪夫距离
将一个点(x,y)的坐标变为((x+y)/2,(x−y)/2) 后,原坐标系中的切比雪夫距离 = 新坐标系中的曼哈顿距离

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int N=1e5+10;
double a[N],b[N],c[N],d[N];
int q[N],w[N];
int main()
{
    int n;
    //cin>>n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        double x,y;
        //cin>>x>>y;
        scanf("%lf%lf",&x,&y);
        q[i]=x;
        w[i]=y;
        a[i]=(x+y)/2;//排序求中位数的曼哈顿距离
        c[i]=(x+y)/2;
        b[i]=(x-y)/2;//排序求中位数的曼哈顿距离
        d[i]=(x-y)/2;
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    double  x,y;
    ll sum=0;
    if(n%2==1)
    {
        x=a[n/2];
        y=b[n/2];
    }
    else
    {
        x=(a[n/2]+a[n/2+1])/2;
        y=(b[n/2]+b[n/2+1])/2;
    }
    if((x==(int)(x))&&(y==int(y)))//恰好中位数是整数
    {

        for(int i=1; i<=n; i++)
        {
            sum+=(abs(c[i]-x)+abs(d[i]-y));
        }
        //cout<<sum<<endl;
        printf("%lld",sum);
    }
    else
    {
        ll ans1=0,ans2=0,ans3=0,ans4=0;//不是整数的四种情况
        int a=x+y,b=x-y;
        for(int i=1; i<=n; i++)
        {
            ans1+=max(abs(q[i]-(int)a),abs(w[i]-(int)b));
        }
        for(int i=1; i<=n; i++)
        {
            ans2+=max(abs(q[i]-(int)a-1),abs(w[i]-(int)b));
        }
        for(int i=1; i<=n; i++)
        {
            ans3+=max(abs(q[i]-(int)a-1),abs(w[i]-(int)b-1));
        }
        for(int i=1; i<=n; i++)
        {
            ans4+=max(abs(q[i]-(int)a),abs(w[i]-(int)b-1));
        }
        sum=min(min(min(ans1,ans2),ans3),ans4);
        //cout<<sum<<endl;
        printf("%lld",sum);
    }
    return 0;
}

atcoder 183
F启发式合并只要用个map记录每个组几班的有多少个然后合并的时候把小的往大的合并就好了

#include<bits/stdc++.h>
#define fp(i,a,b) for(int i=a;i<=b;i++)
typedef long long ll;
typedef double dl;
using namespace std;

const int N=2e5+7;
const ll M=1e9+7;
const int INF=0x3f3f3f3f;

int f[N],c[N],sz[N];
map<int,int> ve[N];

int find(int x)
{
    if(f[x]!=x)
    f[x]=find(f[x]);
    return f[x];
}

void merge(int x, int y) 
{
    x = find(x), y = find(y);
    if (x == y) return;
    if (sz[x] > sz[y]) swap(x, y);
    f[x] = y;
    for (auto i : ve[x])
        ve[y][i.first] += i.second;
    ve[x].clear();
    sz[y] += x;
}
void solve()
{
    int n,q;
    scanf("%d%d",&n,&q);    
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&c[i]);
        sz[i]=1;
        ve[i][c[i]]++;
    }
    for(int i=1;i<=q;i++)
    {
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)
        {
            merge(x,y);
        }
        else {
            int z=find(x);
            cout << ve[z][y] << endl;
        }
    }
}

int main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0),cout.tie(0);
    //int T; scanf("%d",&T)
    //for(int i=1;i<=T;i++)
        solve();
}