ACGO巅峰赛#19 # 全题解

亚洲卷王 AK IOI

2025-05-20 20:17:11

发布于：北京

61阅读

0回复

0点赞

T1

首先枚举正方形左上角的坐标 $(i,j)$ ，求出右下角坐标 $(i+m-1,j+m-1)$ ，判断错误的像素点是否在这里面即可。

要注意，右下角坐标不能超出大正方形。

时间复杂度： $O(n^2)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,x,y,ans;
char a[105][105],b[105][105];
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++) cin>>a[i]+1;
    for(ll i=1;i<=n;i++) cin>>b[i]+1;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            if(a[i][j]^b[i][j]){
                x=i,y=j;
                break;
            }
        }
        if(x) break;
    }
    for(ll i=1;i<=x;i++){
        for(ll j=1;j<=y;j++){
            if(i+m-1>n||j+m-1>n) continue;
            ans+=i+m-1>=x&&j+m-1>=y;
        }
    }
    cout<<ans;
    return 0;
}

T2

注意：要么全文单面打印，要么全文双面打印，不能混合！

单面打印的价格是很显然的： $a \times m + c \times (n-m)$ .

考虑双面打印的价格。

显然，双面打印一定是这样打印的： $(1,2),(3,4),...$ ，其中，我们只需要在 $1,3,5,...$ 这些位置花钱就好了。

所以使用 $\texttt{unordered\_set}$ 记录需要花钱的位置。

思考如何求解价格。

令 $\texttt{unordered\_set}$ 的大小为 $S$ ，我们需要双面打印 $T$ 次，可以得到： $T=\lfloor \cfrac{n+1}{2} \rfloor$ .

需要彩色打印的只有 $S$ 个位置，而其他 $T-S$ 个位置都可以使用黑白打印。

取最小值即可。

时间复杂度： $O(m)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a,b,c,d,n,m,ansa,ansb;
ll p[200005];
unordered_set<ll> uset;
int main(){
    cin>>a>>b>>c>>d>>n>>m;
    for(ll i=1;i<=m;i++){
        cin>>p[i];
        uset.insert(p[i]+1>>1);
    }
    ansa=m*a+(n-m)*c;
    ansb=d*((n+1>>1)-uset.size())+b*uset.size();
    cout<<min(ansa,ansb);
    return 0;
}

T3

暴力就不说了。

注意到每一次移动，只会在横坐标与纵坐标之间的一个修改，而且障碍的坐标不变。所以考虑统计每一个 $x$ 坐标所对应的 $y$ 坐标们，以及 $y$ 坐标所对应的 $x$ 坐标们。

由于值域巨大，使用 $\texttt{map}$ 存储。

现在我们进行操作。如果我们碰不到障碍，直接修改坐标就好了；如果碰到障碍了，那么我们一定是碰到了第一个在路上的障碍。明显的二分。

随便调一下，然后就过了。

