2017 清北济南考前刷题Day 7 morning

期望得分：100+50+20=170

实际得分：10+50+20=80

1. 纸牌

题目描述

在桌面上放着n张纸牌，每张纸牌有两面，每面都写着一个非负整数。你的邪王真眼可以看到所有牌朝上的一面和朝下的一面写的数字。现在你需要将一些牌翻过来，使得所有牌朝上的一面中，至少有一半（≥n/2）的数字是一样的。请你求出最少需要翻几张牌，或者判断无解。

注意：在翻牌的时候，你不能把牌扔掉，不能偷偷把别的牌放进来，也不能用笔涂改牌上面的数字。

输入格式

第一行包含一个整数n，表示牌的数量；

接下来n行，每行两个非负整数a_i, b_i，表示每张牌上写的两个数字，a_i对应朝上的一面，b_i对应朝下的一面。

输出格式

如果有解，则输出一个整数，表示最少的翻牌次数，否则输出Impossible。

样例输入1

1 2

2 1

3 4

样例输出1

样例解释1

把第一张牌翻过来，那么就有两个2一个3朝上了，2的数量超过了半数。

样例输入2

1 2

3 4

5 6

样例输出2

Impossible

样例解释2

所有数字都只有一个，因此相同的数字数超过半数是不可能的。

最多只有四种数的个数会超过n/2，

所有数先排序，然后枚举，当一个数的个数为n/2时，就用这个数来更新答案

注意：如果正反都为同一个数，这个数只能算1个

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 300001

int a[N],b[N],c[N<<1];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

int main()
{
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    int n,cnt=0;
    read(n);
    for(int i=1;i<=n;++i)
    {
        read(a[i]); c[++cnt]=a[i];
        read(b[i]); if(a[i]!=b[i]) c[++cnt]=b[i];
    }
    sort(c+1,c+cnt+1);
    int ans=n+1,sum=0,m=n+1>>1;
    for(int i=1;i<=cnt;++i)
    {
        if(c[i]==c[i-1])
        {
            ++sum;
            if(sum==m)
            {
                int tot=0;
                for(int j=1;j<=n;++j)  if(a[j]==c[i]) tot++;
                tot=min(tot,m);
                ans=min(ans,m-tot);
            }        
        }
        else sum=1;
    }
    if(ans>n) printf("Impossible");
    else printf("%d",ans);
}

View Code

2. 后缀数组

题目描述

给定一个字符串S，它的长为n，后缀数组的功能是，将其所有后缀按字典序从小到大排好序。我们对其做一点小小的改动：再给定一个数字m，记ss_i表示从S的第i位开始、长度最多为m的子串，我们希望将这些字符串{ss_i}按字典序从小到大排序。举个栗子，当S="abcab"，m=2时，ss_i的值分别为：

ss₁="ab"

ss₂="bc"

ss₃="ca"

ss₄="ab"

ss₅="b"

但是，只是把{ss_i}全部排好序还是太简单了。初始状态下，ss₁~ss_n按顺序排成一行，我们只能通过不断交换某两个相邻字符串的位置来做排序。再举个栗子，把上面提到的ss₁~ss₅排好序的一种方案是：

(0) 原序列："ab", "bc", "ca", "ab", "b"

(1) 交换第3和第4个串："ab", "bc", "ab", ca", "b"

(2) 交换第2和第3个串："ab", "ab", "bc", ca", "b"

(3) 交换第4和第5个串："ab", "ab", "bc", b", "ca"

(4) 交换第3和第4个串："ab", "ab", "b", bc", "ca"

现在，你需要求出，最少通过多少次相邻字符串交换，才能把所有子串{ss_i}排成字典序从小到大的形式。

( ´_ゝ｀)NOIP怎么可能会考后缀数组

输入格式

第一行包含两个整数n和m；

第二行包含字符串S，它的长为n，只包含小写字母。

输出格式

一个整数，表示最少交换次数。

样例输入

5 2

abcab

样例输出

样例解释

样例就是题目描述中提到的例子。

数据范围

对于20%的数据，有n≤10;

对于40%的数据，有n≤100;

