首页 > 代码库 > Codeforces Round #258 (Div. 2)
Codeforces Round #258 (Div. 2)
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;}
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;}
D - Jzzhu and Cities
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。