时间复杂度： $O(n \log^2n+m \log^2n)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
const ll MAXN=2e5+25,INF=1ll<<60;
ll n,m,c,t,posx,posy;
char op;
ll x[MAXN],y[MAXN];
map<ll,vector<ll>> mpa,mpb;
inline ll bfind(const vector<ll> &a,const ll &x,const ll &op){
    ll ans=-1,l=0,r=a.size();
    r--;
    if(op==0){
        while(l<=r){
            ll mid=l+r>>1;
            if(a[mid]>=x){
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        if(ans==-1) return INF;
        return a[ans];
    }
    if(op==1){
        while(l<=r){
            ll mid=l+r>>1;
            if(a[mid]<=x){
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        if(ans==-1) return -INF;
        return a[ans];
    }
    if(op==2){
        while(l<=r){
            ll mid=l+r>>1;
            if(a[mid]<=x){
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        if(ans==-1) return -INF;
        return a[ans];
    }
    while(l<=r){
        ll mid=l+r>>1;
        if(a[mid]>=x){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    if(ans==-1) return INF;
    return a[ans];
}
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        mpa[x[i]].eb(y[i]);
        mpb[y[i]].eb(x[i]);
    }
    for(auto &it:mpa) sort(it.second.begin(),it.second.end());
    for(auto &it:mpb) sort(it.second.begin(),it.second.end());
    while(m--){
        cin>>op>>c;
        if(op=='w'){
            t=bfind(mpa[posx],posy,0);
            if(t<=posy+c) posy=t-1;
            else posy+=c;
        }
        else if(op=='d'){
            t=bfind(mpa[posx],posy,1);
            if(t>=posy-c) posy=t+1;
            else posy-=c;
        }
        else if(op=='l'){
            t=bfind(mpb[posy],posx,2);
            if(t>=posx-c) posx=t+1;
            else posx-=c;
        }
        else{
            t=bfind(mpb[posy],posx,3);
            if(t<=posx+c) posx=t-1;
            else posx+=c;
        }
    }
    cout<<posx<<' '<<posy;
    return 0;
}

T4

暴力是很显然的。直接去掉边再跑搜索。

发现操作只有删除，想到逆序操作就变成了增加。

很显然的并查集，在上面多维护一个集合大小就好了。

注意维护一下合并的顺序，无关删除的直接合并，有关的按照输入的逆序处理，最后答案倒过来输出。

别忘了并查集维护的是集合大小，所以用 $n$ 减去集合大小才是答案。

此时还并没有做完。

容易发现，暴力枚举每一个群内的两人关系再合并的时间复杂度过大，所以我们创建 $m$ 个虚点编号为 $n+1$ 到 $n+m$ 表示群聊。

这样我们的复杂度就很低了。

注意，虚点的集合父亲为本身，大小初始化为 $0$ 。这是因为我们只关心人，而不关心群聊。

时间复杂度： $O(q \log (n+m))$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
#define pll pair<ll,ll>
#define mkp make_pair
#define fir first
#define sec second
const ll MAXN=2e5+25;
ll n,m,q,s,t;
ll par[MAXN<<1],siz[MAXN<<1];
vector<ll> ans;
vector<pll> a,oper;
set<pll> sets;
inline void init(){
    for(ll i=1;i<=n+m;i++) par[i]=i;
    for(ll i=1;i<=n;i++) siz[i]=1;
    return;
}
inline ll sfind(const ll &x){
    if(par[x]==x) return x;
    return par[x]=sfind(par[x]);
}
inline ll inset(const ll &x,const ll &y){return sfind(x)==sfind(y);}
inline void smerge(const ll &x,const ll &y){
    if(inset(x,y)) return;
    siz[sfind(y)]+=siz[sfind(x)];
    par[sfind(x)]=sfind(y);
    return;
}
int main(){
    cin>>n>>m>>q;
    init();
    for(ll i=1;i<=m;i++){
        cin>>s;
        for(ll j=1;j<=s;j++){
            cin>>t;
            a.eb(t,i+n);
        }
    }
    for(ll i=1;i<=q;i++){
        cin>>s>>t;
        oper.eb(s,t+n);
        sets.insert(mkp(s,t+n));
    }
    for(auto &i:a){
        if(sets.count(i)) continue;
        smerge(i.fir,i.sec);
    }
    reverse(oper.begin(),oper.end());
    for(auto &i:oper){
        ans.eb(siz[sfind(1)]);
        smerge(i.fir,i.sec);
    }
    reverse(ans.begin(),ans.end());
    for(auto &i:ans) cout<<n-i<<'\n';
    return 0;
}

T5

明显的 DP。

设 $dp_{i,j}$ 表示到达 $i$ 层，目前位于房间 $j$ 的最大收获。

状态转移实在太显然了：

$dp_{i,j}=\max(\max_{1 \leq k < j}{dp_{i-1,k}},\max_{j < k \leq m}{dp_{i-1,k}})+a_{i,j}$

发现可以边跑边记录上一层的最大值，这样转移复杂度就降为 $O(1)$ 了。

但是如果上一层的最大值的位置刚好等于 $j$ 的话， $j$ 房间开不了门。所以我们还要维护一个次大值。

这就很简单了。

时间复杂度： $O(nm)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
const ll MAXN=2e5+25;
ll n,m,fir,sec,newfir,newsec,ans;
vector<ll> a[MAXN],dp[MAXN];
int main(){
    cin>>n>>m;
    for(ll i=0;i<=n+1;i++){
        a[i].resize(m+2);
        dp[i].resize(m+2);
    }
    for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) cin>>a[i][j];
    for(ll i=1;i<=n;i++){
        newfir=newsec=0;
        for(ll j=1;j<=m;j++){
            if(fir^j) dp[i][j]=dp[i-1][fir]+a[i][j];
            else if(sec) dp[i][j]=dp[i-1][sec]+a[i][j];
            if(dp[i][j]>=dp[i][newfir]){
                newsec=newfir;
                newfir=j;
            }
            else if(dp[i][j]>dp[i][newsec]) newsec=j;
            ans=max(dp[i][j],ans);
        }
        fir=newfir;
        sec=newsec;
    }
    cout<<ans;
    return 0;
}

T6

大模拟。

首先需要确定 $4$ 个数的运算顺序。可以使用 $\texttt{next\_permutation}$ 枚举全排列。

三个运算符直接使用三重循环来枚举： $0$ 代表 $+$ ， $1$ 代表 $-$ ， $2$ 代表 $\times$ ， $3$ 代表 $\div$ .

设 $F(a,i,b)$ 表示 $a,b$ 进行 $i$ 运算符所代表的操作。

运算无非这 $5$ 种：

F(F(F(a[0],i,a[1]),j,a[2]),k,a[3])
F(F(a[0],i,a[1]),j,F(a[2],k,a[3]))
F(F(a[0],i,F(a[1],j,a[2])),k,a[3])
F(a[0],i,F(F(a[1],j,a[2]),k,a[3]))
F(a[0],i,F(a[1],j,F(a[2],k,a[3])))

字符串输出按照这个写就好。

时间复杂度： $O(Kn)$ ，其中 $K$ 是常数，不超过 $8000$ .

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll _,res;
bool can;
string s;
ll a[4];
char ops[4]={'+','-','*','/'};
inline ll F(const ll &x,const ll &op,const ll &y){
	if(x<-1e9||y<-1e9) return -1e18;
	if(op==0) return x+y;
	if(op==1) return x-y;
	if(op==2) return x*y;
	if(y==0||x%y) return -1e18;
	return x/y;
}
inline bool check(const ll &x){return x>=0&&x%24==0;}
inline void OUT(const string &s){
	can=true;
	cout<<s<<'\n';
    return;
}
int main(){
	cin>>_;
	while(_--){
		can=false;
		for(ll i=0;i<4;i++) cin>>a[i];
		sort(a,a+4);
		do{
			for(ll i=0;i<4;i++){
				for(ll j=0;j<4;j++){
					for(ll k=0;k<4;k++){
						res=F(F(F(a[0],i,a[1]),j,a[2]),k,a[3]);
						if(check(res)){
							s="(("+to_string(a[0])+ops[i]+to_string(a[1])+")"+ops[j]+to_string(a[2])+")"+ops[k]+to_string(a[3]);
							OUT(s);
							break;
						}
						res=F(F(a[0],i,a[1]),j,F(a[2],k,a[3]));
						if(check(res)){
							s="("+to_string(a[0])+ops[i]+to_string(a[1])+")"+ops[j]+"("+to_string(a[2])+ops[k]+to_string(a[3])+")";
							OUT(s);
							break;
						}
						res=F(F(a[0],i,F(a[1],j,a[2])),k,a[3]);
						if(check(res)){
							s="("+to_string(a[0])+ops[i]+"("+to_string(a[1])+ops[j]+to_string(a[2])+"))"+ops[k]+to_string(a[3]);
							OUT(s);
							break;
						}
						res=F(a[0],i,F(F(a[1],j,a[2]),k,a[3]));
						if(check(res)){
							s=to_string(a[0])+ops[i]+"(("+to_string(a[1])+ops[j]+to_string(a[2])+")"+ops[k]+to_string(a[3])+")";
							OUT(s);
							break;
						}
						res=F(a[0],i,F(a[1],j,F(a[2],k,a[3])));
						if(check(res)){
							s=to_string(a[0])+ops[i]+"("+to_string(a[1])+ops[j]+"("+to_string(a[2])+ops[k]+to_string(a[3])+"))";
							OUT(s);
							break;
						}
					}
					if(can) break;
				}
				if(can) break;
			}
		}while(!can&&next_permutation(a,a+4));
		if(!can) cout<<"Impossible\n";
	}
	return 0;
}