目录

L1

L1-1 今天我要赢                                                                       -分数 5

L1-2 种钻石                                                                              -分数 5

L1-3 谁能进图书馆                                                                   -分数 10

L1-4 拯救外星人                                                                       -分数 10

L1-5 试试手气                                                                           -分数 15

L1-6 斯德哥尔摩火车上的题                                                     -分数 15

L1-7 机工士姆斯塔迪奥                                                            -分数 20

L1-8 静静的推荐                                                                       -分数 20

L2

L2-1 插松枝                                                                              -分数 25

L2-2 老板的作息表                                                                   -分数 25

L2-3 龙龙送外卖                                                                       -分数 25

L2-4 大众情人                                                                           -分数 25

L3

L3-1 千手观音                                                                           -分数 30

L3-2 关于深度优先搜索和逆序对的题应该不会很难吧这件事   -分数 30

L3-3  教科书般的亵渎                                                               -分数 30

L1

L1-1 今天我要赢                                                                       -分数 5

签到题

代码：

  

L1-2 种钻石                                                                              -分数 5

代码：

L1-3 谁能进图书馆                                                                   -分数 10

比较麻烦，就是按照题目要求写if

代码：

L1-4 拯救外星人                                                                       -分数 10

代码：

L1-5 试试手气                                                                           -分数 15

代码：

L1-6 斯德哥尔摩火车上的题                                                     -分数 15

代码：

L1-7 机工士姆斯塔迪奥                                                            -分数 20

由于每次只会涂一行或者一列所以可以发现安全的位置是n*m-（n*涂了一列的次数-m*涂了一行的次数+涂了一列的次数*涂了一行的次数）；

代码：

L1-8 静静的推荐                                                                       -分数 20

可以先把可以通过pat考试通过的添加到答案，然后由于只进行K轮，每次都区一个严格递增数列，那么只需要对每个分数的人数与K取最小值加到答案即可

代码：

  

L2

L2-1 插松枝                                                                              -分数 25

模拟题 ，根据题目要求模拟即可，每次先从小盒子里取松针，如果没有就从推送器上取......值得注意的是有3个要输出松枝的条件。

代码：

