Codeforces Round 993 (Div. 4)

Posted 2024-12-19 Updated 2024-12- 19

By NoahShen

68~88 min read

Codeforces Round 993 (Div. 4)

A. Easy Problem

题意

多测，输出n-1

Code

#include<bits/stdc++.h>
using namespace std;
void solve(){int n;cin>>n;cout<<n-1<<"\n";}
int main(){
    int t;cin>>t;while(t--)solve();
    return 0;
}

B. Normal Problem

题意

通过玻璃翻转，输出另一侧的字符串的样子

分析

q变p p变q 字符串翻转

Code

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

char transform(char c) {
    if (c == 'p') return 'q';
    if (c == 'q') return 'p';
    return 'w';
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string a, b;
        cin >> a;
        reverse(a.begin(), a.end());
        for (char c : a) b += transform(c);
        cout << b << "\n";
    }
    return 0;
}

C. Hard Problem

题意

3种猴，排座位，最大满意数

分析

贪心排

Code

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int t; 
    cin >> t; // 输入测试用例数
    while (t--) {
        long long m, a, b, c; // m: 每排座位数, a: 只想坐第1排, b: 只想坐第2排, c: 无偏好
        cin >> m >> a >> b >> c;

        // 第1排尽量满足a，第2排尽量满足b
        long long row1_used = min(m, a); // 第1排可以安排的猴子
        long long row2_used = min(m, b); // 第2排可以安排的猴子

        // 计算剩余座位和无偏好猴子的数量
        long long row1_left = m - row1_used; // 第1排剩余座位
        long long row2_left = m - row2_used; // 第2排剩余座位

        // 将无偏好猴子分配到剩余座位上
        long long remaining_c = c; // 剩余无偏好的猴子数量
        long long row1_c = min(row1_left, remaining_c);
        remaining_c -= row1_c; // 更新剩余无偏好猴子数量
        long long row2_c = min(row2_left, remaining_c);

        // 计算总共可以安排的猴子数量
        long long total = row1_used + row2_used + row1_c + row2_c;
        cout << total << "\n";
    }
    return 0;
}

D. Harder Problem

题意

输入的 $a_i $ 是构造出的字符串 $b_1,b_2...b_i $的一个众数

分析

如果每个数都只出现一次，则这个数一定是众数

那么构造数列时，就把自然数排进去，提前查询的 $a_i $就提前排

Code

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

int n,a[200005],b[200005],used[200005];

void solve(){
    cin>>n;for(int i=1;i<=n;i++)cin>>a[i],used[i]=0;
    int cnt=1;
    for(int i=1;i<=n;i++){
        if(used[a[i]]==0){
            b[i] = a[i];
            used[a[i]] = 1;
        }else{
            while(used[cnt]==1)cnt++;
            b[i] = cnt;
            used[cnt] = 1;
        }
    }
    for(int i=1;i<=n;i++)cout<<b[i]<<" ";
    cout<<"\n";
}

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

E. Insane Problem

题意

在两个区间中寻找 $\frac{x}{y}=k^n $的元组方案数

分析

遍历每一个 $k^n $，寻找x的倍增区间，与y区间取交，剩余的元素数就是当前 $k^n $的方案数

对于一个 $k^n $使用二分确定区间交，则总复杂度为 $O(t\log{\frac{r2}{r1}}\log{r1}) $

Code

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

int k,l1,r1,l2,r2;

int findleft(int ck,int l,int r){
    if(r*ck>=r2){
        if(r/2*ck>r2)
    }
    r*=2;
    if(r==r2)return r;
    return ;
}

void solve(){
    cin>>k>>l1>>r1>>l2>>r2;
    int cur = 1;
    while(cur*l1<=r2){
        int left = findleft(cur,1,r1);
    }
}

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

F. Easy Demon Problem

题意

矩阵删掉某一个十字后的和能否匹配询问的值

分析

记全矩阵和为 $s=\sum_{i,j}{a_ib_j}=S_aS_b $，某一列的和 $col_i=a_i\sum{b_j} $，某一行的和 $row_i=b_i\sum{a_j} $，某一点的值 $M_{i,j}=a_ib_j $，询问的值为 $x $

将题意转为
$ $
find\ \ i,j\ \ that\ \ satisfied\ \ \
s-x = col_i+row_j-M_{i,j}\
s-x = a_iS_b+b_jS_a-a_ib_j\
s-x = S_aS_b-(S_a-a_i)(S_b-b_j)\
x=(S_a-a_i)(S_b-b_j)
$ $
显然只需要枚举x的所有因子并检查因子是否存在即可

