A

分析

我们可以尝试依次把每一只小猫分配到一辆已经租用的缆车上，或者租用一辆缆车安置这种小猫

AC代码

#include<iostream>
#include<algorithm>
#define N 20
using namespace std;
int n,m;
int cat[N],sum[N],ans=N;
bool cmp(int a,int b)
{
    return a>b;
}
void dfs(int u,int k)//第u只猫，k辆车
{
    if(k>=ans) return ;
    if(u==n) 
    {
        ans=k;
        return ;
    }
    
    for(int i=0;i<k;i++)
    if(sum[i]+cat[u]<=m)
    {
        sum[i]+=cat[u]; 
        dfs(u+1,k);
        sum[i]-=cat[u];
    }
    //再来辆车
    sum[k]=cat[u];
    dfs(u+1,k+1);
    sum[k]=0;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>cat[i];
    sort(cat,cat+n,cmp);
    dfs(0,0);
    cout<<ans<<endl;
    
return 0;
}

 

B

分析

因为0到1的距离就是1到0的距离，比较暴力的想法是对每个1跑一下bfs，但是显然会超时，多源BFS能很好的解决这个问题，因为如果我们把所有源点加入队列后，跑出来的路径距离依然是最短路，因为对于每个源点派生出来的分支，只在每一层上遍历的顺序不同，对于不同深度（即距离），也是遵循从上至下，所以跑出来的距离依然是最短路~。~

AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
char a[1009][1009];
int g[1009][1009];
int n,m;
queue<PII> p;


void bfs()
{
        //for(int i=0;i<n;i++)
//           for(int j=0;j<m;j++)
//               {
//                   //cin>>a[i][j];
//                   if(a[i][j]=='1')
//                   { p.push({i,j});
//                    g[i][j]=0;}
//               }
    int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
    while(p.size())
    {
       PII t;
        t=p.front();
       p.pop();
        for(int i=0;i<4;i++)
        {
            int xix=t.first+dx[i],xiy=t.second+dy[i];
            if(xix>=0&&xix<n&&xiy>=0&&xiy<m&&g[xix][xiy]==-1)
               {
                   g[xix][xiy]=g[t.first][t.second]+1;
                   p.push({xix,xiy});
               }
            
        }
    }
}
int main()
{
    memset(g, -1, sizeof g);
    cin>>n>>m;
    for(int i=0;i<n;i++)
          for(int j=0;j<m;j++)
              {
                  cin>>a[i][j];
                  if(a[i][j]=='1')
                  { p.push({i,j});
                   g[i][j]=0;}
              }
    bfs();
    for(int i=0;i<n;i++)
        {  for(int j=0;j<m;j++)
              cout<<g[i][j]<<" ";
              puts("");
              
        }
return 0;
}

 

C

分析

搜索顺序：依次枚举每个字符对应哪个数字
剪枝：
1.从低位向高位依次考虑每一位：
a，b，c，t
被加数 加数 和 进位
(a+b+t) mod n=c

2.由于和也是n位数 ，因此最高位不可以有进位

3.从最低位开始枚举每个未知数

path[N]每个字母对应的数字
q[N] 从低位到高位字母出现的顺序
st[N] 每个数字有没有被用过

AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=30;
int n;
int path[N],q[N];
char e[3][N];
bool st[N];
bool check()
{
    for(int i=n-1,t=0;i>=0;i--)
    {
        int a=e[0][i]-'A',b=e[1][i]-'A',c=e[2][i]-'A';
        if(path[a]!=-1&&path[b]!=-1&&path[c]!=-1)
        {
            a=path[a];b=path[b];c=path[c];
            if(t!=-1)
            {
                if((a+b+t)%n!=c) return false;
                if(!i&&a+b+t>=n) return false;
                t=(a+b+t)/n;
            }
            else 
            {
                if((a+b)%n!=c&&(a+b+1)%n!=c) return false;
                if(!i&&a+b>=n) return false;
            }
        }
        else t=-1;
    }
    
   return true; 
}
bool dfs(int u)
{
    if(u==n) return true;
    for(int i=0;i<n;i++)
    if(!st[i])
    {
        st[i]=true;
        path[q[u]]=i;
        if(check()&&dfs(u+1)) return true;
        st[i]=false;
        path[q[u]]=-1;
        
    }
    return false;
    
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<3;i++)
      cin>>e[i];
      for(int i=n-1,k=0;i>=0;i--)
        for(int j=0;j<3;j++)
        {
            int t=e[j][i]-'A';
            if(!st[t]) 
            {
                st[t]=true;
                q[k++]=t;
            }
            
        }
    memset(st,0,sizeof st);
    memset(path,-1,sizeof path);
    dfs(0);
    for(int i=0;i<n;i++)
       cout<<path[i]<<" ";
    
