1 Barsaker

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 5w+

2020 HDU Multi-University Training Contest 5

6816 Boring Game模拟如图所示的过程,将折叠的纸一层层打开来#include<cstdio>#include<vector>#include<algorithm>using namespace std;const int maxp = 2 * 200 * (1 << 10) + 5;int T, n, k, p[maxp];vector<int>a[maxp];int main(void) { scanf("%d

2020-08-05 15:42:58

HDU - 3472 HS BDC (Dinic算法)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3472判断混合欧拉路径,可以转化为判断混合欧拉回路。欧拉路存在要求度数全部为0,或者仅有2个度数为奇数。若有2个奇数度,则添加一条不定向边将度数变为偶数。然后判断能否通过调整不定向边的方向使得全部度数为0,用dinic算法计算最大流,自己外加一个起点s和终点t,起点s指向所有度数大于0的点(即出度大于入度),让所有度数小于0的点指向t,权值都是设为度数绝对值的一半,如果从s出发的所有边都满流说明构成了欧拉回路

2020-08-02 09:55:12

HDU - 1083 Courses (匈牙利算法)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1083匈牙利算法看起来比较简单,就是后来者匹配点已经被匹配,则取找该点的配对者是否能换点配对,如果能则后来者成功配对,前者则更换了配对点,否则后来者配对失败。因此可以在确保已经配对成功的保持配对成功的状态下,来判断后来者能否成功配对,据此递归。#include<cstdio>#include<cstring>using namespace std;const int maxn =

2020-08-01 11:50:02

2020 HDU Multi-University Training Contest 4

6803 Blow up the Enemy难得一见的比赛水题#include<cstdio>#include<iostream>#include<cmath>using namespace std;const int maxn = 1000 + 5;int T, n, A[maxn], D[maxn];int main(void) { scanf("%d", &T); while (T--){ scanf("%d", &n);

2020-07-30 18:31:29

HDU - 3555 Bomb (数位DP入门)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3555直接算含49的个数,还不用总想着区间#include<cstdio>using namespace std;typedef long long ll;const int LEN = 20;__int64 dp[LEN][10], digit[LEN];void init() { for (int j = 0; j < 10; j++)dp[1][j] = 0;

2020-07-30 08:49:24

HDU - 5721 Palace(最近点对)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5721分析:很显然,先对全部的点搜一遍,这个值能用n-2次,记录下最近的两个点,再搜两次,每次删除其中一个点。思路很容易想到的,主要是怎么操作。#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;const ll INF = 1e12;const int maxn = 1e5

2020-07-29 08:39:55

2020 HDU Multi-University Training Contest 3

6794 Tokitsukaze and Multiple#include<cstdio>#include<map>using namespace std;typedef long long ll;const int maxn = 1e6 + 5;int T, n, p;ll a[maxn], sum[maxn];int main(void) { scanf("%d", &T); while (T--){ scanf("%d%d", &n,

2020-07-29 00:50:41

2020 HDU Multi-University Training Contest 1

6754 Distinct Sub-palindromes找规律 从长度为4开始的串就一样了#include<cstdio>using namespace std;int main(void) { int T, n; scanf("%d", &T); while (T--) { scanf("%d", &n); if (n == 1)printf("26\n"); else if (n == 2)printf("676\n"); else if (

2020-07-25 23:17:13

2020 HDU Multi-University Training Contest 2

6763 Total Eclipse一般思考是,对每个连通块里的全部点减去其中最小点的值,去掉最小点分裂出新的连通块,依次进行,所有减去的值的和为答案。困难的是如何使得连通块分裂。解决办法为逆向构造连通块,在这个过程中最后留下的总是值最大的点,因此可以令点从大到小排序,依次加入图中。对于每个新加入的点x,遍历其所有边(x,y),如果y在x之前加入且x与y不连通,说明y所在连通块受到x影响,且还未把该影响更新。利用并查集将x,y合并,并且让y所在集合的根的父亲更新为x,集合的根也更新为x。这样对于每个点

2020-07-25 21:55:06

C++-----一个类中缺省的6种函数(转载)

#include<iostream>using namespace std; class Test{public: Test() {} //默认构造函数 Test(const Test &t) //默认拷贝构造函数 { a=t.a; p=t.p; } Test& operator = (const Test &t) //赋值操作符重载 { if(this!=&t) { a=t.a; p=

2020-07-18 16:54:12

2019级吉林大学XCPC集训队选拔赛 - 第二轮 补题记录

B题

2020-07-13 14:45:06

