初赛

A: 门牌制作

签到

答案：624

B: 既约分数

基本公式要会

typedef long long ll;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return 1LL*a/gcd(a,b)*b;}

答案：2481215

C: 蛇形填数

自己推公式就好啦(最好别模拟,想想就麻烦QAQ)

答案：761

D: 跑步锻炼

日期题模拟就好啦,注意特判闰年的2月份

代码:

#include<iostream>
using namespace std;

bool is29(int y){
    return ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0));
}

int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int getDay(int y, int m) {
    if (m != 2 || !is29(y))
        return day[m];
    else //即是2月份也是闰年
        return 29;
}
int inc(int& flag){
    int x = flag;
    flag++;
    if (flag == 8)
        flag = 1;
    return x;
}
int main() {
    int add = 0;
    int old = 0;
    int flag = 6;
    for (int y = 2000; y <= 2020; y++){
        for (int m = 1; m <= 12; m++){
            int days=getDay(y, m);
            for (int d = 1; d <=days; d++){
                if (inc(flag) == 1 || d == 1)
                    add++;
                old++;
                if (y == 2020 && m == 10 && d == 1){
                    cout << old + add << ' ' << old;
                    return 0;
                }
            }
        }
    }
    return 0;
}

答案：8879

E: 七段码

实在不会暴力一个一个数就行,就1-7枚举连通块个数,我考场就没想自己能代码敲出来,就果断开始数,运气爆炸,竟然数对了

比较好的做法:

想办法打印图案,然后人眼去数不就好了吗,状压思想呀,用位运算x >> i & 1来判断数字 $x$ 的二进制排列中第 $i$ 位是否为1

#include <iostream>
using namespace std;
int main(){
    int cnt = 1;
    for (int x = 1; x <= 127; x ++){
        cout << "====" << cnt ++ << "====" << endl;
        for (int i = 0; i < 7; i ++){
            if(i == 0){//a
                if(x >> i & 1) cout << " --";
                cout << endl;
            }
            if(i == 1){//f
                if(x >> i & 1) cout << '|';
                else cout << " ";
            }
            if(i == 2){//b
                if(x >> i & 1) cout << "  |";
                cout << endl;
            }
            if(i == 3){//g
                if(x >> i & 1) cout << " --";
                cout << endl;
            }
            if(i == 4){//e
                if(x >> i & 1) cout << '|';
                else cout << " ";
            }
            if(i == 5){//c
                if(x >> i & 1) cout << "  |";
                cout << endl;
            }
            if(i == 6){//d
                if(x >> i & 1) cout << " --";
                cout << endl;
            }
        }
        cout << endl;
    }
    return 0;
}

当然可以加上并查集 , 更方便一些

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;

vector<int> edge[10];
int f[10];
int h[10];

int find(int x){
    return f[x] == x ? x : find(f[x]);
}

void show(){
    cout<<" "<<(h[1] ? "-" : "*")<<" "<<endl;
    cout<<(h[2] ? "|" : "*")<<" "<<(h[3] ? "|" : "*")<<endl;
    cout<<" "<<(h[4] ? "-" : "*")<<" "<<endl;
    cout<<(h[5] ? "|" : "*")<<" "<<(h[6] ? "|" : "*")<<endl;
    cout<<" "<<(h[7] ? "-" : "*")<<" "<<endl;
    cout<<endl;
}
//因为有(#define int long long)宏定义，所以用了signed
signed main(){
    /**
     1
    2 3
     4
    5 6
     7
    **/
    // 记录每个管子的相邻管
    edge[1].pb(2);edge[1].pb(3);
    edge[2].pb(1);edge[2].pb(4);edge[2].pb(5);
    edge[3].pb(1);edge[3].pb(4);edge[3].pb(6);
    edge[4].pb(2);edge[4].pb(3);edge[4].pb(5);edge[4].pb(6);
    edge[5].pb(2);edge[5].pb(4);edge[5].pb(7);
    edge[6].pb(3);edge[6].pb(4);edge[6].pb(7);
    edge[7].pb(5);edge[7].pb(6);
    int res = 0;
    for(int sta = 1; sta < (1<<(8-1)) ; sta ++){
        for(int i = 1 ; i <= 7 ; i ++){
            h[i] = (sta>>(i-1))&1;
            f[i] = i;
        }
        for(int i = 1 ; i <= 7 ; i ++){
            if(!h[i]) continue;
            int fa = find(i);
            for(int j = 0 ; j < edge[i].size() ; j ++){
                int to = edge[i][j];
                if(!h[to]) continue;
                int fb = find(to);
                if(fa != fb)
                    f[fb] = fa;
            }
        }
        int cnt = 0;        // 连通块个数
        for(int i = 1 ; i <= 7 ; i ++){
            if(h[i])
                cnt += (f[i] == i);
        }
        res += (cnt == 1);
        if(cnt == 1)
            show();
    }
    cout<<res<<endl;
    return 0;
}