return 0;
    
}

 

F

分析

Floyd
1.本题的思路就是考虑最小环里面节点编号最大的节点为k,且环里面与k相连的两个点为i，j，环的长度为g[i][k]+g[k][j]+d[j][i];

2.则d[j][i]则表示j到i且经过的节点编号小于k,因为在环中k就是最大的，只能经过小于k的节点了;

3.则这与floyd中k次循环开始前的d[i][j]意义相同;

4.那就不妨在floyd的第一重循环就求一下以k为最大节点编号的环的长度，注意这里的k必须与节点的意义一样：0-n-1或1-n;

AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110,INF=0x3f3f3f;
int n,m;
int d[N][N],g[N][N];
int pos[N][N],path[N],cnt;
void yoy(int a,int b)
{
    if(pos[a][b]==0) return ;
    int c=pos[a][b];
    yoy(a,c);
    path[cnt++]=c;
    yoy(c,b);
}
int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;i++) g[i][i]=0;
    while(m--)
    {
        int a,b,c;
          cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    int res=INF;
    memcpy(d,g,sizeof g);
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++)
                if((long long)d[i][j]+g[j][k]+g[k][i]<res)
                {
                    res=d[i][j]+g[j][k]+g[k][i];
                    cnt=0;
                    path[cnt++]=k;
                    path[cnt++]=i;
                    yoy(i,j);
                    path[cnt++]=j;
                }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(d[i][k]+d[k][j]-d[i][j]<0)
                {
                    d[i][j]=d[i][k]+d[k][j];
                    pos[i][j]=k;
                }
    }
    if(res==INF) puts("No solution.");
    else
    {
        for(int i=0;i<cnt;i++)
            cout<<path[i]<<' ';
        puts("");
    }
return 0;
}

 

H

分析

给定一组字母的大小关系，要你判断是否在某一次读入后，能够判断

1.该字母序列有序，并依次输出；

2.该序列不能判断是否有序；

3.该序列字母次序之间有矛盾，即有环存在。

而这三种形式的判断应该遵循这样的顺序：先判断是否有环（3），再判断是否有序（1），最后才能判断是否能得出结果（2）。

注意：对于（2）必须遍历完整个图！！，而（1）和（3）一旦得出结果，对后面的输入就不用做处理了。

AC代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
vector<int>G[30];//保存图
int in[30];//入度
char ans[30];
int in2[30];//复制上边的度。因为中间会牵扯到度的更改
int i;
int n,m;
int topu()
{
    bool logal=true;//表示是否是全排列
    memcpy(in2,in,sizeof(in));//进行复制操作
    queue<int>Q;
    int cnt=0;//进行数个数
    for(int i=0;i<m;i++)
    {
        if(in[i]==0)
            Q.push(i);
    }
    while(!Q.empty())
    {
        if(Q.size()>1)
            logal=false;
 
 
        int u=Q.front();
        Q.pop();
        ans[cnt++]=u+'A';
 
 
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];
            if(--in2[v]==0)//写错了
                Q.push(v);
        }
    }
    int result=0;
    if(cnt<m)
        result=-1;//说明存在环
    else if(logal==true)//全序
        result=1;
    return result;
}
int main()
{
    string s[1030];
    int flag;
    while(cin>>m>>n,n&&m)
    {
        memset(in,0,sizeof(in));
        if(m==0&&n==0)
            break;
        for(i=0;i<m;i++)
        {
            G[i].clear();
        }
        for( i=0;i<n;i++)
        {
            cin>>s[i];
        }
        for(i=0;i<n;i++)
        {
            int u=s[i][0]-'A',v=s[i][2]-'A';
            G[u].push_back(v);
            ++in[v];
            if((flag=topu())!=0)//说明找到了一个全序，或者不满足的条件
                break;
        }
        ans[m]=0;
       // cout<<flag<<endl<<"*****"<<endl;
        if(flag==1) printf("Sorted sequence determined after %d relations: %s.\n",i+1,ans);
        else if(flag==0) printf("Sorted sequence cannot be determined.\n");
        else if(flag==-1) printf("Inconsistency found after %d relations.\n",i+1);
    }
    return 0;
}