#include <iostream>
using namespace std;
int a[];
int main() {
int n, b, d;
cin >> n >> b >> d;
for (int i = ; i <= n; i++) {
cin >> a[i];
}
int ans = , tmp = ;
for (int i = ; i <= n; i++) {
if (a[i] > b) {
continue;
}
tmp += a[i];
if (tmp > d) {
tmp = ;
ans++;
}
}
cout << ans << endl;
return ;
}
两种情况，先向左走再折回向右或先向右走再折回向左。
#include <iostream>
#include <algorithm>
using namespace std;
int x[], l[], r[];
int main() {
int n, a;
cin >> n >> a;
for (int i = ; i < n; i++) {
cin >> x[i];
}
sort(x, x + n);
int ln=, rn=;
for (int i = ; i < n; i++) {
if (x[i] <= a) {
ln++;
}
}
rn = n - ln;
l[] = ;
for (int i = ; i <= ln; i++) {
l[i] = a - x[ln - i];
}
r[] = ;
for (int i = ; i <= rn; i++) {
r[i] = x[ln + i - ] - a;
}
int ans = 0x7fffffff;
for (int i = ; i <= ln; i++) {
if (rn < n - i - ) {
continue;
}
if ((l[i] << ) + r[n - i - ] < ans) {
ans = (l[i] << ) + r[n - i - ];
}
}
for (int i = ; i <= rn; i++) {
if (ln < n - i - ) {
continue;
}
if ((r[i] << ) + l[n - i - ] < ans) {
ans = (r[i] << ) + l[n - i - ];
}
}
cout << ans << endl;
return ;
}
没看懂题意，估计挺水的。
#include<cstdio>
char s[];
int i,f;
int main()
{
for(gets(s);s[i];++i)
{
if(s[i]>)f=;
if(f)if(s[i]>)--s[i];else break;
}
if(!f)s[i-]=;
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[];
int main() {
cin >> a00 >> a01 >> a10 >> a11;
int n0 = -, n1 = -;
for (int i = ; i <= a00 + ; i++) {
if (i * (i - ) == * a00) {
n0 = i;
break;
}
if (i * (i - ) > * a00) {
break;
}
}
for (int i = ; i <= a11 + ; i++) {
if (i * (i - ) == * a11) {
n1 = i;
break;
}
if (i * (i - ) > * a11) {
break;
}
}
if (n0 == && (a01 || a10)) {
n0 = ;
}
if (n1 == && (a01 || a10)) {
n1 = ;
}
if (n0 == - || n1 == - || n0 * n1 != (a01 + a10)) {
cout << "Impossible" << endl;
return ;
}
if (n0 == && n1 == ) {
cout << ;
return ;
}
memset(a, , sizeof(a));
while (a10 > n0) {
cout << ;
a10 -= n0;
n1--;
}
for (int i = ; i <= n0 - a10; i++) {
cout << ;
}
if (a10) {
cout << ;
n1--;
}
for (int i = ; i <= a10; i++) {
cout << ;
}
for (int i = ; i <= n1; i++) {
cout << ;
}
return ;
}
每个点做一次判断。如果该点可以作为重心或操作一次后可以为重心，则应满足以若该点为树根则其子树的大小均不超过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[], d[], maxsub[], maxfa[];
int N;
vector<int> G[];
inline int getint() {
static char c;
while (((c = getchar()) < '' || c > '') && c != '-');
if (c == '-') {
int res = ;
while ((c = getchar()) >= '' && c <= '') {
res = res * + c - '';
}
return -res;
} else {
int res = c - '';
while ((c = getchar()) >= '' && c <= '') {
res = res * + c - '';
}
return res;
}
}
void dfssize(int x, int fa) {
int v;
S[x] = ;
for (int i = ; 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 = ; i < G[x].size(); i++) {
v = G[x][i];
if (v == fa) {
continue;
}
d[v] = d[x] + ;
dfsdis(v, x);
}
}
void dfssub(int x, int fa) {
int v;
if (S[x] <= (N / )) {
maxsub[x] = S[x];
} else {
maxsub[x] = ;
}
for (int i = ; i < G[x].size(); i++) {
v = G[x][i];
if (v == fa) {
continue;
}
dfssub(v, x);
if (maxsub[v] <= (N / ) && (maxsub[x] < maxsub[v])) {
maxsub[x] = maxsub[v];
}
}
}
void dfsfa(int x, int fa) {
int v, maxA = , maxB = ;
if (fa == ) {
maxfa[x] = ;
} else {
if (N - S[x] <= (N / )) {
maxfa[x] = N - S[x];
} else {
if (maxfa[fa] > maxfa[x]) {
maxfa[x] = maxfa[fa];
}
}
}
for (int i = ; 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 = ; 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 = ; i <= N; i++) {
G[i].clear();
}
int a, b;
for (int i = ; i < N; i++) {
a=getint();
b=getint();
G[a].push_back(b);
G[b].push_back(a);
}
dfssize(, );
d[] = ;
dfsdis(, );
dfssub(, );
memset(maxfa, , sizeof(maxfa));
dfsfa(, );
bool rep;
int size;
int maxs;
bool core;
int v;
for (int i = ; i <= N; i++) {
rep = false;
core = true;
for (int j = ; 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 / )) {
if (rep) {
core = false;
break;
}
if (d[v] > d[i]) {
maxs = maxsub[v];
} else {
maxs = maxfa[i];
}
if (maxs <= (N / ) && (size - maxs <= (N / ))) {
rep = true;
} else {
core = false;
}
}
}
if (core) {
cout << ;
} else {
cout << ;
}
cout << ' ';
}
cout << endl;
return ;
}