爱站程序员基地NOTE：没对答案，考场上的代码，不一定对，大佬们轻喷
可以在此下载题目原版pdf文件：2021年第十二届蓝桥杯省赛 C++大学A组 真题（第一场）
文章目录
- NOTE：没对答案，考场上的代码，不一定对，大佬们轻喷
A题 卡片（5分）
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=10,M=1e7,inf=0x3f3f3f3f;int vis[N+10],a[N+10];bool judge(int x){string s=to_string(x);memset(a,0,sizeof(a));for(int i=0;s[i];i++)a[s[i]-'0']++;for(int i=0;i<N;i++)if(vis[i]<a[i])return 0;for(int i=0;i<N;i++)vis[i]-=a[i];return 1;}int main(){ios::sync_with_stdio(false);for(int i=0;i<N;i++)vis[i]=2021;for(int i=1;i<=M;i++){if(!judge(i)){printf("%d\\n",i-1);break;}}return 0;}
答案：3181
B题 直线（5分）
如果斜率和截距用double存于map：
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=22,inf=0x3f3f3f3f;bool vis[N],flag[N][N][N][N];unordered_map<double,unordered_map<double,int> >vis1;bool judge(int x1,int y1,int x2,int y2){if(x2==x1) // 垂直于x轴{if(!vis[x1]){vis[x1]=1;return 1;}return 0;}double k=(double(y2-y1))/(double(x2-x1));double b=y1-k*x1;if(!vis1[k][b]){vis1[k][b]=1;return 1;}return 0;}int main(){ios::sync_with_stdio(false);int n,m,ans=0;cin>>n>>m;for(int x1=0;x1<=n;x1++){for(int y1=0;y1<=m;y1++){for(int x2=0;x2<=n;x2++){for(int y2=0;y2<=m;y2++){if(!flag[x1][y1][x2][y2]) // 去重 (x1,y1)(x2,y2) (x2,y2)(x1,y1){flag[x1][y1][x2][y2]=flag[x2][y2][x1][y1]=1;ans+=judge(x1,y1,x2,y2);}}}}}printf("%d\\n",ans);return 0;}/*1 2ans:1119 20ans:41509*/
答案：41509
如果斜率和截距用分数形式存于map：
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=22,inf=0x3f3f3f3f;bool vis[N],flag[N][N][N][N];unordered_map<int,unordered_map<int,unordered_map<int,unordered_map<int,bool> > > >vis1;bool judge(int x1,int y1,int x2,int y2){if(x1==x2) // 垂直于x轴{if(!vis[x1]){vis[x1]=1;return 1;}return 0;}int k1=y2-y1;int k2=x2-x1;int tk=__gcd(k1,k2);k1/=tk;k2/=tk;int b1=k2*y1-k1*x1;int b2=x2-x1;int tb=__gcd(b1,b2);b1/=tb;b2/=tb;if(!vis1[k1][k2][b1][b2]){vis1[k1][k2][b1][b2]=1;return 1;}return 0;}int main(){ios::sync_with_stdio(false);int n,m,ans=0;cin>>n>>m;for(int x1=0;x1<=n;x1++){for(int y1=0;y1<=m;y1++){for(int x2=0;x2<=n;x2++){for(int y2=0;y2<=m;y2++){if(!flag[x1][y1][x2][y2]) // 去重 (x1,y1)(x2,y2) (x2,y2)(x1,y1){flag[x1][y1][x2][y2]=flag[x2][y2][x1][y1]=1;ans+=judge(x1,y1,x2,y2);}}}}}printf("%d\\n",ans);return 0;}/*1 2ans:1119 20ans:47561*/
答案：47561
应该是按分数形式存比较靠谱，还有就是枚举两个点的时候也要去重，比如(x1,y1)(x2,y2)与(x2,y2)(x1,y1)实际上是一种枚举方式。
答案应该是47561
C题 货物摆放（10分）
不会…没推出来公式，暴力搞不出
贴一个别人的代码：
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e5+10;ll p[N],d[5],ans=0;unordered_map<ll,unordered_map<ll,unordered_map<ll,bool>>>vis; // 三维标记void find(ll a,ll b,ll c){d[0]=a,d[1]=b,d[2]=c;sort(d,d+3);if(!vis[d[0]][d[1]][d[2]]){vis[d[0]][d[1]][d[2]]=1;do{ans++;}while(next_permutation(d,d+3));}}int main(){ll n=2021041820210418;int cnt=0;for(int i=1;i<=(ll)(sqrt(n));i++){if(n%i==0){p[++cnt]=i;p[++cnt]=n/i;}}for(int i=1;i<=cnt;i++){for(int j=1;j<=cnt;j++){if(p[i]*p[j]>n)continue;if(n%(p[i]*p[j])==0){ll c=n/(p[i]*p[j]);find(p[i],p[j],c);}}}printf("%lld\\n",ans);return 0;}
答案：2430
D题 路径（10分）
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=2021+100,M=N*N+10;const ll inf=0x7f7f7f7f7f7f7f7f;ll head[N],cnt,dis[N];bool vis[N],flag[N][N];struct edge{ll to,w,next;}e[M<<1];void add(ll x,ll y,ll z){e[cnt].to=y;e[cnt].w=z;e[cnt].next=head[x];head[x]=cnt++;}void add_edge(ll x,ll y){ll z=x/__gcd(x,y)*y;add(x,y,z);add(y,x,z);}struct node{ll u,w;bool operator < (const node &s) const{return w>s.w;}};ll dijkstra(ll s,ll t){memset(dis,inf,sizeof(dis));priority_queue<node>q;q.push({s,0});dis[s]=0;while(!q.empty()){node tmp=q.top();q.pop();ll u=tmp.u;if(vis[u])continue;vis[u]=1;for(ll i=head[u];i!=-1;i=e[i].next){ll v=e[i].to;ll w=e[i].w;if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;q.push({v,dis[v]});}}}return dis[t];}int main(){ios::sync_with_stdio(false);memset(head,-1,sizeof(head));ll n=2021;for(ll i=1;i<=n;i++){for(ll j=1;j<=n;j++){if(i!=j&&!flag[i][j]&&abs(i-j)<=21){flag[i][j]=flag[j][i]=1;add_edge(i,j);}}}ll ans=dijkstra(1,n);printf("%lld\\n",ans);return 0;}
答案：10266837
E题 回路计数（15分）
不会…暴力搞不出，不会剪枝…
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=110,inf=0x3f3f3f3f;vector<int>g[N];bool vis[N];ll n,ans=0;void dfs(int u,int cnt){for(auto v:g[u]){if(cnt==n&&v==1) // 已经走满，再走下一个点就是起点了ans++;if(!vis[v]){vis[v]=1;dfs(v,cnt+1);vis[v]=0;}}}int main(){ios::sync_with_stdio(false);cin>>n; // n=21for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(__gcd(i,j)==1)g[i].push_back(j),g[j].push_back(i);vis[1]=1;dfs(1,1);printf("%lld\\n",ans);return 0;}
F题 砝码称重（15分）
牛客上有个类似的题 小M和天平
但是我只会暴力，骗点分QAQ
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=110,inf=0x3f3f3f3f;ll n,a[N],ans=0;bool use[N];unordered_map<ll,bool>vis;void dfs(ll x){for(ll i=1;i<=n;i++){if(!use[i]){use[i]=1;// 加ll y1=x+a[i];if(!vis[y1]){ans++;vis[y1]=1;dfs(y1);y1-=a[i]; // 还原}// 减ll y2=x-a[i];if(y2>0&&!vis[y2]){ans++;vis[y2]=1;dfs(y2);y2+=a[i]; // 还原}use[i]=0; // 还原}}}int main(){ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1,greater<ll>());dfs(0);printf("%lld\\n",ans);return 0;}
G题 异或序列（20分）
不会…（看到有大佬说，特判一下平局，然后先手必赢？）
H题 左孩子右兄弟（20分）
我的思路是每次往下找拥有直接相连的孩子数最多的点，若有k个孩子，则层数最多就能加k。
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e5+10,inf=0x3f3f3f3f;int n,mx=0,dp[N],child[N];vector<int>g[N];void dfs(int u){int sz=g[u].size();for(int i=0;i<sz;i++){int v=g[u][i];dp[v]=dp[u]+child[u];mx=max(mx,dp[v]);dfs(v);}}int main(){ios::sync_with_stdio(false);cin>>n;int fa;for(int i=2;i<=n;i++){cin>>fa;child[fa]++; // 点fa的孩子数量g[fa].push_back(i); // fa -> i}dfs(1);printf("%d\\n",mx);return 0;}/*1ans:021ans:191 1 3 3 3 5 5 6ans:7141 1 1 2 4 5 5 5 6 6 6 11 11ans:9*/
I题 括号序列（25分）
不会…
J题 分果果（25分）
不会…
