AtCoder Beginner Contest 351(补题A~F)

A - The bottom of the ninth

思路：

• B的和大于A的和即可

代码：

#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 1e3+10, INF = 0x3f3f3f3f;
int n=9,m=8;
int a[N],b[N];
int suma=0,sumb=0; 


void solve(){
	for(int i=1;i<=n;i++) cin>>a[i],suma+=a[i];
	for(int i=1;i<=m;i++) cin>>b[i],sumb+=b[i];
	int res=suma-sumb;
	res=max(0*1LL,res)+1;//保证比A的分数多
	cout<<res;
}

signed main(){
	int T=1;
//	cin>>T;
//	IOS;
    while(T--){
    	solve();
	} 
	return 0;
}

B - Spot the Difference

思路：

• 找到字母不同的位置并记录

代码：

#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 1e3+10, INF = 0x3f3f3f3f;
int n;
char a[N][N],b[N][N];


void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    cin>>a[i][j];
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    cin>>b[i][j];
	int x,y;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    if(a[i][j]!=b[i][j]) x=i,y=j;
	cout<<x<<' '<<y;
	
}

signed main(){
	int T=1;
//	cin>>T;
//	IOS;
    while(T--){
    	solve();
	} 
	return 0;
}

C - Merge the balls

思路：

• 每加入一个数字都需要判断右边两个数字是否相同，相同的合并后再加入该序列
• 该操作可以用栈来解决，合并相当于2^x次幂翻一倍，也就是x+1，所以x++后入栈即可
• 当然栈中是不能存2^x次幂的，会爆long long

代码：

#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 1e3+10, INF = 0x3f3f3f3f;
int n;
stack<int> s;


void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		if(s.empty()) s.push(x);
		else{
			while(s.size()&&s.top()==x){
				s.pop();
				x++;
			}
			s.push(x);
		}
	}
	cout<<s.size();
}

signed main(){
	int T=1;
//	cin>>T;
//	IOS;
    while(T--){
    	solve();
	} 
	return 0;
}

D - Grid and Magnet

思路：

• 题意大概就是求单元格的最大自由度，而自由度定义为他从该单元格重复移动所能到达的单元格数
• 如果该单元格的上下左右有磁铁，就不能移动了
• 我们可以标记磁铁周围的单元格，如果走到该这类单元格，那么就不能从该单元格再走了。
• 这样该图就被分割成了若干个连通块，求单元格的最大自由度就转化成了求最大的连通块
• 求连通块可以用bfs或并查集

#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 1e3+10, INF = 0x3f3f3f3f;
int n,m;
char g[N][N]; 
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
bool b[N][N],vis[N][N];
int ans;

void check(int x,int y){
	queue<PII> q;
	q.push({x,y});
	b[x][y]=1;
	int cnt=1;
	set<PII> s; //判断该单元格有没有走过
	while(q.size()){
		auto t=q.front(); q.pop();
		for(int k=0;k<4;k++){
			int tx=t.fi+dx[k];
  			int ty=t.se+dy[k];
  			if(tx<1||ty<1||tx>n||ty>m) continue;
  			if(g[tx][ty]=='#'||b[tx][ty]) continue;
  			if(s.count({tx,ty})) continue;
  			s.insert({tx,ty});
  			if(!vis[tx][ty]){
			  q.push({tx,ty});
			  b[tx][ty]=1;
		    }
			++cnt;
		}
	}
//	cout<<x<<' '<<y<<' '<<cnt<<endl;
	ans=max(ans,cnt);
}

void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++){
	  	cin>>g[i][j];
	  	if(g[i][j]=='.') ans=1;
	  }
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++){
	  	if(g[i][j]=='#'){
	  		for(int k=0;k<4;k++){
	  			int tx=i+dx[k];
	  			int ty=j+dy[k];
	  			if(tx<1||ty<1||tx>n||ty>m) continue;
	  			if(g[tx][ty]=='#') continue;
	  			vis[tx][ty]=1;
			}
		}
	  }
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    if(g[i][j]=='.'&&!b[i][j]&&!vis[i][j]) check(i,j);
	cout<<ans;
}

signed main(){
	int T=1;
//	cin>>T;
//	IOS;
    while(T--){
    	solve();
	} 
	return 0;
}

E - Jump Distance Sum

思路：

• 将曼哈顿坐标系转化为切比雪夫坐标系，这样原坐标(x,y)也就变为了(x+y,x-y),原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离。
• 能从一个点移动到另一个点，那么这两个点的奇偶性一定是相同的
• 所以我们可以奇偶分开来求，对坐标排序后，维护前缀和即可
• 最后别忘了答案要除以2，因为再切比雪夫坐标系中的代价是原坐标系代价的两倍

代码：

#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 2e5+10, INF = 0x3f3f3f3f;
//(x,y)->(x+y,x-y) 原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离。 
int n;
vector<int> a,b,c,d;

void solve(){
	cin>>n;
	for(int i=0;i<n;i++){
		int x,y; cin>>x>>y;
		if((x+y)%2){ //曼哈顿坐标系->切比雪夫坐标系 
			a.push_back(x+y); 
			b.push_back(x-y);
		}
		else{
			c.push_back(x+y);
			d.push_back(x-y);
		}
	}
	sort(a.begin(),a.end()); //升序排序 
	sort(b.begin(),b.end());
	sort(c.begin(),c.end());
	sort(d.begin(),d.end());
	int len1=a.size(),len2=c.size();
	int ans=0;
	int sa=0,sb=0; //记录前缀和
	for(int i=0;i<len1;i++){
		ans+=i*a[i]-sa;
		sa+=a[i];
		ans+=i*b[i]-sb;
		sb+=b[i];
	}
	int sc=0,sd=0;
	for(int i=0;i<len2;i++){
		ans+=i*c[i]-sc;
		sc+=c[i];
		ans+=i*d[i]-sd;
		sd+=d[i];
	}
	cout<<ans/2;
}

signed main(){
	int T=1;
//	cin>>T;
//	IOS;
    while(T--){
    	solve();
	} 
	return 0;
}

F - Double Sum

思路：

• 只有后面的数比前面的数大，才会对答案有贡献
• 用树状数组维护左边比当前位置小的数的个数的集合

代码：

#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 1e6+10, INF = 0x3f3f3f3f;
int n,m,a[N],s[N];

int lowbit(int x){
	return x&-x;
}

void change(int x,int k){
	while(x<=n) s[x]+=k,x+=lowbit(x);
}

int query(int x){//向前查 
	int t=0;
	while(x) t+=s[x],x-=lowbit(x);
	return t;
}

priority_queue<PII,vector<PII>,greater<PII>> q; 

void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		q.push({a[i],i});
	}
	int k=0,ans=0;
	while(!q.empty()){
		int val=q.top().fi,id=q.top().se;
		q.pop();
		int x=query(id); //id左边比a[id]小的数字的个数 
		int y=(n-id)-(k-x);//右边比a[id]大的数字的个数 
		k++; //个数加1 
		ans+=(x-y)*val;
		change(id,1);
	}
	cout<<ans;
}

signed main(){
	int T=1;
//	cin>>T;
//	IOS;
    while(T--){
    	solve();
	} 
	return 0;
}