D-小圆爱玩龙龙Easy_河南萌新联赛2026第四场南阳理工学院小圆爱玩龙龙(Easy)题目大意有n nn件物品背包容量W WW。每件物品花费w i w_iwi价值v i v_ivi。规则在选出来的物品集合里最多可以免费拿其中1件这件免费物品不用花钱。剩下选的其他物品总花费之和≤ W \le W≤W。目标最大化拿到的总价值。形式化选集合S SS选至多一个f ∈ S f\in Sf∈S免费∑ i ∈ S , i ≠ f w i ≤ W \sum\limits_{i\in S,i\neq f} w_i \le Wi∈S,if∑wi≤W求∑ i ∈ S v i \sum\limits_{i\in S}v_ii∈S∑vi的最大值。核心思路暴力枚举解法Easy版图上代码的思路枚举哪一件物品当做免费物品一共n nn种情况假设第f ff件免费这件物品我们必拿价值直接加上(v[f])但是不给它算重量。剩下其余n-1 件物品做普通01背包背包容量依旧是W WW求出最多价值dp[W]。总价值 dp[W] \(v[f]\)。在所有f 0 … n − 1 f0 \dots n-1f0…n−1的结果里取最大值就是答案。时间复杂度O ( n 2 W ) O(n^2W)O(n2W)适合Easy数据n大的时候会超时需要二维dp优化版本。状态解释dp[j]不选第f ff件物品用不超过j jj的钱能拿到的最大快乐值。手中有j元时有的最大快乐值因为第f ff件免费直接拿所以总价值 dp[W] \(v[f]\)。核心代码dp[j] max(dp[j], dp[j - w[i]] v[i]); 花费j时的最大快乐值在买i之前的最大快乐值买上i的快乐值#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, W; cin n W; vectorint w(n), v(n); for (int i 0; i n; i) { cin w[i] v[i]; } int ans 0; // f枚举哪一件物品作为【免费拿走】的物品 // f从0到n‑1依次假设第f件免费 for (int f 0; f n; f) { vectorint dp(W 1, 0); // dp[j]花费j元能拿到的最大快乐值 for (int i 0; i n; i) { if (i f) continue; //免费的这件跳过不参与背包不用花钱买 【//标准01背包倒序循环】 for (int j W; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } // dp[W]剩下物品用最多W元得到的最大价值再加上免费物品的价值v[f] ans max(ans, dp[W] v[f]); } cout ans \n; return 0; }G-你逃不过我你信不信_河南萌新联赛2026第四场南阳理工学院题目大意求1-n的每个数的阶乘之和输出后4位不足4位前面补0核心思路n的范围较大纯算会爆求后4位为非是让后4位做运算我们可以把阶乘和阶乘之和每次都%10000我们发现当n19时后4位都是0313当n19时直接输出0313n19时直接算输出后4位#includebits/stdc.h using namespace std; #define int long long const int N10000; void solve(){ int n; cinn; if(n19){ cout0313endl; return; } int sum0,sum11; 【阶乘与阶乘之和%10000】 for(int i1;in;i){ sum1*i%10000; sumsum1; sum%10000; } string sto_string(sum); int ls.size(); for(int il;i4;i)cout0; couts; } signed main(){ int _1; while(_--){ solve(); } }J-小苯的星轨_河南萌新联赛2026第四场南阳理工学院小茉的星轨题目大意平面上有n nn颗星星坐标( x i , y i ) (x_i,y_i)(xi,yi)所有星星坐标互不相同。选出两颗星星组成无序星星对合法条件过这两颗星星的直线经过原点KaTeX parse error: Cant use function \( in math mode at position 1: \̲(̲(0,0)\)。特殊规则无序对 ((i,j)) 和 ((j,i)) 算同一个。如果两颗星星其中有一颗是原点((0,0))这个对直接合法。求总一共有多少合法无序点对。几何含义两点连线过原点等价于两个点在同一条过原点的直线上。一个点((x,y))把坐标除以gcd ( ∣ x ∣ , ∣ y ∣ ) \gcd(|x|,|y|)gcd(∣x∣,∣y∣)得到最简方向向量同一条过原点直线上的非原点的点最简方向向量要么完全相同要么互为相反数。例((2,4))与( − 1 , − 2 ) (-1,-2)(−1,−2)都在同一条过原点直线。核心思路原点单独处理设原点一共有c n t 0 cnt0cnt0个。原点和其他任意点配对全部合法贡献c n t 0 × ( n − c n t 0 ) cnt0 \times (n-cnt0)cnt0×(n−cnt0)。注意题目保证所有星星坐标互不相同所以原点最多只会出现1个。非原点的点求方向最简向量对一个点((x,y))先求最大公约数g gcd ( ∣ x ∣ , ∣ y ∣ ) g\gcd(|x|,|y|)ggcd(∣x∣,∣y∣)。得到n x x / g , n y y / g nxx/g,\; nyy/gnxx/g,nyy/g。⚠坑本质上是算斜率让斜率相等的两两结合但a/b会保留整数用double也不行除以最大公约数可以避免把所有在同一条直线上的点全变为相同的点统计这样的点有多少个map统计每一个标准化方向的点的数量c n t cntcnt。同一个方向上有c n t cntcnt个点两两配对合法组合数C c n t 2 c n t ∗ ( c n t − 1 ) / 2 \boldsymbol{C_{cnt}^{2}cnt*(cnt-1)/2}Ccnt2cnt∗(cnt−1)/2。答案 原点带来的贡献 所有方向组合数之和。#includebits/stdc.h using namespace std; #define int long long #define endl \n #define pii pairint,int #define fi first #define se second const int N101; void slove(){ int n; cinn; mappii,intmp; int ans0; vectorintx(n1,0); vectorinty(n1,0); for(int i1;in;i){ cin x[i] y[i]; 【星星对的计算】 if(x[i]0y[i]0) { ansn-1; } else { int g__gcd(x[i],y[i]); mp[{x[i]/g,y[i]/g}]; } } for(auto c:mp){ ansc.se*(c.se-1)/2; } coutansendl; } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int _; cin_; while(_--) slove(); return 0; }L-A × B_河南萌新联赛2026第四场南阳理工学院高精度乘法从低位运算#includebits/stdc.h using namespace std; #define int long long void solve(){ string s1,s2; cins1s2; reverse(s1.begin(),s1.end()); reverse(s2.begin(),s2.end()); vectorints3(40,0); int l1s1.size(),l2s2.size(); for(int i0;il1;i){ for(int j0;jl2;j){ s3[ij](s1[i]-0)*(s2[j]-0); } } int lenl1l2; 先进位再% for(int i0;ilen;i){ s3[i1]s3[i]/10; s3[i]%10; } bool okfalse; for(int ilen-1;i0;i--){ if(s3[i]!0)oktrue; if(ok) couts3[i]; } } signed main(){ int _1; while(_--){ solve(); } }
