?
?
A. Appleman and Easy Task
解析：
一个水题，判断每个细胞周围是否都是有偶数个相邻细胞。
?
代码：
?
#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]; int n; char str[105][105]; bool check(int i, int j){ int tmp = 0; if(i>0&&str[i-1][j]=='o') ++tmp; if(i
0&&str[i][j-1]=='o') ++tmp; if(j
?
?
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; i
1){ 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