玩坏第一题

题意:

给出一个 01 矩阵,求任意交换某几行后其中最大的全 1 矩阵大小。

思路:

本来完全可以有 $O(n^2)$的方法,我却用树状数组” 优化” 成了 $O(n^2logn)$
思路是这样的:求出每个点正左侧有多少 1,将这个值放入每一列对应的树状数组内。接下来枚举矩形的长 l,枚举矩形的左侧 x 坐标,然后在树状数组内查找那一列有多少个点右边有 l 个以上的 1,l 和答案的乘积就是面积。

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

#define MX 1010

using namespace std;

int n,m;
int mat[MX][MX];
int fol[MX][MX];
int sum[MX][MX];

void add(int t,int p,int x)
{
    if(p==0)return;
    for(int i=p;i<MX;i+=i&-i)
        sum[t][i]+=x;
}

int qsm(int t,int p)
{
    int x=0;
    for(int i=p;i>=1;i-=i&-i)
        x+=sum[t][i];
    return x;
}

void input()
{
    char ch;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            ch=getchar();
            while(ch!='0'&&ch!='1')ch=getchar();
            mat[i][j]=ch-'0';
        }
    }
}

void work()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=1;j--)
        {
            if(mat[i][j]==0)fol[i][j]=0;
            else fol[i][j]=fol[i][j+1]+1;
            add(j,fol[i][j],1);
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            ans=max(ans,i*(qsm(j,MX)-qsm(j,i-1)));
    printf("%d\n",ans);

}

int main()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    input();
    work();
    return 0;
}

平方算法请参考:https://www.mina.moe/archives/2723

卡坏第二题

题意:

给出 n(1<=n<=500) 种物品的价值 (价值 1<=pi<=10000),和 m(1<=m<=3e5) 个需要达到的价值和 (Pmax 不超过 4e7),求有多少个价值和可以由那些物品构成 (每种物品有无限个)。
其中有 30 分的数据满足 1<=n<=10,1<=m<=100,最大价值和 Pmax 不超过 2e5
还有 30 分满足 1<=n<=100,1<=m<=300000,最大价值和 Pmax 不超过 4e7
空间限制 64MB

思路:

对于前 30 分的数据,完全可以用普通背包来做。复杂度为 O(nPmax)
但是还有 30 分是不是也可以用背包呢?
貌似不行,因为空间限制太苛刻,而且时间复杂度过高。
这里介绍一个新的名词:位运算背包。
由于这中背包只需要考虑解的存在性,所以我们可以用每一个二进制位表示这个价值能否达到。利用 64 位 CPU 强大的位运算能力,为我们的程序添加 1/64 的常数。
方法是这样的,虽然有点复杂,但是非常直观:
用一个mask数组元素的每一位连续地表示对应物品的价值是否存在,f数组元素的每一位连续地表示对应价值是否存在。当向f[i]转移时,用mask数组每一个元素与f[i]数组靠后的元素进行按位与(要移动mask数组的每个元素(>>和<<)),如果按位与的结果不为 0, 说明 f[i] 可以由之前的某些 f 转移过来,因此可以将复杂度降为 O(nPmax/64)
上代码:

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

#define MX 300003
#define LEN 700000

using namespace std;
typedef long long ll;

const int L=64;
int n,m;
int game[MX],son[MX],mxs;

class force1
{
    public:
    ll f[LEN],mask[4];
    void set_mask(int pos){mask[pos/L]|=((1LL<<ll(pos%L)));}
    int get_ok(int pos)
    {
        ll now=pos/L;
        ll mov=pos%L;
        ll a1=0,b1=0,a2=0,b2=0,a3=0,b3=0,a4=0,b4=0;
        if(now>=0)a1=f[now]&(mask[3]>>(L-mov-1));
        if(now>=1)b1=f[now-1]&(mask[3]<<(mov+1)),a2=(f[now-1]<<(L-mov-1))&mask[2];
        if(now>=2)b2=f[now-2]&(mask[2]<<(mov+1)),a3=(f[now-2]<<(L-mov-1))&mask[1];
        if(now>=3)b3=f[now-3]&(mask[1]<<(mov+1)),a4=(f[now-3]<<(L-mov-1))&mask[0];
        if(now>=4)b4=f[now-4]&(mask[0]<<(mov+1));
        if(a1||a2||a3||a4||b1||b2||b3||b4)return 1;
        return 0;
    }
    void dp()
    {
        for(int i=1;i<=n;i++)set_mask(4*L-game[i]-1);
        f[0]=1;
        for(int i=1;i<=mxs;i++)
            if(get_ok(i))f[i/L]|=(1LL<<(i%L));
        int ans=0;
        for(int i=1;i<=m;i++)if(f[son[i]/L]&(1LL<<(son[i]%L)))ans++;
        cout<<ans<<endl;
    }
}f1;