答案 : 80

签到

不过,考场不知道浮点数自动四舍五入,自己还特地写了个函数,长知识了

#include "bits/stdc++.h"
using  namespace std;
int main(){
    double f=1.66;
    printf("%.1lf\n",f);//输出1.7
    printf("%d",(int)f);//输出1
}

G: 回文日期

日期题模拟就好啦,注意特判闰年的2月份

代码:

#include<iostream>
#include<algorithm>
using namespace std;
int m[13] = {-1,31,28,31,30,31,30,31,31,30,31,30,31};

bool isYear(int year){
    return year%400 == 0 || (year%4==0 && year%100!=0);
}

//判断该日期只有有效
bool judgeDate(int year,int month,int day){
    if(month == 0 || month > 12)
        return false;
    //日期特判:闰年的二月份
    if(isYear(year) && month == 2)
        return day <=29;
    return day <= m[month];
}

int main(){
    bool flag = false;
    int n;
    scanf("%d",&n);
    for(int i = n+1;i<=89991231;i++){
        int a[8];
        for(int j = 7,t = i; j >= 0; j--, t/=10)
            a[j] = t % 10;
        int year = a[0]*1000+a[1]*100+a[2]*10+a[3];
        int month = a[4]*10+a[5];
        int day = a[6]*10+a[7];
        if(!judgeDate(year,month,day))
            continue;
        //回文
        if(a[0] == a[7] && a[1] == a[6] &&a[2] == a[5] &&a[3] == a[4] ){
            if(!flag){
                cout<<i<<endl;
                flag = true;
            }
            //abab形式
            if(a[0] == a[2] && a[1] == a[3] && a[0] != a[1]){
                cout<<i<<endl;
                break;
            }
        }
    }
    return 0;
}

H: 子串分值和

部分分做法:

反正我比赛时是暴力做的QAQ , $O(n^2)$ 枚举子串位置加上 $O(nlogn)$ 插入子串到set里,整体到了$O(n^{3}logn)$ , 50%数据都过不了…

正解:

思维题 , 不是我刚开始想的$dp$ , 就是算贡献呀 , (刚开始觉得会前后关联 , 不太行 , 就放弃了…) 依次枚举每个字符 $i$ (设此时位置为$p$), 定义$last[i]$表示字符 $i$ 在当前枚举点之前最后一次出现的位置 , 显然这个字母所能贡献的无重复字符串的左端点可以出现在$[last[i]+1,p]$ ，右端点就在$[p,n]$之中 , 而且满足无后效性 , 都是每个字母真正的贡献 , 这不就 $O(n)$了吗
$$\sum _{i=1}^n(i-last[i])\ast (n-i+1)$$

代码:

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
char str[N];
int last[30];
int main() {
    scanf("%s", str + 1);
    int n = strlen(str + 1);
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        res += 1ll * (i - last[str[i] - 'a']) * (n - i + 1);
        last[str[i] - 'a'] = i;
    }
    printf("%lld\n", res);
    return 0;
}

I: 平面切分

部分分做法:

比赛时是暴力做的 , 暴力了N在1-2的情况就放弃了,N=1就是2,N=2有重合,相交不重合,平行不重合3种情况

正解:

在一个平面内，如果所有的直线互不相交，则每添加一条直线，就会额外增加一个平面,即每添加一条非重边，非重边自身就会贡献一个平面（自身）；当这条直线与当前平面内的已有直线每产生一个不同位置的交点，这条直线对平面的总数量的贡献就额外多增加一个

先对直线去重 , 之后每添加一条直线时设置一个空set，将当前直线与当前平面内所有直线的交点$(x,y)$存入set，那么这条直线对平面的贡献个数就是set.size()+1 , 复杂度为$O(n^2{\log }_{2}n)$ , 这里用long double是为了防止精度丢失

