stone/reverse/string/digit(完美消除)

stone：

【問題描述】

? 平平去海邊度假，海邊有一片美麗的鵝卵石灘。平平在鵝卵石灘上撿了 $n$ 塊美麗的 鵝卵石，并把它們排成一個序列，其中排第 i 位的鵝卵石的美麗度為 a_i。平平想從里面 按照原序列的順序挑選出一個鵝卵石的子序列，使得在這個子序列里的后一塊鵝卵石的美 麗度不比前一塊低。平平還想知道，他這么做能得到的最長的子序列長度是多少。 平平想了想，認為這個問題很 naive，于是他決定將上述鵝卵石序列首尾相連，組成 一個鵝卵石環，然后計算在這個環上的滿足要求的最長子序列的長度。

【輸入】 輸入第一行包含一個整數 T，代表數據組數。 接下來有 2T 行，每兩行代表一組數據。 每組數據的第一行包含一個整數 n ，代表鵝卵石的個數。 第二行包含 n 個非負整數，依次是 a_1 到 a_n，代表 n 個鵝卵石各自的美麗程度。 保證所有數據隨機生成。具體地，每一項 a_i 獨立地從 [1,n] 內的整數中等概率選 取。

【輸出】 輸出共 T 行，每行一個正整數 m，表示該組數據中最長的滿足要求的子序列的長度。

【輸入樣例】

? 2

? 3

? 3 1 2

? 10

? 1 3 8 8 1 7 9 3 10 10

【輸出樣例】

? 3

? 7

【輸出說明】 對第一組數據，選取的子序列為 a_2, a_3, a_1 。

? 1<=n<=1e4,t=10;

先破環成鏈

設DP數組dp[i][j]=k 表示區間[i,j]的最長不下降子序列期望長度為k

但是發現這樣會(T+M)LE

區間隨機生成下數據的最長不下降子序列期望長度為$\sqrt{n}$，

所以我們可以將dp方城寫成dp[i][k]=j，表示右端點為i，最長不下降子序列長度為k的最右左端點為j，用樹狀數組維護即可

?

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define rep(i,a,b) for(register int i=a;i<=b;i++) #define lowbit(x) x&(-x) using namespace std; int n,t,a[20005],dp[20005][208],c[10050],res; inline int read(){int x=0,f=1;char ch=getchar();while('0'>ch || ch>'9'){if(ch=='-') f=-1; ch=getchar();}while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x*f; } struct Tree{inline void upt(int x,int y){while(x<=n) c[x]=max(c[x],y),x+=lowbit(x);}inline int find(int x){int ans=0;while(x) ans=max(ans,c[x]),x-=lowbit(x);return ans;} }Q; int main(){scanf("%d",&t);while(t--){scanf("%d",&n); res=0;memset(dp,0,sizeof(dp));rep(i,1,2*n) dp[i][1]=i;rep(i,1,n) a[i]=read(),a[i+n]=a[i];rep(j,2,207){memset(c,0,sizeof(c));rep(i,1,2*n){int zlk=Q.find(a[i]);if(i-zlk<n && zlk) dp[i][j]=zlk,res=j;if(dp[i][j-1]) Q.upt(a[i],dp[i][j-1]); }}printf("%d\n",res);}return 0; }

?

reserve：

題目大意：求將環上任意一個區間翻轉后，環上的最大區間和(n<=1e6)

本題可以轉換為求任意兩個連續區間的最大和

首先處理鏈上的情況:dp[i][j][0/1]表示前i個數選了j個區間，本數選沒選，推下DP方程

之后我們只需再強智選環的環首尾，再跑遍dp即可

?

