cogs专题

【COGS】256 [POI2001] 金矿线段树

传送门：【COGS】256 [POI2001] 金矿题目分析：将每个点作为一个矩阵的右下角添加这个矩阵的下边以及上边，这样本题转化成了区间加减以及求区间最大的问题。代码如下： #include <cstdio>#include <vector>#include <cstring>#include <algorithm>using namespace std

【COGS】421 [SDOI2009] HH的项链树状数组

传送门：【COGS】421 [SDOI2009] HH的项链题目分析：将区间以右端点为关键字降序排序，然后从左到右依次遍历每个数并插入到树状数组中，如果遍历到一个数的时候在他的前面已经有一个相同的数时，将之前位置上的数从树状数组中删除。然后我们每处理完一个位置上的数后，看这个位置上是否有右端点，如果有则做一次求和，这个右端点属于的区间【L，R】的值即sum(R)-sum(L-1)。

【COGS】577 蝗灾 cdq分治

传送门：【COGS】577 蝗灾题目分析：cdq分治入门题= =。。。。用差分思想将矩阵分成四块来计算。。排序一维，另一维用树状数组解决。代码如下： #include <cstdio>#include <vector>#include <cstring>#include <algorithm>using namespace std ;#define REP(

COGS水题赛总结

既然水题是水题赛，学到的东西就主要是来自代码风格上的了。 ①复制数组要用memcpy，循环是较慢的。 ②跳马那道题我竟然还判断了一下其是否会越界，但实际上，越界是不可能发生的，以后这种边界情况我必须要仔细推敲才好。 ③最后一道题我还开了两个Bool数组来判断某个点是否是水及是否经过过，实际上这两个是完全可以合并的。代码：分组： #include<iostream> usin

（cogs 613 火车站饭店）树形DP

题面【题目描述】政府邀请了你在火车站开饭店，但不允许同时在两个相连的火车站开。任意两个火车站有且只有一条路径，每个火车站最多有 50 个和它相连接的火车站。告诉你每个火车站的利润，问你可以获得的最大利润为多少？例如下图是火车站网络：最佳投资方案是 1 ， 2 ， 5 ， 6 这 4 个火车站开饭店可以获得的利润为 90. 【输入格式】第一行输入整数 N(<=10000

COGS 2082 Asm.Def谈笑风生

【题目描述】 “人呐都不知道，自己不可以预料，直升机刚一出圣地亚哥就把我丢到你们船上，说中央已经决定了，让我来帮忙监听无线电信号……” 美国海军“无蛤”号电子测量船的船长，斯科特·华莱士继续把玩着手中的鸭嘴笔，“咱们就在你要监听的那个人工智能舰队眼皮底下，你怎么知道这么作死没问题？” “管它呢，我告诉你一点人生的经验，有事就坐那个撤，”Asm.Def瞟了一眼窗外为“无

Cogs 1298.通讯问题

1298.通讯问题 ★ 输入文件：jdltt.in 输出文件：jdltt.out 简单对比时间限制：1 s 内存限制：128 MB 【题目描述】一个篮球队有n个篮球队员，每个队员都有联系方式（如电话、电子邮件等）。但并不是每个队员的联系方式都公开，每个队员的联系方式只有一部分队员知道。问队员可以分成多少个小组，小组成员之间可以相互通知（包括一个队员一个组，表示自己通知自己）。【输

Cogs 750. 栅格网络(对偶图)

栅格网络流 ★★☆ 输入文件：flowa.in 输出文件：flowa.out 简单对比时间限制：1 s 内存限制：128 MB 【问题描述】 Bob 觉得一般图的最大流问题太难了，他不知道如何解决，于是他想尝试一个简单点的：栅格网络中的最大流问题，这个虽说简单了一点，但对 Bob 来说依旧太难，现在他有个麻烦需要你帮忙：给你一个 N*M 的栅格（如下所示），栅格中的边表示可以流水的管道

Cogs 1708. 斐波那契平方和(矩阵乘法)

斐波那契平方和 ★★☆ 输入文件：fibsqr.in 输出文件：fibsqr.out 简单对比时间限制：0.5 s 内存限制：128 MB 【题目描述】 ,对 1000000007 取模。F0=0，F1=1，F2=1 【输入格式】一行一个整数 N 【输出格式】一行一个整数 Ans 【样例输入】 4 【样例输出】 15 【数据范围】 1≤ N ≤1015 /

深海机器人（cogs 742）

«问题描述：深海资源考察探险队的潜艇将到达深海的海底进行科学考察。潜艇内有多个深海机器人。潜艇到达深海海底后，深海机器人将离开潜艇向预定目标移动。深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人完成采集。每条预定路径上的生物标本的价值是已知的，而且生物标本只能被采集一次。本题限定深海机器人只能从其出发位置沿着向北或向东的方向移动，而且多个深海机器人可以在同一时间

COGS 2189 帕秋莉的超级多项式

放模板啦！以后打比赛的时候直接复制过来。说句实话vector的效率真的不怎么样，但是似乎也还行，最主要是……写得比较爽。 #include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <cmath>using namespace std;typedef long long

COGS 2085 Asm.Def的一秒

【题目描述】 “你们搞的这个导弹啊，excited！” Asm.Def通过数据链发送了算出的疑似目标位置，几分钟后，成群结队的巡航导弹从“无蛤”号头顶掠过，布满了天空。 “一共发射了多少导弹？” “十亿美元。”斯科特·华莱士回答，“单价100万，现在天上有1000多枚。这玩意能自动搜索10个可疑点，找到目标就发动攻击。” “什么？10个？我给了它10万个点！” “这会让