借鉴原文 : 试题I 平面切分

代码:

#include <iostream>
#include <set>
using namespace std;
#define debug(x) cout<<#x<<":"<<x<<endl;
const int N = 1e3 + 10;
typedef long long ll;
typedef long double ld;
ld s[N][2];
ll res = 0;
pair<ld, ld> p; //用来记录交点

int main(){
    int n;
    cin >> n;
    set<pair<int,int>> st2;
    for (int i = 0; i < n; ++i){
        int a,b;
        cin>>a>>b;
        //筛掉重边
        if(st2.find({a, b}) == st2.end())
            st2.insert({a, b});
    }
    n=st2.size();
    for(auto k:st2){
        static int i=0,j=0;//被坑了
        s[i++][0]=k.first;
        s[j++][1]=k.second;
    }
    for (int i = 0; i < n; i++){
        set<pair<ld, ld>> points;
        for (int j = 0; j < i; j++){
            if (s[i][0] == s[j][0])//平行
                continue;
            
            p.first = (s[j][1] - s[i][1]) / (s[i][0] - s[j][0]);
            p.second = s[j][0] * p.first + s[j][1];
            points.insert(p);
        }
        res += points.size() + 1; //计入答案
    }
    cout << res + 1 << endl;
    return 0;
}
/*
3
1 1
2 2
3 3
*/

但是这份代码在 acwing 上只通过了部分数据,希望大佬能提出漏洞orz

J: 字串排序

部分分做法:

当时还有 2h+ 做 H,I,J , 想了一会应该是把字母小的放后面 , 看数据要想一个常数很小的$O(n^2)$算法才可能ac掉 , 看样例是从后往前从a开始依次排列2个相同的字母 , 就很好奇 , 推了一会放弃了(菜死了 ) , 决定先得部分分 , 我先写了一个冒泡 , 然后跟着样例拿冒泡试数据 , 因为对于50% 的评测用例有$1<V<100$反正不多, 直接打了1-100的数据 , 就没事干了

正解:

dp,详细思路见博客 : 第十一届蓝桥杯——字串排序（DP）

决赛

A: 美丽的2

签到

答案：563

B: 扩散

思路1:

图形平移后把4个点一次性放到queue去bfs即可 , 注意别dfs , 因为bfs染每一个点时都会贪心地保证其可以向外扩张到最大 (bfs第二次染这个点的效果一定比第一个次染这个点的效果更差 , 所以第二次就不染了) , 而dfs在重复染一个点时会搞混的

代码:

#include<bits/stdc++.h>
using namespace std;

const int N=2025;
int mp[N*3][N*3];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
struct node{
    int x,y;
    int t;
};

