当前位置：个人在线分享 > Codeforces Round 952 (Div. 4) c++题解(A-H1)

Codeforces Round 952 (Div. 4) c++题解(A-H1)

作者 : admin 本文共4670个字，预计阅读时间需要12分钟 发布时间： 2024-06-12 共1人阅读

开头 : 

这场没打，今天vp了一下，写了A-G,然后就去吃饭了!

比赛链接 : 

Dashboard – Codeforces Round 952 (Div. 4) – Codeforces

A

直接交换，输出即可

inline void solve(){
	string a , b ; cin >> a>> b ;
	char c = a[0] ;
	a[0] = b[0] ;
	b[0] = c ;
	cout << a << " " << b << endl ; 
}

B

数据范围小，模拟那个过程即可;

#include
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef unsigned long long ULL ;
#define PI acos(-1)
#define endl '
'
#define pair PII ;
#define x first
#define y second
#define no do { cout << "No" << endl; return; } while(0)
#define yes do { cout << "Yes" << endl; return; } while (0)
#define lowbit(x) ((x) & -(x))
#define rep(i, s, e) for (int i=(s);i>= 1;
     }
     return res;
 }


inline void solve(){
	int n ; cin >> n ;
	int ans = 0 ,yss = 1 ;
	rep(i,2,n+1){
		int x = i ;
		int res = 0 ;
		while(xans) {
			ans = res ;
			yss = i ;
		}
	}
	cout << yss <> _;
    while(_ --) solve();
    return 0;
}

C

也是模拟遍历，先用前缀和预处理一下;

如果ma * 2 = b[i],表示a[1,i]是满足题目条件的;

inline void solve(){
	 int n ; cin >> n ;
	 rep(i,1,n) cin >> a[i] ;
	 rep(i,1,n) b[i] = b[i-1] + a[i] ;
	 int ans = 0 ;// ma 
	 // b[i]-ma = ma
	 LL ma = 0 ;
	 rep(i,1,n){
	 	ma = max(ma,a[i]) ;
	 	if(ma*2==b[i]) ans ++ ;
	 }
	 cout << ans << endl; 
}

D

因为所有点都是关于中心点对称分布的，直接求横坐标，纵坐标的平均数就是答案了

inline void solve(){
	 int n ,m ; cin >> n >> m ;
	 vector<vector> a(n+1,vector(m+1)) ;
	 vector b ;
	 rep(i,1,n)
	 	rep(j,1,m){
	 		cin >> a[i][j] ;
	 		if(a[i][j]=='#') b.pb({i,j}) ;
		 }
	int sz = b.size() ;
	int xx , yy ;
	if(sz==1){
		xx = b[0].x ; yy = b[0].y ;
		cout << xx << " " << yy << endl ;
		return ;
	}
	LL xs = 0 , ys = 0 ; 
	for(auto& bc : b){
		int xc = bc.x , yc = bc.y ;
		xs += xc ;
		ys += yc ; 
	}
	xx = xs / sz ;
	yy = ys / sz ;
	cout << xx << " " << yy << endl ; 
}

E

直接暴力即可,遍历其中两条边,复杂度(2000^2) ;

对于每个满足条件的长宽高i,j,k(也就是i*j*k==s)，在S中的移动范围分别是[i,x],[j,y],[k,z];

然后相乘即可;

inline void solve(){
	LL x , y , z , s ; cin >> x >> y >> z >> s ;
	LL ans = 0 ;
	rpL(i,1,x){
		rpL(j,1,y){
			LL k = s / (i*j) ;
			if(s%(i*j)==0 && k<=z){
				LL res = (x-i+1)*(y-j+1)*(z-k+1) ;
				ans = max(ans,res) ;
			}
		}
	}
	cout << ans << endl; 
}

F

一个非常明显的二分答案，但是用堆也可以做;

(可能这场题多的原因);

#include
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef unsigned long long ULL ;
#define PI acos(-1)
#define endl '
'
#define PII pair 
#define x first
#define y second
#define no do { cout << "No" << endl; return; } while(0)
#define yes do { cout << "Yes" << endl; return; } while (0)
#define lowbit(x) ((x) & -(x))
#define rep(i, s, e) for (int i=(s);i>= 1;
     }
     return res;
 }

int h , n ;
int a[N] , c[N] ;

bool pd(LL m){
	LL dmg = 0 ;
	rep(i,1,n){
		dmg += a[i] * ((m+c[i]-1) / c[i]) ;
		if(dmg>=h) return true ;
	}
	return dmg>=h ;
}

