玩坏第一题
题意：
给出一个 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 条评论