知识点:下一届是第几届蓝桥杯……
新一届蓝桥杯大赛即将在2024年拉开序!
作为大一新生的小蓝,在听说了这场盛大的比赛后,对其充满了期待与热情。但作为初次参赛的新手,他对蓝桥杯的相关赛制和历史并不了解。于是,他决定寻求上届蓝桥杯总冠军小桥的指导。
小桥的实力不容小觑,她只参加过一次蓝桥杯,就斩获了第14届的总冠军。
小桥可以指导小蓝,但她要先确认小蓝对蓝桥杯的热爱是否真挚。于是她向小蓝提出了一个问题:即将开始的蓝桥杯是第几届的。
作为新生的小蓝自然不知道答案,因此请你帮助小蓝回答这个问题。
注意:请使用阿拉伯数宁表示答案
点击蓝桥杯官网查看下一届是第几届……
- #include
- using namespace std;
- int main()
- {
- cout << 15 << endl;
- return 0;
- }
小蓝家要装修了,小蓝爸爸买来了很多块(你可以理解为数量无限) 2 x 3 规格的地砖,小蓝家的地板是 n x m 规格的,小蓝想问你,能否用这些 2 x 3 的地砖铺满地板。
铺满地板: 对于地板的每个区域,都有且只有一块地砖覆盖,地砖可以旋转,但不能切割。
找规律,我们能发现两个数中,如果存在一个可以被6整除,则可以确定可以被实现(需要先排除特殊情况)。
特殊情况
1、maxx % 2 == 0 && minn % 3 == 0 || maxx % 3 == 0 && minn % 2 == 0的情况可以实现。
2、较长的边小于等于2或较短的边小于等于1,不可以实现。
3、如果存在一个可以被6整除,则可以确定可以被实现。
4、其余情况均不可以。
- #include
- #define int long long
- #define MOD 10000
- #define N 1000010
- using namespace std;
-
- void solve()
- {
- int n,m;
- cin >> n >> m;
- int maxx,minn;
- maxx = max(n,m);
- minn = min(n,m);
- if(maxx <= 2 || minn <= 1)
- {
- cout << "No" << endl;
- return;
- }
- if(maxx % 2 == 0 && minn % 3 == 0 || maxx % 3 == 0 && minn % 2 == 0)
- {
- cout << "Yes" << endl;
- return;
- }
- if(maxx % 6 == 0 || minn % 6 == 0)
- {
- cout << "Yes" << endl;
- return;
- }
- cout << "No" << endl;
- }
-
- int32_t main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int _;
- // _ = 1;
- cin >> _;
- while(_--)
- solve();
- return 0;
- }
知识点:差分
假设我们放木板将玩具分开,先求相邻玩具身高差(差分),将身高差前k - 1的大的相邻玩具中间使用木板隔开,放置k - 1个木板,将玩具分为k组,这时各组身高极差之和最小。
- #include
- #define int long long
- #define MOD 10100
- #define N 100100
- using namespace std;
- int n,m;
- int a[N];
- vector
int,int>> b; - vector<int> c;
-
- bool cmp(pair<int,int> aa, pair<int,int> bb)
- {
- return aa.first > bb.first ;
- }
-
- void solve()
- {
- cin >> n >> m;
- for(int i = 0; i < n; i ++) cin >> a[i];
- for(int i = 1; i < n; i ++)
- {
- b.emplace_back(a[i] - a[i - 1],i);
- }
- sort(b.begin(),b.end(),cmp);
- if(n == m)
- {
- cout << 0 << endl;
- return;
- }
- for(int i = 0; i < m - 1; i ++)
- {
- c.push_back(b[i].second);
- }
- sort(c.begin(),c.end());
- int ans = 0,idx = 0,flag = a[0];
- for(int i = 0; i < n; i ++)
- {
- if(idx < m - 1 && c[idx] == i)
- {
- idx ++;
- ans += a[i - 1] - flag;
- flag = a[i];
- }
- }
- ans += a[n - 1] - flag;
- cout << ans<< endl;
- }
-
- int32_t main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int _;
- _ = 1;
- // cin >> _;
- while(_--)
- solve();
- return 0;
- }
知识点:堆优化版dijkstra算法(在我前几天的博客里面有这个知识点…嘿嘿嘿……)
小蓝最近迷上了一款电玩游戏“蓝桥争雷”。这款游戏由很多关卡和副本组成,每一关可以抽象为一个节点,整个游戏的关卡可以抽象为一棵树形图,每一关会有一道算法题,只有当经验值不低于第 i 关的要求 ki 时,小蓝才能挑战成功通过此关,并且获得 si 的经验值,每关的经验值只能获得一次。每个关卡除了 1号点,都会有一个前置关卡,只有通过了前置关卡,才能挑战后续关卡。
小蓝初始在 1号点,也就是游戏开局初始点,同时具有一个初始经验值 P,他可以任意规划挑战顺序,他想问你最多能够挑战成功多少道题。
小蓝会告诉你关卡的所有信息,以及他的初始经验值,你需要回答他最多能够挑战成功多少关卡。
输入
第一行输入两个整数 n P,表示关卡的数量以及小蓝的初始经验值。
接下来n行,每行输入三个整数,fi、si、ki,表示每一关的前置关卡,(f1一定为0);si表示经验值,ki表示挑战成功最少需要的经验值。
输出
输出一个数字,表示在最优的规划下,最多能挑战成功的关卡数量。
我们可以使用邻接表存储这个图,建立一个小根堆,{w,i}i表示关卡,w表示第i关需要多少经验值,priority_queue
我们先将点1存入小根堆,开始循环,小根堆为空时退出循环。
1、将小根堆中w值最小的取出
2、判断这个点能否过关,如果能则进行下一步操作,如果不能则退出循环。
3、将以此关为前置关卡的关卡存入小根堆中(可能没有以此关为前置关卡的关卡),准备开始下一次循环。
- #include
- #define int long long
- #define N 200100
- using namespace std;
- typedef pair<int,int> PII;
- int n,p,ans;
- int e[N],ne[N],h[N],idx;
- int need[N],give[N];
-
-
- void bfs()
- {
- priority_queue
,greater> heap; - heap.push({need[1],1});
- while(!heap.empty())
- {
- PII t = heap.top();
- heap.pop();
- int w = t.first;
- int s = t.second;
- if(p < need[s]) break;
- ans ++;
- p += give[s];
- for(int i = h[s]; i != -1; i = ne[i])
- {
- int j = e[i];
- heap.push({need[j],j});
- }
- }
- }
-
-
- void add(int a,int b,int nee,int giv)
- {
- e[idx] = b,ne[idx] = h[a],h[a] = idx ++,need[b] = nee,give[b] = giv;
- }
-
-
- void solve()
- {
- memset(h,-1,sizeof(h));
- cin >> n >> p;
- for(int i = 1; i <= n; i ++)
- {
- int a,nee,giv;
- cin >> a >> giv >> nee;
- add(a,i,nee,giv);
- }
- bfs();
- cout << ans << endl;
- }
-
- int32_t main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int _;
- _ = 1;
- // cin >> _;
- while(_--)
- solve();
- return 0;
- }