源代码:ACM/OpenjudgeNow/Codeforces at master · abmcar/ACM (github.com)
A. Min Or Sum
题目大意:
思路:
a+b >= a|b,我们可以把a,b换成0,a|b,这种形式,最终,我们可以把数组替换为若干个0和一个数组|和
最终的和为数组 | 和
代码:
void work()
{
cin >> n;
int ans = 0;
for (int i= 1; i <= n; i++)
{
int temp;
cin >> temp;
ans |= temp;
}
cout << ans << Endl;
}
B. Avoid Local Maximums
题目大意:
思路:
思考一下,如果我们发现了一个局部最大值,那么我们应该怎么操作?
如果改变较大的那个数,会发现可能导致新的局部最大值产生,因此,需要改变较小的值
选择后一个较小值(因为前面的已经操作过了),使得nums[i+1] = max(nums[i], nums[i + 2])即可
代码:
void work()
{
cin >> n;
vector<int> nums(n + 3);
for (int i = 1; i <= n; i++)
cin >> nums[i];
nums[0] = nums[n + 1] = 1e9;
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1])
{
nums[i + 1] = max(nums[i], nums[i + 2]);
ans++;
}
}
cout << ans << endl;
for (int i = 1; i <= n; i++)
cout << nums[i] << " \n"[i == n];
}
C. Differential Sorting
题目大意:
思路:
由于不最小化操作数,可以发现如果数组最后两个不递减,可以使得其他数都为最后两数之差(为负)
如果为负数,那么只有当前面的数也全为负数时才可能不递减,如果存在正数,则无法把num[x] 替换为小于 num[y]的(只有-正数才会更小),此时判断是否已经排序即可
代码:
void solution()
{
cin >> n;
nums.resize(n + 1);
nums[0] = -1e14;
for (int i = 1; i <= n; i++)
cin >> nums[i];
if (nums[n - 1] > nums[n])
{
cout << "-1" << endl;
return;
}
else
{
if (nums[n] < 0)
{
if (is_sorted(nums.begin(), nums.end()))
cout << 0 << endl;
else
cout << -1 << endl;
return;
}
}
cout << n - 2 << endl;
for (int i = 1; i <= n - 2; i++)
cout << i << " " << n - 1 << " " << n << endl;
}
D. Infinite Set
题目大意:
思路:
很容易可以想到按位数dp
dp[i] = dp[i-1] + dp[i-2]
难点在于已有数的去重添加
如果我们去生成的话,数量会很大,难以承受(因为也是类fib上升)
正难则反,由于生成存在一定规律,我们可以做一个set存原始节点,判断后续每个数是否可以从该节点产生
如果末尾为1,则为从x*2+1生成
如果末尾为00,则为x*4生成
如果末尾为10,则不可生成
之后按照fib来dp即可
代码:
signed main()
{
cin >> n >> p;
nums.resize(n + 1);
dp.resize(p + 50);
for (int i = 1; i <= n; i++)
{
cin >> nums[i];
}
sort(nums.begin() + 1, nums.end());
// cout << nums[1] << " " << nums[2] << endl;
for (int i = 1; i <= n; i++)
{
int nowNum = nums[i];
bool flag = false;
while (nowNum > 0)
{
if (useful.count(nowNum))
{
flag = true;
break;
}
if (nowNum & 1)
{
nowNum >>= 1;
}
else if (nowNum & 3)
{
break;
}
else
{
nowNum >>= 2;
}
}
if (!flag)
useful.insert(nums[i]);
}
vector<int> tmp(p + 50, 0);
for (int it : useful)
tmp[log2(it) + 1]++;
int ans = 0;
for (int i = 1; i <= p; i++)
{
dp[i] = tmp[i];
if (i >= 2)
{
dp[i] += dp[i - 1];
dp[i] = dp[i] % Mod;
}
if (i >= 3)
{
dp[i] += dp[i - 2];
dp[i] = dp[i] % Mod;
}
ans += dp[i];
ans = ans % Mod;
}
cout << ans << endl;
return 0;
}