codeforces1304解题报告<

A. Two Rabbits

【题意】

两只兔子分别从 $x,y$ 两个位置相向跳跃，每步分别可跳 $a,b$ 步。问跳多少步后可以相遇。如果无法相遇输出 $-1$ 。

【思路】

输出 $\frac{y-x}{a + b}$ 即可。不能整除时即无解。

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

int main() {
    int T = read();
    while(T--) {
        ll x = read(),y = read(),a = read(),b = read();
        a += b;
        y -= x;
        if(y % a != 0) {
            puts("-1");
        }
        else printf("%d\n",y / a);
    }
    return 0;
}

B. Longest Palindrome

【题意】

给出 $n$ 个长度为 $m$ 的，字符串，从中选最多个组成回文串。

【思路】

先找到恰好相反的所有字符串。

如果除去这些字符串之后可以找到到一个本身就是回文串的字符串就将他加到中间去。

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 110;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int q[N],vis[N];
char s[N][N];
int main() {
    int n = read(),m = read();

    for(int i = 1;i <= n;++i)
        scanf("%s",s[i] + 1);

    int tot = 0;

    for(int i = 1;i <= n;++i) {
        if(vis[i]) continue;
        for(int j = i + 1;j <= n;++j) {
            if(vis[j]) continue;
            int flag = 0;
            for(int k = 1;k <= m;++k) {
                if(s[i][k] != s[j][m - k + 1]) {
                    flag = 1;break;
                }
            }
            if(!flag) {
                vis[i] = vis[j] = 1;
                q[++tot] = i;q[++tot] = j;
            }
        }
    }
    int flag = 0;
    for(int i = 1;i <= n;++i) {
        if(vis[i]) continue;
        int bz = 0;
        for(int j = 1;j <= m;++j) {
            if(s[i][j] != s[i][m - j + 1]) {
                bz = 1;break;
            }
        }
        if(!bz) {
            flag = i;break;
        }
    }
    int k = 0;
    if(flag) k = 1;
    // printf("%d\n",tot);
    printf("%d\n",m * (tot + k));

    for(int i = 1;i <= tot;i += 2) {
        printf("%s",s[q[i]] + 1);
    }
    if(flag) printf("%s",s[flag] + 1);
    for(int i = tot;i >= 2;i -= 2) 
        printf("%s",s[q[i]] + 1);

    return 0;
}

C. Air Conditioner

【题意】

一家餐厅有 $n$ 个顾客，每个顾客有一个到达时间，可以接受的温度范围。餐厅每单位时间可以将温度 $+1$ 或者将温度 $-1$ 或保持不变。问是否可以使每个顾客到达时温度都在其可接受的范围之内。

【思路】

从后向前考虑，维护一个当前可容纳的温度范围。并于当前客人可容纳范围取交集。

然后再根据当前客人和前一个客人之间的时间扩大范围。

当出现当前可容纳范围为空集或者最初温度不在最终可容纳范围之内时表明无解。

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 110;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int t[N],l[N],r[N];
int main() {
    int T = read();
    while(T--) {
        int n = read(),m = read();
        for(int i = 1;i <= n; ++i) {
            t[i] = read();l[i] = read();r[i] = read();
        }

        int L = -1e9,R = 1e9;
        int flag = 0;
        for(int i = n;i >= 1;--i) {
            R = min(R,r[i]);
            L = max(L,l[i]);
        // printf("!!%d %d\n",L,R);

            if(R < L) {
                flag = 1;break;
            }
            R += (t[i] - t[i - 1]);
            L -= (t[i] - t[i - 1]);
            // printf("!!%d\n",t[i] - t[i - 1]);
        }
        // printf("%d\n",flag);
        if(flag) puts("NO");
        else if(m >= L && m <= R) puts("YES");
        else puts("NO");
    }

    return 0;
}

D. Shortest and Longest LIS

【题意】

给出一个长度为 $n-1$ 的仅包含 $'<','>'$ 的字符串。完成以下两个任务：

