1 仰望星空的蚂蚁

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 19w+

【模板】乘法逆元

void exgcd(LL a,LL b,LL &d,LL &x,LL &y) { if(!b) d=a,x=1,y=0; else { exgcd(b,a%b,d,y,x); y-=x*(a/b); }}LL inv(LL u) { LL x,y,d; exgcd(u,mod,d,x,y); return (x%mod+mod)%mod;}

2020-10-21 21:14:07

【题解】Beautiful Bracket Sequence (easy version)

分析:本题妙就妙在没有直接计算每种深度,而是逐层扩展,考虑新增括号的方案贡献。因为假如外面有一层括号,那么所有区间内方案的深度都要加1,这个贡献是可以算的。//Interval DP#include<bits/stdc++.h>#define int long longusing namespace std;const int N=2005;const int mod=998244353;int n,dp[N][N],g[N];char s[N];int kpow.

2020-10-05 19:49:43

【题解】相框

问题 B: 相框时间限制: 1 Sec 内存限制: 256 MB题目描述【问题描述】P大的基础电路实验课是一个无聊至极的课。每次实验,T君总是提前完成,管理员却不让T君离开,T君只能干坐在那儿无所事事。先说说这个实验课,无非就是把几根导线和某些元器件(电阻、电容、电感等)用焊锡焊接起来。为了打发时间,T君每次实验做完后都在焊接一些诡异的东西,这就是他的杰作:T君不满足于焊接奇形怪状的作品,强烈的破坏欲驱使他拆掉这个作品,然后将之焊接成规整的形状。这会儿,T君正要把这个怪物改造成一个环形,当作自

2020-09-25 12:48:34

【题解】bfs难题

A. [USACO18OPEN,Silver]Multiplayer Moo解析:这题挺水的。首先跑一个bfs求连通块,附上对应的连通块标号,大小,颜色(及数字)。对相邻的连通块连边。然后枚举选择的两个颜色,对这两种颜色的连通块再求一次连通块即可。乍一看时间复杂度O(m2cnt)O(m^2cnt)O(m2cnt),其中cnt是连通块数目,m是颜色数目。而cnt,m<=2502cnt,m<=250^2cnt,m<=2502,显然超时。cnt是不能优化的,这是求连通块的时间代价。而枚举

2020-09-17 20:17:08

【题解】火枪打怪

法一.法二.法三.(本人的作死方法,调了一晚上)xj=p−(i−j)2x_j=p-(i-j)^2xj​=p−(i−j)2xj+1=p−(i−j−1)2=p−(i−j)2−1+2(i−j)x_j+1=p-(i-j-1)^2=p-(i-j)^2-1+2(i-j)xj​+1=p−(i−j−1)2=p−(i−j)2−1+2(i−j)xj=xj+1+(1+2i)−2jx_j=x_{j+1}+(1+2i)-2jxj​=xj+1​+(1+2i)−2j推广一下:xj=xj+1+sum−tot∗2jx.

2020-09-06 09:34:13

【题解】倍增两题

前言:本人发现做倍增的题完全是无从下手,所以补了之前两道倍增的题,现来讲讲思路。专题:用倍增优化前缀pre数组(类似于lca)A.城市网络#include<bits/stdc++.h>using namespace std;const int N=1e5+5;//用倍增优化前缀数组(类似于lca)void read(int &x) { int f=1;x=0;char c=getchar(); while(c<'0'||c>'9') {if(c=='-'

2020-08-28 19:34:30

【题解】对称二叉树

数的同构给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。一般情况(树hash):https://blog.csdn.net/dpppbr/article/details/52915576递归判断(用于二叉树):https://www.cnblogs.com/jingjing1234/p/10822040.html回归本题

2020-08-25 21:49:07

【题解】NOIP普及组2019

用了大概一个晚自习来做这四道题,顺便复习一下以前学过的知识。A. 数字游戏签到题。。。#include <iostream>using namespace std;string s;int ans;int main() { cin >> s; for (int i = 0; i < s.size(); i++) if (s[i] == '1') ans++; cout << ans;}

2020-08-24 22:18:03

【总结】欧拉回路

A.原始生物一句话题意:给定一个连通块,求其经过所有边的节点数量最少和(不一定是一笔画,可以多笔划)。于是我们可以统计每个点在路径中出现的次数,累加即可可以这样想:对于节点i的入度为ininin,出度为outoutout,则出现次数为max(in,out)max(in,out)max(in,out).因为数量少的一类边一定先被遍历完,所以最后还要单独构造abs(in−out)abs(in-out)abs(in−out)个点。题目并没有告诉你整个图联通,我们可以推广,分别求出每个连通块的答案,累加即可

2020-08-20 22:18:55

【题解】可爱路径【第四周】

