您的位置: 首页  >  IT文章  >  Codeforces补题2020.3.2 （Round621 Div2）

Codeforces补题2020.3.2 （Round621 Div2）

分类: IT文章 • 2024-03-21 18:21:54

A.Cow and Haybales

美国建设行动（USACO）最近命令农夫约翰在农场上布置n堆干草堆。第i堆包含ai haybales。

但是，农夫约翰刚刚去度假，贝西独自一人。每天，顽皮的贝西（Bessie）可以选择将任何干草堆中的任何干草捆移到相邻的干草堆中。形式上，她有一天可以选择两个索引i和j（1≤i，j≤n），使得| i | j | = 1且ai> 0并应用ai = ai-1，aj = aj + 1。她也可能因为懒惰而决定在某些日子不做任何事情。

贝西想使第1堆中的干草草数量最大化（即使a1最大化），而在农夫约翰回来之前，她只有d天的时间这样做。如果她的行为最佳，请帮助她找到最大的草捆数量！

输入值 输入包含多个测试用例。第一行包含一个整数t（1≤t≤100）-测试用例的数量。接下来的2t行包含测试用例的描述-每个测试用例两行。

每个测试用例的第一行包含整数n和d（1≤n，d≤100）-分别是干草堆的数量和天数。

每个测试用例的第二行包含n个整数a1，a2，…，an（0≤ai≤100）—每堆中的干草草数量。

输出量 对于每个测试用例，输出一个整数：如果Bessie表现最佳，则在d天后可能堆入1号草堆的最大草捆数量。

题解：

从头开始依次遍历每个草堆即可。

简单题。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1014;
int a[maxn];
int T;
int N,K;
int main () {
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&N,&K);
        vector<int> vi;
        for (int i=1;i<=N;i++) scanf("%d",&a[i]);
        for (int i=2;i<=N;i++) {
            if (!a[i]) continue;
            while (K>=i-1&&a[i]) {
                a[1]++;
                a[i]--;
                K=K-(i-1); 
            }
        }
        printf ("%d
",a[1]);
    } 
    return 0;
}
View Code

B.Cow and Friend

贝茜有太多的朋友，因为她是每个人最喜欢的母牛！她的新朋友Rabbit（Rabbit）试图越过以便他们玩！

更具体地说，他希望通过进行多跳来从（0,0）变为（x，0）。如果跳的端点之间的欧几里得距离是它的n个最喜欢的数字之一：a1，a2，…，an，他只愿意在2D平面上从一个点跳到另一个点。 Rabbit从（0,0）到（x，0）所需的最小跳数是多少？兔子可能会落在具有非整数坐标的点上。可以证明，兔子总是可以到达目的地。

回想点（xi，yi）和（xj，yj）之间的欧几里得距离为（xi-xj）2+（yi-yj）2 --------------------- √。

例如，如果Rabbit有喜欢的数字1和3，则他可以从两步跳中从（0,0）跳到（4,0），如下所示。请注意，还有其他有效的方法可以在2跳中跳到（4,0）（例如（0,0）→（2，−5–√）→（4,0））。

这是第一个示例的图形。这两跳的距离均为3，这是Rabbit最喜欢的数字之一。 换句话说，Rabbit每次选择一些数字ai，并在他想要的任何方向上选择距离等于ai的跃点。同一号码可以多次使用。

输入值 输入包含多个测试用例。第一行包含一个整数t（1≤t≤1000）-测试用例的数量。接下来的2t行包含测试用例-每个测试用例两行。

每个测试用例的第一行包含两个整数n和x（1≤n≤105，1≤x≤109），分别是喜欢的数字和Rabbit希望移动的距离。

每个测试用例的第二行包含n个整数a1，a2，…，an（1≤ai≤109）—兔子最喜欢的数字。可以保证最喜欢的数字是不同的。

保证所有测试用例的n之和不超过105。

输出量 对于每个测试用例，请打印一个整数-所需的最小跃点数。

题解：

依次遍历每个喜欢的数字，如果等于需要移动的距离输出1，如果只有大于的输出2，如果都小于就分类讨论。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100014;
int a[maxn];
bool cmp (int a,int b) {
    return a>b;
}
int N,d;
int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&N,&d);
        for (int i=1;i<=N;i++) scanf("%d",&a[i]);
        sort(a+1,a+N+1,cmp);
        int ans=1e9;
        for (int i=1;i<=N;i++) {
            if (a[i]>d) ans=min(ans,2);
            if (a[i]==d) ans=1;
            if (a[i]<d) {
                ans=min(ans,(d+a[i]-1)/a[i]);
            }
        }
        printf ("%d
",ans);
    }
    return 0;
}
View Code

C.Cow and Message

牛贝西（Bessie）刚刚截获了农夫约翰（John Farmer）发给汉堡皇后（Burger Queen）的短信！但是，Bessie确信内部隐藏了一条秘密消息。

