freopen再出问题，模拟赛遗憾爆零

T1

排序，因为

a,b,c \in Z^+

，所以第一第二一定是

a

和

b

，最后一个一定是

a+b+c

，所以就这么解决。

CPP

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

int x[10],tot=0;
map<int,int> mp;

signed main(){
	
	 // freopen("a.in","r",stdin);
	 // freopen("a.out","w",stdout);
	
	for(int i=1;i<=7;i++){
		cin>>x[i];
		tot+=x[i];
	}
	sort(x+1,x+8);
	tot>>=2;
	int a=x[1],b=x[2];
	int c=tot-a-b;
	
	cout<<a<<" "<<b<<" "<<c;
	
	 // fclose(stdin);
	 // fclose(stdout);
	
	return 0;
}

T2 暴力枚举

就是暴力。

CPP

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

int n,b[N];
bool check(int x){
	int t[2*N]={0},tmp=x;
	t[x]++;
	for(int i=1;i<n;i++){
		tmp=b[i]-tmp;
		t[tmp]++;
		if(t[tmp]>1 || tmp<=0){
			return 0;
		}
	}
	return 1;
}

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	for(int i=1;i<n;i++) cin>>b[i];
	
	int minn=999999999;
	for(int i=1;i<n;i++){
		if(check(i)){
			minn=i;
			break;
		}
	}
	
	if(minn==999999999){
		cout<<"Not found =(";
		return 0;
	}
	cout<<minn<<" ";
	int tmp=minn;
	for(int i=1;i<n;i++){
		tmp=b[i]-tmp;
		cout<<tmp<<" ";
	}
	
	return 0;
}

T3 线头法树上贪心算法

目标：在树中经过最少路径覆盖遍历整棵树，等价于叶子节点的数量（以根节点为 1，叶子且编号不为根的节点为叶子）。记叶子数量为 cnt，因此只需考虑前 cnt 个“果子”即可，它们可能成为最终答案。
关键思想：
- 将叶子节点视为一次摘果子的机会。
- 对于每个非叶子结点，如果其子树下存在尚未使用的叶子机会，并且该节点上方有果子，则可以用叶子机会摘下该结点的果子。
- 定义：
  - val[u] 表示结点 u 上的果子数量。
  - dp[u] 表示结点及其子树能往上提供的摘果子机会总数（线头法中的容量）。
- 遍历顺序：从深到浅进行后序遍历，达到根节点时即可统计可摘的果子数量。最终答案为累积的 min(dp[u], val[u]) 的和。
转移关系（简述）：
- 叶子结点：dp[u] 初始为 1（如果是叶子且不是根）。
- 非叶子结点：将子树的 dp[v] 累加到 ret，dp[u] = ret +（若自身是叶子且非根，则加 1）。
- 记 ans += min(dp[u], val[u])；然后更新 dp[u] = max(0, dp[u] - val[u])，以便上层继续使用。
代码：
- 没有

T4 糖果均分模型 + 找中位数

聚焦“将每个 a_i 取模 m 后，找最小花费使得通过加减变成同一个数”的问题，以及给出的示例和思路的实现细化。

要点与思路

对每组测试：将 a_i 对 m 取模并排序，得到一个模数序列 b。
为考虑环状模结构，复制数组并对第二段加 m，得到长度为 2n 的展开数组 c。
通过滑动窗口定长为 n 的区间 [i, i+n-1]，在该区间内找中位数 mid，并以该中位数作为目标值计算花费：
- 左侧花费 L = (#元素在左) * a[mid] - sum(left部分)
- 右侧花费 R = sum(right部分) - (#元素在右) * a[mid]
- 总花费 = L + R
在所有长度为 n 的区间中取最小值。
由于区间内的中位数为最优目标值，能保证最小总花费。
时间复杂度：O(n log n) 排序 + O(n) 枚举区间与常数操作，总体 O(n log n)。
空间复杂度：O(n)。

ACS Day12 模拟赛复盘

文章操作

freopen再出问题，模拟赛遗憾爆零

T1

T2 暴力枚举

T3 线头法树上贪心算法

T4 糖果均分模型 + 找中位数

相关推荐

评论

ACS Day12 模拟赛复盘