NOIP模拟测试「简单的区间·简单的玄学·简单的填数·简单的序列」
簡單的區間
$update$
終于$AC$了
找到$(sum[r]+sum[l](sum表示以中間點為基準的sum)-mx)\%k==0$的點
注意這里$sum$表示是以$mid$為基準點,(即$sum[l]$為后綴和,$sum[r]$為前綴和)
回憶$(sum[r]-sum[l])\%k==0$這個經典問題做法(入陣曲簡化版),開桶,桶里維護$sum[l]\%k$,那么$r$貢獻就是桶里$sum[r]\%k$個數
于是這個題開桶維護$sum$,問題轉化為求$max$即可
記錄$max$位置是否$>mid$,區別對待
設$f[i][0]$表示$max$在$mid$右面,$f[i][1]$表示$max$在$mid$左面
$f[i][0]$存下右面$sum[r]-mx$,找桶里是否存在左面$sum[l]$
$f[i][1]$存下右面$sum[r]$ 找到左面是否存在$mx-sum[l]$
完了
?
簡單的玄學
題解
題目中說至少兩個相同那么答案就所有方案-全不相同
所有方案${(2^n)}^m=2^{n*m}$,
互不相同,首先第一個隨便選剩下避開已經選過就行$2^n*2^{n-1}......2^{n-m+1}$
那么題目很傻逼的讓你取模并且約分,你需要先約分再取模(取模再約分的話這個題就太水了,所以是先約分再取模)
思考怎么約分
下面全是$2$多少次方,于是我們看上面多少個二就行了
$2^n*(2^{n}-1)......({2^n}-m+1)$很惡心,思考轉化
性質:$2^n-x$中二個數$=$$x$中二的個數
證明:假設$x$可以表示為$j*(2^w)$(j可以是分數),乘法分配率$2^w*(2^{n-w}-j)$后面這個里面沒有別的$2$因子了,原式$=$$2^w$,又$j$中沒有$2$因子故相乘因子數不變,得證
那么原式就變成求$(m-1)!$里$2$因子數
可以簡單求
for(ll i=1;(1ll<<i)<=m-1;i++){(ercnt+=(m-1)/(1ll<<i));}例如$1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$這個序列
分別有$(2^1)*2$,$(2^2)*1$,$(2^3)*1$那么就是$8/8+8/4+8/2$
可以看作$/2$時給所有有$2$因子填上一個二(即$2$,$4$,$6$,$8$中填一個2),此時$4$還剩$1$個沒填$8$還剩$2$個沒填
$/4$給$4$,$8$里填此時$8$還剩$1$個沒填
最后$/8$,全部填滿
代碼
#include<bits/stdc++.h> using namespace std; #define ll long long const ll mod=1e6+3; const ll phi=1e6+2; ll x,y,n,m; ll meng(ll x,ll k){ll ans=1;for(;k;k>>=1,x=x*x%mod)if(k&1)ans=ans*x%mod;return ans; } ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y); } int main(){ // freopen("sd.txt","w",stdout);scanf("%lld%lld",&n,&m); /* if(log(m)>n){printf("1 1\n");return 0;} */ ll maxn=meng(2,n%phi);y=meng(maxn,m%phi);x=1;ll ercnt=n; for(ll i=0;i<m;i++){ // printf("maxn-i=%lld i=%lld m=%lld x=%lld\n",maxn-i,i,m,x);x=x*(maxn-i)%mod;if(!x) break;}//2逆元500002for(ll i=1;(1ll<<i)<=m-1;i++){(ercnt+=(m-1)/(1ll<<i));printf("ercnt=%lld 1<<=%lld\n",ercnt-n,1ll<<i);}y=y*meng(500002,ercnt)%mod;x=x*meng(500002,ercnt)%mod;printf("%lld %lld\n",(y-x+mod)%mod,y); } View Code簡單的填數
題解
一個$up$代表填的上界,$down$代表填的下界
先不考慮已經填了的
$up$兩位一進,$down$五位一進
考慮已經填的
先考慮上界
若$a[i]>up$比上界大肯定不合法
若$a[i]=up$取$min(2,up)$
若$a[i]<up$則將$up$調整到$a[i]$次數變為$2$
下界類似
若$a[i]<down$比下界小不合法
若$a[i]>down$將$down$調整到$a[i]$
統計答案時反著掃
序列為什么不是$up$呢
7 0 0 0 2 0 2 0 正解 2 1 1 2 2 2 2 2 用up: 2 1 1 2 2 3 2 2代碼
/* 7 0 0 0 2 0 2 0 hack 2 1 1 2 2 2 2 2 up: 2 1 1 2 2 3 2 2 10f */ #include<bits/stdc++.h> using namespace std; #define ll long long #define A 1010101 struct node {ll cnt,x; }up[A],down[A]; ll n; ll a[A],tong[A]; int main(){ // freopen("da.in","r",stdin); freopen("ans.bf","w",stdout);scanf("%lld",&n);for(ll i=1;i<=n;i++){scanf("%lld",&a[i]);}if(a[1]!=1&&a[1]!=0){printf("-1\n");return 0;}up[1].cnt=1,up[1].x=1;down[1].cnt=1,down[1].x=1;for(ll i=2;i<=n;i++){up[i]=up[i-1],down[i]=down[i-1];if(++up[i].cnt>2) up[i].cnt=1,up[i].x++;if(++down[i].cnt>5) down[i].cnt=1,down[i].x++;if(a[i]){if(up[i].x>a[i]){up[i].x=a[i];up[i].cnt=2;}else if(up[i].x==a[i]){up[i].cnt=min(up[i].cnt,2ll);}if(down[i].x<a[i])down[i].x=a[i],down[i].cnt=1;if(up[i].x<a[i]||down[i].x>a[i]){printf("-1\n");return 0;}}}if(up[n].cnt==1){up[n].x=up[n-1].x;}if(up[n].x<down[n].x){printf("-1\n");return 0;}printf("%lld\n",up[n].x);tong[up[n].x]=1;a[n]=up[n].x;for(ll i=n-1;i>=1;i--){if(!a[i]){ll t=min(a[i+1],up[i].x);if(tong[t]==5) t--;a[i]=t;}tong[a[i]]++;}for(ll i=1;i<=n;i++){printf("%lld ",a[i]);} } View Code?
簡單的序列
這是一個簡單$dp$,但我覺得很棒在此寫下題解
真的非常簡單,
有一個長度$n$括號序列(只有$"()"$ ),給定其中長度為$m$一段,求滿足括號匹配方案數
$n,m<=1e6$ $n-m<=4000$
題解
?
性質:我們發現一個合法匹配序列左擴號時刻比右括號多(顯然),最后左擴號數量等于右括號數量
設$f[i][j]$表示長度為$i$序列,左擴號比右括號多$j$個方案數
那么類似的設$g[i][j]$為右括號比左擴號多$j$的方案數
(其實$f$和$g$值完全一樣)
?
轉移非常簡單
當前括號可能是$($則貢獻$f[i][j]=f[i-1][j-1]$為$)$則$f[i][j]=f[i-1][j+1]$
總貢獻$f[i][j]=f[i-1][j-1]+f[i-1][j+1]$
類似的$g[i][j]=g[i-1][j-1]+g[i-1][j+1]$
那么思考統計答案
其實也非常簡單
枚舉第一段長度$i$,第一段左擴號比右括號多$j$,設給定序列左擴號比右括號多$j$
$ans=\sum\limits_{i=1}^{i<=n-m} \sum\limits_{j=0}^{j<=i} f[i][j]*g[(n-m)-i][j+tot]$
注意判是否合法
代碼
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 4040 const ll mod=1e9+7; char c[2020202]; ll f[A][A]; ll tot,mint,n,m,ans; int main(){ // freopen("da.in","r",stdin); freopen("ans.bf","w",stdout);scanf("%lld%lld",&n,&m);scanf("%s",c+1);for(ll i=1;i<=m;i++){if(c[i]=='(')tot++;else tot--;if(i==1) mint=tot;else mint=min(mint,tot);}f[0][0]=1;for(ll i=1;i<=n-m;i++){for(ll j=0;j<=i;j++){if(j==0) f[i][j]=f[i-1][j+1];else f[i][j]=(f[i-1][j+1]+f[i-1][j-1])%mod;}}for(ll i=0;i<=n-m;i++){for(ll j=0;j<=i;j++){if(j+mint>=0&&j+tot<=n-m)ans=(ans+f[i][j]*f[(n-m)-i][j+tot]%mod)%mod;}}printf("%lld\n",ans); } View Code我沒數據,也沒法提交,和$std$對拍了一下
下面是我的數據生成及對拍
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main(){ 4 system("g++ bf.cpp -o bf"); 5 system("g++ sol.cpp -o sol"); 6 system("g++ da.cpp -o da"); 7 int rp=0; 8 while(++rp){ 9 cout<<rp<<" "; 10 system("./da"); 11 system("./sol"); 12 system("./bf"); 13 if(system("diff -B -b ans.sol ans.bf")){ 14 puts("WA"); 15 while(1); 16 } 17 puts("AC"); 18 } 19 } 對拍 1 #include<bits/stdc++.h> 2 using namespace std; 3 int main(){ 4 freopen("da.in","w",stdout); 5 srand(time(NULL)); 6 7 int m=rand()%10000+300; 8 int c=rand()%m+1; 9 while(m-c>2000){ 10 c=rand()%m+1; 11 } 12 cout<<m<<" "<<c<<endl; 13 for(int i=1;i<=c;i++){ 14 if(rand()%2){ 15 printf("("); 16 } 17 else printf(")"); 18 } 19 cout<<endl; 20 } 數據生成?
?
轉載于:https://www.cnblogs.com/znsbc-13/p/11474038.html
總結
以上是生活随笔為你收集整理的NOIP模拟测试「简单的区间·简单的玄学·简单的填数·简单的序列」的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： NOIP模拟测试34「次芝麻·呵呵呵·长
- 下一篇： 小班教案《找小猫》反思