916

话说上次目标是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循环
我来评几句
登录后评论

已发表评论数()

相关站点

热门文章