青岛黄岛区建设工程管理局网站,17做网店这个网站做起多少钱,企业信用不良记录查询,烟台做网站推广的公司哪家好前言#xff1a; 昨天晚上自己一个人打的小白月赛#xff08;因为准备数学期末已经写烦了#xff09;#xff0c;题目难度感觉越来越简单了#xff08;不在像以前一样根本写不了一点#xff0c;现在看题解已经能看懂一点了#xff09;#xff0c;能感受到自己在不断进步…前言 昨天晚上自己一个人打的小白月赛因为准备数学期末已经写烦了题目难度感觉越来越简单了不在像以前一样根本写不了一点现在看题解已经能看懂一点了能感受到自己在不断进步希望在暑假能更努力一点吧少打点游戏多学学算法还有web的学习也要抓起来了这几天不是在看高数就是在打游戏感觉好堕落。
正文 链接(1条未读私信) 牛客小白月赛98_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)
A 骰子魔术 #includebits/stdc.h
using namespace std;
int a[10005];
int main(){int n,x;cinnx;for(int i1;in;i){int d;cind;a[d];}if(a[x])coutYES;else coutNO;return 0;
}
桶排秒了。
B 最少剩几个 #includebits/stdc.h
using namespace std;
int main(){int n,res0,ans0;cinn;int on;while(o--){int x;cinx;if(x%21)res;}int zn-res;if(zres){ansn-2*res;}else{ansn-2*z-((res-z)/2)*2;}coutansendl;return 0;
}
因为奇数加偶数一定是奇数奇数乘奇数一定为奇数分两种情况讨论当偶数数量大于奇数的时候直接用总数减奇数数量的两倍当奇数大于偶数的时候先减去偶数的两倍在考虑剩下的奇数即可。
C 两个函数 #includebits/stdc.h
using namespace std;
typedef long long ll;
const int mod998244353;
ll quickmod(ll a, ll b, ll c)
{ll ans 1;a a % c;while(b){if(b1) ans (ans * a) % c;b b 1;a (a * a) % c;}return ans;
}
int main(){int n;cinn;while(n--){ll a,x,ans;cinax;if(x1)ansa*x%mod;else{ans(((a*a)%mod)*((x)*(x-1)/2%mod))%mod;}coutansendl;}return 0;
}我们可以将公式转化为 最后直接一边算一遍取模即可。
D 切割 01 串 2.0 #includebits/stdc.h
using namespace std;
const int N 1e5 5;
int dp[1000][1000];
int pre[N],suf[N];
int main(){int t 1;while(t --{int n,l,r; cin n l r;string s; cin s;s # s;// 区间dp// dp[a][b] dp[a][k] dp[k1][b] 1;for(int i 1; i n ; i ){if(s[i] 0) pre[i] pre[i - 1] 1;else pre[i] pre[i - 1];}for(int i 1 ; i n ; i ){if(s[i] 1) suf[i] suf[i - 1] 1;else suf[i] suf[i - 1];}for(int len 2 ; len n ; len ){for(int i 1 ; i n - len 1; i ){int j i len - 1;for(int k i ; k j ; k ){int q0 pre[k] - pre[i - 1];int q1 suf[j] - suf[k];int res abs(q0 - q1);if(res l res r)dp[i][j] max(dp[i][j],dp[i][k] dp[k 1][j] 1);}}}cout dp[1][n];}
}
比赛时这题一直想用递归根本没去想是dp甚至是我练过的区间dp导致我用递归一直暴内存怎么优化都过不了。其实细想想这题确实就是区间dp因为从小区间推导到大区间就免去了对一次切割产生两个子段进行·递归的过程,详情可以见代码。 E and xor or #includebits/stdc.h
using namespace std;
typedef long long ll;
const int N5e55;
ll a[N];
ll n,k1,k2;
ll work(int x){ll ans0,cnt0;for(int i1;in;i){bool flagtrue;for(int jx;j60;j){int ua[i]j1;int va[i-1]j1;if(u!v){flagfalse;}}if(flag)cnt;else{anscnt*(cnt1)/2;cnt1;}}anscnt*(cnt1)/2;return ans;
}
int main(){cinnk1k2;for(int i1;in;i){cina[i];}coutwork(k2)-work(k1)endl;return 0;
}
看了题解发现这题还挺简单
利用前缀和的思想用所有结果小于 2^k2的子数组个数 - 所有结果小于2^k1的子数组个数即为答案。
发现这个 2^k 刚好只有一位(二进制下)要结果小于它则必须满足在二进制中 k ~ 60 位中不能有 1。 根据题目条件满足不能有 1 即这个子数组元素在k ~ 60位的每一位不能同时存在 1 和 0。
F 绝妙的手法 看了下题解的代码直接给我吓跑了代码量还挺大的。
2024.7.12补
出题人出来说这题出错了所以不用补了。这又何尝不是另一种补完呢
后记 话说后天就考高数了我还一道题没写是不是有点不务正业了
