CZOJ Weekly Exercise Round 1 官方题解

博主： cyx2009
发布时间：2023 年 04 月 22 日
626 次浏览
3 条评论
3140字数
分类： OI 模拟赛官方题解

A. 玉兔祥云

$\tt{J\textcolor{red}{Yawa}}$

$\tt{c\textcolor{red}{yx2009}}$

Sol

对于第一问，考虑抽屉原理。

对于第二问，考虑贪心。

Code

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x, y;
    cin >> x >> y;
    cout << max(0LL, y - 9LL * x)
         << ' ' << y / 10 << endl;
    return 0;
}

B. 视界巡航

$\tt{z\textcolor{red}{js123}}$

$\tt{c\textcolor{red}{yx2009}}$

$\tt{z\textcolor{red}{js123}}$

$\tt{c\textcolor{red}{yx2009}}$

$\tt{B\textcolor{red}{yGones}\ and\ \tt{c\textcolor{red}{hufuzhe}}}$

Sol

阅读题意可知，这题我们需要动态维护序列的最大值最小值。

每次操作进行修改最大最小并重排的复杂度是错误的，达到了 $\mathcal O(q\times n \log n)$ 的级别。

那么，我们不难想到 C++ 的 STL，multiset。

multiset 与 set 的区别在与，multiset 的元素是可以重复的。根据题意及样例，这里可能会有重复元素出现。

下面介绍一下 multiset：

multiset 位于 set 库中。请使用 #include<set> 等或使用包含 set 库的库。
multiset<type>mst 建立一个 type 类型的 multiset 容器。type 可以是 int/long long/pair<int,int>/string 等。
mst.clear() 清空。
mst.insert(x) 向集合插入元素 $x$。
mst.empty() 查询集合是否为空。
mst.begin()/mst.end() 返回集合开头/结尾迭代器。代码中所用的 *s.begin() 和 *(--s.end()) 即为开头与结尾元素。
mst.erase(x) 删除迭代器为 $x$ 的元素。

乱搞做法：平衡树。

赛时码不出来怎么办？C++ 拥有强大的 pb_ds 库，可以直接实现。但是在提交的时候请选择开启 O2 优化的语言，因为 pb_ds 在无 O2 下的表现极劣。

Code

代码

/*
Auther:  zjs123
Luogu:   754000
QQ:      755328053
*/
#include<bits/stdc++.h>
using namespace std;
int n,t;
int op;
long long x,a,b;
multiset<long long> s;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a;
        s.insert(a);
    }
    cin>>t;
    while(t--){
        cin>>op>>b;
        if(op==1)x=b;
        else if(op==2){
            s.erase(--s.end());
            s.insert(b);
        }
        else{
            s.erase(s.begin());
            s.insert(b);
        }
        cout<<*(--s.end())+x<<"\n";
    }
    return 0;
}

C. 恶灵群舞

$\tt{z\textcolor{red}{js123}}$

$\tt{c\textcolor{red}{yx2009}}$

$\tt{z\textcolor{red}{js123}}$

$\tt{c\textcolor{red}{yx2009}}$

$\tt{B\textcolor{red}{yGones}\ and\ \tt{c\textcolor{red}{hufuzhe}}}$

Sol

阅读完题意，不难联想到搜索。

因为要求出最右下角的答案，所以我们需要先找出所有答案。

考虑进行搜索，用 $z_{i,j}$ 表示走到 $(i,j)$ 的最小代价。因为每个点最多走不到很多次，穿墙的其实很少，所以时间复杂度 $\mathcal O(nm)$。

Code

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    long long x,y;
    long long va;
};
long long n,m,a,b;
long long aa[120][120];
long long h[120][120];
pair<long long,long long> vis[120][120];
long long dx[]={1,-1,0,0};
long long dy[]={0,0,1,-1};
void dfs(long long x,long long y){
    h[x][y]=1;
    for(long long i=0;i<4;i++){
        long long tx=x+dx[i];
        long long ty=y+dy[i];
        if(tx>0&&tx<=n&&ty>0&&ty<=m&&h[tx][ty]==0&&aa[tx][ty]==0)dfs(tx,ty);
    }
}
queue<node> q;
long long z[120][120];
long long ans=0x3f3f3f3f3f3f3f3f;
long long xx,yy;
main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>a>>b;
    memset(z,0x3f,sizeof z);
    for(long long i=1;i<=n;i++){
        for(long long j=1;j<=m;j++){
            cin>>aa[i][j];
        }
    }
    memset(vis,0x3f,sizeof vis);
    dfs(1,1);
    q.push(node{1,1,0});
    vis[1][1]=make_pair(1,0);
    z[1][1]=0;
    while(!q.empty()){
        long long x=q.front().x;
        long long y=q.front().y;
        long long va=q.front().va;
        q.pop();
        for(long long i=0;i<4;i++){
            long long tx=x+dx[i];
            long long ty=y+dy[i];
            if(tx>0&&tx<=n&&ty>0&&ty<=m&&aa[tx][ty]==0&&vis[tx][ty].second>va+a){
                vis[tx][ty].second=va+a;
                q.push(node{tx,ty,va+a});
                z[tx][ty]=min(z[tx][ty],va+a);
            }
            if(tx>0&&tx<=n&&ty>0&&ty<=m&&aa[tx][ty]==1&&aa[tx+dx[i]][ty+dy[i]]==0&&vis[tx+dx[i]][ty+dy[i]].second>va+b){
                tx+=dx[i];
                ty+=dy[i];
                vis[tx][ty].second=va+b;
                q.push(node{tx,ty,va+b});
                z[tx][ty]=min(z[tx][ty],va+b);
            }
        }
    }
    for(int i=n;i>=1;i--){
        for(long long j=m;j>=1;j--){
            if(ans>z[i][j]&&h[i][j]==0){
                ans=z[i][j];
                xx=i;
                yy=j;
            }
        }
    }
    if(ans==0x3f3f3f3f3f3f3f3f){
        cout<<"No";
        return 0;
    }
    cout<<"Yes\n";
    cout<<ans<<" ("<<xx<<","<<yy<<")";
    return 0; 
}

Nothing

cyx&wyr の阴谋

D. 狂热派对

$\tt{c\textcolor{red}{yx2009}}$

$\tt{B\textcolor{red}{yGones}\ and\ \tt{c\textcolor{red}{hufuzhe}}}$

Sol

其实就是中等的模拟。代码只是变量比较长。

造数据才是大模拟！cyx 为了造数据更容易甚至改了题面。但尽管如此数据生成的代码与 std 的长度相差不大。

我们对于每个记录，按照题意描述检查一下，如果过了就打上标记，并计算时间差得到该题的罚分。被 hack 就取消标记。出现非 CE 或非 WA on 1 就把这题分数按规定减去 $50$。

Code

代码

