第十一届蓝桥杯省赛第一场C++A/B组真题题解

整除序列题目描述：

有一个序列，序列的第一个数是 n，后面的每个数是前一个数整除 2，请输出这个序列中值为正数的项

思路：

模拟就行

#include
using namespace std;
typedef long long ll;

int main(){
    ll n; cin >> n;
    while(n){
        cout << n << ' ';
        n /= 2;
    }
    cout << endl;
    return 0;
}

解码题目描述：

给出缩写后的字符串，让你还原回去，缩写的方式是将一段长度小于10的相同的字符串缩写成一个字符+一个数字的形式

思路：

模拟就行

#include
using namespace std;
typedef long long ll;

int main(){
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] >= '0' && s[i] <= '9'){
            int p = s[i] - '1';
            while(p>0)cout< 
走方格 
题目描述： 
 
 二维矩阵，你在(1, 1)问到(n, m)的路线的数量，其中不能走横纵坐标都是偶数的点 
 
思路： 
 
 最简单的dp计数 
 
#include 
using namespace std;

#define endl 'n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "n";
typedef long long ll;
typedef pair  pii;

#define MAX 300000 + 50
int n, m, k;
int tr[MAX];
int dp[50][50];

void work(){
    cin >> n >> m;
    dp[1][1] = 1;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(i % 2 == 0 && j % 2 == 0)continue;
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
        }
    }
    cout << dp[n][m] << endl;
}


int main(){
    io;
    work();
    return 0;
}



 
整数拼接 
题目描述： 
 
 给定长度为n的数组a[i]，你可以从中选择出两个数a[i], a[j](i != j)，将其一前一后拼在一起形成一个新的数字，例如：12和345可以拼接出12345或者34512，问存在多少种拼接方法，使的拼接出来的数是k的倍数 
 
思路： 
 
 很有意思的一个题 
 我们将在前面的数字叫做a, 将后面的数字叫做b 
 拼接得到的数字可以被拆成两部分：
     
      
       
        
         a
        
        
         ∗
        
        
         1
        
        
         
          0
         
         
          
           l
          
          
           o
          
          
           
            g
           
           
            10
           
          
          
           b
          
          
           +
          
          
           1
          
         
        
       
       
        a*10^{log_{10}{b}+1}
       
      
     a∗10log10b+1和
     
      
       
        
         b
        
       
       
        b
       
      
     b两部分 
 我们先考虑每个数a[j]作为b的情况，假设 
     
      
       
        
         p
        
        
         =
        
        
         1
        
        
         
          0
         
         
          
           l
          
          
           o
          
          
           
            g
           
           
            10
           
          
          
           b
          
          
           +
          
          
           1
          
         
        
       
       
        p=10^{log_{10}{b}+1}
       
      
     p=10log10b+1,则我们需要求1到j-1中出现的数a[i]，能满足(a[i]*p) % k + a[j] % k) %k = 0,也就是(a[i]*p) % k = k - a[j] % k 
 所以我们可以开一个数组tr[pp][x],
     
      
       
        
         p
        
        
         p
        
        
         =
        
        
         
          l
         
         
          o
         
         
          
           g
          
          
           10
          
         
         
          b
         
         
          +
         
         
          1
         
        
       
       
        pp={log_{10}{b}+1}
       
      
     pp=log10b+1,表示乘以 
     
      
       
        
         x
        
        
         ∗
        
        
         1
        
        
         
          0
         
         
          
           p
          
          
           p
          
         
        
       
       
        x*10^{pp}
       
      
     x∗10pp%k后等于x的数量,对于每个数x，当她作为拼接的后半部分数字的情况，答案是tr[pp][(k-tr[i]%k)%k] 
 注意要判断不能用同一个数，自己和自己能结合的情况就是：(tr[i]+tr[i]*pp)%k=0 
 特别特别坑的一个点是，极限情况下使用pow函数和数字相乘会爆longlong，用快速幂就行 
 
#include 
using namespace std;

#define endl 'n'
#define inf 0x3f3f3f3f
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "n";
typedef long long ll;
typedef pair  pii;

#define MAX 300000 + 50
ll n, m, k;
ll tr[MAX];
ll num[15][MAX];

