本文主要是介绍9.12日考试总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天花4个小时做了一套6道题，效果不是很理想。
前两题不说了，很简单。
第三题就是大坑了，给出一个字符串，从金字塔顶端向下一层一层地蛇形填充，字符串用完则重头再来，询问某一层一个字母出现了多少次。范围：字符串长度10^6，层数10^18（明明层数几万就可以把所有的非正确算法卡死完了，非要弄那么大）。
这个还是比较好想，首先确定蛇形是个幌子，不影响结果。对于一个询问，求出前面有多少个字母，然后就可以锁定这一行开始的字母是什么了，然后做一个除法，最后特判一下剩余的就行了。但是要注意，等比数列前N项和模字符串长度时，n*(n+1)/2在乘的时候会爆，需要将那个除以二放在n和n+1中是偶数的那里去除，然后两个边分别模了再乘，不然会溢出的。
第四题杀人游戏，N个人，每个人指认一个人，杀手不会指认同党，平民随意指认，计算最多有多少人是杀手，N在五十万以内。首先画成图，一个点若是杀手，则直接连边的点不能是杀手（差不多是个最大独立集）。
我考场上做的时候搞忘这种图的性质了，所以没弄出正解。每个点只有一个出边，说明每个连通块内最多只有一个环，然后枚举割掉环上任意相邻两边的两种情况，较大值就是这个连通块的解了。P.S. yly大蛤考完后把ZJOI2008骑士那道题的代码改了一下，把所有点权全部设为1，直接过了这道题orz。。
第五题：M栋宿舍楼，一共N天，每天有个人到入住到一个指定的宿舍楼，同时会举办一个派对，嘈杂度为该宿舍楼里的人数（包括他自己）。现一共有K次机会可以把任意一栋教学楼里的人轰走，问怎样安排使得嘈杂度之和最小。M<=100，N<=10^6，K<=500.
这种题一般二分或DP。二分不太好检验，就从DP入手吧。先明确顺序不重要，统计出每栋楼一共先后来了多少人就行了。
首先 f[i, j] 表示i个人，分成j部分产生的最小代价。然后再利用求得的f值做一次0~K背包即可。这个算法由两个DP构成，后半部分不会超时，前半部分就会TLE&MLE了。可以想到贪心的思路取而代之，尽量平均分，但是我考场上平均分这里细节没处理好，我想的是前面几部分每部分一样多，最后的余数自成一组，这个是不科学的。事实证明最好是可以分成若干组，使得每组之间的差值不超过1，而且这一定是可以做到的，至于有多少个是下取整，多少个是上取整，用古人解鸡兔同笼那种抬起一只脚的方法就行了。
谢天谢地后面的0~k背包数据范围设置不大。不然再加上队列优化就彻底麻烦啦。
#include<iostream>
#include<cstdio>
#include<cstring>
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
#define LL long long
const int MAXN = 1000010;
const LL INF = 1LL<<60;
int N, M, K;
LL f[505];
int cnt[505];LL arrange(int n0, int t0) { //n0个分为t0组if (n0 % t0 == 0) {return ((LL)t0) * (1 + n0/t0) * (n0/t0) / 2LL;}LL each = n0/t0, more = n0%t0;return more*(2+each)*(1+each)/2 + (t0-more)*(1+each)*each/2;
}void BackPack() {for (int i = 1; i<=M; ++i)for (int j = K; j>=0; --j) {LL mn = INF;for (int k = 0; k<=cnt[i] && k<=j; ++k)mn = Min(mn, f[j-k] + arrange(cnt[i], k+1));f[j] = mn;}
}int main()
{scanf("%d%d%d", &N, &M, &K);int t;for (int i = 1; i<=N; ++i){scanf("%d", &t);cnt[t] ++;}BackPack();cout << f[K] << '\n';return 0;
}
最后一题，给定一棵树，树上有若干关键点，求从树上每个点开始走完所有关键点的最短路径。N在五十万。
这题我考场上基本一眼看出正解，但是没时间了，早知道这题分值这么大我就先做这题了。。
正解给的是什么连接关键点的路径减去最长链上的路径什么的，比较巧妙。
我想的是从这题本身出发，强行上树DP。具体实现有点像K辆铲雪车问题和最长链问题的合集。
f[i,1]表示从i出发，走完i为根的子树中的所有关键点，最后回到i的最短路径。
f[i,0]表示从i出发，走完i为根的子树中的所有关键点，最后停在子树中的最短路径，同时come[i]记录这个值从哪个子树来的。
f[i,2]意义和f[i,0]类似，只不过是次短路径，切与f[i,0]来自不同的子节点。
g[i,1]和g[i,0]，分别表示从i开始，走完其父亲边通向的所有关键点，最后是否返回i节点的最短路径。
转移的时候真的比较麻烦，方程也不是特别好描述。。特别是g数组的转移，一定要多考虑细节。
最后答案，对于每个i，取(f[i,0]+g[i,1])和(f[i,1]+g[i,0])之间的较小值即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
const int MAXN = 500010;void get(int &r) {char c; r = 0;do c=getchar(); while (c<'0'||c>'9');do r=r*10+c-'0',c=getchar(); while (c>='0'&&c<='9');
}struct Node {int to, d; Node*next;
}Edge[MAXN*2], *ecnt=Edge, *adj[MAXN];
void adde(int a, int b, int c) {(++ecnt)->to = b;ecnt->d = c;ecnt->next = adj[a];adj[a] = ecnt;
}
int N, K;LL f[MAXN][3], g[MAXN][2];
int come[MAXN];
bool must[MAXN];
bool need[MAXN], need1[MAXN];
int needn[MAXN];
int fa[MAXN], fal[MAXN];void predfs(int u)
{if (must[u])need1[u] = need[u] = 1;for (Node*p = adj[u]; p; p=p->next){if (p->to == fa[u]) continue;fa[p->to] = u;fal[p->to] = p->d;if (need1[fa[u]]) need1[u] = 1;predfs(p->to);if (need[p->to]) need[u] = 1;needn[u] += need[p->to];}
}void dfs1(int u)
{int mx1 = 0, mx2 = 0, t;for (Node*p = adj[u]; p; p=p->next){if (p->to == fa[u] || !need[p->to]) continue;dfs1(p->to);t = (p->d) - f[p->to][0] + f[p->to][1];if (t > mx1) mx2 = mx1, mx1 = t, come[u] = p->to;else if (t > mx2) mx2 = t;f[u][1] += f[p->to][1] + 2*p->d;}f[u][0] = f[u][1] - mx1;f[u][2] = f[u][1] - mx2;
}void dfs2(int u)
{need1[u] = need1[fa[u]] || (needn[fa[u]]-need[u])>0;if (need1[u]){g[u][1] = g[fa[u]][1] + f[fa[u]][1] - f[u][1];g[u][0] = g[fa[u]][0] + f[fa[u]][1] - f[u][1] - fal[u]*need[u];if (u==come[fa[u]])g[u][0] = Min(g[u][0], g[fa[u]][1] + f[fa[u]][2] - f[u][1] - fal[u]);elseg[u][0] = Min(g[u][0], g[fa[u]][1] + f[fa[u]][0] - (f[u][1]+fal[u])*need[u]);if (!need[u])g[u][1] += 2 * fal[u], g[u][0] += fal[u];}for (Node*p = adj[u]; p; p=p->next)if (p->to != fa[u])dfs2(p->to);
}int main()
{get(N), get(K);int a, b, c;for (int i = 1; i<N; ++i) {get(a), get(b), get(c);adde(a, b, c); adde(b, a, c);}for (int i = 1; i<=K; ++i)get(a), must[a] = 1;predfs(1);dfs1(1);dfs2(1);for (int i = 1; i<=N; ++i)cout << Min(g[i][0]+f[i][1], g[i][1]+f[i][0]) << '\n';return 0;
}
这篇关于9.12日考试总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