/*
Auther:  cyx2009
Luogu:   516346
QQ:      2176807108
*/
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
string Problem_Name[2520];
struct Submission
{
    string Time, Verdict, Problem;
    int Minute;
} CYX_Submission[25020], ZJS_Submission[25020];
string Start_Time;
int INT_Start_Time;
long long CYX_Score, ZJS_Score;
int ZJS_WA[2520];
int CYX_WA[2520];
bool ZJS_Hacked[2520];
bool CYX_Hacked[2520];
bool ZJS_AC[2520];
bool CYX_AC[2520];
int ZJS_Problem_Score[2520];
int CYX_Problem_Score[2520];
map<string, int> Name_to_Id;
int Time_String_to_Int(string Time)
{
    int HH, MM, Minute;
    HH = (Time[0] - '0') * 10 + (Time[1] - '0');
    MM = (Time[3] - '0') * 10 + (Time[4] - '0');
    Minute = HH * 60 + MM;
    return Minute;
}
int Get_Int_Submission_Time(string Time)
{
    int Minute = Time_String_to_Int(Time);
    return Minute < INT_Start_Time ? Minute + 24 * 60 - INT_Start_Time : Minute - INT_Start_Time;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> Problem_Name[i];
        Name_to_Id[Problem_Name[i]] = i;
    }
    cin >> Start_Time;
    INT_Start_Time = Time_String_to_Int(Start_Time);
    for (int i = 1; i <= n; i++)
    {
        cin >> ZJS_Submission[i].Time >> ZJS_Submission[i].Problem >> ZJS_Submission[i].Verdict;
        ZJS_Submission[i].Minute = Get_Int_Submission_Time(ZJS_Submission[i].Time);
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> CYX_Submission[i].Time >> CYX_Submission[i].Problem >> CYX_Submission[i].Verdict;
        CYX_Submission[i].Minute = Get_Int_Submission_Time(CYX_Submission[i].Time);
    }
    for (int i = 1; i <= n; i++)
    {
        if (ZJS_Submission[i].Verdict == "Hacked")
        {
            if (!ZJS_Hacked[Name_to_Id[ZJS_Submission[i].Problem]])
            {
                CYX_Score += 100;
                ZJS_Hacked[Name_to_Id[ZJS_Submission[i].Problem]] = 1;
                ZJS_AC[Name_to_Id[ZJS_Submission[i].Problem]] = 0;
            }
        }
        else if (ZJS_Submission[i].Verdict == "CompileError")
        {
            continue;
        }
        else if (ZJS_Submission[i].Verdict.size() >= 23 && ZJS_Submission[i].Verdict.substr(0, 21) == "Wrongansweronpretest(")
        {
            if (ZJS_Submission[i].Verdict[21] == '1')
                continue;
            ZJS_WA[Name_to_Id[ZJS_Submission[i].Problem]]++;
        }
        else if (ZJS_Submission[i].Verdict == "PretestsPassed")
        {
            ZJS_AC[Name_to_Id[ZJS_Submission[i].Problem]] = 1;
            ZJS_Problem_Score[Name_to_Id[ZJS_Submission[i].Problem]] =
                max(
                    Name_to_Id[ZJS_Submission[i].Problem] * 150,

                    Name_to_Id[ZJS_Submission[i].Problem] * 500 -
                        ZJS_Submission[i].Minute * Name_to_Id[ZJS_Submission[i].Problem] * 2 -
                        ZJS_WA[Name_to_Id[ZJS_Submission[i].Problem]] * 50);
            ZJS_WA[Name_to_Id[ZJS_Submission[i].Problem]]++;
        }
    }
    for (int i = 1; i <= m; i++)
    {
        if (CYX_Submission[i].Verdict == "Hacked")
        {
            if (!CYX_Hacked[Name_to_Id[CYX_Submission[i].Problem]])
            {
                ZJS_Score += 100;
                CYX_Hacked[Name_to_Id[CYX_Submission[i].Problem]] = 1;
                CYX_AC[Name_to_Id[CYX_Submission[i].Problem]] = 0;
            }
        }
        else if (CYX_Submission[i].Verdict == "CompileError")
        {
            continue;
        }
        else if (CYX_Submission[i].Verdict.size() >= 23 && CYX_Submission[i].Verdict.substr(0, 21) == "Wrongansweronpretest(")
        {
            if (CYX_Submission[i].Verdict[21] == '1')
                continue;
            CYX_WA[Name_to_Id[CYX_Submission[i].Problem]]++;
        }
        else if (CYX_Submission[i].Verdict == "PretestsPassed")
        {
            CYX_AC[Name_to_Id[CYX_Submission[i].Problem]] = 1;
            CYX_Problem_Score[Name_to_Id[CYX_Submission[i].Problem]] =
                max(
                    Name_to_Id[CYX_Submission[i].Problem] * 150,

                    Name_to_Id[CYX_Submission[i].Problem] * 500 -
                        CYX_Submission[i].Minute * Name_to_Id[CYX_Submission[i].Problem] * 2 -
                        CYX_WA[Name_to_Id[CYX_Submission[i].Problem]] * 50);
            CYX_WA[Name_to_Id[CYX_Submission[i].Problem]]++;
        }
    }
    for (int i = 1; i <= k; i++)
    {
        if (ZJS_AC[i])
        {
            ZJS_Score += ZJS_Problem_Score[i];
        }
        if (CYX_AC[i])
        {
            CYX_Score += CYX_Problem_Score[i];
        }
    }
    cout << ZJS_Score << " " << CYX_Score << endl;
    if (CYX_Score > ZJS_Score)
    {
        cout << "cyx" << endl;
    }
    else if (ZJS_Score > CYX_Score)
    {
        cout << "zjs" << endl;
    }
    else
    {
        cout << "Wow!Same!" << endl;
    }
    return 0;
}

E. 绿茵战场

$\tt{c\textcolor{red}{yx2009}}$

$\tt{B\textcolor{red}{yGones}\ and\ \tt{c\textcolor{red}{hufuzhe}}}$

Hint

Hint 1

首先，不考虑拜日教皇骗人的情况，我们如何准确查询？

Hint 2

当我们学会了不骗的人情况下准确查询后，如何知道拜日教皇有没有骗人呢？

Sol

之后的分析以及代码均由 $0$ 作为起始下标。

先考虑 Hint 1。

我们发现，$2^{31}-1=2,147,483,647$。

也就是说，$10^9$ 只需要大约 $30$ 个 bit 即可。

我们枚举每个 bit 表示的实际数字并查询。检查返回值与 $cnt$ 的大小关系。

如果返回值比 $cnt$ 小，说明这个 bit 被消除了，也就是原数的这个 bit 是 $1$。

举个例子：$(10)_{10}=(1010)_2$。

$(10-2)_{10}=(8)_{10}=(1000)_2$。

这里我们消去第 $1$ 个 bit，也就是消去了 $2^1=2$。

