題目鏈接：點擊查看

題目大意：規(guī)定一個數(shù)列中在不改變內(nèi)部順序的前提下，至少存在著一組(i,j)滿足：

i<j

a[i]<a[j]

就稱該數(shù)列為上升數(shù)列，現(xiàn)在給出n組數(shù)列，每兩組數(shù)列可以進行拼接操作，即Sx={1,2,3},Sy={4,5,6}，Sx+Sy={1,2,3,4,5,6}，Sy+Sx={4,5,6,1,2,3}，現(xiàn)在問n^2種組合可以組成多少個上升數(shù)列

題目分析：挺綜合的一道題目吧，情況得討論清楚，不然很容易過了第一個樣例然后過不去第二個樣例。。不過這個題目的樣例給的很良心，三個樣例都過掉基本上就已經(jīng)AC了

首先我們可以給數(shù)列分類，分為上升數(shù)列，如{0,2,0,2}，也就是單獨拿出來就是一個上升數(shù)列，剩下的就是非上升數(shù)列，非上升數(shù)列也包括兩種，一種是下降數(shù)列，也就是{8,8,7,7,6,6}，還有一種是相等的數(shù)列，如{6,6,6}，下降數(shù)列和相等數(shù)列我們姑且視為一種數(shù)列，分完類后我們稱上升數(shù)列為up，其他數(shù)列為down，則有下列四種組合方式：

up1+up2：上升數(shù)列

up+down：上升數(shù)列

down+up：上升數(shù)列

down1+down2：如果down1中的最小值小于down2中的最大值，則是上升數(shù)列，否則不是

分析到這里就差不多了，我們可以預(yù)處理出所有的上升數(shù)列，因為只要和上升數(shù)列有組合關(guān)系的數(shù)列組合后的新數(shù)列一定是上升數(shù)列，那么對答案的貢獻為2*(n-1)+1，n-1代表的是除了當(dāng)前上升數(shù)列之外的n-1個數(shù)列與其拼接，前后為兩種情況，故乘二，最后的加一是其本身前后拼接而成的，不過需要注意一點，也是卡了我好久的一個細(xì)節(jié)，如果有多個上升數(shù)列，在處理第一個上升數(shù)列時，n-1個其他數(shù)列中也會存在上升數(shù)列，所以會重復(fù)，我們可以選擇在處理完第一個上升數(shù)列后記錄一下，以后再處理類似情況的時候就不再記錄就好了

剩下的就是用簡單dp模擬第四種情況了，可以枚舉n次，讓每一個數(shù)列位于前面的位置時的貢獻，也可以記錄讓每一個數(shù)列位于后面時的貢獻，看個人喜好吧

最后就是記得開longlong，第一發(fā)沒開longlong白給了一發(fā)。。

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;int dp[N],mmax[N],vis[N];//dp[i]:從0~i有多少個最小值，mmax[i]:第i個數(shù)列的最大值，vis[i]:第i個數(shù)列是否為上升數(shù)列int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,nn;LL ans=0;scanf("%d",&n);nn=n;//用nn標(biāo)記還剩多少個數(shù)列，用來專門處理上升數(shù)列重復(fù)計算的情況for(int i=1;i<=n;i++){int mmin=inf;mmax[i]=-inf;int num;scanf("%d",&num);while(num--){int x;scanf("%d",&x);mmin=min(mmin,x);mmax[i]=max(mmax[i],x);if(x>mmin)vis[i]=true;}if(vis[i])//如果當(dāng)前數(shù)列為上升數(shù)列，計算貢獻，并令nn--，后續(xù)不再重復(fù)計算{ans+=2*(nn-1)+1;nn--;}elsedp[mmin]++;}for(int i=1;i<N;i++)//維護一下dp數(shù)組dp[i]+=dp[i-1];for(int i=1;i<=n;i++){if(!vis[i])ans+=dp[mmax[i]-1];}printf("%lld\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1284B New Year and Ascent Sequence(乱搞)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。