A.Divide and Conquer
算法本质
思维
题目大意
给n个元素，可以进行以下操作：
- 选则元素值
x，使得x /= 2（向下取整）
最小化操作使得元素和为偶数。
思路推演
如果开始元素和为偶数则ans = 0
否则暴力每个元素改变奇偶性所需的操作数，找出最小值。
B.Make Array Good
算法本质
思维
题目大意
给长度为n的数组a[]，对于a[]定义美丽：
- 任意两个元素中的大值 % 小值 == 0
允许最多进行n次以下操作：
- 选择
i，使a[i]加上一个[0, a[i]]的值
输出操作情况。
思路推演
首先排序a[]方便观察。（升序）
随后手动模拟发现，a[i]对于a[i-1]总是可以轻易地增加到其倍数。
于是发现贪心即可。
C.Binary Strings are Fun
算法本质
思维
题目大意
对于总长为奇数的01字符串s，定义美丽：
- 对于奇数下标
i，s[1~i]中s[i]的字符占比超过一半
对于长度为n的01字符串s1，若长度为2*n-1的01字符串s2满足以下条件，则称s2是s1的扩展字符串：
- 对于任意
i：s2[2*i-1] = s1[i]
现给定长度为n的01字符串a，求其n个 前缀字符串 的 美丽 扩展字符串数目。（%mod）
思路推演
题目看起来定义繁琐、复杂，先手动模拟一下。
当s的末尾为01或者10时，其美丽扩展字符串的情况只有一种。（这个结论不详述）
进一步思考随后s考虑结尾是多个相同字符情况，发现s对ans的贡献为2^(结尾连续相同字符数-1)。
于是预处理a每个下标的结尾连续相同字符数即可。
D.GCD Queries
算法本质
思维
题目大意
给定0~n-1n个元素，将其顺序打乱放入p[]中。通过至多2n次以下询问来猜测0值元素的位置：
- 输出
? x y，会返回gcd(p[x], p[y])（gcd(0, x) == x）
猜测：
- 输出
! x y，若p[x]==0 || p[y]==0即算作猜测正确
思路推演-1 试错
这类题，最需要考虑就是每个数字本身的特性。
显然的一个做法是：根据数字的特性，将某个数字x，对其他数字都询问一遍，获得信息，然后进一步缩小范围。
若x为0，其得到结果唯一，好判断。
若x不为0，则会得到一部分1、一部分大于1的值，而0就藏在那部分大于1的值中。重复过程、便可一直缩小0的范围。
但是这个做法，当第一次取x取到1时，所需要的最多操作数为3n。（希望找到某个方法优化，但是找不到）
思路推演-2 正解
正解这个思路相当……让人有：这tm也可以？
平均一下哎，每2次查询都需要去掉一个非0位置。
选择3个值a b c：查询gcd(a,b)和gcd(a,c)
- 前值==后值：
则a一定不是0值，丢掉 - 前置!=后值：
假设gcd(a,b) < gcd(a,c)
则b一定不是0值，丢掉
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
//init
cin>>n;
deque<int> dq;
rep(i,1,n) dq.push_back(i);
//cal
while (dq.size() > 2)
{
int a=dq.front(); dq.pop_front();
int b=dq.front(); dq.pop_front();
int c=dq.front(); dq.pop_front();
int gcd_ab, gcd_ac;
cout<<"? "<<a<<" "<<b<<endl;
cout<<"? "<<a<<" "<<c<<endl;
cin>>gcd_ab>>gcd_ac;
if (gcd_ab == gcd_ac)
{
dq.push_back(b);
dq.push_back(c);
}
else if (gcd_ab < gcd_ac)
{
dq.push_back(a);
dq.push_back(c);
}
else
{
dq.push_back(a);
dq.push_back(b);
}
}
cout<<"! "<<dq.front()<<" "<<dq.back()<<endl;
cin>>m;
return;
}
评论 (0)