被这套题搞的突然失去梦想。。
B题题意:给你三个值p，q，r，在一段序列上选取3个值ai,aj,ak(1<=i<=j<=k<=n)使得ai*p+aj *q+ak *r最大。
思路:做的时候想歪了，但弄懂了一个之前一直疑惑的问题。。之后认真思考这道题时发现不是很难想,首先博主做的时候认定为一道dp题。
dp转移方程为:dp[j][i] = max(dp[j - 1][i], dp[j][i - 1] + num[i] * a[j])
博主将p,q,r按顺序存进了num里面，那么dp[ j ][ i ]的意思为前j个数已经取了i个数的最大值。边界dp[j][1]=max(dp[j-1][i],num[1]*a[j]);
代码如下
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
ll a[100005];
ll num[10];
ll dp[100005][5];
const ll inf = 0x3f3f3f3f3f3f3f3f;
int main()
{long long n;cin >> n >> num[1] >> num[2] >> num[3];for (int i = 0;i <= n;i++)for (int j = 0;j <= 3;j++)dp[i][j] = -inf;for (int i = 1;i <= n;i++)scanf("%lld", &a[i]);dp[1][1] = num[1] * a[1];for (int i = 1;i <= 3;i++)for (int j = 1;j <= n;j++){if (i == 1)dp[j][i] = max(dp[j - 1][i], num[1] * a[j]);elsedp[j][i] = max(dp[j - 1][i], dp[j][i - 1] + num[i] * a[j]);}cout << dp[n][3] << endl;}可能有些大佬会用前缀后缀做这道题，但博主感觉那个方法不太实用，如果下次求4个数，就不好做了。。但这个dp却可以。
C题题意:有一棵树，结点的值有m种，有一个值比较特殊，记为k，如果有一个结点选了它，那么他周围的点的值不能超过k。特殊的值有x个，问有多少种方法赋值。
思路:一眼望去就是一道树形dp题，然而加上特殊的值有x个这个限制条件就不好做了，虽然转移方程写得出来。
转移方程如下:
dp[cur][0][cnt]代表当前结点cur的值小于k，它的子树有cnt个特殊的点的答案。
dp[cur][1][cnt]代表当前结点cur的值等于k，它的子树(包括自己)有cnt个特殊的点的答案。
dp[cur][2][cnt]代表当前结点cur的值大于k，它的子树有cnt个特殊的点的答案。
聪明的读者一定能够将状态转移推出来，但如何求在子树上分配特殊点的数量，这是个问题。这其中又有一个递推关系在里面。如果有x个特殊点，有size个儿子。那么求分配特殊点的数量这个问题又可以变成若干个子问题:最后一个儿子有1个,前size-1个儿子有x-1个.如果最后一个儿子有2个，那么前size-1个孩子就要x-2个。。。
所以到一个儿子的树时，只要知道前一个儿子的各种分配方式的数量，那么也就知道现在的分配数量是多少了。
细节请看代码:
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 1e5 + 5;
vector<int>V[maxn];
typedef long long ll;
int k, x;
int n, m;
ll dp[maxn][3][15];
ll a[3][15], b[3][15];
const ll mod = 1000000007;
void dfs(int u, int pre)
{int Size = V[u].size();if (Size == 1 && V[u][0] == pre){dp[u][0][0] = k - 1;dp[u][1][1] = 1;dp[u][2][0] = m - k;return;}for (int i = 0;i < Size;i++){int to = V[u][i];if (to == pre)continue;dfs(to, u);}memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));for (int i = 0;i < 3;i++)a[i][0] = 1;//a[1][1] = 1;for (int to : V[u]){if (to == pre)continue;for(int c=0;c<3;c++)for(int i=0;i<=x;i++)for (int j = 0;j <= x;j++){if (i + j > x)break;ll temp = 0;if (c == 0){temp = dp[to][0][j] + dp[to][1][j];temp %= mod;temp += dp[to][2][j];temp %= mod;b[c][i + j] += temp*a[c][i] % mod;b[c][i + j] %= mod;}else if (c == 1){temp = dp[to][0][j] % mod;b[c][i + j] += temp*a[c][i] % mod;b[c][i + j] %= mod;}else{temp = dp[to][0][j] + dp[to][2][j];temp %= mod;b[c][i + j] += temp*a[c][i] % mod;b[c][i + j] %= mod;}}for (int i = 0;i < 3;i++)for (int j = 0;j <= x;j++)a[i][j] = b[i][j], b[i][j] = 0;} for (int l = 0;l <= x;l++){dp[u][0][l] = (1ll * a[0][l] * (k - 1)) % mod;if (l >= 1)dp[u][1][l] = a[1][l - 1];dp[u][2][l] = (1ll * a[2][l] * (m - k)) % mod;}
}int main()
{cin >> n >> m;int u, v;for (int i = 1;i < n;i++){scanf("%d%d", &u, &v);V[u].push_back(v);V[v].push_back(u);}cin >> k >> x;dfs(1, 0);ll ans = 0;for (int i = 0;i < 3;i++)for (int j = 0;j <= x;j++){ans += dp[1][i][j];ans %= mod;}cout << ans << endl;
}D题题意:(好复杂的题意啊。。)又是一棵树，，父与子的关系有2种，一种是儿子是父亲的special case，另一种儿子是父亲的part。并且，如果v是u的special case或者part，u是t的special case或者part，那么v也是t的special case或者part。如果v是u的part，而t是u的special case，那么v也是t的part。(虽然有点绕，但题目大概意思应该讲通了。。)
现在有若干个询问1 u v代表v是不是u的special case。2 u v 代表v是不是u的part
思路:读者请捋顺其中的关系。。如果是询问1，那么其实就是再问你u是不是v的祖先，并且u到v的边都是第一种边。询问2其实问你u和v共同祖先k到v的边是不是都是第二种，k到u的边是不是都是第一种。
所以这道题只要看清题意，注意细节，会求lca就做出来了。
代码如下:
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 1e5 + 5;
vector<int>V1[maxn], V2[maxn];
int dep[maxn];
int One[maxn], Two[maxn];
int st[maxn][20];
int f[maxn];
int n;
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
void dfs(int u, int d,int one,int two)
{int Size = V1[u].size();dep[u] = d;One[u] = one, Two[u] = two;int x = find(u);for (int i = 0;i < Size;i++){int y = find(V1[u][i]);if (x != y)f[y] = x;st[V1[u][i]][0] = u;if (V2[u][i] == 0)dfs(V1[u][i], d + 1, one + 1, two);elsedfs(V1[u][i], d + 1, one, two + 1);}
}void ST()
{for(int i=1;i<20;i++)for (int j = 1;j <= n;j++){if ((1 << i) > dep[j])continue;st[j][i] = st[st[j][i - 1]][i - 1];}
}
int query(int u, int v)
{if (dep[u] < dep[v])swap(u, v);int d = dep[u] - dep[v];for (int i = 0;i < 20;i++)if (d&(1 << i))u = st[u][i];if (u == v)return u;for (int i = 19;i >= 0;i--){if (st[u][i] != st[v][i]){u = st[u][i];v = st[v][i];}}u = st[u][0];v = st[u][0];return u;
}
int main()
{cin >> n;int parent, type;for (int i = 1;i <= n;i++){f[i] = i;scanf("%d%d", &parent, &type);if (parent == -1 && type == -1)continue;V1[parent].push_back(i);V2[parent].push_back(type);}for (int i = 1;i <= n;i++)if (dep[i] == 0){dfs(i, 1,0, 0);}ST();int q;cin >> q;int u, v;for (int i = 1;i <= q;i++){scanf("%d%d%d", &type, &u, &v);int x = find(u);int y = find(v);if (x != y)puts("NO");else{if (type == 1){if (query(u, v) != u || u == v||Two[v]-Two[u]!=0)puts("NO");elseputs("YES");}else{int thefa = query(u, v);if (Two[u] - Two[thefa] != 0 || One[v] - One[thefa] != 0||thefa==v)puts("NO");elseputs("YES");}}}return 0;
}请一定要自己写一遍，注意if里面的语句。这些细节可能导致你会wa掉。。
E题题意:将一个数转换为b进制后，如果0到b-1都出现了偶数次(包括0次，不包括前导0)，这个数就是magic数。问l到r在b进制下中有几个magic数。
思路:典型的数位dp，只要想办法来判断这个状态合不合法这道题就可以a了。
我们可以用dp[b][pos][now]来代表在b进制下最高位到pos位下的状态now的magic数的个数。
那么now状态是什么呢？如何用now来判断该数的合法性呢？
如果前面有一位数为c，那么就用now^(1<< c),那么这样就可以利用now是否为0来判断是不是合法了。
代码如下:
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
ll dp[12][100][5000];
ll l, r;
int b;
int a[105];
ll dfs(int pos, ll now, bool lead, bool limit)
{if (pos == -1){if (now == 0)return 1;else return 0;}if (!limit && !lead&&dp[b][pos][now] != -1)return dp[b][pos][now];int up = limit ? a[pos] : b - 1;ll ans = 0;for (int i = 0;i <= up;i++){ans += dfs(pos - 1, lead&&i==0?now:now ^ (1LL << i), lead&&i == 0, limit&&i == a[pos]);}if (!limit && !lead)dp[b][pos][now] = ans;return ans;}ll solve(ll x)
{int pos = 0;while (x){a[pos++] = x%b;x /= b;}return dfs(pos - 1, 0, true, true);
}int main()
{int T;scanf("%d", &T);memset(dp, -1, sizeof(dp));while (T--){scanf("%d%lld%lld", &b, &l, &r);/*for (int i = 0;i <= r;i++)cout << solve(i) << endl;solve(r);solve(l - 1);*/printf("%lld\n", solve(r) - solve(l - 1));}return 0;
}F题题意:在笛卡尔坐标中，有q次询问，第一种询问1 l r k,代表在x>=l&&x
#include<iostream>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
typedef long long ll;
int a[100005], b[100005], c[100005];
int main()
{int q;cin >> q;int type,l,r;int k;while (q--){scanf("%d%d%d", &type, &l, &r);if (type == 1){scanf("%d", &k);if (k > 0){for (int i = l;i < r;i++){if (!a[i] || a[i] && a[i] > k)a[i] = k;if (b[i])c[i] = a[i] + b[i];}}else{k = -k;for (int i = l;i < r;i++){if (!b[i] || b[i] && b[i] > k)b[i] = k;if (a[i])c[i] = a[i] + b[i];}}}else{ll ans = 0;for (int i = l;i < r;i++)ans =ans+ c[i];printf("%lld\n", ans);}}return 0;
}结果竟然出人意料的A了。。
所以呢，放这道题的意思就是希望读者不要看到数据量那么大，就不敢做了。尝试一下暴力说不定就过了呢。。
ok，正解肯定不是这个，博主看了看题解，正解是分块。但博主还没弄懂，有兴趣的读者可以去看看Tutorial，稍后可能会更新正解。