复杂度为 $O(q\sqrt{X_{max}}) $

Code

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

int n,m,q,a[200005],b[200005];
int sa,sb;
map<int,int>ca,cb;

bool check(int q1,int q2){
	if(ca[q1]==1 and cb[q2]==1)return true;
	if(cb[q1]==1 and ca[q2]==1)return true;
	return false;
}

signed main(){
	cin>>n>>m>>q;
	for(int i=0;i<n;i++)cin>>a[i],sa+=a[i];
	for(int i=0;i<m;i++)cin>>b[i],sb+=b[i];
	for(int i=0;i<n;i++)ca[sa-a[i]]=1;
	for(int i=0;i<m;i++)cb[sb-b[i]]=1;
	for(int i=0;i<q;i++){
		int tmp;cin>>tmp;
		int flag=0;
		for(int j=1;j<=sqrt(abs(tmp));j++)
			if(tmp%j==0)
				if(check(tmp/j,j) or check(-tmp/j,-j)){
					flag=1;
					break;
				}
		if(flag)cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

G1. Medium Demon Problem (easy version)

题意

有向图，每个节点只有1出度，能且仅能形成自环/ 树+一条回边(一个环)

每单位时间沿边向下一个节点传递一个单位的值，自身多于一个单位的值会被丢弃

求最小的稳定时间，注意输出要加2

分析

先找环，再找环上那棵数的 $depth_{max} $

复杂度为 $O(2n) $

Code

一开始写的时候没规划好，dfs写完了才发现还要记录一堆东西，太丑了

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

int to[200005],in[200005];
int cur_node_in_cycle[200005],tag,totle_dfs_visited[200005],cur_dfs_visited[200005];
int distance_from_cycle[200005];
vector<int>nonein;

void dfs(int cur){
	if(cur_node_in_cycle[cur]){
		if(totle_dfs_visited[to[cur]]){
			tag = cur;
			return ;
		}else{
			tag = -1;
			return ;
		}
	}
	if(cur_dfs_visited[cur]){tag=-1;return ;}
	cur_node_in_cycle[cur] = 1;
	totle_dfs_visited[cur] = 1;
	cur_dfs_visited[cur] = 1;
	dfs(to[cur]);
	if(tag==-1)cur_node_in_cycle[cur]=0;
	if(tag==cur)tag=-1;
	totle_dfs_visited[cur] = 0;
}

int dfs2(int cur,int cnt){
	if(distance_from_cycle[cur])return distance_from_cycle[cur]+cnt;
	if(cur_node_in_cycle[cur]){
		distance_from_cycle[cur] = 0;
		return cnt;
	}
	else{
		distance_from_cycle[cur] = dfs2(to[cur],cnt+1)-cnt;
		return distance_from_cycle[cur]+cnt;
	}
}

void solve(){
	nonein.clear();
	memset(in,0,sizeof(in));
	memset(cur_node_in_cycle,0,sizeof(cur_node_in_cycle));
	memset(cur_dfs_visited,0,sizeof(cur_dfs_visited));
	memset(distance_from_cycle,0,sizeof(distance_from_cycle));
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>to[i];
		in[to[i]]=1;
	}
	for(int i=1;i<=n;i++){
		if(in[i]==0)nonein.push_back(i);
	}
	for(auto i:nonein){
		tag=0;
		dfs(i);
	}
	int ans = 0;
	for(auto i:nonein){
		ans = max(ans,dfs2(i,0));
	}
	cout<<ans+2<<"\n";
}

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

G2. Medium Demon Problem (hard version)

题意

与G1一致，区别在于节点不会丢弃任何值

分析

从求 $depth_{max} $变为求环上有子树的节点的子树 $size_{max} $

注意是子树的size，不是环上节点的size，一个环上节点可能连着好几个子树

Code

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

int to[200005],in[200005];
int cur_node_in_cycle[200005],tag,totle_dfs_visited[200005],cur_dfs_visited[200005];
int sum_of_son[200005];
vector<int>nonein;
vector<int>edges[200005];
int multyin[200005];

void dfs(int cur){
	if(cur_node_in_cycle[cur]){
		if(totle_dfs_visited[to[cur]]){
			tag = cur;
			return ;
		}else{
			tag = -1;
			return ;
		}
	}
	if(cur_dfs_visited[cur]){tag=-1;return ;}
	cur_node_in_cycle[cur] = 1;
	totle_dfs_visited[cur] = 1;
	cur_dfs_visited[cur] = 1;
	dfs(to[cur]);
	if(tag==-1)cur_node_in_cycle[cur]=0;
	if(tag==cur)tag=-1;
	totle_dfs_visited[cur] = 0;
}

int total;
int vis3[200005];

void dfs2(int cur){
	vis3[cur] = 1;
	total++;
	if(edges[cur].size()==0)return ;
	for(auto i:edges[cur]){
		if(cur_node_in_cycle[i])continue;
		dfs2(i);
	}
}
int n;
void solve(){
	nonein.clear();
	for(int i=0;i<n+1;i++)edges[i].clear();
	memset(multyin,0,sizeof(multyin));
	memset(in,0,sizeof(in));
	memset(cur_node_in_cycle,0,sizeof(cur_node_in_cycle));
	memset(cur_dfs_visited,0,sizeof(cur_dfs_visited));
	memset(sum_of_son,0,sizeof(sum_of_son));
	
	memset(vis3,0,sizeof(vis3));
	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>to[i];
		in[to[i]]++;
		edges[to[i]].push_back(i);
	}
	for(int i=1;i<=n;i++){
		if(in[i]==0)nonein.push_back(i);
		if(in[i]>1)multyin[i]=1;
	}
	for(auto i:nonein){
		tag=0;
		dfs(i);
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(vis3[i])continue;
		if(multyin[i] and cur_node_in_cycle[i]){
			vis3[i]=1;
			for(auto j:edges[i]){
				total = 0;
				if(cur_node_in_cycle[j])continue;
				dfs2(j);
				ans = max(ans,total);
			}
		}
	}
	cout<<ans+2<<"\n";
}

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