文本是小写拉丁字母的字符串s。如果t作为s的子序列（其索引形成算术级数）存在，则她认为字符串t隐藏在字符串s中。例如，字符串aab被隐藏在字符串aaabb中，因为它出现在索引1、3和5上，它们形成了算术级数，并且相差2。贝西认为任何出现次数最多的隐藏字符串都是秘密信息。 。如果索引集不同，则S的子序列的两次出现是不同的。帮助她找到秘密信息的发生次数！

例如，在字符串aaabb中，a被隐藏3次，b被隐藏2次，ab被隐藏6次，aa被隐藏3次，bb被隐藏1次，aab被隐藏2次，aaa被隐藏1次， abb隐藏1次，aaab隐藏1次，aabb隐藏1次，aaabb隐藏1次。秘密消息的出现次数是6。

输入值 第一行包含小写拉丁字母（1≤| s |≤105）的字符串s，这是Bessie截获的文本。

输出量 输出一个整数-秘密消息的出现次数。

题解：

出现次数最多的子串只可能是长度1或2的子串，开两个数组DP处理。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1014;
typedef long long ll;
ll a[maxn];
ll b[maxn][maxn];
string s;
int main () {
    cin>>s;
    for (int i=0;i<s.length();i++) {
        int c=s[i]-'a';
        for (int j=0;j<26;j++) 
            b[j][c]+=a[j];
        a[c]++;
    }
    ll ans=0;
    for (int i=0;i<26;i++) 
        ans=max(ans,a[i]);
    for (int i=0;i<26;i++) 
        for (int j=0;j<26;j++)
            ans=max(ans,b[i][j]);
    printf("%lld
",ans);
    return 0;
}
View Code

D.Cow and Fields

贝西正在农场放牧，该农场由n条通过m条双向道路连接的田地组成。她目前在第1场，将在一天结束时返回她在第n场的家。

谷仓母牛联合会已命令农夫约翰额外安装一条双向道路。该农场有k个特殊领域，他决定在两个不同的特殊领域之间安装道路。他可以在已经有直接连接它们的道路的两个特殊领域之间添加道路。

添加道路后，贝西将沿着从字段1到字段n的最短路径返回家中。由于贝西需要更多的运动，因此农夫约翰必须最大限度地增加这条最短路径的长度。救救他！

输入值 第一行包含整数n，m和k（2≤n≤2⋅105，n-1≤m≤2⋅105，2≤k≤n）-农场的田地数量，道路数量，以及特殊字段的数量。

第二行包含k个整数a1，a2，…，ak（1≤ai≤n）-特殊字段。所有的ai都是不同的。

接下来的m条线中的第i条包含整数xi和yi（1≤xi，yi≤n，xi≠yi），表示字段xi和yi之间的双向道路。

保证一个人可以到达其他任何领域。还可以保证，对于任何一对田地，最多只有一条道路将它们连接起来。

输出量 在Farmer John最佳安装一条道路后，输出一个整数，即从字段1到n的最短路径的最大可能长度。

题解：找两个特殊的点a，b，1到a的最短路径长度是x，N到b的最短路径是y，要使得1到N的最短距离最长，就必须使得x+y+1的长度最大，但是a和b在路径上的先后顺序是个问题。

a1+bn+1<=an+b1+1

a1+bn<=an+b1

a1-an<=b1-bn

推导得到这个公式，把所有的特殊结点按照这个顺序排序，再依次从前往后遍历选出最大的路径即可。如果本来的最短路径就不用经过特殊结点，就直接输出本来的最短路径。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+14;
int N,M,K,x,y;
vector<int> g[maxn];
int d[2][maxn];
int a[maxn];
int visit[maxn];
void bfs (int x,int st) {
    memset(visit,0,sizeof(visit));
    for (int i=1;i<=N;i++) 
        d[x][i]=1e9;
    queue<int> q;
    d[x][st]=0;
    visit[st]=1;
    q.push(st);
    while (!q.empty()) {
        int u=q.front();
        q.pop();
        for (int i=0;i<g[u].size();i++) {
            int v=g[u][i];
            if (visit[v]) continue;
            d[x][v]=d[x][u]+1;
            q.push(v);
            visit[v]=1;
        }
    }
}
int main () {
    scanf("%d%d%d",&N,&M,&K);
    for (int i=0;i<K;i++) {
        scanf("%d",&a[i]);
    }
    for (int i=0;i<M;i++) {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    bfs(0,1);
    bfs(1,N);
    int ans=0;
    vector<pair<int,int>> vi;
    for (int i=0;i<K;i++) {
        vi.push_back({d[0][a[i]]-d[1][a[i]],a[i]});
    }
    sort (vi.begin(),vi.end());
    int tmp=0;
    for (int i=0;i<vi.size();i++) {
        if (i!=0) ans=max(ans,tmp+d[1][vi[i].second]+1);
        tmp=max(tmp,d[0][vi[i].second]); 
    }
    printf ("%d
",min(ans,d[0][N]));
    return 0;
}
View Code

相关推荐