Fork me on GitHub
image frame

My Blog

蓝桥杯复盘

前言

之前一直考虑复盘一下今年的蓝桥杯，但是苦于没有时间（摸鱼摸掉了）。所以拖到现在才写。
我参加的是C++ B组，最后省一中等偏上。
由于我语文不太好，行文整体偏向于流水账。

Day0

敲了一些常用的数据结构，比如线段树、树状数组、ST表、倍增LCA等等。还写了一下图论最短路的模板题（dijkstra、SPFA、Floyd）。
晚上吃完饭突然发现不能用无线鼠标，于是去买了一个有线鼠标，手感一般（和机房的类似）。买完鼠标后晚上写了一些数论的板子（线性筛、exgcd、线性求逆元等等）。最后看了一些洛谷上一些经典的线性dp（但是没有看递推题单，结果G题推错方程当场炸掉20分）。看完发现也十二点多了，遂睡觉。
晚上比较紧张睡不着，三点钟看了一次手机，大概四点才睡的。

Day1 上午

早上起的比较晚，于是没吃早饭直接开打了。
开考后没几分钟就收到了5张黄牌，吓得我都不敢在动了。但是好在监考老师说没事。于是开始写题。以下是考试的时间线（不准确）：
9:05 写掉A
9:06 看到B和日期有关，遂不写，开始看C
9:14 发现C是模拟，于是切掉
9:15-9:20 开始看D，把玩了一些小案例。发现就是对于每个元素在2(n-i)和2(i-1)之间取最大值。
9:31 写掉D，开始看E
9:40 E看不懂，开始看F，一眼看出暴力前缀和可以得到70。于是直接开始写。
9:50 码出了F的二维前缀和，放着开始看G
9:55 发现G好像有点像原题，通过分析小样例可以一眼看出边界条件，于是开始重点突破递推方程。
10:10 感觉递推方程的f[i][j]意义不明，遂放着，开H
10:15 看完H感觉是搜索，但是又怕爆复杂度，想着重新优化一下降到O(nlogn)以下。开始犯困了。

matlab第四次作业

第一题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
clc
clear
a=input('输入三角形的一条边 ');
b=input('输入三角形的一条边 ');
c=input('输入三角形的一条边 ');
if(a>0&&b>0&&c>0)
    if((a+b>c)&&(a+c>b)&&(b+c>a))
        p=(a+b+c)/2;
        s=sqrt(p*(p-a)*(p-b)*(p-c));
        fprintf('三角形面积为%f\n',s);
    else
        fprintf('不能构成一个三角形\n');
    end
else
    fprintf('不能构成一个三角形\n');
end

第二题代码

1
2
3
4
5
6
7
8
clc
clear
n=input('输入一个数n ');
sum=0;
for ii=1:n
    sum=sum+ii;
end
sum

第三题代码

1
2
3
4
5
6
7
8
function res=myfactorial(n)
res=1;
if n==1
    res=1;
else
    res=myfactorial(n-1)*n;
end
end

第四题代码

1
2
3
4
5
6
7
a=input('输入一个数a ');
b=input('输入一个数b ');
t=a;
a=b;
b=t;
fprintf('a=%d\n',a);
fprintf('b=%d\n',b);

第五题代码

1
2
3
4
5
6
7
clc
clear
a=input('输入二次项系数a ');
b=input('输入一次项系数b ');
c=input('输入常数c ');
r=roots([a b c]);
disp(r);

第六题代码

1
2
3
4
function [r,theta]=Coord_Trans(x,y)
r=sqrt(x*x+y*y);
theta=atan(y/x);
end

第七题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
clc
clear
n=input('学生成绩: ');
switch floor(n/10)
    case {0,1,2,3,4,5}
        disp('不及格');
    case {6,7}
        disp('及格');
    case {8}
        disp('良好');
    case {9,10}
        disp('优秀');
    otherwise
        disp(-1);
end

第八题代码