1.找到满足该字符串的一个n的排列，并且该排列的LIS最小。

2.找到满足该字符串的一个n的排列，并且该排列的LIS最大。

【思路】

第一个条件就尽可能的让前面的数字大，从大到小的塞入数字。

第二个恰好相反，就让前面的尽可能小，从小到大的塞入数字。

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 200010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char s[N];
int a[N];
int main() {
    int T = read();
    while(T--) {
        int n = read();
        int now = n;
        scanf("%s",s + 1);
        a[n] = 0;
        for(int i = 1;i < n;) {
            if(s[i] == '>') a[i] = now--,++i;
            else {
                int j = i;
                for(j = i;;++j) {
                    if(s[j] != '<') break;
                }
                int k = j;
                for(;j >= i;--j) {
                    a[j] = now--;
                }
                i = k + 1;
            }
        }
        if(!a[n]) a[n] = now;

        for(int i = 1;i <= n;++i) printf("%d ",a[i]);
        puts("");

        a[n] = 0;
        now = 1;

        for(int i = 1;i < n;) {
            if(s[i] == '<') a[i] = now++,++i;
            else {
                int j = i;
                for(j = i;;++j) {
                    if(s[j] != '>') break;
                }
                int k = j;
                for(;j >= i;--j) a[j] = now++;
                i = k + 1;
            }
        }
        if(!a[n]) a[n] = now;
        for(int i = 1;i <= n;++i) printf("%d ",a[i]);
        puts("");
    }

    return 0;
}

E. 1-Trees and Queries

【题意】

给出 $n$ 个结点的一棵树，然后又 $m$ 次询问，每次询问给出 $a,b,c,d,k$ ，表示在 $a,b$ 之间添加一条边，从 $c$ 到 $d$ 是否存在长度为 $k$ 的路径,每条边和每个点都可重复经过。

【思路】

因为每个点可以重复经过，一条路径只要满足 $dist(c,d) \le k$ 并且 $dist(c,d)$ 与 $k$ 的奇偶性相同即可。

$dist(c,d)$ 有 $3$ 种情况:

1.不经过边 $(a\rightarrow b)$

2.经过边 $(a\rightarrow b)$ 且路径为 $dist(c,a)+dist(d,b)+1$

3.经过边 $(a\rightarrow b)$ 且路径为 $dist(d,a)+dist(c,b)+1$

枚举一下判断即可。

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 200010,logN = 20;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int v,nxt;
}e[N];
int lca[N][logN + 1];

int head[N],ejs;
void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] =ejs;
}
int dis[N];
void dfs(int u,int fa) {
    for(int i = 1;i <= logN;++i)
        lca[u][i] = lca[lca[u][i - 1]][i - 1];

    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        lca[v][0] = u;
        dis[v] = dis[u] + 1;
        dfs(v,u);
    }
}

int LCA(int x,int y) {
    if(dis[x] < dis[y]) swap(x,y);

    for(int i = logN;i >= 0;--i)
        if(dis[lca[x][i]] >= dis[y]) x = lca[x][i];

    for(int i = logN;i >= 0;--i) 
        if(lca[x][i] != lca[y][i]) x = lca[x][i],y = lca[y][i];

    if(x != y) x = lca[x][0];
    return x;
}

int dist(int x,int y) {
    return dis[x] + dis[y] - 2 * dis[LCA(x,y)];
}

int main() {
    int n = read();    
    for(int i = 1;i < n;++i) {
        int u = read(),v = read();
        add(u,v);add(v,u);
    }

    dfs(1,0);

    int Q = read();
    while(Q--) {
        int x = read(),y = read(),a = read(),b = read(),k = read();

        int t = dist(a,b);
        if(t <= k && (t & 1) == (k & 1)) {
            puts("YES");continue;
        }
        // puts("!!!");
        int t1 = dist(x,a),t2 = dist(y,b);
        t = t1 + t2 + 1;
        if(t <= k && (t & 1) == (k & 1)) {
            puts("YES");continue;
        } 

        t1 = dist(x,b);t2 = dist(y,a);
        t = t1 + t2 + 1;
        if(t <= k && (t & 1) == (k & 1)) {
            puts("YES");continue;
        }
        puts("NO");

    }
    return 0;
}

