A. Function Height
由于只能提升(x)为奇数的点，每个三角形的底一定为(2)， 则要求我们求：
(2 * (h_1 + h_2 + … + h_n) / 2 = k)，使(max(h_1, h_2…h_n))最小。
则应使每个(h)平摊重量，答案即为(lceil n/k ceil)。
#include <cstdio>
#include <iostream>
#include <cmath>
typedef long long LL;
using namespace std;
LL n, k;
int main(){
cin >> n >> k;
cout << ((k % n) ? k / n + 1 : k / n );
return 0;
}
B. Diagonal Walking v.2
设(a = min(n, m), b = max(n, m))
(b > k)，即使每次最大移动，也不能到达终点。
首先使点移动到((a, a))，剩下移动(b - a) 次即可到目标，可以考虑交叉移动的方式，但交叉移动必须符合偶数次才行，所以如果不能偶数次，就令(k) 少两次机会，让(b - a) 与 (k - a) 的奇偶性一致。
最后如果(b - a) 为奇数，则会少交叉移动一次，最终答案会$ - 1$。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
int q;
int main(){
scanf("%d", &q);
while(q--){
LL n, m, k, ans; cin >> n >> m >> k;
if(max(n, m) > k) puts("-1");
else{
if((abs(n - m) & 1) == 0 && (k - min(n, m)) & 1)
n--, m--, k-=2;
ans = min(n, m); k -= min(m, n);
if(abs(m - n) & 1) ans += k - 1;
else ans += k;
cout << ans << endl;
}
}
return 0;
}
C. Classy Numbers
不会数位(dp)，看了dalao的题解理解了一些
设计一个(dfs(pos, st, limit))
表示处理(pos)位数，已经有(st)个非(0)位（最多3位），有(limit)限制代表在求最高限度是(a[pos])下多少个，无限制则最高可填到(9)。
-
依次从高到低考虑每一位可以填哪些数（(0 - 9)）
-
若为(0)，则已经(st)不变
-
若为其他数字，必须保证当前(st < 3)才可选择
-
若选择与(a[pos])相同的数字，则下一次也需限制选择数字的大小
由于多组数据，若没有限制，可以记忆化搜索，极大增加效率。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
int a[20];
LL dp[20][5];
LL dfs(int pos, int st, bool limit){
if(pos == -1) return 1;
if((!limit) && dp[pos][st]) return dp[pos][st];
int up = limit ? a[pos] : 9;
LL res = 0;
for(int i = 0; i <= up; i++){
if(!i) res += dfs(pos - 1, st, limit && i == a[pos]);
else if(st != 3) res += dfs(pos - 1, st + 1, limit && a[pos] == i);
}
if(!limit) dp[pos][st] = res;
return res;
}
LL work(LL x){
int tot = 0;
while(x) a[tot++] = x % 10, x /= 10;
return dfs(tot - 1, 0, true);
}
int main(){
int T; scanf("%d", &T);
while(T--){
LL l, r; cin >> l >> r;
cout << work(r) - work(l - 1) << endl;
}
return 0;
}
D. Vasya and Arrays
(Two-Pointer)算法，尝试前几项能否堆起来。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 300010;
int n, m, ans = 0;
LL a[N], b[N];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%lld", a + i), a[i] += a[i - 1];
scanf("%d", &m);
for(int i = 1; i <= m; i++) scanf("%lld", b + i), b[i] += b[i - 1];
if(a[n] != b[m]) puts("-1");
else{
int i = 1, j = 1;
while(true){
if(i > n || j > m) { puts("-1"); break; }
while(a[i] < b[j]){
if(i + 1 > n) { puts("-1"); return 0; }
i++;
}
while(a[i] > b[j]){
if(j + 1 > m){ puts("-1"); return 0; }
j++;
}
if(a[i] == b[j]){
i++, j++, ans++;
if(i == n + 1 && j == m + 1) { printf("%d
", ans); break; }
}
}
}
return 0;
}