2 c4Lnn

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 11w+

HDU 2768. Cat vs. Dog

链接http://acm.hdu.edu.cn/showproblem.php?pid=2768题意n个观众,每个观众都是一个爱猫的人(即讨厌狗)或一个爱狗的人(即一个讨厌猫)每个观众可以投票决定两件事:一只宠物保留,一只宠物扔掉挑选留下来的宠物,以便最大限度地满足观众思路将每个观众和与其矛盾的观众连线,求二分图最大独立集代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).beg

2020-09-26 22:19:32

POJ 3189. Steady Cow Assignment

链接http://poj.org/problem?id=3189题意将 nnn 头牛分配给 mmm 个谷仓,每个谷仓容量不同,给出每头牛对于 mmm 个谷仓喜欢程度的排名求最小区间(选择的最大喜欢程度的排名 - 最小喜欢程度的排名)思路二分图多重匹配设 l=r=1l=r=1l=r=1如果当前区间匹配成功 l++如果当前区间匹配失败 r++代码#include <cstdio>#include <iostream>#include <algorithm&

2020-09-25 18:23:25

HDU 4687. Boke and Tsukkomi

链接http://acm.hdu.edu.cn/showproblem.php?pid=4687题意思路代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(),(x).end()#define PB push_back#define EB emplace_back#define MP make_pair#define FI first#define SE secon

2020-09-22 23:59:17

2018中国大学生程序设计竞赛 - 网络选拔赛 J. YJJ‘s Salesman

链接http://acm.hdu.edu.cn/showproblem.php?pid=6447题意矩形地图上有n个村庄,从左上出发在 (x,y)(x,y)(x,y) 时,只能移动到 (x+1,y)(x+1,y)(x+1,y),(x,y+1)(x,y+1)(x,y+1),(x+1,y+1)(x+1,y+1)(x+1,y+1)而移动到 (x+1,y+1)(x+1,y+1)(x+1,y+1) ,如果是村庄,则可进行交易,获得收入求能获得的最大收入思路离散化所有点记 dp[i][j]dp[i][

2020-09-18 23:53:34

2018中国大学生程序设计竞赛 - 网络选拔赛 I. Tree and Permutation

链接http://acm.hdu.edu.cn/showproblem.php?pid=6446题意nnn 个点的树形图,按照排列遍历树,求 n!n!n! 个排列的总路径长思路对于每条路径 i→ji\rightarrow ji→j,在所有排列中出现的总次数是 (n−1)∗(n−2)!(n-1)*(n-2)!(n−1)∗(n−2)!DFS 遍历所有边,每条边 u→vu\rightarrow vu→v 存在于 size(v)∗(n−size(v))size(v)*(n-size(v))size(v)

2020-09-18 23:36:32

POJ 2226. Muddy Fields

链接http://poj.org/problem?id=1325题意A,BA,BA,B 两台机器,每台机器各有 mmm 种模式,一开始两台机器都在各自的模式 000现在有 nnn 个任务,可以任意顺序执行,aia_iai​ 表示任务 iii 在 AAA 上执行,需要设置模式为 aia_iai​,bib_ibi​ 表示任务 iii 在 bbb 上执行,需要设置模式为 bib_ibi​每台机器转换一次模式需重启一次,求最小重启次数思路代码#include <cstdio>#incl

2020-09-18 22:25:15

牛客练习赛69 D. 火柴排队

链接题意思路代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(),(x).end()#define PB push_back#define EB emplace_back#define MP make_pair#define FI first#define SE secondusing namespace std;typedef double DB;typed

2020-09-16 17:46:31

HDU 4185. Oil Skimming

链接http://acm.hdu.edu.cn/showproblem.php?pid=4185题意n∗nn*nn∗n 的 010101 矩阵中覆盖最多的 1∗21*21∗2 的只包含 111 的块,每个点只能在一个块中思路判断右和下是否能和当前点构成 1∗21*21∗2 的块,能则在两点间连边建完图后,易发现这是个二分图,跑二分图最大匹配代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x)

2020-09-14 12:00:21

HDU 2819. Swap

链接http://acm.hdu.edu.cn/showproblem.php?pid=2819题意n∗nn*nn∗n 的 010101 矩阵,任意交换两行或两列,可交换无限次,问是否可使矩阵对角线上都为 111,输出交换方案思路代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(),(x).end()#define PB push_back#define EB emp

2020-09-14 11:50:01

HDU 1281. 棋盘游戏

链接http://acm.hdu.edu.cn/showproblem.php?pid=1281题意对一个N*M的棋盘,在格子里放尽量多国际象棋里的“车”,并且使得他们不能互相攻击,但是限制了只有某些格子才可以放某些格子若不放子,就无法保证放尽量多的“车”,这样的格子被称做重要点求有多少个这样的重要点思路先对行列做二分图最大匹配每次删除一条匹配边,重新匹配,判断匹配数是否小于原本匹配数代码#include <bits/stdc++.h>#define SZ(x) (int)

