\(T2\) 膜拜大佬

题意：\(m\) 次查询一个字符串是否在给定的 \(n\) 个字符串中。

暴力的用 \(map\) 容器去维护，简直是弱化版的 \(csp-j\ 2021 \ T3\)。

map mp;
int n,m;
string s;
int main(){
    freopen("dalao.in","r",stdin);
    freopen("dalao.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        cin>>s;
        mp[s]=1;
    }
    m=read();
    for(int i=1;i<=m;i++){
        cin>>s;
        cin>>s;
        cin>>s;
        if(mp[s]){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }
    }
    return 0;
}

\(T3\) 走迷宫

一个标准的 \(bfs\)，无脑搜就可以了。

对于传送门，可以发现，有传送门一定要传送，设一组传送门 \(d_1,d_2\)，不难发现，当 \(d_2\) 周围有空地可以去时，是能够回到 \(d_1\) 的，所以标记时，只标记进入传送门的点，不标记离开传送门的点。

int n,m;
char mp[305][305];
bool vis[305][305];
struct gate{
    int x1,y1;
    int x2,y2;
    int cnt;
}gt[30];
struct node{
    int x,y,t;
    node(int x,int y,int t):x(x),y(y),t(t){}
};
int sx,sy,ex,ey;
queue q;
int ans=0x3f3f3f3f;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
inline void bfs(){
    while(!q.empty()) q.pop();
    q.push(node(sx,sy,0));
    while(!q.empty()){
        node tmp=q.front();
        q.pop();
        int x=tmp.x,y=tmp.y,t=tmp.t;
        if(x==ex&&y==ey){
            ans=min(ans,t);
            continue;
        }
        for(int i=0;i<4;i++){
            int xx=x+dx[i],yy=y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&mp[xx][yy]!='#'){
                //printf("%d %d %d %d\n",x,y,xx,yy);
                vis[xx][yy]=1;
                if(mp[xx][yy]<='Z'&&mp[xx][yy]>='A'){
                    int ch=mp[xx][yy]-'A'+1;
                    if(gt[ch].x1==xx&>[ch].y1==yy){
                        q.push(node(gt[ch].x2,gt[ch].y2,t+1));
                    }
                    else{
                        q.push(node(gt[ch].x1,gt[ch].y1,t+1));
                    }
                }
                else{
                    q.push(node(xx,yy,t+1));
                }
            }
        }
    }
    if(ans==0x3f3f3f3f){
        printf("-1\n");
    }
    else{
        printf("%d\n",ans);
    }
    return;
}
int main(){
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=30;i++){
        gt[i].x1=gt[i].y1=gt[i].y1=gt[i].y2=gt[i].cnt=0;
    }
    for(int i=1;i<=n;i++){
        scanf("%s",mp[i]+1);
        for(int j=1;j<=m;j++){
            if(mp[i][j]<='Z'&&mp[i][j]>='A'){
                int ch=mp[i][j]-'A'+1;
                if(gt[ch].cnt==0){
                    gt[ch].x1=i,gt[ch].y1=j;
                    gt[ch].cnt++;
                }
                else{
                    gt[ch].x2=i,gt[ch].y2=j;
                    gt[ch].cnt++;
                }
            }
            else if(mp[i][j]=='@'){
                sx=i,sy=j;
            }
            else if(mp[i][j]=='='){
                ex=i,ey=j;
            }
        }
    }
    bfs();
    return 0;
}

赛时的另一个想法

通过大力模拟可以发现，从一点去传送门且仍留在传送门当地的代价为 \(3\)，即进入传送门——离开另一传送门——进入另一传送门，综上，可以把两个地点都放入队列并且都标记上。

然而，实际是错误的，还需要去特判是否能传回来。

\(T4\) 鸭子游戏

其实是有动态规划的影子的，不过核心算法是差分。

先考虑一个问题，最终一致的纸牌个数有影响吗？有，但不完全有，因为如果我们以任意一个牌堆初始纸牌个数为基准，其方案数是不会改变的，因为相对增加减少是可以抵消的，例如 \({1,2,1,2,1,2}\) 这一组数，以 \(1\) 为基准和以 \(2\) 为基准是等价的。