inline void solve(){
	cin >> h >> n ;
	LL sum = 0 ;
	rep(i,1,n) cin >> a[i]  , sum += a[i];
	rep(i,1,n) cin >> c[i] ;
	if(sum>=h){
		cout << 1 << endl ;
		return ;
	}
	LL l = 1 , r = 2e12 ;
	while(l+1>1 ;
		if(pd(m)) r = m ;
		else l = m ; 
		// cout << l << endl ;
	}
	cout << r <> _;
    while(_ --) solve();
    return 0;
}

G

  1.      D(n) : 表示数位和;
  2. D(k*n) = k*D(n) : 那么n的所有数位上的数x在*k之后不能够进位
  3. –> 能够推出x<=[9/k]  ps : []代表下取整 
  4.  然后计算[10^l,10^r)中有多少个数n满足这个条件
  5. 对于每一个数位，有t=[9/k]+1 种选择，有r个数位，res=t^r
  6. ans = t^r-t^l

用快速幂优化一下 : 

#include
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef unsigned long long ULL ;
#define PI acos(-1)
#define endl '
'
#define PII pair
#define x first
#define y second
#define no do { cout << "No" << endl; return; } while(0)
#define yes do { cout << "Yes" << endl; return; } while (0)
#define lowbit(x) ((x) & -(x))
#define rep(i, s, e) for (int i=(s);i>= 1;
     }
     return res;
 }


inline void solve(){
//	 D(n) : 表示数位和 
//	 D(k*n) = k*D(n) : 那么n的所有数位上的数x在*k之后不能够进位
//	 --> 能够推出x> l >> r >> k ;
	if(k>=10){
		cout << 0 << endl ;
		return ;
	}
	int p = floor(1.0*9/k)+1 ;
	LL ans = (qmi(p,r,Mod) - qmi(p,l,Mod)) % Mod ;
	if(ans<0) ans += Mod ;
	cout << ans <> _;
    while(_ --) solve();
    return 0;
}

H

用并查集记录关于每个点的连通块 ;

然后遍历每一行，每一列来求将这一行/列全改为#,之后的连通块的大小，找到最大的;

#include
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef unsigned long long ULL ;
#define PI acos(-1)
#define endl '
'
#define PII pair 
#define no do { cout << "No" << endl; return; } while(0)
#define yes do { cout << "Yes" << endl; return; } while (0)
#define lowbit(x) ((x) & -(x))
#define rep(i, s, e) for (int i=(s);i>= 1;
     }
     return res;
 }

struct DSU {
    std::vector f, siz;
    DSU() {}
    DSU(int n) {
        init(n);
    }
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) return false;
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};


inline void solve(){
	int n ,m ; cin >> n >> m  ;
	vector s(n) ;
	rep(i,0,n-1) cin >> s[i] ;
	int sz = n * m ;
	DSU dsu(sz) ;
	rep(i,0,n-1){
		rep(j,0,m-1){
			if(i+1<n&&s[i][j]=='#'&&s[i+1][j]=='#'){//对行进行扩展 
				dsu.merge(i*m+j,(i+1)*m+j);//合并 
			}
			if(j+1<m&&s[i][j]=='#'&&s[i][j+1]=='#'){
				dsu.merge(i*m+j,i*m+j+1);//合并 
			}
		}
	}
	int ans = 0 ;
	vector vis(sz,-1) ;
	rep(r,0,n-1){
		int res = 0 ;
		rep(i,0,m-1){//修改一行 
			if(s[r][i]=='.') res ++ ;//修改成#的数目 
			for(int xx=max(0,r-1);xx<=min(n-1,r+1);xx++){//找上下两行的联通块 
				if(s[xx][i]=='#'){
					int u=dsu.find(xx*m+i);
					if(vis[u]!=r){
						vis[u] = r ;
						res += dsu.size(u);
					}
				}
			}
		}
		ans = max(ans,res) ;
	}
	vis.assign(sz,-1) ;
	for(int c=0;c<m;c++){
		int res = 0 ;
		for(int i=0;i<n;i++){
			if(s[i][c]=='.') res++ ;
			for(int y=max(0,c-1);y<=min(m-1,c+1);y++){
				if(s[i][y]=='#'){
					int u = dsu.find(i*m+y);
					if(vis[u]!=c){
						vis[u] = c ;
						res += dsu.size(u) ;
					}
				}
			}
		}
		ans = max(ans,res) ;
	}
	cout << ans <> _;
    while(_ --) solve();
    return 0;
}

本站无任何商业行为
个人在线分享 » Codeforces Round 952 (Div. 4) c++题解(A-H1)
admin

admin 钻石

分享到：

相关推荐

E-->