前言：

? 昨天晚上自己一個(gè)人打的小白月賽（因?yàn)闇?zhǔn)備數(shù)學(xué)期末已經(jīng)寫(xiě)煩了），題目難度感覺(jué)越來(lái)越簡(jiǎn)單了（不在像以前一樣根本寫(xiě)不了一點(diǎn)，現(xiàn)在看題解已經(jīng)能看懂一點(diǎn)了），能感受到自己在不斷進(jìn)步，希望在暑假能更努力一點(diǎn)吧，，少打點(diǎn)游戲，多學(xué)學(xué)算法，還有web的學(xué)習(xí)也要抓起來(lái)了，這幾天不是在看高數(shù)就是在打游戲，感覺(jué)好墮落。

正文：

?鏈接：(1條未讀私信) ?？托“自沦?8_ACM/NOI/CSP/CCPC/ICPC算法編程高難度練習(xí)賽_?？透?jìng)賽OJ (nowcoder.com)

A 骰子魔術(shù)：

#include<bits/stdc++.h>
using namespace std;
int a[10005];
int main(){int n,x;cin>>n>>x;for(int i=1;i<=n;i++){int d;cin>>d;a[d]++;}if(a[x])cout<<"YES";else cout<<"NO";return 0;
}

桶排秒了。

B 最少剩幾個(gè)？：

#include<bits/stdc++.h>
using namespace std;
int main(){int n,res=0,ans=0;cin>>n;int o=n;while(o--){int x;cin>>x;if(x%2==1)res++;}int z=n-res;if(z>=res){ans=n-2*res;}else{ans=n-2*z-((res-z)/2)*2;}cout<<ans<<endl;return 0;
}

因?yàn)槠鏀?shù)加偶數(shù)一定是奇數(shù)，奇數(shù)乘奇數(shù)一定為奇數(shù)，分兩種情況討論，當(dāng)偶數(shù)數(shù)量大于奇數(shù)的時(shí)候直接用總數(shù)減奇數(shù)數(shù)量的兩倍；當(dāng)奇數(shù)大于偶數(shù)的時(shí)候先減去偶數(shù)的兩倍在考慮剩下的奇數(shù)即可。

C 兩個(gè)函數(shù)：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
ll quickmod(ll a, ll b, ll c)
{ll ans = 1;a = a % c;while(b){if(b&1) ans = (ans * a) % c;b = b >> 1;a = (a * a) % c;}return ans;
}
int main(){int n;cin>>n;while(n--){ll a,x,ans;cin>>a>>x;if(x==1)ans=a*x%mod;else{ans=(((a*a)%mod)*((x)*(x-1)/2%mod))%mod;}cout<<ans<<endl;}return 0;
}

我們可以將公式轉(zhuǎn)化為

最后直接一邊算一遍取模即可。

D 切割 01 串 2.0：

#include<bits/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;// 區(qū)間dp// dp[a][b] = dp[a][k] + dp[k+1][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];}
}

比賽時(shí)這題一直想用遞歸，根本沒(méi)去想是dp，甚至是我練過(guò)的區(qū)間dp，導(dǎo)致我用遞歸一直暴內(nèi)存，怎么優(yōu)化都過(guò)不了。其實(shí)細(xì)想想這題確實(shí)就是區(qū)間dp，因?yàn)閺男^(qū)間推導(dǎo)到大區(qū)間就免去了對(duì)一次切割產(chǎn)生兩個(gè)子段進(jìn)行·遞歸的過(guò)程,詳情可以見(jiàn)代碼。

?E and xor or：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
ll a[N];
ll n,k1,k2;
ll work(int x){ll ans=0,cnt=0;for(int i=1;i<=n;i++){bool flag=true;for(int j=x;j<=60;j++){int u=a[i]>>j&1;int v=a[i-1]>>j&1;if(u!=v){flag=false;}}if(flag)cnt++;else{ans+=cnt*(cnt+1)/2;cnt=1;}}ans+=cnt*(cnt+1)/2;return ans;
}
int main(){cin>>n>>k1>>k2;for(int i=1;i<=n;i++){cin>>a[i];}cout<<work(k2)-work(k1)<<endl;return 0;
}

看了題解發(fā)現(xiàn)這題還挺簡(jiǎn)單，

利用前綴和的思想，用所有結(jié)果小于 2^k2的子數(shù)組個(gè)數(shù) - 所有結(jié)果小于2^k1的子數(shù)組個(gè)數(shù)，即為答案。

發(fā)現(xiàn)這個(gè)? 2^k?剛好只有一位(二進(jìn)制下)，要結(jié)果小于它，則必須滿足在二進(jìn)制中?k?~?60?位中不能有?1。 根據(jù)題目條件，滿足不能有?1?即這個(gè)子數(shù)組元素在k?~?60位的每一位不能同時(shí)存在?1?和?0。

F 絕妙的手法：

看了下題解的代碼直接給我嚇跑了，代碼量還挺大的。

2024.7.12補(bǔ)：

出題人出來(lái)說(shuō)這題出錯(cuò)了，所以不用補(bǔ)了。這又何嘗不是另一種補(bǔ)完呢（

后記：

? 話說(shuō)后天就考高數(shù)了我還一道題沒(méi)寫(xiě)是不是有點(diǎn)不務(wù)正業(yè)了（