1
2
3
4
5
6
7
8
9
10
11
clc
clear
a=1;b=1;c=2;n=3;
while c<=500
    c=a+b;
    %fprintf('%d %d\n',a,b);
    a=b;
    b=c;
    n=n+1;
end
fprintf("%d %d\n",c,n);

第九题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
clc
clear
n=[1 2 3 5 7];
buf=n;
for ii=1:5
    cnt=0;
    while(1)
        if (cnt~=0&&n(ii)==1)
            break;
        else
            if mod(n(ii),2)==0
                n(ii)=n(ii)/2;
            else
                n(ii)=n(ii)*3+1;
            end
            cnt=cnt+1;
        end
    end
    fprintf('%d经过%d步变为1\n',buf(ii),cnt);
end

随机好句摘抄

在你最冷的时候，有人不顾自己寒冷抱着你，这就是幸福。

所谓辉煌的人生，不过是欲望的囚徒。

我有故人抱剑去，斩尽春风未肯归。

第二章

第一题

　　只需要把$x_1x_2$换成y在利用0-1规划的性质对条件进行变形即可。

第二题

　　很明显决策变量是小区，要达到全部覆盖只需要满足每个小区能选的小学数量大于1即可。
　　这题连数据都不需要。

1
2
3
4
5
6
7
8
9
10
11
12
13
model:
sets:
col/1..6/:x;
endsets
min=@sum(col:x);
x(1)+x(2)+x(3)>1;
x(2)+x(4)>1;
x(3)+x(5)>1;
x(4)+x(6)>1;
x(5)+x(6)>1;
x(1)>1;
x(2)+x(4)+x(6)>1;
end

第三题

　　没啥好说的引入0-1的限制就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
model:
sets:
she/1..6/;
com/1..4/;
link(she,com):c,x;
endsets
data:
c=4 2 3 4
6 4 5 5
7 6 7 6
7 8 8 6
7 9 8 6
7 10 8 6;
enddata
max=@sum(link:c*x);
@for(she(i):@sum(com(j):x(i,j))=1);
@for(com(j):@sum(she(i):x(i,j))>1);
@for(link:@bin(x));
end

第四题

　　待更新

第五题

　　首先考虑到比较小的数据范围，可以搜索出料头小于1米的切割方案（大于1米则可以切出一根1米的棍子）。
　　对于这七种切割方案进行规划，即可得到最小使用根数（注意材料根数要是整数）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
model:
sets:
row/1..3/;
col/1..7/:x;
link(row,col):a;
endsets
data:
a=1 2 0 0 0 0 1
0 0 3 2 1 0 1
4 1 0 2 4 6 1;
enddata
min=@sum(col:x);
@for(row(i):@sum(col(j):a(i,j)*x(j))>100);
@for(col:@gin(x));
end

第六题

　　和第三题很像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
model:
sets:
car/1..8/;
pos/1..5/;
link(pos,car):c,x;
endsets
data:
c=30 25 18 32 27 19 22 26
29 31 19 18 21 20 30 19
28 29 30 19 19 22 23 26
29 30 19 24 25 19 18 21
21 20 18 17 16 14 16 18;
enddata
min=@sum(link:c*x);
@for(pos(i):@sum(car(j):x(i,j))=1);
@for(car(j):@sum(pos(i):x(i,j))<1);
@for(link:@bin(x));
end

第一章

第一题

　　没啥好说的，直接用linprog干就完事。只要注意把maxz取负求最小值即可。大于等于的条件也要记得加负号。

1
2
3
4
5
6
7
8
clc
clear
c=[3 -1 -1]';
a=[1 -2 1;4 -1 -2];
b=[11;-3];
aeq=[-2 0 1];beq=1;
[x,fval]=linprog(-c,a,b,aeq,beq,zeros(3,1));
fval=-fval

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
model:
sets:
col/1..3/:c,x;
row/1..2/:b;
link(row,col):a;
endsets
data:
c=3 -1 1;
a=1 -2 1 4 -1 -2;
b=11 -3;
enddata
max=@sum(col:c*x);
@for(row(i):@sum(col(j):a(i,j)*x(j))<b(i));
-2*x(1)+x(3)=1;
end