int main()
{
    freopen("present.in","r",stdin);
    freopen("present.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&game[i]);
    for(int j=1;j<=m;j++)scanf("%d",&son[j]),mxs=max(mxs,son[j]);
    f1.dp();
    return 0;
}

正解是剩余系下的最短路:

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

#define MX 300003

using namespace std;

int n,m,mod=99999999;
int p[MX],s[MX];

void input()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&p[i]),mod=min(mod,p[i]);
    for(int j=1;j<=m;j++)scanf("%d",&s[j]);
}

int dis[MX],inq[MX],q[MX];
void spfa(int frm)
{
    int h=0,t=1,nu,nv;
    memset(dis,0x3f,sizeof(dis));
    q[++h]=frm;
    inq[frm]=1;
    dis[frm]=0;
    while(h>=t)
    {
        nu=q[t++];
        for(int i=1;i<=n;i++)
        {
            nv=(nu+p[i])%mod;
            if(dis[nu]+p[i]<dis[nv])
            {
                dis[nv]=dis[nu]+p[i];
                if(!inq[nv])
                {
                    q[++h]=nv;
                    inq[nv]=1;
                }
            }
        }
        inq[nu]=0;
    }
}

int main()
{
    freopen("present.in","r",stdin);
    freopen("present.out","w",stdout);
    input();
    spfa(0);
    int ans=0;
    for(int i=1;i<=m;i++)
        if(dis[s[i]%mod]<=s[i])ans++;
    cout<<ans<<endl;
    return 0;
}

裱坏第三题

题意:

AddEdge 最近沉迷日本麻将。
麻将是一个四人游玩的游戏。麻将牌由以下四类牌组成:
万子: 一万至九万, 我们用 1m~9m 表示。
索子: 一索至九索, 我们用 1s~9s 表示。
饼子: 一饼至九饼, 我们用 1p~9p 表示。
以上三种为数牌。
字牌: 包括东、南、西、北、白、发、中七种牌, 为了方便, 我们依次用
1c~7c 表示。
以上每种牌各有四张。
麻将和牌时有 14 张牌, 和牌型通常为四面子加一雀头。面子是指顺子 (三
张同色且数字连续的数牌, 如 1p 2p 3p 或 6m 7m 8m, 字牌不能形成顺子) 或刻
子 (三张相同的牌, 如 3s 3s 3s 或 5c 5c 5c), 雀头是一对子即两张相同的牌 (如
1m 1m 或 7c 7c)。
麻将中还有两种特殊和牌型:
七对子: 由七个不同的对子组成 (日本麻将不承认 “龙七对” 手役, 即一杠
子加五对子)。
国士无双: 由 1m 9m 1s 9s 1p 9p 1c 2c 3c 4c 5c 6c 7c 加上这十三张牌中的任
意一张组成。
每局麻将开始时四名玩家各有 13 张牌, 每一轮每名玩家摸一张牌并打出一
张牌。当一副手牌再加上某一张牌构成一个和牌型时, 我们称这副手牌听这张牌。
考虑一副未进行吃、碰、杠等鸣牌操作的手牌, 判断这副手牌可以听哪些牌。注
意: 在此题中, 不能再摸起的牌即每种牌的第五张不能算作听的牌。

思路:

枚举
然而考场上我把 mahjong 打成了 majong,狠狠地掉了 97 分。
为什么不是 100 分?因为我的算法有一定的问题,但遇上了仁慈的 SPJ,在多组数据中,我的代码只错了极少的点。
为什么会错呢?
因为我枚举的策略是:先添牌,固定对子,再看剩下的有没有和牌的可能。在判断和牌的时候,我会先出完所有的对子,再找顺子,但是像 4m,4m,4m,4m,5m,6m,6m,6m,7m,7m,8m,8m 这种情况程序会剩下几张 5m,7m,8m,如果先出顺子才行。
所以必须一下几个策略结合:1. 先出对子,2. 先从左往右出顺子,3. 先从右往左出顺子。这样才可以减少很多出错的可能。
以下是结合 3 中策略的代码:

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