2020-09-12 13:16:26

NC 51274. 导弹防御塔

链接https://ac.nowcoder.com/acm/problem/51274题意思路代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(),(x).end()#define PB push_back#define EB emplace_back#define MP make_pair#define FI first#define SE secondusi

2020-09-10 20:25:57

HDU 1045. Fire Net

链接http://acm.hdu.edu.cn/showproblem.php?pid=1045题意在 n∗nn*nn∗n 的图上有一些围墙,放置一些大炮,大炮能攻击上下左右任何距离的其他大炮,但不能穿过围墙,求最多能放多少个互相不会攻击的大炮思路按行对每个连通块染色,然后按列对每个连通块染色对每个点所在的行连通块与列连通块之前连边跑二分图最大匹配代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define A

2020-09-10 17:06:21

NC 51272. 棋盘覆盖

链接https://ac.nowcoder.com/acm/contest/1062/B题意n∗nn*nn∗n 的棋盘上,有m个点被删除了,求棋盘能被多少个1∗21*21∗2 的多米诺骨牌进行掩盖思路每个点只能被一个骨牌覆盖,所以每个点只能和一个点匹配对于每个点,判断其相邻的点是否合法,合法则连边,表示可以和其匹配建完图跑二分图最大匹配代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x)

2020-09-09 17:12:45

洛谷 P1525. 关押罪犯

链接https://www.luogu.com.cn/problem/P1525题意nnn 个点,mmm 条无向边,将所有点分成两个集合,使两个集合里的边权最大值最小思路二分边权将边权大于 midmidmid 的边加入图中判定是否为二分图代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(),(x).end()#define PB push_back#define

2020-09-09 16:16:24

POJ 2296. Map Labeler

链接http://poj.org/problem?id=2296题意给每个点分配一个正方形,点只能在正方形的上边和下边的中点,每个正方形不能重叠,可以有公共边求正方形的最大边长合法图例思路2 - SAT 问题,每个点在正方形上边和下边两种状态当两点横坐标差大于等于正方形边长或纵坐标差大于等于两倍正方形边长,不用考虑所以只有三种情况纵坐标差大于 000 小于正方形边长纵坐标差大于等于正方形边长小于两倍正方形边长纵坐标差等于 000二分 mmm 建图,判断是否矛盾代码#inc

2020-09-09 01:52:52

HDU 4421. Bit Magic

链接http://acm.hdu.edu.cn/showproblem.php?pid=4421题意已知数组 bbb,求是否存在满足要求的数组 aaa思路按位做2-代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(),(x).end()#define PB push_back#define EB emplace_back#define MP make_pair

2020-09-08 22:47:44

HDU 1816. Get Luffy Out *

链接http://acm.hdu.edu.cn/showproblem.php?pid=1816题意nnn 对钥匙,一对钥匙中用了其中一把另一把就不能用了mmm 扇门,每扇门可以用两把钥匙(选一把即可)解开求按顺序最多能解开多少扇门思路2 - SAT对于 nnn 对钥匙,设 a,ba,ba,b 为一对钥匙选了 aaa 则 bbb 不能选选了 bbb 则 aaa 不能选对于 mmm 扇门,设 a,ba,ba,b 可以解开其中一扇门不选 aaa 则选 bbb不选 bbb 则选 a

2020-09-08 03:57:26

HDU 3715. Go Deeper

链接http://acm.hdu.edu.cn/showproblem.php?pid=3715题意数组 xxx 为 0∼n0\sim n0∼n 的取值,每个数只有 0,10,10,1 两种取值数组 a,ba,ba,b 取值为 0∼n0\sim n0∼n数组 ccc 取值为 0,1,20,1,20,1,2有 mmm 个不等式,xai+xbi≠cix_{a_i}+x_{b_i}\ne c_ixai​​+xbi​​​=ci​给数组 xxx 赋值,问最多能满足前多少个不等式思路2 - SAT

2020-09-05 19:04:00

洛谷 P3275. [SCOI2011]糖果

链接<>题意思路代码#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include <cmath>#include <climits>#include <string>#include <vector>#include <stack>#include <q

2020-09-04 17:30:09

洛谷 P4926. [1007]倍杀测量者

链接https://www.luogu.com.cn/problem/P4926题意有两种约束条件sa≥sb(k−T)s_a\ge s_b(k-T)sa​≥sb​(k−T)sb<sa(k+T)s_b< s_a(k+T)sb​<sa​(k+T)现在有 sss 个条件,ttt 个已知点,使 TTT 尽可能大来满足所有条件思路o=1o=1o=1,sa≥sb(k−T)→log⁡(sa)≥log⁡(sb)+log⁡(k−T)s_a\ge s_b(k-T) \right

2020-09-03 17:06:18

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 阅读者勋章Lv1
    阅读者勋章Lv1
    授予在CSDN APP累计阅读博文达到3天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。