A. Hard Way

题意是给定平面三角形，求x轴上的点与三角形边的点连线经过三角形内部的点集长度

容易发现当$y_1=y_2\geq y_3$时，答案为$|x_1-x_2|$，其他情况下均为0

B. Power Walking

题意为给定一个长度为N的序列，将序列中的数分给$K(1\leq K\leq N)$个小孩，求每个小孩分到的序列中不同数字个数之和的最小值

记原序列中不同数字个数为Q，则答案就是min(Q,K)

C. Great Sequence

题意为给定一个长度为N的序列和x，如果$x\times a_i=a_j$那么$a_i$和$a_j$便可两两配对，问最少添加多少个数字，可以使得该序列所有数字均可两两配对完毕

我们可以用一个set容器维护一个序列，map容器维护set容器序列中数字的个数。

然后我们遍历set容器，对于遍历到$a_i$，我们查询map容器中有无$x\times a_i$，如果有，则$x\times a_i$次数减去$a_i$的次数，如果结果小于等于0，则在set容器中擦除$x\times a_i$并添加相反数的答案。否则我们可以直接添加该次数于答案。

D. Repetitions Decoding

题意为给定长度为N的序列，我们可以在第$i$个元素后添加两个相同的数，求操作方法使得一个长度为$2p$的子序列有$a_i=a_{i+p}(i\in[1,p])$，且对任意数均至少属于一个这样的子序列。

观察下面操作：

1 2 3 1 –1 2 3 1 2 2 — 1 2 3 1 2 3 3 2

我们可以发现，一个这样的操作至少能消除序列中的两个数，并使得这两数中的数倒序

于是我们可以模拟解决

E. Anonymity Is Important

对于这题，我们可以用set容器先填充1~N的数字，用数组rb维护问询0 l r 1，数组ans维护每个点的情况

对于0 l r 1的问询，我们可以更新rb[l]=min(rb[l],r)，然后查询rb[l]是否小于set容器中l的后一个数，如果是则修改ans[l]=1表示该病人有病

对于0 l r 0的问询，我们可以逐个删除set容器内$[l,r]$的数并更新相应的ans数组，然后更新set容器中r的后一个数k的rb数组，即rb[k]=min(rb[k],rb[i])$i\in[l,r]$，并判断l前一个数和r后一个数是否生病

对于问询1 x,只需输出ans[x]的情况即可

F. Two Arrays

只学会了乱搞的做法

题意是给定N个长度为M$(M\in[1,5])$的序列，每个序列有个权值$w_i$，如果$i$序列和$j$中的数字均不相同则该两序列可配对，求可配对序列中权值之和的最小值，如果无则输出-1

我们可以先对N*M个数字进行离散化,然后每个数字随机映射到0~(N-1)，用SOS dp计算最小值，重复T次

对于两个序列，不同数字映射到不同数字的概率为$\frac{A_{N}^{10}}{20^{10}}$。

而实际上取N=18,T=12即可

Code

//A
LL tt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(ss,1,tt){
        LL x[3],y[3];
        f(i,0,2)cin>>x[i]>>y[i];
        if(y[0]==y[1]&&y[2]<y[0]){
            cout<<abs(x[0]-x[1])<<"\n";
        }else if(y[2]==y[1]&&y[0]<y[1]){
            cout<<abs(x[2]-x[1])<<"\n";
        }else if(y[2]==y[0]&&y[1]<y[0]){
            cout<<abs(x[2]-x[0])<<"\n";
        }else cout<<"0\n";
    }
    return 0;
}

//B
const LL maxn=3e5+9;
LL tt,n,v[maxn],cnt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(ss,1,tt){
        cin>>n;
        cnt=0;
        map<LL,int> vis;
        f(i,1,n)cin>>v[i];
        f(i,1,n){
            if(!vis[v[i]]){
                cnt+=1;
                vis[v[i]]=1;
            }
        }
        LL ans=cnt;
        f(i,1,n){
            if(i>cnt)ans+=1;
            cout<<ans<<(i==n?"\n":" ");
        }
    }
    return 0;
}

//C
const LL maxn = 2e5 + 9;
LL tt, n, x, a[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> tt;
    f(ss, 1, tt)
    {
        map<LL, int> v;
        set<LL> vis;
        cin >> n >> x;
        LL ans = 0;
        f(i, 1, n)
        {
            cin >> a[i];
            v[a[i]] += 1;
            vis.insert(a[i]);
        }
        for (auto it : vis)
        {
            if (v.count(it * x))
            {
                LL mi = min(v[it], v[it * x]);
                // cout<<it<<"\n";
                v[it] -= mi, v[it * x] -= mi;
                if (v[it * x] == 0)
                {
                    vis.erase(it * x);
                }
            }
            ans += v[it];
        }
        cout << ans << "\n";
    }
    return 0;
}