$f(8)<f(10)$，第 $1$ 个 bit 确实是 $1$。

$(10-1)_{10}=(9)_{10}=(1001)_2$

这里我们消去第 $0$ 个 bit，也就是消去了 $2^0=1$。

$f(9)=f(10)$，第 $0$ 个 bit 不是 $1$。

所以退位什么只会导致 $1$ 个数相同或更多。感兴趣的话可以多找点例子。

综上，我们枚举 $0\sim 29$ 每一个 bit 代表的数 $x$ 并查询。如果得到的结果比 $cnt$ 小，那么 $ans\gets ans+x$，答案加上 $x$。

至此，Hint 1 的解决方法结束。

for(int i=0;i<30;i++)
{
    cout<<"? "<<(1<<max(i-1,0))<<'\n';
    fflush(stdout);
    int c;
    cin>>c;
    if(c==0)bit++,ans|=1<<i;
    if(bit==cnt)break;
}

如何处理 Hint 2 所提到的骗人情况呢？

我们发现题目中给了 $60$ 次的询问限制，而 Hint 1所提到的只有 $30$ 次询问。

我们发现，如果每次 ? 0 $f(n-x)$ 永远不变，一定是 $cnt$。也就是说，一旦返回不是 $1$，也就是不相等，那么一定骗人了。

因此，我们查询 $m$ 次 ? 0。因为骗人有周期性，所以想知道之后第 $i$ 条询问的回答是否骗人只需查看第 $i\bmod m$ 个询问的结果。

Code

代码

/*
Auther:  cyx2009
Luogu:   516346
QQ:      2176807108
*/
#include<bits/stdc++.h>
using namespace std;
bool f[50];//是否说谎 
int cnt,m;
int ans,bit; 
int main()
{
    cin>>cnt>>m; 
    for(int i=0;i<m;i++)
    {
        cout<<"? 0\n";
        fflush(stdout);
        int x;
        cin>>x;
        if(x!=1)f[i]=0;
        else f[i]=1;
    }
    for(int i=0;i<30;i++)
    {
        cout<<"? "<<(1<<max(i-1,0))<<'\n';
        fflush(stdout);
        int c;
        cin>>c;
        if(!f[i%m])c=(c+1)%3; 
        if(c==0)bit++,ans|=1<<i;
        if(bit==cnt)break;
        // cout<<bit<<"\n"; 
        // fflush(stdout);
    }
    cout<<"! "<<ans<<'\n';
    fflush(stdout);
    return 0;
}

Nothing

说句闲话，这题是一道大杂烩的原题。

主体部分（Hint 1）为 CF1780D，另一部分（Hint 2）为 CF1010B。

在写下这段的时候，这两题在 CF 的评分均为 *1800，融合之后的这题，个人认为难度放到提高组也是不为过的。

至于为什么出交互，可能是受到了「信息与未来 2022」启发。~~小学生比赛都能出交互，普及组模拟赛不能出吗？~~

F. 数码方阵

$\tt{c\textcolor{red}{yx2009}}$

$\tt{J\textcolor{red}{Yawa}}$

Solution

首先，这里输入很奇葩。我们可以把它拆成一个序列，设序列长度为 $N=n\times m$。

假设 $A_{N-1}+2 \leq A_N$。可以证明，Xuan 总是会获胜。

如果 Xuan 能够使得 $A_N<A_{N-1}$ 并让 Xiang 面对一个必输的局面，Xuan 就会赢。
假设通过使 $a_N<a_{N-1}$ 能够获得所有必胜的局面。然后，如果我们 $a_N \gets a_{N-1}+1$，那么可以从该局面过渡到的所有局面都是必胜的。因此，将 $a_N \gets a_{N-1}+1$ 所得到的局面是必败的。所以，初始局面是必胜的。

接下来，考虑当给定一个满足 $a_N=a_{N-1}+1$ 的局面。根据上述证明，Xuan 和 Xiang 不应该给出最大两个元素差为 $2$ 或更大的局面。综上，我们可以假设 $a$ 的最大两个元素的差为 $1$。

然后，我们发现每一步操作都会将 $\max\{a\}$ 减少 $1$。

当 $\max\{a\}=N-1$ 时，该局面无法进行操作，因此可以根据输入中 $a_N$ 和 $N-1$ 的奇偶性差异来确定赢家。

复杂度为 $O(N)$。

但是输入不是有序，进行排序。复杂度为 $O(N \log N)$。

std 和这里的说法有些不同，std 写法更为简洁。

Code

代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[300020];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n * m; i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + n * m + 1);
    for (int i = 1; i <= n * m; i++)
    {
        a[i] -= i - 1;
    }
    if (a[n * m] == a[n * m - 1] && (a[n * m] % 2 == 0))
        puts("Xiang");
    else
        puts("Xuan");
    return 0;
}

最后修改：2023 年 07 月 11 日

v我50吃疯狂星期四

3 条评论

tangchaojun
July 9th, 2023 at 04:23 pm

C题，Code 55-56：值改变后依然需要做边界检查。
vis定义成pair意义何在，全程没有使用first

回复
1. 出题人 and 出锅人 2
  July 15th, 2023 at 08:59 pm
  
  @tangchaojun
  
  1.虽然但是，对最终结果没有任何影响
  2.我tm匆匆忙忙改出来的代码，一个意思知道就行了，空间又不要你付钱
  
  回复
PE
July 8th, 2023 at 09:00 am

T2:multiset wrong
平衡树 wrong
priorty_queue right

回复

发表评论取消回复
欢迎多多评论捏

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

CZOJ Weekly Exercise Round 1 官方题解

cyx2009 • 2023 年 04 月 22 日

<h1><span class="external-link"><a class="no-external-link" href="http://czoj.com.cn/p/P1711" target="_blank"><i data-feather="external-link"></i>A. 玉兔祥云</a></span></h1>
<p><div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-d3c98b891a99ded757655e1eb08cdd1c960' role="tab" data-target='#tabs-d3c98b891a99ded757655e1eb08cdd1c960'>Idea</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-d3c87884f861a1e351e44f4bd3aec7fc951' role="tab" data-target='#tabs-d3c87884f861a1e351e44f4bd3aec7fc951'>Data</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-8d9ac05843074d1d3117ad60331564fa832' role="tab" data-target='#tabs-8d9ac05843074d1d3117ad60331564fa832'>Std</a></li><li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-9c94adec0f235622110da33bf6535d54743' role="tab" data-target='#tabs-9c94adec0f235622110da33bf6535d54743'>Sol</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-bfa271cd73835386015eb6e47f3f8f9884' role="tab" data-target='#tabs-bfa271cd73835386015eb6e47f3f8f9884'>Check</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-d3c98b891a99ded757655e1eb08cdd1c960' class="tab-pane fade  ">
            <br />