/* 通過翻轉，我們可以使換上任意兩個連續區間并成一個區間 所以答案顯然是換上兩個最大的連續區間的和 分為兩種情況 1.強制選還上首尾的區間 2.區間不包含環的首尾，直接在鏈上DP dp[i][j][k]表示到第i位，選了j個子段的最大值 ，第i個數選沒選(k=0/1) */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define rep(i,a,b) for(int i=a;i<=b;i++) #define int long long using namespace std; int n,dp[200040][3][2],a[200005],maxn=-1000000000,b; signed main(){scanf("%lld",&n);rep(i,1,n){scanf("%lld",&a[i]),maxn=max(maxn,a[i]);if(a[i]>=0) b++;}if(b<2){printf("%lld",maxn); return 0;}memset(dp,128,sizeof(dp));dp[0][0][0]=0;rep(i,1,n){rep(j,0,2){if(j>=1) dp[i][j][1]=max(dp[i-1][j][1]+a[i],max(dp[i-1][j-1][0]+a[i],dp[i-1][j-1][1]+a[i]));dp[i][j][0]=max(dp[i-1][j][1],dp[i-1][j][0]);}}maxn=max(dp[n][2][0],dp[n][2][1]);memset(dp,128,sizeof(dp));dp[1][0][1]=a[1];rep(i,2,n){rep(j,0,2){if(j>=1) dp[i][j][1]=max(dp[i-1][j][1]+a[i],max(dp[i-1][j-1][0]+a[i],dp[i-1][j-1][1]+a[i]));else dp[i][j][1]=dp[i-1][j][1]+a[i];dp[i][j][0]=max(dp[i-1][j][1],dp[i-1][j][0]);}}printf("%lld",max(maxn,dp[n][2][1]));return 0; }

?

String:

【問題描述】

給出一個長度為 2N 的數字串，這個數字串中的每一位都是 0-9 的整數，其中，有一 些位置上的數是我們已知的，還有一些位置上的數未知，當且僅當這個數字串滿足：前 N 個數碼的乘積等于后 N 個數碼的乘積的時候，我們稱這個數字串是一個好的數字串，給出 一個有若干個位置未知的數字串，請你求出在未知處填上數碼之后，使得這個串是一個好 的串的方案數

【輸入】 輸入第一行包含一個整數 N 第二行一個長度為 2N 的數字串，其中有一些位置上為問號，代表這些位置上的字符未 知。

【輸出】 所求的方案數

【輸入樣例】

? ?2

? ?2??3

【輸出樣例】

? ?4

【樣例說明】

? (3,2) (6,4), (9,6), (0,0) 不難證明沒有其它的解

【數據規模】

? 對于 30%數據：1≤n≤4

? 對于所有數據：1≤n≤18

? 比較簡單的數位DP

? 將0~9中的質數列出來，設一個五維DP，隨便推推dp式子

? ?

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define int long long #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; int dp[40][60][40][30][30],n,b1,b2,a1,a2,res,b[10]={0,0,1,0,2,0,1,0,3,0}; int c[10]={0,0,0,1,0,0,1,0,0,2},d[10]={0,0,0,0,0,1,0,0,0,0},e[10]={0,0,0,0,0,0,0,1,0,0}; int ksm(int x,int y){int r=1;while(y){if(y&1) r=(r*x);x*=x;y>>=1;}return r; }int C(int x,int y){int res=1;rep(i,y-x+1,y) res*=i;rep(j,1,x)res/=j;return res; } char a[40]; signed main(){ // freopen("string.out","w",stdout);scanf("%lld%s",&n,a+1);dp[0][0][0][0][0]=1;rep(i,1,n){if(a[i]=='0') ++b1;if(a[i]=='?') ++b2;}rep(i,n+1,n*2){if(a[i]=='0') ++a1;if(a[i]=='?') ++a2;}int ans=0,ans2=0;rep(i,1,a2) ans=ans+C(i,a2)*ksm(9,a2-i);if(a1) ans+=ksm(9,a2);rep(i,1,b2) ans2=ans2+C(i,b2)*ksm(9,b2-i);if(b1) ans2+=ksm(9,b2);if(a1 || b1){printf("%lld",ans2*ans);return 0;}res=ans*ans2;rep(i,1,2*n){rep(j,0,54){rep(k,0,36){rep(l,0,18){rep(m,0,18){if(i<=n){if(a[i]!='?'){if(j-b[a[i]-'0']>=0 && k-c[b[a[i]-'0']]>=0 && l-d[b[a[i]-'0']]>=0 && m-e[b[a[i]-'0']]>=0) dp[i][j][k][l][m]=dp[i-1][j-b[a[i]-'0']][k-c[a[i]-'0']][l-d[a[i]-'0']][m-e[a[i]-'0']];else dp[i][j][k][l][m]=0;continue;}rep(t,1,9) if(j-b[t]>=0 && k-c[t]>=0 && l-d[t]>=0 && m-e[t]>=0){dp[i][j][k][l][m]+=dp[i-1][j-b[t]][k-c[t]][l-d[t]][m-e[t]];}}else{if(a[i]!='?') dp[i][j][k][l][m]=dp[i-1][j+b[a[i]-'0']][k+c[a[i]-'0']][l+d[a[i]-'0']][m+e[a[i]-'0']];else rep(t,1,9) dp[i][j][k][l][m]+=dp[i-1][j+b[t]][k+c[t]][l+d[t]][m+e[t]];}}}}}}cout<<dp[2*n][0][0][0][0]+res;return 0; }

