icpc网络赛2024-1

M - Find the Easiest Problem

给定一些提交记录，问哪道题被通过的最多

int T = next();
while(T--)
{
    int n = next();
    set<string> st[30];
    rep(i, 0, n)
    {
        string team, problem, stat;
        cin>>team>>problem>>stat;

        if (stat[0] == 'a') st[problem[0]-'A'].insert(team);
    }

    int maxx = 0, prob;
    rep(i, 0, 26) if (st[i].size() > maxx) maxx = st[i].size(), prob = i;

    cout<<(char)(prob+'A')<<endl;
}

A - World Cup

给定足球比赛的对战规则，求在你的黑幕后国足能达到的最高排名。
开始我还以为像乒乓球有半区，结果被橄榄了

显然从小组赛出线的最弱战力是第30，然后开始手算。手算很ez所以略。

int T = next();
while(T--)
{
    vector<int> v;
    rep(i, 0, 32) v.push_back(next());
    int china = v[0];

    sort(v.begin(), v.end(), greater<int>());
    int pos;
    rep(i, 0, 32) if (v[i] == china) pos = i+1;

    if (pos == 1) cout<<1<<endl;
    else if (pos <= 5) cout<<2<<endl;
    else if (pos <= 19) cout<<4<<endl;
    else if (pos <= 26) cout<<8<<endl;
    else if (pos <= 30) cout<<16<<endl;
    else cout<<32<<endl;
}

F - Make Max

给定一个正整数序列\(A\)，可以进行“选择一个子序列\(A_{l...r}\)并把\(A_{l...r}\)中的所有数都替换成\(max\{A_{l...r}\}\)"的操作。求可能的最大操作数。

显然对于一个数\(A_i\)，它要被尽可能小的数替换来让操作数尽可能多。于是可以很自然的想到求出一个数左边和右边第一个比它大的数，位置记为\(l_i, r_i\)，并用小一点的替换它。如果你是把小车造成火箭的ds爱好者，可以使用平衡树。于是可以使用单调栈求出\(l_i, r_i\)。不难发现对于\(A_i\)，\([l_i+1, r_i-1]\)就是它用来进行操作的最大序列。于是对每个位置计数即可。
需要注意的是\(A_{l_i}=A_{r_i}\)的情况需要去重。

int T = next();
while(T--)
{
    int n = next();
    rep(i, 0, n) cin>>w[i], l[i] = 0, r[i] = n-1;

    stack<int> st;
    st.push(0);
    rep(i, 1, n)
    {
        while (st.size() && w[i] > w[st.top()]) st.pop();
        if (st.size()) l[i] = w[i] == w[st.top()] ? i : st.top()+1; // 去重
        st.push(i);
    }

    while(st.size()) st.pop(); // stack没有clear()是认真的？？
    st.push(n-1);
    rev(i, n-2, 0)
    {
        while (st.size() && w[i] > w[st.top()]) st.pop();
        if (st.size()) r[i] = st.top()-1;
        st.push(i);
    }

    int ans = 0;
    rep(i, 0, n) ans += r[i]-l[i];
    cout<<ans<<endl;
}

C - Permutation Counting 4

给定\(n\)组限制\(l_i, r_i\)，要求满足\(p_i \in [l_i, r_i]\)的排列\(p\)的个数的奇偶性。

把这些限制转化为一个\(n*n\)的矩阵\(A\)，其中当\(j \in [l_i, r_i]\)时\(A_{ij}\)为\(1\)，否则为\(0\)。
容易发现答案所求\(p\)的排列个数即为\(perm(A)\)，即积和式。
又因为积和式与行列式展开计算时仅有符号的不同，所以在\(\mod2\) 意义下\(perm(A)=det(A)\)。
于是问题转化为了求\(mod2\)意义下的\(det(A)\)。容易发现如果满秩时\(A\)一定可以转化为一个单位矩阵\(E\)，此时\(det(A)=1\)；如果\(A\)不满秩，即存在线性相关的若干行时，\(det(A)=0\)。
于是问题转化为了求\(A\)是否满秩。又观察到每行的\(1\)都是连续的，所以可以转化为图论问题模拟是否存在线性相关的若干行。
需要@Lcyanstars 教我启发式做法/kel

