Neo__Z-CSDN博客

原创 pytorch 实现 Style Transfer

pytorch 实现 Style Transfer设CNN中第lll 层风格图片、内容图片、生成图片的feature map分别为SlS^lSl、ClC^lCl、GlG^lGl。第lll层内容损失函数定义为 LCl=∑ij(Cijl−Gijl)2L_C^l=\sum\limits_{ij}(C^l_{ij}-G^l_{ij})^2LCl=ij∑(Cijl−Gijl)2对于 featu...

2020-02-10 10:22:15 756 2

原创 MNIST用matplotlib实现可视化

import osos.environ['TF_CPP_MIN_LOG_LEVEL']='2'import tensorflow as tfimport matplotlib.pyplot as pltimport numpy as npfrom tensorflow.examples.tutorials.mnist import input_datamnist = input_da...

2019-10-29 23:04:29 1118

原创 Tensorflow多层感知机实现MNIST分类

import osos.environ['TF_CPP_MIN_LOG_LEVEL']='2'import tensorflow as tfimport tensorflow.contrib.layers as layersfrom tensorflow.examples.tutorials.mnist import input_datamnist = input_data.read_...

2019-10-29 21:39:18 566

原创 TensorFlow常用激活函数

thresholdimport osos.environ['TF_CPP_MIN_LOG_LEVEL']='2'import tensorflow as tfimport numpy as npimport matplotlib.pyplot as plt def threshold(x): cond = tf.less(x, tf.zeros(x.shape, dtype=...

2019-10-29 16:09:52 277

原创 Tensorflow 逻辑回归处理mnist数据集

import osos.environ['TF_CPP_MIN_LOG_LEVEL']='2'import tensorflow as tffrom tensorflow.examples.tutorials.mnist import input_data mnist = input_data.read_data_sets('./data/mnist_data/', one_hot=...

2019-10-29 15:28:26 244

原创 Tensorflow 实现线性回归

import osos.environ['TF_CPP_MIN_LOG_LEVEL']='2'import tensorflow as tf import numpy as npimport matplotlib.pyplot as pltdef normalize(X): mean = np.mean(X) std = np.std(X) X = (X-mea...

2019-10-29 13:05:13 152

原创 loj#2331. 「清华集训 2017」某位歌姬的故事【动态规划】

传送门解题思路：将序列离散化后，可以给每个点确定一个取值的上界，那么每一种上届的贡献是独立的，分别求出再相乘即可。对于一种上界 www，把对应的点和限制提出，那么对于每个右端点，唯一有用的限制就是左端点最靠右的，记为L[i]L[i]L[i]，再设 f[i][j]f[i][j]f[i][j] 表示到第 iii 个点，最后一个 www 在 jjj 的方案数转移即可。#include...

2018-05-31 15:38:40 1249

原创 loj#2326. 「清华集训 2017」简单数据结构【动态规划+set】

传送门解题思路：感觉复杂度是证不来的……不过跑得挺快…… 注意序列长度不超过20，所以也比较暴力，就是记录每个值的位置，以每个点开头的最长长度和每个长度对应的最小结尾位置，用set维护以每个点为结尾的最长序列开头位置，用桶维护答案……向左加就枚举倍数更新，向右加就枚举约数更新……#include&lt;bits/stdc++.h&gt;using namespace std;in...

2018-05-31 11:27:46 862

原创 loj#2322. 「清华集训 2017」Hello world!【分块+并查集+树状数组】

传送门解题思路：考虑对步数分块，对于步数大于S的直接暴力修改查询，步数小于S的建S棵树，第i棵树x先第i个祖先连边，用并查集维护连续是1的一段，树状数组维护查询。这样修改是O(Slogn)O(Slogn)O(Slogn)的，查询是O(logn)O(logn)O(logn)，不知有没有更优秀的复杂度。#include<iostream>#include<alg...

2018-05-31 08:59:22 960

原创 loj#2542. 「PKUWC 2018」随机游走

传送门解题思路：Min-Max容斥真神奇……然而不知如何证明……设 Max(s)Max(s)Max(s) 表示集合里最晚被访问的节点被访问的期望步数（也就是访问所有节点的期望步数）。设 Min(s)Min(s)Min(s) 表示集合里最早被访问的节点被访问的期望步数（也就是第一次访问到集合里的节点的期望步数）那么 Max(s)=∑T∈S(−1)|T|+1Min(T)Ma...

2018-05-29 17:08:37 766

原创 loj#2541. 「PKUWC 2018」猎人杀【容斥+概率dp+生成函数+分治FFT】

传送门解题思路：思路巧妙……原题中每轮概率都在变化，一脸不可做，但注意到对问题的转化：我们杀人后将其打上标记，但还是可以以他为目标重复选，直到选到一个未打标记的人。这和原问题等价，而且这样每轮选中每人的概率都不变。考虑容斥，枚举强制在1号后面死的人，即1号至少在这些人前面，令 A=∑wiA=∑wiA=\sum w_i，SSS 为枚举到的人的 wiwiw_i 之和，ttt 为...

2018-05-29 15:14:59 1720

原创 loj#2540. 「PKUWC 2018」随机算法【概率dp+状压dp】

传送门解题思路：朴素的dp是O(n3n)O(n3n)O(n3^n)，即每个点有三种状态：没考虑过，考虑了且在独立集中，考虑了但没在独立集中，需要优化。设 f[i][s]f[i][s]f[i][s] 表示考虑前 iii 个点，独立集为 sss 的方案数，主要的问题就在于对于一个当前轮不能加入独立集的点，是否在之前就被考虑过，但注意到考虑了但没在独立集中的点数我们是知道的，即i−bin[s...

2018-05-29 10:23:43 521

原创 loj#2538. 「PKUWC 2018」Slay the Spire【期望dp】

传送门解题思路：做这道题时一定要静下心来思考，不能慌……假设摸到 iii 张强化牌，m−im−im-i张攻击牌。首先发现强化牌数值都大于1，所以有一个显然的结论，强化牌能用就用，即： i<ki<kiiii 张强化牌，k−ik−ik-i 张最大的攻击牌； i≥ki≥ki\ge k，用 k−1k−1k-1 张强化牌和最大的攻击牌；那么先把牌从大到小排，fi,jfi,...

2018-05-29 09:30:26 853

原创 loj#2537. 「PKUWC 2018」Minimax【概率dp+线段树合并】

传送门解题思路：感觉自己当时好菜啊……设 fu,ifu,if_{u,i} 为 uuu 选 iii 的概率，假如是从左子树转移来的，则fu,i=fl,i(p∑fr,j<i+(1−p)∑fr,j>i)fu,i=fl,i(p∑fr,j<i+(1−p)∑fr,j>i)f_{u,i}=f_{l,i}(p\sum f_{r,ji}) 然后想到线段树合并，节点表示选当前区...

2018-05-29 07:53:38 1036

原创 loj#2330. 「清华集训 2017」榕树之心【树形dp】

传送门解题思路：先考虑根是否可行，即步数是否能抵消完。考虑w[x]w[x]w[x]表示xxx的子树内最少的消剩下的点数。观察发现，最难消的肯定是sizesizesize最大的儿子，设为 yyy ，而且如果 yyy 能被消完，即others=size[x]−1−size[y]>=w[y]others=size[x]−1−size[y]>=w[y]others=size[x...

2018-05-25 19:33:02 569

原创 bzoj5330: [Sdoi2018]反回文串【莫比乌斯反演+Miller-Robin】

Description“回文串什么的最讨厌了……” 小Q讨厌任何形式的回文串：（1）如果一个字符串从左往右读和从右往左读是一样的，那么小Q讨厌它；例如aa和aba （2）对于一个字符串来说，若将某个前缀子串移除并拼接到字符串的尾部，能得到一个小Q讨厌的字符串，那么小Q也会讨厌原来的这个字符串；例如aab和baa。现在问题来了，如果任意字符串只可以由k种已知的字符组成（也就是说字...

2018-05-25 18:49:32 529

原创 bzoj5329: [Sdoi2018]战略游戏【圆方树+虚树】

Description省选临近，放飞自我的小Q无心刷题，于是怂恿小C和他一起颓废，玩起了一款战略游戏。这款战略游戏的地图由n个城市以及m条连接这些城市的双向道路构成，并且从任意一个城市出发总能沿着道路走到任意其他城市。现在小C已经占领了其中至少两个城市，小Q可以摧毁一个小C没占领的城市，同时摧毁所有连接这个城市的道路。只要在摧毁这个城市之后能够找到某两个小C占领的城市u和v，使得从...

2018-05-25 18:21:39 307

原创 bzoj5328: [Sdoi2018]物理实验【坐标旋转+扫描线+set】

Description小T这学期有物理实验课，为了顺利完成下一节课的实验，他打算在课前对实验内容进行预习。这次实验在一个二维平面上进行，平面上放置了一条无限长的直线导轨，导轨上放置了一个长为L的激光发射器，激光发射器会向导轨两侧沿导轨垂直方向同时发射宽度为L的平行激光束。平面上还放置了n个挡板，每个挡板可以看作是一条线段，现在每个挡板都不和直线导轨接触，且和直线导轨的夹角不超过85...

2018-05-25 18:17:25 507

原创 loj#2325. 「清华集训 2017」小 Y 和恐怖的奴隶主

传送门解题思路：设 p[i][j][k][l]p[i][j][k][l]p[i][j][k][l] 表示 iii 回合奴隶主 1、2、31、2、31、2、3 血剩余情况为 j、k、lj、k、lj 、k 、l 的概率，那么对答案的贡献就是 p[i][j][k][l]j+k+l+1p[i][j][k][l]j+k+l+1\frac{p[i][j][k][l]}{j+k+l+1} 。先预...

2018-05-24 20:54:22 583

原创 LOJ#6389. 「THUPC2018」好图计数 / Count【生成函数】

传送门解题思路：终于卡过去了…… 这题和求无标号有根树个数的思路差不多，可以先看这里，因为下面一些公式演算会省略中间过程。设大小为 nnn 的好图数目为fnfnf_n，其中连通的数目为gngng_n 注意但n≥2n≥2n\ge 2时，不连通的好图和连通的好图一一对应，即gn=fn/2gn=fn/2g_n=f_n/2考虑生成函数F(x)=∑fixiF(x)=∑fixiF(x)=\...

2018-05-24 19:09:01 966

原创 SPOJ PT07D ：Let us count 1 2 3 【树的计数】

传送门解题思路：四种树的计数方式： 1.有标号无根树：根据prufer序列可知是nn−2nn−2n^{n-2}2.有标号有根树：一棵有标号无根树以每个节点为根，所以是nn−1nn−1n^{n-1}3.无标号有根树：设 fifif_i 表示树的大小为 iii 的方案数，其生成函数是 F(x)=∑fixiF(x)=∑fixiF(x)=\sum f_i x^i 考虑到一棵无...

2018-05-24 15:26:07 837

原创 LOJ#6387. 「THUPC2018」绿绿与串串 / String【manacher】

传送门解题思路：签到题。先manacher，一个点如果回文右端点抵到n则合法，或是左端点抵到1且右端点合法。#include<bits/stdc++.h>using namespace std;int getint(){ int i=0,f=1;char c; for(c=getchar();(c!='-')&&(c<'0'|...

2018-05-23 19:42:01 468

原创 bzoj4897: [Thu Summer Camp2016]成绩单【区间dp】

Description期末考试结束了，班主任L老师要将成绩单分发到每位同学手中。L老师共有n份成绩单，按照编号从1到n的顺序叠放在桌子上，其中编号为i的成绩单分数为w_i。成绩单是按照批次发放的。发放成绩单时，L老师会从当前的一叠成绩单中抽取连续的一段，让这些同学来领取自己的成绩单。当这批同学领取完毕后，L老师再从剩余的成绩单中抽取连续的一段，供下一批同学领取。经过若干批次的领取后...

2018-05-23 15:45:37 318

原创 bzoj4105: [Thu Summer Camp 2015]平方运算【线段树】

DescriptionInput第一行有三个整数N，M，p，分别代表序列的长度、平方操作与询问操作的总次数以及在平方操作中所要模的数。接下来一行N个数代表一开始的序列{X1,X2,…,XN}。接下来M行，每行三个整数op,l,r。其中op代表本次操作的类型。若op=0，代表这是一次平方操作，平方的区间为[l,r]；如果op=1，代表这是一次询问操作，询问的区间为[l,r]。...

2018-05-22 20:56:49 380

原创 bzoj4103: [Thu Summer Camp 2015]异或运算【可持久化trie树】

Description给定长度为n的数列X={x1,x2,…,xn}和长度为m的数列Y={y1,y2,…,ym}，令矩阵A中第i行第j列的值Aij=xi xor yj，每次询问给定矩形区域i∈[u,d],j∈[l,r]，找出第k大的Aij。Input第一行包含两个正整数n,m，分别表示两个数列的长度第二行包含n个非负整数xi 第三行包含m个非负整数yj 第四行包含一个正整...

2018-05-22 18:21:56 279

原创 bzoj5077: [Ctsc2016]时空旅行【线段树+凸包】

Description2045年，人类的技术突飞猛进，已经找到了进行时空旅行的方法。小R得到了一台时空旅行仪，他想用它调查不同时空中人类的发展状况。根据平行时空理论，宇宙中存在着很多独立的时空，每个时空在下一个时间点还会分化出若干个不同的时空。宇宙是一个三维空间，人类使用空间直角坐标系来描述空间中的一个位置，三维坐标分别是 x ,y,z。我们假设在初始的时空（编号为 0）中，人类存在...

2018-05-22 17:04:55 513

原创 bzoj5336: [TJOI2018]party【状压dp】

Description小豆参加了NOI的游园会，会场上每完成一个项目就会获得一个奖章，奖章只会是N, O, I的字样。在会场上他收集到了K个奖章组成的串。兑奖规则是奖章串和兑奖串的最长公共子序列长度为小豆最后奖励的等级。现在已知兑奖串长度为N，并且在兑奖串上不会出现连续三个奖章为NOI，即奖章中不会出现子串NOI。现在小豆想知道各个奖励等级会对应多少个不同的合法兑奖串。...

2018-05-21 15:00:24 523

原创 bzoj5335: [TJOI2018]智力竞赛【二分+最小路径覆盖】

Description小豆报名参加智力竞赛，他带上了n个好朋友作为亲友团一块来参加比赛。比赛规则如下: 一共有m道题目，每个入都有1次答题机会，每次答题为选择一道题目回答，在回答正确后，可以从这个题目的后续题目，直达题目答错题目或者没有后续题目。每个问题都会代表一个价值，比赛最后的参赛选手获得奖励价值等价于该选手和他的亲友团没有回答的问题中的最低价值。我们现在知道小豆和他的亲友团...

2018-05-21 14:56:08 344

原创 bzoj5317: [Jsoi2018]部落战争【凸包/Minkowski sum】

传送门解题思路：先求凸包。合法向量相当于凸包A中存在一点经过该向量可到凸包B中。即 A+v⃗ =BA+v→=BA+\vec v=B ，那么v⃗ =A−Bv→=A−B\vec v=A-B 画图发现，这些向量的轮廓就是凸包A绕取反后凸包B坐标平移一圈。好像这个东西也叫Minkowski sum，即求{v⃗ =a⃗ +b⃗ ,a⃗&...

2018-05-21 14:53:12 1523

原创 Codeforces908H. New Year and Boolean Bridges【并查集+强联通+FWT】

题目大意：有一个n个点的有向图。定义i能到达j时f(i,j)=1，否则f(i,j)=0。对于每个点对(i,j)，给定以下三个条件中的某一个为真： (1) f(i,j) and f(j,i)=1； (2) f(i,j) or f(j,i)=1； (3) f(i,j) xor f(j,i)=1。求满足条件时的最小边数。 1<=n<=47。解题思路：等价于满足...

2018-05-18 18:35:01 384

原创 UOJ#205. 【APIO2016】Fireworks【动态规划+折线优化+可并堆】

题目大意：给出一棵树，边有边权，可以花费1的代价把一条边的权值加1或者1，不能减到负的。要让根到所有叶子的边权和都相等。问最小代价。 n&amp;lt;=600000解题思路：设 fx(i)fx(i)f_x(i) 表示 xxx 的子树中的叶子到 xxx 距离全部搞成 iii 的最小代价。设 gx(i)gx(i)g_x(i)表示 xxx 的子树中的叶子到 faxfaxf...

2018-05-18 11:32:10 316

原创 hihoCoder Challenge 29 D. 不上升序列【动态规划+折线+堆】

题目大意：给出一个整数序列，可以花费1的代价把一个数+1或1，求把它变成不上升序列的最小代价。n&lt;=500000;令 fi(x)fi(x)f_i(x) 为前个数，调整出最大值不超过 xxx 的最小代价,那么 fifif_i 是一条不升的折线考虑转移 fi(x)=miny≤xfi−1(y)+|ai−y|fi(x)=miny≤xfi−1(y)+|ai−y|f_i(x)=\te...

2018-05-18 08:39:42 230

原创 bzoj4182: Shopping【点分治+单调队列优化多重背包】

题目大意：给定一棵有 n 个点的树，第 i 个点有 di 件商品，价格为 ci，价值为 wi。你手头有 m 块钱，且你要保证你买过的点在树上互相连通，问买到的物品的总价值最多是多少。 1 ≤ n ≤ 500, 1 ≤ m ≤ 4000, di ≤ 100。解题思路：如果直接树形dp是O(nm2d)O(nm2d)O(nm^2d)的，显然过不了考虑如果强制要选一个点怎么做。 ...

2018-05-17 21:35:18 490

原创 bzoj4361: isn【树状数组优化dp+容斥】

Description给出一个长度为n的序列A(A1,A2…AN)。如果序列A不是非降的，你必须从中删去一个数，这一操作，直到A非降为止。求有多少种不同的操作方案，答案模10^9+7。Input第一行一个整数n。接下来一行n个整数，描述A。Output一行一个整数，描述答案。Sample Input41 7 5 3Sample Outpu...

2018-05-17 15:41:33 164

原创 hdu4352 XHXJ's LIS【数位dp】

题目大意：定义f(i)表示将i看成字符串的最长上升子序列长度。给定l,r,k，求满足l<=i<=r且f(i)=k的个数。 1<=l<=r<=10^18，1<=k<=10，T<=10000。解题思路：注意是最长上升序列，如果是不下降序列就无法做了。回忆O(nlogn)求 LIS 的过程，维护一个上升序列，每次新加一个数的时候，...

2018-05-17 14:27:23 161

原创 TopCoder SRM697 div1 hard【prufer序列】

题目大意：有n≤2000n≤2000n\le 2000个城市，每个城市有个权值wiwiw_i，任意两个城市之间的道路数有wi∗wjwi∗wjw_i*w_j条。对于每种生成树，设每个点的度数为didid_i，其权值定义为∏di∏di\prod d_i。问所有无根生成树的权值和。答案对109+7109+710^9+7取模。解题思路：主要说一下思路和推导过程。考虑生成树中的一条边 (i...

2018-05-17 11:02:22 298

原创 Codeforces908G - New Year and Original Order【数位dp】

题目大意：令S(i)表示将i的数位从小到大排序后形成的数。例如S(50394)=3459。给定整数n，求S(1)+…+S(n)。对10^9+7取模。 1<=n<=10^700。解题思路：对于形如3459这种不下降数，一般可以化为a[4]*1111+a[3]*111+a[2]*11+a[1]*1的形式去处理。其中a[i]的意义为相邻两位的差，又可以表示为所有数位中大...

2018-05-17 09:33:09 541 1

原创 bzoj4380: [POI2015]Myjnie【区间dp】

Description有n家洗车店从左往右排成一排，每家店都有一个正整数价格p[i]。有m个人要来消费，第i个人会驶过第a[i]个开始一直到第b[i]个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于c[i]，那么这个人就不洗车了。请给每家店指定一个价格，使得所有人花的钱的总和最大。Input第一行包含两个正整数n,m(1<=n<=...

2018-05-17 07:49:09 232

原创 Codeforces908D. New Year and Arbitrary Arrangement【期望dp】

题目大意：给定整数k,pa,pb。初始有一个空序列，每次往末尾添加一个字符，有pa/(pa+pb)的概率添加a，有pb/(pa+pb)的概率添加b。当ab作为子序列出现了至少k次的时候停止，问此时ab**子序列**出现次数的期望。对10^9+7取模。 1<=k<=1000，1<=pa,pb<=10^6。解题思路：设f[i][j]f[i][j]f[i...

2018-05-16 20:27:22 260

原创 bzoj3639: Query on a tree VII【LCT+set】

题目大意：给一棵黑白带点权树，支持单点翻转颜色，单点修改权值，询问某点同色连通块内点权最大值。 n,m<=100000解题思路：同Qtree6，把虚边维护size改为用multiset维护最大点权即可。#include<bits/stdc++.h>#define ll long longusing namespace std;int getint(){...

2018-05-16 17:03:08 296

空空如也

空空如也