在十四届蓝桥杯开赛前一星期开始复习

十三届蓝桥杯国赛原题

1.2022

#include
using namespace std;

long long int f[2023][11][2023];  //表示前2022个物品选择10个物品，体积总和为2022的方案个数  ,,数组下标为1开始，所以使2023，11，2023

int i, j, k;
int main()
{
    for (i = 0; i <= 2022; i++)  //因为体积为0，物品为0的所有情况都只有一种选择，即什么都不选
        f[i][0][0] = 1;
    for (i= 1; i <= 2022; i++)  //枚举所有物品
    {
        for (j = 1; j <= 10; j++)   //选了几个物品
        {
            for (k = 1; k <= 2022; k++)  //枚举体积
            {
                f[i][j][k] = f[i-1][j][k];  //不选第i个物品
                if (k >= i)  //选第i个物品
                    f[i][j][k] += f[i-1][j - 1][k - i];
            }
        }
    }
    cout << f[2022][10][2022];
    return 0;
}

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

2.钟表

试题 B: 钟表
【问题描述】
在 12 小时制的钟表中，有分针、时针、秒针来表示时间。记分针和时
针之间的夹角度数为 A（0 ≤ A ≤ 180）、分针和秒针之间的夹角度数为 B（0 ≤ B ≤ 180）。而恰好在 s 时 f 分 m 秒时，满足条件 A = 2B 且 0 ≤ s ≤ 6； 0 ≤ f < 60；0 ≤ m < 60，请问 s, f, m 分别是多少。
注意时针、分针、秒针都围绕中心匀速转动。
提交格式为三个由一个空格隔开的整数，分别表示 s, f, m。如 3 11 58表示
3 点 11 分 58 秒
问题解析
本人答案是：4 48 0.
我是这么想的，常见的那种时钟，分针和秒针走了，时针也是会跟着走的，比如有的人可能想着是6 0 15这样，但是秒针走了时针和分针其实也在走，严格来说此时分针和秒针并不是90度，分针和时针也不是180度，所以我认为是不行的。
我们知道秒针走一圈（360度）是60秒，即秒针一秒钟可以走6度；分针60分钟走一圈，即10秒钟走1度；时针12小时走一圈，即120秒走一度。根据范围我们知道我们可以枚举的最大时间是6小时59分59秒，即25199秒，我们只要从0枚举到25199，通过秒数算出分针、时针和秒针走过的角度，相减后得到角A和角B，再判断是否满足A=2*B即可。算出来后发现有两个结果：0 0 0和4 48 0，0 0 0被官方发公告ban了，所以我写的是4 48 0.
————————————————
版权声明：本文为CSDN博主「你好_Ä」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/fnmdpnmsl/article/details/125347764

