整體概述
- 難度：1000 →\rightarrow→ 1400 →\rightarrow→ 1600
P3918 [國家集訓隊] 特技飛行
-
標簽：貪心
-
前置知識：無
-
難度：橙 1000
題目描述：
輸入格式：
輸出格式：
樣例輸入：
5 2
2 2
樣例輸出：
12
解題思路：
-
發現一次操作沒有貢獻，至少要兩次操作。同時發現無論操作多少次，總貢獻等同于只操作第一次和最后一次帶來的貢獻。
-
所以我們讓價值最大的貢獻操作時間最長即可，即將 ccc 從大到小排序，然后依次填充在頭尾，模擬一遍計算總貢獻即可。
完整代碼
#include<bits/stdc++.h>
#define Size(x) ((int)(x).size())
#define int long long
using namespace std;
const int N = 1e3+5;
int n,k,a[N],c[N];
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin >> n >> k;for(int i=1;i<=k;i++) cin >> c[i];sort(c+1,c+k+1,[&](int x,int y){return x>y;});int res = 0;for(int i=1,j=1;i<=k && j<=n/2;i++,j++)res += ((n-j+1) - j)*c[i];cout << res;return 0;
}
P11465 水上舞者索尼婭
-
標簽：數學
-
前置知識：逆元
-
難度：黃 1400
題目描述：
輸入格式：
輸出格式：
樣例輸入：
3
2 2
3 1
12 34
樣例輸出：
12
14
178629506
解題思路：
-
我們發現，對于一張還剩 iii 次的 一串香蕉一串香蕉一串香蕉，在場上由 kkk 個索尼婭的時候，本質是使用了 k+1k+1k+1 張還剩 iii 次的 一串香蕉一串香蕉一串香蕉，隨后產生 k+1k+1k+1 張還剩 i?1i-1i?1 次的 一串香蕉一串香蕉一串香蕉。
-
那么總使用次數即 (k+1)+(k+1)2+...+(k+1)n(k+1) + (k+1)^2 + ... + (k+1)^n(k+1)+(k+1)2+...+(k+1)n，用等比數列求和即 (k+1)?(1?(k+1)n)1?(k+1)=(k+1)?((k+1)n?1)k\frac {(k+1)*(1-(k+1)^n)} {1-(k+1)} = \frac {(k+1)*((k+1)^n-1)} {k}1?(k+1)(k+1)?(1?(k+1)n)?=k(k+1)?((k+1)n?1)?。
-
注意在模意義下除 kkk 是乘以 kkk 的逆元即可，
完整代碼
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9+7;
int n,k;
inline int qpow(int a,int b){int res = 1;for(;b;b>>=1,a=a*a%mod)if(b&1) res=res*a%mod;return res;
}
inline void solve(){cin >> n >> k;cout << ((k+1)*(qpow(k+1,n)-1))%mod*(qpow(k,mod-2))%mod << '\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T; cin >> T;while(T--) solve();return 0;
}
P6457 [COCI 2006/2007 #5] IVANA
-
標簽：區間DP
-
前置知識：拆環成鏈
-
難度：綠 1800
題目描述：
輸入格式：
輸出格式：
樣例輸入：
3
3 1 5
4
1 2 3 4
8
4 10 5 2 9 8 1 7
樣例輸出：
3
2
5
解題思路：
-
首先發現是環上的操作，我們先翻個倍拆環成鏈。
-
由于每次操作都是在已選擇的區間的邊緣上進行操作，我們考慮區間 DPDPDP，題目所求的是奇數個數更多的玩家獲勝，那么我們定義 dpi,jdp_{i,j}dpi,j? 表示當前先手取完區間 [i,j][i,j][i,j] 此時先手最多比后手多幾個奇數。
-
那么 dpi,j=max(dpi,i?dpi+1,j,dpj,j?dpi,j?1)dp_{i,j} = max(dp_{i,i}-dp_{i+1,j},dp_{j,j}-dp_{i,j-1})dpi,j?=max(dpi,i??dpi+1,j?,dpj,j??dpi,j?1?)，全部更新一遍即可。
-
最后統計的時候需要注意，我們需要枚舉先手取的起始點 iii，若 dpi,i?dpi+1,i+n?1>0dp_{i,i} - dp_{i+1,i+n-1} \gt 0dpi,i??dpi+1,i+n?1?>0 則滿足題意則統計答案。
完整代碼
#include<bits/stdc++.h>
#define Size(x) ((int)(x).size())
#define int long long
using namespace std;
const int N = 205;
int n,m,a[N],dp[N][N];
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin >> n; m = n*2;for(int i=1;i<=n;i++) cin >> a[i], a[i+n] = a[i];for(int l=1;l<=m;l++) if(a[l]&1) dp[l][l] = 1;for(int len=2;len<=n;len++){for(int l=1;l<=m-len+1;l++){int r = l+len-1;dp[l][r] = max(dp[l][l]-dp[l+1][r],dp[r][r]-dp[l][r-1]);}}int res = 0;for(int i=1;i<=n;i++) if(dp[i][i] - dp[i+1][i+n-1] > 0) res += 1;cout << res;return 0;
}
)
