Monoxer Programming Contest 2022（AtCoder Beginner Contest 238）（E，F）

E（图）

E

这个题大意就是给你一段区间和，问你可以根据这个区间和得到从\(1\)到\(n\)的和

这个题都说是一个很明显的图论题，但是我一开始真的没看出来，看来是练习不够

题目每次给出的\(l\)和\(r\),可以看做把\(l-1\)和\(r\)看做一条边

我们最后只需要判断从\(0\)是否可以到达\(n\)即可

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=2e5+10;
const int mod=998244353;
int n,q;
vector<int>g[maxn];
bool vis[maxn];
void dfs(int u,int fa)
{
   if(vis[u]) return ;
   vis[u]=true;
   for (auto v:g[u])
   {
      if(v==fa) continue;
      dfs(v,u);
   }
   return ;
}
signed main() 
{
   cin>>n>>q;
   for (int i=1;i<=q;i++)
   {
      int l,r;
      cin>>l>>r;
      g[l-1].push_back(r);
      g[r].push_back(l-1);
   }
   dfs(0,-1);
   if(vis[n])
   {
      cout<<"Yes\n";
   }
   else 
   {
      cout<<"No\n";
   }
   system ("pause");
    return 0;
}

F(dp)

F

这个题大意就是有\(n\)个人，每个人都会有\(2\)次比赛，每次比赛都可以得到一个名次，然后我们会从这\(n\)个人中选择\(k\)个人，但是我们还有一个限制，如果\(a\)两场排名都比\(b\)高,如果选择了\(b\),那么\(a\)也必须选中

问我们有多少种选人方式

这个\(dp\)蛮有意思的

\(dp[i] [j] [k]\)其中\(i\)代表我们已经安排好了前\(i\)个人，并且在这\(i\)中已经选择了\(j\)个人，其中\(k\)代表的是前\(i\)个人还没有被选中的人的最高的第二场排名（最小），那么对于下一个要选择的人，它必须比这个\(k\)还要好，必须赢了前面的那些未选择的人一轮（我们会按照第一轮从小到大的顺序来选择，这样，前面出现的一定比后面出现的排名高），不然，就会让前面的一些排名高的人赢了它两场，并且选了它，那么前面的人也会强制选中，不符合规律，而且也会打乱\(j\)(选中的人数)，所以对于这一轮选中的这个人，必须比\(k\)还要小

对于不选\(i\),我们还需要维护未选中的最高排名\(k\),所以还要更新不选中之后的情况

对了，对于每一个都可选的情况（把\(k\)设置为\(n+1\)，这样都可以选了，也就是初状态，后面要一个都不留，\(k\)不会变，那么对于需要选择的人数和总人数都一样的情况很关键，最后不要漏了）

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=300+10;
const int mod=998244353;
int n,k;
int dp[maxn][maxn][maxn];
int a[maxn],b[maxn],rk[maxn];
signed main() 
{
   cin>>n>>k;
   for (int i=1;i<=n;i++)
   {
      cin>>a[i];
   }
   for (int i=1;i<=n;i++)
   {
      cin>>b[i];
      rk[a[i]]=b[i];
   }
   dp[0][0][n+1]=1;
   for (int i=1;i<=n;i++)
   {
      for (int j=0;j<=k;j++)
      {
         for (int last=0;last<=n+1;last++)//last=n+1的情况是都选
         {
            if(j<k&&rk[i]<last)
            //符合条件一定是逆序的，如果一场比赛赢了，那个下一个比赛就不可以再赢，不然会强制选中，dp每次都会记录选中的人数，一旦出现了这个问题，就很不好统计人数了，所以我们杜绝这个情况
            //我们这个是以第一场比赛的排名从小到大排序的，那么对于这一个人，如果想要被选中，
            //那么在一直第一场比赛失利的情况下（小），那么第二场就必须比之前所有未选中的人的排名还要高，这个我们只需要和最高排名的人比较即可
            {
               dp[i][j+1][last]=(dp[i][j+1][last]+dp[i-1][j][last])%mod;
            }
            int nxt=min(last,rk[i]);
            dp[i][j][nxt]=(dp[i][j][nxt]+dp[i-1][j][last])%mod;
         }
      }
   }
   int ans=0;
   for (int i=0;i<=n+1;i++)//都选，全选完了，一个不剩的情况
   {
      ans=(ans+dp[n][k][i])%mod;
   }
   cout<<ans<<"\n";
   system ("pause");
    return 0;
}