Whowell-CSDN博客

原创 2018 ACM ICPC 全国邀请赛(江苏)赛后感受

一个打铁菜鸟的赛后反思徐州邀请赛结束啦，带着郁闷的心情回到学校，可以说是非常失落，还是自己太菜了，没能给上半年留下一个很好的结尾，都是我的锅，感觉自己罪孽深重的样子，状态也很是不好，最近在调整自己的状态，虽然快考试了，但还是想坚持训练，不能放弃。从今年1月份开始，我们开始准备省赛，一直到现在，...

2018-06-07 22:24:21 2450 1

原创 Mac vscode 配置 c++

Mac vscode 配置 c++1.安装下载安装：下载地址很多文档可以在上面的地址找到，其中可以看到一些预定义变量：Variables Reference2.安装插件：3.创建自己的cpp文件4.command+shift+p打开命令行工具窗口a.配置c_cpp_properties.json文件选择C/Cpp: Edit Configuration...

2019-03-09 14:22:04 5194

原创 Chernobyl’ Eagle on a Roof URAL - 1223[递推dp]

题目：有n个鸡蛋，m层的楼房，假设所有鸡蛋的坚硬程度都是一样的，要做实验确定楼层E，在楼层E扔下一个鸡蛋鸡蛋没碎，在E+1或者更高的楼层扔下一个鸡蛋，鸡蛋就会碎，假设一个鸡蛋没有碎，就会用到下一次实验，求最坏情况下的最少实验次数，就能确定E的；题解：最坏情况下的最小值，表示有个鸡蛋，层楼的最坏情况下的最少实验次数，状态转移方程如下：具体解释：枚举楼层，如果实验鸡蛋碎了，那么就用...

2018-09-29 16:26:41 342

原创 ACM-ICPC 2018 沈阳赛区网络预赛 [菜菜的我！！！]

A. Gudako and Ritsuka [博弈动态规划] 题库链接通过率: 1.55% 通过人数: 2 留坑 B. Call of Ac...

2018-09-13 20:45:42 404

原创牛客网暑期ACM多校训练营（第十场）[题解]

A Rikka with Lowbit题目：有两个操作，一个就是将变为 ,二是求一个区间和的期望；题解：可以看出就是一个区间和就可以啦。代码：#include<bits/stdc++.h>#define ll long long using namespace std;const ll mod = 998244353;const int maxn...

2018-09-13 20:44:57 323

原创计算方法 [课程学习]

计算方法 [课程学习] 201809 有效数字的规格化形式：计算有效数字：误差限，规格化，得到m,则有效数字是小数点后第m位到最左端第一非零数字之间的数字是有效数字，位数是有效数字位数。一元非线性方程求根求非线性方程的近似解，图像如下（找出隔根区间）： ...

2018-09-12 11:27:57 1703

原创 ACM-ICPC 2018 徐州赛区网络预赛

A. Hard to prepare [计数dp] 题库链接通过率: 76.7 % 通过人数: 507题意：有个顾客围成一个...

2018-09-09 18:38:32 460

原创牛客网暑期ACM多校训练营（第三场）E Sort String [字符串 + hash函数 / 字符串 + kmp]

题目：要求将前个字符放到后面字符串的后面形成一个新串,如果，和就放在一组，最后将每一组按照字典序排序，每一组的个数就是这组的一个标号。思路1：将字符串复制一下，那么用字符串hash，只要维护之前有没有出现过就可以啦，但是非常卡时间！！！字符串hash的常见方法：*111111...... unsigned long long 相当于对取模unsigned lon...

2018-09-04 12:53:56 164

原创牛客网暑期ACM多校训练营（第三场）A PACM Team [多维背包]

A PACM Team 题目：有n个物品属性(p,a,c,m,g)，其中g是获得的利润，然后总容量是P,A,C,M，求最大的收益。思路：就是01背包，但是会爆内存，建议用short......没写出来还是对背包理解不行，好好看一下吧代码：#include<bits/stdc++...

2018-08-29 15:57:41 227

原创 “浪潮杯”第九届山东省ACM大学生程序设计竞赛 E - Sequence [最小值次小值滚动]

题目：在一个数列中,假如一个数比在它之前出现的任意一个数大，那么它是一个好数,现在必须删去一个数，使剩余的数好数最多，多个解输出最小值.解题思路：最大最小值记录一下，记录一个数所关联的good数的度，取最小的就可以啦。。。代码：#include<iostream>#include<cstdio>#include<cstring>#incl...

