2025河南萌新赛第四场vp记录
solved 8 problems
A、G：@DASJ
C、J、H：@xmjlove
D、F、L：@dbywsc
A.完美序列
思路
遍历数组，先将所有出现的数字和他出现的次数记录下来，然后再次遍历数组，外层循环枚举所有可能的和，内层循环枚举两个数字，当这两个数字相同时，可以组成数字次数除以 \(2\) 并乘 \(2\) 个数字（因为可能数字次数是奇数），如果两个数字不相同，则可以组成数字次数少的乘 \(2\) 个数字，每次循环结束取一次最大值，最后，输出结果。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=11000;
int a[MAXN];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;a[x]++;}int ans=0;for(int i=1;i<=10010;i++){int sum=0;for(int j=1;j<=i-j;j++){if(j==i-j){sum+=a[j]/2*2;}else{sum+=min(a[i-j],a[j])*2;}}ans=max(ans,sum);}cout<<ans<<endl;return 0;
}
G.封闭路线
思路
遍历数组，让每一个数字都与这个数组中除它的以外的所有数字进行按位或运算，并且记录结果，然后在遍历一遍数组，查询数组中是否有这个数字，有的话就重复操作，直到遍历完整个数组，然后输出“YES”；如果没有，直接输出“NO”。
代码
#include <bits/stdc++.h>
using namespace std;
int a[110];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i]; }for(int i=1;i<=n;i++){for(int j=n;j>i;j--){int ans=0;int shu=a[i]|a[j];for(int m=1;m<=n;m++){if(shu==a[m]){ans=1;break;}}if(ans==0){cout<<"NO"<<endl;return 0;}}}cout<<"YES"<<endl;return 0;
}
C.合并石子
思路
最后石子一定会移动到某一个位置上，所以计算出移动到每个位置上的花费，取最小值集合；
做两遍前缀和和后缀和，第一遍处理到 \(i\) 位置的要移动多少石子，第二遍处理到 \(i\) 位置要多少花费。
代码
int n=read();int k=read();int[] a=new int[n];for(int i=0;i<n;i++)a[i]=read();long[] s1=new long[n];long[] s2=new long[n];s1[0]=a[0];s2[n-1]=a[n-1];for(int i=1;i<n;i++)s1[i]=s1[i-1]+a[i];for(int i=n-2;i>=0;i--)s2[i]=s2[i+1]+a[i];long[] s3=new long[n];long[] s4=new long[n];for(int i=1;i<n;i++)s3[i]=s3[i-1]+(s1[i-1]+k-1)/k;for(int i=n-2;i>=0;i--)s4[i]=s4[i+1]+(s2[i+1]+k-1)/k;long ans=Long.MAX_VALUE;for(int i=0;i<n;i++){ans=Math.min(ans,s3[i]+s4[i]);}pw.println(ans);
J.故障机器人的完美牌组
思路
使字典序最大，保证数组第一个数最大即可，找出数组后面最大的数，加到第一个上就行。
如果后面最大的数是 \(0\) ，为了使数组长度不减，不进行操作
代码
int n=read();int[] a=new int[n];for(int i=0;i<n;i++)a[i]=read();if(n==1){pw.println(1);pw.println(a[0]);pw.flush();pw.close();br.close();return;}int max=-1;int maxidx=0;for(int i=1;i<n;i++){if(a[i]>=max){max=a[i];maxidx=i;}}if(max==0){pw.println(n);for(int i=0;i<n;i++){pw.print(a[i]+" ");}}else {a[0]+=max;pw.println(n-1);for(int i=0;i<n;i++){if(i!=maxidx)pw.print(a[i]+" ");}}
H.杀戮尖塔第四厉害高手
思路
设 \(dp_{i, j}\) 为到达 \(i\) 点时使用了 \(j\) 次传送的最大战斗力
则可以通过父节点转移
dp1[node][0]=Math.max(dp1[father][0]+b[node],dp1[node][0]);
dp1[node][1]=Math.max(dp1[father][1]+b[node],dp1[node][1]);
dp1[node][2]=Math.max(dp1[father][2]+b[node],dp1[node][2]);
dp1[node][3]=Math.max(dp1[father][3]+b[node],dp1[node][3]);
也可以通过上一层的任意节点转移，每个点计算完成后同时更新本层的最大值
dp1[node][1]=Math.max(dp1[node][1],dp2[dis][0]+b[node]);
dp1[node][2]=Math.max(dp1[node][2],dp2[dis][1]+b[node]);
dp1[node][3]=Math.max(dp1[node][3],dp2[dis][2]+b[node]);
到达 \(n\) 节点时战斗力不为负无穷，则可以到达
代码
int n=read();int m=read();int k=read();ArrayList<ArrayList<Integer>> map=new ArrayList<>();int[] vis=new int[n+1];long[][] dp1=new long[n+1][4];long[][] dp2=new long[n+1][4];int[] a=new int[n+1];int[] b=new int[n+1];for(int i=0;i<=n;i++){Arrays.fill(dp1[i],Long.MIN_VALUE);Arrays.fill(dp2[i],Long.MIN_VALUE);map.add(new ArrayList<>());}for(int i=1;i<=n;i++){a[i]=read();b[i]=read();}for(int i=1;i<=m;i++){int u=read();int v=read();map.get(u).add(v);}Queue<Integer> q=new LinkedList<>();q.add(1);vis[1]=1;for(int i=0;i<4;i++){dp1[1][i]=k>=a[1]?k+b[1]:Long.MIN_VALUE;dp2[1][i]=k>=a[1]?k+b[1]:Long.MIN_VALUE;}while (!q.isEmpty()){int father=q.poll();int dis=vis[father];for(int node:map.get(father)){if(vis[node]==0)q.add(node);vis[node]=dis+1;if(dp2[dis][0]>=a[node])dp1[node][1]=Math.max(dp1[node][1],dp2[dis][0]+b[node]);if(dp2[dis][1]>=a[node])dp1[node][2]=Math.max(dp1[node][2],dp2[dis][1]+b[node]);if(dp2[dis][2]>=a[node])dp1[node][3]=Math.max(dp1[node][3],dp2[dis][2]+b[node]);if(dp1[father][0]>=a[node])dp1[node][0]=Math.max(dp1[father][0]+b[node],dp1[node][0]);if(dp1[father][1]>=a[node])dp1[node][1]=Math.max(dp1[father][1]+b[node],dp1[node][1]);if(dp1[father][2]>=a[node])dp1[node][2]=Math.max(dp1[father][2]+b[node],dp1[node][2]);if(dp1[father][3]>=a[node])dp1[node][3]=Math.max(dp1[father][3]+b[node],dp1[node][3]);dp2[dis+1][0]=Math.max(dp2[dis+1][0],dp1[node][0]);dp2[dis+1][1]=Math.max(dp2[dis+1][1],dp1[node][1]);dp2[dis+1][2]=Math.max(dp2[dis+1][2],dp1[node][2]);dp2[dis+1][3]=Math.max(dp2[dis+1][3],dp1[node][3]);}}if(dp1[n][0]!=Long.MIN_VALUE||dp1[n][1]!=Long.MIN_VALUE||dp1[n][2]!=Long.MIN_VALUE||dp1[n][3]!=Long.MIN_VALUE)pw.print("YES");else pw.print("NO");
D. 箭头谜题I
思路
比较明显的分层，可以直接跑一遍01BFS，如果到 \((n, m)\) 的最短路不超过 \(k\) 次魔法就 YES，否则 NO 。
代码
void solve(void) { int n, m, k; std::cin >> n >> m >> k;std::vector<std::string> g(n);for(int i = 0; i < n; i++) std::cin >> g[i];std::vector<int> dist(n * m, INF);int dx[] = {-1, 1, 0, 0};int dy[] = {0, 0, -1, 1};char ch[] = {'U', 'D', 'L', 'R'};std::deque<int> q;q.push_back(0);dist[0] = 0;while(q.size()) {int u = q.front(); q.pop_front();int x = u / m, y = u % m;int dis = dist[u];if(u == (n - 1) * m + (m - 1)) break;for(int i = 0; i < 4; i++) {int a = dx[i] + x, b = dy[i] + y;if(a < 0 || a >= n || b < 0 || b >= m) continue;int w = (g[x][y] == ch[i] ? 0 : 1);if(dis + w < dist[a * m + b]) {dist[a * m + b] = dis + w;if(w == 0) q.push_front(a * m + b);else q.push_back(a * m + b);}}}std::cout << (dist[(n - 1) * m + m - 1] <= k ? "YES\n" : "NO\n");
}
F.Minecraft
思路
如果物品 \(a\) 可以用来合成物品 \(b\) 就建一条 \(a \rightarrow b\) 的边，可以发现最后整个问题就转化成了一个 DAG，此时满足拓扑序才能让合成出来的数量最大。但是当一个物品需要多种物品合成时，要考虑不同物品之间的关系，所以可以二分答案，每次check时逆着跑一遍拓扑序看能否满足。
官方题解说可能会出现爆 long long 的情况，保险起见使用了 unsigned long long。
代码
std::vector<int> G[N];
void solve(void) { int n, m; std::cin >> n >> m;std::vector<u64> a(n + 1), in(n + 1, 0);u64 sum = 0;for(int i = 1; i <= n; i++) {std::cin >> a[i];sum += a[i];}std::vector<std::vector<int> > pre(n + 1);while(m--) {int v, k; std::cin >> v >> k;while(k--) {int u; std::cin >> u;pre[v].push_back(u);G[u].push_back(v);in[v]++;}}std::queue<int> q; std::vector<int> L;for(int i = 1; i <= n; i++) {if(in[i] == 0) q.push(i);}while(q.size()) {auto u = q.front();q.pop();L.push_back(u);for(auto v : G[u]) {if(--in[v] == 0) q.push(v);}}std::vector<int> revL = L;std::reverse(revL.begin(), revL.end());std::vector<u64> rd(n + 1);auto check = [&](u64 x) -> bool {std::fill(rd.begin(), rd.end(), 0);rd[1] = x;for(auto v : revL) {if(rd[v] <= a[v]) continue;u64 need = rd[v] - a[v];if(pre[v].empty()) return false;for(auto u : pre[v]) {rd[u] += need;}}return true;};u64 l = 0, r = sum, ans = 0;while(l <= r) {u64 mid = (l + r) / 2;if(check(mid)) {ans = mid;l = mid + 1;} else {r = mid - 1;}}std::cout << ans;
}
L.故障机器人的完美遗物
思路
由唯一分解定理得任意数字 \(x\) 的因数个数为：
\[d(x) = \prod_{i = 1}^{k}(\alpha_i + 1)
\]
当 \(k \geq 2\) 时 \(d(x)\) 一定不会是质数，所以 \(x\) 一定是下面的形式：
\[x = a^{b - 1} \ , a,b \in \mathbb{P}, b \geq 2
\]
所以 \(a\) 的范围缩小到了 \(10^6\) 以内，可以用线性筛预处理。之后再预处理一下每个数的不同次幂，如果合法的话就标记起来，等到输入时直接判断就i好了。
代码
i64 cnt = 0, primes[N];
bool st[N];
void work(int n) {for(int i = 2; i <= n; i++) {if(!st[i]) primes[cnt++] = i;for(int j = 0; primes[j] <= n / i; j++) {st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}
}
void solve(void) { work(N - 1);int n; std::cin >> n;std::set<i64> s;i64 ans = 0;for(int i = 0; i < cnt; i++) {i64 k = primes[i] * primes[i];int cnt = 2;while(k <= 1e12) {if(!st[cnt + 1])s.insert(k);k *= primes[i];cnt++;}}for(int i = 1; i <= n; i++) {i64 x; std::cin >> x;if(s.count(x)) {ans += x;}}std::cout << ans;
}