rating又掉下去了。好不容易蓝了。。。。
A。。没读懂题，wa了好几次，明天问队友补上。。。
题意：一条直线上n个点x1,x2...xn，现在在位置a，求要经过任意n-1个点的最小路程
题解：分类讨论，乱搞搞总会出来的，我大概写的很笨……
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; int x[]; ll cal(ll x, ll a, ll z) {
return min((a-x)*+(z-a) , (z-a)*+(a-x));
} int main() {
int n, a;
scanf("%d%d", &n, &a);
for (int i = ; i < n; ++i) {
scanf("%d", x+i);
}
sort(x, x+n);
ll ans = 1e18, tmp; if (n == ) cout << ;
else if (n == ) cout << min(abs(a-x[]), abs(a-x[]));
else if (a >= x[n-]) cout << a-x[];
else if (a <= x[]) cout << x[n-]-a;
else if (a <= x[]) cout << min(cal(x[], a, x[n-]), (ll)(x[n-]-a));
else if (a > x[n-]) cout << min(cal(x[], a, x[n-]), (ll)(a-x[]));
else cout << min(cal(x[],a,x[n-]), cal(x[],a,x[n-]));
return ;
}
题意：给一个字符串，要求替换任意一个非空字串，使得替换后字串字典序最小。替换的方法是z->y,y->x,....,b->a,a->z
题解：C题怎么会这么简单。。。很容易想到替换尽可能靠前的字符，而且不能替换a，注意题目要求的必须替换一个字串，所以字串中所有字母都是a的时候，只能把最后一个变成z了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; char a[];
int main() {
while (cin >> a) {
bool fg = false;
int n = strlen(a);
int cnt = ;
for (int i = ; i < n; ++i) {
if (a[i] != 'a') {a[i]--; fg=true;}
else if(fg) break;
}
if (!fg) a[n-] = 'z';
cout << a << endl;
} return ;
}
题意：对于一个只有0和1的序列，会有很多00,01,10,11的子序列，现在给你00,01,10,11的子序列的数量，求符合要求的子串，没有输出Impossible
题解：注意，子序列不同于子串，不连续。
设子串中0的数量是x，那么00的数量一定是C(2,x)，1同理。然后设0的数量是x，1的数量是y，所以所有子序列的个数是C(2,x+y)，即C(2,x+y)==a+b+c+d，如果不相等则不可能构成。要注意的地方是当00的数量为0的时候，x既可以为0，也可以为1，需要根据bc判断。y同理。
至于字符串的构造，有点贪心的想法。瞎搞的。。。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char ans[];
int main() {
ll a, b, c, d;
while (cin >> a >> b >> c >> d) {
ll x = (ll)sqrt(a*)+;
ll y = (ll)sqrt(d*)+;
if (a+b+c+d == ) {
puts("");
continue;
}
if (a == ) {
if (b || c) x = ; else x = ;
}
if (d == ) {
if (b || c) y = ; else y = ;
}
if (!(x*(x-) == a* && y*(y-) == d*)) {
puts("Impossible");
continue;
}
ll n = x+y;
ll xnt = n*(n-)/-a-d;
if (b+c != xnt) {
puts("Impossible");
continue;
}
int idx = ;
int cnt = x+y;
while (cnt) {
if (b < y) {
ans[idx++] = '';
c -= x;
y--;
} else if (c < x) {
ans[idx++] = '';
b -= y;
x--;
} else if (b >= c) {
ans[idx++] = '';
b -= y;
x--;
} else {
ans[idx++] = '';
c -= x;
y--;
}
cnt--;
}
ans[idx] = ;
printf("%s\n", ans);
}
return ;
}
题意：给一棵树，对于每一个结点，可不可以通过在树上去掉一条边再增加一条边（必须还是一棵树），使这个结点成为这棵树的重心。
题解：%%%明神
对于一个点，如果不能当重心，一定是它有一棵子树u，size[u]>n/2，那么只要在这个子树u中找到一个子树v，满足size[v]<=n/2且size[u]-size[v]<=n/2就可以了。
于是树形dp，求每个点的<=n/2的最大子树的大小。
至于向上思想类似，随便搞搞，具体看代码。
不喜欢用邻接表存图，看起来很麻烦，可是vector确实会慢一些，比赛一定不能用=。=
#include <bits/stdc++.h> using namespace std; typedef long long ll;
const int N = ; vector<int> g[N];
int sz[N], up[N], dn[N]; // up向上的最大的不大于n/2的子树大小 dn向下的
int ans[N];
int n; inline int read()
{
char ch = getchar();
int data = ;
while (ch < '' || ch > '')
ch = getchar();
do {
data = data* + ch-'';
ch = getchar();
} while (ch >= '' && ch <= '');
return data;
} void UP(int &x, int y) { if(y>x) x=y; }
void dfs(int u, int fa) { // 第一遍向下dfs
sz[u] = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if (v == fa) continue;
dfs(v, u);
if (sz[v] - dn[v] > n/) ans[u] = ;
sz[u] += sz[v];
UP(dn[u], dn[v]);
}
if (sz[u] <= n/) dn[u] = sz[u];
}
void dfs1(int u, int fa) { // 第二遍向上
if (n-sz[u] - up[u] > n/) ans[u] = ;
if (n-sz[u] <= n/) up[u] = n-sz[u]; int mx = ; // 对于每一个结点向上的最大值 可能来自向上的链 也可能来自父节点的其他子树
// mx记录的就父节点其他子树的最大值
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if (v == fa) continue;
up[v] = max(up[u], mx);
UP(mx, dn[v]);
}
mx = ;
for (int i = g[u].size()-; i >= ; --i) {
int v = g[u][i];
if (v == fa) continue;
UP(up[v], mx);
UP(mx, dn[v]);
dfs1(v, u);
}
} int main() {
scanf("%d", &n);
int u, v;
for (int i = ; i < n; ++i) {
u = read(); v = read();
g[u].push_back(v);
g[v].push_back(u);
}
if (n == ) { printf("1 1"); return ; } for (int i = ; i <= n; ++i) ans[i] = ;
dfs(, );
dfs1(, );
for (int i = ; i <= n; ++i) {
printf("%d", ans[i]);
if (i != n) printf(" ");
}
return ;
}