第二题

　　只要注意把$\vert x \vert$变换为$u_i+v_i$，把$x$变换为$u_i-v_i$进行建模即可。

1
2
3
4
5
6
7
8
9
10
clc
clear
c=1:4;
c=[c,c]';
aeq=[1 -1 -1 1;1 -2 1 -3;1 -1 -2 3];
beq=[0;1;-0.5];
aeq=[aeq,-aeq];
[uv,fval]=linprog(c,[],[],aeq,beq,zeros(8,1));
x=uv(1:4)-uv(5:8)
fval

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
model:
sets:
col/1..4/:c,x;
row/1..3/:b;
links(row,col):a;
endsets
data:
c=1 2 3 4;
a=1 -1 -1 1 1 -1 1 -3 1 -1 -2 3;
b=0 1 -0.5;
enddata
min=@sum(col:c*@abs(x));
@for(row(i):@sum(col(j):a(i,j)*x(j))=b(i));
@for(col:@free(x)); !x的值可正可负
end

第三题

　　这里我是用的非线性的优化函数fmincon，但是用线性优化函数再加上整数限制算可能更好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
clc
clear
f=@(x) -(x(1)+x(2)+1.65*x(8)+2.3*x(9)-(300/6000)*(5*x(1)+10*x(6))-(321/10000)*(7*x(2)+9*x(7)+12*x(9))-(250/4000)*(6*x(3)+8*x(8))-(783/7000)*(4*x(4)+11*x(9))-(200/4000)*x(5));
a=zeros(5,9);
a(1,1)=5;a(1,6)=10;
a(2,2)=7;a(2,7)=9;a(2,9)=12;
a(3,3)=6;a(3,8)=8;
a(4,4)=4;a(4,9)=11;
a(5,5)=7;
b=[6000;10000;4000;7000;4000];
aeq=[1 1 -1 -1 -1 0 0 0 0;0 0 0 0 0 1 1 -1 0];
beq=[0;0];
[x,fval]=fmincon(f,randn(9,1),a,b,aeq,beq,zeros(9,1));
fval=-fval

第四题

　　本题使用matlab求解很不方便，这里只提供lingo代码。
　　这道题关键在于对三个仓载货量和最大容许量成比例的建模。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
model:
sets:
wu/1..4/:a,b,c,y;
cang/1..3/:w,v;
links(wu,cang):x;
endsets
data:
c=3100 3800 3500 2850;
b=480 650 580 390;
a=18 15 23 12;
w=10 16 8;
v=6800 8700 5300;
enddata
max=@sum(wu(i):c(i)*@sum(cang(j):x(i,j)));
@for(wu(i):@sum(cang(j):x(i,j))<a(i));
@for(cang(j):@sum(wu(i):x(i,j))<w(j));
@for(cang(j):@sum(wu(i):b(i)*x(i,j))<v(j));
@for(cang(j):@sum(wu(i):x(i,j))/w(j)=(@sum(wu(i):x(i,1))/w(1)));
@for(wu(i):y(i)=@sum(cang(j):x(i,j)));
end

!a(i)为运输货物i的重量
!b(i)为单位货物所占的空间
!c(i)为单位货物的利润
!y(i)为四种物资的量
!w,v分别是空间和体积限制

第五题

　　这题和上一题一样，由于决策变量是二维变量使用lingo求解更为方便

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
model:
sets:
row/1..3/;
col/1..4/:b;
link(row,col):c,x;
endsets
data:
b=62 83 39 91;
c=132 0 100 103
  0 91 100 100
  106 89 100 98;
@text('ex.txt')=@table(x); !存到文本文件中;
enddata
min=@sum(link:c*x);
@for(col(j):@sum(row(i):x(i,j))=b(j));
end

