Mashup-Math_Topic_One

Tutorial and Introspection

A Rudolf and 121

注意到第 $1$ 位只能被第 $2$ 位影响，以此类推位置，对于 $a_i$ , 如果 $<0$ ，不合法 ; 否则，$a_i-=a_i,a_{i+1}-=2\ast a_i,a_{i+2}-=a_i$

操作到最后再检查一下 $n-1$ 跟 $n$ 这两个位置

void solve(){cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];}for(int i = 1; i <= n - 2; i ++){if(a[i] == 0){continue;}else if(a[i] < 0){cout << "NO\n";return ;}else{int tmp = a[i];a[i] -= tmp;a[i + 1] -= 2 * tmp;a[i + 2] -= tmp;}}if(a[n] == 0 && a[n - 1] == 0){cout << "YES\n";}else{cout << "NO\n";}
}

Divisible Pairs

这题主要考察对取模的理解

$a+b$ mod x = 0, 即 $a+b=p\ast x$ , 所有数对 $x$ 取模，a%=x,b%=x , 得$a+b=0orx$

$a-b$ mod x = 0, 取模 x, 即 a=b

一边读入一边计算，不会重复计算

void solve(){int n, x, y, res = 0;cin >> n >> x >> y;map<pair<int, int>, int> mp;for(int i = 1; i <= n; i ++){int tmp;cin >> tmp;if(mp.count({x - tmp % x, tmp % y})){res += mp[{x - tmp % x, tmp % y}];}else if(mp.count({-tmp % x, tmp % y})){res += mp[{-tmp % x, tmp % y}];}mp[{tmp % x, tmp % y}] ++;}cout << res << '\n';
}

Anna and the Valentine’s Day Gift

如果 $x\ge 10^m$ , 在 $x$ 没有前导零的情况下, 只需要 $x$ 的长度为 $m+1$ 即可，知道这个性质贪心两边操作即可

(萨沙不需要最大化最终的数字，只要最大化数字的位数即可。)

void solve(){int n, m, res = 0;cin >> n >> m;vector<int> a(n + 5), c(n + 5);for(int i = 1; i <= n; i ++){cin >> a[i];res += to_string(a[i]).size();}auto check = [](int x) -> int{string tmp = to_string(x);int sz = tmp.size(), i = sz - 1;while(tmp[i] == '0') i --;return sz - i - 1;};sort(a.begin() + 1, a.begin() + n + 1, [&](int x, int y) -> bool{return check(x) > check(y);});for(int i = 1; i <= n; i += 2){res -= check(a[i]);}cout << (res >= m + 1 ? "Sasha" : "Anna") << '\n';
}

Physical Education Lesson

如果位置 $n$ 的人报数为 $x$ , 队伍长为 $k$ , 不难发现

$n=(2k-2)\ast t+x$ , $t\in [0,\lfloor \frac{n-x}{2k-2}\rfloor ]$

或 $n=(2k-2)\ast t+k+k-x$ , 即 $t\in [1,1+\lfloor \frac{n+x-2}{2k-2}\rfloor ]$

对 $n-x$ 和 $n+x-2$ 分解因子，留下偶数因子对应的 $k$ 插入 $set$ 集合当中，

最后检查所有 $k>=x$ 的合法解数量

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, x;
void solve(){set<int> s;cin >> n >> x;/*n = (2k-2)*t + xn-x = (2k-2)*tn = (2k-2)*t + k + k - xn + x - 2 = (2k-2) * tk < n*//*num = a * b*/auto op = [&](int num){set<int> tmp = set<int> ();for(int i = 1; i * i <= num; i ++){if(num % i == 0){if(i % 2 == 0) tmp.insert(i);if((num / i) % 2 == 0) tmp.insert(num / i);}}for(auto x : tmp){s.insert(x / 2 + 1);}};op(n - x);op(n + x - 2);int res = 0;for(auto k : s){if(k >= x){res ++;}}cout << res << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T --){solve();}return 0;
}
/*10 22356n-x=8, 2 4 8               2 3 5n+x-2=10 2  10
*/

Eat the chip

纵向距离决定谁吃谁，然后进行模拟，被吃者逃离，捕食者靠近，$O(h)$

实际存在 $O(1)$ 做法就能判断，这里不做深究

