D.Y.T-CSDN博客

原创 1107 Social Clusters (30 分) 按爱好分类并没有什么错误！

本题明显是一道并查集题目，如果直面硬刚选择连接人员并查集，然后n^2遍历建立并查集，那么会感受到30分的难度，因为只要把数据改大些就能让这种做法超时。一种更好的做法是连接爱好，这样做本题便会变成一个简单的带权并查集模板题。复杂度远远小于O(n^2)#include <bits/stdc++.h>using namespace std;const int N = 1010;int f[N], size[N];int find(int x){ return x==f[x]?x:f

2021-03-05 21:26:25 144

原创 1104 Sum of Number Segments (20 分) 精度问题，大坑!!

程序中有多次浮点数相加时，切记放大1000倍左右用long long 存储！n = int(input())m = [float(n) for n in input().split()]k = [0 for i in range(n)]ans = 0for i in range(n): k[i] = int(m[i]*1000) ans += k[i]*(n-i)*(i+1)ans = ans/1000print("%.2f"%ans)...

2021-03-03 20:23:55 235 1

原创分支限界法求解01背包问题

使用优先队列，求最大价值首先按照性价比排序bound函数表示当前状态之后的选择都是理想的，这样能到达的理想最大值每个节点存储物品在树中的层次，表示已经对多少个物品做出了选择，当前状态放入背包的总价值和重量。#include <bits/stdc++.h>using namespace std;const int N = 110;struct stone{ int v, w; stone(){ v = w = 0; } bool operator < (ston

2020-12-18 20:24:52 4309 2

原创 P2522 Problem b 莫比乌斯反演+数论分块+二维前缀和

#include <bits/stdc++.h>#define rll register ll#define ll long longusing namespace std;const int N = 5e4+100;int p[N], prime[N], mu[N], cnt;void primes(int n){ mu[1] = 1; for(int i = 2; i <= n; i++){ if(!p[i]) p[i] = prime[++cnt] = i.

2020-12-17 00:49:17 125

原创 P2257 YY的GCD 线性筛+莫比乌斯反演+数论分块

#include <cstdio>#define min(a,b) ((a<b)?(a):(b))#define ll long longusing namespace std;const int N = 1e7+10, lnN = 15;int p[N], prime[N/lnN], f[N];int mu[N], cnt;void primes(ll n){ mu[1] = p[1] = 1; for(register int i = 2; i <= n; .

2020-12-17 00:41:28 101

原创计算机网络原理笔记第四章

IPv6IPv6仍旧是无连接，协议数据单元(PDU)称为分组。主要变化更大的地址空间扩展的地址层次结构灵活的首部格式改进的选项允许协议继续扩充支持即插即用，自动配置支持资源的预分配首部改为8字节对齐IPv6数据报的一般形式基本首部IPv6有固定40字节的基本首部。对首部中的某些字段进行了如下更改：取消了首部长度，因为首部长度固定取消服务类型取消总长度，改为有效载荷取消标识，标志和片偏移字段，其功能放在扩展首部把TTL字段改为跳数限制取消协议字段，改用下一个首部

2020-12-16 14:46:27 220

原创《web前端开发技术》练习题

练习1HTML是一种（超文本标记）语言世界上第一个网页是（http://info.cern.ch）访问FTP站点使用的协议类型是（ftp）下列不是开发HTML网页的软件是（Visual Basic），开发软件有：EditPlus, Notepad, TextPad, Sublime Text, WebStorm, HBuilder, AdobeDreamweaver设计JavaScript语言的公司是（Netscape）练习2下列标记用于设置页面标题的标记是（<title>）

2020-12-16 14:04:08 7225 1

原创 P3455 [POI2007]ZAP-Queries 莫比乌斯反演+数论分块

∑i=1a∑j=1b[(i,j)=k]=∑d=1min(⌊ak⌋,⌊bk⌋)μ(d)⌊⌊ak⌋d⌋⌊⌊bk⌋d⌋\sum_{i=1}^a\sum_{j=1}^b[(i,j)=k]=\sum_{d=1}^{min(\lfloor \frac{a}k\rfloor,\lfloor\frac{b}k\rfloor)}\mu(d)\lfloor\frac{\lfloor\frac{a}k\rfloor}d\rfloor\lfloor\frac{\lfloor\frac{b}k\rfloor}d\rfloori=1.

2020-12-15 19:53:46 124

原创 P4213 模板杜教筛