2018-08-29 09:30:45 339

原创 “浪潮杯”第九届山东省ACM大学生程序设计竞赛 A - Anagram[思维+字符串]

题目：给两个字符串A,B通过给定的操作，A->B;感觉水题，瞎搞吧。。。代码：#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define ll long long#define INF 1e9+7;using namespa...

2018-08-28 15:39:39 246

原创 “浪潮杯”第九届山东省ACM大学生程序设计竞赛 B - Bullet[二分 + 最大流匹配]

题目：n*n的方格中可能有monster，Shino只能在一行一列只能杀一个，求尽可能多的杀monster获得经验的最小值最大。题解：每次二分最小值，二分匹配，我习惯用最大流跑。。。具体一点就是说一开始先确定杀得怪物最多有多少个，如果是0个，那么输出0,否则二分最小值，最大流匹配，判断满足杀最多的monster获得经验的最小值最大，最后就得到答案啦。代码：#include<...

2018-08-28 15:07:20 313 1

原创 “浪潮杯”山东省第九届ACM大学生程序设计竞赛 G - Games [dp + 背包优化]

G - Games题意：给定n个数字，求从中拿至多d个数子，异或和为x的方法数。题解：计算方案数，应该想到是计数dp的...... 状态：表示从前个数字中取个数字的异或和为的方案数。状态转移方程：空间复杂度是太大...

2018-08-28 13:35:05 278 6

原创牛客网暑期ACM多校训练营（第三场）H Diff-prime Pairs [素数筛+前缀和]

H Diff-prime Pairs题目：找满足 ,都是prime的(i, j)对。题解：如果，那么，这样就枚举，如果两个素数不相等，那么和一定满足都是素数，这样就是O(n)的复杂度啦。代码：#include<bits/stdc++.h>#define ll long long...

2018-08-26 19:29:06 186

原创 2018中国大学生程序设计竞赛 – 网络选拔赛 1001 Buy and Resell [模拟]