using namespace std;

typedef struct mag
{
    int s[20];
    int p[20];
    int c[20];
    int m[20];
}mahj;

mahj cad;
mahj ting;

bool gsws(mahj a)
{
    if(a.m[1]==1&&a.m[9]==1&&a.s[1]==1&&a.s[9]==1&&a.p[1]==1&&a.p[9]==1&&a.c[1]==1&&a.c[2]==1&&a.c[3]==1&&a.c[4]==1&&a.c[5]==1&&a.c[6]==1&&a.c[7]==1)
    {
        cout<<13<<" "<<"1m 9m 1s 9s 1p 9p 1c 2c 3c 4c 5c 6c 7c"<<endl;
        return 1;
    }
    return 0;
}

bool gsws2(mahj a)
{
    if(a.m[1]>=1&&a.m[9]>=1&&a.s[1]>=1&&a.s[9]>=1&&a.p[1]>=1&&a.p[9]>=1&&a.c[1]>=1&&a.c[2]>=1&&a.c[3]>=1&&a.c[4]>=1&&a.c[5]>=1&&a.c[6]>=1&&a.c[7]>=1)
    {
        return 1;
    }
    return 0;
}

bool qdz(mahj a)
{
    int cnt=0;
    for(int i=1;i<=9;i++)if(a.m[i]==2)cnt++;
    for(int i=1;i<=9;i++)if(a.s[i]==2)cnt++;
    for(int i=1;i<=9;i++)if(a.p[i]==2)cnt++;
    for(int i=1;i<=7;i++)if(a.c[i]==2)cnt++;
    if(cnt==7)return 1;
    return 0;
}

bool checksm(mahj a)
{
    int ok=0;
    for(int i=1;i<=9;i++)
        if(a.m[i]>=3)a.m[i]-=3,ok++;
    for(int i=1;i<=9;i++)
        if(a.s[i]>=3)a.s[i]-=3,ok++;
    for(int i=1;i<=9;i++)
        if(a.p[i]>=3)a.p[i]-=3,ok++;
    for(int i=1;i<=7;i++)
        if(a.c[i]>=3)a.c[i]-=3,ok++;
    for(int i=1;i<=7;i++)
        while(a.m[i]&&a.m[i+1]&&a.m[i+2])
            a.m[i]--,a.m[i+1]--,a.m[i+2]--,ok++;
    for(int i=1;i<=7;i++)
        while(a.s[i]&&a.s[i+1]&&a.s[i+2])
            a.s[i]--,a.s[i+1]--,a.s[i+2]--,ok++;
    for(int i=1;i<=7;i++)
        while(a.p[i]&&a.p[i+1]&&a.p[i+2])
            a.p[i]--,a.p[i+1]--,a.p[i+2]--,ok++;
    if(ok>=4)return 1;
    return 0;
}

bool checkshun(mahj a)
{
    //cout<<a.m[4]<<endl;
    int ok=0;
    for(int i=1;i<=7;i++)
        while(a.m[i]&&a.m[i+1]&&a.m[i+2])
            a.m[i]--,a.m[i+1]--,a.m[i+2]--,ok++;
    for(int i=1;i<=7;i++)
        while(a.s[i]&&a.s[i+1]&&a.s[i+2])
            a.s[i]--,a.s[i+1]--,a.s[i+2]--,ok++;
    for(int i=1;i<=7;i++)
        while(a.p[i]&&a.p[i+1]&&a.p[i+2])
            a.p[i]--,a.p[i+1]--,a.p[i+2]--,ok++;
    for(int i=1;i<=9;i++)
        if(a.m[i]>=3)a.m[i]-=3,ok++;
    for(int i=1;i<=9;i++)
        if(a.s[i]>=3)a.s[i]-=3,ok++;
    for(int i=1;i<=9;i++)
        if(a.p[i]>=3)a.p[i]-=3,ok++;
    for(int i=1;i<=7;i++)
        if(a.c[i]>=3)a.c[i]-=3,ok++;
    if(ok>=4)return 1;
    return 0;
}

