moyangxian-CSDN博客

原创算法模板.

算法模板图论最小生成树prim（朴素版）prim（堆优化版）#include<bits/stdc++.h>using namespace std;#define F first#define S second#define IOS typedef pair<int,int> PII;ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)typedef long long ll;const int INF=0x3f3f3f

2020-07-22 16:53:56 390

原创 CDZSC_2022寒假个人训练赛21级(2)

A题解：输出n, 1, 2, 3, 4…即可。#include<bits/stdc++.h>using namespace std;void solve() { int n; scanf("%d", &n); printf("%d", n); for (int i = 2; i <= n; i++) printf(" %d", i - 1); printf("\n");}signed main() { int T; scanf("%d", &am

2022-01-22 19:32:42 608

原创 CDZSC_2022寒假个人训练赛21级(1)

A题意：略题解：将n个数加起来的总和除以n即可。#include<bits/stdc++.h>using namespace std;signed main(){ int n; scanf("%d", &n); int sum = 0; for(int i = 1; i <= n; i++){ int x; scanf("%d", &x); sum += x; }

2022-01-19 16:31:24 790

原创 HTML学习

HTML我的第一个网页基本标签图片标签链接标签我的第一个网页<!DOCTYPE html><html lang="en"><head>   <meta charset="UTF-8"> <me

2021-12-06 21:00:30 360

原创 2020CCPC威海 J - Steins；Game (sg函数、线性基)

题意：n堆石子，每堆石子有黑和白两种颜色，拿黑色堆石子的时候必须拿数量最少的（最少一个），白色没有限制可以任意拿（最少一个）。后手的人可以在游戏开始之前对所有石子堆染色，问后手能赢的染色方案数。题解：首先可以将黑色和白色分成两个游戏，两个游戏的异或和为0即后手胜利。白色游戏：相当于nim游戏黑色游戏：通过sg打表能发现SG值 = 最小堆石子数 − ( ( 最小堆数量 + [ 所有堆石子数相同 ] ) % 2 )能发现sg值只跟最小堆有关系，然后我们可以枚举最小堆。用一个pre维护异或前缀和，suf

2021-08-06 16:59:32 460

原创计算机网络基础

计算机网络基础第一章概述计算机网络的定义及主要功能物理层数据链路层网络层第一章概述计算机网络的定义及主要功能1.计算机网络的两个重要的功能：通信，资源共享2.最早出现的计算机网络：APRANET3.“三网”指电信网络，有线电视网络，计算机网络4.网络协议三要素：语法，语义，时序（同步）5.不同范围的网络类型：WAN：广域网MAN：城域网LAN：局域网PAN：个人区域网6.网络性能指标：速率、带宽、吞吐量、时延、时延带宽积7.分组交换和电路交换的区别分组交换：存储转发方式

2021-07-07 23:28:06 251 1

原创 Linux系统及编程基础

