首页 > 代码库 > Codeforces Round #258 (Div. 2)

Codeforces Round #258 (Div. 2)

2024-07-13 01:47:12   221人阅读

A - Jzzhu and Children

找到最大的ceil(ai/m)即可

#include <iostream>#include <cmath>using namespace std;int main(){    int n,m;    cin >> n >> m;    double a, maxv = 0;    int maxIdx = 0;    for(int i = 0; i < n; ++ i){        cin >> a;        if(maxv <= ceil(a/m)){            maxv = ceil(a/m);            maxIdx = i+1;        }    }    cout<<maxIdx<<endl;}
View Code

B - Jzzhu and Sequences

fi = fi-1-fi-2

f1=x, f2=y, f3=y-x, f4 = y-x-y = -x, f5 = -x-(y-x) = -y , f6 =-y-(-x) = x-y

f7 = x-y-(-y)=x, f8 = x-(x-y) = y...........

注意该序列的循环节是6

只要算出前六个数即可。

#include <iostream>#include <vector>#define ll long long#define MOD 1000000007using namespace std;int main(){    ll x,y,n;    cin >> x >> y >> n;    vector<ll> f(6,0);    f[0] =x;f[1]=y;    for(int i = 2; i < 6; ++ i) f[i] = f[i-1]-f[i-2];    cout<<(f[(n-1)%6]%MOD+MOD)%MOD<<endl;}
利用循环节

本题也可以采用矩阵快速幂运算

#include <iostream>#include <vector>#include <algorithm>#include <string>#include <queue>#include <utility>#define ll long long#define MOD 1000000007using namespace std;struct matrix{    ll m[2][2];}ans, base;matrix multi(matrix a, matrix b){    matrix tmp;    for(int i = 0; i < 2; ++i)    {        for(int j = 0; j < 2; ++j)        {            tmp.m[i][j] = 0;            for(int k = 0; k < 2; ++k)                tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]);        }    }    return tmp;}ll fast_mod(ll n,ll x,ll y){    base.m[0][0] = 1;    base.m[0][1] = -1;    base.m[1][0] = 1;    base.m[1][1] = 0;    ans.m[0][0] = ans.m[1][1] = 1;    ans.m[0][1] = ans.m[1][0] = 0;    while(n)    {        if(n & 1)        {            ans = multi(ans, base);        }        base = multi(base, base);        n >>= 1;    }    return ans.m[0][0]*y+ans.m[0][1]*x;}int main(){    ll x,y,n;    cin >> x >> y >> n;    ll res = 0;    if(n == 1) res = x;    else if(n == 2) res = y;    else res = fast_mod(n-2,x,y);    if(res < 0) res = res%MOD;    cout<<(res+MOD)%MOD<<endl;}
矩阵快速幂运算

注意结果输出时对负数要 (res%mod+mod)%mod，因为res可能大于mod， 不然结果可能被cha掉

C - Jzzhu and Chocolate

题目的意思：

　　给nxm的巧克力，切k刀后，求最小块巧克力的最大面积

解题思路：

　　可以假设n<m，如果n>m，则交换n和m。

　　现在将行分成x行，列分成y列，相当于行切x-1次，列切y-1次，x-1+y-1=k 即x+y=k-2，

　　此时最小块面积是floor(n/x)*floor(m/y),要使最小块面积最大，即使x*y尽量小。

　　x*y=x(k-2-x) = -x2+(k-2)x，这是一个开头向下的抛物线，抛物线中间值最大，要是值x*y最小，x必须在抛物线的两边，x在0这边或者k这边。

　　现在分情况考虑

　　（1）如果k<n，这最优的(x,y)，是{x=1,y=k+1}（列切k次）或者{x=k+1, y=1}(行切k次)

　　（2）如果n≤k<m，这最优的(x,y)，是{x=1,y=k+1}(列切k次)

　　（3）如果m≤k≤n+m-2，最优的(x,y)，是{x=k+2-m,y=m}(行切k+1-m次，列切m次)

　　（4） 如果 k>n+m-2，则不存在切割方法（行最多切n-1次，列最多切m-1次）

#include <iostream>#include <vector>#include <algorithm>#include <string>#define ll long longusing namespace std;int main(){    ll n,m,k;    cin >> n >> m >>k;    if(n > m) swap(n,m);    if(k < n) cout<<max(n*(m/(k+1)),n/(k+1)*m)<<endl;    else if(k>=n && k < m) cout<<n*(m/(k+1))<<endl;    else if(k>=m && k <= n+m-2) cout<<n/(k+2-m)<<endl;    else cout<<-1<<endl;}
View Code

D - Jzzhu and Cities


联系
我们