codeforces1304解题报告<

A. Two Rabbits

【题意】

两只兔子分别从两个位置相向跳跃，每步分别可跳步。问跳多少步后可以相遇。如果无法相遇输出。

【思路】

输出即可。不能整除时即无解。

【代码】

#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

【题意】

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

【思路】

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

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

【代码】

#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

【题意】

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

【思路】

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

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

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

【代码】

#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

【题意】

给出一个长度为的仅包含的字符串。完成以下两个任务：

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

【题意】

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

【思路】

因为每个点可以重复经过，一条路径只要满足并且与的奇偶性相同即可。

有种情况:

1.不经过边

2.经过边且路径为

3.经过边且路径为

枚举一下判断即可。

【代码】

#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

【题意】

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

【思路】

用表示以第行作为第一行的矩阵覆盖这个区间时，答案最大为多少。

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

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

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

当与上一行相交时，如果上一行开始时位置为时，当前行造成的贡献就是，当变大时会变大，t变大时也变大，单调队列优化即可。

【代码】

#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;
}
全部评论

相关推荐

11-29 17:09
已编辑
西安电子科技大学 C++
点赞 评论 收藏
分享
头像
11-28 14:42
江淮汽车_JAVA开发工程师(准入职员工)
江淮汽车内推
安徽江淮汽车股份有限公司机械工程师面经先是自我介绍，让后针对你的简历问一些问题，最后拉一下家常，问你有没有女朋友啊，父母是干什么的啊等等。问题整理：1.你是怎么组织策划联谊活动的？2.你在实习的时候都干了些什么？3.你有没有女朋友？4.家庭成员情况，父母是干什么的？是否是独生的？5.对我们公司的认识及了解？6.对薪资待遇有什么要求？7.如何面对生活上的压力？8.用三个词描述一下自己的性格特点！9.近期参加的项目或者竞赛?遇到的困难和挑战?当时是怎么考虑去解决该问题?结果如何?10.请您具体描述一下解决难题的过程中，面对不同的关键人物您是如何应对的，结果如何?总的来说，整个面试很少专业性的问题，...
点赞 评论 收藏
分享
11-28 20:35
苏州大学 IC验证工程师
如何评价
qz鹿：*** 祝他毕业就失业
点赞 评论 收藏
分享
10-24 13:36
门头沟学院 Java
亲手挂自己
又不服气又无能为力的一集
Zzzzoooo：更新：今天下午有hr联系我去不去客户端，拒了
点赞 评论 收藏
分享
11-26 15:52
西京学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
237389次浏览 2039人参与
# 机械求职避坑tips #
23655次浏览 249人参与
# 北方华创开奖 #
67104次浏览 553人参与
# 25届秋招总结 #
411316次浏览 4128人参与
# 25届机械人为了秋招做了哪些准备？ #
26297次浏览 363人参与
# 地方国企笔面经互助 #
6975次浏览 17人参与
# 阿里云管培生offer #
62633次浏览 1760人参与
# ai智能作图 #
29118次浏览 351人参与
# 虾皮求职进展汇总 #
91815次浏览 750人参与
# 实习，投递多份简历没人回复怎么办 #
2440902次浏览 34746人参与
# 软件开发投递记录 #
1481677次浏览 23947人参与
# 我的实习求职记录 #
6133765次浏览 84021人参与
# 我在牛爱网找对象 #
74899次浏览 555人参与
# 发工资后，你做的第一件事是什么 #
9159次浏览 43人参与
# 985本硕1个中小厂offer，摆烂or继续努力 #
83312次浏览 602人参与
# 机械人怎么评价今年的华为 #
157972次浏览 1352人参与
# 京东求职进展汇总 #
513112次浏览 4680人参与
# 如果可以，你希望哪个公司来捞你 #
33979次浏览 196人参与
# 你觉得通信/硬件有必要实习吗？ #
54800次浏览 698人参与
# 歌尔求职进展汇总 #
42915次浏览 294人参与
# 在职场上，你最讨厌什么样的同事 #
6092次浏览 91人参与
# 如果再来一次，你还会选择这个工作吗？ #
115903次浏览 1145人参与
牛客网
牛客企业服务