?

Digit：

【問題描述】

對于一個正整數n，定義一個消除操作為選定[L，R，x]，如果n的第L到第R位上的數 字都≥x，并且這些數都相等，那么該操作合法(從低位到高位編號從1開始),并將這些位數 上的數減x。 定義n的最小操作數為對一個數操作最少的次數使得這個數變成0的次數。如1232的最 小操作數為3，一個合法解是[2,2,1]，[1,3,2]，[4,4,1]。 試求[L，R]內最小操作數為k的數的個數。

【輸入】 輸入為三個正整數L、R、k。

【輸出】 輸出答案。

【輸入輸出樣例】

? digit.in

? 10 21 2

? digit.out

? 9

【輸入輸出樣例解釋】 [10，21]區間內除10、11、20是最小操作數為1的以外均是最小操作數為2。

【數據范圍】 對于30%的數據，1≤L≤R≤107。 對于70%的數據，1≤L≤R≤109。 對于100%的數據，1≤k≤109，1≤L≤R≤1018。 保證數據有一定梯度。

對于一個數字，我們按位將它拆分，發現如果第i位(從左往右)大于第i-1位，那么這一位肯定要多進行一次操作，使他砍到和第i-1位一樣高，所以這就是一個單調棧，反之就將棧內比它大的數彈出即可

設dp[i][j][k]表示第計算到第i位，狀態為j，需進行k次操作的數的數量，狀態即為棧內有(1<<i)或沒有(0<<i)該數，跑數位DP

CODE：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define int long long #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; int dp[21][2025][21],tot,m[21],pre[2025][21],k; int wk(int y){if(y<0) return 0;return 1<<y;} int DP(int x,int y,int t,int z){if(t>k) return 0;//cout<<"H";if(x==0 && t==k) return 1;else if(x==0) return 0;if(!z && dp[x][y][t]!=-1) return dp[x][y][t];int ans=0,en=z?m[x]:9;rep(i,0,en){int hh=t;if(!(y&(wk(i-1))) && i) ++hh;ans+=DP(x-1,pre[y][i],hh,z && en==i);}if(!z) dp[x][y][t]=ans;return ans; } int cnt(int x){tot=0;memset(dp,-1,sizeof(dp));while(x){m[++tot]=x%10; x/=10;}return DP(tot,0,0,1); } signed main(){ // freopen("digit.out","w",stdout);int l,r; scanf("%lld%lld%lld",&l,&r,&k);rep(i,0,2024) rep(j,0,9) pre[i][j]=(((1<<j)-1)&i)|wk(j-1);printf("%lld",cnt(r)-cnt(l-1));return 0; }

?

轉載于:https://www.cnblogs.com/handsome-zlk/p/11272031.html

總結

以上是生活随笔為你收集整理的stone/reverse/string/digit(完美消除)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。