对于60%的数据，有n≤5000;

另有10%的数据，有m≤5;

另有10%的数据，S是随机生成的;

对于100%的数据，有1≤m≤n≤50000

把所有子串排好序，答案就是逆序对的个数

注意处理相同子串

唯一的问题是如何对所有子串排序

正解思路：

哈希排序

即归并排序字符串，用二分+哈希值找出两个字符串第一个不同的字母

#include<cstdio>
#include<iostream>

#define N 50001

const int mod=10000019;

int n,m,d;

char s[N];

long long has[N],bit[N];

int a[N],b[N];

long long ans;

int GetHash(int l,int r)
{
    int tmp;
    if(r<=n) 
    {
        tmp=has[r]-has[l-1]*bit[r-l+1]%mod;
        if(tmp<0) tmp+=mod;
    }
    else
    {
        tmp=has[n]-has[l-1]*bit[n-l+1]%mod;
        if(tmp<0) tmp+=mod;
        tmp=1LL*bit[r-n]%mod;
    }
    return tmp;
}

int cmp(int i,int j)
{
    int l=1,r=m,mid,tmp=-1;
    while(l<=r)
    {
        mid=l+r>>1;
        if(GetHash(i,i+mid-1)!=GetHash(j,j+mid-1)) tmp=mid,r=mid-1;
        else l=mid+1;
    }
    if(tmp==-1) return 0;
    char x= i+tmp-1>n ? ' ' : s[i+tmp-1];
    char y= j+tmp-1>n ? ' ' : s[j+tmp-1];
    if(x<y) return -1;
    return 1;
}

void gbsort(int l,int r)
{
    if(l==r) return;
    int mid=l+r>>1;
    gbsort(l,mid);
    gbsort(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid && j<=r)
    {
        d=cmp(a[i],a[j]);
        if(d<=0) b[k++]=a[i++];
        else if(d>0) b[k++]=a[j++],ans+=mid-i+1;
    }
    //printf("%d %d %I64d
",l,r,ans);
    while(i<=mid) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    for(k=l;k<=r;++k) a[k]=b[k];
}

int main()
{
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    bit[0]=1;
    for(int i=1;i<=n;++i) bit[i]=bit[i-1]*27%mod;
    has[1]=s[1]-'a'+1;
    for(int i=2;i<=n;++i) has[i]=(has[i-1]*27+(s[i]-'a'+1))%mod;
    for(int i=1;i<=n;++i) a[i]=i;
    gbsort(1,n);
    std::cout<<ans;
}

View Code

考场思路：

假设当前比较每个子串的第i位

把第i位为a的放到一个vector里，b放到一个vector里……

继续递归下去

时间复杂度 O（n^2 * 26)

那个26 可以去掉，但每一层递归都要开26的vector，实测更慢

不用vector 会MLE

50分代码

#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#define lowbit(x) x&-x

using namespace std;

int n,m,cnt;

#define N 50002

char s[N];

int rank[N],sum[N];

int c[N];

void mysort(int dep,vector<int>v)
{
    int siz=v.size();
    if(!siz) return;
    if(dep==m)
    {
        for(int i=0;i<siz;i++)
            rank[v[i]]=cnt+1;
        cnt++;
        return;
    }
    vector<int>b; 
    int mi=27,mx=-1;
    for(int i=0;i<siz;i++)
    {
        if(v[i]+dep==n+1)  rank[v[i]]=++cnt; 
        else mi=min(mi,s[v[i]+dep]-'a'),mx=max(mx,s[v[i]+dep]-'a');
    }
    for(int i=mi;i<=mx;i++)
    {
        b.clear();
        for(int j=0;j<siz;j++)
            if(v[j]+dep<=n && s[v[j]+dep]-'a'==i) b.push_back(v[j]);
        mysort(dep+1,b);
    }
}

void add(int x)
{
    while(x<=cnt)
    {
        c[x]++;
        x+=lowbit(x);
    }
}

int query(int x)
{
    int tot=0;
    while(x)
    {
        tot+=c[x];
        x-=lowbit(x);
    }
    return tot;
}

