HGOI20190126 模拟赛

/*

最后一题比较难！

*/

solution：观察这个奇怪的图，不能共用走廊，就是1.2打包，3,4打包，每个包之间连线的线段覆盖问题。

考虑吧每个数映射成一个约为一半的数，且相邻(前奇后偶映射值一样)，如1.2映射为1且3.4映射为2，(2x-1.2x)映射成x

然后线段覆盖，用差分维护即可。

# include <bits/stdc++.h>

using namespace std;

const int MAXN=;

int s[MAXN],c[MAXN];

int n;

inline int read()

{

    int X=,w=;char c=;

    while (!(c>=''&&c<='')) w|=c=='-',c=getchar();

    while (c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();

    return w?-X:X;

}

void add(int l,int r)

{

    c[l]++; c[r+]--;

}

int main()

{

    n=read();

    for (int i=;i<=n;i++) {

        int l=(read()+)/,r=(read()+)/;

        if (l>r) swap(l,r);

        add(l,r);

    }

    for (int i=;i<=;i++) s[i]=s[i-]+c[i];

    int ans=;

    for (int i=;i<=;i++) ans=max(ans,s[i]);

    printf("%d\n",ans*);

    return ;

}

solution：可以字符串哈希、可以字典树、可以直接hash映射！

# include <bits/stdc++.h>

using namespace std;

const int N=;

char s[N],A[N];

int ans;

struct tt{

    int ch[N][],size;

    int val[N];

    tt(){

        size=;

        memset(ch[],,sizeof(ch[]));

        memset(val,,sizeof(val));

    }

    int idx(char a) { return a;}

    void insert()

    {

        int u=,len=strlen(s);

        for (int i=;i<len;i++) {

            int c=idx(s[i]);

            if (!ch[u][c]) {

                memset(ch[size],,sizeof(ch[size]));

                ch[u][c]=++size;

            }

            u=ch[u][c];

        }

        val[u]++;

        if (val[u]>ans) {

            ans=val[u];

            memcpy(A,s,sizeof(s));

        }

    }

}Tree;

int main()

{

    int  T; scanf("%d",&T);

    while (T--) {

        scanf("%s",s);

        Tree.insert();

    }

    printf("%s %d\n",A,ans);

    return ;

}

solution：这道题就是最小化

可以证明，d是a中位数时最小！

# include <bits/stdc++.h>

# define int long long

using namespace std;

const int N=2e6+;

int a[N],n,o,ans;

inline int read()

{

    int X=,w=;char c=;

    while (!(c>=''&&c<='')) w|=c=='-',c=getchar();

    while (c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();

    return w?-X:X;

}

signed main()

{

    n=read();

    for (int i=;i<=n;i++) read(),a[i]=read();

    sort(a+,a++n);

    if (n&) o=a[n/+]; else o=(a[n/]+a[n/+])/;

    for (int i=;i<=n;i++) ans=ans+abs(o-a[i]);

    printf("%lld\n",ans);

    return ;

}