题解 | DEFK

情人节也要A+B

https://ac.nowcoder.com/acm/contest/102256/A

D

构造 $5$ 个正数使 int 有符号整数类型溢出至负数，再加至 $0$ 即可。
fun fact:CF div3有道题，这道是求最大的不重叠子数组数量，数组中的数限制在了 $10^5$ ，数组之和最大是 $10^{10}$ ，会溢出但答案可能正确，此时需要针对 INT_MAX 专门卡，出题人没有卡，导致了赛后出现大量hack。链接：https://codeforces.com/contest/2033/problem/D

赛时有人使用C++(g++)输出超限，但实际输出字符并未超限，其实是输出了 $<-10^9$ 或 $>10^9$ 的数……很神秘。

UPD：1000000000 1000000000 1000000000 -1000000000 这种解法会溢出正数再溢出负数，很神奇的溢出回去了，所以目标程序会算出正确答案。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<49<<'\n';
    auto accept=[&]()->void
    {
        cout<<1<<'\n';
        cout<<1<<'\n';
    };
    auto reject=[&]()->void
    {
        cout<<5<<'\n';
        cout<<1000000000<<' '<<1000000000<<' '<<1000000000<<' '<<1000000000<<' '<<294967296<<'\n';
    };
    set<int> st={2,3,5,6,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,30,31,32,33,34,38,39,40,46};
    for(int i=1;i<=49;i++)
    {
        if(st.count(i))reject();
        else accept();
    }
    return 0;
}

E

注意到题目中的数组只开了 $10005$ ，而 $n \leq 2 \times 10^4$ ，只需构造 $n \geq 10005$ 的数据即可。
命题之初是想数组开到 $114514$ ， $n \leq 2 \times 10^5$ ，但是这种情况选手最大可能输出字符可能超过 $10^7$ ，选手程序可能还未输出答案便已运行超时，故现题目缩减到如此规模。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<49<<'\n';
    auto accept=[&]()->void
    {
        cout<<1<<' '<<1<<' '<<1<<'\n';
        cout<<1<<'\n';
    };
    auto reject=[&]()->void
    {
        cout<<10006<<' '<<1<<' '<<1<<'\n';
        for(int i=0;i<10006;i++)cout<<1<<' ';
        cout<<'\n';
    };
    set<int> st={2,3,5,6,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,30,31,32,33,34,38,39,40,46};
    for(int i=1;i<=49;i++)
    {
        if(st.count(i))reject();
        else accept();
    }
    return 0;
}

F

构造 $q=10^4$ ，每组询问 $l=1,r=10^4$ 即可。
命题之初是 $n \leq 2 \times 10^5$ ，检查时间复杂度 $\geq 10^9$ 算运行超时，但是这种情况选手最大可能输出字符可能超过 $10^7$ ，选手程序可能还未输出答案便已运行超时，故现题目缩减到如此规模。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<49<<'\n';
    auto accept=[&]()->void
    {
        cout<<1<<' '<<1<<'\n';
        cout<<1<<'\n';
        cout<<1<<' '<<1<<'\n';
    };
    auto reject=[&]()->void
    {
        cout<<10000<<' '<<10000<<'\n';
        for(int i=0;i<10000;i++)cout<<1<<' ';
        cout<<'\n';
        for(int i=0;i<10000;i++)cout<<1<<' '<<10000<<'\n';
    };
    set<int> st={2,3,5,6,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,30,31,32,33,34,38,39,40,46};
    for(int i=1;i<=49;i++)
    {
        if(st.count(i))reject();
        else accept();
    }
    return 0;
}

K

并非本题出题人，只是想发个本题的技巧（
直接打表很慢，可以使用enum加快打表
enum中第 $i$ 个变量若不赋初值，其的值为 $i-1$ 。
再利用可变参数模板函数建图。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
enum _enum{A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z};
vector<vector<int>> ver(26);
template<class... Args>
void add(int u, int v, Args&&... args)
{
    ver[u].push_back(v);
    ver[v].push_back(u);
    if constexpr (sizeof...(args) >= 2)
        add(args...);
}
int main()
{ 
    ios::sync_with_stdio(false); cin.tie(nullptr); 
    char c;cin>>c;
    add(Q,W,W,E,E,R,R,T,T,Y,Y,U,U,I,I,O,O,P,A,S,S,D,D,F,F,G,G,H,H,J,J,K,K,L,Z,X,X,C,C,V,V,B,B,N,N,M,Q,A,A,W,W,S,S,E,E,D,D,R,R,F,F,T,T,G,G,Y,Y,H,H,U,U,J,J,I,I,K,K,O,O,L,L,P,A,Z,Z,S,S,X,X,D,D,C,C,F,F,V,V,G,G,B,B,H,H,N,N,J,J,M,M,K);
    for(auto it:ver[c-'A'])cout<<(char)(it+'A');
}