2021辽宁省大学生程序设计竞赛

按照 a : b c a:bc a:bc的形式给你三个队伍的顺序（ b > = a > = c b>=a>=c b>=a>=c），输出一种满足所有输入的方案，否则返回No Answer

注意可能题目给的队伍不完全联通，需要用虚拟源点连接

一定要能从源点出发走到所有点

最短路

#include
using namespace std;
const int N=510;
string s;
int n,cnt=0;
int g[N][N];
mapmp;
mapid;
int dist[N],res[N];
bool vis[N];
void get(char c){
    if(!mp.count(c)){
        mp[c]=++cnt;
        id[cnt]=c;
    }
}
bool spfa(int u){
    memset(dist,0x3f,sizeof dist);
    queueq;
    q.push(u); vis[u]=true,dist[u]=0;
    while(q.size()){
        auto t=q.front(); q.pop();
        vis[t]=false;
        for(int i=1;i<=cnt;i++){
            if(g[t][i]!=1){
                if(dist[i]>dist[t]+g[t][i]){
                    dist[i]=dist[t]+g[t][i];
                    res[i]=res[t]+1;
                    if(res[i]>=cnt+1) return false;
                    if(!vis[i]){
                        vis[i]=true;
                        q.push(i);
                    }
                }
            }
        }
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i
        for(int j=1;j
        cin>>s;
        get(s[0]);get(s[2]);get(s[3]);
        g[mp[s[0]]][mp[s[2]]]=-1;
        g[mp[s[3]]][mp[s[0]]]=-1;
    }
    for(int i=1;i<=cnt;i++) g[cnt+1][i]=0;
    if(!spfa(cnt+1)) cout<<"No Answer";
    else{
        int ma=dist[1];
        for(int i=1;i<=cnt;i++) ma=min(ma,dist[i]);
        for(int i=ma;i<=0;i++){
            for(int j=1;j<=cnt;j++){
                if(dist[j]==i) cout< 
最长路
 
#include
using namespace std;
const int N=510;
string s;
int n,cnt=0;
int g[N][N];
mapmp;
mapid;
int dist[N],res[N];
bool vis[N];
void get(char c){
    if(!mp.count(c)){
        mp[c]=++cnt;
        id[cnt]=c;
    }
}
bool spfa(int u){
    memset(dist,-0x3f,sizeof dist);
    queueq;
    q.push(u); vis[u]=true,dist[u]=0;
    while(q.size()){
        auto t=q.front(); q.pop();
        vis[t]=false;
        for(int i=1;i<=cnt;i++){
            if(g[t][i]!=-1){
                if(dist[i]
                    dist[i]=dist[t]+g[t][i];
                    res[i]=res[t]+1;
                    if(res[i]>=cnt+1) return false;
                    if(!vis[i]){
                        vis[i]=true;
                        q.push(i);
                    }
                }
            }
        }
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n;
    memset(g,-1,sizeof g);
    while(n--){
        cin>>s;
        get(s[0]);get(s[2]);get(s[3]);
        g[mp[s[2]]][mp[s[0]]]=1;
        g[mp[s[0]]][mp[s[3]]]=1;
    }
    for(int i=1;i<=cnt;i++) g[cnt+1][i]=0;
    if(!spfa(cnt+1)) cout<<"No Answer";
    else{
        int ma=dist[1];
        for(int i=1;i<=cnt;i++) ma=max(ma,dist[i]);
        for(int i=0;i<=ma;i++){
            for(int j=1;j<=cnt;j++){
                if(dist[j]==i) cout< 
放棋子（组合数+dp）4星（正确性未解决） 
题意： 
已知一个
    
     
      
       
        n
       
       
        ∗
       
       
        m
       
      
      
       n*m
      
     
    n∗m的棋盘，问在任意一个
    
     
      
       
        n
       
       
        ∗
       
       
        n
       
      
      
       n*n
      
     
    n∗n的区域内都有k个棋子的情况下的方案数是多少
 

    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        100
       
      
      
       1leq nleq 100
      
     
    1≤n≤100
 

    
     
      
       
        n
       
       
        ≤
       
       
        m
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         18
        
       
      
      
       nleq m leq 10^{18}
      
     
    n≤m≤1018
 

    
     
      
       
        0
       
       
        ≤
       
       
        k
       
       
        ≤
       
       
        n
       
       
        ∗
       
       
        n
       
      
      
       0leq kleq n*n
      
     
    0≤k≤n∗n
 
题解： 
显然，第n+1列能放的棋子数和第1列的棋子数相同
 
设
    
     
      
       
        f
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       f[i][j]
      
     
    f[i][j]为前
    
     
      
       
        i
       
      
      
       i
      
     
    i列摆放了
    
     
      
       
        j
       
      
      
       j
      
     
    j个棋子的方案数，则有：
 KaTeX parse error: Undefined control sequence:  at position 62: …    ,   ̲ ̲g[z]为C_n^z 
 由于列数很大，所以我们需要进行优化：
 
当
     
      
       
        
         m
        
        
         =
        
        
         n
        
       
       
        m= n
       
      
     m=n时，可以直接求得
当
     
      
       
        
         m
        
        
         >
        
        
         n
        
       
       
        m>n
       
      
     m>n时，因为第
     
      
       
        
         i
        
       
       
        i
       
      
     i列的棋子数和第
     
      
       
        
         i
        
        
         %
        
        
         n
        
       
       
        i%n
       
      
     i%n列的棋子数相同，所以我们可以将
     
      
       
        
         i
        
        
         (
        
        
         m
        
        
         >
        
        
         n
        
        
         )
        
       
       
        i(m>n)
       
      
     i(m>n)
 
的部分直接放在
    
     
      
       
        i
       
       
        %
       
       
        n
       
      
      
       i%n
      
     
    i%n的位置
 
 
 
证明正确性：（未能证明）
 
 
1）当我们分开算时，假设我们已经求出来
      
       
        
         
          n
         
        
        
         n
        
       
      n列存放
      
       
        
         
          k
         
        
        
         k
        
       
      k个棋子的方案数为
      
       
        
         
          x
         
        
        
         x
        
       
      x，则
      
       
        
         
          n
         
        
        
         n
        
       
      n后面列的每种方案对最终答案的贡献应该是与
      
       
        
         
          x
         
        
        
         x
        
       
      x相乘，即
 
 

      
       
        
         
          a
         
         
          n
         
         
          s
         
         
          =
         
         
          x
         
         
          ∗
         
         
          
           p
          
          
           1
          
         
         
          ∗
         
         
          
           p
          
          
           i
          
         
         
          ∗
         
         
          .
         
         
          .
         
         
          .
         
         
          ∗
         
         
          
           p
          
          
           
            n
           
           
            −
           
           
            1
           
          
         
         
          ,
         
         
          
           p
          
          
           i
          
         
         
          为
         
         
          第
         
         
          (
         
         
          t
         
         
          %
         
         
          n
         
         
          ,
         
         
          t
         
         
          >
         
         
          n
         
         
          )
         
         
          =
         
         
          i
         
         
          列
         
         
          对
         
         
          应
         
         
          方
         
         
          法
         
         
          的
         
         
          方
         
         
          案
         
         
          数
         
        
        
         ans=x*p_{1}*p_{i}*...*p_{n-1},p_i为第(t%n,t>n)=i列对应方法的方案数
        
       
      ans=x∗p1​∗pi​∗...∗pn−1​,pi​为第(t%n,t>n)=i列对应方法的方案数
 
 
2）当我们合起来算时，按照以上dp的思路，设第
      
       
        
         
          i
         
        
        
         i
        
       
      i列出现了
      
       
        
         
          y
         
        
        
         y
        
       
      y次，即
      
       
        
         
          g
         
         
          [
         
         
          z
         
         
          ]
         
         
          =
         
         
          (
         
         
          
           C
          
          
           n
          
          
           z
          
         
         
          
           )
          
          
           y
          
         
        
        
         g[z]=(C_n^z)^y
        
       
      g[z]=(Cnz​)y，
 
 
#include
#define endl 'n'
#define x first
#define y second
#define INF 0x3f3f3f3f
#define mod 1000000007
#define int long long
using namespace std;
typedef long long ll;
typedef pairPII;
const int N=110,M=N*N;
int n,m,k;
int c[N][N],f[N][M];
int g[N][3];
int qsm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    for(int i=0;i
        for(int j=0;j<=i;j++){
            if(!j) c[i][j]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        }
    }
    cin>>n>>m>>k;
    int d=m/n,y=m%n;//d代表有多少轮
    for(int i=0;i<=n;i++){//预处理出每一列的放法
        g[i][0]=qsm(c[n][i],d);
        g[i][1]=qsm(c[n][i],d+1);
    }
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            for(int z=0;z<=min(n,j);z++){
                f[i][j]=(f[i][j]+f[i-1][j-z]*g[z][i<=y]%mod)%mod;
            }
        }
    }
    cout< 
制造游戏币（dfs+完全背包）4星 
题意： 
有
    
     
      
       
        n
       
      
      
       n
      
     
    n个物品，有
    
     
      
       
        m
       
      
      
       m
      
     
    m个要求：
 

    
     
      
       
        (
       
       
        
         b
        
        
         i
        
       
       
        ,
       
       
        
         c
        
        
         i
        
       
       
        )
       
      
      
       (b_i,c_i)
      
     
    (bi​,ci​)代表物品
    
     
      
       
        
         b
        
        
         i
        
       
      
      
       b_i
      
     
    bi​的个数必须严格大于
    
     
      
       
        
         c
        
        
         i
        
       
      
      
       c_i
      
     
    ci​
 
每一个物品能选无数次
 
问构成
    
     
      
       
        t
       
      
      
       t
      
     
    t元的方案数
 
题解： 
给有关系的物品之间建边，dfs将物品组（选了
    
     
      
       
        
         c
        
        
         i
        
       
      
      
       c_i
      
     
    ci​必须选
    
     
      
       
        
         b
        
        
         i
        
       
      
      
       b_i
      
     
    bi​）构建出来，再用完全背包求方案数
 
注意当一个物品都不选时也要满足关系，将必须存在的价格先在k中减去
 
写懵了，文字描述一下dfs过程
 
因为要满足严格大于的关系，所以我们当我们不选任何物品时，也有必须要选择的物品，我们先处理出这些物品，从k中减去，这样就可以将有边的物品看作一个大物品选或不选
 
实际上可能出现存在环的现象
 
#include
#define endl 'n'
#define x first
#define y second
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef pairPII;
const int N=310,M=1e5+10;
int h[N],e[N],ne[N],idx;
int n,m,k;
ll g[N],f[M];
bool vis[N];
int fa[N];//并查集判环
int find(int x){
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u){
    for(int i=h[u];~i;i=ne[i]){//u的数量要严格大于j,所以选j时一定要选一个u
        int j=e[i];
        g[j]+=g[u];
        dfs(j);
    }
    if(h[u]!=-1) k-=g[u];//将不选任何物品时必须存在的物品从k中减去
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) cin>>g[i],fa[i]=i;
    while(m--){
        int a,b; cin>>a>>b;
        add(a,b);vis[b]=true;
        a=find(a),b=find(b);
        if(a!=b) fa[a]=b;//并查集判环
        else{
            cout<<0;
            return 0;
        }
    }
    
    for(int i=1;i<=n;i++){
        if(!vis[i]) dfs(i);
    }
    if(k<0) cout<<0;
    else{
        f[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=g[i];j<=k;j++){
                f[j]=(f[j]+f[j-g[i]])%mod;
            }
        }
        cout< 
阿强的路（多条件状态转移+floyd变式）4星 
题意： 
已知一个n个点m条边无重边无自环的无向图，并给出点权和边权，求出任意两点间的难度
 
难度定义为两点间的路径中能得到的
    
     
      
       
        最
       
       
        大
       
       
        点
       
       
        权
       
       
        ∗
       
       
        最
       
       
        大
       
       
        边
       
       
        权
       
      
      
       最大点权*最大边权
      
     
    最大点权∗最大边权的最小值
 
题解： 
~~太棒辣不是求最短路径上得最大点权*最大边权~
 
如何对floyd进行变形？ 
floyd是枚举任意两点，通过第三个点更新两点间得最小（最大）距离——点
     
      
       
        
         i
        
       
       
        i
       
      
     i到点
     
      
       
        
         j
        
       
       
        j
       
      
     j只经过前
     
      
       
        
         k
        
       
       
        k
       
      
     k个点的最小（最大）距离
 
floyd基于dp的思想从前往后枚举第三点
    
     
      
       
        k
       
      
      
       k
      
     
    k，因为要找最大点权，所以我们可以将点按照点权进行排序，这样枚举第三点时一定是从最大点权更新
 
我们还需要记录最大边权，裸的floyd
    
     
      
       
        g
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       g[i][j]
      
     
    g[i][j]代表的是当前的最小距离，这里我们让
    
     
      
       
        g
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       g[i][j]
      
     
    g[i][j]表示当前的最大边权即可
 
#include
#define endl 'n'
#define x first
#define y second
#define INF 0x3f3f3f3f
#define mod 1000000007
#define int long long
using namespace std;
typedef long long ll;
typedef pairPII;
const int N=510;
struct P{
    int w,id;
    bool operator<(const P&x)const{
        return w
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    memset(g,0x3f,sizeof g);
    memset(f,0x3f,sizeof f);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        p[i]={w[i],i};
    }
    sort(p+1,p+1+n);
    while(m--){
        int a,b,c; cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],(ll)c);
        f[a][b]=f[b][a]=min(f[a][b],g[a][b]*max(w[a],w[b]));
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(g[i][j]>max(g[i][p[k].id],g[p[k].id][j])){//i-j内的最大边权一定是i-k或k-j内的最大边权
                    g[i][j]=max(g[i][p[k].id],g[p[k].id][j]);
                    f[i][j]=f[j][i]=min(f[i][j],g[i][j]*max({w[i],w[j],p[k].w}));//前k个点的最大点权一定是p[k].w
                }
                //如果g[i][j]
        for(int j=1;j<=n;j++){
            if(i==j) f[i][j]=0;
            if(g[i][j]>1e18) f[i][j]=-1;
            cout<