[数据结构与算法][Acwing] 第 17 场周赛

B.

题意

给定一个 $n\times m$ 的方格矩阵。

每个方格要么是黑色，要么是白色。

请你计算，共有多少个非空方格集合满足：

• 集合内的所有方格颜色都相同。
• 集合内的任意两个方格都在同一行或同一列上

思路

因为数据范围很小

因此我们可以枚举每一行以及每一列,对于当前行统计出的$cnt$

我们知道方案数就是

$C_{cnt}^1+C_{cnt}^2..+C_{cnt}^{cnt}$

又组合定理可知从$1..cnt$的组合我们可以化简为$2^{(cnt)}?1$即可

code

// Problem: 方格集数量
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/3975/
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)

typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N = 60;


ll f[N][N];
int n,m;
char g[N][N];

void init(){
	for(int i = 0; i<N; i++ ){
		for(int j=0;j<=i;j++)
		if(!j)f[i][j] = 1;
		else f[i][j] = (f[i-1][j]+f[i-1][j-1]);
	}
}
void solve(){
	//cout<<f[2][1]<<endl;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) 
		cin>>g[i][j];
		
	
	ll ans = 0 ;
	
	for(int i=1;i<=n;i++){
		int c0 = 0 ;
		int c1 = 0 ;
		
		for(int j=1;j<=m;j++){
			if(g[i][j] == '0') c0++;
			else c1++;
		}
 
		for(int j = 1;j<=c0;j++){
			ans += f[c0][j];
		}
		
		for(int j=1;j<=c1;j++){
			ans += f[c1][j];
		}
	}
	
	// cout<<ans<<endl;
	
	for(int i=1;i<=m;i++){
		int c0 = 0 ;
		int c1 = 0 ;
		

		
		for(int j=1;j<=n;j++){
			if(g[j][i] == '0') c0++;
			else c1++;
		}
		
		// cout<<c0<<' '<<c1<<endl;
		
		for(int j = 1;j<=c0;j++){
			ans += f[c0][j];
		}
		
		for(int j=1;j<=c1;j++){
			ans += f[c1][j];
		}
		ans -= c0 , ans -=c1;
		
	}
	
	cout<<ans<<endl;
	
	
}

int main(){
	init();
	
    //int t;cin>>t;while(t--)
    solve();
    return 0 ;
}

C.

题意

给定两个数组$a[],b[]$

寻找一个最小的$x$,使得$b[i]+x,b[i]?x$能覆盖到所有的$a[]$

对结果进行四舍五入

思路

一眼二分了 (会的太少,局限性一下子就看出来了)

我们可以二分这个$x$,对于下边界$0$,下边界取 $max(a[i]+b[i])$

然后$check$的时候,直接暴力即可

$1900ms$卡过去的…

Code

// Problem: 无线网络
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/3976/
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)

typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N = 1e5+10;
const double eps  = 1e-5;

int a[N],b[N];
int n,m;

bool check(long double x){
	int p = 1;
	
	for(int i=1;i<=m;i++){
		long double l  = b[i] - x;
		long double r  = b[i] + x;
		
		while(a[p] >= l && a[p]<=r  && p<=n ){
			++p;
		}
		if(p == n+1)return true;
	}
	return false;
	
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	
	sort(a+1,a+1+n);
	sort(b+1,b+1+m);
	
	long double l = 0 , r =  max(abs(a[n]),abs(a[1]))+max(abs(b[n]),abs(b[1]));
	while(r - l > eps){
		long double mid = (l+r)/2;
		if(check(mid)) r = mid;
		else l = mid;
	}
	
//	cout<<l<<endl;
	
	
	if(l -  (int)l >= 0.5) cout<<(int)ceil(l)<<endl;
	else cout<<(int)l<<endl;
// 	
	
}

int main(){
    //int t;cin>>t;while(t--)
    solve();
    return 0 ;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