$\tt{J\textcolor{red}{Yawa}}$<br />
</div><div role="tabpanel" id='tabs-d3c87884f861a1e351e44f4bd3aec7fc951' class="tab-pane fade  ">
            <br />
$\tt{J\textcolor{red}{Yawa}}$<br />
</div><div role="tabpanel" id='tabs-8d9ac05843074d1d3117ad60331564fa832' class="tab-pane fade  ">
            <br />
$\tt{J\textcolor{red}{Yawa}}$<br />
</div><div role="tabpanel" id='tabs-9c94adec0f235622110da33bf6535d54743' class="tab-pane fade active in">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-bfa271cd73835386015eb6e47f3f8f9884' class="tab-pane fade  ">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div>
</div>
</div></p>
<h2>Sol</h2>
<p>对于第一问，考虑抽屉原理。</p>
<p>对于第二问，考虑贪心。</p>
<h2>Code</h2>
<pre><code class="language-cpp">#include &lt;bits/stdc++.h&gt;
using namespace std;
int main()
{
    int x, y;
    cin &gt;&gt; x &gt;&gt; y;
    cout &lt;&lt; max(0LL, y - 9LL * x)
         &lt;&lt; ' ' &lt;&lt; y / 10 &lt;&lt; endl;
    return 0;
}</code></pre>
<h1><span class="external-link"><a class="no-external-link" href="http://czoj.com.cn/p/P1712" target="_blank"><i data-feather="external-link"></i>B. 视界巡航</a></span></h1>
<p><div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-e9a0df96f0a7b35947a8c2f43b13f65d330' role="tab" data-target='#tabs-e9a0df96f0a7b35947a8c2f43b13f65d330'>Idea</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-a6f54a7766ff8ad0bf22fad1c570f7b5391' role="tab" data-target='#tabs-a6f54a7766ff8ad0bf22fad1c570f7b5391'>Data</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-a599f44043891267ede340bde1917df2922' role="tab" data-target='#tabs-a599f44043891267ede340bde1917df2922'>Std</a></li><li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-8b019db2ed20dd7e1affd0b87d17b2e31003' role="tab" data-target='#tabs-8b019db2ed20dd7e1affd0b87d17b2e31003'>Sol</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-5a787c82dd635b6b7787b9bb668dbec1374' role="tab" data-target='#tabs-5a787c82dd635b6b7787b9bb668dbec1374'>Check</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-e9a0df96f0a7b35947a8c2f43b13f65d330' class="tab-pane fade  ">
            <br />
$\tt{z\textcolor{red}{js123}}$<br />
</div><div role="tabpanel" id='tabs-a6f54a7766ff8ad0bf22fad1c570f7b5391' class="tab-pane fade  ">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-a599f44043891267ede340bde1917df2922' class="tab-pane fade  ">
            <br />
$\tt{z\textcolor{red}{js123}}$<br />
</div><div role="tabpanel" id='tabs-8b019db2ed20dd7e1affd0b87d17b2e31003' class="tab-pane fade active in">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-5a787c82dd635b6b7787b9bb668dbec1374' class="tab-pane fade  ">
            <br />
$\tt{B\textcolor{red}{yGones}\ and\ \tt{c\textcolor{red}{hufuzhe}}}$<br />
</div>
</div>
</div></p>
<h2>Sol</h2>
<p>阅读题意可知，这题我们需要动态维护序列的最大值最小值。</p>
<p>每次操作进行修改最大最小并重排的复杂度是错误的，达到了 $\mathcal O(q\times n \log n)$ 的级别。</p>
<p>那么，我们不难想到 C++ 的 STL，multiset。</p>
<p>multiset 与 set 的区别在与，multiset 的元素是可以重复的。根据题意及样例，这里可能会有重复元素出现。</p>
<p>下面介绍一下 multiset：</p>
<ol>
<li>multiset 位于 <code>set</code> 库中。请使用 <code>#include&lt;set&gt;</code>  等或使用包含 <code>set</code> 库的库。</li>
<li><code>multiset&lt;type&gt;mst</code> 建立一个 type 类型的 multiset 容器。type 可以是 <code>int/long long/pair&lt;int,int&gt;/string</code> 等。</li>
<li><code>mst.clear()</code> 清空。</li>
<li><code>mst.insert(x)</code> 向集合插入元素 $x$。</li>
<li><code>mst.empty()</code> 查询集合是否为空。</li>
<li><code>mst.begin()/mst.end()</code> 返回集合开头/结尾迭代器。代码中所用的 <code>*s.begin()</code> 和 <code>*(--s.end())</code> 即为开头与结尾元素。</li>
<li><code>mst.erase(x)</code> 删除迭代器为 $x$ 的元素。</li>
</ol>
<hr />
<p>乱搞做法：平衡树。</p>
<p>赛时码不出来怎么办？C++ 拥有强大的 pb_ds 库，可以直接实现。但是在提交的时候请选择开启 O2 优化的语言，因为 pb_ds 在无 O2 下的表现极劣。</p>
<h2>Code</h2>
<p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-0386b6e1f5c0f59b0ab30e555f83ccc630" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-0386b6e1f5c0f59b0ab30e555f83ccc630" class="collapse collapse-content"><p></p></p>
<pre><code>/*
Auther:  zjs123
Luogu:   754000
QQ:      755328053
*/
#include&lt;bits/stdc++.h&gt;
using namespace std;
int n,t;
int op;
long long x,a,b;
multiset&lt;long long&gt; s;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin&gt;&gt;n&gt;&gt;x;
    for(int i=1;i&lt;=n;i++){
        cin&gt;&gt;a;
        s.insert(a);
    }
    cin&gt;&gt;t;
    while(t--){
        cin&gt;&gt;op&gt;&gt;b;
        if(op==1)x=b;
        else if(op==2){
            s.erase(--s.end());
            s.insert(b);
        }
        else{
            s.erase(s.begin());
            s.insert(b);
        }
        cout&lt;&lt;*(--s.end())+x&lt;&lt;"\n";
    }
    return 0;
}</code></pre>
<p><p></p></div></div></div></p>
<h1><span class="external-link"><a class="no-external-link" href="http://czoj.com.cn/p/P1713" target="_blank"><i data-feather="external-link"></i>C. 恶灵群舞</a></span></h1>
<p><div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-2e3b7a11736ca8945ce21211de7b2ca0610' role="tab" data-target='#tabs-2e3b7a11736ca8945ce21211de7b2ca0610'>Idea</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-46b76897abfdef7e29a5196b6902e55d111' role="tab" data-target='#tabs-46b76897abfdef7e29a5196b6902e55d111'>Data</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-bb537f03f70feaf0751731607b9fbec2732' role="tab" data-target='#tabs-bb537f03f70feaf0751731607b9fbec2732'>Std</a></li><li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-4f8dd7e6f5f2a92c7bdb07c2bddccc40243' role="tab" data-target='#tabs-4f8dd7e6f5f2a92c7bdb07c2bddccc40243'>Sol</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-358e14558adaac7e69ab59118cbbba3d984' role="tab" data-target='#tabs-358e14558adaac7e69ab59118cbbba3d984'>Check</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-2e3b7a11736ca8945ce21211de7b2ca0610' class="tab-pane fade  ">
            <br />