请勿抄袭~#include<bits/stdc++.h>#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize("Ofast")#pragma GCC optimize("inline")#pragma GCC optimize("-fgcse")#pragma GCC optimize("-fgcse-lm")#pragma GCC optimize("-fipa-sra")#pragma GCC

2020-08-19 22:24:56

【题解】道路航线

#include <bits/stdc++.h>using namespace std;const int N = 2.5 * 1e4 + 5;const int M = 5 * 1e4 + 5;struct rec { int x, y, z;} e[M];struct edge { int v, w;};void read(int &x) { int f = 1; x = 0; char c = getchar();

2020-08-18 21:37:03

【模板】拓扑排序

#include<bits/stdc++.h> using namespace std;const int N=205;const int M=20005;void read(int &x) { int f=1;x=0;char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') {x=(x<<1)+(

2020-08-18 15:07:55

【题解】次小生成树/最小度限制生成树

问题描述给定一张NNN个点MMM条边的无向图,求无向图的严格次小生成树。设最小生成树的边权之和为sumsumsum ,严格次小生成树就是指边权之和大于sumsumsum的生成树中最小的一个。引理先建出一棵最小生成树,满足使用的边都是最小的,剩下的边(称为非树边)一定没有树边优。如果我们加入一条非树边,删除最小生成树中的一条边,次小生成树一定是包括在以这种方法建出的树中的。证明:既然次小生成树SSS比某个生成树大,不妨设这个生成树是TTT。TTT一定可以用SSS替换一条边得到(否则说明SSS是MS

2020-08-17 19:49:39

【模板】LCA

#include<bits/stdc++.h>using namespace std;const int N=50010;struct Edge{ int v,w;};int f[N][20],d[N],dist[N];vector<Edge> son[N];int T,n,m,tot,t;queue<int> q;void bfs() { memset(d,0,sizeof(d)); q.push(1);d[1]=1; while(q.s

2020-08-16 20:54:27

【总结】初学数论(筛素数)

埃氏筛用素数筛合数,代码简单,拓展性强。复杂度O(n∗loglogn)O(n*loglogn)O(n∗loglogn),可以看作常数较大的n。运用:对于求[l,r]的素数,可以用[1,sqrt(r)sqrt (r)sqrt(r)]的所有素数来筛区间[l,r],相比直接求[1,r]的线性筛更优,因为线性筛对每个数有且仅能筛一个数,而这个数很有可能不在区间内,是无意义的。void work() { for(int i=2;i<=n;i++) { if(!b[i]) { pri[++cn

2020-08-10 21:09:25

【模板】有向图tarjan

本人只会模板。。。#include<bits/stdc++.h>using namespace std;const int N=10005,M=50005;vector<int> son[N];int dfn[N],low[N],num,s[N],out[N],top,cnt;int scc[N];int sz[N],n,m; void tarjan(int u) { low[u]=dfn[u]=++num,s[++top]=u; for(int i=0;i&

2020-08-09 21:11:43

【模板】最小生成树

#include<bits/stdc++.h>using namespace std;const int maxn=5*1e5+5;struct rec{ int x,y,z;}edge[maxn];bool operator <(rec a,rec b) { return a.z<b.z;}void read(int &x) { int f=1;x=0;char c=getchar(); while(c<'0'||c>'9') {if(c

2020-08-09 18:47:25

【题解】「NOIP2016」蚯蚓

经典的队列优化题,细节贼多,本人抽时间补一下详解。#include<bits/stdc++.h> using namespace std;const int inf=-0x3f3f3f3f;int n,m,q,u,v,t,in[100005],delta;double p;queue<int> a,b,c;void read() { scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);

2020-08-08 20:54:39

【总结】最短路模板+最小路径生成树

Dijkstra#include<bits/stdc++.h>using namespace std;int n,m,st,ed,dis[2505];bool vis[2505];struct edge{ int v,w; edge(){} edge(int V,int W) {v=V,w=W;}};void read(int &x) { int f=1;x=0;char c=getchar(); while(c<'0'||c>'9') {if(c=

2020-07-29 19:52:54

【题解】乌龟跑步(#3397)

一只乌龟由于智商低下,它只会向左或向右走,不过它会遵循主人小h的指令:F(向前走一步),T(掉头)。现在小h给出一串指令,由于小h有高超的计算能力,他可以马上知道乌龟最后走到哪里。为了难倒小h,他的好朋友小c就说,现在让你修改其中n个指令,使得乌龟移动到离起点最远的地方。(修改是指“T”变成“F”,或“F”变成“T”,可以对同一个指令多次修改)。乌龟一开始在0点解析:这道题的错因是没有理解清楚题意,不是做不来,实在是看题不够仔细。。一定要警醒自己!(莫非真的是理解能力不行?)首先,本题有两个操作:向

2020-07-28 22:00:40

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。