B. Summation Game
题目:
思路:
千万别想的太难了,想难你就输了
鲍勃想最小化数组的话肯定是把x个最大的全乘以-1,爱丽丝想最大化就要删去k个最大值,但是不一定要删k个
观察数据,n是2e5,那么我们暴力枚举删后i个元素然后取最大值即可,同时要注意先排序
代码:
#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"void solve()
{int n, k, x;cin >> n >> k >> x;vector<int> a(n+1);for (int i = 1; i <= n; i++){cin >> a[i];}sort(a.begin()+1, a.end());int res = -1e18;for (int i = 1; i <= n; i++){a[i] += a[i - 1];}int sum = a[n];//删i个元素for (int i = 0; i <= k; i++){int j = n - i;int minus = sum - a[j];int bobnum = a[j] - a[max(j - x,0LL)];int chage = sum - minus - 2*bobnum;//cout << sum << " " << minus << " " << bobnum << " " << chage << endl;res = max(res, chage);}cout << res << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}
C. Partitioning the Array
题目:
思路:
首先,我们把问题分成两个部分
①.分成n/k个子数组
②.找出一个m满足题意
问题①肯定是没问题的,我们可以暴力枚举1~快速直到哪些树是n的因数
那么问题②该如何解决呢,首先我们要明白题意的意思,既然是要每个子数组全相等,也就是说对于任意一个ai,要满足 ,其中a = a[i],b = a[i+k],根据同余的减法,也就是说有
(abs(a[i] - a[i+k]) 0 mod m),即
那我们只需要暴力枚举即可,我们求出gcd(a[i] - a[i+k],a[i+1],a[i+1+k],....) = g
至于为什么要求gcd也很明显,因为每个a[i] - a[i+k]都要能被m整除,所以肯定要求所有a[i] - a[i+1]的最大公因数
因为m大于等于2,所以只要g大于一就能增加答案
代码:
#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"int n;int gcd(int a,int b)
{return (!b) ? a : gcd(b, a % b);
}int fuc(const vector<int>&a, int k)
{if (k == n){return 1;}int g = abs(a[1] - a[1 + k]);for (int i = 1; i <= n-k; i++){g = gcd(g, abs(a[i] - a[i + k]));if (g == 1){return 0;}}return 1;
}void solve()
{cin >> n;vector<int> a(n+1,0);for (int i = 1; i <= n; i++){cin >> a[i];}int ans = 0;for (int k = 1; k*k <= n; k++){if (n % k == 0){ans += fuc(a, k);if (k * k != n)ans += fuc(a, n / k);}}cout << ans << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}