$\tt{z\textcolor{red}{js123}}$<br />
</div><div role="tabpanel" id='tabs-46b76897abfdef7e29a5196b6902e55d111' class="tab-pane fade  ">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-bb537f03f70feaf0751731607b9fbec2732' class="tab-pane fade  ">
            <br />
$\tt{z\textcolor{red}{js123}}$<br />
</div><div role="tabpanel" id='tabs-4f8dd7e6f5f2a92c7bdb07c2bddccc40243' class="tab-pane fade active in">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-358e14558adaac7e69ab59118cbbba3d984' class="tab-pane fade  ">
            <br />
$\tt{B\textcolor{red}{yGones}\ and\ \tt{c\textcolor{red}{hufuzhe}}}$<br />
</div>
</div>
</div></p>
<h2>Sol</h2>
<p>阅读完题意，不难联想到搜索。</p>
<p>因为要求出最右下角的答案，所以我们需要先找出所有答案。</p>
<p>考虑进行搜索，用 $z_{i,j}$ 表示走到 $(i,j)$ 的最小代价。因为每个点最多走不到很多次，穿墙的其实很少，所以时间复杂度 $\mathcal O(nm)$。</p>
<h2>Code</h2>
<p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-61cff1794aaf0c281ca39cc7497bfc5c7" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-61cff1794aaf0c281ca39cc7497bfc5c7" class="collapse collapse-content"><p></p></p>
<pre><code>#include&lt;bits/stdc++.h&gt;
using namespace std;
struct node{
    long long x,y;
    long long va;
};
long long n,m,a,b;
long long aa[120][120];
long long h[120][120];
pair&lt;long long,long long&gt; vis[120][120];
long long dx[]={1,-1,0,0};
long long dy[]={0,0,1,-1};
void dfs(long long x,long long y){
    h[x][y]=1;
    for(long long i=0;i&lt;4;i++){
        long long tx=x+dx[i];
        long long ty=y+dy[i];
        if(tx&gt;0&amp;&amp;tx&lt;=n&amp;&amp;ty&gt;0&amp;&amp;ty&lt;=m&amp;&amp;h[tx][ty]==0&amp;&amp;aa[tx][ty]==0)dfs(tx,ty);
    }
}
queue&lt;node&gt; q;
long long z[120][120];
long long ans=0x3f3f3f3f3f3f3f3f;
long long xx,yy;
main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin&gt;&gt;n&gt;&gt;m&gt;&gt;a&gt;&gt;b;
    memset(z,0x3f,sizeof z);
    for(long long i=1;i&lt;=n;i++){
        for(long long j=1;j&lt;=m;j++){
            cin&gt;&gt;aa[i][j];
        }
    }
    memset(vis,0x3f,sizeof vis);
    dfs(1,1);
    q.push(node{1,1,0});
    vis[1][1]=make_pair(1,0);
    z[1][1]=0;
    while(!q.empty()){
        long long x=q.front().x;
        long long y=q.front().y;
        long long va=q.front().va;
        q.pop();
        for(long long i=0;i&lt;4;i++){
            long long tx=x+dx[i];
            long long ty=y+dy[i];
            if(tx&gt;0&amp;&amp;tx&lt;=n&amp;&amp;ty&gt;0&amp;&amp;ty&lt;=m&amp;&amp;aa[tx][ty]==0&amp;&amp;vis[tx][ty].second&gt;va+a){
                vis[tx][ty].second=va+a;
                q.push(node{tx,ty,va+a});
                z[tx][ty]=min(z[tx][ty],va+a);
            }
            if(tx&gt;0&amp;&amp;tx&lt;=n&amp;&amp;ty&gt;0&amp;&amp;ty&lt;=m&amp;&amp;aa[tx][ty]==1&amp;&amp;aa[tx+dx[i]][ty+dy[i]]==0&amp;&amp;vis[tx+dx[i]][ty+dy[i]].second&gt;va+b){
                tx+=dx[i];
                ty+=dy[i];
                vis[tx][ty].second=va+b;
                q.push(node{tx,ty,va+b});
                z[tx][ty]=min(z[tx][ty],va+b);
            }
        }
    }
    for(int i=n;i&gt;=1;i--){
        for(long long j=m;j&gt;=1;j--){
            if(ans&gt;z[i][j]&amp;&amp;h[i][j]==0){
                ans=z[i][j];
                xx=i;
                yy=j;
            }
        }
    }
    if(ans==0x3f3f3f3f3f3f3f3f){
        cout&lt;&lt;"No";
        return 0;
    }
    cout&lt;&lt;"Yes\n";
    cout&lt;&lt;ans&lt;&lt;" ("&lt;&lt;xx&lt;&lt;","&lt;&lt;yy&lt;&lt;")";
    return 0; 
}</code></pre>
<p><p></p></div></div></div></p>
<h2>Nothing</h2>
<p><img src="http://blog.cyx2009.top/usr/uploads/2023/06/1961236525.png" alt="cyx&amp;wyr の阴谋" loading="lazy"  style=""></p>
<h1><span class="external-link"><a class="no-external-link" href="http://czoj.com.cn/p/P1714" target="_blank"><i data-feather="external-link"></i>D. 狂热派对</a></span></h1>
<p><div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-05ed4266eff146eeeaff0124dedafe0a120' role="tab" data-target='#tabs-05ed4266eff146eeeaff0124dedafe0a120'>Idea</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-2d4e90554177be5b0cfafe229f1391bf401' role="tab" data-target='#tabs-2d4e90554177be5b0cfafe229f1391bf401'>Data</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-6723fd6340f1b6b5ac186a6b5ea47296742' role="tab" data-target='#tabs-6723fd6340f1b6b5ac186a6b5ea47296742'>Std</a></li><li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-282bef99753bf9a1f18cf3f18b15b108123' role="tab" data-target='#tabs-282bef99753bf9a1f18cf3f18b15b108123'>Sol</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-43d4534a728260d423c0f8042a6e90f5634' role="tab" data-target='#tabs-43d4534a728260d423c0f8042a6e90f5634'>Check</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-05ed4266eff146eeeaff0124dedafe0a120' class="tab-pane fade  ">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-2d4e90554177be5b0cfafe229f1391bf401' class="tab-pane fade  ">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-6723fd6340f1b6b5ac186a6b5ea47296742' class="tab-pane fade  ">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-282bef99753bf9a1f18cf3f18b15b108123' class="tab-pane fade active in">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-43d4534a728260d423c0f8042a6e90f5634' class="tab-pane fade  ">
            <br />
