A.Save the Nature：
-
题意：
你是一名售票员，有N张票供你选择，需要你计算最少使用多少张票可以使抽成达到K。
称售票的次序为“名次”。名次仅为a的倍数，可以抽成x%；名次仅为b的倍数，可以抽成y%；名次既为a的倍数又为b的倍数，可以抽成(x + y)%。
-
做法：
二分，二分法枚举使用的票数。
//576ms 3700KB
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int T;
int N;
int ans;
int x , a_th;
int y , b_th;
ll K;
priority_queue<ll , vector<ll> , less<ll> > price;
ll gcd(ll a , ll b){
//Greatest Common Divisor
return !b ? a : gcd(b , a%b);
}
ll lcm(ll a , ll b){
//Least Common Multiple
return a * b / gcd(a , b);
}
void input(){
while(price.size())
price.pop();//attention!!!!!!
scanf("%d" , &N);
for(int i=1;i<=N;i++){
ll temp;
scanf("%lld" , &temp);
price.push(temp);
}
scanf("%d%d" , &x , &a_th);
scanf("%d%d" , &y , &b_th);
scanf("%lld" , &K);
if(x < y){
swap(x , y);
swap(a_th , b_th);
}
return;
}
ll lcm_of_ath_and_bth ;
priority_queue<ll , vector<ll> , less<ll> >Q;
bool check(int num){
Q = price;//attention!
ll tot = 0;
int cnt;
cnt = num / lcm_of_ath_and_bth;
while(cnt--){
tot += Q.top() / 100 * (x + y);
Q.pop();
}
cnt = num / a_th - num / lcm_of_ath_and_bth;
while(cnt--){
tot += Q.top() / 100 * x;
Q.pop();
}
cnt = num / b_th - num / lcm_of_ath_and_bth;
while(cnt--){
tot += Q.top() / 100 * y;
Q.pop();
}
return tot >= K;
}
void solve(){
lcm_of_ath_and_bth = lcm(ll(a_th) , ll(b_th));
int l = 1 , r = N;
while(l != r){
int mid = (l + r)>>1;
if(check(mid))
r = mid;
else
l = mid+1;
}
//最后再check一次
ans = check(l) ? l : -1;
return;
}
void output(){
printf("%d\n" , ans);
return;
}
int main(){
scanf("%d" , &T);
while(T--){
input();
solve();
output();
}
return 0;
} B.Sequence Sorting：
-
题意：
给出一个序列，定义每一次操作可以任选一个数将所有该数移到序列最左边或最右边。计算最少花多少次操作可以将序列变成非严格递增序列。
- 做法：记录每种数左端点（第一次出现位置）和右端点（最后一次出现位置），找到无重叠的最多个区间，要求这些数字必须是连续、递增的。
//156ms 2400KB
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 300005;
int T;
int N;
int left_pos[maxn] , right_pos[maxn];
int MAX;
void input(){
MAX = 0;
scanf("%d" , &N);
for(int i=1;i<=N;i++)//这要是还用memset就是sb
left_pos[i] = right_pos[i] = 0;
for(int i=1;i<=N;i++){
int temp;
scanf("%d" , &temp);
/*
if(left_pos[temp])
right_pos[temp] = i;
else
left_pos[temp] = i;
*/
if(!left_pos[temp])
left_pos[temp] = i;
right_pos[temp] = i;
if(MAX < temp)
MAX = temp;
}
return;
}
int solve(){
int num_of_unique = 0;
int ans = 0;
int cnt = 0;
int rightend = 0;
for(int i=1;i<=MAX;i++){
if(!left_pos[i])
continue;
num_of_unique++;
if(left_pos[i] > rightend)
cnt++;
else{
ans = max(ans , cnt);
cnt = 1;//cnt置1，不能置0
}
rightend = right_pos[i];
}
ans = max(ans , cnt);//这里必须再判断一次
return num_of_unique - ans;
}
int main(){
scanf("%d" , &T);
while(T--){
input();
printf("%d\n" , solve());
}
return 0;
} C.Paint the Tree：
感谢Scar_Halo的BLOG。
-
题意：
N个点构成一颗带权树，每个顶点可以被染上K种颜色，如果两个直连顶点具有相同的颜色，则这个边权可以获取，求可以获取的最大边权和。另外：有无限种颜色，并且每种颜色最多使用两次（仅为保证不可以“吃霸王餐”）。
-
做法：
邻接表存图，自底向上树形dp，每个非叶节点可以获取答案当且仅当获取它的全部子节点答案之后。树形dp一般是将dp[v][0]、dp[v][1]作为节点v取/不取的两种状态。但是本题的是在选边权，所以令dp[v][0]、dp[v][1]分别代表“不选/选”节点v的父边。
//592ms 58000KB
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
int T;
int N,K;
struct EDGE{
int v;
int w;
EDGE(int v,int w) : v(v) , w(w) {} ;
};
vector<EDGE> V[maxn];
ll dp[maxn][2];//0代表不连接父节点（父边不用）；1表示连接父节点（父边使用）
void solve(int id , int par){
priority_queue<ll , vector<ll> , less<ll> > Q;
for(vector<EDGE>::iterator p=V[id].begin() ; p<V[id].end() ; p++){
if(p->v == par)
continue;
solve(p->v , id);
dp[id][0] += dp[p->v][0];//这两行
dp[id][1] += dp[p->v][0];//不要忘
Q.push(dp[p->v][1] + p->w - dp[p->v][0]);
}
int cnt = 0;
while(Q.size()){
ll cur = Q.top();
Q.pop();
if(cur <= 0)//不要忘记这个
break;
dp[id][0] += cur;
dp[id][1] += cur;
cnt++;
if(cnt == K){
dp[id][1] -= cur;
break;
}
}
while(Q.size())
Q.pop();
return ;
}
int main(){
cin>>T;
while(T--){
cin>>N>>K;
for(int i=0;i<=N;i++){
dp[i][0] = dp[i][1] = 0;
V[i].clear();
}
for(int i=1;i<N;i++){
int u,v,w;
scanf("%d%d%d" , &u , &v , &w);
V[u].push_back(EDGE(v , w));
V[v].push_back(EDGE(u , w));
}
solve(1 , 0);
printf("%lld\n" , dp[1][0]);
}
return 0;
} D.Stack Exterminable Arrays：
感谢_泛白的BLOG。
感谢黑猫black的BLOG。
-
题意：
类似于括号匹配，称可匹配的串为可毁灭串，问子串中可毁灭串有多少个。
-
做法：该做法为dp，另外有分治做法（还没写）
arr[i] = arr[tail[i] + 1]
tail[i] = NEXT[i + 1][arr[i]]：从下标i开始，到下标NEXT[i][arr[i]] - 1为可毁灭串，且下标NEXT[i][arr[i]]处元素为arr[i]
欲求tail[i]，NEXT[i + 1][arr[i]]
//202ms 21400KB
//如果出现“绝望WA”，一定是batch初始化没做到位。
//map不能轻易使用整体赋值，可能会MLE。
//可以分治做，还没想明白
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 5;
int T;
int N;
int arr[maxn];//array不能做变量名
int tail[maxn];
ll dp[maxn];
ll ans;
map<int , int>NEXT[maxn];
void input(){
ans = 0;
scanf("%d" , &N);
for(int i=1;i<=N;i++){
dp[i] = tail[i] = 0;
NEXT[i].clear();
scanf("%d" , arr + i);
}
dp[N+1] = 0;//attention!!!!!!!!!!!!!!!!!!!!
NEXT[N+1].clear();//attention!!!!!(line 32)
return;
}
void solve(){
for(int i=N;i;i--){
if(NEXT[i + 1].count(arr[i])){
int pos = NEXT[i+1][arr[i]];
tail[i] = pos;
NEXT[i] = NEXT[pos + 1];//MLE
// swap(NEXT[i] , NEXT[pos+1]);//(pos+1)
dp[i] = dp[tail[i] + 1] + 1;
ans += dp[i];
}
NEXT[i][arr[i]] = i;//important
}
return;
}
void output(){
printf("%lld\n", ans);
return;
}
int main(){
scanf("%d" , &T);
while(T--){
input();
solve();
output();
}
return 0;
} ![10.18 航空公司 2435题目题解代码[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)