CF678

CFEDU 13

[A. Johny Likes Numbers](http://codeforces.com/contest/678/problem/A)思路。代码 [B. The Same Calendar](http://codeforces.com/contest/678/problem/B)思路代码dalao做法 [C. Joty and Chocolate](http://codeforces.com/contest/678/problem/C)思路代码 [D. Iterated Linear Function](http://codeforces.com/contest/678/problem/D)思路代码大佬做法 [E. Another Sith Tournament](http://codeforces.com/contest/678/problem/E)思路；代码

A. Johny Likes Numbers

思路。

找第一个大于n的整除k的数， 会发现， 他等于n 整除k + 1 在乘k。 输出即可。

代码

// // main.cpp // CF678 edu13 // // Created by 陈博 on 2020/10/8. // #include <iostream> using namespace std; int n, k; int main() { cin >> n >> k; cout << (long long)k * ((n / k) + 1) << endl; return 0; }

B. The Same Calendar

思路

从n+1年开始枚举， 并判断； 对于当前年i， 首先判断他的平闰年是否和n年相同。 然后对于第二个条件， 其实就是判断从n年到i年的天数是否整除7. 如果这两个条件都符合， 直接输出即可。

代码

// // main.cpp // B // // Created by 陈博 on 2020/10/8. // #include<bits/stdc++.h> using namespace std; int n; int days = 0; bool judge(int x) { if((x % 4 == 0 && x % 100 != 0) || x % 400 == 0) { return true; } return false; } int calc(int now) { if(judge(now)) { return 366; } else { return 365; } } bool flag; int main() { cin >> n; flag = judge(n); n++; for(;;n++) { days += calc(n-1); if(days % 7 == 0 && judge(n) == flag) { cout << n << endl; break; } } return 0; }

dalao做法

大佬直接维护天数%7变成每年的第一天是星期几，在算出n年的第一天是星期几， 并根据这个判断 具体算法见代码

#include <bits/stdc++.h> using namespace std; typedef long long LL; int isleap(int y) { if (y % 100 == 0) { return y % 400 == 0; } return y % 4 == 0; } int main() { int n; cin >> n; int w = 1; for (int i = 2016 ; i > 1000 ; -- i) { if (isleap(i)) { w -= 366 % 7; } else { w -= 365 % 7; } w += 7 , w %= 7; } for (int i = 1001 ; i <= n ; ++ i) { w += isleap(i) + 365; w %= 7; } int p = w; int q = isleap(n); int j = n + 1; while (1) { w += isleap(j) + 365; w %= 7; if (w == p && isleap(j) == q) { printf("%d\n" , j); break; } ++ j; } }

C. Joty and Chocolate

思路

如果他要让获得最大的巧克力数尽量多的话， 那么，应该让刷一个格子获得颜色多的尽量多刷， 所以 ， 我们就可以尽量多刷获得巧克力多的， 然后，再加上获得巧克力少的 ， 最后， 因为有重复 所以再减去他们的最小公倍数刷的格子获得的少的巧克力。

代码

// // main.cpp // C // // Created by 陈博 on 2020/10/8. // #include<bits/stdc++.h> using namespace std; typedef long long ll; ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); } ll n, a, b, p, q; int main() { cin >> n >> a >> b >> p >> q; ll c = a * b / gcd(a, b); ll na = n / a; ll nb = n / b; ll nc = n / c; cout << (ll)na * p + (ll)nb * q - (ll)nc * min(p, q) << endl; return 0; }

你也可以先算出刷红格子与蓝格子同时不算他们的最小公倍数的格子， 然后再加上他们最小公倍数的格子乘上刷红或蓝中获得巧克力的格子。

#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { LL n , a , b , p , q; cin >> n >> a >> b >> p >> q; LL A = n / a , B = n / b , c = a / __gcd(a , b) * b; LL C = n / c; A -= C , B -= C; cout << A * p + B * q + max(p , q) * C << endl; }

D. Iterated Linear Function

思路

$$g^{(0)}(x)=x$$$$g^{(1)}(x)=Ax+B$$$$g^{(2)}(x)=A^{2}x+AB+B$$$$g^{(3)}(x)=A^{3}x+A^{2}B+AB+B$$$$........$$ 由此可以推出：$g^{(n)}(x)=A^{n}x+A^{n-1}B+A^{n-2}B+....+AB+B$ 提公因式得: $A^{n}x+B\times (A^{n-1}+A^{n-2}+....+A+1)$ 根据等比数列公式得：$A^{n}x+\frac{A^n-1}{A-1}B=g^{(n)}(x)$ 求即可。 注意特判A == 1时， 答案等于$1+B\times n$

代码

// // main.cpp // D // // Created by 陈博 on 2020/10/8. // #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll A, B, n, x; ll ksm(ll a, ll b) { ll res = 1; while(b) { if(b & 1) { res = res * a % mod; } b = b >> 1; a = a * a % mod; } return res; } int main() { cin >> A >> B >> n >> x; ll ans = 0; ans = (ans + ksm(A, n) * x % mod) % mod; //cout << ans << endl; if(A == 1) { ans = (ans + n % mod * B % mod) % mod; cout << ans << endl; return 0; } ans = (ans + (ksm(A, n) - 1) * B % mod * ksm((A-1), mod-2) % mod) % mod; cout << ans << endl; return 0; }

大佬做法

矩阵乘法优化dp 首先写出递推式$dp[i]=A\times dp[i-1]+B$ 然后构造矩阵方程：$$\left(\begin{array}{cc}& \\ & \end{array}\right)\times \left(\begin{array}{c}dp[i]\\ dp[i-1]\end{array}\right)=\left(\begin{array}{c}dp[i+1]\\ dp[i]\end{array}\right)$$很容易得出里面的矩阵应为$\left(\begin{array}{cc}A& B\\ 1& 0\end{array}\right)$, 那么只要用矩阵快速幂将这个矩阵乘上n-1次并乘初始矩阵即可。

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int Q = 1e9 + 7; struct Matrix { int n , m , a[2][2]; Matrix (int _n = 0, int _m = 0) { n = _n , m = _m; memset(a , 0 , sizeof(a)); } Matrix operator * (const Matrix &R) const { Matrix res(n , R.m); for (int i = 0 ; i < n ; ++ i) { for (int j = 0 ; j < m ; ++ j) { for (int k = 0 ; k < R.m ; ++ k) { res.a[i][k] += (LL)a[i][j] * R.a[j][k] % Q; res.a[i][k] %= Q; } } } return res; } }; int main() { LL A , B , n , x; cin >> A >> B >> n >> x; Matrix I(1 , 2); I.a[0][0] = x , I.a[0][1] = 1; Matrix P(2 , 2); P.a[0][0] = A; P.a[1][0] = B; P.a[1][1] = 1; while (n) { if (n & 1) { I = I * P; } P = P * P; n >>= 1; } cout << I.a[0][0] << endl; }

E. Another Sith Tournament

思路；

设f[s]表示当前状态下获胜的最大概率 状压， s中每一位表示每个骑士， 0表示被淘汰， 1表示存在。 转移方程为。$$f[s]=maxsize(f[s\oplus (1<<j)]\times a[i][j]+f[s\oplus (1<<j)\times a[j][i])$$

代码

// // main.cpp // E // // Created by 陈博 on 2020/10/8. //想出状压来了， 可惜没有成功的设计出状态转移方程， 后借鉴题解并自我编写代码 #include <iostream> using namespace std; int n; double dp[1 << 19]; double a[20][20]; int main() { cin >> n; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { cin >> a[i][j]; // cout << a[i][j] << " "; } //cout << endl; } //cout << "ok" << endl; dp[1] = 1; for(int i = 2; i <= (1 << n) - 1; i++) { if((i & 1) == 0) { dp[i] = 0; continue; } for(int j = 0; j <= n-1; j++) { for(int k = j+1; k <= n-1; k++) if(i & (1<<j) && i & (1 << k)) { dp[i] = max(dp[i ^ (1 << j)] * a[k+1][j+1] + dp[i^(1 << k)] * a[j+1][k+1], dp[i]); } } } printf("%.6lf\n", dp[(1 << n) - 1]); return 0; }