4443: [Scoi2015]小凸玩矩阵 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 2129 Solved: 1023 [Submit][Status][Discuss] Description 小凸和小方是好朋友，小方给小凸一个N*M（N<=M)的矩阵A,要求小秃从其中选出N个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的N个数中第K大的数字的最小值是多少。 Input 第一行给出三个整数N,M,K 接下来N行，每行M个数字，用来描述这个矩阵 Output 如题 Sample Input 3 4 2 1 ...

题目描述 \text{sideman}sideman 做好了回到 \text{Gliese}Gliese 星球的硬件准备，但是 \text{sideman}sideman 的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有 NN 个顶点和 MM 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。 \text{sideman}sideman 现在想把危险程度降到最小，具体地来说，就是对于若干个询问 (A, B)(A,B)，\text{sideman}sideman 想知道从顶点 AA 航行到顶点 BB 所经过的最危险的边的...

题目链接：[CQOI2018]异或序列 我们将序列前缀异或和处理一下就不难看出，直接莫队维护即可。 但是add和del函数要注意一些细节， add：我们应该先计算贡献，再++，防止k=0 del：我们应该先–，再减去贡献，防止k=0 还需要注意，我们查询[l,r]，但是前缀异或和预处理之后，就变成[l-1,r]了。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long #define lowbit(x) (x&(-x)) using namespace s...

题意翻译 Rick 和他的同事们做出了一种新的带放射性的婴儿食品(???根据图片和原文的确如此…)，与此同时很多坏人正追赶着他们。因此 Rick 想在坏人们捉到他之前把他的遗产留给 Morty。 在宇宙中一共有 nn 个星球标号为 1 \sim n1∼n。Rick 现在身处于标号为 ss 的星球(地球)但是他不知道 Morty 在哪里。 众所周知，Rick 有一个传送枪，他用这把枪可以制造出一个从他所在的星球通往其他星球(也包括自己所在的星球)的单行道路。但是由于他还在用免费版，因此这把枪的使用是有限制的。 默认情况下他不能用这把枪开启任何传送门。在网络上有 qq 个售卖这些传送枪的使用...

2424: [HAOI2010]订货 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1483 Solved: 998 [Submit][Status][Discuss] Description 某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单位产品要付存贮费用m，假定第一月月初的库存量为零，第n月月底的库存量也为零，问如何安排这n个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为S。 Input 第1行：n, m...

题目链接：学姐的逛街计划 描述 doc 最近太忙了, 每天都有课. 这不怕, doc 可以请假不去上课. 偏偏学校又有规定, 任意连续 n 天中, 不得请假超过 k 天. doc 很忧伤, 因为他还要陪学姐去逛街呢. 后来, doc发现, 如果自己哪一天智商更高一些, 陪学姐逛街会得到更多的好感度. 现在 doc 决定做一个实验来验证自己的猜想, 他拜托 小岛 预测出了 自己 未来 3n 天中, 每一天的智商. doc 希望在之后的 3n 天中选出一些日子来陪学姐逛街, 要求在不违反校规的情况下, 陪学姐逛街的日子自己智商的总和最大. 可是, 究竟这个和最大能是多少呢? 格式 输入格...

题目描述 在 2016 年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树，根为 11 ，有以下两种操作： 标记操作：对某个结点打上标记。（在最开始，只有结点 11 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。） 询问操作：询问某个结点最近的一个打了标记的祖先。（这个结点本身也算自己的祖先） 你能帮帮她吗? 输入格式 第一行两个正整数 NN 和 QQ 分别表示节点个数和操作次数。 接下来 N-1N−1 行，每行两个正整数 u,v ,, (1 \leqslant u,v \leqslant n)u,v(1⩽u,v⩽n) 表示 uu 到 vv 有...

题目描述 Farmer John has decided to assemble a panoramic photo of a lineup of his N cows (1 <= N <= 200,000), which, as always, are conveniently numbered from 1…N. Accordingly, he snapped M (1 <= M <= 100,000) photos, each covering a contiguous range of cows: photo i contains cows a_i throug...

3251: 树上三角形 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1282 Solved: 521 [Submit][Status][Discuss] Description 给定一大小为n的有点权树，每次询问一对点(u,v)，问是否能在u到v的简单路径上取三个点权，以这三个权值为边 长构成一个三角形。同时还支持单点修改。 Input 第一行两个整数n、q表示树的点数和操作数 第二行n个整数表示n个点的点权 以下n-1行，每行2个整数a、b，表示a是b的父亲（以1为根的情况下） 以下q行，每行3个整数t、a、b 若t=0，则询问(a,...

3709: [PA2014]Bohater Time Limit: 5 Sec Memory Limit: 128 MBSec Special Judge Submit: 3211 Solved: 1005 [Submit][Status][Discuss] Description 在一款电脑游戏中，你需要打败n只怪物（从1到n编号）。为了打败第i只怪物，你需要消耗d[i]点生命值，但怪物死后会掉落血药，使你恢复a[i]点生命值。任何时候你的生命值都不能降到0（或0以下）。请问是否存在一种打怪顺序，使得你可以打完这n只怪物而不死掉 Input 第一行两个整数n,z(1<=n,z&lt...

题目描述 “我要成为魔法少女！” “那么，以灵魂为代价，你希望得到什么？” “我要将有关魔法和奇迹的一切，封印于卡片之中„„” 在这个愿望被实现以后的世界里，人们享受着魔法卡片（SpellCard，又名符卡）带来的便捷。 现在，不需要立下契约也可以使用魔法了！你还不来试一试？ 比如，我们在魔法百科全书（Encyclopedia of Spells）里用“freeze”作为关键字来查询，会有很多有趣的结果。 例如，我们熟知的Cirno，她的冰冻魔法当然会有对应的 SpellCard 了。 当然，更加令人惊讶的是，居然有冻结时间的魔法，Cirno 的冻青蛙比起这些来真是小巫见大巫了。 这说明之...

幻方构造： 1.若 (K-1) 在第一行但不在最后一列，则将 K 填在最后一行， (K-1) 所在列的右一列； 2.若 (K-1) 在最后一列但不在第一行，则将 K 填在第一列， (K-1) 所在行的上一行； 3.若 (K-1) 在第一行最后一列，则将 K 填在 (K-1) 的正下方； 4.若 (K-1) 既不在第一行，也最后一列，如果 (K-1) 的右上方还未填数，则将 K 填在 (K-1) 的右上方，否则将 L 填在 (K-1) 的正下方。 #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int lon...

Kids in kindergarten enjoy playing a game called Hawk-and-Chicken. But there always exists a big problem: every kid in this game want to play the role of Hawk. So the teacher came up with an idea: Vote. Every child have some nice handkerchiefs, and if he/she think someone is suitable for the role of...

有N个变量X0~XN−1，每个变量的可能取值为0或1。 给定M个算式，每个算式形如 XaopXb=c，其中 a,b 是变量编号，c 是数字0或1，op 是 and，or，xor 三个位运算之一。 求是否存在对每个变量的合法赋值，使所有算式都成立。 输入格式 第一行包含两个整数N和M。 接下来M行，每行包含三个整数a b c，以及一个位运算（AND,OR,XOR中的一个）。 输出格式 输出结果，如果存在，输出“YES”，否则输出“NO” 数据范围 1≤N≤1000, 1≤M≤106 输入样例： 4 4 0 1 1 AND 1 2 1 OR 3 2 0 AND 3 0 0 XOR 输出...