自定义博客皮肤VIP专享

*博客头图:

格式为PNG、JPG,宽度*高度大于1920*100像素,不超过2MB,主视觉建议放在右侧,请参照线上博客头图

请上传大于1920*100像素的图片!

博客底图:

图片格式为PNG、JPG,不超过1MB,可上下左右平铺至整个背景

栏目图:

图片格式为PNG、JPG,图片宽度*高度为300*38像素,不超过0.5MB

主标题颜色:

RGB颜色,例如:#AFAFAF

Hover:

RGB颜色,例如:#AFAFAF

副标题颜色:

RGB颜色,例如:#AFAFAF

自定义博客皮肤

-+
  • 博客(111)
  • 收藏
  • 关注

原创 双哈希

就是构造两个哈希函数,然后将结果记为pair存map,能够进一步减少冲突率例题:Birthday Cake题意给你n个串,问有几对串可以拼成形如AA串。思路先对所有串跑一个哈希,然后遍历所有串,如果该串是ABA型那么就去找B的个数,自然溢出法还差一点,双哈希就过了。ac代码#include<bits/stdc++.h>using namespace std;#define endl '\n'#define ll long long#define ull un

2021-05-16 16:12:53 1393 3

原创 异或相加

求解一对异或值的思路:异或就相当于每一位相加然后每一位对2取模的结果比如3^5=(011)^(101)=(112)->(110)=6那么要求3(011),5(101),7(111)三个分别异或求和就是3^5=(1 1 2) -> (1 1 0)5^7=(2 1 2) -> (0 1 0)3^7=(1 2 2) - > (1 0 0)所以异或求和等于(1 1 0) + (0 1 0) + (1 0 0) = 6 + 2 + 4 = 12其实还有一个思路,

2021-05-16 15:39:32 1812

原创 牛客普及组D-迷阵

题目链接:点这里~题目大意n*n的矩阵,每个位置有属性wij,精神混乱时间是从(1,1)到(n,n)走过路径中属性的最大值-最小值,问精神混乱时间最小值是多少。思路二分。很暴力的二分。首先二分那个差值,然后暴力枚举其中的最小值i,那么路径中最大值也就是i+mid,从(1,1)开始走dfs,属性在最小值到最大值这个区间才能走,然后最后看看能不能走到(n,n)即可,这里既可以是bfs又可以是dfs。ac代码#include<bits/stdc++.h>using name

2021-05-03 11:56:44 190

原创 zone 2021 C - MAD TEAM

题目链接:点这里~题目大意n哥队员每个队员有5个能力值,现在需要挑出3个队员,m1,m2,m3,m4,m5分别是每个能力值在这3个队员中的最大值,s是五个最大值的最小值。求挑选队员,使得s最大。3≤N≤3000思路最小值最大,那么肯定要考虑二分了,二分的关键在于怎么写这个check函数。求的是五个最大能力值中的最小值最大,那么这五个最大能力值肯定都得大于mid。因为只有五种能力,所以可以用五位的二进制记录状态,表示当前能力值是否>=mid,并标记该状态,表示存在该状态,然后枚举三个

2021-05-01 22:57:00 123

原创 zone2021 E-Sneaking

题目链接:点这里~题目大意求从点(1,1)走到点(r,c)的最少花费。操作是向左走花费a[x-1][y],向右走花费a[x][y],向下走花费b[x][y],向上走,花费是向上走的步数+1。思路比赛的时候先是从(1,1)开始跑dfs但是肯定T呀,然后是从(1,1)开始跑bfs但还是T了4个点,最后居然是跑一个优先队列,dist表示从(1,1)走到本地的最小花费,每次优先队列弹出dist最小的更新其他点,跑到终点(r,c)就可以跳出。ac代码#include<bits/st

2021-05-01 22:21:30 142

原创 C 涂墙

题目链接:2021年广东工业大学第十五届文远知行杯程序设计竞赛(同步赛)C题目大意问你能否找到5个数使得这五个数的完全平方和等于n? 1<=n<=1e6思路有返回值的搜索。层数大于5直接返回false,下一个值 t*t找大于n的最小完全平方数。ac代码#include<bits/stdc++.h>using namespace std;mt19937_64 rng(time(0));#define io cin.tie(0);ios::sync_wit

2021-03-29 19:14:16 161

原创 E 捡贝壳

