• 蓝桥杯备战刷题（自用）

    1.被污染的支票

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6. int main()
    7. {
    8.   int n;
    9.   cin>>n;
    10.   vector<int>L;
    11.   map<int,int>mp;
    12.   bool ok=0;
    13.   int num;
    14.   for(int i=1;i<=n;i++)
    15.   {
    16.     cin>>num;
    17.     if(mp[num]==1)ok=1;
    18.     else
    19.     {
    20.       mp[num]=1;
    21.       L.push_back(num);
    22.     }
    23.   }
    24.   sort(L.begin(),L.end());
    25.   int x=L.back()*2;//?????
    26.   vector<int>L2;
    27.   for(int i=2;i
    28.   {
    29.     if(x%i==0)L2.push_back(i);
    30.   }
    31.   if(L!=L2)ok=1;
    32.   if(ok)
    33.   {
    34.     cout<<-1<
    35.   }
    36.   else
    37.   {
    38.     cout<
    39.   } 
    40.   return 0;
    41. }

    2.日期统计

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5. int main()
    6. {
    7.   int ans=0;
    8.   int num[100]={5, 6, 8, 6, 9, 1, 6, 1, 2, 4,
    9.                 9, 1, 9, 8, 2, 3, 6, 4, 7, 7, 
    10.                 5, 9, 5, 0, 3, 8, 7, 5, 8, 1,
    11.                 5, 8, 6, 1, 8, 3, 0, 3, 7, 9,
    12.                 2, 7, 0, 5, 8, 8, 5, 7, 0, 9,
    13.                 9, 1, 9, 4, 4, 6, 8, 6, 3, 3,
    14.                 8, 5, 1, 6, 3, 4, 6, 7, 0, 7,
    15.                 8, 2, 7, 6, 8, 9, 5, 6, 5, 6,
    16.                 1, 4, 0, 1, 0, 0, 9, 4, 8, 0,
    17.                 9, 1, 2, 8, 5, 0, 2, 5, 3, 3};
    18.   int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    19.   for(int mon=1;mon<=12;mon++)
    20.   {
    21.     for(int day=1;day<=days[mon];day++)
    22.     {
    23.       int temp[8]={2,0,2,3,mon/10,mon%10,day/10,day%10};
    24.       int k=0;
    25.       for(int i=0;i<100;i++)
    26.       {
    27.         if(num[i]==temp[k])
    28.         {
    29.           k++;
    30.         }
    31.         if(k==8)
    32.         {
    33.           ans++;
    34.           break;
    35.         }
    36.       }
    37.     }
    38.   }
    39.   cout<
    40.   return 0;
    41. }

    3.01串的熵

    1. #include 
    2. #include 
    3. using namespace std;
    4. int main()
    5. {
    6.   int n=23333333;
    7.   for(int i=0;i<=n/2;i++)//0的次数
    8.   {
    9.     double a=(i*1.0)/n;
    10.     double b=((n-i)*1.0)/n;
    11.     double ans=0;
    12.     ans-=(a*log2(a)*i+b*log2(b)*(n-i));
    13.     if(fabs(ans-11625907.5798)<0.0001)
    14.     {
    15.       cout<
    16.       break;
    17.     }
    18.   }
    19.   return 0;
    20. }

    （注意浮点数，double，以及比较大小时使用1e-4） 

    4.冶炼金属

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. int main()
    5. {
    6.   ll n,a,b,minn,maxx;
    7.   maxx=1e9;//要满足最小的
    8.   minn=0;//要满足最大的
    9.   cin>>n;
    10.   for(ll i=0;i
    11.   {
    12.     cin>>a>>b;
    13.     minn=max(minn,a/(b+1)+1);
    14.     maxx=min(maxx,a/b);
    15.   }
    16.   cout<" "<
    17.   return 0;
    18. }
    1. //二分
    2. #include 
    3. using namespace std;
    4. int a[10000+5];
    5. int v[10000+5];
    6. int n;
    7. bool check_min(int x)
    8. {
    9.   for(int i=1;i<=n;i++)
    10.   {
    11.     if(a[i]/x>v[i])return false;
    12.   }
    13.   return true;
    14. }
    15. bool check_max(int x)
    16. {
    17.   for(int i=1;i<=n;i++)
    18.   {
    19.     if(a[i]/xreturn false;
    20.   }
    21.   return true;
    22. }
    23. int main()
    24. {
    25.   cin>>n;
    26.   for(int i=1;i<=n;i++)
    27.   {
    28.     cin>>a[i]>>v[i];
    29.   }
    30.   int L=1,R=1000000000,minn=0;
    31.   while(L<=R)
    32.   {
    33.     int mid=(L+R)>>1;
    34.     if(check_min(mid))
    35.     {
    36.       minn=mid;
    37.       R=mid-1;
    38.     }
    39.     else L=mid+1;
    40.   }
    41.   int maxx=0;
    42.   L=1,R=1000000000;
    43.   while(L<=R)
    44.   {
    45.     int mid=(L+R)>>1;
    46.     if(check_max(mid))
    47.     {
    48.       maxx=mid;
    49.       L=mid+1;
    50.     }
    51.     else R=mid-1;
    52.   }
    53.   cout<" "<
    54.   return 0;
    55. }

    5.飞机降落

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5. struct node
    6. {
    7.   int t,d,l;
    8. };
    9. bool ok=0;
    10. vectorv;
    11. vector<int>vis;
    12. int n;
    13. void dfs(int cnt,int last)
    14. {
    15.   if(cnt==n)
    16.   {
    17.     ok=1;
    18.     return;
    19.   }
    20.   for(int i=0;i
    21.   {
    22.     if(!vis[i]&&v[i].t+v[i].d>=last)//可以降落
    23.     {
    24.       vis[i]=1;
    25.       dfs(cnt+1,max(last,v[i].t)+v[i].l);
    26.       vis[i]=0;//恢复
    27.     }
    28.   }
    29. }
    30. int main()
    31. {
    32.   int t;
    33.   cin>>t;
    34.   while(t--)
    35.   {
    36.     cin>>n;
    37.     v.clear();
    38.     vis.clear();
    39.     for(int i=1;i<=n;i++)
    40.     {
    41.       //t d l (t/t+d -- l)
    42.       int x,y,z;
    43.       cin>>x>>y>>z;
    44.       v.push_back({x,y,z});
    45.       vis.push_back(0);
    46.     }
    47.     ok=0;
    48.     dfs(0,0);//0架飞机，0需要时间
    49.     if(!ok)cout<<"NO"<
    50.     else cout<<"YES"<
    51.   }
    52.   return 0;
    53. }

    6.接龙数列

    这道题其实本质就是求解出数列中最长的接龙数列，计算出最长的接龙数列长度，数列总长度-最长接龙数列长度等于最少删除次数。这就是一个求最优解的问题，然而看到这道题的数据量可以发现，暴力求解一定会超时，因此考虑动态规划。 动态规划最重要的就是状态转移方程，而这个题目就可以定义状态为当前最长接龙数列长度，则dp[i]就是以i为数字最后一位的最长接龙数列长度，设x为当前数字的第一位(如果为接龙数列，也就是前一位数的最后一位)，y为当前数字的最后一位，则转移方程可以写为dp[y]=max(dp[x]+1,dp[y])

    1. #include 
    2. using namespace std;
    3. int f[10];//表示在i=0-9中,f[i]为以i数字为连接的最长接龙数列的长度
    4. int main()
    5. {
    6.   int n;
    7.   cin>>n;
    8.   int ans=0;
    9.   string s;
    10.   for(int i=0;i
    11.   {
    12.     cin>>s;
    13.     int pre=s[0]-'0',nex=s[s.size()-1]-'0';
    14.     f[nex]=max(f[nex],f[pre]+1);
    15.     ans=max(ans,f[nex]);
    16.   }
    17.   cout<//总的-最长长度=删去的
    18.   return 0;
    19. }

    7.岛屿个数

    搜索出所有岛屿，这个不难做到。由于岛屿之间互相隔离，则如果岛屿的一个格子在一个环内，那么整个岛屿也都在环内。遍历所有的岛屿，选中当前岛屿的第一个格子，搜索周围海洋，若能搜索到地图的边界外，则此岛屿不在任何一个环内；否则，此岛屿在某个环内，岛屿数量减一。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6. #define pii pair
    7. const int N=100;
    8. int n,m,ans;
    9. vectorbool>>vis;
    10. string s[N];
    11. int dx[8]={-1,1,0,0,-1,1,-1,1};
    12. int dy[8]={0,0,-1,1,-1,1,1,-1};
    13. bool inmap(int x,int y)
    14. {
    15.   if(x<1||x>n||y<1||y>m)return 0;
    16.   return 1;
    17. }
    18. //bfs统计岛屿的情况
    19. void bfs(int x,int y)
    20. {
    21.   vis[x][y]=1;
    22.   queueq;
    23.   q.push({x,y});
    24.   while(!q.empty())
    25.   {
    26.     auto t=q.front();
    27.     q.pop();
    28.     for(int i=0;i<4;i++)
    29.     {
    30.       int xx=t.first+dx[i];
    31.       int yy=t.second+dy[i];
    32.       if(!inmap(xx,yy)||vis[xx][yy]||s[xx][yy]!='1')continue;
    33.       vis[xx][yy]=1;
    34.       q.push({xx,yy});
    35.     }
    36.   }
    37. }
    38. bool check(int x,int y)//是否不在环内，即周围是海洋（用是否到边界判断）
    39. {
    40.   vectorbool>>fin(n+1,vector<bool>(m+1,0));
    41.   fin[x][y]=1;
    42.   queueq;
    43.   q.push({x,y});
    44.   while(!q.empty())
    45.   {
    46.     auto t=q.front();
    47.     q.pop();
    48.     //到达边界，证明不在环中
    49.     if(t.first==1||t.first==n||t.second==1||t.second==m)return 1;
    50.     for(int i=0;i<8;i++)
    51.     {
    52.       int xx=t.first+dx[i];
    53.       int yy=t.second+dy[i];
    54.       if(!inmap[xx][yy]||fin[xx][yy]||s[xx][yy]!='0')continue;
    55.       fin[xx][yy]=1;
    56.       q.push({xx,yy});
    57.     }
    58.   }
    59.   return 0;
    60. }
    61. int main()
    62. {
    63.   int t;
    64.   cin>>t;
    65.   while(t--)
    66.   {
    67.     ans=0;
    68.     cin>>n>>m;
    69.     for(int i=1;i<=n;i++)
    70.     {
    71.       cin>>s[i];
    72.       s[i]='2'+s[i];
    73.     }
    74.     vis=vectorbool>>(n+1,vector<bool>(m+1,0));
    75.     for(int i=1;i<=n;i++)
    76.     {
    77.       for(int j=1;j<=m;j++)
    78.       {
    79.         if(!vis[i][j]&&s[i][j]=='1')
    80.         {
    81.           bfs(i,j);
    82.           if(check(i,j))ans++;
    83.         }
    84.       }
    85.     }
    86.     cout<
    87.   }
    88.   return 0;
    89. }

     8.子串简写

    1. #include 
    2. using namespace std;
    3. int main()
    4. {
    5.   int k;
    6.   //最小可以简写的长度
    7.   cin>>k;
    8.   string s;
    9.   char st,ed;
    10.   cin>>s>>st>>ed;
    11.   long long ans=0;
    12.   int st_num=0;
    13.   for(int i=0,j=k-1;jsize();i++,j++)
    14.   {
    15.     if(s[i]==st)st_num++;
    16.     if(s[j]==ed)ans+=st_num;
    17.   }
    18.   cout<
    19.   return 0;
    20. }
    21. //4
    22. //abababdb a b

     （注意规律，开long long）

     9.整数删除

    1. #include
    2. using namespace std;
    3. //优先队列+双向链表
    4. const int N=5e5+10;
    5. #define ll long long
    6. #define val first
    7. #define pos second
    8. #define pli pair
    9. int n,k;
    10. ll a[N],pre[N],nxt[N];
    11. priority_queue,greater>q;//小根堆
    12. int main()
    13. {
    14.   cin>>n>>k;
    15.   for(int i=1;i<=n;i++)
    16.   {
    17.     cin>>a[i];
    18.     q.push({a[i],i});
    19.     pre[i]=i-1;
    20.     nxt[i]=i+1;
    21.   }
    22.   pre[1]=-1;
    23.   nxt[n]=-1;
    24.   while(k--)
    25.   {
    26.     pli now;
    27.     do{
    28.       now=q.top();
    29.       q.pop();
    30.     }while(a[now.pos]!=now.val);//保证弹出同一个
    31.     int PRE=pre[now.pos];
    32.     int NXT=nxt[now.pos];
    33.     if(PRE!=-1)
    34.     {
    35.       a[PRE]+=now.val;
    36.       q.push({a[PRE],PRE});
    37.       nxt[PRE]=NXT;
    38.     }
    39.     if(NXT!=-1)
    40.     {
    41.       a[NXT]+=now.val;
    42.       q.push({a[NXT],NXT});
    43.       pre[NXT]=PRE;
    44.     }
    45.     a[now.pos]=-1;
    46.   }
    47.   for(int i=1;i<=n;i++)
    48.   {
    49.     if(a[i]!=-1)cout<" ";
    50.   }
    51.   return 0;
    52. }

     10.景区导游

    1. //最近公共祖先。倍增做法 (深搜)
    2. #include 
    3. #include 
    4. #define ll long long
    5. using namespace std;
    6. const int N=1e5+10;
    7. vector<int>e[N],w[N];
    8. int n,k;
    9. ll dep[N],fa[N][20],dist[N],b[N];
    10.  
    11. void dfs(int u,int father){
    12.     
    13.     fa[u][0]=father;
    14.     dep[u]=dep[father]+1;
    15.     
    16.     for(int i=1;i<20;i++){
    17.         fa[u][i]=fa[fa[u][i-1]][i-1];
    18.     }
    19.     
    20.     for(int i=0;isize();i++){
    21.         int v=e[u][i];
    22.         int t=w[u][i];
    23.         if(v!=father){
    24.             dist[v]=dist[u]+t;
    25.             dfs(v,u);
    26.         }
    27.     }
    28. }
    29.  
    30. int lca(int u,int v){
    31.     
    32.     if(dep[u]swap(u,v);
    33.     
    34.     for(int i=19;i>=0;i--){
    35.         if(dep[fa[u][i]]>=dep[v])
    36.             u=fa[u][i];
    37.     }
    38.     if(u==v) return v;
    39.     
    40.     for(int i=19;i>=0;i--){
    41.         if(fa[u][i]!=fa[v][i]){
    42.             u=fa[u][i],v=fa[v][i];
    43.         }
    44.     }
    45.     
    46.     return fa[u][0];
    47. }
    48.  
    49. ll sol(int x,int y){
    50.     if(!x||!y) return 0;
    51.     return dist[x]+dist[y]-2*dist[lca(x,y)];
    52. }
    53. int main(){    
    54.     
    55.     cin>>n>>k;
    56.     for(int i=1;i
    57.         int x,y,t;
    58.         cin>>x>>y>>t;
    59.         e[x].push_back(y);
    60.         e[y].push_back(x);
    61.         w[x].push_back(t);
    62.         w[y].push_back(t);
    63.     }
    64.     dfs(1,0);
    65.     ll Dis=0;
    66.     for(int i=1;i<=k;i++){
    67.         cin>>b[i];
    68.         Dis+=sol(b[i],b[i-1]);
    69.     }
    70.     
    71.     for(int i=1;i<=k;i++){
    72.         cout<sol(b[i-1],b[i])-sol(b[i],b[i+1])+sol(b[i-1],b[i+1])<<" ";
    73.     }
    74.     return 0;
    75. }

     11.砍树

    1. #include 
    2. #include 
    3. using namespace std;
    4. const int N=1e5+10;
    5. vector<int>e[N],num[N];
    6. int n,m,dep[N],fa[N][21],s[N],ans;
    7. void dfs(int u,int Fa)
    8. {
    9.   dep[u]=dep[Fa]+1;
    10.   fa[u][0]=Fa;
    11.   for(int i=1;i<=20;i++)
    12.   {
    13.     fa[u][i]=fa[fa[u][i-1]][i-1];
    14.   }
    15.   for(auto &v:e[u])
    16.   {
    17.     if(v==Fa)continue;
    18.     dfs(v,u);
    19.   }
    20. }
    21. int LCA(int u,int v)
    22. {
    23.   if(dep[u]swap(u,v);
    24.   for(int i=20;i>=0;i--)
    25.   {
    26.     if(dep[fa[u][i]]>=dep[v])
    27.     {
    28.       u=fa[u][i];
    29.     }
    30.   }
    31.   if(u==v)return u;
    32.   for(int i=20;i>=0;i--)
    33.   {
    34.     if(fa[u][i]!=fa[v][i])
    35.     {
    36.       u=fa[u][i];
    37.       v=fa[v][i];
    38.     }
    39.   }
    40.   return fa[u][0];
    41. }
    42. void dfs2(int u,int Fa)
    43. {
    44.   for(int i=0;isize();i++)
    45.   {
    46.     int v=e[u][i],p=num[u][i];
    47.     if(v==Fa)continue;
    48.     dfs2(v,u);
    49.     s[u]+=s[v];
    50.     if(s[v]==m)ans=max(ans,p);
    51.   }
    52. }
    53. int main()
    54. {
    55.   cin>>n>>m;
    56.   for(int i=1;i
    57.   {
    58.     int x,y;
    59.     cin>>x>>y;
    60.     e[x].push_back(y);
    61.     e[y].push_back(x);
    62.     num[x].push_back(i);
    63.     num[y].push_back(i);
    64.   }
    65.   dfs(1,0);
    66.   for(int i=1;i<=m;i++)
    67.   {
    68.     int a,b;
    69.     cin>>a>>b;
    70.     s[a]++;s[b]++;s[LCA(a,b)]-=2;
    71.   }
    72.   dfs2(1,0);
    73.   cout<
    74.   return 0;
    75. }

  • 相关阅读:
    Apache Flink ML 2.1.0 发布公告
    实例042：变量作用域
    MySQL高级02-MySQL的数据目录
    search_everything文件搜索引擎的测试用例
    数据结构篇：链表和树结构的操作方法
    【10】leetcode note
    实验二 逻辑回归算法实验
    notepad++官网地址 https://notepad-plus-plus.org，notepad++使用教程
    这种动态规划你见过吗——状态机动态规划之股票问题(上)
    【AtomicLong】常规用法
  • 原文地址：https://blog.csdn.net/gyeolhada/article/details/136279841