2019河北省大学生程序设计竞赛(部分题解)

2019河北省大学生程序设计竞赛

• B.Icebound and Sequence
  B题题解

• G.点我
  签到题

• H.天神的密码
  签到题

#include 
#include 
#include 
#include
#include
#define ll long long
using namespace std;ll solve(ll n){ll temp;while(n>=10){temp=0;while(n){temp+=n%10;n/=10;}n=temp;}return n;
}int main(){int t,k;ll n;scanf("%d",&t);while(t--){scanf("%lld%d",&n,&k);if(k==2)n=n*n;printf("%lld\n",solve(n));}
}

• J.舔狗
  拓扑排序

#include
#define ll long long
using namespace std;
const int maxn=1e6+10;
int d[maxn],G[maxn],n,vis[maxn],ans;
queue<int>q;
void topo()
{for(int i=1;i<=n;i++)if(!d[i])q.push(i);//入度为0的加入 while(!q.empty()){int u=q.front();q.pop();int v=G[u];vis[u]=1;//标记该点 if(vis[v])continue;ans+=2;vis[v]=1;//如果被舔的人没被标记,就配对 int vv=G[v];//这个被舔的人被配对了,就不能和自己想舔的人配对了 d[vv]--;//删掉这条边,入度减一 if(d[vv]==0)q.push(vv);}
}
int dfs(int u)//以舔狗u为起点寻找一条拓扑路径 
{vis[u]=1;int res=1;if(!vis[G[u]]) res+=dfs(G[u]);return res;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&G[i]),d[G[i]]++;//G[i]为被舔的人,G[i]的入度+1 topo();for(int i=1;i<=n;i++)if(!vis[i]){int res=dfs(i);ans+=res/2*2;//只能配对偶数个人 }printf("%d\n",n-ans);
}

• K. 河北美食
  用map模拟
  这个之前用puts(“YES”);wa了一发，提醒一下自己不要混用这种输入输出流。
  还有就是map会自己把映射下标按顺序排好(排序时间为log n)，可以用unordered_map节省插入时间(这个容器的映射下标好像是随机排放)。而题目是要我们按初始顺序输出，所以我们不能用迭代器，用vector保存映射下标然后依次输出就好了。

#include 
#include 
#include 
#include
#include
#define LL long long
using namespace std;
using namespace std::tr1;
unordered_map <string,int> M;int main(){std::ios::sync_with_stdio(false);int n,m,num,k;cin>>n>>m;string name;vector<string>ve;for(int i=0;i<n;i++){cin>>name>>num;ve.push_back(name);M[name]=num;		}while(m--){cin>>k;	while(k--){cin>>name>>num;M[name]-=num;if(M[name]<0){cout<<"NO"<<endl;return 0;}			}	} cout<<"YES"<<endl;for(int i=0;i<ve.size();i++)if(M[ve[i]]!=0)cout<< ve[i] <<' '<< M[ve[i]]<<endl;return 0;	
} 

• L.smart robot
  搜索

解法一
连续的枚举i,在矩阵中搜索i的值,如果不存在就输出i。

//解法1
#include
#include 
using namespace std;int n,a[100][100],num[100],dir[4][2]={1,0,0,1,-1,0,0,-1};
struct node{int x,y,step;
};bool bfs(int x){int len=1;if(!x)	num[len++]=0;	while(x){num[len++]=x%10;x/=10;}queue<node>q;for(int i=1;i<=n;i++)for (int j=1;j<=n;j++)if(a[i][j]==num[1])q.push(node{i,j,1});while(!q.empty()){node temp= q.front();q.pop();if(temp.step==len-1)return 1;for(int i=0;i<4;i++){int dx=temp.x+dir[i][0];int dy=temp.y+dir[i][1];if(dx<1||dx>n||dy<1||dy>n)continue;if(a[dx][dy]!=num[temp.step+1])continue;q.push(node{dx,dy,temp.step+1});	}}return 0;						
}int main(){scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);	for(int i=0;;i++)if(!bfs(i)){printf("%d\n",i);return 0;		}
}

解法二
题目告诉我们:The numbers in the matrix are randomly generated.
就是说矩阵里所有数都是随机的，所以应该不会有恶意数据卡我们,我们就用dfs
预处理到四位数，然后查询,可以用很少时间通过，当然在实际比赛中更推荐第一种，第二种做法不是很保险。

//解法2
#include
#define ll long long
using namespace std;
const int N=1e5;
int n,a[100][100];
bool vis[N];
int dir[4][2]={1,0,0,1,-1,0,0,-1};
void dfs(int v,int x,int y,int step){vis[v]=1;if(step==4)return; //step的大小要看测试数据的情况for(int i=0;i<4;i++){int xx=x+dir[i][0];int yy=y+dir[i][1];if(xx<1||xx>n||yy<1||yy>n)continue;dfs(v*10+a[xx][yy],xx,yy,step+1);}
}int main(){	scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]); memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dfs(a[i][j],i,j,1);//预处理 for(int i=0;;i++){if(!vis[i]){printf("%d\n",i);return 0;}}	
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！