B题

DP诶，当时觉得可能是DP，但是太菜了，实在推不出来QAQ

dp[i][j]，指的是  在第i轮改变后，有j个不同的位置

dp[i][j]由dp[i - 1][l]转移得来，由l个不同转为j个不同

从不同的地方选x个，相同的地方选y个

则 x + y = m 且 l - x + y = j

dp[i][j] = dp[i - 1][l] * C(x,n) * C(y,n - l)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int P =  998244353;
ll c[110][110],f[110][110],x,y;
char a[110],b[110];
int n,m,k,T,num;

void init()
{
    for(int i = 0;i < 110; ++i)
    {
        c[i][0] = 1;
        for(int j = 1;j <= i; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % P;
    }
}

int main()
{
    scanf("%d",&T);
    init();
    while(T--)
    {
        memset(f,0,sizeof(f));
        scanf("%d%d%d",&n,&k,&m);
        scanf("%s",a);
        scanf("%s",b);
        num = 0;
        for(int i = 0;i < n; ++i)
            num += (a[i] != b[i]);
        f[0][num] = 1;
        for(int i = 1;i <= k; ++i)
            for(int j = 0;j <= n; ++j)
                for(int l = 0;l <= n; ++l)
                {
                    if(j - l + m < 0) continue;
                    if((j - l + m) & 1) continue;
                    y = (j - l + m) / 2;
                    x = m - y;
                    if(x < 0 || y < 0 || x > l || y > n - l) continue;
                    f[i][j] = (f[i][j] + f[i - 1][l] * c[l][x] % P * c[n - l][y] % P) % P;
                }
        printf("%lld\n",f[k][0]);
    }
    return 0;
}

H题

题意：n个区间的左右端点，第i个区间的纵坐标都为i，选择若干个点，在所有点的横坐标都不相同的前提下，使得每一条线段所代表的区间都至少含有一个点被标记。问被标记的线段最多有多少？

贪心解决是肯定的，但是怎么贪很成问题，赛场上自闭了两个多小时都贪不出来

思路：

首先把区间线段放进优先队列中按照左端点从小到大排序，相等右端点从小到大排序
每一次判断当前点的左端点是不是大于之前出现过的左端点的最大值。如果大于，更新最大值，计数器+1
如果不是，把当前点的左端点更新为之前出现过的左端点的最大值+1，把此点放进优先队列

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;

typedef long long ll;
struct node
{
    ll l,r;
    bool operator < (const node & b) const
    {
        if(l != b.l)
            return l > b.l;
        return r > b.r;
    }
}a;
priority_queue<node>q;
ll T,maxx,ans,n;

int main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld",&n);
        maxx = ans = 0;
        for(int i = 0;i < n; ++i)
        {
            scanf("%lld%lld",&a.l,&a.r);
            q.push(a);
        }
        while(!q.empty())
        {
            a = q.top();
            q.pop();
            if(a.l > maxx)
            {
                maxx = a.l;
                ans++;
            }
            else
            if(a.l < a.r)
            {
                a.l++;
                q.push(a);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

听很多人说二分图匹配能水过去，个人感觉复杂度偏高，可能是数据太水了吧

#include <bits/stdc++.h>
using namespace std;

struct Seg
{
    int beg, en;
} seg[100000];
int t, n;
map<int, int> match;
map<int, bool> vis;

bool DFS(int u)
{
    for (int v = seg[u].beg; v <= seg[u].en; v++)
    {
        if (!vis[v])
        {
            vis[v] = 1;
            if (match[v] == 0 || DFS(match[v]))
            {
                match[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int hungary()
{
    match.clear();
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        vis.clear();
        res += DFS(i);
    }
    return res;
}

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d%d", &seg[i].beg, &seg[i].en);
        printf("%d\n", hungary());
    }
    return 0;
}