Codeforces Round 931 (Div. 2)

Find a Mine

算法本质

思维

题目大意

矩阵地图中，有2颗地雷（坐标未知），玩家可以进行至多3次探测：

• 制定一个坐标
• 返回2颗地雷与坐标的曼哈顿值的较小值

最后输出某颗地雷的坐标。

思路推演

矩阵中的曼哈顿值很有趣，如果在中间部分放置，其地雷可能存在的地方是一个正菱形。显然，如果我们在角落进行探测，可能的范围会缩小。

进一步可以发现，如果在两个对角进行探测，则可以锁定两个地雷所在的斜线，在任意选一个位置探测即可。

经验

这类题其实比较典型，既然是3个操作，2个地雷，其过程很有可能是，通过前1-2次操作，可以获得两颗地雷的部分信息（两者的信息量是一致的），然后使用最后的操作获取某个地雷的所有信息。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
int ask(int x, int y)
{
    cout<<"? "<<x<<" "<<y<<endl;
    return in();
}
bool ck(int x, int y)
{
    if (x<1 || x>n || y<1 || y>m)
        return 0;
    return 1;
}
inline void solve()
{
    cin>>n>>m;
    int d1=ask(1, 1), d2=ask(n, m), d3=ask(n, 1);
    set<pair<int,int>> cod;
    if ((d1+d3-n+1)%2==0)       // 说明左侧上下有交点
    {
        int rt = (d1+d3-n+1)/2;
        int y = rt + 1;
        int x = d1 - rt + 1;
        if (ck(x, y))
            cod.insert({x, y});
    }
    if ((d2+d3-m+1)%2==0)
    {
        int up = (d2+d3-m+1)/2;
        int x = n - up;
        int y = d3 - up + 1; 
        if (ck(x, y))
            cod.insert({x, y});
    }
    if (cod.size()==2)
    {
        auto [x, y] = *cod.begin();
        int dis = ask(x, y);
        if (dis)
            cod.erase({x, y});
        else
        {
            cod.clear();
            cod.insert({x, y});
        }
    }
    auto [x, y] = *cod.begin();
    cout<<"! "<<x<<" "<<y<<endl;
    return;
}

XOR Break --- Solo Version

算法本质

思维

题目大意

给定初始值x和目标值y，需要玩家进行至多63回合，最终使得x==y值：（以下2个操作记作1回合）

• 将x分解成2个值a b，需要保证：

  • a^b == x
  • a < x
  • b < x
• 然后选择将a或者b赋值给x

输出转换过程

1 < y < x < 1e18

思路推演

既然我们最后会选择a或b进行赋值，这明显告诉我们，不用管另一个值，只需要保证其合法即可。
为了之后方便叙述，我们这里强制保证a < b

模拟一下分解过程，发现一个很不错的性质：

• 若x的二进制位高的某几位1并非单独b的话，之后的所有二进制位都可以任意分配

这个性质特别好，如果y是比较小的情况的话，我们可以先构建a为y的超集，然后再得到y。

我们进行了更多的模拟，发现如果y的最高位不超过初始x的次高位（从高往低，第2个出现1的位），则可以如此构建。

如果x仅有1位，显然不可行

例如：（左边是高位）
x = 101000
y = 000101
我们构建 a = y
如果y在x的次高位上没有值，则a=y+x次高位
a = 001101
b = x^a
同时这样会保证：b<x 且 a是y的超集

接着我们考虑其他情况，如果y的最高位介于x的最高位和次高位之间，可以证明这样没有解。

如果y的最高位同x的最高位一致，又因为保证了y<x——所以我们可以直接使得b=y, a=x^b，一步到位。

63次操作属于障眼法

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
int get_top(int x)
{
    while (x > lowbit(x))
        x-=lowbit(x);
    return x;
}
inline void solve()
{
    int a, b, c;
    cin>>a>>b;
    int tar=b;
    c = a^b;
    if (get_top(a) == get_top(b))
    {
        cout<<1<<endl;
        cout<<a<<" "<<b<<endl;
        return;
    }
    flag = 1;
    int val = a;
    val -= get_top(val);
    val = get_top(val);     // 获取次高位的值
    if (b >= val*2)     // 如果介于高位和次高位之间,无解
    {
        cout<<"-1"<<endl;
        return;
    }
    else if ((b&val)==0)    // 有解,开始制造超集
        b+=val, c-=val;
    
    if (b==tar)        // 有可能超集刚好相等，所以一步到位
    {
        cout<<1<<endl;
        cout<<a<<" "<<b<<endl;
    }
    else        // 使用超集作为中间值
    {
        cout<<2<<endl;
        cout<<a<<" "<<b<<" "<<tar<<endl;
    }
    return;
}

XOR Break --- Game Version

算法本质

思维、简单博弈

题目大意（小改）

玩家和系统进行博弈游戏，两者轮流执行以下操作：

• 从a b两个值中选择一个作为x

• 将x分解成2个值a b，需要保证：

  • a^b == x
  • a < x
  • b < x

如果无法分解，记作当前玩家输掉游戏

初始系统给定的a b保证a==b（但是游戏过程中不一定会相等了）。
玩家可以选择先手或者后手，需要在63回合内击败对手（自己行动才记作一个回合）。

输出游戏过程。

思路推演

我们考虑，如果x值的二进制位仅有一个1，则显然无法分解，会失败。所有有两个1就是必胜态。
但是当继续推理时，情况就十分复杂了——因为对手有2个选择。

博弈论的一部分，需要我们观察到更加内核本质的变化，从而逼迫对手一直处于必败态。

奇偶是一个比较常思考的方向，考虑到异或的特殊性，我们可以一直让对手的x处于由奇数个1组成，而我们的x由偶数个1组成。
稍加模拟，发现可行。

接下来我们需要在63回合获胜，就需要防止对手一直拖回合。考虑到单个1无法分解，于是对于x，我们可以把最高位的1作为a，剩余的值作为b，对手就会被迫选择b，这样每回合至少都减少了一个高位1，63回合绰绰有余。

这题2400，不理解，从过题人数结合难度来看，大概2100-2200吧。

因为当时标2400，思考简单博弈的时候，还自我否定，想着2400怎么可能一个简单博弈出来了。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
int get_top(int x)
{
    while (x > lowbit(x))
        x-=lowbit(x);
    return x;
}
int get_num(int x)
{
    int res=0;
    while (x)
        x-=lowbit(x), res++;
    return res;
}
void send(int x)
{
    int a=get_top(x);
    int b=x-a;
    cout<<a<<" "<<b<<endl;
}
int recceive()
{
    int a, b;
    cin>>a>>b;
    return (get_num(a)%2==0 ? a : b);
}
inline void solve()
{
    int x;
    cin>>x;
    if (get_num(x)%2)
        cout<<"second"<<endl;
    else
    {
        cout<<"first"<<endl;
        send(x);
    }
    while (1)
    {
        x = recceive();
        if (x==0)    break;
        send(x);
    }
    return;
}

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。