C传送门

题意是给定1-n的序列，附加n个0，每次a序列可以任意取出一张加入b序列尾部并且从b序列头部取出一张加入a序列。问最少多少步能完成排序。

分类贪心。第一类情况是b序列的尾部已经是一个完整的上升序列，并且a序列和b序列前部能顺序完成拼出上升序列，这种情况模拟一下，最后判断是否能成立。

另一种情况是必须把b序列取出一定的数。这种情况，对于每个取到的数子a[i] = k.他在第一个数字1加入a序列以后，最迟要在之后k步内取到，所以取如a序列的数字的步数就是tmp = max(tmp, i – a[i] + 1),在最大一个步数的数字取完后，就能保证顺序加入b序列的尾部时能完成排序，此时答案是tmp + n;因为加入n个数字需要n步。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int a[maxn], b[maxn], vis[maxn];
int n; 
int go()
{
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(b[i]) ans = max(ans, i - b[i] + 1);
    }
    return ans + n;
}
int go2()
{
    set<int> st;
    for(int i = 1; i <= n; i++) if(a[i]) st.insert(a[i]);
    int ans = 0;
    int p = 1;
    while(st.size() && ans < n)
    {
        b[n + p] = *st.begin();
        st.erase(st.begin());
        if(b[p]) st.insert(b[p]);
        ans++, p++;
    }
    int t = 1;
    while(b[t] != 1) t++;
    for(int i = t, j = 1; j < n; i++, j++) if(b[i] + 1 != b[i + 1]) return INT_MAX;
    return ans;
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    cout << min(go(), go2());
}

D传送门

题意是说给一颗树关系。边不交叉。问节点形成的圆排列有多少种是满足条件的。

需要观察到的是因为在圆上而且边不交叉。所以每个节点的儿子一定是连续的一段区间，儿子之间是可以任意交换的。答案就是n * \prod{!son[p]}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 233;
int n; 
ll a[maxn], p[maxn];
ll mod = 998244353;
int main()
{
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int x, y; cin >> x >> y;
        a[x]++, a[y]++;
    }
    p[0] = 1;
    for(int i = 1; i <= n; i++) p[i] = (p[i - 1] * i) % mod;
    ll ans = 1;
    for(int i = 1; i <= n; i++)
    {
        ans = (ans * p[a[i]]) % mod;
    }
    cout << ans * n % mod;
}