#include<bits/stdc++.h>
using namespace std;
#define int long long// void solve(){
// 	int h, w, x1, y1, x2, y2;
// 	cin >> h >> w >> x1 >> y1 >> x2 >> y2;
// 	auto out = [](int op){
// 		if(op == 1) cout << "Alice\n";
// 		else if(op == 2) cout << "Bob\n";
// 		else cout << "Draw\n";// };// if(x1 >= x2){// 	out(3);// }
// 	else{
// 		int dis = abs(y1 - y2);
// 		if(dis <= 1){
// 			if(abs(x1 - x2) % 2){
// 				out(1);
// 			}
// 			else{
// 				out(2);
// 			}
// 		}
// 		else{
// 			out(3);
// 		}
// 	}
// }
/*获胜条件 : 当被捕食者进入攻击区域时，捕食者通过之前的操纵使得两者距离之差不超过 3除非距离间隔为 1, 捕食者直接发起进攻否则被捕食者一定
*/
/*如果两者距离为 0, 捕食者不改变, 否则，捕食者令距离减 -1;被捕食者一定要让距离 + 1捕食者先手, 而被捕食者进入判定区域时先手假设横向距离为 3，纵向距离为 51 : 22 : 33 : 24 : 3h <= 1e6即纵向的距离, 显然题目比较善良，让我们通过 O(h) 而非 O(1)的操作完成题目那么就可以通过模拟解决了
*/
void solve(){int h, w, x1, y1, x2, y2;cin >> h >> w >> x1 >> y1 >> x2 >> y2;auto out = [](int op){if(op == 1) cout << "Alice\n";else if(op == 2) cout << "Bob\n";else cout << "Draw\n";};// 计算横向距离auto dis = [&] () -> long long {return abs(y1 - y2);};// a 远离 bauto a_away_b = [&] () -> void {for(int i = -1; i <= 1; i ++){int tmp = y1 + i;if(tmp >= 1 && tmp <= w && abs(tmp - y2) >= dis()){y1 = tmp;}}};auto a_in_b = [&] () -> void {for(int i = -1; i <= 1; i ++){int tmp = y1 + i;if(tmp >= 1 && tmp <= w && abs(tmp - y2) <= dis()){y1 = tmp;}}};auto b_away_a = [&] () -> void {for(int i = -1; i <= 1; i ++){int tmp = y2 + i;if(tmp >= 1 && tmp <= w && abs(tmp - y1) >= dis()){y2 = tmp;}}};auto b_in_a = [&] () -> void {for(int i = -1; i <= 1; i ++){int tmp = y2 + i;if(tmp >= 1 && tmp <= w && abs(tmp - y1) <= dis()){y2 = tmp;}}};if(x1 >= x2){out(3);}else{// 进入判定区域的时候，结局就已经注定了if((x2 - x1) % 2 == 1){ // A 吃 Bfor(int i = 1; i <= x2 - x1 - 1; i ++){if(i & 1){a_in_b();}else{b_away_a();}}if(abs(y1 - y2) <= 1) out(1);else out(3);}else{ // B 吃 Afor(int i = 1; i <= x2 - x1 - 1; i ++){if(i & 1){a_away_b();}else{b_in_a();}}if(abs(y1 - y2) <= 1) out(2);else out(3);}}}
signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T --){solve();}return 0;
}
// 每次移动改变两棋子之间的横向距离 dis_x 和纵向距离 dis_y
// 先手到达 dis_x = 0 且 dis_y = 0 的玩家获胜
// 如果无人取胜，平局。
// 每次操作，纵向距离必然 -1
// 如果两者距离为奇数, 必然是 A 尝试吃掉 B 或者平局
// 如果两者距离为偶数，必然是 B 尝试吃掉 A 或者平局

Increasing Subsequences

题解写的很好

让我们来看看构建所需数组的解决方案之一。

假设数组 $a$ 有 $x$ 个递增子序列。如果我们在数组末尾添加一个新的最小值，那么新数组中的递增子序列数等于 $x+1$ （因为新元素不会与其他元素形成递增子序列）。(由于新元素不会与其他元素形成递增子序列，因此只会添加由该元素组成的子序列）。如果我们在数组的末尾添加一个新的最大值，那么新数组中的递增子序列数等于 $2x$ （因为新元素与其他元素形成递增子序列）。

利用上述事实，我们来定义一个递归函数 $f(x)$ ，它返回的数组恰好有 $x$ 个递增子序列。对于奇数值 $x$ ，返回 $f(x)=f(x-1)+min$ （这里的 + 表示在数组末尾添加一个元素）；对于偶数值 $x$ ，返回 $f(x)=f(\frac{x}{2})+max$ 。现在我们需要估算通过这种算法得到的数组中的元素个数。需要注意的是，第一种类型（ $x\to x-1$ ）不能有两次连续的运算，因此每两次运算， $x$ 的值至少减少两次。因此，数组的大小满足 $200$ 的限制。

#include<bits/stdc++.h>
using namespace std;
#define int long longvector<int> f(int x){vector<int> res;if(x == 2){res.push_back(0);}else if(x & 1){res = f(x - 1);res.push_back(*min_element(res.begin(), res.end()) - 1);}else{res = f(x / 2);res.push_back(*max_element(res.begin(), res.end()) + 1);}return res;
}void solve(){int x;cin >> x;auto res = f(x);cout << res.size() << '\n';for(auto a : res) cout << a << ' ';cout << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T --){solve();}return 0;
}