CCF-NOIP-2018 提高組(複賽) 模擬試題(三)
T1 取球遊戲
問題描述
現有 \(N\) 個小球，依次編號為 \(1\) 到 \(N\) ，這些小球除了編號以外沒有任何區別。從這 \(N\) 個小球中取出 \(M\) 個，請問有多少種取球方案使得在取出的 \(M\) 個小球中，編號最小的小球的編號為 \(K\) 。
考慮到方案數可能很大，請輸出方案數對
\(1e9+7\)
去模的值。
輸入格式
輸入資料只有一行，包含三個整數 \(N,M,K\) 。
輸出格式
一個整數，表示取法總數對 \(1e9+7\) 取模的值。
樣例
| 樣例輸入1 |
|---|
| 4 2 2 |
| 樣例輸出1 |
|---|
| 2 |
| 樣例輸入2 |
|---|
| 888 222 555 |
| 樣例輸出2 |
|---|
| 424089030 |
題解
板子題，盧卡斯定理。這裡給盧卡斯定理的板子寫法。
#include<bits/stdc++.h>
#define p 1000000007
#define maxn 10000005
using namespace std;
long long E[maxn];
inline void init(){
E[0]=1;
for(register int i=1;i<maxn;i++)E[i]=E[i-1]*i%p;
}
inline long long inv(long long a,long long m){
if(a==1)return a;
return inv(m%a,m)*(m-m/a)%m;
}
inline long long lucas(long long n,long long m){
long long ans=1;
while(n&&m){
long long a=n%p;
long long b=m%p;
if(a<b)return 0;
ans=ans*E[a]%p*inv(E[a-b]*E[b]%p,p)%p;
n/=p;
m/=p;
}
return ans;
}
long long n,m,k;
int main(){
init();
cin>>n>>m>>k;
n-=k;m-=1;
printf("%lld",lucas(n,m));
return 0;
}
T2 維修機器人
問題描述
土豪賈老師擁有 \(n\) 個機器人。這 \(n\) 個機器人排成一行，第 \(i\) 個機器人的身高
為 \(h_i\) 。賈老師發現這些機器人的身高參差不齊，看起來十分不美觀，於是決定對
它們的身高進行修改。
賈老師希望修改後的機器人隊伍身高值單調，形式化地說，滿足下面兩個條
件之一的機器人隊伍是合格的隊伍 。
- \(h_1\le h_2\le ... \le h_{n-1} \le h_n\)
- $h_1 \ge h_2\ge...\ge h_{n-1} \ge h_n $
增加第 \(i\) 個機器人的身高，需要的費用為 \(m_1\) ，減小第 \(i\) 個機器人的身高，需
要的費用為 \(m_2\) 。注意，費用與是否增加和是否減小有關，與具體增加或減小的
數值無關。對於一個身高為 \(5\) 的機器人，把它的身高增加到 \(6\) 和增加到 \(100\) 所需
要的費用都為 \(m_1\) 。
賈老師希望你能幫他計算出，為了得到合格的機器人隊伍，所需要花費的最
小費用是多少。 由於某些特殊的原因， 我們保證這 \(n\) 個機器人不同的身高不會超
過
\(1,000\)
個。
輸入格式
輸入檔案共包含兩行。
第一行共包括三個正整數，分別為 \(n,m_1,m_2\) ，含義如上文所述。
第二行包含 \(n\)個整數，依次表示每個機器人的身高
\(h_i\)
。
輸出格式
共一行，包含一個整數，表示賈老師所需修理費用的最小值。
樣例
| 樣例輸入1 |
|---|
| 5 2 3 |
| 1 2 3 5 4 |
| 樣例輸出1 |
|---|
| 2 |
| 樣例輸入2 |
|---|
| 15 5 7 |
| 10 10 10 10 10 9 2 8 7 6 1000 5 3 4 1 |
| 樣例輸出2 |
|---|
| 17 |
資料規模與規定
題解
首先考 \(m_1=m_2\) 的情況，因為升高或降低一個機器人的高度所需要的花費一樣，所以我們只需要設法用最小的步數將整個序列變為單調遞增或單調遞減即可。此時我們可以選擇求整個序列的最長不上升與最長不下降序列子序列，用 \([n-max(up_{size},down_{size})]*m_1\) 即可得到答案
程式碼如下(75)
#include<bits/stdc++.h>
#define maxn 50005
#define inf 0x3f3f3f3f
using namespace std;
inline char get(){
static char buf[30],*p1=buf,*p2=buf;
return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline long long read(){
register char c=get();register long long f=1,_=0;
while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
return _*f;
}
bool cmp(long long a,long long b){
return a>b;
}//過載upper_bound
long long n,m1,m2;
long long a[maxn],f[maxn],g[maxn];
long long ans1,ans2;
long long cas[maxn];
int main(){
//freopen("robot.in","r",stdin);
//freopen("robot.out","w",stdout);
n=read();m1=read();m2=read();
for(register long long i=1;i<=n;i++)a[i]=read();
if(m1==m2){
for(register long long i=0;i<maxn;i++)f[i]=0,g[i]=0x3f3f3f3f;
g[0]=0;
for(register long long i=1;i<=n;i++){
f[i]=upper_bound(g+1,g+1+ans1,a[i])-g;
g[f[i]]=a[i];
ans1=max(ans1,f[i]);
}
//cout<<ans1<<endl;
for(register long long i=0;i<maxn;i++)f[i]=0,g[i]=0x3f3f3f3f;
g[0]=0;
for(register long long i=1;i<=n;i++){
f[i]=upper_bound(g+1,g+1+ans2,a[i],cmp)-g;
g[f[i]]=a[i];
ans2=max(ans2,f[i]);
}
//cout<<ans2<<endl;
printf("%lld",(n-max(ans1,ans2))*m1);
return 0;
}
return 0;
}
注意到題目的關鍵條件，不同的 \(h_i\) 取值不超過$T=1000 $個。考慮將
讀入資料先離散成 \(1——1000\) 的整數，接下來用動態規劃解決。設 \(dp[i][j]\) 表示將前 i 個機
器人改為單調不減，第 \(i\) 個機器人的身高變為 \(j\) 所需的最小費用。則 \(dp[i][j]=min(dp[i- 1][k])+change(a[i],j)(1≤k≤j)\) 。其中 \(change(x,y)\) 表示把一個機器人的身高從 \(x\) 改為 \(y\) 所需的
費用，這個值只能是 \(m_1\) 或者0或者 \(m_2\) 。
按上述做法時間複雜度為 \(O(nT^2 )。\) 注意到對於當前的決策位置， \(k\) 的可取值越來越
多， 因此可以再同時維護$ min(dp[i-1][k])$， 這樣轉移代價變成 \(O(1)\) ， 時間複雜度變為 \(O(nT)\) ，
可以獲得
\(100\)
分。
#include <bits/stdc++.h>
#define maxn 50005
#define maxt 1005
#define maxl 1000005
#define inf 0x3f3f3f3f
using namespace std;
int n,m1,m2;
int p[maxn];
int t[maxt];
bool vis[maxl];
int level[maxl];
int cnt;
int now,pre;
int minv;
int dp[2][maxt];
int ans=inf;
void init(){
scanf("%d %d %d",&n,&m1,&m2);
for (int i=1;i<=n;i++){
scanf("%d",&p[i]);
if (!vis[p[i]]) t[++cnt]=p[i];
vis[p[i]]=true;
}
sort(t+1,t+cnt+1);
for (int i=1;i<=cnt;i++) level[t[i]]=i;
for (int i=1;i<=n;i++) p[i]=level[p[i]];
}
inline int getdp(){
now=1;
for (int i=1;i<=cnt;i++){
if (i>p[1])dp[now][i]=m1;
else if (i<p[1])dp[now][i]=m2;
else dp[now][i]=0;
}
for (int i=2;i<=n;i++){
now=1-now;pre=1-now;
minv=dp[now][1]=dp[pre][1];
for (int j=2;j<=cnt;j++){
minv=min(minv,dp[pre][j]);
dp[now][j]=minv;
}
for (int j=1;j<p[i];j++)dp[now][j]+=m2;
for (int j=p[i]+1;j<=cnt;j++)dp[now][j]+=m1;
}
int res=inf;
for (int i=1;i<=cnt;i++)res=min(res,dp[now][i]);
return res;
}
void solve(){
ans=getdp();
reverse(p+1,p+n+1);
ans=min(ans,getdp());
printf("%d\n",ans);
}
int main(){
freopen ("robot.in","r",stdin);
freopen ("robot.out","w",stdout);
init();
solve();
return 0;
}
T3 下標
問題描述
Bella 同學在學習 C++的時候，有一天意外地把 \(a[i]\) 寫成了 \(i[a]\) ，發現程
序居然還能正常地編譯和執行！（如果你現在做題做累了，不妨拿出半分鐘時間
試試看這是不是真的！ ）
通過進一步的實驗， Bella 認為，對於任意的兩個合法的表示式 \(A\) 和 \(B\) ，表
達式 \(A[B]\) 與 \(B[A]\) 是等價的。
並且，等價是具有傳遞性的。例如， \(a[b[c]]\) 和 \(c[b][a]\) 是等價的，因為這
兩個表示式都和 \(a[c[b]]\) 等價。
現在給你一些合法的表示式，其中只會出現小寫字母與方括號。你需要對每
個表示式進行若干次這樣的等價變換，得到一個字典序儘可能小的表示式。
更正式地，所有可能出現的表示式恰好能由如下上下文無關文法從符號
Expr生成：
\[Expr -> Term | Expr [ Expr ]\]
\[Term -> Char | Char Term\]
\[Char -> a | b | ... | z\]
而每次的等價變換，是將一個形如 \(Expr1[Expr2]\) 的式子變為
\(Expr2[Expr1]\) ，並且要求 \(Expr1\) 與 \(Expr2\)都能由
\(Expr\)
生成。
輸入格式
輸入檔案的第一行只包含一個正整數 \(T\) ，表示該輸入檔案的資料個數。
接下來
\(T\)
行，每行一個字串，表示一個合法的表示式。
輸出格式
對於每個輸入資料，輸出一行，表示所能得到的字典序最小的表示式。
樣例
| 樣例輸入 |
|---|
| aaa[bbb] |
| a[b[abbb]] |
| b[a[azzz]] |
| x[a][b[a]] |
| 樣例輸出 |
|---|
| aaa[bbb] |
| a[abbb[b]] |
| a[azzz][b] |
| a[b]a[x]] |
題解
將輸入字串的括號進行匹配，找到每個右括號對應的左括號。記
匹配後的字串為 \(S=aaa[A][B]\) ，其中 \(A\) 和 \(B\) 都為 \(expr，B\) 右側的括號為整個字串
的結尾， \(B\) 左側的括號是與最後的右括號匹配的左括號。定義過程 \(solve(S)\) 表示尋找
字串 S 的最小字典序表示，首先遞迴呼叫 \(solve(aaa[A])與solve(B)\) 然後再比較
\(aaa[A][B]\) 與 \(B[aaa[A]]\) 的字典序， 將 \(S\) 變為這兩者中較小的一個。時間複雜度 \(O(n^2)\) ，
期望得分 80 分。在 80 分做法的基礎上，使用連結串列控制整個字串，記錄每個字串
的後繼元素，這可以使得等價變換的時間複雜度變為
\(O(1)\)
即可。
#include<bits/stdc++.h>
using namespace std;
int match[N];
char st[N];int n;
int nxt[N];
bool cmp(int l0,int r0,int l1,int r1){
//puts("===");
for (int i=l0,j=l1;;i=nxt[i],j=nxt[j]){
//printf("%c %c\n",st[i],st[j]);
if (st[i]!=st[j]) return st[i]<st[j];
else if (i==r0||j==r1) return i==r0;
}
}
int cnt[N];
void solve(int &l,int r){
if (isalpha(st[r])){
if (cnt[r+1]-cnt[l]) for (;;);
return;
}
if (match[r]==-1) for (;;);
int mid=match[r],u=mid-1,v=mid+1,ed=r--;
//printf("%d %d %d %d %d %d\n",l,u,mid,v,r,ed);
solve(l,u);
solve(v,r);
if (!cmp(l,u,v,r))
swap(l,v),swap(u,r);
nxt[u]=mid;
nxt[mid]=v;
nxt[r]=ed;
/*for (int i=l;;i=nxt[i]){
putchar(st[i]);
if (i==ed) break;
}
puts("");*/
}
int stk[N],top;
void work(){
scanf("%s",st);
n=strlen(st);
for (int i=0;i<n;++i) nxt[i]=i+1;
cnt[0]=0;
for (int i=0;i<n;++i) cnt[i+1]=cnt[i]+!isalpha(st[i]);
top=0;
memset(match,-1,sizeof(match));
for (int i=0;i<n;++i)
if (st[i]=='[') stk[top++]=i;
else if (st[i]==']') match[i]=stk[--top];
if (top) for (;;);
//for (int i=0;i<n;++i) printf("%d ",match[i]);puts("");
int l=0;
solve(l,n-1);
//puts("");return;
for (int i=l;i<n;i=nxt[i]) putchar(st[i]);
puts("");
}
int main(){
freopen ("subscript.in","r",stdin);
freopen ("subscript.out","w",stdout);
int T;scanf("%d",&T);
while (T--) work();
return 0;
}