#include
using namespace std;
int main()
{
    for(int i = 0; i < 25960 ; i++)
    {
        double m = (double) 1/10.0 * i ;
        double h = (double) 36 / 4320 * i ;
        double s = (double)  6 / 1.0 * i ;

        while(m > 360) m -= 360 ;
        while(s > 360) s -= 360 ;
        double a , b ;
        a = abs(m - h);
        b = abs(m - s);
        if(a == 2 * b) cout << i / 3600 << " " << i / 60 % 60 << " " << i % 60 << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3卡牌

2.解题思路
从题意出发，发现想直接求出答案，并没有一个很高效的办法，但如果给定我们一个 x ，让我们去判断能否凑出 x套牌，这个操作对我们来说并不难。所以我们可以考虑二分答案的做法，既然要二分那肯定得具有两段性，不难理解，如果我们可以凑出x xx套牌，那么[1,x−1]套牌也都是一定可以凑出来的,而并不一定可以凑出大于x xx的套牌数。
那么二分的check判断函数我们该如何书写呢？显然要凑够x套牌，我们需要使得每种类似的牌都有x xx张，如果已经当前判断牌的类型的数量已经大于等于x ，则不需要使用空白牌补充。如果使用当前类型的牌数加上它最多可加上的空白牌数仍然小于x ,那么此时可以直接返回false了。如果当前牌类型允许补充空白牌的数量足够给我们进行补充到 x，那么我们让空白牌的数减去需要使用的数量，如果不够用了，那么也返回false，如果可以完成所有的牌的填充，则返回true。
另外一个需要注意的点是r 的上限，以及m 的范围。m 的最大范围已经超出int，所以我们要使用long long，另外n 的最大范围是2×10^5
，而m 最大取到n^2
,能凑出的最大套牌数应该是2n,所以r的上限一定不能设小了。
整体做法的时间复杂为:O(nlogn)
————————————————
版权声明：本文为CSDN博主「执 梗」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_57487901/article/details/127124262

#include 
using namespace std;
typedef long long ll ;
const int N = 2e5 + 10;
ll n , m ;
int a[N] , b[N];
bool check(int mid , int a[] , int b[])
{
  ll ans = m;
	for (int i = 0; i < n; i++)
	{
		if (a[i] < mid)
		{
			if (mid - a[i] > b[i] || mid - a[i] > ans)return false;
			else ans -= mid - a[i];
		}
	}
	return ans >= 0;

  //bool flag = true ;
   //for(int i = 0 ; i < n ; i++) 
   //{
   //  if(a[i] + b[i] < m) flag = false;
  // }
   //return flag;
}
int main()
{
  cin >> n >> m ;
  for(int i = 0 ; i < n ; i++) cin >> a[i];
  for(int i = 0 ; i < n ; i++) cin >> b[i];
  int l = 0 , r = 2*N ;
  while(l < r)
  {
    int mid = l + r + 1 >> 1;
    if(check(mid , a , b))   l = mid ;
    else  r = mid - 1 ;
  }
  cout << l ;
  // 请在此输入您的代码
  return 0;
}
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

4最大数字

看上去N的范围貌似很大，达到了1e17的范围，但其实我们最多只需要考虑这最多17位数，所以可以想到爆搜得到答案。
一个数的大小是从左到右依次判断，所以我们从最左边开始枚举，我们无需关注后面的数，要利用自己的1号操作和2号操作保证当前这个数位的数一定要尽可能最大
然后分别考虑两种操作，首先两种操作不可能混用，因为它们是抵消的效果，所以要么对这个数全使用1操作，要么2操作。假设某个数位的值为x,首先考虑1号操作，使用后可以让该数位变大，出于贪心考虑，我们想让它变成9，那么需要进行9-x次1号操作，当然可能此时1号操作并不足以让我们将x变成9，但我们还是使用剩余的全部的次数将其变大，所以每次考虑1号操作应该使用的操作数t应该为t=min(n,9-x),此时x将变为x+t，然后进行下一位的判断。
其次我们考虑2号操作，这个的判断比较简单，它是让某个值减小，唯一能让某个数变大的机会就是将其减到0后再减就会变成9。那么这样操作需要的次数就是x+1，如果操作次数不够，那我们宁愿不使用，因为这只会让这个数位变得更小。
在深搜dfs的过程中，参数记录遍历到第几个数位以及此时累计的和，当搜索完所有数位后，将此时的和与答案进行一个取max，最后的值则为答案。
————————————————
版权声明：本文为CSDN博主「执 梗」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_57487901/article/details/127150940

#include 
using namespace std;
string s ;
int a,b;
long long ans = 0 ;
void dfs(int i , long long v)
{
  int m = s[i] - '0' ;
  if(s[i]) 
  {
    int t = min(a,9-m);
    a -= t;
    dfs(i+1, v*10 + m + t);
    a += t ;
    if(b > m)
    {
      b -= m +1  ;
      dfs(i + 1 , v * 10 + 9) ;
      b += m + 1 ;
    }
  }
  else 
  {
    ans = max(ans , v);
  }
}
int main()
{
  cin >> s >> a >> b ;
  dfs(0,0);
  cout << ans ;
  return 0;
}
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

4.5 Dijkstra算法

acwing例题：Dijkstra求最短路I

#include
#include
using namespace std;
const int N = 510 ;
int g[N][N];
int n , m ;
bool st[N];
int d[N];
int dijkstra()
{
    memset(d,0x3f,sizeof d);
    d[1] = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        int t = -1 ;
        for(int j = 1 ; j <= n ; j++)
        {
            if(!st[j] && (t == -1 || d[t] > d[j]))
            {
                t = j ;
            }
        }
        
        st[t] = true;
        
        for(int j = 1 ; j <= n ; j++)
        {
            d[j] = min(d[j] , d[t] + g[t][j]) ; 
        }
    }
    
    if(d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}
int main()
{
    cin >> n >> m ;
    memset(g, 0x3f, sizeof g);
    while(m--)
    {
        int a , b, c ;
        cin >> a >> b >>c ;
        g[a][b] = min(g[a][b] , c);
    }
    int t = dijkstra();
    cout << t;
    return 0;
}
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

5出差

题意很明显考察的是一个最短路径问题，虽然题目说了给定的是双向边，但是假设g[i]的含义是到达i城市需要隔离的时间。假设有城市A和城市B,且两城市存在一条权值为w的双向边，当我们从A去到B所需要花费的时间应该是w+g[B],当我们从B去到A所花的时间应该是w+g[A]。所以虽然题意是双向边，但是方向不同的情况下，权值并不一定相同，所以我们应该看成两条边。
也就是说,存在邻接矩阵gra[][]，gra[i][j]表示从i到j的所需要的时间，g[i][j]和g[j][i]并不一定是相等的。所以我们在建图时应该分清楚，需要注意的是终点n的隔离时间我们是不考虑的，所以我们要把它置为0。然后建图完毕后直接跑一遍最短路算法即可，由于n nn的最大只有1000,所以使用朴素dijkstra算法也是能过的。
————————————————
版权声明：本文为CSDN博主「执 梗」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_57487901/article/details/127132577

#include
using namespace std;
const int N = 1010 ;
int w[N];
int g[N][N] ;
int n , m ;
bool st[N];
int d[N];
int dijkstra()
{
  memset(d , 0x3f , sizeof d);
  d[1] = 0 ;
  for(int i = 1; i <= n ; i++)
  {
    int t = -1 ;
    for(int j = 1 ; j <= n ; j++)
    {
      if(!st[j] && (t == -1 || d[t] > d[j]))
        t= j ;
    }

      for(int j = 1 ; j <= n ; j++)
        d[j] = min(d[j] , d[t] + g[t][j]);

      st[t] = true ;
  }
  return d[n];
}
int main()
{
  cin >> n >> m;
  for(int i = 1 ; i <= n ; i++) cin >> w[i];
  w[n] = 0;
  memset(g , 0x3f , sizeof g);
  while(m--)
  {
    int a,b,c;
    cin >> a >> b >> c;
    g[a][b] = w[b] + c;
    g[b][a] = w[a] + c;
  }
  cout << dijkstra() ;
  return 0;
}
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