第七场专题
多校第七场 DP+map模拟
HDU 4939 Stupid Tower Defense DP 推一下。 #include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include<queue>#include<stack>#include<vector>#include<ctype.h>#inclu
【Nowcoder】2021牛客暑假集训营（第七场): xay loves trees 双指针 + 线段树 + 尺取
传送门 题意 给你两个树，求一个最大集合，要求集合内的任意两个点在第一个树上，比如是祖先关系，在第二棵树，不能存在祖先关系 分析 某人吐槽我的题解写的太简单了，然后我觉得。。。承认错误死不悔改 这道题如果分开来求的话，一个是求树的直径，一个是树上DP，都比较简单，如果当他们在一起应该怎么处理呢，我们考虑维护两个指针，因为在树上两点之间的路径肯定是维护，所以肯定是符合第一个条件的，这样我们就
2019牛客暑期多校训练营（第七场）I Chessboard —— 组合，n个球放入m个盒子的情况数
This way 题意： 你可以选择k*k的矩形，每个格子中填的数要大于等于m，并且要保证（所有不同行不同列的数之和）的所有情况相同。 题解： 不会，，按照它的题解做吧，我这里就翻译一下将一些细节说的明白一点 首先，这里是设一个函数，那么为什么 因为每个格子至少要放m个，那么不同行不同列的个数是k，所以变成了T-k*m 那么对于要满足“不同行不同列的数之和”全相等这个条件，对于任意一行
2019牛客暑期多校训练营（第七场）F Energy stones —— set+树状数组求随时间增长的区间和问题
This way 题意： 有n个石头，这些石头一开始有一些能量e[i]，并且每过一个单位的时间会增长l[i]，直到有c[i]的能量为止。现在有q个询问 t l r表示在t时刻的时候收割l-r的所有能量，并且将其能量置为0，然后这些石头的能量重新增长。问你最后你收割了多少能量 题解： for一遍所有的石头，用一个set维护在这个时候有哪些收割的时刻。 每个石头有两种状态：未达到c[i]和已达
牛客多校第七场 C Bit Compression
题目：点击打开链接 题意：一个长度为n的01字符串，第i个和第i+1个经过^或者|或者&运算后合并，问最终01串变成1的方法有多少种。 分析：直接暴力用stl模拟，或者dfs+剪枝，减掉全为0的情况，时间和空间复杂度都有点玄学。或者使用预处理，暴力的复杂度是3^n的，只需要再优化一点点！ 如果剩下了16个变量，可能性只有65536个。 预处理他们，得到一个3^(n-4)的做法。 暴力代码：
牛客网暑期ACM多校训练营（第七场） - J - Sudoku Subrectangles
题目：点击打开链接 题意：已知一个n*m充满字符的矩阵，求出有多少个子矩阵，其每一行每一列都没有相同的字母（不同行不同列的位置字母可以相同） 分析：枚举以每一个点作为子矩阵的左上角，求出有多少个，然后最后求和即为答案。预处理每一个点向下想右最大的延伸长度。显然，无论是往右还是往下这样的一段，长度都不会超过52。复杂度为O(52*n*m)。有很多细节需要注意，最好画个草图。 代码： #pr
【蓝桥·算法双周赛】第七场分级赛——小白入门赛
2.霓虹【算法赛】 - 蓝桥云课 (lanqiao.cn) st数组用来存第i个位置，这个字母有没有编号j #include<bits/stdc++.h>const int N=1e6+10;using ll=long long;std::map<std::string,std::string> mp;std::string a,aa;int st[N][10];//int st
「蓝桥·算法双周赛」第七场分级赛——小白入门赛
题目列表 说明 好久没打蓝桥杯的比赛，回来试试水，就开了第1、2、3一共三个题，第4题可惜了。 1.thanks,mom【算法赛】 思路： 没什么好说的，但是当时比赛刚开始服务器有问题，基本提交的全WA了。 #include <bits/stdc++.h>#define endl '\n'#define int long longusing namespace s
upc2018年第三阶段个人训练赛第七场C题
问题 C: Restoring Road Network http://exam.upc.edu.cn/problem.php?cid=1392&pid=2 时间限制: 1 Sec 内存限制: 128 MB 提交: 896 解决: 184 [提交] [状态] [讨论版] [命题人:admin] 题目描述 In Takahashi Kingdom, which once existed,
8.10 第七场 Fall with Trees
8.10 第七场 Fall with Trees Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 2600 Accepted Submission(s): 618 Problem Description Fall wants to d
B.Mask Allocation (gcd 规律) 2020牛客暑期多校训练营（第七场）
传送门 思路： 题意：将n*m个口罩分装到经量少的盒子，使得既能均分成n份又能均分成m份。设m <= n，则前m个答案必定为m个m，大了分不了，小了又非最优，再继续考虑后n - m个和m个。还发现了 dfs做法 和 gcd的辗转相除思路。 代码实现： #include<bits/stdc++.h>#define endl '\n'#define null NULL#define
H. Dividing 2020牛客暑期多校训练营（第七场）
传送门 思路： 题意：定义传奇元组： (1,k)始终是传奇元组。如果(n,k)是传奇元组，(n+k,k)与(nk,k)也是传奇元组。 我们想知道1≤n≤N,1≤k≤K时传奇元组(n,k)的数目。 官方题解： 如果n是k的倍数，即n=xk，那么可以减掉(x-1)个k，将n变为k，再/k为1。而如果n-1是k的倍数，即n=xk+1，那么x次除k就行。 详细可参考大佬题解。 代码实
D. Fake News (思维 / 特判) 2020牛客暑期多校训练营（第七场）
传送门 思路： 题意：判断1到n的平方和是否是一个可开平方的数，若是输出 “Fake news!”，不然输出 “Nobody knows it better than me!”.因为1到n的平方和有公式 n*(n+1)*(2n+1)/6 ，刚开始一直讨论觉得可能需要统计下质因数的个数书否都为偶数。后面一气之下就特判了下 1 和 24 两组数据竟然过了！！！ 代码实现： #includ
Sequence（矩阵快速幂变形）2018多校第七场
题意一目了然，中间会改变的矩阵快速幂。 很显然，我并没有做过这种题，只做过中间不会改变的矩阵快速幂。 于是看题解发现我可以在矩阵中多加一个维度来储存每次加上的一个数，开一个三维矩阵。 | d c [p/i] | | f(n-1) | | 1 0 0 | * | f(n-2) | | 0 0 1 | | 1 |