HDU 1956 “Sightseeing Tour“ (混合欧拉回路)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1956引用discuss里的题解思路:简单来说就是利用网络流里反向弧的特征来平衡每个点的度,能变向的只有无向边,所以有向边要删除。以下为dinic算法的AC代码(G++)#include<cstdio>#include<cstring>#include<queue>using namespace std;const int inf = 0x3f3f3f3f;

2020-07-13 10:19:27

2019级吉林大学XCPC集训队选拔赛 - 第一轮 补题记录

Problem A题目大意:给出两个整数n,m表示行数和列数,图中’W’表示船只,’.'表示海水,设两个W的坐标为(xi,yi),(xj,yj),若|xi-xj|<=1&&|yi-yj|<=1则船只有联系,或者它们通过有联系的船只间接产生联系,求有联系的船只有多少对。简单来说就是先算出每个八连块的船只数,配对数目则为这些船只里面任取2个。代码如下:#incl...

2020-06-16 16:41:58

JLU 2020 Winter Freshman Round 1 补题记录

B题基本八数码题,BFS+Cantor#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int factory[] = { 1,1,2,6,24,120,720,5040,40320,362880 };const int dir[4][2] = { {-1,0} ,{0,-1},{1,0} ,{0,1}

2020-06-27 23:03:41

习题 7-2 黄金图形(Golygons,ACM/ICPC World Finals 1993,UVa225)

原题链接:https://vjudge.net/problem/UVA-225分类:回溯法备注:注意细节,DFS题意:每条路径不可在同一点重复驻留,路障在你要走的路中,那么这条路是不可以走的,注意vis数组的检测,要留心别把刚刚就走过的点还放到检测列表中,踏踏实实分类讨论。代码如下:#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int dir[4

2020-07-06 00:12:03

例题 7-7 天平难题(Mobile Computing,ACM/ICPC Tokyo 2005,UVa1354)

原题链接:https://vjudge.net/problem/UVA-1354分类:二进制法备注:枚举二叉树,好题根据紫书思路:每次从集合任意选两个节点组成一个新节点。  之前自己试的时候,并没有用什么技巧,但是没做出来,然后看了作者的代码,实在是妙啊。这部分之前的内容讲了子集生成,有增量构造法,位向量法,二进制法。见识了二进制法的妙用,比自己想的快多了。  以后有时间就算能自己写出例题也应该看看lrj的代码,毕竟都是精品,光顾着自己的那点可怜知识,就算写出了题也不一定有多少进步。代码如下:

2020-07-04 14:14:51

例题 7-6 带宽(Bandwidth,UVa 140)

原题链接:https://vjudge.net/problem/UVA-140分类:回溯法备注:最优剪枝在排序的过程中判断目前的最大带宽,如果大于已记录的带宽则回溯,只有排序一轮完成后再判断目前的宽带和已经记录的带宽,若更小则更新排序数组和带宽值,否则直接返回。此外根据紫书思路,还能利用u节点有m个相邻节点没有确定位置,则若m>k也可回溯。如果加上这一剪枝,运行能从30-40(ms)直接变为0(ms)。代码如下:#include<cstdio>#include<io

2020-07-03 19:46:44

例题 7-5 困难的串(Krypton Factor,UVa 129)

原题链接:https://vjudge.net/problem/UVA-129分类:回溯法备注:隐性回溯,字符串代码如下:#include<cstdio>using namespace std;const char a[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";int n, L, cnt;char ans[90];bool over;bool check(int pos) { int len = 1, tot = pos + 1; while (2

2020-07-03 12:09:14

习题 6-11 树重建(Tree Reconstruction,UVa 10410)

原题链接:https://vjudge.net/problem/UVA-10410分类:树备注:加深理解DFS和BFS, 思维1.在BFS序中,与点a相邻的下一个点可能有三种身份:(1)节点a的孩子 (2)节点a的兄弟 (3)节点a的兄弟的孩子2.在DFS序中,与点a相邻的下一个点可能有三种身份:(1)节点a的孩子(2)节点a的后兄弟(3)与节点a无之间关系设bfs(x)为值为x在BFS序列中的的下标,取DFS序列中两相邻节点u,v;若bfs(u)+1=bfs(v)并且v>u,则可将v视为

2020-07-02 16:24:43

习题 6-12 筛子难题(A Dicey Promble,ACM/ICPC World Finals 1999,UVa810)

原题链接:https://vjudge.net/problem/UVA-810分类:图备注:思维,DFS要注意判重,在原图基础上加两个维度:筛子的top和front即可,否则可能陷入死循环。选择使用DFS成功,BFS莫名失败了。代码如下:#include<iostream>#include<cstring>#include<string>#include<vector>#include<queue>using namespace

2020-07-02 14:20:01

查看更多

勋章 我的勋章
  • 签到达人
    签到达人
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。