F. Animal Observation

【题意】

给出一个 $n\times m$ 的方格图，每个方格上有一个数字。有红色和蓝色两种 $2\times K$ 的矩阵。红色第一行必须覆盖第奇数行，蓝色第一行必须覆盖第偶数行。两个矩阵重复覆盖的位置答案只计算一次，求最种被覆盖到的方格数字之和为多少。

【思路】

用 $f[i][j]$ 表示以第 $i$ 行作为第一行的矩阵覆盖 $[j,j+k-1]$ 这个区间时，答案最大为多少。

考虑 $k$ 比较小的时候暴力转移，先对于每一行求个前缀和。然后枚举一下上一行开始的位置，统计答案即可。

当k比较大时，发现转移有当前行和上一行相交和当前行与上一行不相交两种情况。

如果当前行与上一行不相交，只需要求个前缀最大值和后缀最大值进行转移即可。

当与上一行相交时，如果上一行开始时位置为 $t(t\ge j - k + 1)$ 时，当前行造成的贡献就是 $sum[j + k - 1] - sum[t - 1]$ ，当 $j$ 变大时 $t$ 会变大，t变大时 $sum[t - 1]$ 也变大，单调队列优化即可。

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 40010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int a[52][N],f[52][N],q[N],g[52][N],h[52][N];
int main() {
    int n = read(),m = read(),k = read();
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= m;++j) 
            a[i][j] = a[i][j - 1] + read();

    for(int i = 1;i <= m - k + 1;++i) f[1][i] = a[1][i + k - 1] - a[1][i - 1];
    for(int i = 2;i <= n;++i) {
        for(int j = 1;j + k - 1 <= m;++j) 
            g[i][j] = max(g[i][j - 1],f[i - 1][j] + a[i][j + k - 1] - a[i][j - 1]);

        for(int j = m - k + 1;j >= 1;--j)
            h[i][j] = max(h[i][j + 1],f[i - 1][j] + a[i][j + k - 1] - a[i][j - 1]);


        for(int j = k + 1;j + k - 1 <= m;++j) f[i][j] = max(f[i][j],g[i][j - k] + a[i][j + k - 1] - a[i][j - 1]);

        for(int j = m - k + 1;j >= 1;--j) f[i][j] = max(f[i][j],h[i][j + k] + a[i][j + k - 1] - a[i][j - 1]);

        int l = 1,r = 0;

        for(int j = 1;j <= m - k + 1;++j) {
            while(l <= r && q[l] <= j - k) ++l;
            while(l <= r && f[i - 1][q[r]] + a[i][j + k - 1] - a[i][q[r] - 1] <= f[i - 1][j] + a[i][j + k - 1] - a[i][j - 1]) --r;
            q[++r] = j;
            f[i][j] = max(f[i][j],f[i - 1][q[l]] + a[i][j + k - 1] - a[i][q[l] - 1]);
        }

        l = 1,r = 0;
        for(int j = m - k + 1;j >= 1;--j) {
            while(l <= r && q[l] >= j + k) ++l;
            while(l <= r && f[i - 1][q[r]] + a[i][q[r] + k - 1] - a[i][j - 1] <= f[i - 1][j] + a[i][j + k - 1] - a[i][j - 1]) --r;
            q[++r] = j;
            f[i][j] = max(f[i][j],f[i - 1][q[l]] + a[i][q[l] + k - 1] - a[i][j - 1]);
        }

    }

    int ans = 0;
    for(int i = 1;i <= m - k + 1;++i)    ans = max(ans,f[n][i]);

    cout<<ans;

    return 0;
}