河北省大学生程序设计竞赛
B.Icebound and Sequence
B题题解
G.点我
签到题
H.天神的密码
签到题
#include <iostream>#include <string>#include <map>#include<vector>#include<cstdio>#define ll long longusing 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 longusing 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 longusing 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 longusing 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;}}}
