周末这两天真的是玩爽了我的胆子真是肥嘟嘟的。。。1.牛客网-报名后才能查看题目#includeiostream using namespace std; const int maxn 2e55; int a[maxn],b[maxn]; int main(){ int n; cin n; for(int i 0;i n;i){ cin a[i] b[i]; } for(int i 0;i n;i) { cout a[i]; if(i ! n-1) cout ; } cout endl; for(int i 0;i n;i) { cout b[i]; if(i ! n-1) cout ; } return 0; }2.牛客网-报名后才能查看题目#includeiostream using namespace std; const int maxn 2005; int n,m,res 0; char a[maxn][maxn]; int main(){ cin n m; for(int i 1;i n;i){ for(int j 1;j m;j) cin a[i][j]; } for(int i 1;i n;i) for(int j 1;j m;j){ if(i 1 || i n || j 1 || j m){ if(a[i][j] #) res; } } cout res endl; return 0; }3.牛客网-报名后才能查看题目对于同余可以这样简单理解两个整数除以同一个数如果得到的余数相同那么这两个数就互为同余。也就是 a % m b % m --- (a - b)%m 0;然后你再看他题目中a1...aj,aj1.....an可以想到用前缀和来解决这个问题就解决了#includeiostream #includealgorithm using namespace std; const int maxn 2e55; long long n,m,temp,res; long long a[maxn]; int main(){ cin n m; for(int i 1;i n;i){ cin temp; a[i] a[i-1]temp; } for(int i 1;i n;i){ if(abs(a[i] - a[n]a[i-1])%m0) res; } cout res endl; return 0; }4.牛客网-报名后才能查看题目因为这道题目有一个找是否被占用也可以理解为空柜子是否存在然后就能想到去重找元素是否存在的快递方法set我开始用的是while但是有超时风险这里补充一点对于set:lower_bound的作用是在一个有序集合中找到第一个大于等于指定数字的元素。#includeiostream #includeset using namespace std; const int maxn 2e55; long long n,m,t,sum 0; long long a[maxn]; setint st; int main(){ cin n m; for(int i 0;i n;i) { cin a[i]; st.insert(i); } int now 0; for(int i 0;i m;i){ cin t; now (nowt)%n; //寻找now及其之后的第一个空位置 auto it st.lower_bound(now); if(it st.end()) it st.begin(); now *it; sum a[now]; //被占用了就从空柜子集合中删除 st.erase(it); } cout sum now1endl; return 0; }记得开long long5.牛客网-报名后才能查看题目你会首先想到动态规划#includeiostream #includevector #includealgorithm using namespace std; const long long INF -(1LL 60); int n,m,k; int main(){ int T; cin T; while(T--){ cin n m k; vectorlong long a(n); vectorint c(n); vectorlong longb(m); vectorint d(m); for(int i 0;i n;i) cin a[i] c[i]; for(int i 0;i m;i) cin b[i] d[i]; if(k 0){ cout 0 endl; continue; } //dp[i][0]拿了i件第一堆物品最后来自第一堆 dp[i][1]最后来自第二堆 vectorvectorlong long dp(k1,vectorlong long(2,INF)); if(n 0) dp[1][0] a[0]; if(m 0) dp[0][1] b[0]; //现在已经拿了一件了要继续拿到k件 for(int t 1;t k;t){ vectorvectorlong long ndp(k1,vectorlong long(2,INF)); //i:第一堆拿了多少件 for(int i 0;i t;i){ int j t-i; if(i n || j m) continue; //最后一次从第一堆拿 if(dp[i][0] ! INF){ //可以换到第二堆 if(j m){ ndp[i][1] max(ndp[i][1],dp[i][0]b[j]); } //上一个是标记0继续拿第二堆 if(i n c[i-1] 0){ ndp[i1][0] max(ndp[i1][0],dp[i][0]a[i]); } } //最后一次从第二堆拿 if(dp[i][1] ! INF){ //标记为1 if(i n){ ndp[i1][0] max(ndp[i1][0],dp[i][1]a[i]); } //标记为0 if(j m d[j-1] 0){ ndp[i][1] max(ndp[i][1],dp[i][1]b[j]); } } } dp.swap(ndp); } long long ans INF; for(int i 0; i k; i){ ans max(ans, dp[i][0]); ans max(ans, dp[i][1]); } if(ans INF) { cout IMPOSSIBLEendl; } else { cout ans endl; } } return 0; }没时间了题解明天补。来了,先不要看代码咱们从头开始做这道题两堆找最大可能第一想法是贪心但是这道题不能只是简单的两堆拿最大的那个因为还要考虑标记的约束。dp[i][j][0]表示第一堆拿了i件第二堆拿了j件0代表最后一次是从第一堆拿的01和标记没关系dp[i][j][1]代表最后一次是从第二堆拿的此时的最大价值是多少。两堆物品都是从上往下拿的第一堆拿了i,下一次如果拿只能拿i1。当前物品是什么我们可以通过i、j确定。下一次能从哪一堆拿我们可以通过上一次拿的是哪一堆以及上一个物品的标记确定。不需要记录整个拿取过程。(滚动数组优化空间)分两种情况来讨论1.上一次从第一堆拿dp[i][j][0]若是拿出的物品标记为0还从第一堆拿dp[i1][j][0] max(dp[i1][j][0],dp[i][j][0]a(i1))(取或不取这个括号里面的i1是下标从第二堆拿dp[i][j1][0] max(dp[i][j1][1],dp[i][j][0]b(j1));刚刚拿出的物品标记为1只能拿第二堆从第二堆拿dp[i][j1][0] max(dp[i][j1][1],dp[i][j][0]b(j1));2.上一次从第二堆拿dp[i][j][1]这个状态转移方程和上面是一样的刚刚上面提了一嘴因为他求解只依赖上一次的状态不用保存所有的历史结果我们开始想那么应该如何来优化呢我们如果知道第一堆拿了多少件i也知道了目前已经总共拿了t件了那么第二堆就是t-i件于是我们可以假设dp[i][0]表示第一堆拿了i件最后一件从第一堆拿。也就是dp保存了当前拿了t件的状态ndp保存了下一轮拿t1件的状态,计算完之后dp.swap(ndp)交换两个数组即可一个小地方代码中const long long INF -(1LL 60);这里用一个非常小的负数表示不可达状态。不能全部初始化为 0因为题目允许负数价值。 
长河君 · 2026/11/3 10:47:41 · 阅读 1.2k 牛客周赛round168解题
周末这两天真的是玩爽了我的胆子真是肥嘟嘟的。。。1.牛客网-报名后才能查看题目#includeiostream using namespace std; const int maxn 2e55; int a[maxn],b[maxn]; int main(){ int n; cin n; for(int i 0;i n;i){ cin a[i] b[i]; } for(int i 0;i n;i) { cout a[i]; if(i ! n-1) cout ; } cout endl; for(int i 0;i n;i) { cout b[i]; if(i ! n-1) cout ; } return 0; }2.牛客网-报名后才能查看题目#includeiostream using namespace std; const int maxn 2005; int n,m,res 0; char a[maxn][maxn]; int main(){ cin n m; for(int i 1;i n;i){ for(int j 1;j m;j) cin a[i][j]; } for(int i 1;i n;i) for(int j 1;j m;j){ if(i 1 || i n || j 1 || j m){ if(a[i][j] #) res; } } cout res endl; return 0; }3.牛客网-报名后才能查看题目对于同余可以这样简单理解两个整数除以同一个数如果得到的余数相同那么这两个数就互为同余。也就是 a % m b % m --- (a - b)%m 0;然后你再看他题目中a1...aj,aj1.....an可以想到用前缀和来解决这个问题就解决了#includeiostream #includealgorithm using namespace std; const int maxn 2e55; long long n,m,temp,res; long long a[maxn]; int main(){ cin n m; for(int i 1;i n;i){ cin temp; a[i] a[i-1]temp; } for(int i 1;i n;i){ if(abs(a[i] - a[n]a[i-1])%m0) res; } cout res endl; return 0; }4.牛客网-报名后才能查看题目因为这道题目有一个找是否被占用也可以理解为空柜子是否存在然后就能想到去重找元素是否存在的快递方法set我开始用的是while但是有超时风险这里补充一点对于set:lower_bound的作用是在一个有序集合中找到第一个大于等于指定数字的元素。#includeiostream #includeset using namespace std; const int maxn 2e55; long long n,m,t,sum 0; long long a[maxn]; setint st; int main(){ cin n m; for(int i 0;i n;i) { cin a[i]; st.insert(i); } int now 0; for(int i 0;i m;i){ cin t; now (nowt)%n; //寻找now及其之后的第一个空位置 auto it st.lower_bound(now); if(it st.end()) it st.begin(); now *it; sum a[now]; //被占用了就从空柜子集合中删除 st.erase(it); } cout sum now1endl; return 0; }记得开long long5.牛客网-报名后才能查看题目你会首先想到动态规划#includeiostream #includevector #includealgorithm using namespace std; const long long INF -(1LL 60); int n,m,k; int main(){ int T; cin T; while(T--){ cin n m k; vectorlong long a(n); vectorint c(n); vectorlong longb(m); vectorint d(m); for(int i 0;i n;i) cin a[i] c[i]; for(int i 0;i m;i) cin b[i] d[i]; if(k 0){ cout 0 endl; continue; } //dp[i][0]拿了i件第一堆物品最后来自第一堆 dp[i][1]最后来自第二堆 vectorvectorlong long dp(k1,vectorlong long(2,INF)); if(n 0) dp[1][0] a[0]; if(m 0) dp[0][1] b[0]; //现在已经拿了一件了要继续拿到k件 for(int t 1;t k;t){ vectorvectorlong long ndp(k1,vectorlong long(2,INF)); //i:第一堆拿了多少件 for(int i 0;i t;i){ int j t-i; if(i n || j m) continue; //最后一次从第一堆拿 if(dp[i][0] ! INF){ //可以换到第二堆 if(j m){ ndp[i][1] max(ndp[i][1],dp[i][0]b[j]); } //上一个是标记0继续拿第二堆 if(i n c[i-1] 0){ ndp[i1][0] max(ndp[i1][0],dp[i][0]a[i]); } } //最后一次从第二堆拿 if(dp[i][1] ! INF){ //标记为1 if(i n){ ndp[i1][0] max(ndp[i1][0],dp[i][1]a[i]); } //标记为0 if(j m d[j-1] 0){ ndp[i][1] max(ndp[i][1],dp[i][1]b[j]); } } } dp.swap(ndp); } long long ans INF; for(int i 0; i k; i){ ans max(ans, dp[i][0]); ans max(ans, dp[i][1]); } if(ans INF) { cout IMPOSSIBLEendl; } else { cout ans endl; } } return 0; }没时间了题解明天补。来了,先不要看代码咱们从头开始做这道题两堆找最大可能第一想法是贪心但是这道题不能只是简单的两堆拿最大的那个因为还要考虑标记的约束。dp[i][j][0]表示第一堆拿了i件第二堆拿了j件0代表最后一次是从第一堆拿的01和标记没关系dp[i][j][1]代表最后一次是从第二堆拿的此时的最大价值是多少。两堆物品都是从上往下拿的第一堆拿了i,下一次如果拿只能拿i1。当前物品是什么我们可以通过i、j确定。下一次能从哪一堆拿我们可以通过上一次拿的是哪一堆以及上一个物品的标记确定。不需要记录整个拿取过程。(滚动数组优化空间)分两种情况来讨论1.上一次从第一堆拿dp[i][j][0]若是拿出的物品标记为0还从第一堆拿dp[i1][j][0] max(dp[i1][j][0],dp[i][j][0]a(i1))(取或不取这个括号里面的i1是下标从第二堆拿dp[i][j1][0] max(dp[i][j1][1],dp[i][j][0]b(j1));刚刚拿出的物品标记为1只能拿第二堆从第二堆拿dp[i][j1][0] max(dp[i][j1][1],dp[i][j][0]b(j1));2.上一次从第二堆拿dp[i][j][1]这个状态转移方程和上面是一样的刚刚上面提了一嘴因为他求解只依赖上一次的状态不用保存所有的历史结果我们开始想那么应该如何来优化呢我们如果知道第一堆拿了多少件i也知道了目前已经总共拿了t件了那么第二堆就是t-i件于是我们可以假设dp[i][0]表示第一堆拿了i件最后一件从第一堆拿。也就是dp保存了当前拿了t件的状态ndp保存了下一轮拿t1件的状态,计算完之后dp.swap(ndp)交换两个数组即可一个小地方代码中const long long INF -(1LL 60);这里用一个非常小的负数表示不可达状态。不能全部初始化为 0因为题目允许负数价值。