Codeforces Round 790 (Div. 4)

D:题意：给定一个国际象棋棋盘，每个点都有权值，求在哪放置象，能使得象能攻击到的位置和最大。

Solution：由于数据范围很小，我们考虑最简单的暴力实现。对于每一个点，我们向四个攻击方向去走直到到达边界，定义方向数组即可。

int dx[5]={1,1,-1,-1};
int dy[5]={-1,1,1,-1};
void solve(){
	cin>>n>>m;
	vector<vector<int>>v(n,vector<int>(m));
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>v[i][j];
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			int res=v[i][j];
			for(int k=0;k<4;k++){
				int tx=i,ty=j;
				while(tx+dx[k]>=0&&tx+dx[k]<n&&ty+dy[k]>=0&&ty+dy[k]<m){
					tx+=dx[k];
				   ty+=dy[k];
				   res+=v[tx][ty];
				}
			}
			ans=max(ans,res);
		}
	}
	cout<<ans<<endl;
}

给出jls的dp写法。复杂度较小，学习一下

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    std::vector a(n, std::vector<int>(m)), f(a), g(a);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> a[i][j];
            f[i][j] = g[i][j] = a[i][j];
            if (i > 0 && j > 0) {
                f[i][j] += f[i - 1][j - 1];
            }
            if (i > 0 && j + 1 < m) {
                g[i][j] += g[i - 1][j + 1];
            }
        }
    }
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < m; j++) {
            if (j > 0) {
                f[i - 1][j - 1] = f[i][j];
            }
            if (j + 1 < m) {
                g[i - 1][j + 1] = g[i][j];
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ans = std::max(ans, f[i][j] + g[i][j] - a[i][j]);
        }
    }
    std::cout << ans << "\n";
}

F:题意：给定一个数组，我们希望寻求最大值域区间，使得区间内的每个数都出现k次。

Solution：显然我们答案与原序列的顺序无关，我们先把大于k次的数用map拿出来。此时的新vector已经有序，我们需要找到最大连续区间就是答案。

void solve(){
	cin>>n>>m;
	map<int,int>mp;
	//map<int,int>pos1;
	//map<int,int>pos2;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	mp[a[i]]++;
		// if(pos1[a[i]]==0)pos1[a[i]]=i;
		// pos2[a[i]]=i;
	}
	vector<int>v;
	
	for(auto [x,y]:mp)if(y>=m)v.push_back(x);
	if(v.size()==0){
		cout<<-1<<endl;
		return ;
	}
	//for(auto x:v)cerr<<x<<" ";
	
	int l=v[0],r=v[0];int ans=0;
	int ansl=l,ansr=r;
	for(int i=1;i<v.size();i++){
		if(v[i]!=v[i-1]+1){
			//这里可以自己写函数
			if(ans<r-l+1){
				ans=r-l+1;
				ansr=r,ansl=l;
				//l=r=v[i];
			}
			l=r=v[i];
		}
		else r++;
	}
	if(ans<r-l+1){ans=r-l+1;ansr=r,ansl=l;}
	cout<<ansl<<" "<<ansr<<endl;
}

G:题意：给定一颗黑白树，我们希望找到子树中的黑白节点相等的子树数量。

Solution：考虑直接dfs这棵树，维护两个数组代表子树的黑点与百点数量，最后只需要逐一对比统计答案

debug:字符串下标0base导致全部信息偏移

int bai[N],hei[N];
string s;
vector<int>e[N];
void dfs(int u){
	if(s[u]=='W')bai[u]++;
	else hei[u]++;
	for(auto v:e[u]){
		
		
		dfs(v);
		bai[u]+=bai[v];
		hei[u]+=hei[v];
	}
	//cerr<<u<<" "<<bai[u]<<" "<<hei[u]<<" "<<endl;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		bai[i]=hei[i]=0;
		e[i].clear();
		}
	for(int i=2;i<=n;i++){
		int x;cin>>x;
	e[x].push_back(i);
	}
	cin>>s;
	s=" "+s;
	dfs(1);
	int ans=0;
	
	for(int i=1;i<=n;i++)if(hei[i]==bai[i])ans++;
	cout<<ans<<endl;
}

H题意：给定一个数组，有两座桥，第一座桥上第i个点到第a[i]的点联想，其中第i个点在0-1之间，而a[i]的含义是a[i]-a[i]+1.我们希望钦定每个点的合适的位置，使得n条直线之间交点尽可能多，经过不断手模发现，答案就是当前的左端点的右边，所有右端点比当前右端点大的点都会贡献，好像就是正序对的数量。显然树状数组维护即可。

void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	Fenwick<int>c(n+2);
	for(int i=1;i<=n;i++)c.add(a[i],1);
	int ans=0;
	for(int i=1;i<=n;i++){
		c.add(a[i],-1);
		ans+=c.sum(a[i]);
		
	}
	cout<<ans<<endl;
}