Acwing

题目描述 给你一个 \(n\) 个点 \(n\) 条边的有向图，若选了当前节点，那么当前节点的儿子节点至少有一个不能选。求最多能选多少个点。 具体思路 显然是一棵基环树，因此考虑基环树 dp。 我们先不管环的条件，先考虑朴素的树形 dp。 设 \(f_{x,0}\) 表示 \(x\) 节点不选，最多 ......

这个题目就当一个见识吧 设f[i][j][k]表示当前的状态是[i,j]并且j后面还有k个与j颜色相同的木块的最大价值 第一种情况，当第j块和第j-1块颜色相同时，f[i][j][k]=f[i][j-1][k+1] 第二种情况，当第j块和第j-1块颜色不同时，考虑最后那一堆颜色相同的怎么消去的 如果 ......

题目描述 给你一棵树，让你判断树上每个节点是否在树的直径上。 树的直径：树上最远的两个点之间的距离。 树的直径可能不止一条。 具体思路 对于树的直径，我们有三种求法。 树形dp 设 \(d_x\) 表示 \(x\) 往下走能够到达最远距离，\(f_x\) 表示经过 \(x\) 的最长链的长度。 那么 ......

\(AcWing\) \(126\). 最大的和 关键字 最大子段和，有一维和二维两种情况 一维：\(O(N)\) 二维：\(O(n^3)\) 一、题目描述 给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为 \(1×1\) 或更大的连续子阵列。 矩形的总和是该矩形中所有元素的总和。 在 ......

Acwing.第123场周赛 比赛链接 回家休息了五天调整好状态继续出发！！！！ A.队列 一共有三个队列，当前分别已有 a,b,c个人。 现在有 n个人尚未进队，每个人都需要被安排到一个队列当中。 为了队形整齐，我们希望所有人被安排进队后，三个队列包含的人数均相等。 请你判断，是否可能做到。 输入 ......

一、题目描述 给定你一个长度为 n 的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行，第一行包含整数 n。 第二行包含 n 个整数（所有整数均在 \(1∼10^9\) 范围内），表示整个数列。 输出格式 输出共一行，包含 n 个整数， ......

\(AcWing\) \(431\). 守望者的逃离 一、题目描述 恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。 守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。 为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。 到那时，岛上的所有人都会遇难 ......

\(AcWing\) \(414\). 数字游戏 一、题目描述 丁丁最近沉迷于一个数字游戏之中。 这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。 游戏是这样的，在你面前有一圈整数（一共 \(n\) 个），你要按顺序将其分为 \(m\) 个部分，各部分 ......

\(AcWing\) \(463\). 求和 一、题目描述 一条狭长的纸带被均匀划分出了 \(n\) 个格子，格子编号从 \(1\) 到 \(n\)。 每个格子上都染了一种颜色 \(color_i\)（用 \([1，m]\) 当中的一个整数表示），并且写了一个数字 \(number_i\)。 定义一 ......

第九十八场周赛. AcWing 4949. 末尾连续0 给定一个正整数 \(m\)，请你统计一共有多少个正整数 \(n\) 满足，\(n\) 的阶乘的末尾连续 \(0\) 的数量恰好为 \(m\)。 输出满足条件的 \(n\) 的数量以及所有满足条件的 \(n\)。 例如，当 \(m=1\) 时，满 ......