int main(){
    mp[0 + N][0 + N]=1;
    mp[2020 + N][11 + N]=1;
    mp[11 + N][14 + N]=1;
    mp[2000 + N][2000 + N]=1;
    queue<node> q;
    q.push(node{0 + N, 0 + N, 0});
    q.push(node{2020 + N, 11 + N, 0});
    q.push(node{11 + N, 14 + N, 0});
    q.push(node{2000 + N, 2000 + N, 0});
    while(!q.empty()){
        node now=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int y=now.y+dy[i];
            int x=now.x+dx[i];
            int st=now.t+1;
            if(!mp[x][y]){
                mp[x][y]=1;
                if(st<2020){
                    q.push(node{x,y,st});
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<N*3;i++)
        for(int j=0;j<N*3;j++)
            ans+=mp[i][j];
    cout<<ans;
    return 0;
}

思路2:

暴力也可以的 , 求无限大的画布里与给出的四个点中至少一个点曼哈顿距离小于等于 2020 的点有多少个 , 那么我们把枚举范围定到二维$[-3000,5000]$，统计有多少个满足条件的就好了

代码:

#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const PII poi[] = {{0, 0}, {2020, 11}, {11, 14}, {2000, 2000}};

bool isBlack(int x, int y, int i){
    int disX = x - poi[i].first;
    int disY = y - poi[i].second;
    return abs(disX) + abs(disY) <= 2020;
}

int main() {
    int answer = 0;
    for (int i = -3000; i <= 5000; i++){
        for (int j = -3000; j <= 5000; j++){
            for (int k = 0; k < 4; k++){
                if (isBlack(i, j, k)){
                    answer++;
                    break;
                }
            }
        }
    }
    printf("%d\n", answer);
    return 0;
}

答案 : 20312088

C: 阶乘约数

思路:

通过算术基本定理发现,我们只要质因数分解,然后带公式即可

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=105;
typedef long long ll;
int a[N];
int main(){
    for(int i=2;i<=100;i++){
        int x=i;
        for(int j=2;j*j<=i;j++){
            while(x%j==0){
                a[j]++;
                x/=j;
            }
        }
        if(x!=1) a[x]++;
    }
    ll ans=1;
    for(int i=1;i<=100;i++)
        if(a[i]) ans*=(a[i]+1);
    printf("%lld",ans);
    return 0;
}

答案 : 39001250856960000

D: 本质上升序列

200个字母得想一个$O(n^3)$左右的算法

思路1:

动态规划 , $dp[i]$表示以$s[i]$为结尾的且和之前子序列本质不同的子序列个数

$$dp\left[i\right]=\{\begin{array}{l}j=0,1,2,\dots ,i-1\\ dp\left[i\right]+dp\left[j\right],s[i]>s[j]\\ dp\left[i\right]-dp\left[j\right],s[i]==s[j]\end{array}$$
为什么$s[i]==s[j]$时$dp\left[i\right]$要减去$dp\left[j\right]$呢 , 举一个刁钻的例子 , 比如abcecde里面的e , 当枚举第二个e时我们经过讨论,发现所有重合的情况,只要减去$dp\left[j\right]$就可以避免掉
这是$O(n^2)$的算法 , 很稳

代码:

#include <bits/stdc++.h>
using  namespace  std;
int dp[205];
int main(){
    string s="tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
    for (int i = 0; i < 200; ++i){
        dp[i]=1;
    }
    int ans=0;
    for (int i = 0; i < 200; ++i){
        for (int j = 0; j < i; ++j){
            if(s[i]>s[j])dp[i]+=dp[j];
            else if(s[i]==s[j])dp[i]-=dp[j];
        }
    }
    for (int i = 0; i < 200; ++i){
        ans+=dp[i];
    }
    cout<<ans<<endl;
}

思路2:

如果序列中出现重复的子串s,我们可以发现肯定是前一个含s的递增子序列的个数要>=其后的含s的递增子序列的个数，可以说其后的答案是第一个的子集，那么对于同一种的递增子序列我们只需要记录其最早出现的即可，后续的出现也不需要管了

所以，我们可以使用bfs，队列内记录递增子串以及该递增子串最后一个字符的位置，对于每次队首的字符串s，其末尾位置设为t，我们只需要从t+1到s.size()-1位置找到任何比s[t]大的即可插入到队列中去，这个过程进行去重、计数即可 , 同样也是$O(n^2)$的算法

代码:

#include<cstdio>
#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
#define mk make_pair
const int inf=0x3f3f3f3f;
typedef long long ll;
int n,m,ans;
char s[205]="tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
unordered_map <string,int> vis;

int main(){
    queue<pair<string,int> >q;
    for(int i=0;i<200;i++){
        string str="";
        str+=s[i];
        if(vis[str]==0){
            vis[str]=1;
            q.push(mk(str,i));
            ans++;
        }
    }
    while(!q.empty()){
        string str=q.front().first;
        int pos=q.front().second;
        q.pop();
        for(int i=pos+1;i<200;i++){
            if(s[i]>s[pos]&&vis[str+s[i]]==0){
                vis[str+s[i]]=1;
                q.push(mk(str+s[i],i));
                ans++;
            }
        }
    }
    printf("%d",ans);
    return 0;
}

答案 : 3616159

E: 玩具蛇

思路:

枚举起点,dfs即可

代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
typedef long long ll;
int ans;
int v[5][5];
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};

void dfs(int x,int y,int sum){
    if(sum==16){
        ans++;
        return;
    }
    for(int i=0;i<4;i++){
        int fx=x+dx[i];
        int fy=y+dy[i];
        if(fx<1||fy<1||fx>4||fy>4||v[fx][fy]==1) continue;
        v[fx][fy]=1;
        dfs(fx,fy,sum+1);
        v[fx][fy]=0;
    }
}
int main(){
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            memset(v,0,sizeof(v));
            v[i][j]=1;
            dfs(i,j,1);
        }
    }
    printf("%d",ans);
    return 0;
}