题目链接:2021年广东工业大学第十五届文远知行杯程序设计竞赛(同步赛)E题目大意长度为n的数组a,q次询问,每次询问包含l,r,x。就是问区间[l,r]内x倍数的个数。思路可以将每个值的位置存vector,然后询问的时候倍增思想,从x开始,2x,3x,往上找,然后判断这些数的位置是不是在区间内即可。ac代码#include<bits/stdc++.h>using namespace std;mt19937_64 rng(time(0));#define io c

2021-03-29 11:44:43 135

原创 B找山坡

题目链接:2021年广东工业大学第十五届文远知行杯程序设计竞赛(同步赛)B题目大意大小为n的数组a,存在一个区间,左右边界值相等,区间内所有数都大于等于边界值,问这样的区间右端点和左端点之差的最大值。 1<=-n<=1e6, 1<=ai<=1e9思路可以将一个值存在的位置都存vector,然后遍历这个vector,相邻位置区间最小值大于等于这个值的话,两个区间可以合并,然后取区间最大值即可,这里直接用线段树。不过由于数值比较大1e9,可以先进行离散化处理。ac代码

2021-03-29 11:26:23 137

原创 M型字符串

题目链接:点这里~题目大意给你一个字符串s,问你有多少个前缀si满足si是由两个一摸一样的且是回文串拼接成的,这两个串可以是首尾共享一个字符。字符串长2e5。思路只有一组样例,长度也才2e5,可以直接顺着跑一边哈希,倒着跑一边哈希,然后直接枚举长度,分两种情况判断即可。ac代码#include<bits/stdc++.h>using namespace std;mt19937_64 rng(time(0));#define io cin.tie(0);ios::s

2021-03-29 11:14:05 506

原创 D 动态序列

题目链接:2021年广东工业大学第十五届文远知行杯程序设计竞赛(同步赛)D题目大意n个数q次询问,每次询问分五种,op=1表示序列中所有数乘k,op=2表示序列中所有数加上k,op=3表示序列头部增加一个整数k,op=4表示序列尾部增加一个整数k,op=5表示输出序列第k个位置的数,结果对qe9+7取模。思路就是线段树先乘后加,最后输出区间和,不过这里的区间是单点。可以用l表示区间左端点,r表示区间右端点。先跑一边询问,用双向队列方便首尾加数,看最后序列一共的个数len用于建树,然后更新查询

2021-03-29 11:06:41 167

原创 2021年度训练联盟热身训练赛第四场 Connect3

题目链接:训练联盟4 B题目大意有一个4*4的棋盘,可以看成他是竖着的,下棋的时候其实是从下到上堆上去的,也就是说要想下到(3,1)位置,前提是(2,1)和(1,1)已经有棋子填着,所以说显然,刚开始下棋,只能在第一行下,也就是说(1,1),(1,2),(1,3),(1,4)。如果说场上出现同一行或者同一列挥着对角线上相邻的三个棋子同色,则结束游戏,那中颜色的玩家获胜。然后给你一个x表示黑棋先下的位置是(1,x),然后是a,b,表示白棋最后下的位置,问当白棋下最后一步赢了时,最后棋盘上棋子的所有可能

2021-03-28 21:00:25 80 1

原创 牛客练习赛79 回文字D

题目链接:牛客练习赛79 D题目大意定义一个D型回文串S:S长度小于D称之为D型回文,S长度大于等于D,且任意长度为D的子串都是回文称之为D型回文。问你一个字符串S最少能分成几个连续的子串,都是D型回文?思路其实就是将连续的D型回文拼到一起,看最后有几个D型回文团,比如[1,2,3,4,5,6](下标),如果[1 2]回文,[2 3]回文,[3 4]不回文,[4 5]回文,[5 6]回文,那么前两个和后两个可以拼到一起,就是[1 2 3], [4 5 6]这几个D型回文串。判断回文就

2021-03-27 13:57:30 92

原创 Codeforces Round #710 (Div. 3) 解题报告

题目链接:https://codeforces.com/contest/1506A. Strange Table题目大意给你n,m表示矩阵的长宽,有两种填数方法,一种是一列一列填数,从上到下从左到右;一种是一行一行填数,从左到右从上到下;数字从1开始累加1。然后给你一个k,在按列填数的矩阵中找到他的位置,输出当前位置在按行填数的矩阵中填的数值。思路按列填数,那么c1=k/n表示之前有几列,c2=k%n表示处在第几行,如果k%n==0那么代表在第c1列最后一行,否则就在c1+1列c2行。按