那么以 \(3\) 为基准呢？不难发现还需要在整体上加上 \(1\) 或 \(2\)，因此得出本题的第一个结论：最终形成的纸牌数量必须是初始数量中的任意一个。那就让其都为 \(a_1\) 吧。

接着我们考虑差分数组 \(b\)，令 \(b_i=a_i-a_{i-1}\)，特别地 \(b_1=0\)，之后我们让所有的 \(a_i\) 都等于原数与 \(a_1\) 之差。

不难发现的是，如果出现牌数多于基准的，单调不上升序列 \([i,j]\)，其需要的操作数就是最多牌堆此时的 \(a_i\)，同理也有如果出现少于基准的，单调不下降序列 \([i,j]\)，其需要的地操作数为最少牌堆此时的 \(a_i\)。

既然如此就可以在 \(O(n)\) 的复杂度内更新答案。方案如下：

• 如果 \(a_i\) 与 \(a_{i-1}\) 异号，直接答案加上 \(|a_i|\)
• 如果 \(a_i\) 与 \(a_{i-1}\) 同号，且 \(|a_{i-1}|>=|a_i|\)，说明前一个的牌堆的操作足以覆盖掉目前的牌堆，无需改变答案。
• 如果 \(a_i\) 与 \(a_{i-1}\) 同号，且 \(|a_{i-1}|<|a_i|\)，说明前一个的牌堆的操作不够覆盖掉目前的牌堆，答案加上差分数组 \(b_i\)

这里大家可以发现，我们实际上每次更新到 \(a_i\) 时，是保证前 \(i\) 个都为基准的方案数。

int n;
int a[maxn],b[maxn];
int ans;
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    b[1]=0;
    for(int i=2;i<=n;i++){
        b[i]=a[i]-a[i-1];
    }
    for(int i=2;i<=n;i++){
        a[i]-=a[1];
    }
    a[1]=0;
    for(int i=2;i<=n;i++){
        if(a[i]>0){
            if(a[i-1]>=0){
                if(b[i]>=0){
                    ans+=b[i];
                }
            }
            else{
                ans+=a[i];
            } 
        }
        else if(a[i]<0){
            if(a[i-1]<=0){
                if(b[i]<=0){
                    ans+=abs(b[i]);
                }
            }
            else{
                ans+=abs(a[i]);
            }
        }
    }
    printf("%d\n",ans);
    return 0;   
}

然而，有一个更好的解法。

考虑如下的一个数组 \(A=\{2,3,3,1,5\}\)，差分之后就有 \(B=\{0,1,0,-2,4\}\)，我们可以发现，如果修改一个区间 \([l,r]\)，差分数组是在 \(l\) 与 \(r+1\) 的数值会改变。例如我们在 \([2,3]\) 位置 \(-1\)，得到的数组 \(A'=\{2,2,2,1,5\}\)，差分数组 \(B'=\{0,0,0,-1,4\}\)。若将 \(4\) 单点 \(+1\)，同理差分数组变作 \(B''=\{0,0,0,0,3\}\)。

总结一下上述操作得出的结论：一次修改可以将任意一正一负的差分数值分别 \(-1\)、\(+1\)。也就是说，实际上修改次数实际为正数之和与负数之和的绝对值较大值，我们设 \(cnt1=\sum_{i=1}^n [b_i>0],cnt2=\sum_{i=1}^n [b_i<0]\)。这样我们操作的次数 \(ans1\) 应当为：

int n;
int a[maxn],b[maxn];
int cnt1,cnt2;
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=2;i<=n;i++){
        b[i]=a[i]-a[i-1];
        if(b[i]>0){
            cnt1+=b[i];
        }
        else{
            cnt2-=b[i];
        }
    }
    printf("%d %d\n",max(cnt1,cnt2),abs(cnt1-cnt2)+1);
    return 0;
}