第十二届蓝桥杯B组真题题解

时间显示

简单的模拟题，换算好时间就行

#include<cstdio>

int main()
{
    long long n;
    scanf("%lld", &n);
    n /= 1000;
    n %= 60 * 60 * 24;
    printf("%02d:%02d:%02d\n", n / 3600, n / 60 % 60, n % 60);
    return 0;
}

砝码称重

可以用dp做也可以直接母函数来做。都是比较模板的题hdu1709原题。写文章-CSDN博客生成函数相关知识可以参考我之前写的这篇来学习,重点在理解c1和c2在模拟多项式的作用。问题比这个简单一点。稍微改改就行，不直接贴ac代码了

#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,c1[maxn],c2[maxn],num[105];
int elem[105];
int main() {
    while (~scanf("%d",&n)){
        for (int i=1;i<=n;i++)scanf("%d",&elem[i]),num[i]=1;
        int sum=0;
    	for (int i=1;i<=n;i++)sum+=elem[i]*num[i];//num全为1，此处为了模板好修改，好理解。
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
    	c1[0]=c1[elem[1]]=1;
    	for (int i=2;i<=n;i++){
    		for (int j=0;j<=sum;j++)
    			for (int k=0;k+j<=sum&&k<=elem[i];k+=elem[i])
    			{
    				c2[abs(k-j)]+=c1[j];//天平问题唯一的区别就是可以组合出k和j的绝对值，加上即可。
    				c2[j+k]+=c1[j];
    			}
    		for (int j=0;j<=sum;j++){
    			c1[j]=c2[j];
    			c2[j]=0;
    		}
    	}
    	vector<int>ans;
    	for (int i=0;i<=sum;i++)
    		if (!c1[i])ans.push_back(i);
    	printf("%lu\n",ans.size());
    	for (int i=0;i<ans.size();i++)
    		printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');
    }
    return 0;
}

杨辉三角

结合了二分和数学。首先杨辉三角对称。所有右边不考虑。对于左边斜着看，由于每个斜行都是单调的，并且16行也是递增的。所以可以结合二分和组合数来找到位置。注意从最多16层。因为C（32，16）大于1e9.只需要二分找到位置，再用公式计算它的具体位置即可

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
int n;
int c(int a,int b){
    int res=1;
    for(int i=a,j=1;j<=b;i--,j++)
        res=res*i/j;
    return res;
}
bool check(int k){
    int l=2*k,r=max(n,l);
    while(l<r){
        int mid=(l+r) >>1;
        if(c(mid,k)>=n)r=mid;
        else l=mid+1;
    }
    if(c(r,k)!=n)return false;
    else{
        cout<<(r+1)*r/2+k+1;
        return 1;
    }
}
signed main(){
    cin>>n;
    for(int k=16;;k--){
        if(check(k)){
            return 0;
        }
    }
}
 

双向排序

2016 天津oi省选的题的弱化版。可以直接用线段树合并和分解做，对每个位置建立权值线段树，维护下排序的过程即可，不过这题弱化了一些地方，所以不需要这么麻烦的方法。观察性质，分情况讨论，用栈维护也可以通过这题。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
const int N=1e5+10;
int n,m,top,tot;
int rt[N],stk[N*40],op[N];
struct node{
    int l,r,x;
}q[N*40];
set<int>s;
inline int newnode(){return top?stk[top--]:++tot;}
inline void del(int u){q[stk[++top]=u]={0,0,0};}
void upd(int &u,int l,int r,int p)
{
    q[u=++tot].x=1;
    if(l==r) return;
    int m=(l+r)>>1;
    if(p<=m) upd(q[u].l,l,m,p);
    else upd(q[u].r,m+1,r,p);
}
void print(int u,int l,int r,int f)
{
    if(!u) return;
    if(l==r) cout<<l<<" ";
    int m=(l+r)>>1;
    if(f)
    {
        print(q[u].l,l,m,f);
        print(q[u].r,m+1,r,f);
    }
    else
    {
        print(q[u].r,m+1,r,f);
        print(q[u].l,l,m,f);
    }
}
void split(int x,int &y,int k,int f)
{
    if(!x) return;
    y=newnode();
    if(f)
    {
        int v=q[q[x].l].x;
        if(k<=v)
        {
            if(k<v) split(q[x].l,q[y].l,k,f);
            swap(q[x].r,q[y].r);
        }
        else split(q[x].r,q[y].r,k-v,f);
    }
    else
    {
        int v=q[q[x].r].x;
        if(k<=v)
        {
            if(k<v) split(q[x].r,q[y].r,k,f);
            swap(q[x].l,q[y].l);
        }
        else split(q[x].l,q[y].l,k-v,f);
    }
    q[y].x=q[x].x-k;
    q[x].x=k;
}
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    q[x].x+=q[y].x;
    q[x].l=merge(q[x].l,q[y].l);
    q[x].r=merge(q[x].r,q[y].r);
    del(y);
    return x;
}
auto spl(int x)
{
    auto it=s.lower_bound(x);
    if(*it==x) return it;
    --it;split(rt[*it],rt[x],x-*it,op[x]=op[*it]);
    return s.insert(x).first;
}
int main(void)
{
    sync;
    cin>>n>>m;
    s.insert(n+1);
    for(int i=1;i<=n;++i)
    {
        upd(rt[i],1,n,i);
        s.insert(i);
    }
    while(m--)
    {
        int o,l,r=n;
        cin>>o>>l;
        if(o==0) r=l,l=1;
        auto L=spl(l),R=spl(r+1);
        for(auto it=++L;it!=R;++it)
            rt[l]=merge(rt[l],rt[*it]);
        op[l]=o;s.erase(L,R);
    }
    for(int x:s)
    {
        if(x==n+1) break;
        print(rt[x],1,n,op[x]);
    }
    return 0;
}
 

括号序列

一个比较特殊的dp题，容易发现，所有间隔都可以插入括号，但是插入（）形式的括号没有意义，所以括号格式一定是）（的，那么问题就变成了插入左括号的方案数乘插入右括号的方案数即可算出答案。所以我们只需要考虑左括号的插入方案数即可，定义dp[I] [j]的状态为前i个括号，左括号比右括号多j个的方案数，那么分情况讨论，状态转移方程很容易列出

如果当前是左括号，f[i] [j]=f[i-1] [j-1];

如果当前是右括号，f[i] [j]=f[i-1] [j+1]+....f[i-1] [0]

对于第二种情况，可以用完全背包的技巧，减少一维，从小到大枚举，至于右括号，翻转序列，然后在改变括号，跑一边就行。注意由于要求添加最少，所以答案是第一个存在方案的，f[n] [j]。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5010;
char s[N];
ll f[N][N];
int n;
int get()
{
    memset(f, 0, sizeof f);

    f[0][0] = 1;
    for(int i = 1; i <= n; i ++ )
        if(s[i] == '(')
        {
            for(int j = 1; j <= n; j ++ )
            f[i][j] = f[i - 1][j - 1];
        }
        else
        {
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
            for (int j = 1; j <= n; j ++ )
                f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod;
        }
    for(int i = 0; i <= n; i ++ )
        if(f[n][i])
            return f[n][i];
}
int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    ll l = get();
    reverse(s + 1, s + n + 1);
    for(int i = 1; i <= n; i ++ )
        if(s[i] == '(') s[i] = ')';
        else s[i] = '(';
    ll r = get();
    cout << l * r % mod;
}