1001 Buy and Resell 题目：有1-n个货物，可以在某个点buy，然后在后面的点resell，可以同时买多个，问最大的利润和最小的交易次数。题解：模拟运算，前 i 天都是可以买的，加入待卖序列(x, 0)，对于第 i 天如果最小的待卖的价格比a[i]小，那么说明可以卖，然后将(a...

2018-08-26 10:55:51 310

原创 2018中国大学生程序设计竞赛 – 网络选拔赛 1003 Dream [费马小定理]

1003 Dream 题目：就是定义乘法和加法满足,输出加法跟乘法，不能都定义为0;题解：首先考虑，再根据费马小定理可知(p是素数);于是只需要将加法与乘法定义为： m + n : m * n : 即可。至于集合相等的那个约束，验证一下可以发现是正确的。...

2018-08-26 09:17:09 215

原创 2018中国大学生程序设计竞赛 – 网络选拔赛 1004 Find Integer [费马大定理]

1004 Find Integer 题目：给定,求满足等式的正整数b，c如果不存在则输出-1 -1。题解：根据费马大定理，n>2是没有整数解，n = 0是也没有正整数解，故n=1,2是枚举一下就可以了。代码：#include<bits/stdc++.h>#define ll l...

2018-08-26 09:06:55 468

原创牛客网暑期ACM多校训练营（第二场）I car [思维题]

I car题意：一个n*n的方格，在边缘放置car，car 只能以相同的速度从一边走到一边，不能相撞，并且不能走有障碍物的一行题解：脑补一下，就是题解中的，如果n是偶数，那么就是保证每行每列只有一个就是2*n，如果是奇数，那么就是需要注意中间那个一行一列只能放一个，否则会相撞，...

2018-08-24 23:22:18 169

原创牛客网暑期ACM多校训练营（第二场）D money [思维题]

D money题意：从1-n一次经过，可以buy或者sell a[i]这样的商品，问交易最少的次数能获得的最大的利润。题解：找最长的1 2 2 3这样的区间，最大利润就是最大的间最小的，这样的交易次数最小。代码：/**2018 nowcoder second D money*...

2018-08-22 18:16:11 218

原创牛客网暑期ACM多校训练营（第二场）A run [简单计数dp]

A run题目：云秒钟可以走1米或者跑k米，但是不能连续两秒钟或者多秒钟跑k米，问走到区间的不同的方案数。思路：简单的计数dp,下面是有关dp的状态以及状态转移方程，状态：dp[i][j]表示第i米是通过走1米还是走k米得到的方案数；状态转移方程： dp[i+1][0] +...

2018-08-22 11:03:34 178

原创 2018 ccpc camp day 1 E. Growth [ 离散化 + dp ]

Problem E. Growth题解：艰难的补题中...题目中m，x，y都很大，但是n只有1000，所以就将x,y离散化（因为递增可以算是跨越式的）；把奖励的x拿出来从小到大排序，得到。把奖励的y拿出来从小到大排序，得到。用表示 a 值到达，b 值达到时接下来每天可以得到的奖励。其中为满足...

2018-08-15 11:36:31 308

原创 2018 ccpc camp day 3 G. Stones [ SG 简单博弈]

G. Stones题目：题意很简单啦，就是两个人分别从n堆石子中拿石子，每次只能拿(a~b)个，不能取的就失败，并且如果一个人取完了一堆就立即获胜；两个条件： 1.从n堆石子轮流取（a~b）个石子，不能取者失败； 2.如果一个人取完一堆就立即获胜；那...

2018-08-06 09:57:49 430 2

原创 2018 Multi-University Training Contest 3 Problem L. Visual Cube

Problem L. Visual Cube 简单的模拟题，输出一个如图的cube;代码：#include <cstdio>int main(){ int n, a, b, c, mx, my, i, j; char x[100][100]; scanf("%d...

2018-07-31 00:33:55 151

原创 2018 Multi-University Training Contest 3 Problem D. Euler Function

Problem D. Euler Function题目：给定k，求第k小的数n，满足是合数(1<=k<=10^9);显然不是合数，只考虑的情况。设 ,则;问什么是上面这个式子，说明一下（欧拉函数有如下性质）：p为质数1. phi(p) = p - 1; 因为质数 p 除了 1 以外的因数...

2018-07-31 00:03:01 158

原创牛客网暑期ACM多校训练营（第一场）E Removal [计数dp]

E Removal 题目：一个数组序列，有n个数，计算删掉m个数字后不相同的序列的个数；思路：计数dp,总之就是动态规划，我们先算不考虑重复的情况就是状态dp[ i ][ j ]：前 i 个数，删除 j 个的方法数；状态转移方程：dp[ i ][ j ] = dp[ i - 1][ j - 1] + dp[ i - 1 ][ j ];//当前位置数字是否删除！考虑重...

2018-07-27 21:19:56 323

原创牛客网暑期ACM多校训练营（第一场）F Sum of Maximum [容斥 + 拉格朗日插值]

F Sum of Maximum 题目：给定一个数组a,求出给定公式的的值；看题目的公式，通过观察发现公式的值与a数组的顺序无关，所以首先将a数组按照从小到大排序；假设 < ，考虑最大值对答案的贡献：对于每个x:1.考虑~的方案数：因为<，当最大值时，~ 可以随便选;所以方案数就是：, 记为.2.考虑~的方案数：因为 ...

2018-07-27 17:26:02 355

原创牛客网暑期ACM多校训练营（第一场）B Symmetric Matrix [数学]

B Symmetric Matrix题目：计算满足题目的n*n的矩阵的数量，题目给出的条件，应该能可以看出是一个对称矩阵，类似一个图邻接矩阵；这样子就应该想成是一个无向图，a[i][1] + a[i][2] + a[i][3] + ...... + a[i][n] = 2；意思就是这个图就是一堆环；...

2018-07-26 20:38:49 350

原创牛客网暑期ACM多校训练营（第一场）D Two Graphs [模拟]

题目：要求计算与Ａ同构的Ｂ的子图的个数；思路：将Ａ图全排列映射到Ｂ图中，判断是否同构，每个Ｂ与Ａ同构的子图，都计算了Ａ的“自同构”次，去重得到答案；解释一下为什么会多算看下面这张图：　　　考虑G1边互换两个节点，也可以构成同构，在G2中每一种方案也可以通过互换顺序，得到另一种同构，但其本质是相同的，所以找出G1中自同构的数量，每个满足题意的方案被计算了“自同构”次，...

2018-07-24 20:48:47 174

原创背包问题学习总结

一、01背包问题题目：有件物品和一个容量为的背包。放入第件物品耗费的费用是，得到的价值是。求解将哪些物品装入背包可使价值总和最大。存在两种状态：第一种是第i件不放进去，这时所得价值为: 第二种是第i件放进去，这时所得价值为：最基础的背包问题，特点是：每种物品仅有一件，可以选择放或...

2018-07-24 10:33:41 1090

原创牛客网暑期ACM多校训练营（第一场）A Monotonic Matrix [Lindström–Gessel–Viennot lemma]

A Monotonic Matrix学习一下Lindström–Gessel–Viennot lemma，有一个没听说过的数学，这数学场是要慢慢学习；一种计算非交叉格子路径数的方法:主要公式就是对于一张无边权的DAG图，给定n个起点和对应的n个终点，这n条不相交路径的方案数为：题目：在所有的n...

2018-07-23 22:23:42 130

原创 ubuntu 16.04 系统　解压zip文件文件名乱码

转载自：https://blog.csdn.net/u012005313/article/details/50998470 －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－我使用的系统是ubuntu 16.04 在系统下，解压zip文件，之后文件名就是乱码，就很无奈；解决办法：安装软件：sudo apt-get install u...

2018-07-21 09:39:09 2447

原创牛客网暑期ACM多校训练营（第一场）J-Different Integers [树状数组/莫队]

J-Different Integers题意很清楚啦，就是找两边区间不同数字的个数，还是自己菜啦，我一眼瞅上去感觉是莫队，主要原因是我昨天刚刚学习了qsc的莫队算法视频，以为只有查询操作，没有修改操作，用莫队就好啦，没想到T到怀疑人生，最后可能是服务器的问题吧，我莫队调整了常数，卡过去啦，不管咋说，还是要...

2018-07-20 11:23:44 217

原创 Educational Codeforces Round 47 B Minimum Ternary String[字符串]

B. Minimum Ternary Stringtime limit per test:1 secondmemory limit per test:256 megabytesinput:standard inputoutput:standard output You are given a ternary string (it is a string which cons...

2018-07-19 09:35:07 152

原创数论 [高斯消元学习]

高斯消元法，是线性代数中的一个算法，可用来求解线性方程组，并可以求出矩阵的秩，以及求出可逆方阵的逆矩阵。初等行变换：（1）对调两行；（2）以k != 0乘某一行的所有元素；（3）把某一行所有元素的k倍分别加到另一行对应的元素上去；高斯消元法的...

2018-07-18 21:11:57 166

原创数论继续学习16---母函数（又名生成函数）

数论继续学习16---母函数（又名生成函数）前言：母函数是个很难的东西，难在数学而ACM中所用的母函数只是母函数的基础应该说除了不好理解外，其他都是非常简单的母函数即生成函数，是组合数学中尤其是计数方面的一个重要理论和工具。但是ACM中的母函数木有像数学那么深究，应用的都是母函数的一些基本（就好比方程的配方，因式的分解，写起来容易，你用电脑写起来就麻烦了，所...

2018-07-18 16:19:00 510 2

原创 Codeforces 340 E. XOR and Favorite Number [莫队算法]

E. XOR and Favorite Numbertime limit per test：4 secondsmemory limit per test：256 megabytesinput：standard inputoutput：standard outputBob has a favorite number k and ai of length n. Now he ask...

2018-07-18 14:49:15 230

原创 U盘格式化以后容量突然减少 [已解决]

今天把U盘格式化了，突然 4G U盘突然变成了120k，奇怪！！！其实U盘并没有坏掉，具体原因我也不清楚，下面解决一下！首先打开cmd，输入Diskpart 之后输入list disk 如图：显然，我的U盘显示的容量是正确的，那么下面我们就能够找回来了，选择你的U盘，我的是2，所以选择2：select disk 2输入clean(报错就在来一次)：...

2018-06-13 11:21:16 21214 4

原创 Codeforces Round #487 (Div. 2) B. A Tide of Riverscape [贪心]

B. A Tide of Riverscapetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe records are expressed as a string ss of characters '0', '1' and '.', whe...

2018-06-12 20:08:53 143

原创 Codeforces Round #487 (Div. 2) A. A Blend of Springtime [思维题]

A. A Blend of Springtimetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputWhen the curtains are opened, a canvas unfolds outside. Kanno marvels at al...

2018-06-12 20:00:09 170

原创 Codeforces Round #487 (Div. 2) C. A Mist of Florescence [思维+构造矩阵]

C. A Mist of Florescencetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputAs the boat drifts down the river, a wood full of blossoms shows up on the ...

2018-06-12 19:50:14 153

空空如也

空空如也