2021-03-26 11:44:42 135 1

原创 Hanjo

题目链接:abc_196d题目大意一个房间大小是h*w,有两种板砖,a块1*1的,b块2*1的。用完所有板砖可以铺满整个房间,问你有几种铺的方案。h*w<=16思路看到16,就可以二进制记录状态了嘛,然后二维转一维进行搜索,5(101)表示1,3位置已经砖覆盖,具体看代码。ac代码#include<bits/stdc++.h>using namespace std;mt19937_64 rng(time(0));#define io cin.tie(0);i

2021-03-22 21:43:59 240

原创 sosdp(高维前缀和)

思想sosdp跟状压差不多,以5(101)为例,状压记录的是(100, 1)这两个状态,而sosdp记录的是(101, 100, 1, 0)这四个状态,也可以说是他的子集。即sosdp[mask]存的是 所有的a[i],其中i&mask == i或者i|mask == mask。实现方法//dp[j]记录子集的和for(int i = 0; i < n; i ++){ for(int j = 0; j < (1 << n); j ++){

2021-03-19 16:56:20 734 2

原创 Digits Paradise in Hexadecimal (数位dp)

题目链接:abc194_5题目大意给你一个长度2e5的16进制表示的数字串S,问你从1到S的这些数中(16进制表示),数字表示正好出现k种数的个数。比如12321,她就有3种数。思路数位dp,不过要考虑前导零。他要k种数,可以用state记录状态,比如5(101)就表示他的状态是取了1,3,有2种数。然后呢dp数组中除了要有下标pos,上界限制limit,前导零led外,还要引入一个cnt,表示该状态的种数,因为返回dp数组的前提是dp数组已经修改过,并且没有上界限制了,也就是说,后面可以随

2021-03-14 19:29:23 168

原创 ac自动机模板及例题