答案 : 552

F: 皮亚诺曲线距离

注:

红线是自己画的 , 方便分析题目

思路:

好家伙，皮亚诺分形，那就分治，递归时注意图形的转换，分别求从$(0,0)$第一个点和第二个点的距离，再把距离相减,通过calc函数计算距离，计算时把整幅图看做是由9个较小的方格组成的，看看从左下角的方格到该点所在的方格所需要走几个方格，再乘以每个方格内部曲线的长度，接着递归调用函数再求在小方格中到该点所在更小的方格要走几格，最后把各步求得的结果加起来就好了。因为其中有的小方格方向和1阶的方向不太一样，其实它就是做了个对称变换，再它变换回去就可以了，可以不再分别判断，复杂度$O(k)$，可以轻松过掉

代码:

#include<iostream>
#include<cmath>

using namespace std;

typedef pair < int , int > loc;
typedef long long ll;

ll cacl(ll n, loc loca){
    //定位到一个1阶皮亚诺里面,也就是分成9块
    ll pre_len=pow(3,n-1);
    ll total=0;
    ll x=loca.first,y=loca.second;
    loc xy (x / pre_len, y / pre_len);

    //num是在一阶皮亚诺里从左下角到loca所在的方格所占有的方格数
    ll num=0;
    
    if(xy.first==0){//第一列
        num=xy.second+1;
    }
    else if(xy.first==1){//第二列
        if(xy.second==2)num=4;
        else if(xy.second==1)num=5;
        else num=6;
    }
    else{//第三列
        num=7+xy.second;
    }
    //看从左下角的方格到该点所在的方格所需要走几个方格，再乘以每个方格内部曲线的长度
    total+=pre_len * pre_len * (num-1);

    //递归到最后一层了
    if(n==1){
        //结束标志
        return total;
    }

    loc pre(loca);
    
    //第一列
    if(num==1);
    else if(num==2){//x左右颠倒
        pre=make_pair(-(x-pre_len+1),y-pre_len);
    }
    else if(num==3){
        pre=make_pair(x,y-2*pre_len);
    }

    //第二列
    else if(num==4){//y左右颠倒
        pre=make_pair(x-pre_len,-(y-3*pre_len+1));
    }
    else if(num==5){//x,y左右颠倒
        pre=make_pair(-(x-2*pre_len+1),-(y-2*pre_len+1));
    }
    else if(num==6){//y左右颠倒
        pre=make_pair(x-pre_len,-(y-pre_len+1));
    }

    //第三列
    else if(num==7){
        pre=make_pair(x-2*pre_len,y);
    }
    else if(num==8){//x左右颠倒
        pre=make_pair(-(x-3*pre_len+1),y-pre_len);
    }
    else{
        pre=make_pair(x-2*pre_len,y-2*pre_len);
    }
    return total+cacl(n-1,pre);
}

int main(){
    ll n,x1,y1,x2,y2;
    cin>>n>>x1>>y1>>x2>>y2;
    loc first(x1, y1),second(x2, y2);
    cout<<abs(cacl(n,first)-cacl(n,second));
    return 0;
}

G: 游园安排

只写了$O(n^2)$的暴力 , 虽然知道最长上升子序列(LIS)有$O(nlogn)$的 , 但是当时就没好好学…打完听pyf说写的二分 , 顿时感觉自己更菜了

LIS的状态转移方程：
d p [ i ] = max ⁡ { 1 , d p [ j ] + 1 } ( j = 1 , 2 , … , i − 1 & & a [ i ] ≤ a [ j ] ) \begin{aligned}dp\left[ i\right] =\max \left\{ 1,dp\left[ j\right] +1\right\} \\ \left( j= 1,2,\ldots ,i-1\& \& a\left[ i\right] \leq a\left[ j\right] \right) \end{aligned} dp[i]=max{1,dp[j]+1}(j=1,2,…,i−1&&a[i]≤a[j])​

先给一道母题:

最长上升子序列 II

思路:

较难理解的地方在于栈中序列虽然递增，但是每个元素在原串中对应的位置其实可能是乱的，那为什么这个栈还能用于计算最长子序列长度呢？