H. Hard Demon Problem

题意

把给定的子矩阵平铺开，平铺的方式去看题目

求平铺开数列的 $\sum{iA_i} $

分析

这题的q是1e6的，那么单次询问复杂度必须低于 $O(\sqrt{n}) $

先分析全矩阵，或者说以 $1,1 $开头的矩阵的求法，注意这里列是y，行是x
$ $
\sum_{x=1}^{n}\sum_{y=1}^{n}{[(x-1)n+y]M_{x,y}}\
=\sum_{x=1}^{n}\sum_{y=1}^{n}{{xnM_{x,y}+yM_{x,y}-nM_{x,y}}}
$ $
显然可以看出，对于每一个 $x $而言 $\sum_{y=1}^{n}xM_{x,y} $都是一个不变的数字，对 $y $同理

那么我们可以预处理 $xM_{x,y},yM_{x,y},M_{x,y} $的二维前缀和，在需要的时候通过 $O(1) $的时间求出答案

推广到全部子矩阵，记 $col = (y_2-y_1+1) $
$ $
\sum_{x=x_1}^{x_2}\sum_{y=y_1}^{y_2}{[(x-x_1)col+(y-y1+1)]M_{x,y}}\
=\sum_{x=x_1}^{x_2}\sum_{y=y_1}^{y_2}{{xcolM_{x,y}+yM_{x,y}-[x_1col+y_1-1]M_{x,y}}}\
$ $
前半部分可以通过刚才处理的三个前缀和求出，后半部分全是常数，也可以直接求出

时间复杂度为 $O(q) $，因为输入输出比较大，记得优化读写

Code

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

int xM[2005][2005],yM[2005][2005],M[2005][2005],n,q,t;
int x1,yy1,x2,y2;

int getsum(int (*m)[2005]){
	return m[x2][y2]-m[x1-1][y2]-m[x2][yy1-1]+m[x1-1][yy1-1];
}

void solve(){
	cin>>n>>q;
	int tmp;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){//j is y, i is x
			cin>>tmp;
			xM[i][j]=xM[i][j-1]+xM[i-1][j]-xM[i-1][j-1]+tmp*(i);
			yM[i][j]=yM[i][j-1]+yM[i-1][j]-yM[i-1][j-1]+tmp*(j);
			M[i][j]=M[i][j-1]+M[i-1][j]-M[i-1][j-1]+tmp;
		}
	
	for(int i=0;i<q;i++){
		cin>>x1>>yy1>>x2>>y2;
		int sM = getsum(M);
		int ans=(getsum(xM)-(x1-1)*sM)*(y2-yy1+1)+getsum(yM)-(yy1-1)*sM-(y2-yy1+1)*sM;
		cout<<ans<<" ";
	}
	cout<<"\n";
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>t;while(t--)solve();
	return 0;
}

日记

算法 ACM OI 技术

License: CC BY 4.0