B-最少剩幾個(gè)？_?？托“自沦?8 (nowcoder.com)

思路

奇數(shù)+偶數(shù) = 奇數(shù)；奇數(shù)*偶數(shù) = 奇數(shù)

所以在既有奇數(shù)又有偶數(shù)時(shí)，兩者結(jié)合可以同時(shí)刪除

先分別統(tǒng)計(jì)奇數(shù)，偶數(shù)個(gè)數(shù)

若偶個(gè)數(shù)大于奇?zhèn)€數(shù)，答案是偶個(gè)數(shù)-奇?zhèn)€數(shù)

若奇?zhèn)€數(shù)大于偶個(gè)數(shù)，奇數(shù)個(gè)數(shù)減去偶個(gè)數(shù)再對2取模

ac代碼

#include<bits/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 ji=0,ou=0;cin>>n;vector<ll>a(n);for(int i=0;i<n;i++) {cin>>a[i];if(a[i] & 1) ji++;else ou++; }if(ou>ji)  ans=ou-ji;else{if((ji-ou)%2) ans=1;else ans=0;}cout<<ans<<endl;   return 0;
}

C-兩個(gè)函數(shù)_?？托“自沦?8 (nowcoder.com)

（超時(shí)問題如何解決）

初始代碼（超時(shí)）

#include<bits/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;cin>>q;for(int i=0;i<q;i++){ll ans=0;cin>>a>>x;if(x==1) ans=(a*x)%998244353;else{for(int i=1;i<x;i++){ans+=(a*(a%998244353*i)%998244353)%998244353;ans%=998244353;					}}ans%=998244353;cout<<ans<<endl;}return 0;
}

解決思路

1.? 快速冪

時(shí)間復(fù)雜度是 O(log n)，相比于直接進(jìn)行指數(shù)運(yùn)算，大大提高了計(jì)算效率

快速冪代碼

int FastPow(int a,int x,int mod)
{int ans = 1;a%=mod;while(x){if(x&1) ans=(ans*a)%mod;a= (a*a)%mod;x>>=1;}return ans;
}

2.? 遞推式

因?yàn)槭乔蠛瓦^程，可以用遞推式

ac代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
ll mod=998244353;int main()
{IOS;ll q,a,x;cin>>q;for(int i=0;i<q;i++){ll ans=0;cin>>a>>x;if(x==1) ans=a%mod;else {a = a*a %mod;ans=(x-1)*x/2 %mod *a %mod;}cout<<ans<<endl;}return 0;
}

D-切割 01 串 2.0_牛客小白月賽98 (nowcoder.com)

思路：

1.? 前綴和

? ? ? ? 記錄在索引的每一個(gè)位置處之前，0或1的個(gè)數(shù)

2.dp

????????dp[i][j]?表示考慮前?i?個(gè)字符時(shí)，最多可以進(jìn)行多少次切割；對于每個(gè)長度?len，遍歷所有可能的切割起點(diǎn)?l，使得?l + len - 1?不超過序列的長度；對于每個(gè)起點(diǎn)?l，計(jì)算可能的切割終點(diǎn)?r；

? ?對于每個(gè)起點(diǎn)?l?和終點(diǎn)?r，遍歷所有可能的切割分割點(diǎn)?k，使得?k?在?l?和?r?之間；

動(dòng)態(tài)規(guī)劃過程的關(guān)鍵在于，通過遞歸地考慮所有可能的切割方式，并使用前綴和數(shù)組來快速計(jì)算分割點(diǎn)?k?兩側(cè)的子串中0和1的累計(jì)數(shù)量。通過這種方式，算法能夠高效地找到滿足條件的切割次數(shù)的最大值

代碼

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)using namespace std;/*
算法：區(qū)間DP + 前綴和 O(N*N*N)
數(shù)據(jù)結(jié)構(gòu)：s0,s1前綴和數(shù)組 + 二維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;
}