题意 给出一个数组，把这个数组中的元素分成两部分，使得每一部分的和都是奇数或者都是偶数，问能不能分
思路 直接判断整个数组的元素和是奇数还是偶数，如果是奇数直接输出NO，偶数直接输出YES，因为奇数=奇数+偶数，偶数既可以等于偶数加偶数，也可以等于奇数加偶数
代码 #include <bits/stdc++.h> using namespace std;void solve () int n; cin >> n; i64 sum = 0 ; for (int i = 0 ; i < n; i ++ ) { int x; cin >> x; sum += x; } if (sum % 2 == 0 ) cout << "YES\n" ; else cout << "NO\n" ; } int main () ios::sync_with_stdio (false ); cin.tie (0 ), cout.tie (0 ); int t; cin >> t; while (t -- ) { solve (); } }
题意 给出一个数x，位数从右到左，可以选择k进行操作，每轮操作如下;
如果第k-1个位置>=5，那么将第k个位置的数加1
如果在操作前第k个位置就是9，那么将其前面第一个小于9的数直接加1
上述两操作完成后，将第k位后面的所有数字都变成0
问经过操作使得原来的x可能变为的最大值是多少
思路 这题好难理解，读题花了我半天，题目读不懂的时候要崩溃
自己写的代码太复杂，这里参考了蒋老师的，大佬的思路好清晰TAT
大概步骤就是，存字符一样倒着存x，定义一个flag标记进位，k记录最后一位进位的位置，然后从第一项开始遍历，一旦遇到加上进位大于等于5的数就更新flag和k，遇到小于5的就把进位情况加上，然后恢复进位flag为false
然后将所有在最后一位进位的位置k后的数字全部标注成0，如果此时还有进位就把第一位从0标记成1，然后输出即可
代码 #include <bits/stdc++.h> using namespace std;typedef pair<int , int > PII;using i64 = long long ;void solve () string s; cin >> s; vector<char > ss (s.size() + 1 ) ; for (int i = 0 ; i <= s.size (); i ++ ) { ss[i] = s[s.size () - 1 - i]; } ss[s.size ()] = '0' ; bool flag = false ; int k = -1 ; for (int i = 0 ; i < s.size (); i ++ ) if (ss[i] + flag >= '5' ) { k = i; flag = true ; } else { ss[i] += flag; flag = false ; } for (int i = 0 ; i <= k; i ++ ) ss[i] = '0' ; if (flag) ss[s.size ()] = '1' ; for (int i = s.size () - 1 + flag; i >= 0 ; i -- ) cout << ss[i]; cout << '\n' ; } int main () ios::sync_with_stdio (false ); cin.tie (0 ), cout.tie (0 ); int t; cin >> t; while (t -- ) { solve (); } }
题意 在数组a中选择任意两个个数的所有组合中，把两个数里较小的数形成数组b，现在给出数组b，求可能的一种数组a
思路 （怎么感觉这题比上一题简单！
先用个例子模拟我的思路过程——
数组b：7 5 3 5 3 3
统计每个数字出现的次数，按照数字从小到大排序，得到：
首先明确一点，在数组b中出现过的数字一定会在数组a中出现（因为数组b就是数组a中的元素组成的，这个应该很好理解）
从大到小看，7出现了1次，这1次是怎么得到的呢，一定是数组a中大于等于7的这一部分得到的（因为只要小于7，被保留到b中的数字就不会是7了）
我们设数组a中大于等于7的数字有n个，在这n个数字中两两组合，得到了数组b中的1个7，所以 $C_n^2=1$，也就是 $\frac{n*(n-1)}{2}=1$ ，解得 $n=2$，也就是数组a中有2个数字大于等于7，（我们为了方便全部取7），把2个7存到数组a里
然后看第二个数5,数字5出现了2次，这2次一定是数组a中大于等于5的部分得到的
我们设数组a中大于等于5的数字有n个，在这n个数字中两两组合，得到了数组b中的2个5，所以 $C_n^2=2$，也就是 $\frac{n*(n-1)}{2}=2$ ，解得 $n=3$，也就是数组a中有3个数字大于等于5，我们的数组a现在是{7,7}，已经有两个数字比5大了，所以再增加一个大于等于5的数字即可，（为了方便再加进去一个5）
然后看第三个数3,数字3出现了3次，这3次一定是数组a中大于等于3的部分得到的
我们设数组a中大于等于3的数字有n个，在这n个数字中两两组合，得到了数组b中的3个3，所以 $C_n^2=3$，也就是 $\frac{n*(n-1)}{2}=3$ ，解得 $n=4$，也就是数组a中有4个数字大于等于3，我们的数组a现在是{7,7,5}，已经有3个数字比3大了，所以再增加一个大于等于3的数字即可，（为了方便再加进去一个3）
然后…结束了啊，输出a就可以啦
具体实现步骤如下：
统计b中每个数字出现的次数（用map统计，map的key代表数字的值，value代表数字出现的次数）（正好map可以按照key排序）
（key出现的次数也就代表着，==原数组a中有多少元素大于等于 key ==，大于等于嘛，所以我们直接将原数组中大于等于key的值都赋为key就好了）
因为map会按照key从小到大排序，所以我们从后往前遍历map即可，对于当前的 key 来说，设原数组 $a$ 中有 $n$ 个元素>=key，因此会在b中形成 value 个 key 和 sum 个比 key 大的数 （sum是数组b大于当前key的数字的个数），因此在 a 数组中就有 second+sum 个大于等于 first 的数，可以得到 $second+sum=\frac{(n-1)n}{2}$，这个式子里只有 n 是未知数，根据一元二次方程求解公式就可以得到 $n=\frac{1+\sqrt{8 (sum+second)+1}}{2}$，所以就可以直接求出原数组中>= key的元素个数 n，目前原数组 a 中有 cnt 个数（且这 cnt 个数都是大于等于当前 key 的，因为我们是按照 key 从大到小遍历的），现在算出有 n 个数>= key，我们就把 cnt 到 n 这一段还没有填充的位置用当前的 key 填上即可，这样遍历到数组结束就可以得到一种可能的 a 了
代码 #include <bits/stdc++.h> using namespace std;typedef pair<int , int > PII;using i64 = long long ;void solve () int n; cin >> n; vector<int > temp ((n - 1 ) * n / 2 ) ; map<int , int > b; for (int i = 0 ; i < (n - 1 ) * n / 2 ; i ++ ) { cin >> temp[i]; if (!b.count (temp[i])) b[temp[i]] = 1 ; else b[temp[i]] ++ ; } vector<int > ans (n) ; int sum = 0 , cnt = 0 ; for (map<int , int >::reverse_iterator it = b.rbegin (); it != b.rend (); it ++ ) { int res = (1 + sqrt (8 * (it->second + sum) + 1 )) / 2 ; for (int j = cnt; j < res; j ++ ) ans[cnt ++ ] = it->first; sum += it->second; } for (int i = n - 1 ; i >= 0 ; i -- ) cout << ans[i] << ' ' ; cout << '\n' ; } int main () ios::sync_with_stdio (false ); cin.tie (0 ), cout.tie (0 ); int t; cin >> t; while (t -- ) { solve (); } }
题意 给出两个数组 a 和 b，如果存在 $u, v$ 使得 $a_u-a_v>=b_u-b_v$，就说明 u 点可以到 v 点，如果一个点能到其他所有点就叫它 strong，现在问有多少点 strong ，分别是哪些点
思路 （是我的错觉吗怎么感觉这题更简单了啊喂
首先肯定是化简 $a_u-a_v>=b_u-b_v$，把它变成 $a_u-b_u>=a_v-b_v$，然后定义一个数组 c，$c_i=a_i-b_i$，（c 中元素存pair，first 存$a_i-b_i$，second 存 i），然后对 c 排序，由于差值较大的点可以连向差值较小的点，所以 first 越大的点能到达的点的数量就越多，而 first 最大的点就是所谓的 strong 点了
计算最大的first有多少个，输出他们的second即可
代码 #include <bits/stdc++.h> using namespace std;typedef pair<int , int > PII;using i64 = long long ;void solve () int n; cin >> n; vector<int > a (n) ; vector<int > b (n) ; for (int i = 0 ; i < n; i ++ ) cin >> a[i]; for (int i = 0 ; i < n; i ++ ) cin >> b[i]; vector<PII> c (n) ; for (int i = 0 ; i < n; i ++ ) { c[i] = make_pair (a[i] - b[i], i + 1 ); } sort (c.begin (), c.end ()); vector<int > res; for (int i = n - 1 ; i >= 0 ; i -- ) { if (i == n - 1 ) res.push_back (c[i].second); else if (c[i].first == c[i + 1 ].first) res.push_back (c[i].second); else break ; } cout << res.size () << '\n' ; for (int i = res.size () - 1 ; i >= 0 ; i -- ) cout << res[i] << ' ' ; cout << '\n' ; } int main () ios::sync_with_stdio (false ); cin.tie (0 ), cout.tie (0 ); int t; cin >> t; while (t -- ) { solve (); } }
题意 给出一个数组，分别以数组中的每个元素为 s，统计 [s 与数组中每个元素形成的区间内][不同数字出现的次数之和]，输出以当前元素为 s 的结果
思路 这题也不难，显然的前缀和
首先排序！
想到把每个数作为 s，然后和数组中所有数形成区间，进行差分运算，但是这样时间复杂度就是O(n^2^)，显然会出问题
然后开始考虑，我们只需要所有元素出现的次数总和，并不需要某一个元素出现了多少次，所以直接拿大数减小数加1即可，举个例子说明吧：
排好序后的数组为 1 1 2 5 7 3 - (1 + 1 + 2) + 3 1 + 7 + 1
按照这个思路，其中 5 前后的数可以用前缀和计算，这样整个算法的复杂度就是O(n)了
注意爆 int 0.0
代码 #include <bits/stdc++.h> using namespace std;using i64 = long long ;typedef pair<i64, i64> PII;void solve () int n; cin >> n; vector<PII> a (n) ; for (int i = 0 ; i < n; i ++ ) { cin >> a[i].first; a[i].second = i; } sort (a.begin (), a.end ()); vector<i64> res (n) ; res[0 ] = a[0 ].first; for (int i = 1 ; i < n; i ++ ) res[i] = res[i - 1 ] + a[i].first; vector<PII> ans (n) ; for (int i = 0 ; i < n; i ++ ) { if (i != 0 ) ans[i].second = i * a[i].first - res[i - 1 ] - (n - i - 1 ) * a[i].first + res[n - 1 ] - res[i] + n; else ans[i].second = i * a[i].first - (n - i - 1 ) * a[i].first + res[n - 1 ] - res[i] + n; ans[i].first = a[i].second; } sort (ans.begin (), ans.end ()); for (int i = 0 ; i < n; i ++ ) cout << ans[i].second << ' ' ; cout << '\n' ; } int main () ios::sync_with_stdio (false ); cin.tie (0 ), cout.tie (0 ); int t; cin >> t; while (t -- ) { solve (); } }
微信
