A

分析

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

AC代码

#include<iostream>#include<algorithm>#define N 20using 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;}