实际上这个栈不用于记录最终的最长子序列，而是以$stk[i]$结尾的子串长度最长为 $i$ (或者说长度为 $i$ 的递增子串中，末尾元素最小的是$stk[i]$),这就是为什么新进来的元素要不就在末尾增加，要不就替代第一个大于等于它元素的位置，找元素去替代的复杂度是$O(logn)$，那么整体的复杂度就是$O(nlogn)$了

这里的替换就蕴含了一个贪心的思想，对于同样长度的子串，我们希望它的末端越小越好，这样就有更多的机会拓展了

母题的二分代码:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(void){
    int n;
    cin >> n;
    vector<int>arr(n);
    for (int i = 0; i < n; ++i)cin >> arr[i];

    vector<int>stk;//模拟堆栈
    stk.push_back(arr[0]);

    for (int i = 1; i < n; ++i){
        if (arr[i] > stk.back())//如果该元素大于栈顶元素,将该元素入栈
            stk.push_back(arr[i]);
        else//替换掉第一个大于或者等于这个数字的那个数
            *lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];
    }
    cout << stk.size() << endl;
    return 0;
}

本题的代码:

#include<iostream>
#include<algorithm>

using namespace std;
const int inf=0x3f3f3f3f;
typedef long long ll;
const int N=100005;
int n,m;
string s,a[N],b[N],c[N];

int cnt=0;

//分割字符串到a数组,下标从1到cnt
void spilt(){
    cin>>s;
    for(int i=0;i<s.length();i++){
        if(s[i]>='A'&&s[i]<='Z'){
            a[++cnt]+=s[i];
            i++;
            while(s[i]>='a'&&s[i]<='z'){
                a[cnt]+=s[i];
                i++;
            }
            i--;
        }
    }
}
int main(){
    spilt();
    int sum=1;
    int p[N];
    b[1]=a[1];//模拟堆栈
    p[1]=sum;//记录最终答案(以a的下标形式记录)
    for(int i=2;i<=cnt;i++){
        if(a[i]>b[sum]){
            b[++sum]=a[i];//将元素a[i]入栈
            p[i]=sum;//记录答案
        }
        else{
            //找到第一个大于或者等于a[i]的那个数
            m=lower_bound(b+1,b+1+sum,a[i])-b;
            b[m]=a[i];//替换
            p[i]=m;//记录答案
        }
    }

    //定位答案
    int temp=sum;
    for(int i=cnt;i>=1;i--){
        if(temp==0) break;
        if(p[i]==temp){
            c[temp]=a[i];
            temp--;
        }
    }

    for(int i=1;i<=sum;i++){
        cout<<c[i];
    }
    return 0;
}

H: 答疑

$e_i$的取值很迷，数据看是$O(n^2)$的算法，如果结构体sort+cmp去贪心就是$O(n)$了，所以就想了另一种貌似更靠谱的 贪心，for外层是每次找最优的一个人，找够n人，for内层是看哪个人最优，每次贪心的找最小花费累加就是答案了

代码:

#include <cstdio>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 1010;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll a[N], b[N], c[N];
bool vis[N];

int main(){
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++){
        ll minCost = INF;
        ll minPos = -1;
        for (ll j = 1; j <= n; j++){
            if (vis[j]){
                continue;
            }
            //他消耗的时间
            ll cost = a[j] + b[j];
            //他影响后人的时间
            cost += (n - i) * (a[j] + b[j] + c[j]);
            if (cost < minCost){
                minCost = cost;
                minPos = j;
            }
        }
        ans += minCost;
        vis[minPos] = true;
    }
    printf("%lld\n", ans);
    return 0;
}

放上结构体排序的代码:

#include<cstdio>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
typedef long long ll;
int n,m;
ll ans=0,sum=0;

struct node{
    int z,s1,s2;
}s[1000];

int cmp(node a,node b){
    if(a.s2!=b.s2) return a.s2<b.s2;
    else return a.s1<b.s1;
}

int main(){
    int x,y;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d %d %d",&x,&y,&s[i].z);
        s[i].s1=x+y;
        s[i].s2=x+y+s[i].z;
    }
    sort(s,s+n,cmp);
    for(int i=0;i<n;i++){
        ans+=s[i].s1;//进入+解答
        sum+=ans;//记录发消息的时间点
        ans+=s[i].z;//离开
    }
    printf("%lld",sum);
    return 0;
}