//---------------------------↓乱定义区------------------------------------
int n,m,k;
stackhe;
queuetui;
dequezhi;
//---------------------------↓乱写乘区------------------------------------
void solve()
{
    cin>>n>>m>>k;
    for(int i=1,j;i<=n;i++)
    {
        cin>>j;
        tui.push(j);
    }
    for(int i=1;i<=n;i++)//一共要插n个，保证一回合插一个即可
    {
        kai:{}
        int f=0;
        if(!he.empty() && (zhi.empty() || zhi.back()>=he.top()))
        {
            f=1;
            zhi.push_back(he.top());he.pop();
        }
        if(!f)
        {
            if(!tui.empty() && (zhi.empty()|| zhi.back()>=tui.front()))
            {
                f=1;
                zhi.push_back(tui.front());tui.pop();
            }else
            {
                while(!tui.empty() && he.size()=tui.front()))
                {
                    f=1;
                    zhi.push_back(tui.front());tui.pop();
                }
            }
        }
        if(!f || zhi.size()==k ||i==n)
        {
            int e=0;
            while(!zhi.empty())
            {
                if(!e)e=1;
                else cout<<" ";
                cout<>tn;
	while(tn--)
    {
        solve();
    }
	return 0;
}

L2-2 老板的作息表                                                                   -分数 25

代码：

//---------------------------↓乱定义区------------------------------------
int n,kai=0;
set>st;
string s;
//---------------------------↓乱写乘区------------------------------------
void solve()
{
   cin>>n;
   getchar();
   for(int i=0;i<=n;i++)
   {
       getline(cin,s);
       int a,b,c,d,e,f;
       sscanf(s.c_str(),"%d:%d:%d - %d:%d:%d",&a,&b,&c,&d,&e,&f);
       st.insert({a*3600+b*60+c,d*3600+e*60+f});
   }
   for(auto [a,b]:st)
   {
       if(kai

L2-3 龙龙送外卖                                                                       -分数 25

对于节点a，b，如果a，b互不是对方祖先，可以发现，不论先去a还是b，都得在回去他们的最近公共祖先，然后在去往另一个点，所以每条边对答案的贡献都是2，由于送完最后一趟后不用返回，那么只需要减去从根节点到最远需要到达的点的距离即可。我们可以先从根节点dfs求出到所有点的最短距离，然后根据每个需要到达的点，向上走到没有走过的点统计每条边的贡献即可。

代码：

//---------------------------↓乱定义区------------------------------------
int n,m,root;
int dis[maxn];
int fa[maxn],f[maxn];
vectorv[maxn];
//---------------------------↓乱写乘区------------------------------------
void dfs(int rt,int len)
{
    dis[rt]=len;
    for(int i:v[rt])
    {
        dfs(i,len+1);
    }
}
void solve()
{
   cin>>n>>m;
   for(int i=1,j;i<=n;i++)
   {
       cin>>j;
       fa[i]=j;
       if(j==-1)root=i;
       else v[j].pd(i);
   }
   dfs(root,0);
   f[root]=1;
   int ans=0,ma=0;
   for(int i=1,j;i<=m;i++)
   {
       cin>>j;
       ma=max(ma,dis[j]);
       while(!f[j])
       {
           f[j]=1,j=fa[j],ans+=2;
       }
       cout<

L2-4 大众情人                                                                           -分数 25

 由于朋友的朋友可以通过中间的朋友传递距离，所以可以看出这是个多源路径最短路问题，直接Floyd，然后根据题目要求，找到答案即可。

代码：

//---------------------------↓乱定义区------------------------------------
int n;
string s;
int k;
int f[maxn];
ll dp[maxn][maxn];
//---------------------------↓乱写乘区------------------------------------
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)dp[i][j]=0xfffffffffffff;
    for(int i=1;i<=n;i++)dp[i][i]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>s>>k;
        if(s[0]=='F')f[i]=1;
        for(int j=0,a,b;j>s;
            sscanf(s.c_str(),"%d:%d",&a,&b);
            dp[i][a]=b;
        }
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i!=j)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
    }
    vectorans1,ans2;
    ll m1=0xfffffffffffff,m2=0xfffffffffffff;
    for(int i=1;i<=n;i++)
    {
        ll ma=0;
        for(int j=1;j<=n;j++)
        {
            if(i==j||f[i]==f[j])continue;
            ma=max(ma,dp[j][i]);
        }
        if(f[i])
        {
            if(m1>ma)m1=ma,ans1.clear();
            if(m1==ma)ans1.pd(i);
        }else
        {
            if(m2>ma)m2=ma,ans2.clear();
            if(m2==ma)ans2.pd(i);
        }
    }
    int e=0;
    for(auto i:ans1)
    {
        if(!e)e=1;
        else cout<<" ";
        cout< 
 
L3 
L3-1 千手观音                                                                           -分数 30 
 
 
拓扑排序题 ，由于给的每个数字都是严格递增的，那么对于每个位数相同的数字，都可以连边，计算入度，例如，1，123，132，222，这3个数字，我们根据123，132，可以推断出2<3,根据123,222可以推断出1<2,那么可以推出1<2<3.，而1和其他数位数不同，不可以直接推出关系。连完边后拓扑排序，因为给出的拓扑排序不一定是可以推出唯一拓扑序的，所以根据题目要求还需要对于同时在queue里的字母，按字典序排序，我们把queue换成priority_queue即可。
 
代码：
 
//---------------------------↓乱定义区------------------------------------
int n,cnt;
unordered_mapid;
unordered_mapname;
vectorv[maxn],ve[maxn];
set>st;
int ru[maxn];
//---------------------------↓乱写乘区------------------------------------
void tp()
{
    priority_queue,greater>p;
    for(int i=1;i<=cnt;i++)
    {
        if(ru[i]==0)p.push(name[i]);
    }
    int e=0;
    while(!p.empty())
    {
        string now=p.top();p.pop();
        if(!e)e=1;
        else cout<<".";
        cout<>n;
    cnt=0;
    for(int i=0;i>s;
        for(int j=0;j 
 
L3-2 关于深度优先搜索和逆序对的题应该不会很难吧这件事   -分数 30 
 
 
 
 根据样例解释可以发现，（1）对于节点5，他的子节点1，2，无论如何排列，在dfs序中都必在5后，而4，对于1，2节点，不是在任何dfs中都有贡献的。
 
(2)对于节点3、5，由于3是5的双亲节点，那么根据（1）可以知道3必在5的前面，且在所有dfs序排列中都不会有贡献，对于节点5，1，就是在所有dfs序排列中都会产生贡献
 
(3)在一个1-n不重复序列的全排列中一个数字出现在另一个数字前的概率是1/2,也就是会有n！/ 2个逆序对，而在这个dfs排列中，对于2个非有祖先关系的2个点，其中一个点出现在另一个节点的概率可以发现也是是1/2,又由于2个节点值不同，所以必然会在一半的排列中会产生贡献。
 
我们不妨对与所有节点对，都假设都会在一半的dfs序排列中都会产生贡献，那么就不需要考虑（3）这个条件了，只需要看对于节点对中有祖先关系的，进行考虑。
 
对于祖先节点，和一个子节点，如果祖先节点的值比子节点大，那么我们少计算了一半贡献，如果小，那么我们多计算了一半贡献，只需要对应的加减即可。
 
那么我们只需要dfs遍历，然后通过树状数组（Fenwick Tree / Binary Indexed Tree）计算这个节点的祖先节点有多少比他大，有多少比他小即可。复杂度O（n*log(n)）
 
代码：
 
//---------------------------↓乱定义区------------------------------------
int n,r;
vectorv[maxn];
ll c[maxn],fuda[maxn],fuxiao[maxn],jc[maxn],num[maxn];
ll ans;
//---------------------------↓乱写乘区------------------------------------
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,ll e)
{
    for(;x<=n;x+=lowbit(x))c[x]+=e;
}
ll sum(int x)
{
    ll ans=0;
    for(;x>0;x-=lowbit(x))ans+=c[x];
    return ans;
}
ll ksm(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
void dfs(int rt,int fa)
{
    fuda[rt]=sum(n)-sum(rt);
    fuxiao[rt]=sum(rt-1);
    num[rt]=1;
    add(rt,1);
    for(int &i:v[rt])
    {
        if(i==fa)continue;
        dfs(i,rt);
        num[rt]=num[rt]*num[i]%mod;
    }
    add(rt,-1);
    num[rt]=num[rt]*jc[v[rt].size()-1]%mod;
}
void solve()
{
    cin>>n>>r;
    jc[0]=1;
    for(int i=1;i<=n;i++)jc[i]=jc[i-1]*i%mod;
    for(int i=1,a,b;i>a>>b;
        v[a].pd(b);
        v[b].pd(a);
    }
    v[r].pd(0);
    dfs(r,0);

    ans=0;
    ll two=ksm(2,mod-2);
    ans=1ll*n*(n-1)/2%mod*num[r]%mod*two%mod;

    for(int i=1;i<=n;i++)
    {
        ans+=fuda[i]*num[r]%mod*two%mod;
        ans-=fuxiao[i]*num[r]%mod*two%mod;
        ans=(ans+mod)%mod;
    }
    cout<
 
 
L3-3  教科书般的亵渎                                                               -分数 30 
 
 
待补状态┭┮﹏┭┮,只想到暴力骗7分，不知道dp咋推