第九十八场周赛. AcWing 4948. 大乘积 我们规定，如果一个非负整数 \(a\) 满足以下两个条件之一，则称 \(a\) 为美丽数： \(a=0\) \(a=10^x\)，其中 \(x\) 为任意非负整数。 给定 \(n\)个非负整数 \(a_1,a_2,…,a_n\)，这其中有至少 \( ......

Acw 5046 思路 dp，\(dp_i\) 表示前i种药且吃第i种药使智商达到\(r_i\)的方案，根据题意可知 \[dp_i = \sum dp_j,(r_j\in [l_i,r_i-1]) \]先将各区间按右端点排序， 求j的区间可用二分. 代码 //9.24 int n,m,k; int ......

比赛链接 A简单输出 题目链接 简单的模拟一下就好了，注意是多组样例就行。 #include<bits/stdc++.h> using namespace std; void solve(){ int n; cin>>n; for(int i=1;i<=n;i++){ cout<<i<<" "; } ......

原题 考虑朴素\(dp\)，设\(dp_i\)表示前\(i\)个数划分后的最小答案 可以得到转移： \[dp_i = \min_{j=1}^{i-1}\{dp_j + \max_{k=j+1}^{i}\{a_k \} \} \]计算复杂度\(O(n^2)\)，会超时 我们发现对于可能成为答案的状态是 ......

参考文献 简单的容斥原理介绍请看下图： C++ 代码 简单的容斥原理介绍请看下图： 本题思路： 将题目所给出的m个数可以看成是m位的二进制数，例如 当p[N]={2,3}时，此时会有01,10,11三种情况 而二进制的第零位表示的是p[0]上面的数字2,第1位表示p[1]上面的数字3 所以当i=1时 ......

AcWing.5151.程序调用 有 \(n\) 个程序，编号 \(1∼n\)。 初始时，这 \(n\) 个程序都在一个调用队列当中，位于队列第 \(i\) 位的是编号为 \(a_i\) 的程序。 每个程序都有一个调用级别，根据程序在队列中的排位，排在第 \(1∼k\) 位的程序属于 \(1\) 级 ......

AcWing.5149.简单计算 约翰的农场有\(n\)头奶牛，编号 \(1∼n\)。 为了决出谁才是牛中强者，它们之间决定来一场顶牛大赛。 已知，每两头奶牛之间都会有一场一对一对决，对决可能产生以下几种结果：没有牛被顶翻、一头牛被顶翻、两头牛都被顶翻。 所有对决的结果已经用一个 \(n×n\) 的 ......

AcWing.5149.简单计算 给定三个整数 \(x,y,z\),请你计算并输出 \(⌊(z-y)/x⌋*x+y\) 的值。注意，⌊ ⌋ 表示向下取整。 输入格式 第一行包含整数 T，表示共有 T组测试数据。 每组数据占一行，包含三个整数 \(x,y,z\)。 输出格式 每组数据输出一行结果。 数 ......

原题 首先\(conn(conn(s_2,n_2),m) = conn(s_2,n_2 \times m)\)，因此我们可以找一个最大的\(m'\)满足\(conn(s_2, m')\)能由\(conn(s_1, n1)\)生成，然后再通过\(m = \lfloor \frac{m'}{n_2} \ ......

题目链接：https://www.acwing.com/problem/content/description/395/ 解题思路： 差分约束。 为了方便起见，定义第 \(i\) 个时间段为 \(i-1:00\) 到 \(i:00\) 这个时间段。 首先，为了方便开一个额外的点，令 \(R_i\) ......

Acw 5220 题意 自己看 思路 假设串N长度为\(n\)，串H长度为\(m\)，遍历串H，对于\([i,i+n-1]\)这一段子串，如果所含字母个数与串N所含字母个数相同，则认为匹配，问题在于 如何判断 排列重合 的问题。字符串哈希。匹配的话直接将这一段的哈希值放入set中，去重，最后set的 ......

Acwing.第121场周赛 比赛链接 这次怎么出的这么简单，偷懒了是吧哈哈哈 A. 简单计算 题目链接 #include<bits/stdc++.h> using namespace std; typedef long long ll; void solve(){ int a,b,c; cin>> ......

AcWing 第94场周赛 4870. 装物品 - AcWing题库 4870 装物品 4870. 装物品 - AcWing题库 巨简单题 #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; if ( ......

这一道题就是显然的multi-SG题目了（只是没有明显的后继节点，只能分解节点罢了） 这里无论双方怎么决策，决策图都不可能出现1x某某的网格（原因见蓝书），所以我们在程序中就不要考虑SG[1][某某] 最后的不能分解的节点就是2x2,2x3,3x3（注意不要涉及1x某某哦），我们把这三个节点赋成0即 ......

AcWing 第120场周赛 竞赛 - AcWing 5146 最大GCD 5146. 最大GCD - AcWing题库 不难发现，最大公约数的条件是 \(GCD(\lfloor \frac{n}{2} \rfloor ,\lfloor \frac{n}{2} \rfloor * 2)\) #inc ......

AcWing 第97场周赛 4944. 热身计算 - AcWing题库 4944 热身计算 4944. 热身计算 - AcWing题库 #include <bits/stdc++.h> using namespace std; int a, b; int main() { cin >> a >> b ......

AcWing 第85场周赛 竞赛 - AcWing 4791 死或生 4791. 死或生 - AcWing题库 简单题 #include <bits/stdc++.h> using namespace std; int a[3][2]; int n; int main() { cin >> n; w ......

AcWing 第5场周赛 竞赛 - AcWing 3726 调整数组 3726. 调整数组 - AcWing题库 简单题，判断奇偶数是否同时存在 #include <bits/stdc++.h> using namespace std; int t, m; int main() { cin >> t ......

题意描述： 给定一块n*m的区域，用1*2的长方形填充，长方形可以横着或竖着摆，问一共有多少种填充方案 具体思路： 题意没什么好说的，简单易懂，很经典的一类状态压缩问题（在棋盘中求填充方案）。 观察数据，满足n，m都比较小，但是搜索的复杂度大到无法接受，考虑使用状态压缩求解此类问题 首先，肯定是第一 ......

Acwing.第 120 场周赛 比赛链接 A最大GCD 给定一个正整数 n（n≥2），请你确定两个正整数 a,b，使得 1≤a<b≤n，且 gcd(a,b)尽可能大。 输出 gcd(a,b)的最大可能值。 gcd(a,b)指 a,b的最大公约数。 提示：可以通过给定样例观察一下 n和答案之间的关系 ......