【CF】Day7——Codeforces Round 919 (Div. 2) BC
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;
}