int main()
{
//    freopen("sort.in","r",stdin);
//    freopen("sort.out","w",stdout);
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    vector<int>ve;
    for(int i=1;i<=n;i++) ve.push_back(i);
    mysort(0,ve);
    for(int i=1;i<=n;i++) sum[rank[i]+1]++;
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
    //for(int i=1;i<=n;i++) printf("%d ",rank[i]);
    //printf("
");
    //for(int i=1;i<=cnt;i++) printf("%d ",sum[i]);
    //printf("
");
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+= rank[i]==1 ? sum[rank[i]] : sum[rank[i]]-query(rank[i]-1);
        add(rank[i]);
    }
    cout<<ans;
}

View Code

3. 巧克力

题目描述

有一块分成n*m个格子的矩形巧克力，虽然形状上很规整但质量分布并不均匀，每一格有各自的重量，用n*m个正整数表示。你需要将这一整块巧克力切成k小块，要求每块都是矩形，且它们的重量分别为a₁~a_k。一块巧克力的重量等于它包含的所有格子的重量之和。

切巧克力的时候，你可以每次选一块大的巧克力，沿着某条格线横向或纵向将其切成两块小的巧克力。切下来的小块巧克力可以继续切割。切割路线不能是折线或斜线。任何时候当前的所有巧克力块都必须是矩形的。

对于给定的巧克力和分割要求，请你判断是否存在一个切割方案满足上述要求。

输入格式

输入包含多组测试数据。输入文件的第一行包含一个正整数T，表示数据组数；

接下来，每组测试数据的第一行包含3个正整数n, m, k，表示巧克力的长、宽以及它需要被切成多少块；

接下来n行，每行m个正整数，第i行第j个数w_i,j表示巧克力第i行第j列那一格的重量；

接下来一行包含k个正整数a₁~a_k，表示要求切成的每块巧克力的重量。

输出格式

输出T行，表示对每组测试数据的判断结果。如果第i组测试数据存在一种切割方案，则在第i行输出"yes"，否则输出"no"。

样例输入

3 3 4

1 2 3

4 5 6

7 8 9

12 16 8 9

2 2 2

1 1

1 3

样例输出

yes

状压

50%的数据每个格子的w=1

f[i][j][s] 表示用状态为s的巧克力能否拼出 i*j的的矩形

记忆化搜索枚举横切、竖切

根据面积计算新的长宽

100%的数据待填

20暴力

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

int T,n,m,k;

int w[11][11],a[16];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void init()
{
    read(n); read(m); read(k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            read(w[i][j]);
    for(int i=1;i<=k;i++) read(a[i]);
}

namespace solve1
{
    int pos[11],tot[11];
    
    bool ok;
    
    void judge()
    {
        memset(tot,0,sizeof(tot));
        for(int i=1;i<=k-1;i++)
            for(int j=pos[i-1]+1;j<=pos[i];j++)
                tot[i]+=w[1][j];
        for(int j=pos[k-1]+1;j<=m;j++) tot[k]+=w[1][j];
        sort(tot+1,tot+k+1);
        for(int i=1;i<=k;i++)
            if(tot[i]!=a[i]) return;
        ok=true;
    }
    
    void dfs(int sum,int last)
    {
        if(ok) return;
        if(sum==k) { judge(); return; }
        for(int i=last+1;i+k-1-sum<m;i++)
        {
            if(sum==1 && i==2)
            {
                int esa=3;
            }
            pos[sum]=i;
            dfs(sum+1,i);
            if(ok) return;
        }
    }
    
    void work()
    {
        sort(a+1,a+k+1);
        ok=false;
        dfs(1,0);
        puts(ok ? "yes" : "no");
    }
}

namespace solve2
{
    void work()
    {
        int sum=0;
        for(int i=1;i<=k;i++)  sum+=a[i];
        if(sum>n*m) puts("no");
        else puts("yes");
    }
}

int main()
{
    freopen("chocolate.in","r",stdin);
    freopen("chocolate.out","w",stdout);
    read(T);
    while(T--)
    {
        init();
        if(n==1) solve1::work();
        else solve2::work();
    }
}

View Code