The 10th Shandong Provincial Collegiate Programming Contest

https://codeforces.com/gym/104459

*G. Heap

题意

有一个初始序列，现将每个元素插入堆中。每个元素插入时会按照大根堆或小根堆的规则插入。给出初始序列和最终序列，问每次插入是将它视作大根堆还是小根堆，若有多种可能，输出字典序最小的。

题解

由于每次插入只会影响从当前位置到根的路径上的点，所以直接模拟就可以了。倒序枚举每个元素，找到当前元素最终落在了路径上的哪里，检验路径上经过的元素已经最终位置的父亲是否符合一个统一的大根堆或小根堆规则。如果该元素落在了路径最底下并且它的父亲和它相等，那么都有可能，为了字典序最小，我们认为它是小根堆。

代码

H. Tokens on the Segments

题意

有一些线段 $[l_i,r_i]$，你可以在 $x$ 轴上放置一些不重合的点，每个点只能属于一条线段，问至少有多少条线段满足至少含有一个点。

题解

贪心。

首先，对于 $l$ 相同的线段，我们肯定优先处理 $r$ 较小的，给它们分配点。但是，当 $l$ 上的点指派给某条线段以后，剩下的以 $l$ 为左端点的线段左端点就相当于变成了 $l+1$。也就是说，记已被分配的最大的点右侧的点为 $x$，那么所有左端点小于等于 $x$ 的线段都可以视作左端点为 $x$。此时，要处理的下一条线段是它们中 $r$ 最小的。

所以我们得到了这样的流程：将线段按左端点升序排序。用优先队列维护待处理线段的右端点（按升序排序），同时记录下上面提到的 $x$。每次将优先队列中右端点小于 $x$ 的弹出，若优先队列为空，则将 $x$ 移动到下一条线段的左端点，并且将所有左端点等于 $x$ 的线段加入进来；若优先队列不为空，则将 $x$ 分配给这条线段。

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1e5+5;
pii a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
        sort(a+1,a+n+1);
        int id=1,x=-1,ans=0;
        priority_queue<int,vector<int>,greater<int>> q;
        while(1)
        {
            while(!q.empty()&&q.top()<x) q.pop();
            if(q.empty())
            {
                if(id>n) break;
                x=a[id].first;
            }
            else
            {
                q.pop();
                ans++;
                x++;
            }
            while(id<=n&&a[id].first==x)
            {
                q.push(a[id].second);
                id++;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

*I. Connected Intervals

题意

给出一棵树，求所有的区间 $[l,r](1\leq l\leq r\leq n)$，满足所有标号在 $[l,r]$ 内的点构成的导出子图是一个连通块。

题解

记 $f(l,r)$ 为区间 $[l,r]$ 内的点构成的导出子图的连通块数量。考虑将 $r$ 加入的过程，若 $r$ 有两个相邻的点 $u,v\in [l,r-1]$。那么在 $[l,r-1]$，$u,v$ 一定在两个不同的连通块内。所以，对于 $r$，所有满足 $u\in [l,r-1]$ 的 $u$ 的数量就是由 $f(l,r-1)$ 到 $f(l,r)$ 连通块减少的个数，而每个 $u$ 会对所有 $l\leq u$ 的 $f(l,r-1)$ 产生贡献。

所以，我们从 $1$ 到 $n$ 枚举 $r$，用线段树对所有 $l$ 维护 $f(l,r)$（具体地，维护区间最小值和最小值的个数，统计答案时判断最小值是否为 $1$），这个题就做完了。

代码

*J. Triangle City

题意

有一个三角形网格，要求从 $(1,1)$ 走到 $(n,n)$。要求每条边只经过一次，求一条路径使得经过边的边权之和最大。

题解

把玩一下样例可以发现一种行走方案总可以由网格中刨去一条从 $(1,1)$ 到 $(n,n)$ 的路径得到（因为此时，只有 $(1,1)$ 和 $(n,n)$ 两个奇点，由一笔画的知识可以知道一定可以从 $(1,1)$ 出发走到 $(n,n)$ 结束）。所以要使得边权之和最大，跑出 $(1,1)$ 到 $(n,n)$ 的一条最短路，然后将这些边删除，利用剩下的边跑一遍欧拉回路就可以了。感觉实现起来稍微有点麻烦。

代码

K. Happy Equation

题意

解方程

$$a^x\equiv x^a\pmod {2^p}$$

其中 $1\leq x\leq 2^p$。

数据范围：$1\leq a\leq 10^9,1\leq p\leq 30$。

题解

诈骗题啊！

打表可得 $a$ 为奇数时答案始终为 $1$。

当 $a$ 为偶数时：

若 $x\geq p$，则 $a^x\equiv 0\pmod {2^p}$。只需求解 $x^a\equiv 0\pmod {2^p}$。记 $x$ 中 $2$ 的次数为 $k$，则 $x^a$ 中 $2$ 的次数为 $ka$。原方程即要求 $ka\geq p$，解得 $k\geq \lceil\dfrac{p}{a}\rceil$ 。容易知道，在 $[p,2^p]$ 范围内，$2^k$ 的倍数有 $2^{p-k}-\lfloor\dfrac{p-1}{2^k}\rfloor$ 个。

对于小于 $p$ 的 $x$，直接暴力跑就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fpow(ll a,ll b,ll p)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        ll a,p;cin>>a>>p;
        if(a&1) cout<<1<<'\n';
        else
        {
            ll ans=0;
            for(int i=1;i<p;i++) 
                if(fpow(a,i,(1<<p))==fpow(i,a,(1<<p))) ans++;
            ll k=(p+a-1)/a;
            ans+=(1<<(p-k))-(p-1)/(1<<k);
            cout<<ans<<'\n';
        }
    }
    return 0;
}