$\tt{B\textcolor{red}{yGones}\ and\ \tt{c\textcolor{red}{hufuzhe}}}$<br />
</div>
</div>
</div></p>
<h2>Sol</h2>
<p>其实就是中等的模拟。代码只是变量比较长。</p>
<p>造数据才是大模拟！cyx 为了造数据更容易甚至改了题面。但尽管如此数据生成的代码与 std 的长度相差不大。</p>
<p>我们对于每个记录，按照题意描述检查一下，如果过了就打上标记，并计算时间差得到该题的罚分。被 hack 就取消标记。出现非 CE 或 非 WA on 1 就把这题分数按规定减去 $50$。</p>
<h2>Code</h2>
<p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-aa5cd84afd733e005c3861cd9f18ddb648" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-aa5cd84afd733e005c3861cd9f18ddb648" class="collapse collapse-content"><p></p></p>
<pre><code>/*
Auther:  cyx2009
Luogu:   516346
QQ:      2176807108
*/
#include &lt;bits/stdc++.h&gt;
using namespace std;
int n, m, k;
string Problem_Name[2520];
struct Submission
{
    string Time, Verdict, Problem;
    int Minute;
} CYX_Submission[25020], ZJS_Submission[25020];
string Start_Time;
int INT_Start_Time;
long long CYX_Score, ZJS_Score;
int ZJS_WA[2520];
int CYX_WA[2520];
bool ZJS_Hacked[2520];
bool CYX_Hacked[2520];
bool ZJS_AC[2520];
bool CYX_AC[2520];
int ZJS_Problem_Score[2520];
int CYX_Problem_Score[2520];
map&lt;string, int&gt; Name_to_Id;
int Time_String_to_Int(string Time)
{
    int HH, MM, Minute;
    HH = (Time[0] - '0') * 10 + (Time[1] - '0');
    MM = (Time[3] - '0') * 10 + (Time[4] - '0');
    Minute = HH * 60 + MM;
    return Minute;
}
int Get_Int_Submission_Time(string Time)
{
    int Minute = Time_String_to_Int(Time);
    return Minute &lt; INT_Start_Time ? Minute + 24 * 60 - INT_Start_Time : Minute - INT_Start_Time;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin &gt;&gt; n &gt;&gt; m &gt;&gt; k;
    for (int i = 1; i &lt;= k; i++)
    {
        cin &gt;&gt; Problem_Name[i];
        Name_to_Id[Problem_Name[i]] = i;
    }
    cin &gt;&gt; Start_Time;
    INT_Start_Time = Time_String_to_Int(Start_Time);
    for (int i = 1; i &lt;= n; i++)
    {
        cin &gt;&gt; ZJS_Submission[i].Time &gt;&gt; ZJS_Submission[i].Problem &gt;&gt; ZJS_Submission[i].Verdict;
        ZJS_Submission[i].Minute = Get_Int_Submission_Time(ZJS_Submission[i].Time);
    }
    for (int i = 1; i &lt;= m; i++)
    {
        cin &gt;&gt; CYX_Submission[i].Time &gt;&gt; CYX_Submission[i].Problem &gt;&gt; CYX_Submission[i].Verdict;
        CYX_Submission[i].Minute = Get_Int_Submission_Time(CYX_Submission[i].Time);
    }
    for (int i = 1; i &lt;= n; i++)
    {
        if (ZJS_Submission[i].Verdict == "Hacked")
        {
            if (!ZJS_Hacked[Name_to_Id[ZJS_Submission[i].Problem]])
            {
                CYX_Score += 100;
                ZJS_Hacked[Name_to_Id[ZJS_Submission[i].Problem]] = 1;
                ZJS_AC[Name_to_Id[ZJS_Submission[i].Problem]] = 0;
            }
        }
        else if (ZJS_Submission[i].Verdict == "CompileError")
        {
            continue;
        }
        else if (ZJS_Submission[i].Verdict.size() &gt;= 23 &amp;&amp; ZJS_Submission[i].Verdict.substr(0, 21) == "Wrongansweronpretest(")
        {
            if (ZJS_Submission[i].Verdict[21] == '1')
                continue;
            ZJS_WA[Name_to_Id[ZJS_Submission[i].Problem]]++;
        }
        else if (ZJS_Submission[i].Verdict == "PretestsPassed")
        {
            ZJS_AC[Name_to_Id[ZJS_Submission[i].Problem]] = 1;
            ZJS_Problem_Score[Name_to_Id[ZJS_Submission[i].Problem]] =
                max(
                    Name_to_Id[ZJS_Submission[i].Problem] * 150,

Name_to_Id[ZJS_Submission[i].Problem] * 500 -
                        ZJS_Submission[i].Minute * Name_to_Id[ZJS_Submission[i].Problem] * 2 -
                        ZJS_WA[Name_to_Id[ZJS_Submission[i].Problem]] * 50);
            ZJS_WA[Name_to_Id[ZJS_Submission[i].Problem]]++;
        }
    }
    for (int i = 1; i &lt;= m; i++)
    {
        if (CYX_Submission[i].Verdict == "Hacked")
        {
            if (!CYX_Hacked[Name_to_Id[CYX_Submission[i].Problem]])
            {
                ZJS_Score += 100;
                CYX_Hacked[Name_to_Id[CYX_Submission[i].Problem]] = 1;
                CYX_AC[Name_to_Id[CYX_Submission[i].Problem]] = 0;
            }
        }
        else if (CYX_Submission[i].Verdict == "CompileError")
        {
            continue;
        }
        else if (CYX_Submission[i].Verdict.size() &gt;= 23 &amp;&amp; CYX_Submission[i].Verdict.substr(0, 21) == "Wrongansweronpretest(")
        {
            if (CYX_Submission[i].Verdict[21] == '1')
                continue;
            CYX_WA[Name_to_Id[CYX_Submission[i].Problem]]++;
        }
        else if (CYX_Submission[i].Verdict == "PretestsPassed")
        {
            CYX_AC[Name_to_Id[CYX_Submission[i].Problem]] = 1;
            CYX_Problem_Score[Name_to_Id[CYX_Submission[i].Problem]] =
                max(
                    Name_to_Id[CYX_Submission[i].Problem] * 150,

Name_to_Id[CYX_Submission[i].Problem] * 500 -
                        CYX_Submission[i].Minute * Name_to_Id[CYX_Submission[i].Problem] * 2 -
                        CYX_WA[Name_to_Id[CYX_Submission[i].Problem]] * 50);
            CYX_WA[Name_to_Id[CYX_Submission[i].Problem]]++;
        }
    }
    for (int i = 1; i &lt;= k; i++)
    {
        if (ZJS_AC[i])
        {
            ZJS_Score += ZJS_Problem_Score[i];
        }
        if (CYX_AC[i])
        {
            CYX_Score += CYX_Problem_Score[i];
        }
    }
    cout &lt;&lt; ZJS_Score &lt;&lt; " " &lt;&lt; CYX_Score &lt;&lt; endl;
    if (CYX_Score &gt; ZJS_Score)
    {
        cout &lt;&lt; "cyx" &lt;&lt; endl;
    }
    else if (ZJS_Score &gt; CYX_Score)
    {
        cout &lt;&lt; "zjs" &lt;&lt; endl;
    }
    else
    {
        cout &lt;&lt; "Wow!Same!" &lt;&lt; endl;
    }
    return 0;
}</code></pre>
<p><p></p></div></div></div></p>
<h1><span class="external-link"><a class="no-external-link" href="http://czoj.com.cn/p/P1715" target="_blank"><i data-feather="external-link"></i>E. 绿茵战场</a></span></h1>
<p><div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-8a23ed955f61f11eafb4c9c836dbb52e730' role="tab" data-target='#tabs-8a23ed955f61f11eafb4c9c836dbb52e730'>Idea</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-0cbb9823c22e35b763d0a75fc996b522371' role="tab" data-target='#tabs-0cbb9823c22e35b763d0a75fc996b522371'>Data</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-3046968b1cc68243940b33cdcee1610d672' role="tab" data-target='#tabs-3046968b1cc68243940b33cdcee1610d672'>Std</a></li><li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-779713443388e589d91cf97c3933844c113' role="tab" data-target='#tabs-779713443388e589d91cf97c3933844c113'>Sol</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-8a6cba88bdb4eff7c33cd3acf9c5d41c364' role="tab" data-target='#tabs-8a6cba88bdb4eff7c33cd3acf9c5d41c364'>Check</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-8a23ed955f61f11eafb4c9c836dbb52e730' class="tab-pane fade  ">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-0cbb9823c22e35b763d0a75fc996b522371' class="tab-pane fade  ">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-3046968b1cc68243940b33cdcee1610d672' class="tab-pane fade  ">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-779713443388e589d91cf97c3933844c113' class="tab-pane fade active in">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-8a6cba88bdb4eff7c33cd3acf9c5d41c364' class="tab-pane fade  ">
            <br />
