此文章可以使用目錄功能喲↑(點選上方[+])
被自己蠢哭,去年還能進一下複賽,今年複賽都沒戲了...
Accept: 0 Submit: 0
5
1 6 2 4 4
36
16
12
6
為了枚舉最小值點,我們需要知道每一個點作為最小值點左右可以延伸的最大範圍l[i],r[i],求這兩個數組可以用dp來做
預處理完之後,枚舉最小值點,更新長度為r[i]-l[i]+1的區間的答案
枚舉完之後,我們得到了一組值,但這并不是最後的答案
這是因為我們發現假如有一個最優區間,我們一定可以正好處理到或者處理到比這個區間小的區間,也就是說我們求的區間最大的值具有向下的包含性
舉例來說,假如目前處理的區間為l[i],r[i],得到了答案ans,那麼任何長度小于等于r[l]-l[I]+1的區間的答案都至少為ans
是以我們再用線性的時間遞推求出答案即可
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
const int N = 100005;
const int M = 40;
const int inf = 100000000;
const int mod = 2009;
int s[N],n,maxnum[N][20],l[N],r[N];
__int64 ans[N];
void RMQ() //預處理 O(nlogn)
{
int i,j;
int m=(int)(log(n*1.0)/log(2.0));
for(i=1;i<=n;i++)
maxnum[i][0]=s[i];
for(j=1;j<=m;j++)
for(i=1;i+(1<<j)-1<=n;i++)
maxnum[i][j]=max(maxnum[i][j-1],maxnum[i+(1<<(j-1))][j-1]);
}
int Ask_MAX (int a,int b) //O(1)
int k=int(log(b-a+1.0)/log(2.0));
return max(maxnum[a][k],maxnum[b-(1<<k)+1][k]);
int main()
int i,k;
while(~scanf("%d",&n))
{
memset(ans,0,sizeof(ans));
for(i=1;i<=n;i++)
{
scanf("%d",&s[i]);
l[i]=r[i]=i;
}
RMQ();
for(i=2;i<=n;i++)
k=i-1;
while(s[i]<=s[k])
k=l[k]-1;
l[i]=k+1;
for(i=n-1;i>0;i--)
k=i+1;
k=r[k]+1;
r[i]=k-1;
ans[r[i]-l[i]+1]=max(ans[r[i]-l[i]+1],(__int64)Ask_MAX(l[i],r[i])*s[i]);
ans[i]=max(ans[i+1],ans[i]);
printf("%I64d\n",ans[i]);
}
return 0;
Time Limit: 4000/2000 mSec(Java/Others) Memory Limit : 65536 KB
有一個無限大的矩形，初始時你在左上角（即第一行第一列），每次你都可以選擇一個右下方格子，并瞬移過去（如從下圖中的紅色格子能直接瞬移到藍色格子），求到第n行第m列的格子有幾種方案，答案對1000000007取模。
多組測試資料。
兩個整數n,m(2≤n,m≤100000)
一個整數表示答案
4 5
10
解題思路:除去起點(1,1)和終點(n,m)已經固定,中間能經過的是一個(n-2)*(m-2)的矩陣
然後我們可以在這個矩陣裡取0個(就是直接從起點跳到終點)、1個、2個……min(n,m)-2個間接點
而對于取i個間接點,其實就是确定這i個間接點行數與列數有多少種取法
于是,我們得到了組合數公式(假設n<m,此題n,m和m,n結果是一樣的,過我們可以交換n,m實作n<m)
組合數的求解我們可以交給Lucas定理,但是這個公式,我們還需要化簡,不然計算100000項的組合數還是會逾時
為了讓式子看起來更簡潔,對于輸入的n與m,我們預處理-2,即n-=2,m-=2,這樣上述式子就變成了
化簡
剩下的就是套Lucas模闆了,嫌時間長的還可以進行階乘預處理
const int M = 100;
const int inf = 1600000000;
const int p = 1000000007;
typedef long long LL;
LL quick_mod(LL a, LL b)
LL ans = 1;
a %= p;
while(b)
if(b & 1)
ans = ans * a % p;
b--;
b >>= 1;
a = a * a % p;
return ans;
LL C(LL n, LL m)
if(m > n) return 0;
for(int i=1; i<=m; i++)
LL a = (n + i - m) % p;
LL b = i % p;
ans = ans * (a * quick_mod(b, p-2) % p) % p;
LL Lucas(LL n, LL m)
if(m == 0) return 1;
return C(n % p, m % p) * Lucas(n / p, m / p) % p;
__int64 n,m;
int i;
while(~scanf("%I64d%I64d",&n,&m))
n-=2,m-=2;
if(n>m)
swap(n,m);
printf("%I64d\n",Lucas(m+n,n));
const int N = 200005;
const int mod = 1000000007;
__int64 fac[N];
void init()//階乘預處理
fac[0]=1;
for(int i=1;i<=N;i++)
fac[i]=i*fac[i-1]%mod;
__int64 pow_mod(__int64 a,__int64 b)
__int64 s=1;
a=a%mod;
if(b&1)
s=s*a%mod;
a=a*a%mod;
b>>=1;
return s;
__int64 C(int n,int m)
if(n==0||m==0)
return 1;
return fac[n]*pow_mod(fac[m]*fac[n-m]%mod,mod-2)%mod;
int n,m;
init();
while(~scanf("%d%d",&n,&m))
n-=2;m-=2;
printf("%I64d\n",C(m+n,min(n,m))%mod);
Time Limit: 8000/4000 mSec(Java/Others) Memory Limit : 65536 KB
一行表示答案
5 2 3
1 2 3 4 6
2 5
1 4
解題思路:此題的做法有很多種,不過有種利用STL來解的做法,我覺得挺巧妙的
首先利用vector将區間分組,将所有具有公共左端點的區間劃分成一組,比如[3,7],[3,11],[3,4]等,這些都是一組的
接下來就是利用multiset來進行模拟了(順帶提一句,這裡不能用set,而用multiset,是因為set無法存儲重複相同的數)
對于目前所在位置i,将所有以i作為左端點的區間右端點值插入multiset(multiset内的數預設從小到大排列)中
若multiset的大小超過了k,那我就删除multiset内最小的值直到小于等于k(之是以删除最小的值,是因為在左端點固定的情況下,右端點越小,會使得區間交的位置數越少)
當且僅當multiset大小恰好等于k,且multiset中目前最小的右端點值≥i時,我們找到了一種符合題目要求的區間取法,于是我們更新答案
當然,在開始的時候,我們需要預處理前n項和sum[n]
#define bitnum(a) __builtin_popcount(a)
const int M = 10;
__int64 sum[N],ans;
multiset<int> s;
vector<int> v[N];
int n,k,m,i,j,l,r;
while(~scanf("%d%d%d",&n,&k,&m))
s.clear();ans=0;
scanf("%I64d",&sum[i]);
sum[i]+=sum[i-1];
v[i].clear();
for(i=0;i<m;i++)
scanf("%d%d",&l,&r);
v[l].push_back(r);
for(j=0;j<v[i].size();j++)
s.insert(v[i][j]);
while(s.size()>k)
s.erase(s.begin());
if(s.size()==k&&*s.begin()>=i)
ans=max(ans,sum[*s.begin()]-sum[i-1]);
printf("%I64d\n",ans);
Time Limit: 12000/6000 mSec(Java/Others) Memory Limit : 65536 KB
中位數定義為所有值從小到大排序後排在正中間的那個數，如果值有偶數個，通常取最中間的兩個數值的平均數作為中位數。
現在有n個數，每個數都是獨一無二的，求出每個數在多少個包含其的區間中是中位數。
多組測試資料
第一行一個數n(n≤8000)
第二行n個數，0≤每個數≤
N個數，依次表示第i個數在多少包含其的區間中是中位數。
1 2 3 4 5
1 2 3 2 1
解題思路:很顯然,此題O(n^2logn)的暴力做法必然會TLE,是以我們要想辦法做到O(n^2)的複雜度
首先對于第i個數,我們從i-1個數開始遞減,分别與第i個數進行比較,假設比第i個數大的數的個數即為l,比第i個數小的數的個數即為r,dp[l-r=k]則為[比第i個數大的數的個數]比[比第i個數小的數的個數]多k個的區間個數,那要保證第i個數是區間内的中位數,我隻需要在第i個數的右邊找有多少個[比第i個數小的數的個數]比[比第i個數大的數的個數]多k個的區間,這樣兩個區間連接配接起來,正好[比第i個數大的數的個數]與[比第i個數小的數的個數]一樣多,這樣,第i個數就是此區間内的中位數
另外,因為數組下标必須為非負整數,故把數組的中心點移至8000,即dp[8000+k],這樣就保證了下标一定是符合要求的
const int N = 8005;
const int M = 8000;
int s[N],dp[2*N];
int n,i,j,k,ans;
for(i=0;i<n;i++)
memset(dp,0,sizeof(dp));
dp[M]=1;
for(k=0,j=i-1;j>=0;j--)
{
if(s[j]>s[i])
k++;
else
k--;
dp[M+k]++;
}
for(ans=dp[M],k=0,j=i+1;j<n;j++)
ans+=dp[M-k];
printf("%d%c",ans,i!=n-1?' ':'\n');
菜鳥成長記