结构体及初始化struct node{ int next[30]; int idx, fail, cnt; //idx表示输入的第几个字符串的终止位置,fail是失配指针,cnt存该字符串出现的次数 void clear(){ //清空 memset(next, 0, sizeof(next)); idx = 0, fail = -1, cnt = 0; }}t[maxn];int tot; //指针int cnt[maxn].

2021-03-13 22:33:57 199

原创 牛数(ac自动机+数位dp)

题目链接:牛客IOI周赛23-提高组B题目大意给你n个数字串,定义牛数x,n个数字串都不是x的子串。然后给你一个长度为2000的数字s,问你[1, s]之间牛数有多少个。思路多个模式串匹配主串,就自然而然地会想到ac自动机了,然后问你[1,s]之间满足条件的数的个数,那么就是数位dp了,不过这里的数位dp要在Trie树上跑,还要注意判断前导零。ac代码#include<bits/stdc++.h>using namespace std;#define io cin.

2021-03-13 18:56:33 365

原创 CCA的期望(数学期望+Floyd)

题目链接:牛客练习赛74 E题目大意n个点m条边,每条边都有权值 的无向图,k次操作,每次操作是选择两个不同点,然后将这两个点之间的最短路上的所有点都染成黑色,起始点的颜色是ai,黑或者白,问你k次操作后黑色点个数的期望(mod 1023694381)。思路求黑色点个数的期望,可以转化成每个点可以染成黑色的概率之和。选点一共有cnt = n * (n - 1) / 2种情况,该点kk可以染成黑色的情况数就是能够经过该点的最短路的个数,这个最短路可以直接用Floyd预处理出来,判断如果di

2021-03-12 15:09:23 104

原创 D. Let‘s Go Hiking

题目链接:Codeforces Round #706 (Div. 2)题目大意A,B两个人走棋,给一个序列n个数ai,刚开始两个人随便选一个位置idxA,idxB。然后对于A来说,A是一直在往数值减小的方向走一格直到不能继续走或者撞到B。B是一直在往数值增加的方向走一个直到不能继续走或者撞到A,不能继续走的人输。A先手,问A能不能赢。思路可以把这个序列看成一座座山,有好几个山峰(山峰就是左右两边数值都比当前的小),开始只能在山峰,因为山峰有两个方向好走,如果不选山峰的话,B会把A的路堵死,A

2021-03-11 17:40:51 238 1

原创 2020icpc上海 D-Walker(二分)

题目链接:https://ac.nowcoder.com/acm/contest/9925/D题目大意有一条0到n的数轴,数轴上有两个点位置分别是p1, p2,可以左右移动,速度分别是v1, v2,求两个点行动轨迹覆盖整个数轴的最短时间。思路大体上三种情况。第一是两人交叉行走,左边的往右跑跑到底,右边的往左跑跑到底,取较大的时间作为覆盖总时间。第二是一个人走完全程,取较小的时间作为覆盖总时间。第三就是将数轴一分为二,左边的覆盖完左区间,右边的覆盖完右区间,取较大值作为覆盖总时间。

2021-03-05 11:45:15 324

原创 多彩的树(状压dp + 数学)

题目链接:https://ac.nowcoder.com/acm/problem/17061题目大意n个点,n-1条边的树,每个节点都有颜色,一共有k种颜色,表示颜色有i种的路径数,求解1<=k<=10, 1<=n<=5e4思路颜色数量少,可以上状压,表示选中的颜色,比如5(101)表示当前选的颜色1,3。然后按照这些颜色跑树上的连通块,当前连通块大小是cnt,那么可以形成的路径数是cnt(单点)+(两个点)但是呢比如5(101)包含了4(100),1(001

2021-03-04 22:37:48 247 1

原创 温澈滢的狗狗(二分+尺取)

题目链接:https://ac.nowcoder.com/acm/contest/9984/D题目大意n只狗狗颜色是ai,颜色不同的狗狗之间有亲密关系,亲密度是下标差。将所有亲密关系按照先亲密度,后第一只狗狗编号,后第二支狗狗编号排序,求第k个亲密关系的两只狗狗的编号。(1<=1e5<=n,1<=ai<=n,1<=k<=n*(n-1)/2)思路二分第k对关系的亲密度,cal(x)表示亲密度小于等于x的亲密关系数,反着求,就是下标差小于等于x的所有关系数 -

2021-03-02 17:59:39 69

原创 Coprime Subsequences(数论gcd)

题目链接:https://ac.nowcoder.com/acm/problem/112055题目大意给你n个正整数,求gcd=1的子序列的个数(mod 1e9+7)思路gcd = i的序列是由一些i的倍数的数构成的,假设a[i]表示给的数中i的倍数的个数,那么这些数一共有(2^a[i] - 1)个组合,但是这些组合并不一定全都满足gcd = i,还要筛去gcd = i*2, i*3....这么多,剩下的才是满足条件的数量。而gcd = i*2 的组合一共有(2^a[i*2] - 1)这么多

2021-03-01 21:09:55 192

原创 动态最小生成树(线段树维护)

题目链接:点这里~题目大意有n个点m条边的图,q次询问,op=1时,修改第x条边。op=2时,询问使用[l,r]范围内的边构成的最小生成树权值。1<=n<=200,1<=m<=3e4思路线段树维护的是区间内构成最小生成树有效边的下标集合s,其中s[0]表示该集合的大小,向上合并的过程类似于归并排序,使得该集合一直保持升序,然后使用kruskal求最小生成树需要的边,最后完成合并。区间查询的时候只需要在线段树上找到这个区间,然后并给ans数组,然后首先看ans[

2021-02-27 23:26:48 462

原创 矩阵消除游戏(二进制枚举)

题目链接:https://ac.nowcoder.com/acm/problem/200190题目大意n*m的矩阵,牛妹每次操作可以消去一行或者消去一列,获得该行/列矩阵的分数,顺便清零,最多k次操作问你可以获得最高分数是多少。1<=n,m<=15;1<=ai<=1e6;1<=k<=n*m思路n和m给的范围很小,可以对行进行二进制枚举。如5(101)表示消去第1行和第3行,然后还剩k-2次操作,那么对剩下每列总和排个序,取前k-2大的数求和,更新最大值

2021-02-27 22:46:44 1146 2

原创 牛客训练营G 机器人(状压dp||记忆化搜索)

题目链接:点这里~题目大意n个机器人,每个机器人会读入一个x,并返回ax+b。现在有一个x,想让你合理安排机器人顺序,使得最终返回得到的x尽可能大,输出最大值。(1<=n,x,ai,bi<=20)思路给的范围很小才20,那么就可以考虑到状压dp。dp[i][t]表示第i次循环在状态t的情况下出的最大值。t在二进制状态下1的位置表示该位置的机器人已经取过,比如5(101)表示1和3位置的机器人已经使用过。所以第i次循环中就枚举状态t中0的位置j,然后使用该机器人j,那么使用过机

2021-02-26 22:57:54 88

原创 九峰与子序列(字符串哈希+dp)

题目链接:点这里~题目大意n个字符串,一个主串s,问多少个子序列串能够拼接成主串s?n<=40, 1<=|s|<=5e6思路这个dp有01背包的思想,dp[i][j]表示前i个字符串能够拼接成s的前j个字符的个数,与01背包不同的就是用到了字符串哈希判断是否相等。tmp是字符串的哈希值,len是字符串的长度,如果tmp等于主串s的子串get(j - len + 1, j)的哈希值,说明可以放最后组成s的前j个字符,那么dp[i][j]+=dp[i-1][j-le

2021-02-20 23:04:01 171 1

原创 武辰延的字符串(二分+字符串哈希)

题目链接:点这里~题目大意给你两个字符串s,t,表示字符串s的长度为i的前缀,同理。问满足的{i, j}有多少种组合。1<=|s|,|t|<=1e5思路s1,s2是模式串,t是主串。暴力枚举s1,二分长度查找s2,字符串比较用哈希。获取子串的Hash:has=((hash[r]-hash[l-1]*p^(r-l+1))%mod+mod)%mod;(如果需反复求解子串hash,则对p的次方进行预处理效果更佳)ac代码#include<bits/stdc++.h&

2021-02-20 13:08:28 218 1

原创 2021牛客寒假算法基础集训营2 E-牛牛与跷跷板(尺取+bfs)

题目链接:点这里~题目大意二维平面上有n块跷跷板,每块跷跷板都有三个值:纵坐标,横坐标左右端点,,牛牛可以从一块跷跷板走到另一块跷跷板当且仅当两块跷跷板有公共边(也就是公共点不算),然后牛牛想从第1块跷跷板走到第n块跷跷板,问走的最少步数。思路问最短路径可以直接bfs,但就是建边较麻烦。首先建1e5个vector,第i个vector存纵坐标为i的跷跷板,每个跷跷板有三个属性:编号和左右端点。同一层只需看左边跷跷板的右端点跟右边跷跷板左端点是否想等即可建边,否则就看第i层跟第i+1层,这部

2021-02-08 21:14:53 229

原创 2021牛客寒假算法基础集训营3 B-内卷 (尺取)

题目链接:点这里~题目大意n个同学考试,需要去给每位同学评定等级,一共有五个等级,但是对于每个同学来说,每个等级分别对应五个不同考试分数:ai, bi, ci, di, ei现在有要求,评定A的同学数量不能超过k,问最终考试成绩最大值和最小值的差值最小是多少?思路每个分数对应一个同学id、一个评定等级,把这些n*5个数据按照分数从小到大排序,使用双指针(尺取法)计算答案需要满足的条件是选的分数能够对应n个同学,评A等级的数量不超过k,所以能不选A就尽量不选。如果说该区间里面某个同

2021-02-08 20:19:23 135 1

原创 AtCoder Beginner Contest 191 解题报告

题目链接:点这里~比赛心得:遇到几何不要慌,试试看暴力行不行=。 =A - Vanishing Pitch题目大意v表示小球速度, t s 表示一个时间区间,d表示球距离棒球手的距离在小球匀速飞行,在[t,s]时间区间内会消失,问棒球手最后能不能击中棒球思路求出小球飞到棒球手所花时间d/v,看是否在那个时间段就行如果怕精度问题可以将时间区间变成距离区间[vt, vs],然后看d是否在区间内就好ac代码#include<bits/stdc++.h>us.

2021-02-06 23:09:57 1789 8

原创 线段树 模板

区间查询最值,区间和#include<bits/stdc++.h>using namespace std;#define io cin.tie(0);ios::sync_with_stdio(false);#define debug(x) cout<<#x<<"="<<x<<endl#define lowbit(x) x&(-x)#define pii pair<int,int>#define mk make_

2021-02-05 22:35:05 161

原创 2021牛客寒假算法基础集训营3 E-买礼物(线段树区间最大)

题目链接:点这里~题目大意n个柜子,每个柜子礼物编号是,q次询问。1 x,表示撤走x柜子里面的礼物。2 ,表示询问区间 [xi,yi]是否有两个相同编号的礼物。对于每次询问输出0/1。思路一看就是数据结构题,但没想到也是个思维题。 对于每个柜子i,pre[i]表示在i之前礼物编号跟ai一样的最近柜子的下标,pos[i]表示在i之后礼物编号跟ai一样的最近柜子的下标。 对pre[i]构建线段树,那么询问的时候只需要查询区间最大值,如果这个区间最大值>=,说明区间内有一个礼...

2021-02-05 22:21:10 159

原创 欧拉降幂 模板

欧拉降幂用来求解 a^b % mod问题求解方法 :a^b%modif(b > mod) return a ^ (b % phi[mod]+ phi[mod]) % mod;else return a ^ (b % phi[mod]) % mod;//phi(欧拉函数,小于n的与其互质的个数)所以说要用到欧拉函数和快速幂。快速幂ll _pow(ll a, ll b, ll c){ ll ans = 1; while(b){ if(b &am

2021-02-03 22:54:56 186

原创 2021牛客寒假算法基础集训营2 I-牛牛的“质因数”

题目链接:点这里~题目大意F(x)表示将x做质因数分解后得到的数字从小到大升序排列,然后将其“拼接”成一个大整数。例如F(12)=223 求%(1e9+7) 1<=n<=4e6思路训练赛有打表的,有dfs的,我这里是bfs广搜,深度最大是7,不会超时 用线性筛筛出n内所有质因子,然后是字符串拼接,取模求和ac代码#include<bits/stdc++.h>using namespace std;#define ll long long#define

2021-02-03 22:37:46 174

原创 F-牛牛与交换排序(思维、双向队列)

题目链接:点这里~题目大意给你一个长度为n的全排列,你可以选择长度为k的区间,然后对这个区间进行翻转 翻转操作可以无数次执行,但是每次翻转长度固定,而且翻转区间左端点是不递减的,即 问能否将其变成1到n的升序?如果可,输出任意一个k。思路翻转就相当于是将归位,因为长度固定,翻转区间左端点不递减,所以如果说这次不归位,那么下次就再也没机会了,因为属于你的位置再也见不到了。 那个就找到第一个a[i]!=i的位置,找到i的家,记为pos,那么再找到a[i]==pos的位置,找到走失的i的位置,

2021-02-03 22:25:34 263

原创 2021牛客寒假算法基础集训营2 G-牛牛与比赛颁奖(差分)

题目链接:点这里~题目大意n支队伍,m道题目,每道题目过题队伍编号刚好是连续的 m行包含两个数ai, bi,表示区间[ai, bi]这些队伍都过了第i题 将选手按照过题量降序排序,第名是金牌线的过题量,第名是银牌线的过题量,第名是铜牌线的过题量 问获得金银铜牌的队伍分别有几只 1≤n≤109,0≤m≤105 思路显然是区间修改,但是队伍数量1e9,线段树开不下,树状数组也开不下,那么就用map维护差分数组。 然后模拟前缀和操作,g数组存放过题量是i的队伍的数量 然后for循

2021-02-03 21:40:58 179 2

原创 D-点一成零(并查集)

题目链接:点这里~题目大意牛牛拿到了一个n*n的方阵,每个格子上面有一个数字:0或1,行和列的编号都是从0到n-1 现在牛牛每次操作可以点击一个写着1的格子,将这个格子所在的1连通块全部变成0。上下左右两个方格是连通的,公用一条边。 k次询问,每次询问给出x,y,将(x,y)方格变成1,牛牛想知道,每次“将某个格子修改成1”之后,“把全部格子的1都变成0”的方案数量。 范围:1<= n <= 500, 1 <= k <= 1e5思路变0为1,就相当于要将连通块合并

2021-02-02 19:51:20 183

原创 2021牛客寒假算法基础集训营1 C-红和蓝(二分图染色)

题目链接:点这里~题目大意你拿到了一棵树,请你给每个顶点染成红色或蓝色。 要求:每个红点周围有且仅有一个红点,每个蓝点周围有且仅有一个蓝点。 最后输出每个点的颜色,R/B,如果不可以输出-1 范围1≤n≤100000思路红a1边上只有一个红a2,那么红a2边上也只有一个红a1,两者可以绑定到成一个点,蓝点同理,所以点数一定是偶数。 那么问题就转换成二分图染色,只有两种颜色,相邻的颜色不同。那么可以从叶节点往上绑定,因为每个叶节点只有一个父亲,如果这个父亲已经绑定过了,那么就不存在这样的

2021-02-02 13:51:27 1549 1

空空如也

空空如也

TA创建的收藏夹 TA关注的收藏夹

TA关注的人

提示
确定要删除当前文章?
取消 删除