20170910校内训练

CCT

最近学校又发了n本五三题霸，BBS看到后十分高兴。但是，当他把五三拿到手后才发现，他已经刷过这些书了！他又认真地看了一会儿，发现新发的这些五三是2017版的，而他刷的是2016版的。现在他想找出所有他没有刷过的题来刷。每本五三都有m道题，并且它的特征（即它和去年版本的五三的差距）可以用一个m位二进制数来代表，二进制位上的1代表该题不同，0代表该题相同。比如4（100）就代表题目3和去年的有不同、5（101）就代表题目1和题目3和去年的有不同。而BBS热衷于给自己找麻烦，他要选择连续一段的几本五三一起刷，并且要求，所有选择的五三的特征中的所有m位中每一位出现1的次数都相同。他又想去刷最多的书，请你告诉他，他最多能刷多少本书？

输入格式：

第一行为两个整数 n、m，接下来的n行为 n 个整数，表示每本五三的特征。

输出格式：

一个整数，表示BBS最多能刷几本书。

样例输入

样例输出

7 3

样例解释：

这7本五三的特征分别为111,110,111,010,001,100,010。选择第3本至第6本五三，这些五三的特征中每一位都出现了2次1。当然，选择第4本到第6本也是可以的，这些五三的特征中每一位都出现了1次1。只是这样子BBS刷的书的数量就少了，他就会不高兴。

数据范围：

对于 100%的数据：1<=n<=100000，1<=m<=30。

首先是题意的转换，怎么去寻找最大的距离

那么我们看例子

转化为2进制

111

110

111

010

001

100

010

每位求前缀和

111

221

332

342

343

443

453

分别减去最右边的数

000

110《----

110

120

010
110《----

120

就可以发现是2和6是最远的相同数字，那么只用6-2=4即可算出答案

那究竟是为什么呢？

显然，如果一个区间[x,y]能满足要求，那么b[y][i]-b[x-1][i]（b数组是前缀和数组，1<=i<=m）必须相等

设b[y][i]=b[x-1][i]+z，那么b[y][i]-b[y][1]=(b[x-1][i]+z)-(b[x-1][1]+z)=b[x-1][i]-b[x-1][1]

这样就证明了上面那个猜想

这样问题就转成了，给定一个矩阵a[n][m]，求对于a[i][j]，找出与它相同的，k最小的a[k][j]（1<=j<=m）

如果不是一个矩阵，而是一个数组，那么随便做

是矩阵我们就需要对a[i][j](1<=j<=m)进行哈希成一个数，存一下它的最小值

为了避免冲突，我们需要拉链

注意，（1）ans至少为1，因为只要有数，它的答案至少都是1。（2）给hash加入00000这种情况

#include<iostream>
#include<cstdio>
using namespace std;
const int mod=5000007;
int a[100101],b[100010][32],ans=0,m,n,k=0;
int hash[5000010],g[100100][31],next[100100],fro[100100];
void ins(int x,int y)
{
    for(int i=hash[x];;i=next[i])
        if(!i)
        { 
            next[++k]=hash[x];hash[x]=k;fro[k]=y;
            for(int j=1;j<=m;j++)g[k][j]=b[y][j]-b[y][1];
            break;
        }
        else
        {
            bool ok=0;
            for(int j=1;j<=m;j++)if(g[i][j]!=b[y][j]-b[y][1]){ok=1;break;}
            if(!ok)break;
        }
}
int Find(int x,int y)
{
    for(int i=hash[x];i;i=next[i])
    {
        bool ok=0;
        for(int j=1;j<=m;j++)if(g[i][j]!=b[y][j]-b[y][1]){ok=1;break;}
        if(!ok)return y-fro[i];
    }
}
int main()
{
    //freopen("cct.in","r",stdin);freopen("cct.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)b[i][j]=b[i-1][j]+((a[i]>>(j-1))&1);
    ins(0,0);
    for(int i=1;i<=n;i++)
    {
        int tot=0;
        for(int j=1;j<=m;j++)tot=(tot+(b[i][j]-b[i][1])*j)%mod;
        ins(tot,i);
    }
    for(int i=1;i<=n;i++)
    {
        int tot=0;
        for(int j=1;j<=m;j++)tot=(tot+(b[i][j]-b[i][1])*j)%mod;
        ans=max(ans,Find(tot,i));
    }
    printf("%d",ans);
    return 0;
}

View Code

MHM

LGL今天一共要上n节课，这n+1节课由0标号至n。由于过度劳累，除了第0节课和第n节课，LGL还打算睡上m节课，所以他做了一个睡觉计划表。通过小道消息，LGL得知WQ今天会在学校中检查，所以他想少睡k节课。但是由于某些原因，他又想使相邻的两节睡觉的课之间上的课数量的最小值最大。由于他很困，所以他请你来帮他计算这个值。

