Codeforces Round 930 (Div. 2)

Bitwise Operation Wizard

算法本质

思维

题目大意

存在长度n的排列p（0开始），现在需要找到下标i j，使得p[i]^p[j]的值最大。
玩家至多可以进行3n轮以下询问：

• 询问每次需要给出a b c d四个整数，会返回p[a] | p[b]于p[c] | p[d]的大小关系：小于、等于、大于

思路推演

4个整数的询问比较少见，变数比较多，所以我们反向思考——怎样的两个数异或值最大。
举个例子，若n=14，异或最大值就是>=n的最小2的幂值，即16，显然较大的值是比较容易得到16的。

如果我们使用a a b b的询问，显然n轮就可以得到谁是最大值p。接下来需要找到另外一个恰好的值：所有与p或是16的下标的最小值。

这个讲起来比较玄学，但是没法，这种题就是不断发散思维一直碰撞

ac核心代码

下面代码对询问次数进行了一些压缩，属于没必要的优化。

头文件、宏定义、快读模板、常见变量、常见变量等略。
char ask(int a, int b, int c, int d)
{
    cout<<"? "<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
    char ans;
    cin>>ans;
    return ans;
}
int getmax(const vector<int> &v)
{
    int p = v[0];
    for (int i=1; i<v.size(); i++)
    {
        if (ask(p, p, v[i], v[i]) == '<')
            p = v[i];
    }
    return p;
}
int getmin(const vector<int> &v)
{
    int p = v[0];
    for (int i=1; i<v.size(); i++)
    {
        if (ask(p, p, v[i], v[i]) == '>')
            p = v[i];
    }
    return p;
}
inline void solve()
{
    cin>>n;
    vector<int> v(n);
    iota(v.begin(), v.end(), 0);
    int maxp = getmax(v);
    int last=(maxp==0?1:0);
    v.clear();
    v.push_back(last);
    for (int i=last+1; i<n; i++)
    {
        if (i==maxp)   continue;
        char c=ask(maxp, last, maxp, i);
        if (c=='<')
            last=i, v.clear(), v.push_back(last);
        else if (c=='=')
            v.push_back(i);
    }
    int q = getmin(v);
    cout<<"! "<<maxp<<" "<<q<<endl;
    return;
}

Pinball

算法本质

思维、数据结构

题目大意

给定由>和<组成的长度n字符串。如果小人现在处于>上，就会花费1秒向右移动一格，同时>会反转为<。

现在请给出小人初始在1~n的情况，花费多少时间会掉出字符串。

思路推演

模拟一下，这个游戏实际很简单，可以改成这样：（初始时）

• 小人左侧的>看作一个墙，<看作空地
• 小人右侧的<看作一个墙，>看作空地
• 小人脚下的字符表示初始行动方向
• 小人遇到墙，会将墙撞碎（变为空地），然后向反方向行走

我们想要知道小人多久出去，先得知道从哪边出去。需要判断一下小人左侧和右侧的墙的数目（使用前缀和），根据小人的初始方向就可以确定。

这个时候我们可以得到2个值：撞碎左边墙的数目、撞碎右边墙的数目。
现在需要计算撞碎这些墙所需要的时间。

这个的解决方法有很多，我们可以维护一个花费时间的前缀和，然后使用数目前缀和+二分来确定位置，确定位置后使用时间前缀和得到时间。

ac核心代码

代码写的比较复杂，还没有优化就不放了。

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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