积性函数对于(a,b)=1(a,b)=1(a,b)=1，fff有f(ab)=f(a)×f(b)f(ab)=f(a)×f(b)f(ab)=f(a)×f(b)完全积性函数对于任意a,ba,ba,b, fff有f(ab)=f(a)×f(b)f(ab)=f(a)×f(b)f(ab)=f(a)×f(b)常见积性函数I(x)=1I(x)=1I(x)=1e(x)=[x=1]e(x)=[x=1]e(x)=[x=1]idk(x)=xkid_k(x)=x^kidk(x)=xkσk(x)=∑d∣xdk\sigm

2020-12-15 19:02:23 110

原创 P2458 保安站岗树形dp

#include <bits/stdc++.h>using namespace std;const int N = 6010;const int inf = 0x3f3f3f3f;int ver[N], ne[N], head[N];int dp[N][3], r[N], v[N], tot;void add(int x, int y){ ver[++tot] = y, ne[tot] = head[x], head[x] = tot;}void dfs(int x){

2020-12-15 00:10:51 132

原创 P1352 上司的舞会树形DP复习

#include <bits/stdc++.h>using namespace std;const int N = 6010;int ver[N], ne[N], head[N];int dp[N][2], r[N], v[N], tot;void add(int x, int y){ ver[++tot] = y, ne[tot] = head[x], head[x] = tot;}int dfs(int x, int sta){ if(x == -1) return

2020-12-15 00:09:18 112

原创快读快写