ll q_pow(ll a, ll b, ll mod){
    ll ans = 1;
    while(b > 0){
        if(b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}


inline ll lg(ll x){
    ll num = 0;
    while (x) {
        ++num;x /= 10;
    }
    return num;
}

void work(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    for(int i = 1; i <= n; ++i){
        ll p = 1;
        for(int j = 0; j <= 10; ++j){
            ++num[j][(tr[i] * p) % k];
            p = (p * 10) % k;
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        ans += num[lg(tr[i])][(k - (tr[i]%k))%k];
        if((tr[i] + (tr[i] * q_pow(10, lg(tr[i]), k))%k)%k == 0)--ans;
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}
 
网络分析 
题目描述： 
 
 两种操作 
 1 x y，表示将x和y连接起来2 x c，表示将与x在同一个连通块的点的权值+c 
 
问最后每个点的权值是多少 
 
思路： 
 
 带权并查集 
 tr[i]表示节点i的权值 
 对于权值修改，我们只需要修改根节点的权值，这样每个点的答案就是当前点到跟节点上路径的权值 
 如何进行路径压缩？ 
 int getfa(int x){
    if(x == fa[x] || fa[fa[x]] == fa[x])return fa[x];//如果当前点就是根节点或者当前点的父亲节点就是根节点，就返回
    int root = getfa(fa[x]);
    tr[x] += tr[fa[x]];//先更新权值
    fa[x] = root;//再更新父节点
    return fa[x];
}
 
 如何合并？ 
 int xx = getfa(x);
int yy = getfa(y);
if(xx == yy)continue;//如果在同一个连通块内就不用管
tr[xx] -= tr[yy];//消除新的根节点yy的权值的影响
fa[xx] = yy;//更新根节点
 
 答案怎么输出： 
 for(int i = 1; i <= n; ++i){
    if(i == getfa(i))cout << tr[i] << ' ';//如果自己就是根节点，就直接输出
    else cout << tr[getfa(i)] + tr[i] << ' ';//否则，经过路径压缩后，一定是直接连接在根节点上面，所以答案是两部分，加上就行
}
 
 
#include 
using namespace std;

#define endl 'n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "n";
typedef long long ll;
typedef pair  pii;

#define MAX 300000 + 50
int n, m, k;
int tr[MAX];
int fa[MAX];

int getfa(int x){
    if(x == fa[x] || fa[fa[x]] == fa[x])return fa[x];
    int root = getfa(fa[x]);
    tr[x] += tr[fa[x]];
    fa[x] = root;
    return fa[x];
}

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)fa[i] = i;
    for(int i = 1, op, x, y; i <= m; ++i){
        cin >> op >> x >> y;
        if(op == 1){
            int xx = getfa(x);
            int yy = getfa(y);
            if(xx == yy)continue;
            tr[xx] -= tr[yy];
            fa[xx] = yy;
        }
        else{
            int xx = getfa(x);
            tr[xx] += y;
        }
    }
    for(int i = 1; i <= n; ++i){
        if(i == getfa(i))cout << tr[i] << ' ';
        else cout << tr[i] + tr[getfa(i)] << ' ';
    }
    cout << endl;
}


int main(){
    io;
    work();
    return 0;
}



 
超级胶水 
题目描述： 
 
 n颗石子，按顺序排成一排 
 每个石子都有自己的重量，相邻两个石子粘起来的花费是两个石子的重量的乘积，每次只能粘相邻的两个石子，问将所有的石子粘起来的最小花费是多少 
 
思路： 
 
 假设当前有三个石子，重量是a, b, c 
 粘1, 2后花费：a*b 
 再粘剩下的两个，花费是(a+b)*c 
 总花费是：ab + ac + bc 
 不难发现，无论粘贴的顺序如何，结果是不变的 
 
#include 
using namespace std;

#define endl 'n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "n";
typedef long long ll;
typedef pair  pii;

#define MAX 300000 + 50
int n, m, k;
ll ans, sum;
ll tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    sum = tr[1];
    for(int i = 2; i <= n; ++i){
        ans += sum * tr[i];
        sum += tr[i];
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

第十一届蓝桥杯省赛第一场C++A/B组真题题解

C/C++/C#相关栏目本月热门文章