2020-02-19 06:27 山东大学 Java

关注

codeforces1307解题报告

A. Cow and Haybales

【题意】

给出一个长度为n的数列，每次操作可以将相邻的两个数字，其中一个-1，另外一个+1。

问K次操作后1位置的数最大为多少。

【思路】

直接把操作转化为对与第i个位置，花费 $i-1$ 的步数向1号位置转移个1。最后1号位置的最大值。

贪心的从左往右考虑，每次可以转移的1的个数为 $min(a_i,\lfloor \frac{now}{i-1}\rfloor)$ ，now是当前剩余的步数。

【代码】

#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 a[N];
int main() {
    int T = read();
    while(T--) {
        int n = read(),d = read();
        for(int i = 1;i <= n;++i) {
            a[i] = read();

            if(i == 1) continue;
            int k = min(d / (i - 1),a[i]);
            d -= k * (i - 1);
            a[1] += k;
        }
        printf("%d\n",a[1]);
    }

    return 0;
}

B. Cow and Friend

【题意】

给出n个喜欢的距离，每次可以移动一个喜欢的距离（欧几里得距离），问从 $(0,0)$ 走到 $(x,0)$ 最少需要多少步。

【思路】

特判 $x$ 为喜欢的距离的情况。

每次走最大的距离为最优方案。因为用mx走两步可以走出 $[0,2mx]$ 中的任何一个距离。

所以输出 $\lceil \frac{x}{mx}\rceil$ 即可。

对于 $mx > x$ 的情况，在排除上面特判的情况下，走一步肯定是不行的，所以也要特判输出2

【代码】

#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;
}
void solve() {
    ll mx = 0,n = read(),X = read();
    int flag = 0;
    for(int i = 1;i <= n;++i) {
        ll x = read();
        mx = max(mx,x);
        if(x == X) flag = 1;
    }
    if(flag) {puts("1");return;}

    if(mx > X) puts("2");
    else printf("%I64d\n",(mx + X - 1) / mx);
}
int main() {
    int T = read();
    while(T--) {
        solve();
    }

    return 0;
}

C. Cow and Message

【题意】

给出一个长度为n的字符串，可以选择一个下标集合 $S$ ，使得S中的数字为等差数列。问所有可能的S所对应的字符串中，出现次数最多的那个出现了多少次。

【思路】

脑筋急转弯，题面具有很大迷惑性。

其实选择最优情况肯定满足 $|S|=2$ 或者 $|S|=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 = 1000010;
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];
ll ans[30][30],cnt[30];
int main() {
    scanf("%s",s + 1);
    int n = strlen(s + 1);
    for(int i = 1;i <= n;++i) {
        for(int j = 0;j < 26;++j)
            ans[s[i] - 'a'][j] += cnt[j];    
        cnt[s[i] - 'a']++;
    }
    ll anss = 0;
    for(int i = 0;i < 26;++i) {
        for(int j = 0;j < 26;++j)
            anss = max(anss,ans[i][j]);
        anss = max(anss,cnt[i]);
    }

    cout<<anss;
    return 0;
}

D. Cow and Fields

【题意】

给出一个n个点m条边的无向图。边权均为1。再给出K个点，从这个K个点中选2两个连边，使得形成的图最短路最长。

【思路】

看到最短路最长容易误解为二分答案。

但稍微思考就会发现答案可定小于等于原图的最短路。

考虑 $n^2$ 的做法，枚举两个点 $(u,v)$ ，然后在之间连边。算出 $min(dist(1,u)+dist(v,n) + 1,dist(1,v)+dist(u,n) + 1)$

$dist(i,j)$ 表示从 $i$ 到 $j$ 的最短路。

所以求一下从1到每个点的最短路dis1,和从n到每个点的最短路dis2。

然后找到dis1和dis2的最大值相加？？？

显然不行，因为无法排除自己加自己的情况，而且无法解决 $n^2$ 做法中min起到的作用。

这里要用到类似与"国王游戏"中的贪心方法（拟阵）。

如果dis1[u]+dis2[v] < dis2[u] + dis1[v]说明u选dis1更小，就按照这个方式排个序。

然后从左向右枚举，左边的选dis1，右边的选dis2，统计即可。

【代码】

#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;
}
struct node {
    int v,nxt;
}e[N << 1];
int a[N],head[N],ejs;
void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
queue<int>q;


void bfs(int S,int *dis) {
    q.push(S);
    while(!q.empty()) {
        int u = q.front();q.pop();
        for(int i = head[u];i;i = e[i].nxt) {
            int v = e[i].v;
            if(!dis[v] && v != S) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
}

int dis1[N],dis2[N];
bool cmp(int x,int y) {
    return dis1[x] + dis2[y] < dis2[x] + dis1[y];
}
int main() {
    int n = read(),m = read(),K = read();
    for(int i = 1;i <= K;++i) a[i] = read();
    for(int i = 1;i <= m;++i) {
        int u = read(),v = read();
        add(u,v);add(v,u);
    }

    bfs(1,dis1);    
    int ans = dis1[n];
    bfs(n,dis2);
    sort(a + 1,a + K + 1,cmp);

    int now = dis1[a[1]],tmp = 0;

    for(int i = 2;i <= K;++i) {
        int x = a[i];

        tmp = max(tmp,dis2[x] + now + 1);
        now = max(now,dis1[x]);
    }

    now = dis2[a[K]];
    for(int i = K - 1;i >= 1;--i) {
        int x = a[i];
        tmp = max(tmp,dis1[x] + now + 1);
        now = max(now,dis2[x]);
    }

    ans = min(ans,tmp);
    printf("%d\n",ans);
    return 0;
}