思路：首先用枚举第一行的按开关情况，一共有32种情况（00000-11111），分别计算出这些情况按开关后亮灭情况再通过改变第二行的将第一行的灯全亮，以此类推通过改变第三行使第二行全亮，改变第四行使第三行全亮，改变第五行使第四行全亮。最后更新最小按灯数。 由于只有25个灯，int的有效范围是32位，故我们可以用int中的25位表示灯的情况。为了表示方便我们将第一行第一个用0位表示，如下所示为五行灯对应int中的位数0 1 2 3 45 6 7 8 910 11 12 13 1415 16 17 18 1920 21 22 23 24 为了满足上述对应，我们应该从后往前逐步更新便可以得到...

先附上本题思路来源 https://blog.csdn.net/gettogetto/article/details/69389810 有点类似与并查集举个例子1 4 2 34 2 3会形成一个循环节，对于这种循环节来说，最少需要循环节内元素个数-1次交换 故代码如下 #include<bits/stdc++.h> using namespace std; struct Node{ int val; int def; friend bool operator <(Node& a,Node& b){ return a.va...

思路：先将货币面值从小到大排序，再依次判断小货币能否组成大货币，如果可以则可以删除该种大货币。 #include<bits/stdc++.h> using namespace std; int a[100086]; int vis[250086]; int main() { int n,t; cin>>t; while(t--) { cin>>n; int ans=n; memset(vis,1,sizeof(vis)); for(int i=0;i<n;i...

