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

题解：模拟。

#include

using namespace std;
typedef long long LL;
typedef pairPII;
const int N=1e5+10;
const int mod=1000000009;

int main(){
    LL n;
    scanf("%lld",&n);
    while(n){
        printf("%lld ",n);
        n/=2;
    }
    return 0;
}

题解：模拟+字符串处理

#include

using namespace std;
typedef long long LL;
typedef pairPII;
const int N=1e5+10;
const int mod=1000000009;
char a[110];
int main(){
    scanf("%s",a);
    int lena=strlen(a);
    for(int i=0;i='2'&&a[i+1]<='9'){
            for(int j=0;j 
题目：2067. 走方格 

 题解：dp。
 
#include

using namespace std;
typedef long long LL;
typedef pairPII;
const int N=1e5+10;
const int mod=1000000009;
LL f[35][35];
int main(){
    f[1][1]=1;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i%2==0&&j%2==0) continue;
            f[i][j]+=f[i-1][j]+f[i][j-1];
        }
    }
    printf("%lld",f[n][m]);
    return 0;
}

 
题目：2068. 整数拼接 

 题解：假设选的是a[i]和a[j],且满足(a[i]*len(a[j])+a[j]) %k ==0，等价于 a[i]*len(a[j])%k == -1 * a[j]%k。
 这时我们可以预先处理出左边的等式，考虑到每个a[i]<=10^9,也就是说每个数最多乘10 ^ 10。
 f[i][j]是当(a[k]*10^i) %k ==j。处理左边等式的复杂度为o(n * 10)，即最大10^6。然后再遍历右边的式子即可，但要注意排除(a[i]+a[i]*len)%k ==0的情况
 
#include

using namespace std;
typedef long long LL;
typedef pairPII;
const int N=1e5+10;
const int mod=1000000009;
int a[N];
int f[15][N];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        int t=a[i];
        for(int j=1;j<=10;j++){
            t=(1ll*t*10)%k;
            f[j][t]++;
        }
    }
    LL ans=0;
    for(int i=1;i<=n;i++){
        int len=to_string(a[i]).size();
        ans+=f[len][(-1*a[i]%k+k)%k];
        int t=a[i]%k;
        while(len--){
            t=(t*10)%k;
        }
        if(t==(-1*a[i]%k+k)%k) ans--;//这里排除是(a[i]+a[i]*len)%k==0
    }
    printf("%lld",ans);
    return 0;
}

 
题目：2069. 网络分析 

 
 
题解：并查集+树上差分
 
 上图来自acwing某大佬链接
 
#include

using namespace std;
typedef long long LL;
typedef pairPII;
const int N=1e5+10;
const int mod=1000000009;
int n,m;
int p[20010];
int v[20010];
int root=10001;
vector g[20010];
int get(int u){
    if(p[u]!=u) p[u]=get(p[u]);
    return p[u];
}
void dfs(int u,int fa){
    v[u]+=v[fa];
    for(int i=0;i>n>>m;
    for(int i=1;i<=20005;i++)
        p[i]=i;
    int x,y,z;
    for(int i=0;i 
题目：2875. 超级胶水 

 题解：经过分析会发现，消耗的胶水量其实就是n个物品中任意两个的乘积之和。
 
#include

using namespace std;
typedef long long LL;
typedef pairPII;
const int N=1e5+10;
const int mod=1000000009;
int n;
int w[N];
int sum[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
        sum[i]=sum[i-1]+w[i];
    }
    LL ans=0;
    for(int i=1;i<=n;i++){
        ans+=1ll*w[i]*sum[i-1];
    }
    printf("%lld",ans);
    return 0;
}