upc专题

[2021.11.19]UPC-2021级新生个人训练赛第4场-19276 Problem B ok 字符串

商场中展示了这么多玩具，乐乐爱不释手。现在游戏环节开始，只要你能解决一个问题，就能够挑选一件精美的玩具。此时，乐乐需要你们这帮“牛娃”的帮助，请你帮助乐乐解决这个问题。现在给你一个长度为 n 的字符串,该字符串只包含字符’o’和’k’。你最多可以修改 t 个字符（将字符’o’改为字符’k’或将字符’k’改为字符’o’），使得某一段连续相同的字符个数是最多的。例如： ‘ooooo’或’kkk

[2021.11.22]UPC-2021级计算机2021随堂测验第五场21281 Problem D 小书童——凯撒密码

题目描述某蒟蒻迷上了“小书童”，有一天登陆时忘记密码了（他没绑定邮箱or手机），于是便把问题抛给了神犇你。蒟蒻虽然忘记密码，但他还记得密码是由一个字符串组成。密码是由原文字符串（由不超过 50 个小写字母组成）中每个字母向后移动 n 位形成的。z 的下一个字母是 a，如此循环。他现在找到了移动前的原文字符串及 n，请你求出密码。输入第一行：一个整数n，含义见题目描述。第二行：未移动前

[2021.11.22]UPC-2021级计算机2021随堂测验第五场18490 Problem A 压缩技术

题目描述设某汉字由N × N的0和1的点阵图案组成。我们依照以下规则生成压缩码。连续一组数值：从汉字点阵图案的第一行第一个符号开始计算，按书写顺序从左到右，由上至下。第一个数表示连续有几个0，第二个数表示接下来连续有几个1，第三个数再接下来连续有几个0，第四个数接着连续几个1，以此类推…… 例如: 以下汉字点阵图案： 0001000 0001000 0001111 0001000 00010

[2021.11.14]UPC-2021级新生个人训练赛第3场-19283 Problem E 调研

题目描述有一直线型展台共有 m 个展位，按该展位离入口处的远近顺序编号，其编号分别为 1、2、……、m；其中只有 n 个是展示新技术的展位，最后一个展示新技术的展位编号为 m。这次调研分两个小组进行，每个小组最多调研连续的 10 个展位，且每个小组调研的展位至少相隔 2 个展位。乐乐希望你设计一种安排方案，使领导调研更多的展示新技术的展位。输入第一行只有一个正整数：n，表示展示新

[2021.11.14]UPC-计算机2021随堂测验第四场-21235 Problem H 自动找人系统

maoge现在转到了警局工作，现在他被要求开发一个找人系统。给定三个参数a，b，c，表示年，月，日，表示一个时间节点。他要找出在两个时间节点之间的时间（两个时间节点本身也包括在内）。现在给定两个时间节点和1个时间发生的时间，他要判断这个时间是否在这个时间段之中。 maoge又双叒叕找到了你来帮忙。输入输入三行，三个时间，每行有三个数，表示年月日。前两行表示两个时间节点（不一定按照第一个小于

[2021.11.14]UPC-计算机2021随堂测验第四场-21232 Problem E 更多闰年数

题目描述输入2 个正整数a和b，表示开始的年份和结束的年份，问从a年到b年有多少闰年？输入第一行2个整数a和b（a≤b），范围在[1, 1,000,000,000]。输出只一个整数。样例输入 Copy 1 10000 样例输出 Copy 2425 题解：类似的题做了n遍了，然而这次的数据量为10^9，于是...从a到b开始遍历逐年判断是否

[2021.11.14]UPC-计算机2021随堂测验第四场-21234 Problem G 买房子

马克思姆想要在一座大房子里面买一套公寓套房，已知有n个套房排成一排，其中有k套房已经被人住了。马克思姆喜欢串门，所以他想要住旁边有人住的房子。我们规定一套房子如果是好房子，那么相邻的房子中至少有一个房子已经有了人住了。但是马克思姆只知道有k个房子有人住了，他并不知道具体哪k个房子住了人。帮助马克思姆算出最少有几个好房子，最多有几个好房子。输入两个整数n,k （1<=n<=109,0<=k<

[2021.11.14]UPC-2021级新生个人训练赛第3场-19282 Problem D 排队

乐乐的 n 位朋友都拥有唯一的一个编号，编号分别为 1 至 n。某天按到达的时间顺序又给了一个顺序号，此时发现顺序号与多数的朋友编号不一致。乐乐想：如果俩俩交换顺序号，使得每位朋友的编号与顺序号相同，则最少需要交换几次？包含二行：第一行只有一个正整数：n，表示乐乐朋友的人数第二行共有 n 个正整数，分别表示按顺序到达的朋友编号输出只有一行且只有一个正整数：最少的交换次数