(a[i] - a[x]) * (a[i] - a[x]) = a[i] * a[i] - 2 * a[i]* a[x] + a[x] * a[x]所以里面一共就有(n - 1)个a[i]的平方，中间这部分减法就是2 * (sum - a[i]) * a[i], sum即是所有数字的和。然后举个简单例子就能发现最后的答案为n倍的平方和-和的平方a b c(a-b)(a-b)+(a-c)(a-c)+(b-c)(b-c)2aa+2bb+2cc-(ab+ac)-(ab+bc)-(ac+bc)=2aa+2bb+2cc-(sum-a)a-(sum-b)b-(sum-c)c=2aa+2bb+2cc-(a+...

来记录下解题思路：坑点：long long型数据取模会TL这题主要是用了数位dp的模板，主要的难点在于，枚举出这个数字所有数位的和的可能情况。 #include<bits/stdc++.h> using namespace std; int T; long long ans; int dp[17][120][120];//dp[pos][pre][ans] pre代表前面数字各个数位的和，ans代表目前的结果 int a[20]; int len; long long dfs(int pos,int pre,int limit,int cnt,int mod)//long long...

我们知道这扇门的一部分一定是在原点，另外一部分是在某一边，所以倘若0两测都有人的话，我们必定只要能减少某一遍到达原点的最长时间，因为不可能另外一边的都走到原点了还接着走过去找那边门。那么我们如何判定门是建立在哪一边的呢，我们只要确定哪一边绝对值更大，就建立在哪一边。确立了建立在哪一测后，我们只要逐个枚举这一侧元素到0 a1 a2 a3当考虑在a2,a3之间时候，最大时间为max(a3-mid,max(x[i-1],mid-x[i])) #include<bits/stdc++.h> using namespace std; int a[100100]; int main() {...

这道题感觉是枚举加一些优化在里面。还是以例子为例吧。dp[i]=1表示某种组合加起来除以3600的余数为i，一开始的时候dp[]数组全为0；当某个组合是3600的倍数的时候，dp[0]=1,这便是说明可以组合形成3600的倍数，便可以输出YES，否则输出NO。假如：2000 1000 3000一开始2000加入的时候，2000%3600=2000，便标记dp[2000]为1下次加入1000的时候遍历dp数组一遍，会发现dp[1600]为1，便在这个基础上加上a[i]再对3600取模（这里因为只要1600被标记了故v中只加入了（1000+1600）%3600=1000），结果存储在v数组中，最后...

这题思路就是：讲最场的歌曲在最后一分钟播放，剩下n-1首歌曲在t-1时间内求最大值以例子演示一下：注意这里最大时长已经被预订最后一分钟播放 1 2 3 4 5 6 0 0 0 0 0 0 先加入时长为2的歌曲变为 0 2 2 2 2 2 加入时长为3的歌曲 0 2 3 3 5 5 最后返回的结果为dp[6]+a[n]即9 #include<bits/stdc++.h> using namespace std; int a[205],n,t; int dp[80005]; int main() { ...

首先我们来看看观察每个区间的值就以题目中的示例为例子解释一下 对应区间段1-5由于可加的物品的重量必须大于等于W（4）故在1-5中只有4，5两个可加贡献为 25+25=20；2是因为有两个数符号条件 在2-4中，只有4一个可加贡献为1*5=5； 3-3中，没有可以加的贡献0故这样当w取4时候，贡献一共为25 这样我们可以看出这道题主要是求出某个区域的的值，这样我们便采用前缀和我们可以采用一个sum数组来记录从前缀和，sum[i]表示从1到i之间所有有效数字的和如果我们要求l,r之间的有效值，则可以用sum[r]-sum[i-1];同理采用cnt数组来记录某个区间段有效物品的个数，cn...

这道题如果要解出来的话，除了要想到二分，更要想到枚举区间段为1的各部分，然后再注意注意细节就差不多了。 #include<bits/stdc++.h> using namespace std; double a,b,c,d; int ans=0; inline double f(double x)//定义好求值的函数 { return a*x*x*x+b*x*x+c*x+d; } int main() { scanf("%lf %lf %lf %lf",&a,&b,&c,&d); for(double i=-100;i<...

这道题应该大家跟我在做的时候都想到了要使这两者数量最接近，所以要使较小的那个不断扩大两倍直到他们两数量最接近（不能超过），然后想到这一点后我就陷入了泥潭，一直在思考怎么确定再次倍增的条件呢，然后就。。。。卡这卡死了，后面补题的时候看了大佬的代码发现，其实根本不用想的这么复杂，当我们使他们两最接近的时候，就可以采取第一种方法，两个各减1，然后再次判断是否可以倍增，直到最后为0。 #include<bits/stdc++.h> using namespace std; int main() { int m,n,T,ans=0; cin>>T; whi...

拖了很久今天终于下定决心来解决这道题了，这么经典的题目居然没有人写题解，本小白就来水一发（大佬勿喷），希望能对大家有点帮助，主要讲下思想和两种方法的实现，感觉难点问题官方题解已经讲的很清楚了。归并排序解法：首先我们来看下为什么归并排序可以计算逆序对对数量：比如一个数列为 5 4 1 2 3首先在归并排序将数列分为两部分 5 4 1 和 2 3左边 5 4 1再次分成两部分 5 4 和 1然后5 4再被分为两部分，5和4接着便开始逐步合并（重点来了）：在合并的时候，由于5 排在 4前面，由于是从小到打排序，必然要先放置4，再放置5，这个时候我们便可以将逆序对+1了，该部分合并完成后变为 4 ...

从题目中我们可以知道有四个变量得考虑——目前所在字符串中的位置，剩余的操作步数，目前乌龟所在位置及乌龟行进方向，故我们可以想到（看大佬的）开个四维数组进行dfs遍历所有情况。下面我们来看代码#include<bits/stdc++.h> using namespace std; string h; int n; int length; bool dp[105][55][205][2]; int ans=0; void dfs(int def,int n,int pos,int way) { if(def==length)//当走到字符串最末尾的时候 { if((...

这道题一开始自己没想到用动态规划去做，后面看了下大佬们的解法，才发现原来还可以动态规划去做。首先讲下我这种解法吧：1.这是概率论中一道典型的配对模型所谓配对模型就是，比如n个人任取n顶不同的帽子，n把钥匙随机开n把锁，求至少有一对配对成功的几率。对应这种配对问题，存在着一个公式，全部配对错误的可能性为：1/2!-1/3!-...+(-1)^(n-1)*1/n!利用这个公式我们便可以对问题进行求解 #include<bits/stdc++.h> using namespace std; void Help(int n) { double a=1; double b=2...