加强制度建设 信息公开 网站 专栏,做枪版电影网站赚钱,网站备案管谁要幕布,织梦 网站公告B-最少剩几个#xff1f;_牛客小白月赛98 (nowcoder.com) 思路
奇数偶数 奇数#xff1b;奇数*偶数 奇数
所以在既有奇数又有偶数时#xff0c;两者结合可以同时删除
先分别统计奇数#xff0c;偶数个数
若偶个数大于奇个数#xff0c;答案是偶个数-奇个数
若奇个数…B-最少剩几个_牛客小白月赛98 (nowcoder.com) 思路
奇数偶数 奇数奇数*偶数 奇数
所以在既有奇数又有偶数时两者结合可以同时删除
先分别统计奇数偶数个数
若偶个数大于奇个数答案是偶个数-奇个数
若奇个数大于偶个数奇数个数减去偶个数再对2取模
ac代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)int main()
{IOS;int n,ans;int ji0,ou0;cinn;vectorlla(n);for(int i0;in;i) {cina[i];if(a[i] 1) ji;else ou; }if(ouji) ansou-ji;else{if((ji-ou)%2) ans1;else ans0;}coutansendl; return 0;
}
C-两个函数_牛客小白月赛98 (nowcoder.com)
超时问题如何解决 初始代码超时
#includebits/stdc.h
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)int main()
{IOS;ll q,a,x;cinq;for(int i0;iq;i){ll ans0;cinax;if(x1) ans(a*x)%998244353;else{for(int i1;ix;i){ans(a*(a%998244353*i)%998244353)%998244353;ans%998244353; }}ans%998244353;coutansendl;}return 0;
}
解决思路
1. 快速幂
时间复杂度是 O(log n)相比于直接进行指数运算大大提高了计算效率
快速幂代码
int FastPow(int a,int x,int mod)
{int ans 1;a%mod;while(x){if(x1) ans(ans*a)%mod;a (a*a)%mod;x1;}return ans;
}
2. 递推式
因为是求和过程可以用递推式
ac代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
ll mod998244353;int main()
{IOS;ll q,a,x;cinq;for(int i0;iq;i){ll ans0;cinax;if(x1) ansa%mod;else {a a*a %mod;ans(x-1)*x/2 %mod *a %mod;}coutansendl;}return 0;
}D-切割 01 串 2.0_牛客小白月赛98 (nowcoder.com) 思路
1. 前缀和 记录在索引的每一个位置处之前0或1的个数
2.dp dp[i][j] 表示考虑前 i 个字符时最多可以进行多少次切割对于每个长度 len遍历所有可能的切割起点 l使得 l len - 1 不超过序列的长度对于每个起点 l计算可能的切割终点 r 对于每个起点 l 和终点 r遍历所有可能的切割分割点 k使得 k 在 l 和 r 之间
动态规划过程的关键在于通过递归地考虑所有可能的切割方式并使用前缀和数组来快速计算分割点 k 两侧的子串中0和1的累计数量。通过这种方式算法能够高效地找到满足条件的切割次数的最大值
代码
#includebits/stdc.h
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)using namespace std;/*
算法区间DP 前缀和 O(N*N*N)
数据结构s0,s1前缀和数组 二维dp[l][r]
*/const int N 510;int s0[N], s1[N];
int dp[N][N];void solve() {int n, L, R;string s;cin n L R s;s s;for (int i 1; i n; i )s0[i] s0[i - 1] (s[i] 0),s1[i] s1[i - 1] (s[i] 1);for (int len 1; len n; len )for (int l 1; l n; l ){int r l len - 1;if (r n) break;for (int k l; k r; k ){int c0 s0[k] - s0[l - 1];int c1 s1[r] - s1[k];if (L abs(c0 - c1) abs(c0 - c1) R) dp[l][r] max(dp[l][r], 1 dp[l][k] dp[k 1][r]);}}cout dp[1][n] \n;
}signed main() {IOS;int t 1;
// cin t;while (t--) {solve();}return 0;
}
