2019河北省大学生程序设计竞赛
B.Icebound and Sequence B题题解
G.点我 签到题
H.天神的密码 签到题
#include <iostream> #include <string> #include <map> #include<vector> #include<cstdio> #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<bits/stdc++.h> #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 <iostream> #include <string> #include <map> #include<tr1/unordered_map> #include<vector> #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<bits/stdc++.h> #include<queue> 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<bits/stdc++.h> #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; } } }