文章目录Linux系统基本操作系统安装，虚拟机软件的使用，虚拟机和主机之间的通信虚拟机与主机之间的通信模式Linux文件系统的特点文件操作命令目录操作命令系统管理，系统，用户，设备，进程用户管理用户管理方法设备管理进程管理网络管理Linux编程ShellShell基本语法特殊字符通配符引号注释符变量表达式，语句函数条件递归read 输入echo 输出Linux下C编程GCCGDBLinux系统基本操作系统安装，虚拟机软件的使用，虚拟机和主机之间的通信虚拟机与主机之间的通信模式1.Bridged(桥接

2021-07-04 18:22:31 264 2

原创洛谷P2482 [SDOI2010]猪国杀

#include<bits/stdc++.h>using namespace std;const int N = 20;vector<char> P;//牌堆int n, m, f;int nxt[N], lst[N];struct Pig { string name;//真实身份 /* 主猪:MP 忠猪:ZP 反猪:FP */ vector<char> p; int hp;//血量 int z;//是否装连弩 int t;//表面身

2021-06-29 22:35:05 166

原创算法模板图论

算法模板图论有向图的强连通分量（Kosaraju）有向图的强连通分量（Kosaraju）测试：hdu 1269const int N = 1e5 + 10;struct Edge{ int to, next;}e1[N], e2[N];int head1[N], tot1, head2[N], tot2;bool vis1[N], vis2[N];int cnt1, cnt2;int st[N];//对原图dfs，点的结束时间从小到大int Belong[N];//每个点属于哪

2021-06-10 01:01:14 88

原创算法模板字符串

#[toc](算法模板字符串)字符串哈希//获取一个字符串的hash值//测试：洛谷P3370const ull P = 13331;//131ull get_hash(string s){ ull res = 1; int len = s.length(); for(int i = 0; i < len - 1; i ++ ) res = res * P + (ull)s[i]; return res;}//测试AcWing841u

2021-06-10 00:57:09 93

原创算法模板数学

矩阵矩阵快速幂测试：洛谷P3390, P1939struct mat{ int a[sz][sz];//注意开long long mat(){memset(a, 0, sizeof(a));} mat operator - (const mat &b)const{ mat res; for(int i = 0; i < sz; i++) for(int j = 0; j < sz; j++)

2021-06-10 00:54:45 70

原创算法模板 xian

算法模板 xian数学矩阵快速幂字符串字符串哈希数学矩阵快速幂测试：洛谷P3390, P1939struct mat{ int a[sz][sz];//注意开long long mat(){memset(a, 0, sizeof(a));} mat operator - (const mat &b)const{ mat res; for(int i = 0; i < sz; i++) for(int j =

2021-06-09 17:58:29 54

原创 2020浙江省赛

2020浙江省赛A - AD 2020 （前缀和）B - Bin Packing Problem(二分，线段树)C - Crossword Validation （字典树）DE - Easy DP Problem（主席树前k大之和）FG - Gliding（最短路）H - Huge Clouds（几何，差分求区间交）I - Invoking the Magic （离散化，并查集）JK - Killing the Brute-force（签到）LA - AD 2020 （前缀和）题意：给出两个日期，问两个

2021-05-24 16:31:27 1217

原创高斯消元

bool dcmp(int x, int y, int k) { if (fabs(a[x][k]) > fabs(a[y][k])) return true; else if (fabs(a[x][k]) < fabs(a[y][k])) return false; else { for (int i = k + 1; i <= n; i++) if (fabs(a[x][i]) < fabs(a[y][i])) return true; return

2021-05-06 12:15:12 63

原创哈夫曼编码压缩文件

#include<algorithm>#include<iostream>#include<cstdlib>#include<cstdio>using namespace std;const long INF=0x7FFFFFFF;int n,m,i,j;struct HuffNode{ unsigned char b; long count; long parent; long lch,rch; char bits[256];}

2021-03-28 10:17:47 831

原创 20排位赛3

20排位赛3ABCDEFGA题意：略题记：略#include<bits/stdc++.h>using namespace std;const int N=110;int a[N];int main(){ cin>>a[0]>>a[1]>>a[2]; sort(a,a+3); cout<<max(0,a[2]-a[1]-a[0]+1)<<endl; return 0;}B题意：

2021-03-19 01:59:40 87

原创 CodeForces - 1324D Pair of Topics（二分或双指针）

题意：略题记：做法一：二分#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=2e5+10;int a[N],b[N],c[N];int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++)

2021-03-10 19:43:14 128

原创 Gym - 102219J Kitchen Plates（暴力或拓扑序列）

题意：略题记：做法一：拓扑排序。五个盘子相当于一个有五个点的有向图，A<B相当于A有一条边指向B。那么建图后做一遍基于BFS的拓扑排序即可。时间复杂度O(V+E)#include<bits/stdc++.h>using namespace std;const int N=10;int head[N],tot;int s[N];vector<int>ans;struct Edge{ int to,next;}e[N];void init(){

2021-03-09 11:40:56 170

原创第十四次试验

#include<iostream>using namespace std;const int N=1010;int g[N][N]={{ 1, 1, 1, 1, 1, 1 },{ 1, 0, 0, 0, 1, 1 },{ 1, 0, 1, 0, 0, 1 },{ 1, 0, 0, 0, 1, 1 },{ 1, 1, 0, 0, 0, 1 },{ 1, 1, 1, 1, 1, 1 }};bool vis[N][N];struct Node{ int x,y;}

2020-12-23 20:12:11 93

原创 2016 CCPC Hangzhou Onsite

2016 CCPC Hangzhou OnsiteA ArcSoft's Office Rearrangement（贪心）B Bomb(Tarjan+缩点)C Car(贪心+卡精度)D Difference(思维+二分)F Four Operations(贪心，模拟)A ArcSoft’s Office Rearrangement（贪心）题意：将n个数分成k个相同的数，一次操作能将两个数合并或将一个数拆分成两个数。求最小操作数题记：求出n个数的总和除k的值s，遍历数组，将x加上a[i]（如果x不为0

2020-12-22 21:09:35 219 1

原创 HDU - 1269 迷宫城堡(判断强连通)

题意：判断一个图是否为强连通图题记：三种做法做法一：暴力，直接dfs每个点判断是否能到达其他n-1个点。#include<iostream>#include<cstring>using namespace std;const int N=1e5+10;struct Edge{ int x,y,next;}edge[N];int head[N],vis[10010];int n,m,cnt;void dfs(int x){ if(cnt==n-1

2020-12-21 20:50:09 137

原创第十三次试验

#include<iostream>#include<vector>#include<queue>#include<cstring>using namespace std;const int N=1e4+10;int g[N][N];int n,m;struct Edge{ int to,next,w;}e[N];int head[N],tot;void init(){ memset(head,-1,sizeof(hea

2020-12-16 20:22:35 62

原创第十二次实验

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int INF=0x3f3f3f3f;const int N=50;struct HTNode{ char data[N]; double w; int fa,l,r;}ht[N];int num[N];struct HCode{ char cd[N]; int

2020-12-09 20:33:10 87

原创数位dp练习

数位dp不要62 HDU - 2089windy数洛谷 P2657 [SCOI2009]不要62 HDU - 2089做法一：#include<bits/stdc++.h>using namespace std;const int N=30;int f[N][N];int a[N],len;int dfs(int pos,int pre,bool limit){ if(!pos) return 1; if(!limit&&~f[pos][pre

2020-12-01 20:54:18 94

原创第十次试验

A(B(D(,G)),C(E,F))#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<cstdlib>using namespace std;const int MaxSize=100;typedef struct Node{ int data; struct Node *l; struct Node

2020-11-25 20:30:20 74

原创第九次试验

#include<iostream>using namespace std;int x;int fun(int n){ if(n==1) return x; return x*fun(n-1);}int main(){ int n; cin>>x>>n; cout<<fun(n)<<endl; return 0;}#include<iostream>

2020-11-18 20:35:28 79

原创第八次试验

#include<iostream>#include<cstdio>#include<cstdlib>using namespace std;char str[100];char mp[100]={"ngzqtcobmuhelkpdawxfyivrsj"};typedef struct snode{ char data; struct snode *next;} LinkStrNode; //声明链串节点类型void StrAssign

2020-11-11 20:01:56 89

原创第七次试验

#include<iostream>#include<cstdlib>#include<string>#include<cmath>#include<cctype>#include<cstdio>using namespace std;#define MaxSize 100typedef char ElemType;typedef struct{ ElemType data[MaxSize]; int front

2020-11-04 20:28:34 104

原创第六次试验

#include <cstdio>#include <cstdlib>#include <iostream>#include <cmath>#define MaxSize 100typedef int ElemType;int n,num=1;typedef struct{ ElemType data[MaxSize]; int top; //栈指针} SqStack; //声明顺序栈类型void InitStack(Sq

2020-10-28 20:36:36 68

原创第五次试验

#include<iostream>#include<cstdio>#include<cstdlib>using namespace std;int n,m;typedef int ElemType;typedef struct LNode{ ElemType data; struct LNode *next;}LinkList;void DispList(LinkList *L,int m){ LinkList *p = L

2020-10-21 20:39:11 9853 1

原创第四次试验

#include<iostream>#include<cstdio>#include<stdlib.h>#include<cstring>#include<string>using namespace std;typedef struct Node{ char data; bool flag; struct Node *next;}Node;string str;void InitList(Node

2020-10-14 20:50:07 81

原创第三次试验

#include<iostream>#include<cstdio>#include<cstdlib>using namespace std;typedef int DataType;typedef struct SqList{ DataType z[100]; DataType data[100]; int length;}SqList;void CreateList(SqList *&L,DataType a[],i

2020-09-27 20:47:32 91

原创第二次试验

#include<bits/stdc++.h>using namespace std;typedef struct student { int num; char name[10]; char sex[10]; int English; int computer; int math; int sum; double average;}Student;typedef struct NODE{ Student data; struct NODE *next;

2020-09-23 20:38:29 116

原创第一次实验

#include <stdio.h>#include <stdlib.h>typedef struct student { int num; char name[10]; char sex[10]; int English; int computer; int math; int sum; double average;}Student;const int N = 100;Student stu[N];int n;void InputStu(Stude

2020-09-16 22:57:59 110

原创 POJ 1416 Shredding Company（DFS）

题意：将num切开然后求和，找到一个小于等于t且最接近t的值，如果得到这个值的方法是唯一的则输出切num的方法，否则输出rejected。如果没有一个方法的数是小于等于t则输出error。题记：dfs去搜索所有切的方法。注意记录切的路径。#include<iostream>#include<queue>#include<cstring>#include<string>#include<algorithm>using namespace

2020-09-08 16:12:06 121

原创 CodeForces - 1392C Omkar and Waterslide（思维）

题意：每次可以选一个区间去加一，最后形成一个非递减序列题记：其实每一个数都只跟它前一个数有关。分成两种情况。时间复杂度当前这个数比前一个数小：答案需要加上前一个数与当前数的差值。当前这个数比前一个大或等于：不需做任何操作。#include<iostream>#include<cstdio>using namespace std;typedef long long ll;const int N=2e5+10;int main(){ int T; c

2020-09-04 17:28:44 193

原创 51Nod - 1094 和为k的连续区间（前缀和）

题意：跟题目一样，求和为k的连续区间。题记：计算前缀和，然后枚举求出答案。#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>using namespace std;typedef long long ll;const int N=1e4+10;//int num[10]={6,2,5,5,4,5,6,3,7,6};ll a[N];int main(

2020-09-04 13:43:52 94

原创计蒜客 - T1853 非常男女（前缀和）

题意：找出男女人数相等的连续子序列长度。题记：将所有的0变成-1，然后直接枚举前缀和数组，找到a[j]-a[i]==0时更新答案。#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>using namespace std;typedef long long ll;const int N=1e5+10;//int num[10]={6,2,5,5,4,5,6

2020-09-04 13:37:59 296 1

原创计蒜客 - T1245 火柴棒等式（枚举）

题意：给出n根火柴，问有多少种拼成不同等式的方式。题记：枚举A和B，然后算出C。最后把火柴数量算一算是否等于n就可以了。#include<iostream>#include<cstdio>using namespace std;typedef long long ll;const int N=1e4+10;int num[10]={6,2,5,5,4,5,6,3,7,6};int getnum(int x){ int res=0; res+=num

2020-09-04 13:30:19 211

原创 UVA - 11971 Polygon（概率）

题意：一根长为n的木条，切k次，切成k+1条小木条，求这些小木条能组成一个多边形的概率。题记：首先反过来思考，k+1条小木条怎样才不能组成一个多边形。当其中有一根木条的长度大于等于其他所有木条的总和时，这些小木条不能形成一个多边形。然后将这根长木条首尾相连形成一个圆。然后变成切k+1次（因为将首尾连起来了，所以要切多一刀）。当这k+1次都砍在同一个半圆上，那么有一根木条的长度必定大于等于n/2。第一刀切在圆上哪个位置都是一样的，所以概率是1，其余k刀砍在同一个半圆的概率为1/2。k+1刀都在同一个半圆上

2020-09-02 11:40:52 108

空空如也

空空如也