inline int read(){ int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f;}inline void write(int x){ if(x&lt

2020-12-14 23:10:50 85

原创 P2260 P2834 [清华集训2012]模积和数论分块

调了1个小时的分块#include <iostream>#include <algorithm>#define ll long longusing namespace std;const int mod = 19940417;ll inv2, inv6;ll sum(ll l, ll r){ return (l+r)%mod*((r+1)%mod+mod-l)%mod*inv2%mod;}ll sum1(ll l, ll r){ return (r*((..

2020-12-14 22:46:27 120 1

原创二次剩余模板

复杂度O(log(m))struct complex{ ll x, y, sqw;//w的平方 complex(ll x = 0, ll y = 0, ll sqw = 0):x(x),y(y),sqw(sqw){ } complex operator * (const complex &b) const { return complex((x*b.x%mod+y*b.y%mod*sqw%mod)%mod, (x*b.y%mod+y*b.x%mod)%mod, sqw); }

2020-12-14 21:33:07 98

原创 P2424 约数和数论分块

f(x)表示约数和求∑i=xyf(i)\sum_{i = x}^yf(i)∑i=xyf(i)首先肯定是求∑i=1nf(i)\sum_{i = 1}^nf(i)∑i=1nf(i)#include <bits/stdc++.h>#define ll long longusing namespace std;ll x, y;ll sum(ll l, ll r){ return (l+r)*(r+1-l)/2;}ll solve(ll n){ ll ans = 0; f.

2020-12-14 21:04:11 99

原创 P1403 数论分块换枚举方式

设f(i)f(i)f(i)是iii的因子的个数,求∑i=1nf(i)\sum_{i=1}^nf(i)∑i=1nf(i)考虑每个可以对答案造成贡献的因子d，对于每个d来说有⌊nd⌋\lfloor\frac{n}{d}\rfloor⌊dn⌋个数可以让d作为因子，因此d对答案的贡献是⌊nd⌋\lfloor\frac{n}{d}\rfloor⌊dn⌋，因此有∑i=1nf(i)=∑i=1n⌊ni⌋\sum_{i=1}^nf(i)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloori.

2020-12-14 20:47:44 85

原创 P2261 数论分块

#include <bits/stdc++.h>#define ll long longusing namespace std;ll sum(ll l, ll r){ return (l+r)*(r-l+1)/2;}ll solve(ll n, ll k){ ll ans = 0; for(ll l = 1, r = 0; l <= n; l = r+1){ if(k/l==0) break; r = min(n, k/(k/l)); ans +=

2020-12-14 20:25:38 112

原创 Gym101981A Adrien and Austin 思维

Adrien and Austin are playing a game with rocks. Initially, there are NNN rocks, indexed from 1 to NNN. In one move, the player chooses at least 1 and at most KKK consecutively indexed rocks (all of them should not have been removed) and removes them from

2020-12-14 01:28:00 173

原创 hdu2516 斐波纳契博弈

特点：1堆石子，第一取不能取完，后面的取不能超过上次二倍，不能取失败。结论：n是斐波纳契数时必败#include <bits/stdc++.h>#define ll long longusing namespace std;const int N = 110;ll f[N];int main(){ f[0] = f[1] = 1; for(int i = 2; i <= 60; i++) f[i] = f[i-1]+f[i-2]; int n; while(sca

2020-12-14 01:11:44 135

原创 p2252 威佐夫博弈

设x<y，设z=(int)((sqrt(5)+1)/2*z)，若x=z，先手必败，反之先手必胜。#include <bits/stdc++.h>using namespace std;int main(){ int x, y; scanf("%d%d", &x, &y); if(x > y) swap(x, y); int z = y-x; z = (int)((sqrt(5)+1)/2*z); if(z == x) printf("0\n");

2020-12-14 00:59:35 125 1

原创 P2197 nim博弈

异或和为0必胜，反之必败。#include <bits/stdc++.h>using namespace std;int main(){ int t; scanf("%d", &t); while(t--){ int n, flag = 0; scanf("%d", &n); for(int i = 1; i <= n; i++) { int x; scanf("%d", &x); flag ^= x; } if(

2020-12-14 00:43:44 114

原创 7-5 氮气工厂 (20分)

某人为了研究QQ飞车，收购了一个氮气工厂，接下来的NNN（1≤NNN≤10000）个星期里，氮气价格和劳力价格不断变化。第 i 周，生产一个单位氮气需要CiC_iCi(1≤CiC_iCi ≤5000)元。工厂有一个存储柜，每保存一单位氮气，每周需要SSS(1≤SSS≤100) 元，这个费用不会变化。存储柜十分强大，可以存无限量的氮气，而且保证它们时刻都能使用。工厂接到订单，在第 i 周需要交付YiY_iYi(1≤YiY_iYi≤10410^4104) 单位的氮气给加油站。第 i 周刚生

2020-12-13 10:18:34 239

原创 7-4 爱玩飞车的小诺 (20分)

小诺非常喜欢玩qq飞车，也喜欢用雷诺这一辆车进行游戏。游戏开始时，雷诺距离终点L，氮气量为P，在起点到终点途中有n个氮气补充点，每个氮气补充点的氮气有限，而雷诺的氮气容量无限，雷诺在游戏途中，每走一个单位的距离消耗一个单位的氮气，给定n个氮气补充点距离终点的距离以及氮气存储量。问雷诺是否能到达终点。输入格式:第一行给出氮气补充点的个数N，接下来N行，每行给出第i个氮气补充点距离终点的距离以及氮气存储量。最后一行给出雷诺距离终点的距离L和氮气量P。输出格式:如果雷诺可达，输出最少的加油次数和游戏成功，

2020-12-13 00:53:18 192 1

原创同余方程求解

https://blog.csdn.net/a27038/article/details/77367076

2020-12-09 10:34:21 664

原创回顾Hash

哈希(Hash)Hash表主要包括两个基本操作：1.计算Hash函数的值。2.定位到对应表中依次遍历、比较。当Hash函数设计较好是，原始信息会被比较均匀的分配到各个表头之后，从而使每次查找、统计的时间降低到O(1)O(1)O(1)。当数列AAA中的值都比较小使，我们可以直接用一个数组计数(建立一个大小等于值域的数组进行统计和映射，其实就是最简单的Hash)。当数列AAA中的值很大时，...

2020-12-09 10:32:46 63

原创就没有鲲鲲上不了的树题集补题

C. hdu6183维护一个数据结构实现以下操作：0：clear3：break1：在一个坐标（x，y）添加颜色为c的点2：查询（1，y1）到（x，y2）的矩形中颜色的数量对每一个颜色建一个线段树，每个线段树维护纵坐标，更新最小的x查询时，遍历每个颜色的线段树，count数量#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define C

2020-12-09 10:32:08 49

原创哈理工训练赛

A.模拟B.C.D.E.F.G.思路:假设N有X位，那么从1到N异或最大的数值就是是2X−12^X-12X−1(X位全1)，那么从1到N能否保证存在两个数异或后是2X−12^X-12X−1呢，既然N有X位，那么一定存在2X−12^{X-1}2X−1这个数，因为它是最小的有X位的数，观察这个数，假如说X=4，那么2X−12^X-12X−1=15=11112_22， 2X−12^{X-1}2X−1=8=10002_22，1000距离异或变为1111差一个011

2020-12-09 10:31:42 96

原创 Same GCDs 欧拉函数

求∑x=0m−1[gcd(a,m)==gcd(a+x,m)]\sum_{x=0}^{m-1}[gcd(a,m)==gcd(a+x,m)]∑x=0m−1[gcd(a,m)==gcd(a+x,m)]由gcd(a,m)==gcd(a+0,m),gcd(a,m)==gcd(a+m,m)gcd(a,m)==gcd(a+0,m),gcd(a,m)==gcd(a+m,m)gcd(a,m)==gcd(a+0,m),gcd(a,m)==gcd(a+m,m)所以原式:=∑x=1m[gcd(a+x,m)==gcd(a,m.

2020-12-09 10:29:58 196

空空如也

空空如也