B. Appleman and Card Game
解析：
兩個水題，貪心問題，直接統計每個字母出現的次數，然後sort一下，每次取最大的。
但是，這裡要注意一下數據范圍，結果用long long表示，在計算過程中需要強制類型轉換，尤其k在計算中一定要是long long型
代碼：
//#define LOCAL
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define Lowbit(x) ((x)&(-(x)))
#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
const int MAXN=1005;
ll a[30];
char str[100010];
int main(){
#ifdef LOCAL
freopen(1.in, r,stdin);
//freopen(1.out, w, stdout);
#endif
int n;
ll k;
scanf(%d%I64d, &n, &k);
scanf(%s, str);
int len = strlen(str);
memset(a, 0, sizeof(a));
for(int i=0; i=0&&k>0; --i){
if(k>=a[i]){
sum += a[i]*a[i];
k -= a[i];
}
else{
sum += k*k;
k-=k;
}
}
printf(%I64d
, sum);
return 0;
}
C. Appleman and Toastman
解析：
三個水題，貪心嘛，每次將最小的那個數字單獨拆開，可以用sort也可以用priority_queue。
代碼：
//#define LOCAL
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define Lowbit(x) ((x)&(-(x)))
#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
const int MAXN=1005;
int main(){
#ifdef LOCAL
freopen(1.in, r,stdin);
//freopen(1.out, w, stdout);
#endif
int i,n;
ll sum = 0;
ll score = 0,tmp;
priority_queue< ll, vector, greater >pq;
scanf(%d, &n);
for(i=0; i1){
score += sum;
tmp = pq.top();
pq.pop();
sum -= tmp;
}
printf(%I64d, score);
return 0;
}
D. Appleman and Tree
解析：
這是一道DP問題，用到樹形DP；
題意：給了一棵樹以及每個節點的顏色，1代表黑，0代表白，要求的是，如果將這棵樹拆成k棵樹，使得每棵樹恰好有一個黑色節點
dp[v][0 ]表示以v為根沒有黑節點子樹的數目
dp[v][1] 表示以v為根有黑節點子樹的數目
說實話，我遇到DP還是比較犯怵的，所以在比賽的時候發現這是道DP問題，也就懶得在動用喝醉的大腦了，直接GG了。
代碼：
//#define LOCAL
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define Lowbit(x) ((x)&(-(x)))
#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define mod 1000000007
const int MAXN=100010;
ll dp[MAXN][2];
vector x[MAXN];
int c[MAXN];
void dfs(int v,int p){
dp[v][0] = 1;
dp[v][1] = 0;
for(int i=0; i
E. Appleman and a Sheet of Paper
解析：
說實話這個題目根本不需要怎麼多讀，直接看樣例的分析就知道題意了。就是簡單的疊紙條，然後查詢區間的紙條總厚度
這裡可以用BIT（樹狀數組），也可以用線段樹。
這裡的代碼，我用的是樹狀數組。
本題解答的一個巧妙的地方就是，如果左邊疊的長，那麼我們可以反過來把右邊的疊過來，但是紙條的左右方向要轉向，所以這裡用了一個flag標記左右的方向。其他部分就和普通的樹狀數組是一樣的做法。
代碼：
//#define LOCAL
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define Lowbit(x) ((x)&(-(x)))
//#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define mod 1000000007
const int MAXN=100010;
int c[MAXN], s[MAXN],n;
void ADD(int p, int val){
s[p] += val;
while(p<=n){
c[p] += val;
p += Lowbit(p);
}
}
int getsum(int p){
int sum = 0;
while(p>0){
sum += c[p];
p -= Lowbit(p);
}
return sum;
}
int main(){
#ifdef LOCAL
freopen(1.in, r,stdin);
//freopen(1.out, w, stdout);
#endif
int i, p;
scanf(%d%d, &n, &p);
memset(c, 0, sizeof(c));
memset(s, 0, sizeof(s));
for(i=1; i<=n; ++i)
ADD(i, 1);
int l=1, r=n;
int x,y,z;
int flag = 0;
for(int k=0; k(r-l+1));
int mid;
if(flag) mid = r-y;
else mid = l+y-1;
int ll = mid-l+1; int rr = r-mid;
if(ll<=rr){
for(i=l; i<=mid; ++i)
ADD(2*mid+1-i, s[i]);
l = mid+1;
}
else{
for(i=mid+1; i<=r; ++i)
ADD(2*mid+1-i, s[i]);
r = mid;
}
flag ^= fg; //標記，如果左邊長，那麼就向左疊，並且從右向左讀；
//如果左邊短，那麼就向右疊，並且從左向右讀。
}
else{
scanf(%d%d, &y,&z);
if(flag) printf(%d
, getsum(r-y)-getsum(r-z));
else printf(%d
, getsum(l+z-1)-getsum(l+y-1));
}
}
return 0;
}