I: 出租车

大模拟 , 暂时不想看 , 待补…

J: 质数行者

$O(n^3)$的dp骗分吧 , 正解要用矩阵快速幂?

先打个素数表

const int maxn=10001;
int prime[maxn],num=0;
bool p[maxn];
void Find_Prime(){
    memset(p,0,sizeof p);//默认全素数 
    for(int i=2;i<maxn;i++){
        if(p[i]==false){
            prime[num++]=i;
            for(int j=i+i;j<maxn;j+=i)
                p[j]=true;
        }
    }
}
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,
103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,
197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307

代码:

#include <cstdio>
#include <algorithm>
#include <map>
#include <iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int MAXN = 310;
const int MOD = 1e9 + 7;

ll dp[MAXN][MAXN][MAXN];
//前300以内的质数
int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293};

int main(){
    //debug((sizeof primes)/4)//有62个
    int n, m, w;
    int r1, c1, h1, r2, c2, h2;
    scanf("%d%d%d", &n, &m, &w);
    scanf("%d%d%d%d%d%d", &r1, &c1, &h1, &r2, &c2, &h2);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            for (int k = 1; k <= w; k++){
                if (i == 1 && j == 1 && k == 1){
                    dp[i][j][k] = 1;
                }
                if (i == r1 && j == c1 && k == h1){
                    continue;
                }
                if (i == r2 && j == c2 && k == h2){
                    continue;
                }
                for (int p = 0; p < 62; p++){
                    if (i - primes[p] >= 1){
                        dp[i][j][k] = (dp[i][j][k] + dp[i - primes[p]][j][k]) % MOD;
                    }
                    if (j - primes[p] >= 1){
                        dp[i][j][k] = (dp[i][j][k] + dp[i][j - primes[p]][k]) % MOD;
                    }
                    if (k - primes[p] >= 1){
                        dp[i][j][k] = (dp[i][j][k] + dp[i][j][k - primes[p]]) % MOD;
                    }
                }
            }
        }
    }
    printf("%lld\n", dp[n][m][w]);
    return 0;
}

但是这是理想情况，想暴力出300以内的数据，复杂度最高在$$300^3\ast 62\ast 4=6.696e9$$感觉 $62\ast 4$ 这个常数有点大，既然本身就跑不到 $300$ 的数据，不妨改一下代码 , 争取容错率强一些，就改成了这样:

代码:

#include <cstdio>
#include <algorithm>
#include <map>
#include <iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int MAXN = 310;
const int MOD = 1e9 + 7;

ll dp[MAXN][MAXN][MAXN];

int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151};

int main(){
    //debug((sizeof primes)/4)//有36个
    int n, m, w;
    int r1, c1, h1, r2, c2, h2;
    scanf("%d%d%d", &n, &m, &w);
    scanf("%d%d%d%d%d%d", &r1, &c1, &h1, &r2, &c2, &h2);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            for (int k = 1; k <= w; k++){
                if (i == 1 && j == 1 && k == 1){
                    dp[i][j][k] = 1;
                }
                if (i == r1 && j == c1 && k == h1){
                    continue;
                }
                if (i == r2 && j == c2 && k == h2){
                    continue;
                }
                for (int p = 0; p < 36; p++){
                    if (i - primes[p] >= 1){
                        dp[i][j][k] = (dp[i][j][k] + dp[i - primes[p]][j][k]) % MOD;
                    }
                    if (j - primes[p] >= 1){
                        dp[i][j][k] = (dp[i][j][k] + dp[i][j - primes[p]][k]) % MOD;
                    }
                    if (k - primes[p] >= 1){
                        dp[i][j][k] = (dp[i][j][k] + dp[i][j][k - primes[p]]) % MOD;
                    }
                }
            }
        }
    }
    printf("%lld\n", dp[n][m][w]);
    return 0;
}

复杂度最高在$$151^3\ast 36\ast 4=4.958e8$$感觉容错率高了一些，算是示范了一下如何混分QAQ

结语

初赛决赛题目链接

部分思路借鉴自大佬 :

2020年第十一届蓝桥杯国赛 B组个人题解

2020第十一届蓝桥杯大赛软件类国赛 C/C++ 大学 B 组

第一次打 , 国二 , 希望下一次能有更好的发挥