考前练习-2

t1写挂，t2过了，t3挂了...代码细节是绝对需要注意的啊qwq

---

T1

首先，我们定义dp状态：

$$dp[k][i]$$
其中 $k$ 代表当前位置状态，$i$ 为位置。

• $k=0$ 时，代表此处没有雷，两边也没有雷。
• $k=1$ 时，代表此处没有雷，前面有雷，后面没有雷。
• $k=2$ 时，代表此处没有雷，两边都有雷。
• $k=3$ 时，代表此处没有雷，前面没有雷，后面有雷。
• $k=4$ 时，代表此处就是个雷。

那么由上面可得方程如下：

$$dp[k][i]=\begin{cases} dp[1][i-1]+dp[0][i-1](k=0)\\ dp[4][i-1](k=1)\\ dp[4][i-1](k=2)\\ dp[0][i-1]+dp[1][i-1](k=3)\\ dp[3][i-1]+dp[2][i-1]+dp[4][i-1](k=4)\\ \end{cases}$$

注意第一个的初始化不能为 $1$ 或 $2$，最后一个的状态不能为 $3$ 或 $2$

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e6+5;
const int Q=1e9+7;
char s[N];
ll cnt[5][N],ans;//0 -->0   1-->front(1)   2--> 2  3-->back(1)  4-->mine
int n;
void solve()
{
    if(s[1]=='?')   cnt[0][2]=cnt[3][3]=cnt[4][4]=1;
    else    if(s[1]=='0')   cnt[0][5]=1;
    else    if(s[1]=='1')   cnt[3][6]=1;
    else    if(s[1]=='*')   cnt[4][7]=1;
    for(int i=2;i<=n;++i)
    {
        if(s[i]=='?')
        {
            cnt[0][i]=(cnt[0][i-1]+cnt[1][i-1])%Q;
            if(i!=n)    cnt[3][i]=(cnt[0][i-1]+cnt[1][i-1])%Q;
            cnt[1][i]=cnt[4][i-1];
            if(i!=n)    cnt[2][i]=cnt[4][i-1];
            cnt[4][i]=((cnt[3][i-1]+cnt[2][i-1])%Q+cnt[4][i-1])%Q;
        }
        else
        {
            if(s[i]=='0')   cnt[0][i]=(cnt[0][i-1]+cnt[1][i-1])%Q;
            else    if(s[i]=='1')   
            {
                cnt[1][i]=cnt[4][i-1];
                cnt[3][i]=(cnt[0][i-1]+cnt[1][i-1])%Q;
            }
            else    if(s[i]=='2')   cnt[2][i]=cnt[4][i-1];
            else    if(s[i]=='*')   cnt[4][i]=((cnt[3][i-1]+cnt[2][i-1])%Q+cnt[4][i-1])%Q;
        }
    }
    for(int i=0;i<5;++i)    
        if(i!=3)    ans=(ans+cnt[i][n])%Q;
}
int main()
{
//  freopen("mine.in","r",stdin);
//  freopen("mine.out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    solve();
    cout<<ans;
    return 0;
}

---

T2

之前做过的题，然后可以有多种做法，我写的是最短路。

可以很容易证明，对于一个点来说，该点的水的高度取决于四周的水（或者地）的高度（同一个方向水和地取最大）的最小值。
那么很容易直接最短路过去。
注意在更新某个节点的时候，我们更新出来的是当前点的水值和高度值之间的最大值。

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll  long long
using namespace std;
const int N=305;
const int M=372100;
const ll inf=0x3f3f3f3f3f;
struct data{
    int x,y;
}dot[M];
int m,n;
ll dis[N][N];
int fx[5]={0,0,0,1,-1};
int fy[5]={0,1,-1,0,0};
bool ind[N][N];
int map[N][N];
void bfs(int x)
{
    queue<data> q;
    data k;k.x=k.y=1;
    q.push(k);
    while(!q.empty())
    {
        data k=q.front();q.pop();
        dis[k.x][k.y]=max(dis[k.x][k.y],map[k.x][k.y]);
        for(int k=1;k<=4;++k)
        {
            int x=k.x+fx[k],y=k.y+fy[k];
            if(x<1||x>n)    continue;
            if(y<1||y>m)    continue;
            if(dis[x][y]>dis[k.x][k.y])
            {
                dis[x][y]=dis[k.x][k.y];
                if(!ind[x][y])
                {
                    ind[x][y]=1;
                    data f;f.x=x,f.y=y;
                    q.push(f);
                }
            }
        }
        ind[k.x][k.y]=0;
    }
}
inline int read()
{
    int x=0,y=1;char c=getchar();
    while(c<'0'||c>'9') 
    {
        if(c=='-')  y=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')   x=x*10+c-'0',c=getchar();
    return x*y;
}
void init()
{
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            map[i][j]=read();
    for(int i=1;i<=n;++i)
        dis[i][1]=max(map[i][1],0),dis[i][m]=max(map[i][m],0);
    for(int j=1;j<=m;++j)   
        dis[1][j]=max(map[i][j],0),dis[1][j]=max(map[n][j],0);
    for(int i=2;i<n;++i)
        for(int j=2;j<m;++j)    dis[i][j]=inf;
}
int main()
{
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
    n=read(),m=read();
    init();
    spfa();
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            ll ans=(dis[i][j]-(ll)map[i][j]);
            printf("%lld ",ans<0? 0:ans);
        }
        puts("");
    }
    return 0;
}

---

T3

...暴力没过一个点...心累。

首先，我们知道，这题对于 $x_i$ 肯定要分解质因数。
然后我们再想，怎么统计集合里面和这个数互质的数？？？
互质的不好算，我们想想看，用补集转化一下，不就是和 $x_i$ 有相同质因子的个数嘛？
这个好像还可做一些...
所以我们可以统计每个值的倍数个数，然后容斥原理计算答案...

#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e6+5;
const int M=5e5+5;
int cnt[500005];
long long ans;
int piece[M][40],sum[M];
int a[N],m,n,x;
bool in[N];
bool vis[M];
void pre_tab()
{
    for(int i=2;i<M;++i)
    {
        if(vis[i])  continue;
        for(int j=1;i*j<M;++j)
        {
            int f=i*j;
            vis[f]=1;
            piece[f][++sum[f]]=i;
        }
    }
}
void dfs(int now,int num,int nowit,int ty)
{
    if(now>sum[x])
    {
        if(ty==-1)
            cnt[num]--;
        ans+=nowit*cnt[num];
        if(ty==1)
            cnt[num]++;
        return ;
    }
    dfs(now+1,num,nowit,ty);
    dfs(now+1,num*piece[x][now],-nowit,ty);
}
inline int read()
{
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')   x=x*10+c-'0',c=getchar();
    return x;
}
int main()
{
//  freopen("gcd.in","r",stdin);
//  freopen("gcd.out","w",stdout);
    pre_tab();
    n=read(),m=read();
    for(int i=1;i<=n;++i)   a[i]=read();//broken(i);
    for(int i=1;i<=m;++i)
    {
        x=read();
        if(!in[x])  
        {
            in[x]=1;x=a[x];
            dfs(1,1,1,1);
        }
        else    
        {
            in[x]=0;x=a[x];
            dfs(1,1,-1,-1);
        }
        printf("%lld\n",ans);
    }
    return 0;   
}