寒假学习计划

比赛地址

牛客

[G] 草莓2

题意

给出一个大小为nm的棋盘,每个位置有一定数量的草莓,一个人每天可以在早上采摘当前所处格子的草莓,在下午移动到相邻的四个格子中任何一个,在晚上每个格子都会长出来一个草莓.现在给出初始位置,求k天后最多能摘到多少草莓.

题解

题目中保证了nm为偶数,也就是欧拉回路一定存在.分情况讨论,当k时,爆搜, k > nm 时,按照欧拉回路走.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include <queue>
using namespace std;

int n, m, x, y;
long long int k, ans = 0, l[10][10], s[10][10];

long long int dfs(int x, int y, int d) {
    if (d == k) return 0;
    if (x == 0 || y == 0 || x == n+1 || y == m+1) return 0;
    long long int ret = 0;
    long long int now = l[x][y];
    long long int back = l[x][y];
    l[x][y] = 0;
    if (ret < dfs(x-1, y, d+1)) {
        ret = dfs(x-1, y, d+1);
    };
    if (ret < dfs(x+1, y, d+1)) {
        ret = dfs(x+1, y, d+1);
    };
    if (ret < dfs(x, y-1, d+1)) {
        ret = dfs(x, y-1, d+1);
    };
    if (ret < dfs(x, y+1, d+1)) {
        ret = dfs(x, y+1, d+1);
    };
    l[x][y] = back;
    now += ret;
    return now;
}

int main(){
    cin >> n >> m >> x >> y >> k;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%lld", &s[i][j]);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) l[i][j] = s[i][j];
    if (k >= n*m) {
        for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) ans += s[i][j];
        for (int i = 0; i < n*m; i++) ans += i;
        ans += 1LL * (k-n*m) * n*m;
    } else {
        for (int i = 0; i < k; i++) ans += i;
        ans += dfs(x, y, 0);
    }
    cout << ans << endl;
    int nowx = x, nowy = y;
    return 0;
}

[H] 游戏

题意

有1-n共n个数,每次可以随机选取2个数删去.假如删去的两个数互质,则得一分.当剩下的数少于两个时停止游戏.求得分的期望.

题解

其实是打表看出来的规律...

题目要求输出最简分数形式,答案最后的形式为\frac{\sum_{i=1}^{n}\phi(i)-1}{2\lfloor\frac{n}{2}\rfloor+1}

官方题解是,因为每一对数被选择到的概率相同,所以只需统计互质的数的对数.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 5010
#define INF 0x3f3f3f3f
using namespace std;

int n,i,x,y;
int p[N],phi[N],Sum[N],flag[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)    {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)  p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

inline int Gcd(int a,int b){return  (!b)?a:Gcd(b,a%b);}

inline void Ready(){
    LL i=0,j=0;
    phi[1]=1;
    for (i=2;i<=5000;i++){
        if (!flag[i])   {p[++p[0]]=i;   phi[i]=i-1;}
        for (j=1;j<=p[0] && i*p[j]<=5000;j++){
            flag[i*p[j]]=1;
            if (i%p[j]) phi[i*p[j]]=phi[i]*(p[j]-1);
            else {
                phi[i*p[j]]=phi[i]*p[j];    break;
            }
        }
    }
    for (i=1;i<=5000;i++)    Sum[i]=phi[i]+Sum[i-1];
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%d",&n);
    Ready();
    x=Sum[n]-1; y=(n-1)/2*2+1;
    cout<<x/Gcd(x,y)<<"/"<<y/Gcd(x,y)<<endl;

    return 0;
}

[K] 修炼

题意

玩家有两种能力,初始均为0.每一天开始的时候,可以给某一种能力加一次点.当天结束后,每种能力会产生等量的能力值.当两种能力值都比通关需求大的时候即视为通关.问最快几天通关.

题解

假设n天通关,那么通关时能力值的总和一定是\frac{n(n+1)}{2}.问题在于是否有一种分配方案可以满足通关需求.

其实拿数学归纳法不难证明,从1-n这n个数抽出一个子集,可以组合出1到\frac{n(n+1)}{2}中的任何一个数.然后就只需要二分n了.

代码

#include <iostream>
#include <algorithm>

#define LL long long

using namespace std;
constexpr int MN(1e4);

LL a1, a2, b1, b2;

#define check(ans) \
    ({ \
        LL d1 = b1 - ans*a1; \
        LL d2 = b2 - ans*a2; \
        ans*(ans+1)/2 >= (d1 < 0 ? 0 : d1) + (d2 < 0 ? 0 : d2); \
    })

int main()
{
    int n;
    LL ans[MN];
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> a1 >> a2 >> n;

    for (int i=0; i<n; ++i)
    {
        cin >> b1 >> b2;
        LL L = 0, R = 1e7, m;
        while (L <= R)
        {
            m = (L+R) >> 1;
            if (check(m))
                R = m - 1;
            else
                L = m + 1;
        }
        ans[i] = L;
    }
    cout << *min_element(ans, ans+n);
}