bool checkni(mahj a)
{
    int ok=0;
    for(int i=7;i>=1;i--)
        while(a.m[i]&&a.m[i+1]&&a.m[i+2])
            a.m[i]--,a.m[i+1]--,a.m[i+2]--,ok++;
    for(int i=7;i>=1;i--)
        while(a.s[i]&&a.s[i+1]&&a.s[i+2])
            a.s[i]--,a.s[i+1]--,a.s[i+2]--,ok++;
    for(int i=7;i>=1;i--)
        while(a.p[i]&&a.p[i+1]&&a.p[i+2])
            a.p[i]--,a.p[i+1]--,a.p[i+2]--,ok++;
    for(int i=1;i<=9;i++)
        if(a.m[i]>=3)a.m[i]-=3,ok++;
    for(int i=1;i<=9;i++)
        if(a.s[i]>=3)a.s[i]-=3,ok++;
    for(int i=1;i<=9;i++)
        if(a.p[i]>=3)a.p[i]-=3,ok++;
    for(int i=1;i<=7;i++)
        if(a.c[i]>=3)a.c[i]-=3,ok++;
    if(ok>=4)return 1;
    return 0;
}

bool sm(mahj a)
{
    mahj c;
    for(int i=1;i<=9;i++)
    {
        if(a.m[i]>=2)
        {
            c=a;
            c.m[i]-=2;
            if(checksm(c)||checkshun(c)||checkni(c))return 1;
        }
    }
    for(int i=1;i<=9;i++)
    {
        if(a.s[i]>=2)
        {
            c=a;
            c.s[i]-=2;
            if(checksm(c)||checkshun(c)||checkni(c))return 1;
        }
    }
    for(int i=1;i<=9;i++)
    {
        if(a.p[i]>=2)
        {
            c=a;
            c.p[i]-=2;
            if(checksm(c)||checkshun(c)||checkni(c))return 1;
        }
    }
    for(int i=1;i<=7;i++)
    {
        if(a.c[i]>=2)
        {
            c=a;
            c.c[i]-=2;
            if(checksm(c)||checkshun(c)||checkni(c))return 1;
        }
    }
    return 0;
}

void input()
{
    char nam;
    int num;
    memset(&cad,0,sizeof(cad));
    memset(&ting,0,sizeof(ting));
    for(int i=1;i<=13;i++)
    {
        scanf("%d",&num);
        nam=getchar();
        while(nam!='s'&&nam!='m'&&nam!='p'&&nam!='c')nam=getchar();
        if(nam=='s')cad.s[num]++;
        if(nam=='m')cad.m[num]++;
        if(nam=='p')cad.p[num]++;
        if(nam=='c')cad.c[num]++;
    }
}

void output()
{
    int cnt=0;
    for(int i=1;i<=9;i++)if(ting.m[i])cnt++;
    for(int i=1;i<=9;i++)if(ting.s[i])cnt++;
    for(int i=1;i<=9;i++)if(ting.p[i])cnt++;
    for(int i=1;i<=7;i++)if(ting.c[i])cnt++;
    if(cnt==0){cout<<"Nooten"<<endl;return;}
    cout<<cnt<<" ";
    for(int i=1;i<=9;i++)if(ting.m[i])cout<<i<<"m ";
    for(int i=1;i<=9;i++)if(ting.s[i])cout<<i<<"s ";
    for(int i=1;i<=9;i++)if(ting.p[i])cout<<i<<"p ";
    for(int i=1;i<=7;i++)if(ting.c[i])cout<<i<<"c ";
    cout<<endl;
}

void work()
{
    if(gsws(cad))return;
    mahj a;
    for(int i=1;i<=9;i++)
    {
        if(cad.m[i]<=3)
        {
            a=cad;
            a.m[i]++;
            if(qdz(a)||sm(a)||gsws2(a))ting.m[i]++;
        }
        if(cad.s[i]<=3)
        {
            a=cad;
            a.s[i]++;
            if(qdz(a)||sm(a)||gsws2(a))ting.s[i]++;
        }
        if(cad.p[i]<=3)
        {
            a=cad;
            a.p[i]++;
            if(qdz(a)||sm(a)||gsws2(a))ting.p[i]++;
        }
        if(cad.c[i]<=3&&i<=7)
        {
            a=cad;
            a.c[i]++;
            if(qdz(a)||sm(a)||gsws2(a))ting.c[i]++;
        }
    }
    output();
}

int main()
{
    freopen("mahjong.in","r",stdin);
    freopen("mahjong.out","w",stdout);
    int t;
    scanf("%d",&t);
    for(int w=1;w<=t;w++)
    {
        input();
        work();
    }
    return 0;
}
分类: 文章

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注