$\tt{B\textcolor{red}{yGones}\ and\ \tt{c\textcolor{red}{hufuzhe}}}$<br />
</div>
</div>
</div></p>
<h2>Hint</h2>
<p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-e5467110d0199c832ab74c292bafbae9100" aria-expanded="true"><div class="accordion-toggle"><span style="">Hint 1</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-e5467110d0199c832ab74c292bafbae9100" class="collapse collapse-content"><p></p>首先，不考虑拜日教皇骗人的情况，我们如何准确查询？<p></p></div></div></div></p>
<p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-fa7aff47912455c4a5c0988e5e28eff65" aria-expanded="true"><div class="accordion-toggle"><span style="">Hint 2</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-fa7aff47912455c4a5c0988e5e28eff65" class="collapse collapse-content"><p></p>当我们学会了不骗的人情况下准确查询后，如何知道拜日教皇有没有骗人呢？<p></p></div></div></div></p>
<h2>Sol</h2>
<p><strong>之后的分析以及代码均由 $0$ 作为起始下标。</strong></p>
<p>先考虑 Hint 1。</p>
<p>我们发现，$2^{31}-1=2,147,483,647$。</p>
<p>也就是说，$10^9$ 只需要大约 $30$ 个 bit 即可。</p>
<p>我们枚举每个 bit 表示的实际数字并查询。检查返回值与 $cnt$ 的大小关系。</p>
<p><strong>如果返回值比 $cnt$ 小，说明这个 bit 被消除了，也就是原数的这个 bit 是 $1$</strong>。</p>
<p>举个例子：$(10)_{10}=(1010)_2$。</p>
<p>$(10-2)_{10}=(8)_{10}=(1000)_2$。</p>
<p>这里我们消去第 $1$ 个 bit，也就是消去了 $2^1=2$。</p>
<p>$f(8)&lt;f(10)$，第 $1$ 个 bit 确实是 $1$。</p>
<p>$(10-1)_{10}=(9)_{10}=(1001)_2$</p>
<p>这里我们消去第 $0$ 个 bit，也就是消去了 $2^0=1$。</p>
<p>$f(9)=f(10)$，第 $0$ 个 bit 不是 $1$。</p>
<p>所以退位什么只会导致 $1$ 个数相同或更多。感兴趣的话可以多找点例子。</p>
<p>综上，我们枚举 $0\sim 29$ 每一个 bit 代表的数 $x$ 并查询。如果得到的结果比 $cnt$ 小，那么 $ans\gets ans+x$，答案加上 $x$。</p>
<p>至此，Hint 1 的解决方法结束。</p>
<pre><code>for(int i=0;i&lt;30;i++)
{
    cout&lt;&lt;"? "&lt;&lt;(1&lt;&lt;max(i-1,0))&lt;&lt;'\n';
    fflush(stdout);
    int c;
    cin&gt;&gt;c;
    if(c==0)bit++,ans|=1&lt;&lt;i;
    if(bit==cnt)break;
}</code></pre>
<hr />
<p>如何处理 Hint 2 所提到的骗人情况呢？</p>
<p>我们发现题目中给了 $60$ 次的询问限制，而 Hint 1所提到的只有 $30$ 次询问。</p>
<p>我们发现，如果每次 <code>? 0</code> $f(n-x)$ 永远不变，一定是 $cnt$。也就是说，一旦返回不是 $1$，也就是不相等，那么一定骗人了。</p>
<p>因此，我们查询 $m$ 次 <code>? 0</code>。因为骗人有周期性，所以想知道之后第 $i$ 条询问的回答是否骗人只需查看第 $i\bmod m$ 个询问的结果。</p>
<h2>Code</h2>
<p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-95ebace3c35efab28abe93684cf01ba770" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-95ebace3c35efab28abe93684cf01ba770" class="collapse collapse-content"><p></p></p>
<pre><code>/*
Auther:  cyx2009
Luogu:   516346
QQ:      2176807108
*/
#include&lt;bits/stdc++.h&gt;
using namespace std;
bool f[50];//是否说谎 
int cnt,m;
int ans,bit; 
int main()
{
    cin&gt;&gt;cnt&gt;&gt;m; 
    for(int i=0;i&lt;m;i++)
    {
        cout&lt;&lt;"? 0\n";
        fflush(stdout);
        int x;
        cin&gt;&gt;x;
        if(x!=1)f[i]=0;
        else f[i]=1;
    }
    for(int i=0;i&lt;30;i++)
    {
        cout&lt;&lt;"? "&lt;&lt;(1&lt;&lt;max(i-1,0))&lt;&lt;'\n';
        fflush(stdout);
        int c;
        cin&gt;&gt;c;
        if(!f[i%m])c=(c+1)%3; 
        if(c==0)bit++,ans|=1&lt;&lt;i;
        if(bit==cnt)break;
        // cout&lt;&lt;bit&lt;&lt;"\n"; 
        // fflush(stdout);
    }
    cout&lt;&lt;"! "&lt;&lt;ans&lt;&lt;'\n';
    fflush(stdout);
    return 0;
}</code></pre>
<p><p></p></div></div></div></p>
<h2>Nothing</h2>
<p>说句闲话，这题是一道大杂烩的原题。</p>
<p>主体部分（Hint 1）为 <span class="external-link"><a class="no-external-link" href="https://codeforces.com/contest/1780/problem/D" target="_blank"><i data-feather="external-link"></i>CF1780D</a></span>，另一部分（Hint 2）为 <span class="external-link"><a class="no-external-link" href="https://codeforces.com/contest/1010/problem/B" target="_blank"><i data-feather="external-link"></i>CF1010B</a></span>。</p>
<p>在写下这段的时候，这两题在 CF 的评分均为 *1800，融合之后的这题，个人认为难度放到提高组也是不为过的。</p>
<p>至于为什么出交互，可能是受到了「信息与未来 2022」启发。<del>小学生比赛都能出交互，普及组模拟赛不能出吗？</del></p>
<h1><span class="external-link"><a class="no-external-link" href="http://czoj.com.cn/p/P1716" target="_blank"><i data-feather="external-link"></i>F. 数码方阵</a></span></h1>
<p><div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-d79385256c93628553ea770fbbb03c5d160' role="tab" data-target='#tabs-d79385256c93628553ea770fbbb03c5d160'>Idea</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-090ae472833bbbcd8f03018ed14efd94801' role="tab" data-target='#tabs-090ae472833bbbcd8f03018ed14efd94801'>Data</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-6ed5b4920d8b5ef28ac3b743c341cd84802' role="tab" data-target='#tabs-6ed5b4920d8b5ef28ac3b743c341cd84802'>Std</a></li><li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-4e0cf38b5060e3caf438bf5faa26fa84663' role="tab" data-target='#tabs-4e0cf38b5060e3caf438bf5faa26fa84663'>Sol</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-bf5f1ecdbfc1cba644db5534b5341da3904' role="tab" data-target='#tabs-bf5f1ecdbfc1cba644db5534b5341da3904'>Check</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-d79385256c93628553ea770fbbb03c5d160' class="tab-pane fade  ">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-090ae472833bbbcd8f03018ed14efd94801' class="tab-pane fade  ">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-6ed5b4920d8b5ef28ac3b743c341cd84802' class="tab-pane fade  ">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-4e0cf38b5060e3caf438bf5faa26fa84663' class="tab-pane fade active in">
            <br />
