- 博客(210)
- 收藏
- 关注
RSS订阅原创 ＜＜人工智能导论＞＞上机--动物特征识别
就写的挺垃圾的。。。/** @author: codancer* @createTime: 2020-11-28, 14:41:28*/#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cmath>#include <vector>#include <set>#include &
2020-11-29 22:32:39
337
原创 ＜＜人工智能导论＞＞上机--遗传算法求解函数最值
利用遗传算法求解函数f(x,y)=1/(x2+y2+1),x,y∈[−5,5]f(x,y)=1/(x^2+y^2+1),x,y\in[-5,5]f(x,y)=1/(x2+y2+1),x,y∈[−5,5]的最大值。显然答案为1。代码:/** @author: codancer* @createTime: 2020-11-28, 21:58:25*/#include <iostream>#include <cstdio>#include <
2020-11-29 22:27:33
2306
1
原创 ＜＜人工智能导论＞＞上机--A*解决八数码问题
A*算法的精髓：f(n)=g(n)+h(n)f(n)=g(n)+h(n)f(n)=g(n)+h(n)h(n)h(n)h(n)是当前状态nnn到目标状态的欧几里得距离和。利用堆优化BFSBFSBFS即可。还可以在BFSBFSBFS时记录前驱，然后倒着找到路线方案。/** @author: codancer* @createTime: 2020-11-28, 17:31:10*/#include <iostream>#include <cstdio>#includ
2020-11-28 18:58:34
518
原创 ＜＜人工智能导论＞＞上机-【野人过河问题】DFS实现
#include<bits/stdc++.h>using namespace std;//3 3 1 //a 为左岸传教士 b为左岸野人 c为船的状态 1为左岸，0为右岸 int cnt=0;bool is_valid(int a,int b,int c){ if(a&&b>a) return 0; if(3-a&&3-b>3-a) return 0; return 1;}bool vis[5][5][2];void DFS
2020-11-13 14:37:11
298
原创 2019 kickstart round H
H-Index题意：对于一个数组，对于每个i(1≤i≤n)i( 1\leq i \leq n)i(1≤i≤n)，找到一个数字HHH，使得a1...aia_{1}...a_{i}a1...ai中大于等于HHH的数字的出现的次数也大于等于HHH。solution:可发现对于从iii到i+1i+1i+1，答案最多增加111，可以用优先队列或者数据结构来实现查询操作，时间复杂度O(nlog(n)...
2019-11-18 16:38:27
553
原创 SQL学习笔记------基础语法
创建数据库:CREATE DATABASE <数据库名>创建表：use student create table studentinfo( name varchar(20), id char(10), score int not null);use <数据库名> 指定数据库char 是固定字节长度， varchar 是可变的字节长度，后面的数字是最大字...
2019-11-09 15:11:47
133
原创 【codeforces 1243】D. 0-1 MST（补图的连通块计数）
题意：给你一个图，求补图的联通块个数。题解：考虑用使用并查集，用set存已经被放入并查集的点，对于没有放入的点，计算该点和联通块相连的点的个数，如果相连的点的个数小于联通块大小，则直接连进去即可。时间复杂度O(n+m∗log)O(n+m*log)O(n+m∗log)。代码：#include<bits/stdc++.h> using namespace std;const...
2019-11-07 10:15:16
671
3
原创 【AtCoder Grand Contest 040】B.Two Contests
题意nnn段区间，要把他们分到两个不同的集合S,TS,TS,T中，不能有剩余，每个区间只能在一个集合里，令SSS中所有区间的交的长度为lslsls，TTT中所有区间的交为ltltlt，求max{ls+lt}max\{ls+lt\}max{ls+lt}。题解找到 LLL 最大的区间 ppp 和 rrr 最小的区间 qqq，那么只有两种情况:1.1.1. p,qp,qp,q在同一个集合内，那么...
2019-11-04 10:42:44
580
原创 【HDU 3622】 Bomb Game(2-SAT)
题意：一个游戏有nnn轮，每轮提供给你两个坐标，你选择其中一个放置炸弹，到最后会放置nnn个炸弹，要保证任意两个炸弹的爆炸区域不会相交，每个炸弹的爆炸半径由你来决定，你的目的是使最小的半径最大。题解：考虑二分半径，对于半径rrr，O(n2)O(n^2)O(n2)的建立约束关系，利用2−SAT2-SAT2−SAT判断可行性。时间复杂度O(n2log(n))O(n^2log(n))O(n2log...
2019-10-30 15:26:06
164
原创 【codeforces 1225D】Power Products
题意计算满足ai∗aj=xk,i<ja_{i}*a_{j}=x^k,i<jai∗aj=xk,i<j的对数。思路考虑x∗y=pkx*y=p^kx∗y=pk，将xxx和yyy进行质因子分解可得:x=p1m1p2m2p3m3...pnmnx=p_1^{m_1}p_2^{m_2}p_3^{m_3}...p_n^{m_n}x=p1m1p2m2p3m3...pnm...
2019-10-27 22:21:05
444
原创 Educational Codeforces Round 75 (Rated for Div. 2)
A如果某个字母连续出现的次数是奇数，那么这个键一定是好的，遍历一遍即可。#include<bits/stdc++.h>using namespace std;int main(){ int T; cin>>T; while(T--){ string s; cin>>s; set&l...
2019-10-25 20:09:05
126
原创 Codeforces Round #595 (Div. 3)
A对数组排序，如果存在相邻两项为1，则最少可以分成两组，否则分成1组。#include<bits/stdc++.h> using namespace std;int a[200];int main(){ int T; cin>>T; while(T--){ int n; cin>>n; ...
2019-10-23 16:59:59
154
原创 【LOJ 网络流24题】方格取数
方格取数题解按照顺序对应不同的格子染色，相邻的染不同的颜色，从SSS向所有的黑色的点建流量为对应权值的边，从所有的白点向TTT建流量为对应权值的边。对于有冲突的黑点和白点之间建流量为infinfinf的边，跑最小割，所有点的和减去最小割即为答案（最大权独立子集）代码：#include<bits/stdc++.h>using namespace std;const int ...
2019-10-11 17:52:52
138
原创 【LOJ 网络流24题】试题库
试题库题解：SSS向mmm中类型连接容量为对应需求量的边，题目种类和对应的属于该种类的题目连流量为1的边，每道题和TTT连流量为111的边，跑最大流即可。#include<bits/stdc++.h>using namespace std;const int N = 80000;const int maxn = 2000;const int INF = 0x3f3f3f...
2019-10-11 17:47:10
280
原创 【LOJ 网络流24题】最长递增子序列
最长递增子序列题解：对于第一个查询直接dpdpdp即可，dpidp_{i}dpi代表以iii结尾的最长上升子序列的最大长度，计算出sss。对于第二个查询，对于每个点拆分成两个点i1,i2i_1,i_2i1,i2，如果dpidp_idpi为111，则SSS向i1i_1i1连接流量为111的边，如果dpidp_idpi为sss，则i2i_2i2向TTT连接流量为111的边，对于每...
2019-10-11 15:01:57
162
原创 【LOJ 网络流24题】圆桌聚餐
圆桌聚餐题解：从SSS向每个单位连接流量为rir_iri的边，每个单位向每个桌子连接流量为111的边，每个桌子向TTT连接流量为cic_ici的边，跑最大流即可。如果满流，即maxflow=maxflow=maxflow=人数，则存在方案。对于方案的输出：对于每个单位，记录下向哪些桌子流出了流量即可。代码：#include<bits/stdc++.h>using nam...
2019-10-11 14:49:54
236
原创 【LOJ 网络流24题】魔术球
魔术球题解：考虑如果i+ji+ji+j为完全平方数，则iii和jjj之间连一条边，那么最后构成一个图GGG，那么问题即可转化为寻找一个最大的数字mmm，使得按照上述方法构成的图的最小路径覆盖数小于等于nnn，我们二分mmm即可，构造方案同最小路径覆盖一题。#include<bits/stdc++.h>using namespace std;const int N = 100...
2019-10-10 18:50:14
183
原创 【LOJ 网络流24题】最小路径覆盖
最小路径覆盖题解：假设x,yx,yx,y之间有一条边，则把xxx和yyy分别拆成x1,x2,y1,y2x_1,x_2,y_1,y_2x1,x2,y1,y2。在x1x_1x1和y2y_2y2之间连接一条流量为111的边，构造好二分图后答案即为n−maxmatchn-maxmatchn−maxmatch。对于方案的输出，可以利用并查集，对于xxx和yyy，如果流量流经x−>yx-...
2019-10-10 16:48:05
168
原创 【LOJ 网络流24题】太空飞行计划
太空飞行计划题解：最大权闭合子图，设V′V'V′为G(V,E)G(V,E)G(V,E)的一个点集，如果VVV中对于每个点的所有的出边所到达的点也∈V′\in V'∈V′，那么V′V'V′即为一个闭合子图，最大权闭合子图即为所有的闭合子图中权值和最大的。定理：从SSS向所有权值为正数的点增加一条等于该点点权的流量的边，从所有权值为负数的点向TTT增加一条等于该点权绝对值流量的边，对于u(wu&...
2019-10-10 16:46:55
157
原创 【codeforces 590div3】F.Yet Another Substring Reverse
题意：现在有一个字符串 sss（1≤∣s∣≤1061 \leq |s| \leq 10^61≤∣s∣≤106）,现在选择一个区间[l,r][l,r][l,r]，反转一次或者不反转。若某区间的字母各不相同，则该区间为完美区间。你要做的就是执行完操作后使完美区间的长度最大。（整个字符串的字母种类数不超过202020）题解:这个问题可以转换为寻找两个不相交的完美区间使得他们的长度和最大。首先枚举...
2019-10-02 12:14:03
222
3
原创 codancer的图论训练（updating...）
2019.9.12580C.Kefa and Parktags: 简单DFS1081D.Maximum Distancetags:带点思维的MST，学会了只联通某些点的并查集
2019-09-12 19:03:28
237
原创 JSOI2007:字符加密(后缀数组)
题意：将长度为nnn的字符串排成一圈，对于nnn种排列方式构成的字符串按字典序从小到大输出最后一位。题解：1.将原串扩展成2倍（避免有些没有遍历到）。2.建立后缀数组，对于saisa_{i}sai小于nnn的输出第sai+n−1sa_i+n-1sai+n−1位即可。代码：// luogu-judger-enable-o2#include<bits/stdc++.h>...
2019-09-12 11:11:13
168
原创 The Preliminary Contest for ICPC Asia Xuzhou 2019
B.so easy并查集，可能会卡掉map,建议使用unordered_map。#include<bits/stdc++.h>using namespace std;const int N = 1e6+100;const int mod = 1e9+7;typedef long long ll;const int INF = 0x3f3f3f3f;const ll ll...
2019-09-09 17:24:15
226
原创 The Preliminary Contest for ICPC Asia Nanjing 2019
A.The beautiful values of the palace首先对于每个(x,y)(x,y)(x,y)，我们可以O(1)O(1)O(1)的查询出这个坐标的值。接下来就将问题转化为了一个106⋅10610^6 \cdot 10^6106⋅106的矩阵，每次查询子矩阵内的点的和。考虑将所有的yyy离散化，计mpi,jmp_{i,j}mpi,j表示(1,1)−(i,j)(1,1)-(i...
2019-09-04 11:08:53
258
原创 AtCoder Beginner Contest 139
A#include<bits/stdc++.h>using namespace std;const int N = 1e6+100;const int mod = 1e9+7;typedef long long ll;const int INF = 0x3f3f3f3f;const ll llINF = 0x3f3f3f3f3f3f3f3f;#define rep(i,...
2019-09-01 22:14:48
277
原创 【codeforces 1026 D】 Shortest Cycle（最小环）
题面题意：一个长度为nnn的数组，如果ai&aj!=0a_{i} \& a_{j}!=0ai&aj!=0，那么iii和jjj之间就有一条边，计算所构成图的最小环。(1≤n≤100000,1≤ai≤1018)(1 \leq n \leq 100000,1 \leq a_i \leq 10^{18})(1≤n≤100000,1≤ai≤1018)思路...
2019-08-28 17:43:37
170
原创 【codeforces 1208D】 Restore Permutation(线段树)
题面题意：一个长度为nnn的排列aaa，现在定义pip_ipi为数组aaa中下标小于等于iii并且小于aia_iai的数字的和。现在给定ppp，求aaa。思路：首先可以肯定的是，ppp中最后一个000出现的位置pospospos在aaa中一定是111。我们可以反证：假设aposa_{pos}apos不为111，假设111在pospospos之前，那么ppos≥1p_{pos} \g...
2019-08-27 11:30:20
182
原创 【HDU 6714】最短路2（Dijkstra）
题面题意：对于floyedfloyedfloyed算法，Di,jD_{i,j}Di,j表示最外层循环最小的能够求出来disi,jdis_{i,j}disi,j的循环次数，计算∑i=1n∑j=1nDi,j\sum_{i=1}^{n}{\sum_{j=1}^{n}{D_{i,j}}}∑i=1n∑j=1nDi,j思路其实Di,jD_{i,j}Di,j即为iii到jjj的最短路路径上最...
2019-08-25 08:53:39
170
原创 【HDU 6638】Snowy Smile(线段树求区间连续最大和)
题面题意平面坐标系有nnn个点，第iii个点的坐标为(xi,yi)(x_i,y_i)(xi,yi),每个点有个权值wiw_iwi，现在你需要寻找一个矩形把某些点圈起来使得他们的权值和最大。思路先把各点的纵坐标离散化，然后把所有的点按照横坐标从小到大排序，枚举矩形的左边界，每加入一个新的点，就把它对应纵坐标yyy的权值和w[y]w[y]w[y]更新并更改右边界，当左右边界都确定以后，利...
2019-08-10 10:56:47
142
原创 【HDU 6627】equation(分段函数求值)
题目链接题意：两个长度为nnn的数组aaa和bbb和一个正整数CCC，计算有多少个xxx满足：∑i=1n∣ai⋅x+bi∣=C\sum_{i=1}^n|a_i \cdot x+b_i|=Ci=1∑n∣ai⋅x+bi∣=C思路：该函数为分段函数，每段的转折点为−biai-\frac{b_i}{a_i}−aibi,先把转折点排序，计最开始的函数值为x⋅suma+sumbx \...
2019-08-06 10:57:12
179
原创 2019牛客暑期多校D.Big Integer
题面题意：定义A(n)A(n)A(n)为nnn个1构成的数字，如A(3)=111A(3)=111A(3)=111，计算有多少对(i,j)(i,j)(i,j)使得A(ij)%p=0A(i^j) \% p = 0A(ij)%p=0。思路：通过枚举发现是有上面的等式是有循环节的，而且循环节是p−1p-1p−1的因子，因此暴力枚举计算出循环节ddd，接下来就是求有多少对ij%d=0i^j \% d...
2019-08-05 20:32:49
110
原创 【HDU 6621】 K-th Closest Distance(主席树+二分)
题面题意：一个长度为nnn的数组，有mmm次查询，对于每次查询，查询[l,r][l,r][l,r]内距离ppp第kkk近的距离。强制在线。思路考虑二分距离disdisdis，对于每次的disdisdis，判断在[l,r][l,r][l,r]内在区间[p−dis,p+dis][p-dis,p+dis][p−dis,p+dis]内的数是否超过了kkk个，该操作可以利用主席树来实现，复杂度O(n...
2019-08-05 19:40:16
150
原创 对主席树的理解以及使用
引入一个长度为nnn的数组，有mmm次查询，每次查询区间[l,r][l,r][l,r]内第kkk小的元素。如果使用暴力，肯定不可以使用线段树？可是我只会查询区间最值啊。那么我们把问题再次简化一下，查询[1,n][1,n][1,n]第kkk小的元素，要求使用线段树来实现。权值线段树为了解决这个问题，我们引入一个名词:权值线段树。那么权值线段树是如何解决上面那个问题的呢？首先，我们对数组...
2019-07-30 15:55:52
1519
2
原创 2019 牛客多校第二场 D.Kth Minimum Clique(bitset优化)
D.Kth Minimum Clique(bitset优化)题面题意：求一个无向连通图的第KKK大完全子图。思路：新技能：利用bitsetbitsetbitset存储子图，假设把iii能到达的点的位设置为111，这样我们就可以通过直接进行与运算来判断这个点是否能放到现在的团里面。然后BFS即可。代码：#include<bits/stdc++.h> using name...
2019-07-23 21:30:10
142
原创 2019江西省程序设计竞赛
A.Cotree题意:两棵树，你需要连接两个点使得∑i=1i=n∑j=i+1j=ndis(i,j)\sum_{i=1}^{i=n}{\sum_{j=i+1}^{j=n}}{dis(i,j)}∑i=1i=n∑j=i+1j=ndis(i,j)最小。思路：对于每棵树进行换根dp，对每棵子树找到一个点使得所有点到这个点的距离和最小，连接这两个点，然后进行一次DFS统计每条边的贡献，累加即可。...
2019-07-21 23:23:31
821
原创 【 Codeforces Round #572 (Div. 2)】E. Count Pairs（数学）
题面题意：现在有一个长度为nnn的数组aaa，找出有多少对(i,j)(i,j)(i,j)满足1≤1\leq1≤i<ji<ji<j≤n\leq n≤n并且(ai+aj)∗(ai2+aj2)modp==k(a_i+a_j)*(a_i^{2}+a_j^{2})modp==k(ai+aj)∗(ai2+aj2)modp==k。思路：左右同乘(ai−aj)(a...
2019-07-06 10:05:12
517
原创 【Educational Codeforces Round 67 (Rated for Div. 2)】E. Tree Painting（换根DP）
题面题意：一棵树，有nnn个节点,现在要找一个点作为根节点使得这棵树的所有子树的大小和最大。求出最大值。思路：先利用一次dfs求出以iii为根的子树的大小sizisiz_isizi和所有的字数和$$...
2019-07-03 10:49:49
172
原创 【ABC 132 E】Hopscotch Addict(最短路)
题面题意：一个有向图，从SSS出发，每次只能走三步(即连续三条边)，现在问你能否经过若干步到达TTT,如果可以输出最少的步数，否则输出−1-1−1。思路：disi,jdis_{i,j}disi,j代表S到iS到iS到i的距离disdis%3dis为jjj的最短路，我们要计算的即为disT,0dis_{T,0}disT,0，BFSBFSBFS即可，注意状态的传递。code:#incl...
2019-06-30 16:40:55
510
原创 【Codeforces Round #569 (Div. 2)】 题解
A小学数学题#include<bits/stdc++.h>using namespace std;long long f[102];void init(){ f[1]=1; for(int i=2;i<=101;i++){ f[i]=f[i-1]+(i-1)*4; }}int main(){ init(); int n; cin>>n;...
2019-06-24 11:58:01
192
原创 【CF 1185G1】Playlist for Polycarp (easy version)（状压DP）
题面题意现在你有nnn首歌，第iii首歌的播放时间为tit_iti,种类为fif_ifi,其中1≤fi≤31 \leq f_i \leq 31≤fi≤3,现在你从家到学校需要花费TTT的时间，你在路上不想闲着，现在你要选几首歌按照一定的顺序播放，你要保证着几首歌的时间总和为TTT（每首歌只会播放一次），并且在播放的时候不会连续播放同一种类的歌曲，计算共有多少种方案，答案对109+710^...
2019-06-20 20:35:00
262
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人