## $Round1~D1T1$外星千足虫

\(\mathtt{BSOJ2793}\)——高斯消元解异或方程组

有\(n\)个数\(\{a_i\}\)

给出\(m\)个信息，每个信息给出\(\displaystyle{(\sum_{i=1}^m a_{b_i})\bmod 2}\)(\(\{b_i\}\)是\({1,2,\cdots,n}\)的子集)

求最少几次操作即可确定可能取值

\(70pts'\)

给出的信息可以转化为\(\displaystyle{\oplus_{i=1}^m a_{b_i}}\)

因此问题转化为求异或方程组最少几行就可以有解

高斯消元求自由元个数即可

复杂度\(O(n^3)\)

\(100pts'\)

考虑高斯消元集合异或操作太浪费，使用\(bitset\)优化异或的特殊情况

复杂度\(O(\frac{n^3}{64})\)

int n,m,ans;
bitset<N> a[M];
int main(void){
    re int i,j;n=read()+1,m=read();
    for(i=1;i<=m;++i)
        for(j=1;j<=n;++j)a[i][j]=gc();
    for(i=1;i<n;++i){
        for(j=i;j<=m;++j)if(a[j][i])break;
        ans=max(ans,j);
        if(j>m)return puts("Cannot Determine"),0;
        if(i^j)swap(a[i],a[j]);
        for(j=1;j<=m;++j){if(i==j||!a[j][i])continue;a[j]^=a[i];}
    }
    printf("%d\n",ans);
    for(i=1;i<n;++i)puts((a[i][n])?"?y7M#":"Earth");
    return 0;
}

把8行的初始设为了i+1

\(\mathtt{BSOJ2794}\)——补集思想简化状态+逆向递推计数dp

求长度为\(n\)的排列满足任意\(i\in[2,n-1]\)有\(a_i>a_{i-1}\&a_i>a_{i+1}\)或\(a_i<a_{i-1}\&a_i<a_{i+1}\)

形象来说本题是要我们求//\和//的数量

首先考虑若排列\(\{a_i\}\)满足要求那么\(\{b_i\}(b_i=n-a_i)\)也满足要求

那么我们单求//就可以了(所以第一个不为\(1\))

紧接着我们会发现这个计数题正着做不好做，但构造任意一个序列是容易的所以我们逆推,用反构造(合法\(\rightarrow\)合法)的过程去实现\(dp\)

已经有\(1\rightarrow i\)首位为\(j\)的序列,设情况有\(dp_{i,j}\)个

• \(j-1\)不是首位,那么交换\(j-1,j\)没有影响,贡献\(dp_{i,j-1}\)
• \(j-1\)是首位,那么去掉\(j\),就得到一个//\序列,\(a_i\rightarrow i-a_i\)即可,贡献\(dp_{i-1,i-j+1}\)

注意滚动一下

int main(void){
    re int i,j,now=0;
    n=read(),mod=read();dp[now][2]=1;
    for(i=3;i<=n;++i){
        now^=1;
        for(j=2;j<=i;++j)dp[now][j]=Mod(dp[now][j-1]+dp[now^1][i-j+1]);
    }
    for(i=2;i<=n;++i)ans=Mod(ans+dp[now][i]);
    printf("%d\n",Mod(ans+ans));
    return 0;
}

\(\mathtt{BSOJ2795}\)——最短路+拓扑排序

给出一个有向图,有一些点必须在限制他的点之后到达他,求\(1\rightarrow n\)的最短路

考虑到限制实际上是让我们满足限制关系\(DAG\)拓扑序的去完成最短路

因此我们就魔改最短路，加入\(Topsort\)的过程即可

设\(dis_x\)表示\(1\rightarrow x\)的最短路(中间未\(Topsort\)完不一定满足要求)

\(real_x\)表示满足拓扑序关系下\(1\rightarrow x\)的实际最短路(限制我的都被走完)

注意:每次用\(real\)去更新\(dis\),只有被限制的更新完了才去更新别的，这样才保证拓扑序

核心

inline void Dijkstra(void){
    re int i,x,v,d;
    for(i=1;i<=n;++i)dis[i]=INF;
    q.push((Node){1,dis[1]=real[1]=0});
    while(!q.empty()){
        x=q.top().x,d=q.top().dis,v=max(dis[x],real[x]),q.pop();
        if(v^d)continue;
        for(i=h[x];i;i=e[i].next){
            re int y=e[i].to;
            if(v+e[i].v<dis[y]){dis[y]=v+e[i].v;if(!deg[y])q.push((Node){y,max(dis[y],real[y])});}
        }
        for(re int y:g[x]){real[y]=max(real[x],v);if(!--deg[y])q.push((Node){y,max(real[y],dis[y])});}
    }
}

\(\mathtt{BSOJ3301}\)——Tarjan+二维hash+虚点技巧

\(n*m\)的方格中,有些点很特殊

• 可以到达同行任意点

• 可以到达同列任意点

• 可以到达八连通的点

  问从任意点出发可以到达最多点数

如果把每个点向其联通的连边，缩点后求最长路就是答案

考虑优化建图，可以发现连边的冗杂在于行列连边，因此我们对每行每列建虚点，边数就与特殊点数有关

n=read(),read(),read();
for(i=1;i<=n;++i){
    x[i]=read(),y[i]=read(),opt[i]=read();
    hash[Find(x[i],y[i])]=fa[i]=i;v[i]=1;
    if(opt[i]==1)Sx[x[i]]?++v[fa[i]=Sx[x[i]]]:Sx[x[i]]=i;
    else if(opt[i]^3)Sy[y[i]]?++v[fa[i]=Sy[y[i]]]:Sy[y[i]]=i;
}//Sx,Sy分别指向他所在行列的第一个点
for(i=1;i<=n;++i){
    if(opt[i]==3){
        for(dir=0;dir<8;++dir)if(hash[res=Find(x[i]+dx[dir],y[i]+dy[dir])])AddEdge(fa[i],fa[hash[res]]);
        if(Sx[x[i]])AddEdge(Sx[x[i]],fa[i]);if(Sy[y[i]])AddEdge(Sy[y[i]],fa[i]);
    }
    else if(opt[i]==1&&Sy[y[i]])AddEdge(Sy[y[i]],fa[i]);
    else if(opt[i]==2&&Sx[x[i]])AddEdge(Sx[x[i]],fa[i]);
}

其中\(Find\)是hash表上

inline int Find(re int a,re int b){
    re int z=(a*13+b*19)%N;
    while(hash[z]&&(x[hash[z]]^a||y[hash[z]]^b))if(++z==N)z=0;
    return z;
}

\(\mathtt{BSOJ3301}\)——前缀和+主席树

给出\(n*m\)的矩阵,多次询问指定区间选数大于等于指定值得最少选数个数

对\(50\%\)数据，\(n,m\le 200\)

对另\(50\%\)数据,\(n=1,m\le 5*10^5\)

对前半部分暴力从大到小枚举权值用二维前缀和试减即可

后半部分利用二分最小值+主席树求和，可以用一个\(\log\)的主席树上划分即可

\(\mathtt{BSOJ3303}\)——费用流+拆点

简述

给一张\(DAG\),有边权,每个点有出发点权.求最小代价使得每个点都被经过。

Solution

遇到点权就拆入出点

建图:对起点\((S,i',1,a_i)\):表示从\(i\)直接出发

\((S,i,1,0),(i',T,1,0)\)

对每条边\((x',y,1,w_{x,y})\)

跑最小费用流即可

Code

n=read(),m=read(),S=0,T=n<<1|1,P=T+1;
for(i=1;i<=n;++i)a[i]=read(),AddEdge(S,i+n,1,a[i]);
for(i=1;i<=n;++i)AddEdge(S,i,1,0),AddEdge(i+n,T,1,0);
while(m--){
    x=read(),y=read(),z=read();
    if(x>y)swap(x,y);
    if(z<a[y])AddEdge(x,y+n,1,z);
}

\(\mathtt{BSOJ3318}\)——数论综合(卢卡斯+CRT)

求\(G^{\sum\limits_{d|n}\binom{n}{d}}\pmod {999911659}(G,n\le 10^9)\)

首先由扩展欧拉定理\(G^{\sum\limits_{d|n}\binom{n}{d}}\equiv G^{\sum\limits_{d|n}\binom{n}{d}~\bmod{~999911659}}\pmod {999911659}\)

因为\(Lucas\)的复杂度是\(O(p\log_p n)\)考虑缩小模数

\(\because 999911658=2×3×4679×35617\)

所以可以分别求组合数再\(CRT\)一下

有一个多组数据版本\(\mathtt{BSOJ4834}\)需要预处理对每个模数的逆元等

\(\mathtt{BSOJ3319}\)——kd树

多组询问离每个点曼哈顿距离最大点

这个是裸题不用题

\(\mathtt{BSOJ3320}\)——双向链表+细节+模拟

简述个鬼

思维导图版本

我写之前学习了loj这位大佬的提交(我不会说是我写到一半发现无懈可击不怎么会写),然后后来就把其他部分改得跟他一致了(他写得太精简了，下面会说明),希望为他起一个注解的作用

这是一个类似(抄袭)三国杀的游戏

我们一句一句的来看一只猪有那些信息:

主猪（MP）：自己存活的情况下消灭所有的反猪。

忠猪（ZP）：不惜一切保护主猪，胜利条件与主猪相同。

反猪（AP）：杀死主猪。

这是类型

游戏开始时候，每个玩家手里都会有4张牌，且体力上限和初始体力都是4。

这是体力，和牌

1.如果没有猪哥连弩，每个出牌阶段只能使用一次“杀”来攻击；

2.任何牌被使用后被弃置（武器是装备上）；

牌分为手牌(消耗品),武装(永久品):只有猪哥连弩

◎献殷勤：使用无懈可击挡下南猪入侵、万箭齐发、决斗；使用无懈可击抵消表敌意；

◎表敌意：对某个角色使用杀、决斗；使用无懈可击抵消献殷勤；

◎跳忠：即通过行动表示自己是忠猪。跳忠行动就是对主猪或对某只已经跳忠的猪献殷勤，或者对某只已经跳反的猪表敌意；

◎跳反：即通过行动表示自己是反猪。跳反行动就是对主猪或对某只已经跳忠的猪表敌意，或者对某只已经跳反的猪献殷勤；

忠猪不会跳反，反猪也不会跳忠；不管是忠猪还是反猪，能够跳必然跳；

除了主猪外只有通过跳身份的办法来显示身份

所以我们定义一只猪

struct Pig{
    char type,card[M],weapon,show;//类型,卡,武器有无,我表示(不表示0)我是什么身份(1忠/主猪,2反猪,3类反猪)
    int heal,cardnum;//血量,卡数
}a[N];

他的行为有抽牌，用牌，找牌(并用掉)

struct Pig{
    char type,card[M],weapon,show;//类型,卡,武器有无,我表示(不表示0)我是什么身份
    int heal,cardnum;//血量,卡数
    inline void Delete(re int&x){re int i;--cardnum;for(i=x;i<=cardnum;++i)card[i]=card[i+1];--x;}//丢掉第x张牌
    inline char Find(re char a){re int i;for(i=1;i<=cardnum;++i)if(card[i]==a)return Delete(i),1;return 0;}//检查手牌有没有a
    inline void Get(re int x){while(x--){card[++cardnum]=st[++top];if(top==m)--top;}}//牌堆摸x张
}a[N];

另外我们用一个双向链表来维护猪之间位置关系，这样删除很方便

接下来看手牌

◎基本牌：

『桃(P)』：在自己的回合内，如果自己的体力值不等于体力上限，那么使用一个桃可以为自己补充一点体力，否则不能使用桃；桃只能对自己使用；在自己的回合外，如果自己的血变为0或者更低，那么也可以使用；

『杀(K)』：在自己的回合内，对攻击范围内除自己以外的一名角色使用。如果没有被『闪』抵消，则造成1点伤害。无论有无武器，杀的攻击范围都是1；

『闪(D)』：当你受到杀的攻击时，可以弃置一张闪来抵消杀的效果；

◎锦囊牌：

『决斗(F)』：出牌阶段，对除自己以外任意一名角色使用，由目标角色先开始，自己和目标角色轮流弃置一张杀，首先没有杀可弃的一方受到1点伤害，另一方视为此伤害的来源；

『南猪入侵(N)』：出牌阶段，对除你以外所有角色使用，按逆时针顺序从使用者下家开始依次结算，除非弃置一张杀，否则受到1点伤害；

『万箭齐发(W)』：和南猪入侵类似，不过要弃置的不是杀而是闪；

『无懈可击(J)』：在目标锦囊生效前抵消其效果。每次有一张锦囊即将生效时，从使用这张锦囊的猪开始，按照逆时针顺序，依次得到使用无懈可击的机会；

效果：用于决斗时，决斗无效并弃置；用于南猪入侵或万箭齐发时，当结算到某个角色时才能使用，当前角色不需弃置牌并且不会受到伤害（仅对一个角色产生效果）；用于无懈可击时，成为目标的无懈可击被无效。

我们会发现『杀(K)』『南猪入侵(N)』『万箭齐发(W)』攻击力都是1,新建一个功能\(Defend(x,y)\)表示\(x\)成功伤害\(y\),注意到这一次可能触发

如果自己的血变为0或者更低，那么也可以使用桃

还可能杀死它猪

inline void Defend(re int x,re int y){//x砍y一点血
    if(!--a[y].heal)a[y].heal+=a[y].Find('P');//能用桃就用
    if(!a[y].heal)Kill(x,y);//杀死了
}

对于\(x\)杀死\(y\)，先看胜利条件

主猪（MP）：自己存活的情况下消灭所有的反猪。

忠猪（ZP）：不惜一切保护主猪，胜利条件与主猪相同。

反猪（AP）：杀死主猪。

再判一下几种情况

◎玩家死亡：如果该玩家的体力降到0或者更低，并且自己手中没有足够的桃使得自己的体力值回到1，那么就死亡了，死亡后所有的牌（装备区，手牌区）被弃置；

◎奖励与惩罚：反猪死亡时，最后一个伤害来源处（即使是反猪）立即摸三张牌。忠猪死亡时，如果最后一个伤害来源是主猪，那么主猪所有装备牌、手牌被弃置；

◎注意，一旦达成胜利条件，游戏立刻结束，因此即使会摸3张牌或者还有牌可以用也不用执行了。

inline void Kill(re int x,re int y){//x把y杀了的结果
    if(a[y].type=='M')Print();//忠猪被杀
    if(a[y].type=='F'){
        if(!(--enemynum))Print();//敌人杀完
        a[x].Get(3);//没结束要摸牌
    }
    else if(a[x].type=='M'&&a[y].type=='Z')a[x].cardnum=a[x].weapon=0;//我杀我忠猪
    r[l[y]]=r[y],l[r[y]]=l[y];//去掉y
}

最困难的判定是无懈可击，我们要看\(x\)可不可以攻击\(y\),首先看\(y\)可不可以被队友(这地方就涉及到显示的身份)无效，然后再看这个无效可不可以被成功无效(成功无效就代表之后再没有一个无效)

我们会发现这是一个递归的过程，重点是理解无效本身是一种会被无效的行为

inline char WXKJ(re int x,re int y){
    re int i;re char first;
    for(i=x,first=1;(first||(i^x));i=r[i],first=0)
        if((!y?CanDefend(i,x):MyPig(i,y))&&a[i].Find('J')){//有y是看友军可不可以无效别人攻击保护你，没y是看敌人可不可以无效你的无效,递归次数%2表示到底实在阻止这场攻击发生
            a[i].show=(a[i].type=='F'?2:1);
            return !WXKJ(i,0);//你不能无效我才发动行为(包括无效)成功
        }
    return 0;
}

在这里判定别人是什么猪就要用到别人显示的身份(而不是真实身份)

inline char CanDefend(re int x,re int y){
    return ((a[x].type=='M'&&(a[y].show==2||a[y].show==3))||(a[x].type=='Z'&&a[y].show==2)||(a[x].type=='F'&&a[y].show==1));
}
inline char MyPig(re int x,re int y){
    return (((a[x].type=='M'||a[x].type=='Z')&&a[y].show==1)||(a[x].type=='F'&&a[y].show==2));
}

然后具体写每个手牌的操作就可以了

Code

\(\mathtt{BSOJ3323}\)——计数dp,巧妙思维

求\(n\)位逐位递增能被\(P\)整除的个数

首先注意到一个性质，合法的数，都可以看做小于等于\(9\)个形如\(000\dots111\)的数累加

设\(cnt_i=\sum[x形如"000\cdots111"][x\equiv i\pmod{p}]\)

考虑做背包，设\(f_{i,j,k}\)表示考虑余数为\(0\cdots i\)的的后缀选\(k\)个和的余数为\(j\)的方案数

枚举每一种余数个数即可转移

\(\displaystyle f_{i,j,k}=\sum_{l=0}^k\binom{cnt_i+l-1}{l}f_{i-1,j−il,k-l}\)注意第二维可能越界

答案很显然

\[Ans=\sum_{i=0}^8f_{p-1,0,i}
\]

for(i=0;i<p;++i){
        C[i][0]=1;
        if(cnt[i])for(j=1;j<9;++j)C[i][j]=1ll*C[i][j-1]*cnt[i]%mod*inv[j]%mod,cnt[i]=Mod(cnt[i]+1);
    }
    dp[now][first][0]=1;
    for(i=0;i<p;++i){
        now^=1;for(j=0;j<p;++j)for(k=0;k<9;++k){
            dp[now][j][k]=0;
            for(l=0;l<=k;++l)dp[now][j][k]=(dp[now][j][k]+1ll*dp[now^1][(j-(i*l%p)+p)%p][k-l]*C[i][l])%mod;
        }
    }
    for(i=0;i<9;++i)ans=Mod(ans+dp[now][0][i]);printf("%d\n",ans);

Code

这里