$\tt{c\textcolor{red}{yx2009}}$<br />
</div><div role="tabpanel" id='tabs-bf5f1ecdbfc1cba644db5534b5341da3904' class="tab-pane fade  ">
            <br />
$\tt{J\textcolor{red}{Yawa}}$<br />
</div>
</div>
</div></p>
<h2>Solution</h2>
<p>首先，这里输入很奇葩。我们可以把它拆成一个序列，设序列长度为 $N=n\times m$。</p>
<p>假设 $A_{N-1}+2 \leq A_N$。可以证明，Xuan 总是会获胜。</p>
<ul>
<li>如果 Xuan 能够使得 $A_N&lt;A_{N-1}$ 并让 Xiang 面对一个必输的局面，Xuan 就会赢。</li>
<li>假设通过使 $a_N&lt;a_{N-1}$ 能够获得所有必胜的局面。然后，如果我们 $a_N \gets a_{N-1}+1$，那么可以从该局面过渡到的所有局面都是必胜的。因此，将 $a_N \gets a_{N-1}+1$ 所得到的局面是必败的。所以，初始局面是必胜的。</li>
</ul>
<p>接下来，考虑当给定一个满足 $a_N=a_{N-1}+1$ 的局面。根据上述证明，Xuan 和 Xiang 不应该给出最大两个元素差为 $2$ 或更大的局面。综上，我们可以假设 $a$ 的最大两个元素的差为 $1$。</p>
<p>然后，我们发现每一步操作都会将 $\max\{a\}$ 减少 $1$。</p>
<p>当 $\max\{a\}=N-1$ 时，该局面无法进行操作，因此可以根据输入中 $a_N$ 和 $N-1$ 的奇偶性差异来确定赢家。</p>
<p>复杂度为 $O(N)$。</p>
<p>但是输入不是有序，进行排序。复杂度为 $O(N \log N)$。</p>
<p>std 和这里的说法有些不同，std 写法更为简洁。</p>
<h2>Code</h2>
<p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-17c2bc44b233e6ea2973fadf9d98bfa841" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-17c2bc44b233e6ea2973fadf9d98bfa841" class="collapse collapse-content"><p></p></p>
<pre><code>#include &lt;bits/stdc++.h&gt;
using namespace std;
int n, m;
int a[300020];
int main()
{
    cin &gt;&gt; n &gt;&gt; m;
    for (int i = 1; i &lt;= n * m; i++)
    {
        cin &gt;&gt; a[i];
    }
    sort(a + 1, a + n * m + 1);
    for (int i = 1; i &lt;= n * m; i++)
    {
        a[i] -= i - 1;
    }
    if (a[n * m] == a[n * m - 1] &amp;&amp; (a[n * m] % 2 == 0))
        puts("Xiang");
    else
        puts("Xuan");
    return 0;
}</code></pre>
<p><p></p></div></div></div></p>

CZOJ Weekly Exercise Round 1 官方题解

A. 玉兔祥云

Sol

Code

B. 视界巡航

Sol

Code

C. 恶灵群舞

Sol

Code

Nothing

D. 狂热派对

Sol

Code

E. 绿茵战场

Hint

Sol

Code

Nothing

F. 数码方阵

Solution

Code

3 条评论

发表评论取消回复
欢迎多多评论捏

CZOJ Weekly Exercise Round 1 官方题解

如何加入 YJOI 共同筹划模拟赛？

机房专用各类下载

常州市程序设计小能手 2023 做题笔记 | CZOI 2023 做题笔记

蓝紫黑の做题笔记

CF1968G1 Division + LCP (easy version)

SP18637 LAWRENCE - Lawrence of Arabia 题解

CF995E Number Clicker 题解

CF17_FINAL_A AKIBA 题解

ABC257_E Addition and Multiplication 2 题解

CZOJ Weekly Exercise Round 1 官方题解

Sol

Code

Sol

Code

Sol

Code

Nothing

Sol

Code

Hint

Sol

Code

Nothing

Solution

Code

3 条评论

发表评论 取消回复 欢迎多多评论捏

CZOJ Weekly Exercise Round 1 官方题解

发表评论取消回复
欢迎多多评论捏