话说上次目标是150分， 然后这一次考的就是。。。147分， 也算是很接近了吧， 不过可能也有题目简单的原因， 其实分数还是能够更高一点。有进步就是好事， 加油加油我最棒， yeah！
这是第一道题，也是得分最高的一道题， 是65分， 其余的是TLE， 其实这道题我也是触摸到了正解的边缘吧， 思想十分正确， 但最后还是没有A掉。 我当时想的是搜索两遍， 分别为湖泊 > 山川和山川 > 湖泊， 就那第一次举例， 将湖泊赋为1 ， 山川为-1， 优先搜索子节点， 将得到的值与0取max并返回， 这样就得到了必走当前根节点的情况下的最大无聊程度， 但此时根节点不一定非要走， 我就枚举每一个点为根节点， 跑n遍DFS， 时间繁杂度为$O(n^2)$。其实正解和我的思路相同， 只是每次返回子节点的值是都取一次max， 这样就保证了可以不选根节点的情况， 以1位根节点DFS即可（据说这个东西叫树形DP）， 而且显然两个DFS可以合成一个。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 100;
template < typename T > inline void read(T &x) {
x = 0; T ff = 1, ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') ff = -1;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= ff;
}
template < typename T > inline void write(T x) {
if(x == 0) {
putchar('0');
return ;
}
if(x < 0) putchar('-'), x = -x;
static T ch[20], tot = 0;
while(x) {
ch[++tot] = x % 10 + '0';
x /= 10;
}
while(tot) putchar(ch[tot--]);
}
int n, ans, flag = false, a[MAXN], f[MAXN], g[MAXN];
int lin[MAXN], tot = 0;
struct edge {
int y, next;
}e[MAXN << 1];
inline void add(int xx, int yy) {
e[++tot].y = yy;
e[tot].next = lin[xx];
lin[xx] = tot;
}
/*inline int dfs1(int x, int fa) {
int u;
if(a[x] == 0) u = -1;
else u = 1;
for(register int i = lin[x], y; i; i = e[i].next) {
if((y = e[i].y) == fa) continue;
u += dfs1(y, x);
}
return max(u, 0);
}
inline int dfs2(int x, int fa) {
int u;
if(a[x] == 1) u = -1;
else u = 1;
for(register int i = lin[x], y; i; i = e[i].next) {
if((y = e[i].y) == fa) continue;
u += dfs2(y, x);
}
return max(u, 0);
}*/
inline void dfs(int x, int fa) {
if(a[x] == 1) f[x] = 1;
else f[x] = -1;
g[x] = -f[x];
for(register int i = lin[x], y; i; i = e[i].next) {
if((y = e[i].y) == fa) continue;
dfs(y, x);
f[x] = max(f[x], f[x] + f[y]);
g[x] = max(g[x], g[x] + g[y]);
}
ans = max(ans, f[x]);
ans = max(ans, g[x]);
return ;
}
int main() {
freopen("trip.in", "r", stdin);
freopen("trip.out", "w", stdout);
read(n);
for(register int i = 1; i <= n; ++i) {
read(a[i]);
if(i != 1 && a[i] != a[i - 1]) flag = true;
}
for(register int i = 1; i < n; ++i) {
int u, v;
read(u); read(v);
add(u, v);
add(v, u);
}
if(!flag) {
write(n);
return 0;
}
// for(register int i = 1; i <= n; ++i) {
// ans = max(ans, dfs1(i, 0));
// ans = max(ans, dfs2(i, 0));
// }
dfs(1, 0);
write(ans);
return 0;
}
正解
看到这道题的时候十分显然， 当然是搜索啊， 枚举每一种情况并取模， 时间复杂度为$O(m^n)$， 那我们就bb正解吧， 是用容斥的思想， 用所有的情况减去不合法的情况。 首先每一个回文串都是前一半对称过来， 而前面的每一个位置都有m种选择， 所以总的方案数就是m$\left\lceil \frac{n}{2} \right\rceil$， 通过一个定理：一个长度为n回文串有前缀回文串， 那一定存在一个长度 $\le\frac{n}{2}$的子前缀回文串（证明省略), 用f(i)表示长度为i的字符串满足方案的个数， 则有$$f(i)=m^{\left \lceil\frac i2 \right \rceil}-\sum_{j=2}^{j \le \left \lceil\frac i2 \right \rceil}f(j) \times m^{\left \lceil\frac {i-j}{2} \right \rceil}$$ 这是一个$O(n^2)$的算法， 期望得分65分， 我们可以通过前缀和来优化到$O(n)$级别， 我们设
$$g(\left \lceil\frac i2 \right \rceil)=\sum_{j=2}^{j \le \left \lceil\frac i2 \right \rceil}f(j) \times m^{\left \lceil\frac {i-j}{2} \right \rceil}$$
则$$g(i) = f(i) + g(i-1) \times\ m$$， 我们可以在$O(n)$的时间里求出答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 100;
const int MAXM = 3e3 + 10;
template < typename T > inline void read(T &x) {
x = 0; T ff = 1, ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') ff = -1;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= ff;
}
template < typename T > inline void write(T x) {
if(x == 0) {
putchar('0');
return ;
}
if(x < 0) putchar('-'), x = -x;
static T ch[20], tot = 0;
while(x) {
ch[++tot] = x % 10 + '0';
x /= 10;
}
while(tot) putchar(ch[tot--]);
}
int n, m, ans, f[MAXN], p[MAXN], g[MAXN];
int main() {
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
read(n); read(m);
p[0] = 1;
for(int i = 1; i <= n; ++i) p[i] = ((ll) p[i - 1] * m) % mod;
for(int i = 1; i <= n; ++i) {
f[i] = p[(i + 1) >> 1] - g[(i + 1) >> 1];
if(f[i] < 0) f[i] += mod;
if(i > 1) g[i] = (f[i] + ((ll) g[i - 1] * m) % mod) % mod;
}
write(f[n]);
return 0;
}
正解
吐槽一波， 这道题数据真的很水。。。
我们可以知道， 最后只能留下一个棋子， 所以只要枚举每一个点是否留下就可以了， 至于一个点怎么样才能留下， 就是加上m以后要吃完所有的点， 这样我们就能够想到， 枚举每一个点， 分别去吃左边和右边的棋子， 如果这个点能够大于最大的那个点， 那么它一定是一个必胜点， 所以每吃一步就做一次判断， 时间复杂度$O(n) \sim O(n^2)$之间， 具体时间大概是$O(n*\sqrt{n})$，但是， 数据过水， 就这样A掉了， 据说正解是记忆化搜索， 从点权最大的点开始向两边搜索， 反正我是不会啦啦。。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 8e6 + 100;
template < typename T > inline void read(T &x) {
x = 0; T ff = 1, ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') ff = -1;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= ff;
}
template < typename T > inline void write(T x) {
if(x == 0) {
putchar('0');
return ;
}
if(x < 0) putchar('-'), x = -x;
static T ch[20], tot = 0;
while(x) {
ch[++tot] = x % 10 + '0';
x /= 10;
}
while(tot) putchar(ch[tot--]);
}
int n, m, r, maxx, a[MAXN], vis[MAXN];
ll x;
inline int goright() {
if(r > n) return 2;
for( ; r <= n; ++r) {
if(x >= a[r]) x += a[r];
else return 1;
if(x >= maxx) return 1;
}
return 1;
}
int main() {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
read(n); read(m);
for(register int i = 1; i <= n; ++i)
read(a[i]), maxx = max(maxx, a[i]);
for(register int i = 1; i <= n; ++i) {
x = a[i] + m;
if((x >= a[i - 1] && vis[i - 1]) || x >= maxx) {
vis[i] = true;
continue;
}
if(x <= a[i - 1] && !vis[i - 1]) continue;
r = i + 1;
int flag = false;
for(register int j = i - 1; j >= 1; --j) {
if(x >= a[j]) x += a[j];
else {
if(goright() == 2) {
flag = 2;
break;
} else {
if(x >= maxx){
vis[i] = true;
break;
}
if(x >= a[j]) x += a[j];
else {
flag = 2;
break;
}
}
}
if(x >= maxx) {
flag = 2;
vis[i] = true;
break;
}
}
if(flag == 2) continue;
if(r <= n) {
for(; r <= n; ++r) {
if(x >= maxx) {
vis[i] = true;
break;
}
if(x >= a[r]) x += a[r];
else break;
}
}
}
for(register int i = 1; i <= n; ++i) {
if(vis[i]) {
write(i);
putchar(' ');
}
}
return 0;
}
神奇的for循环