C. Digital Logarithm
算法本质
思维（贪心）
思路推演
显然，为了达到最小操作数的目的，要在数大的时候尽量都给抵消了，实在不行才操作：
如果a[]和b[]中有重复元素，则移动到一边不变（也可以看作相互抵消了）。
然后我们选择具有部分特征的元素进行操作，然后再比较，一直重复这个过程直到完全抵消。
通过手动模拟，抓住了一个简单的性质，给数字划分等级。
一级：{1}
二级：{2~9}
三级：{10~1e9-1}可以看到，每次对一个数字操作，其都会变成低一级中的对应数字。
我们先对a[] b[]中等级为三级的元素，存在相等情况就抵消。
剩余的三级元素则全部进行操作，变为二级元素，然后再检查能否抵消，最后不行的变为一级元素——一定相同可抵消了。
这个代码实际上就会有2个操作：
- 相互抵消，可以选择
map或者双指针(queue)的方式 - 对更高一级的元素进行操作，随意即可——暴力复杂度也可以承受的
在代码写出框架后会发现，好像完全没有必要分为多个阶段的操作，我们可以使用priority_queue<int>来排序剩下的元素，然后选择a[]剩下的元素中最大ai和b[]剩下的元素中最大bi，如果两者相等，则抵消；若不等则选择较大值操作。
这样的话，实质是把上面的2个操作合并在一起了，但代码中两者可以同时进行——类似于也被我叫做“边输入边计算”的东西。
代码思路
priority_queue <int> qa, qb放a[]和b[]的元素。
同时取出qa.top()和qb.top()，相等则抵消，不等则取大者操作。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int suan(int x) //返回x的长度
{
return log10(x)+1;
}
inline void solve()
{
// init
cin>>n;
priority_queue <int> qa, qb;
rep(i,1,n)
{
int a;
cin>>a;
qa.push(a);
}
rep(i,1,n)
{
int b;
cin>>b;
qb.push(b);
}
//cal 2
int cnt=0;
while(!qa.empty())
{
int a=qa.top(), b=qb.top();
if (a==b) //相等——抵消
{
qa.pop();
qb.pop();
}
else if (a>b) //不等——取大的操作
{
qa.pop();
qa.push( suan(a) );
cnt++;
}
else
{
qb.pop();
qb.push( suan(b) );
cnt++;
}
}
//out
ans = cnt;
cout<<ans<<endl;
return;
}D. Letter Picking
算法本质
dp、思维（博弈论）
思路推演
思维题，特别还是博弈论，就一定得从小规律找起，推导到全局。
部分简单的手动模拟：
bb 平局
ab alice赢
ba alice赢
abba 平局
abcd alice赢可以看到，当长度大于2时，就没有一个相对简单的规律了。
但是这道题有很明显的博弈论的意味，博弈论的精髓就在于，俩人各走一步为一个回合，以回合为单位推进转换——这里就和dp的状态转移对应上了，所以博弈论sg组合数的解决方法是用dp的方式呈现的。
同时，通过大量的模拟，我们发现好像并没有bob赢的情况，猜测bob可能最多平局，于是开始推理。
定理1：若只剩下2个不同的字符，则一定是alice赢。
定理2：若字符串是由一对一对组成的(aabbbbcc)，那一定是平局。
bob能赢的唯一途径：所以最好能让bob在某次选择中先占得先机，最后剩下2个一样的字符，类似于——bacc，让alice选择b，bob选择a。
基于此，alice可以选择优先破坏成对的字符，使得最后剩下2个不一样的字符，这波坏了bob赢的途径。
所以，bob一定不会赢。推出bob一定不会赢，可以很好的简化代码逻辑。
我们现在可以简单的定义，bob一心想着平局，alice一心想着不平局。
因为只能从左边or右边拿字符，这个博弈论的可能性很低，将会比较好做。
假设原字符串为abxxxxcd（xxxx表示偶数个未知字符）
（橘色线条代表alice可以走的，蓝色线条代表bob可以走的）
若abxxxxcd为平局，有两个可能：
- 中间的
bxxxxc为平局 &&a==d xxxxcd平局 &&a==b&&abxxxx平局 &&c==d
其他则都是alice赢。
上面这推理，其实也就是dp里的状态转移方程。
若不推出bob的情况，也是可以做的，只是说逻辑会相对复杂。
代码思路
dp，从底层开始推理。
维护cun[][]cun[l][r]=v表示[l,r]，v=0表示未知，还需要自己去求，v=1表示这个点alice会赢，v=2表示会平局。
然后用对长度为2的字符串节，对cun[][]初始化。
接着长度依次增加2，通过状态转移方程计算。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int cun[maxn][maxn];
//cun[l][r]=v表示[l,r]，v=0表示未知，还需要自己去求，v=1表示这个点alice会赢，v=2表示会平局，v=3表示bob会赢
inline void solve()
{
// init
scanf("%s", ch+1);
n = strlen(ch+1);
// cal
for (int i=1; i<=n-1; i++) //初始化
cun[i][i+1] = 1 + (ch[i]==ch[i+1]);
for (int len=4; len<=n; len+=2)
{
for (int l=1; l+len-1<=n; l++)
{
int r = l+len-1; //状态转移方程（逻辑）
if (cun[l+1][r-1]==2 && ch[l]==ch[r]) cun[l][r]=2;
else if (cun[l][r-2]==2 && cun[l+2][r]==2 && ch[l]==ch[l+1] && ch[r]==ch[r-1]) cun[l][r]=2;
else cun[l][r]=1;
}
}
//out
flag = cun[1][n]==1;
if (flag) cout<<"Alice"<<endl;
else cout<<"Draw"<<endl;
return;
}题目
算法本质
思路推演
代码思路
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。题目
算法本质
思路推演
代码思路
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)