【upc 9541 矩阵乘法】非正解

深度学习算法很大程度上基于矩阵运算。例如神经网络中的全连接本质上是一个矩阵乘法，而卷积运算也通常是用矩阵乘法来实现的。有一些科研工作者为了让神经网络的计算更快捷，提出了二值化网络的方法，就是将网络权重压缩成只用两种值表示的形式，这样就可以用一些 trick 加速计算了。例如两个二进制向量点乘，可以用计算机中的与运算代替，然后统计结果中 1 的个数即可。然而有时候为了降低压缩带来的误差，只允许其中

【upc 9523】Shopping II

题目描述你要买n件物品，其中有一些是凳子。商场正在举行促销活动，如果购物车中有至少一个凳子，那么你可以半价购买这个购物车中最贵的一个物品。你有m辆购物车，请最小化你的花费。输入第一行一个整数t表示数据组数(1≤t≤100)。每组数据第一行两个整数n,m(1≤n,m≤1000)，接下来n行每行两个整数ai,bi ，分别表示第i件物品的价格以及它是否是凳子(1≤ai≤105,0≤bi≤1

UPC训练赛二十/20240217

A:无穷力量题目描述 2022年重庆突发山火让世界看到了中国一个又一个的感人事迹：战士们第一时间奔赴火场，志愿者们自发组成团队，为救火提供一切的可能的服务，人们自发输送物资，有的志愿者甚至几天几夜没有睡觉。每个人献出一点力，造就了集体的无穷力量。山火被灭后，记者想统计共有多少人志愿者参加了灭火行动，他在山脚共找到了N个不同的志愿者进行调查。这N个被调查的志愿者回答如下：第1位志愿者回答：和

BAPC2017 UPC Collatz Conjecture (数论GCD, 去重优化)

4981: Collatz Conjecture 时间限制: 6 Sec 内存限制: 128 MB 提交: 210 解决: 21 [ 提交][ 状态][ 讨论版][命题人: admin] 题目描述 In 1978 AD the great Sir Isaac Newton, whilst proving that P is a strict superset of

upc国庆集训第八天 Princess Principal(思维+栈)

问题 H: Princess Principal 时间限制: 2 Sec 内存限制: 1024 MB 提交: 183 解决: 37 [提交] [状态] [讨论版] [命题人:admin] 题目描述阿尔比恩王国（the Albion Kingdom）潜伏着一群代号“白鸽队（Team White Pigeon）”的间谍。在没有任务的时候，她们会进行各种各样的训练，比如快速判断一个文档有没有

【基础】字符串连接（UPC)

题目描述给出两个字符串，将它们进行拼接，拼接过程中每个字符只允许出现一次。如：两个字符串s1="adeab"，s2="fcadex"，那么连接时s1留下adeb（第2个a出现过了，就不要了），再将s2连接上来形成adebfcx，两个字符串中重复的都过滤掉，但剩余的顺序不要调整。输入两行，每行一个只包含小写英文字母的字符串。输出一行，连接后的字符串。样例输入 Copy

【入门】字符串对比（UPC）

题目描述给定两个仅由大写字母或小写字母组成的字符串(长度介于1到100之间)，它们之间的关系是以下4种情况之一： 1：两个字符串长度不等。比如 Beijing 和 Hebei 2：两个字符串不仅长度相等，而且相应位置上的字符完全一致(区分大小写)，比如 Beijing 和 Beijing 3：两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全一致（也就是

2018江苏冬令营2 ：UPC 石子游戏 (贪心)

石子游戏时间限制: 1 Sec 内存限制: 128 MB 提交: 118 解决: 32 [ 提交][ 状态][ 讨论版][命题人: admin] 题目描述在Bob学会怎样玩Nim Game之后，他打算尝试另一款看起来更为简单的石子游戏这个游戏是这样子玩的：一共有一个玩家，且一开始有N堆石头，第i堆石头有ai个石子。玩家每次只能移动一个石子从一堆到另一堆。在每次

BZOJ 4488:[Jsoi2015]最大公约数 UPC:2018山东冬令营权值 (GCD)

时间限制: 1 Sec 内存限制: 512 MB 提交: 57 解决: 19 [ 提交][ 状态][ 讨论版][命题人: admin] 题目描述给定一个长为n的正整数序列Ai。对于它的任意一个连续的子序列{Al, Al+1, ..., Ar}，定义其权值W (l, r)为其长度与序列中所有元素的最大公约数的乘积，即W (l, r) = (r − l + 1) × g

ARC073 ：Ball Coloring （球染色） UPC-2018山东冬令营（贪心）

