#include <iostream>
using namespace std;
int a[100005];
int main() {
int n, b, d;
cin >> n >> b >> d;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = 0, tmp = 0;
for (int i = 1; i <= n; i++) {
if (a[i] > b) {
continue;
}
tmp += a[i];
if (tmp > d) {
tmp = 0;
ans++;
}
}
cout << ans << endl;
return 0;
}
两种情况，先向左走再折回向右或先向右走再折回向左。
#include <iostream>
#include <algorithm>
using namespace std;
int x[100005], l[100005], r[100005];
int main() {
int n, a;
cin >> n >> a;
for (int i = 0; i < n; i++) {
cin >> x[i];
}
sort(x, x + n);
int ln=0, rn=0;
for (int i = 0; i < n; i++) {
if (x[i] <= a) {
ln++;
}
}
rn = n - ln;
l[0] = 0;
for (int i = 1; i <= ln; i++) {
l[i] = a - x[ln - i];
}
r[0] = 0;
for (int i = 1; i <= rn; i++) {
r[i] = x[ln + i - 1] - a;
}
int ans = 0x7fffffff;
for (int i = 0; i <= ln; i++) {
if (rn < n - i - 1) {
continue;
}
if ((l[i] << 1) + r[n - i - 1] < ans) {
ans = (l[i] << 1) + r[n - i - 1];
}
}
for (int i = 0; i <= rn; i++) {
if (ln < n - i - 1) {
continue;
}
if ((r[i] << 1) + l[n - i - 1] < ans) {
ans = (r[i] << 1) + l[n - i - 1];
}
}
cout << ans << endl;
return 0;
}
没看懂题意，估计挺水的。
#include<cstdio>
char s[100001];
int i,f;
int main()
{
for(gets(s);s[i];++i)
{
if(s[i]>97)f=1;
if(f)if(s[i]>97)--s[i];else break;
}
if(!f)s[i-1]=122;
puts(s);
}
首先根据a00和a11把0和1各自的数目算出来。然后假设在一串连续的0中间逐个插入1。每新插入一个1对10个数和01个数带来的影响与之前插入的1的位置无关，且10个数和01个数的增量之和为0的个数。所以a10与a01之和应为0的个数与1的个数的乘积。满足以上条件时存在满足条件的01串。
构造方法：设0的个数为n0，插入1的位置左边可以有0~n0个0，对应为01个数的增量。在左边不断插入并输出一个1直到剩余的01个数不足n0，此时选择好相应位置输出形如00001000的串，并在最末尾输出剩余个数的1。
注意：若a00或a11的值为0,0和1的个数既可以为0也可以为1，具体应根据a10和a01的值作出判断。这里错了很多次。
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int a00, a01, a10, a11;
int a[1000005];
int main() {
cin >> a00 >> a01 >> a10 >> a11;
int n0 = -1, n1 = -1;
for (int i = 0; i <= a00 + 100; i++) {
if (i * (i - 1) == 2 * a00) {
n0 = i;
break;
}
if (i * (i - 1) > 2 * a00) {
break;
}
}
for (int i = 0; i <= a11 + 100; i++) {
if (i * (i - 1) == 2 * a11) {
n1 = i;
break;
}
if (i * (i - 1) > 2 * a11) {
break;
}
}
if (n0 == 0 && (a01 || a10)) {
n0 = 1;
}
if (n1 == 0 && (a01 || a10)) {
n1 = 1;
}
if (n0 == -1 || n1 == -1 || n0 * n1 != (a01 + a10)) {
cout << "Impossible" << endl;
return 0;
}
if (n0 == 0 && n1 == 0) {
cout << 0;
return 0;
}
memset(a, 0, sizeof(a));
while (a10 > n0) {
cout << 1;
a10 -= n0;
n1--;
}
for (int i = 1; i <= n0 - a10; i++) {
cout << 0;
}
if (a10) {
cout << 1;
n1--;
}
for (int i = 1; i <= a10; i++) {
cout << 0;
}
for (int i = 1; i <= n1; i++) {
cout << 1;
}
return 0;
}
每个点做一次判断。如果该点可以作为重心或操作一次后可以为重心，则应满足以若该点为树根则其子树的大小均不超过n/2或只有一颗子树大小超过n/2，且该子树移除一个大小不超过n/2的子树后剩余部分的大小不超过n/2，移除的部分接在根节点上。
点的总数最大为40w。
重点：
- 枚举每个点时，应能快速知道每个子树的大小。
- 对于每个子树，应能快速知道其中不超过n/2的最大的子树的大小。
1.首先以编号为1的点作为树根，计算出所有的点的子树的大小。当计算点v1是否为重心时，对于边(v1，v2)，若以1为树根时v2是v1的儿子，则v2子树的大小为size(v2)，否则v2子树的大小为N-size(v2)。
2.用的时候临时求会超时，需要提前全算好。maxsub表示从一个顶点向其各个儿子方向找能找到的满足要求的子树大小，maxfa表示向其父亲方向能找到的满足要求的子树大小。maxsub比较好求。maxfa有两种，要么包含该点父亲方向的全部，要么取该节点所有兄弟节点的maxsub和父亲节点的maxfa中最大的。
直接取最大值还会超时，比如如果树的结构像最下面的图一样雄视八荒辐射四极，时间上就退化成了N^2，在计算每个点的maxfa时，要先求兄弟们的maxsub最大值在与其父亲的maxfa比较，但是兄弟实在太多了。仔细想一下就知道，作为的同一个父亲的儿子，每一个点的“兄弟们的maxsub”不是其中的老大就是老二。所以在计算完一个节点的maxfa之后递归计算其儿子的maxfa之前，可以先找到儿子们中的老大和老二，给老大对应的点的maxfa设为老二的maxsub，其余的儿子的maxfa均设为老二的maxsub，这样在计算时就不需要考虑兄弟节点，只需跟父亲结点的maxfa相比即可。
顺便说句题外话，提交结果是这样的：
把程序中的输入部分换成输入挂，提交结果就变成了这样：
仅仅是把cin换成了自己写的用getchar实现的读整数，运行时间就少了将近一半之多，几乎与计算和输出加起来花费的时间相等，可以想见cin，cout是有多么垃圾了。除此之外，我用了vector来保存树的结构，在我的电脑上运行时，最后一句话return 0;用了将近10秒，大概是在析构这个东西：vector<int> G[400005]，不做评价。
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
int S[400005], d[400005], maxsub[400005], maxfa[400005];
int N;
vector<int> G[400005];
inline int getint() {
static char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') {
int res = 0;
while ((c = getchar()) >= '0' && c <= '9') {
res = res * 10 + c - '0';
}
return -res;
} else {
int res = c - '0';
while ((c = getchar()) >= '0' && c <= '9') {
res = res * 10 + c - '0';
}
return res;
}
}
void dfssize(int x, int fa) {
int v;
S[x] = 1;
for (int i = 0; i < G[x].size(); i++) {
v = G[x][i];
if (v == fa) {
continue;
}
dfssize(v, x);
S[x] += S[v];
}
}
void dfsdis(int x, int fa) {
int v;
for (int i = 0; i < G[x].size(); i++) {
v = G[x][i];
if (v == fa) {
continue;
}
d[v] = d[x] + 1;
dfsdis(v, x);
}
}
void dfssub(int x, int fa) {
int v;
if (S[x] <= (N / 2)) {
maxsub[x] = S[x];
} else {
maxsub[x] = 0;
}
for (int i = 0; i < G[x].size(); i++) {
v = G[x][i];
if (v == fa) {
continue;
}
dfssub(v, x);
if (maxsub[v] <= (N / 2) && (maxsub[x] < maxsub[v])) {
maxsub[x] = maxsub[v];
}
}
}
void dfsfa(int x, int fa) {
int v, maxA = 0, maxB = 0;
if (fa == 0) {
maxfa[x] = 0;
} else {
if (N - S[x] <= (N / 2)) {
maxfa[x] = N - S[x];
} else {
if (maxfa[fa] > maxfa[x]) {
maxfa[x] = maxfa[fa];
}
}
}
for (int i = 0; i < G[x].size(); i++) {
v = G[x][i];
if (v == fa) {
continue;
}
if (maxsub[v] >= maxA) {
maxB = maxA;
maxA = maxsub[v];
} else if (maxsub[v] > maxB) {
maxB = maxsub[v];
}
}
for (int i = 0; i < G[x].size(); i++) {
v = G[x][i];
if (v == fa) {
continue;
}
if (maxsub[v] == maxA) {
maxfa[v] = maxB;
} else {
maxfa[v] = maxA;
}
dfsfa(v, x);
}
}
int main() {
N=getint();
for (int i = 1; i <= N; i++) {
G[i].clear();
}
int a, b;
for (int i = 1; i < N; i++) {
a=getint();
b=getint();
G[a].push_back(b);
G[b].push_back(a);
}
dfssize(1, 0);
d[1] = 0;
dfsdis(1, 0);
dfssub(1, 0);
memset(maxfa, 0, sizeof(maxfa));
dfsfa(1, 0);
bool rep;
int size;
int maxs;
bool core;
int v;
for (int i = 1; i <= N; i++) {
rep = false;
core = true;
for (int j = 0; j < G[i].size(); j++) {
v = G[i][j];
if (d[v] > d[i]) {
size = S[v];
} else {
size = N - S[i];
}
if (size > (N / 2)) {
if (rep) {
core = false;
break;
}
if (d[v] > d[i]) {
maxs = maxsub[v];
} else {
maxs = maxfa[i];
}
if (maxs <= (N / 2) && (size - maxs <= (N / 2))) {
rep = true;
} else {
core = false;
}
}
}
if (core) {
cout << 1;
} else {
cout << 0;
}
cout << ' ';
}
cout << endl;
return 0;
}