输入格式：

第一行为三个整数 n、m、k，接下来的m行为m个整数a_i，表示睡觉计划表中LGL想要睡觉的课。

输出格式：

一个整数，表示题目所求的值。

样例输入

样例输出

25 5 2

样例解释：

选择第2节和第14节不睡觉，这样子相邻的两节睡觉的课之间上的课数量的最小值为3，即第17节和第21节之间和第21节到第25节之间。没有答案更大的删除方案。

数据范围：

对于100%的数据：1<=n<=10⁹，0<=k<=m<=50000，0<a_i<n。

跳石头，二分答案+check

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,k,a[50010];
bool check(int x)
{
    int y=0,z=k;
    for(int i=1;i<=m+1;i++)
    {
        if(a[i]-a[y]-1<x)z--;
        else y=i;
    }
    if(z>=0)return 1;
    return 0;
}
int main()
{
    //freopen("mhm.in","r",stdin);freopen("mhm.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)scanf("%d",&a[i]);
    a[0]=0;a[m+1]=n;sort(a,a+m+2);
    int l=0,r=n+1;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid))l=mid+1;
        else r=mid;
    }
    printf("%d",l-1);
    return 0;
}

View Code

AAFA

YYH有n道题要做。每一道题都有一个截止日期t，只要在该日期之前做完，他的父亲LRB就会奖励他w元钱。令人惊讶的是，每一道题他都只需要1秒来做。请问他最多能从父亲那里拿到多少钱？

输入格式：

第一行为一个整数 n，接下来的n行每一行都有两个数t_i和w_i，分别表示第i题的截止日期和奖励。

输出格式：

一个整数，表示YYH的最大获利。

样例输入

样例输出

2 10

1 5

1 7

样例解释：

第1秒做第3道题，第2秒做第1道题。

数据范围：

对于 100%的数据：1<=n、t_i 、w_i <=100000。

从后往前遍历时间轴，如果该秒有题，那么把该秒的奖励加入大根堆，然后对于每一秒，取出最大的值表示做这道题

因为对于某个时间，在这个时间以前都是可以做这道题的，所以很明显，对于每一秒，取最大值即可

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue<int> q;
int n;long long ans=0ll;
struct xxx{
    int t,w;
}f[100100];
bool cmp(xxx a,xxx b){return a.t>b.t;}
int main()
{
//    freopen("aafa.in","r",stdin);freopen("aafa.out","w",stdout);
    scanf("%d",&n);int y=1;
    for(int i=1;i<=n;i++)scanf("%d%d",&f[i].t,&f[i].w);
    sort(f+1,f+n+1,cmp);
    for(int i=100000;i>=1;i--)
    {
        while(i==f[y].t){q.push(f[y].w);y++;}
        if(!q.empty()){ans+=(long long)q.top();q.pop();}
    }
    cout<<ans;
    return 0;
}

View Code

ZZI

YYH拿到了父亲给的钱欣喜若狂，把这些钱拿来造了n栋房子。现在他要给这些房子通电。他有两种方法：第一种是在房间里搭核电发电机发电，对于不同的房子，他需要花不同的代价V_i；，第二种是将有电的房子i的电通过电线通到没电的房子j中，这样子他需要花的代价为a_ij。他现在请你帮他算出他最少要花多少钱才能让所有的房子通上电。

输入格式：

第一行为一个整数 n。接下来的n行为 n 个整数v_i，再接下来的n行每行n个数，第i行第j列的数表示a_ij。

输出格式：

一个整数，表示最小代价。

样例输入

样例输出

4
5

3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

样例解释：

在第4栋房子造核电发电机，再将其他三栋房子通过电线连向它。

数据范围：

对于 100%的数据：1<=n<=300，1<=v_i，a_ij<=100000，保证a_ii=0，a_ij=a_ji。

建一个0号节点，把每个节点向它连一条权值为Vi的无向边，对于每两个点，连一条权值为a[i][j]的无向边，跑最小生成树

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[310][310],d[310],ans=0;
bool used[310];
int main()
{
    //freopen("zzi.in","r",stdin);freopen("zzi.out","w",stdout);
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i][0]);a[0][i]=a[i][0];a[0][0]=0;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);
    memset(d,127,sizeof(d));d[0]=0;
    for(int i=0;i<=n;i++)
    {
        int u=-1;
        for(int j=0;j<=n;j++)if(!used[j]&&(u==-1||d[j]<d[u]))u=j;
        ans+=d[u];used[u]=1;
        for(int v=0;v<=n;v++)d[v]=min(d[v],a[u][v]);
    }
    printf("%d",ans);
    return 0;
}

View Code