球染色时间限制: 2 Sec 内存限制: 512 MB 提交: 66 解决: 22 [ 提交][ 状态][ 讨论版] 题目描述有n组球，每组有两个球，权值分别为xi, yi。你需要对每组球染色，一个染成红色，一个染成蓝色。 Rmax, Rmin, Bmax, Bmin分别表示红色的球中权值最大的，红色的球中权值最小的，蓝色的球中权值最大的，蓝色的球中权值最小

@UPC 6605 @福建OI2018 [FJOI2018] @ 洛谷 P4578 所罗门王的宝藏 (矩阵行列规律)

题目描述据古代传说记载，所罗门王既是智慧的代表，又是财富的象征。他建立了强大而富有的国家，聚集了大批的黄金象牙和钻石，并把这些价值连城的珍宝藏在一个神秘的地方，这就是世人瞩目的“所罗门王的宝藏”。多少个世纪以来，人们一直在寻找这批早已失落的古代文明宝藏，寻找盛产黄金和钻石的宝地。曾经追寻所罗门王宝藏的冒险者们都一去不回，至今没人解开这个谜题。亨利男爵在一次幸运的旅途中意外地得到了三百年前一位葡

@UPC @NOI 小奇遐想 : 树状数组

5727: 小奇遐想时间限制: 1 Sec 内存限制: 128 MB 提交: 362 解决: 83 [提交] [状态] [讨论版] [命题人:admin] 题目描述撷来一缕清风飘渺方知今日书信未到窗外三月天霁垂柳新长枝条风中鸟啼犹带欢笑 ——《清风醉梦》小奇望着青天中的悠悠白云，开始了无限的遐想，在它的视野中，恰好有n朵高度不同的白云排成一排，他想从左到右选出四朵白云a，b，

@UPC 5725 @中石油 5725 @NOI考前欢乐赛 : 小奇画画(BFS)

5725: 小奇画画时间限制: 1 Sec 内存限制: 128 MB 提交: 387 解决: 65 [提交] [状态] [讨论版] [命题人:admin] 题目描述红莲清泪两行欲吐半点却无如初是你杳然若绯雾还在水榭畔画楼处是谁衣白衫如初谁红裳如故 ——《忆红莲》小奇想画几朵红莲，可惜它刚开始学画画，只能从画圆开始。小奇画了n个圆，它们的圆心都在x轴上，且两两不相交（可以相

@UPC @2018江苏冬令营3 B: 庭师的利刃

题目描述作为白玉楼的庭师，妖梦虽然不会n刀流，但是却领悟了生命二刀流。然而我也是个剑的收藏者，家里屯着n把剑，每一把剑都有一个灵魂值a[i]，由于一些剑之间可能有共鸣，所以我需要两把契合度最高的剑。据妖梦所说，两把编号为i,j剑的契合度为a[i] and a[j]。如何深得剑的灵魂呢？(即求最大值) 输入第一行一个整数n，代表藏剑数。第二行n个整数，第i个整数表示a[i]。

@NOIP, @UPC 暑假训练 :打地鼠游戏 (贪心-优先队列)

K: 打地鼠游戏时间限制: 1 Sec 内存限制: 128 MB 提交: 397 解决: 89 [提交] [状态] [讨论版] [命题人:admin] 题目描述伟大的2320学长特别喜欢打地鼠游戏，这个游戏开始后，会在地板上冒出一些地鼠来，你可以用榔头去敲击这些地鼠，每个地鼠被敲击后，将会增加相应的游戏分值。可是，所有地鼠只会在地上出现一段时间（而且消失后再也不会出现），每个地鼠都在

字母简化（UPC练习）

题目描述给出一串全部为小写英文字母的字符串，要求把这串字母简化。简化规则是：统计连续出现的字母数，输出时先输出个数，再输出字母。比如：aaabbbaa，则简化为3a3b2a；而zzzzeeeeea，则简化为4z5e1a。输入有多行。第一行为一个整数n，表示共有n组测试数据（1≤n≤100）。接下来有n行，每行第一个数为字符串长度t（t≤1000），然后为一个长度为t的字符串。输出

UPC-9559 树链博弈

题目传送门题目描述：给定一棵n个点的树，其中1号结点是根，每个结点要么是黑色要么是白色现在小Bo和小Biao要进行博弈，他们两轮流操作，每次选择一个黑色的结点将它变白，之后可以选择任意多个(可以不选)该点的祖先(不包含自己)，然后将这些点的颜色翻转，不能进行操作的人输由于小Bo猜拳经常输给小Biao，他想在这个游戏上扳回一城，现在他想问你给定了一个初始局面，是先手必胜还是后手必胜输

【upc】2020年秋季组队训练赛第十五场 Black and White | 扫描线 + 线段树

问题 B: Black and White 时间限制: 1 Sec 内存限制: 128 MB提交状态题目描述 Consider a square map with N × N cells. We indicate the coordinate of a cell by (i, j), where 1 ≤ i, j ≤ N . Each cell has a color either w