97. 约数之和 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod =9901; 
ll a,b,ans;
ll qpow(ll x,ll k)
{
    ll res=1;
    x%=mod;
    while(k)
    {
        if(k&1)
            res=(res*x)%mod;
        x=(x*x)%mod;
        k>>=1;
    }
    return res;
}
ll sum(ll p,ll k)
{
    if(k==0)
        return 1;
    if(k%2==0)
        return (p%mod*sum(p,k-1)+1)%mod;
    else
        return (1+qpow(p,k/2+1))*sum(p,k/2)%mod;
}
int main()
{
    cin >> a >>b;
    ans=1;
    for(int i=2;i<=a;i++)
    {
        int cnt=0;
        while(a%i==0)
        {
            cnt++;
            a/=i;
        }
        if(cnt)
            ans=ans*sum(i,cnt*b)%mod;
        //cout<<a<<endl;
    }
    if(!a)
        ans=0;
    cout << ans<<endl;
    return 0;
}

243. 一个简单的整数问题2 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn =1e5+1;
typedef long long ll;
ll d[4*maxn],b[4*maxn],a[maxn],n,m,l,r,k;
string op;
void build(ll s,ll t,ll p)
{
    ll mid=(t+s)>>1;
    if(s==t)
    {
        d[p]=a[s];
        return ;
    }
    build(s,mid,p*2);
    build(mid+1,t,p*2+1);
    d[p]=d[p*2]+d[p*2+1];
}
void pushdown(ll s,ll t,ll p)
{
    ll m=(s+t)>>1;
    if(b[p])
    {
        d[p*2]+=(m-s+1)*b[p];
        d[p*2+1]+=(t-m)*b[p];
        b[p*2+1]+=b[p];b[p*2]+=b[p];
        b[p]=0;
    }
}
void add(ll l,ll r,ll c,ll s,ll t,ll p)
{
    ll mid=(s+t)>>1;
    if(l<=s&&t<=r)
    {
        d[p]+=(t-s+1)*c;
        b[p]+=c;
        return ;
    }
    pushdown(s,t,p);
    if(l<=mid)
        add(l,r,c,s,mid,p*2);
    if(r>mid)
        add(l,r,c,mid+1,t,p*2+1);
    d[p]=d[p*2]+d[p*2+1];
}
ll getsum(ll l,ll r,ll s,ll t,ll p)
{
    ll res=0;
    if(l<=s&&t<=r)
    {
        return d[p];
    }
    ll mid=(s+t)>>1;
    pushdown(s,t,p);
    if(l<=mid)
        res+=getsum(l,r,s,mid,p*2);
    if(r>mid)
        res+=getsum(l,r,mid+1,t,p*2+1);
    return res;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,n,1);
    while (m -- )
    {
        cin>>op;
        if(op=="Q")
        {
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",getsum(l,r,1,n,1));
        }
        else
        {
            scanf("%lld%lld%lld",&l,&r,&k);
            add(l,r,k,1,n,1);
        }
    }
    return 0;
}

242. 一个简单的整数问题 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+1; 
ll a[maxn],tree[maxn],n,m,l,r,k;
char op[2];
ll lowbit(ll x)
{
    return x&-x;
}
void add(ll x,ll k)
{
    while(x<=n)
    {
        tree[x]+=k;
        x+=lowbit(x);
    }
}
ll getsum(ll x)
{
    ll res=0;
    while(x)
    {
        res+=tree[x];
        x-=lowbit(x);
    }
    return res;
}
int main()
{
    cin>>n>>m;
    for (int i = 1; i <= n; i ++ )
        scanf("%lld",a+i);
    while(m--)
    {
        scanf("%s",op);
        if(strcmp(op,"Q")==0)
        {
            scanf("%lld",&l);
            printf("%lld\n",a[l]+getsum(l));
        }
        else if(strcmp(op,"C")==0)
        {
            scanf("%lld%lld%lld",&l,&r,&k);
            add(l,k);add(r+1,-k);
        }
    }
    return 0;
}
  • Copyrights © 2022-2024 CPY
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信