5.13 模拟赛题解（没写完）

T1 P4304 [TJOI2013] 攻击装置

快进到 HZOI2023 超越 HZOI2020 （人均场切了紫）

考虑将棋盘黑白染色成这个样子

容易发现相同颜色的点直接一定没有冲突，满足二分图的性质，需要求出最小点覆盖，所以直接按冲突建好双向边，从 \(1\) 到 \(n^2\) 节点跑最大匹配即可。

设求出的最大匹配为 \(ans\)，因为是每个点都跑了一遍，所以真正的最大匹配为 \(\frac{ans}{2}\)，也是最小点覆盖，设所有合法点数为 \(num\)，最终的答案就是 \(num-\frac{ans}{2}\)。

其实这题正解应该是网络流，二分图理论复杂度不对，但是这是古早省选题，数据比较水，且卡不满，所以就放过了二分图。（是道水紫，只是数据太弱）

#include<bits/stdc++.h>
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
    return x;
}
const int N=205;
int a[N][N],id[N][N],cnt,vis[N*N*2],head[N*N*2],maxn,match[N*N*2],n,ans;
int x[9]={0,-1,-2,+1,+2,-1,-2,+1,+2},y[9]={0,-2,-1,-2,-1,+2,+1,+2,+1};
struct EDGE{int v,next;}e[(N*N)<<5];
inline void add(int u,int v){e[++cnt]={v,head[u]},head[u]=cnt;}
inline bool dfs(int x,int round){
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].v;
        if(vis[y]==round)continue;
        vis[y]=round;
        if(match[y]==0||dfs(match[y],round)){
            match[y]=x;return true;
        }
    }
    return false;
}
int main(){
    // freopen("attack.in","r",stdin);freopen("attack.out","w",stdout);
    std::ios::sync_with_stdio(0);std::cin.tie(0),std::cout.tie(0);
    n=read();maxn=n*n;
    int _zc=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            char ch=getchar();
            while(ch!='0'&&ch!='1')ch=getchar();
            if(ch=='1')a[i][j]=1;else _zc++;
        	id[i][j]=++cnt;
        }
    }cnt=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(!a[i][j]){
                for(int w=1;w<=8;++w){
                    int _x=i+x[w],_y=j+y[w];
                    if(_x>=1&&_x<=n&&_y>=1&&_y<=n&&(!a[_x][_y])){
                        add(id[i][j],id[_x][_y]);
                        add(id[_x][_y],id[i][j]);
                    }
                }
            }
        }
    }
	for(int i=1;i<=maxn;++i){
		if(dfs(i,i))ans++;
	}
	std::cout<<_zc-ans/2<<'\n';
}

T2 循环

有啥深意吗，深意就是剩余系内乘法封闭了，所以循环节数量是 \(O(n)\)。

#include<bits/stdc++.h>
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
    return x;
}
std::unordered_map<int,int> t;
int main(){
	freopen("number.in","r",stdin);freopen("number.out","w",stdout);
    int x=read(),last=1;
    while(1){
    	int v=last*x%100;
        if(t[v]){std::cout<<v<<' ';exit(0);}
        else {
            t[v]=1;last=v;
            std::cout<<v<<' ';
        }
    }
}

T3 漫步

没啥深意，都给好顺序了，跑一遍发现如果当前速度比之前所有速度都小于等于，那么就会多一组，本质上是一个单调栈的过程。

#include<bits/stdc++.h>
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
    return x;
}
const int N=1e5+10;
int v[N],d[N],n,f1[N],f2[N],f[N];
int main(){
    freopen("jog.in","r",stdin);freopen("jog.out","w",stdout);
    std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);
    n=read();
    for(int i=1;i<=n;++i){d[i]=read(),v[i]=read();}
    int ans=1;f[n]=v[n];
   	for(int i=n-1;i;--i){
        if(v[i]>f[i+1]){
            f[i]=f[i+1];
        }else{
            f[i]=v[i];ans++;
        }
	}
    std::cout<<ans<<'\n';
}

T4 穿越

挺没意思的，晚上写吧。

T5 结队

感觉埃氏筛都没在我脑子里出现过，晚上写。