int fa[U];
int find(int e)
{
    if (fa[e] == e) return e;
    return fa[e] = find(fa[e]);
}
void merge(int a, int b)
{
    fa[find(b)] = find(a);
}


int T = next();
while(T--)
{
    int n = next();
    hrp(i, 0, n) fa[i] = i;

    int ans = 1, l, r;
    hrp(i, 1, n)
    {
        cin>>l>>r;
        if (find(l-1) == find(r)) ans = 0;
        else merge(l-1, r);
    }
    cout<<ans<<endl;
}

G - The Median of the Median of the Median

给定一个正整数序列\(a\)，记\(b_{l,r}\)是\(a_{l...r}\)的中位数，记\(c_{l,r}\)是\(b_{l...r,l...r}\)的中位数，问\(c\)的中位数。
在该题中，中位数为序列中第\(\lceil m/2 \rceil\)小的数。

对于求中位数，可以二分并把所有数根据是否大于当前数转化为\(1,0(-1)\)。于我而言\(0\)更加直观一点。
首先可以用对顶堆先把\(b\)数组求出来，时间复杂度\(O(n^2\log n)\)，不会T。事实上这一步并不必要，可以一起写到check()函数里。
然后写二分框架和check()函数。对于\(b_{i,j}>mid\)，新建一个数组\(t\)把它标记为\(1\)，否则标记为\(0\)，并对\(t\)做一个前缀和\(sum\)。再然后对于每个\(l \leq i \leq j \leq r\)，检查它是大于还是小于等于\(b_{i,j}\)的中位数，如果小于等于就累计。最后判断它是大于还是小于等于\(c\)的中位数。

int w[U], m[U][U], t[U][U], sum[U][U];
int n = next();
hrp(i, 1, n) cin>>w[i];

hrp(i, 1, n)
{
    priority_queue<int> p1;
    priority_queue<int, vector<int>, greater<int>> p2;
    p1.push(w[i]);

    hrp(j, i+1, n)
    {
        int median;
        if ((j-i)%2) median = p1.size() > p2.size() ? p1.top() : p2.top();
        else median = p1.top();
        m[i][j-1] = median;

        if (w[j] > median) p2.push(w[j]);
        else p1.push(w[j]);
        
        if (p2.size() == p1.size()+2) p1.push(p2.top()), p2.pop();
        if (p1.size() == p2.size()+2) p2.push(p1.top()), p1.pop();
    }
    if ((n-i+1)%2) m[i][n] = p1.size() > p2.size() ? p1.top() : p2.top();
    else m[i][n] = p1.top();
}

auto check = [=](int val)
{
    hrp(i, 1, n) hrp(j, i, n) t[i][j] = m[i][j] > val;

    hrp(i, 1, n) hrp(j, 1, n) sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+t[i][j];

    int ova = 0;
    hrp(i, 1, n) hrp(j, i, n) ova += sum[j][j]-sum[i-1][j]-sum[j][i-1]+sum[i-1][i-1] >= (j-i+2)*(j-i+1)/2/2+1;

    return ova < n*(n+1)/2/2+1;
};
/*
auto check = [=](int val)
{
    hrp(i, 1, n) hrp(j, i, n) t[i][j] = m[i][j] > val ? 1 : -1;

    hrp(i, 1, n) hrp(j, 1, n) sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+t[i][j];

    int ova = 0;
    hrp(i, 1, n) hrp(j, i, n) ova += sum[j][j]-sum[i-1][j]-sum[j][i-1]+sum[i-1][i-1] > 0 ? 1 : -1;

    return ova <= 0;
};
*/

sort(w+1, w+n+1);
int l = 1, r = n;
while(l <= r)
{
    int mid = l+r>>1;
    if (check(w[mid])) r = mid-1;
    else l = mid+1;
}

cout<<w[l]<<endl;