//D
LL tt, n, mdf;
 
void solve()
{
    cin >> n;
    mdf = 1;
    vi v(n), len;
    vector<pii> ans;
    map<int, int> cnt;
    for (auto &it : v)
        cin >> it, cnt[it] += 1;
    for (auto [_, it] : cnt)
        if (it & 1)
        {
            cout << "-1\n";
            return;
        }
    for(int i=0;i<n;){
        int fnd=find(v.begin()+i+1,v.end(),v[i])-v.begin();
        //cout<<i<<":::"<<fnd<<"\n";
        len.push_back((fnd-i)*2);
        f(j,i+1,fnd-1){
            ans.push_back(mp(mdf+fnd-i+(j-i-1),v[j]));
        }
        reverse(v.begin()+i+1,v.begin()+fnd);
        mdf+=(fnd-i)*2;
        for(int j=fnd;j>i+1;--j){
            v[j]=v[j-1];
        }
        i+=2;
    }
    cout<<ans.size()<<"\n";
    for(auto [x,y]:ans)cout<<x<<" "<<y<<"\n";
    cout<<len.size()<<"\n";
    for(auto it:len)cout<<it<<" ";
    cout<<"\n";
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> tt;
    f(ss, 1, tt)
    {
        solve();
    }
    return 0;
}

//E
LL n,q,opt,l,r,sta;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    set<LL> s;
    vi ans(n+1,-1),rb(n+1,0x3f3f3f3f);
    f(i,1,n+1)s.insert(i);
    f(i,1,q){
        cin>>opt;
        if(opt){
            cin>>l;
            if(ans[l]==-1)cout<<"N/A\n";
            else if(ans[l])cout<<"YES\n";
            else cout<<"NO\n";
        }else{
            cin>>l>>r>>sta;
            if(sta){
                auto itl=*s.lower_bound(l);
                rb[itl]=min(rb[itl],r);
                if(rb[itl]<*s.upper_bound(itl))ans[itl]=1;
            }else{
                auto itr=*s.upper_bound(r);
                for(auto itl=s.lower_bound(l);*itl<=r;){
                    ans[*itl]=0;
                    if(itr!=n+1)rb[itr]=min(rb[itr],rb[*itl]);
                    itl=s.erase(itl);
                }
                if(itr!=n+1&&rb[itr]<*s.upper_bound(itr))ans[itr]=1;
                if(*s.begin()<l){
                    int pre=*prev(s.lower_bound(l));
                    if(rb[pre]<*s.upper_bound(pre))ans[pre]=1;
                }
            }
        }
    }
    return 0;
}

//F
const LL maxn=0x3f3f3f3f3f3f,N=18;
 
LL n,m,ans=maxn,cov[500009],cnt[1<<N],pos[100009];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    std::random_device rd;
    std::default_random_engine eng(rd());
    std::uniform_int_distribution<long long> rnd(0, N-1);
    cin>>n>>m;
    vi mm(n),v[n],pp;
    set<int>s;
    f(i,0,n-1){
        v[i].resize(m);
        for(auto &it:v[i])cin>>it;
        for(auto it:v[i])s.insert(it);
        cin>>mm[i];
    }
    for(auto it:s)pp.pb(it);
    f(i,0,n-1){
        f(j,0,m-1){
            v[i][j]=lower_bound(all(pp),v[i][j])-pp.begin();
        }
    }
    f(sss,1,12){
        for(int i=0;i<=pp.size();++i)cov[i]=rnd(eng);
        for(int i=0;i<(1<<N);++i){cnt[i]=maxn;}
        //cout<<cnt[9];
        f(i,0,n-1){
            pos[i]=0;
            f(j,0,m-1){
                pos[i]|=(1ll<<cov[v[i][j]]);
            }
            cnt[pos[i]]=min(cnt[pos[i]],mm[i]);
            //cout<<cnt[pos[i]]<<":::"<<pos[i]<<"\n";
        }
        for(int i=0;i<N;++i){
            for(int mask=0;mask<(1<<N);++mask){
                if(mask&(1<<i)){
                    cnt[mask]=min(cnt[mask],cnt[mask-(1<<i)]);
                }
            }
        }
        for(int i=0;i<(1<<N);++i){
            ans=min(ans,cnt[i]+cnt[(1<<N)-1-i]);
        }
        //cout<<ans<<"\n";
    }
    if(ans==maxn)cout<<"-1";
    else cout<<ans;
    return 0;
}