第十二届蓝桥杯省赛第二场C++B组真题

题目：3496. 特殊年份

题解：模拟+枚举

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<double,double>PII;
const int N=2e5+10;
const int mod=1000000009;

int main(){
    int x;
    int ans=0;
    for(int i=0;i<5;i++){
        cin>>x;
        if((x/1000==x%100/10)&&(x%10==(1+x%1000/100)))
            ans++;
    }
    cout<<ans;
    return 0;
}

题目：3490. 小平方

题解：枚举，

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<double,double>PII;
const int N=2e5+10;
const int mod=1000000009;

int main(){
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<n;i++){
        int t=i*i;
        if(t%n*2<n) ans++;//注意，这边的一半最好让左边乘2，要不然就是右边(n+1)/2;
    }
    cout<<ans;
    return 0;
}

题目：3491. 完全平方数

题解：分解质因数。复杂度为0（sqrt(n)）

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<double,double>PII;
const int N=2e5+10;
const int mod=1000000009;
LL n;
LL p[N];
int ct[N];
int k=0;
int main(){
    cin>>n;
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            p[k]=i;
            while(n%i==0){
                n/=i;
                ct[k]++;
            }
            k++;
        }
    }
    if(n){//注意最后n可能为一个质数（即使是1也不影响结果）
        p[k]=n;
        ct[k]++;
        k++;
    }
    LL ans=1;
    for(int i=0;i<k;i++){
        if(ct[i]%2){
            ans*=p[i];
        }
    }
    printf("%lld",ans);
    return 0;
}

题目：3492. 负载均衡

题解：模拟+优先队列。

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<double,double>PII;
const int N=2e5+10;
const int mod=1000000009;
int n,m;
int v[N];
priority_queue<PII,vector<PII>,greater<PII>> g[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    int a,b,c,d;
    while(m--){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        while(g[b].size()){
            if(g[b].top().first<=a){
                v[b]+=g[b].top().second;
                g[b].pop();
            }
            else break;
        }
        if(v[b]>=d){
            g[b].push({a+c,d});//注意，这道题只要可以分配，就会立即执行
            v[b]-=d;
            printf("%d\n",v[b]);
        }else{
            puts("-1");
        }
    }
    return 0;
}

题目：3494. 国际象棋

题解：状态压缩dp

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const LL M=1e9+7;
const int Maxn=1<<6;
LL f[110][Maxn][Maxn][30];
int get(int x){
    int sum=0;
    for(;x;x-=(x&(-x)))
        sum++;
    return sum;
}

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    int maxn=1<<n;
    f[0][0][0][0]=1;
    for(int i=1;i<=m;i++){
        for(int a=0;a<maxn;a++){
            for(int b=0;b<maxn;b++){
                if(((b>>2)&a)||((a>>2)&b)) continue;
                else{
                    for(int c=0;c<maxn;c++){
                        if(((b>>2)&c)||((c>>2)&b))continue;
                        if(((a>>1)&c)||((c>>1)&a)) continue;
                        int t=get(c);
                        for(int tt=t;tt<=k;tt++){
                            f[i][b][c][tt]=(f[i][b][c][tt]+f[i-1][a][b][tt-t])%M;
                        }
                    }
                }
            }
        }
    }
    LL sum=0;
    for(int i=0;i<maxn;i++){
        for(int j=0;j<maxn;j++){
            sum=(sum+f[m][i][j][k])%M;
        }
    }
    printf("%lld",sum);
    return 0;
}