- 博客(33)
- 收藏
- 关注
RSS订阅原创 New Year‘s Problem codeforce1619D
大致意思就是说，总共有m个商店，有n个朋友。每个商店里卖n中货物，每个商店的第i种货物能给第i个朋友带来不同的高兴值，且只能从n-1个商店里面选出n件礼物，使得n个朋友的高兴值尽量大一点，然后输出在这尽量大的高兴值队列中最小的高兴值是多少。Vlad wants to maximize the minimum of the joys of his friends.首先，要明确，可能满足n个朋友的礼物的队列是不唯一的，也就是说，会有很多不同的值能够满足，要求得最优解，就必须要一次次逼近，所以，选用二分+贪心
2022-01-11 09:23:20
155
原创 Line codeforces7C
这道题相当于是一道扩展gcd的模板提。首先要知道什么是扩展gcd，按照目前的理解来说，扩展gcd是来求一组二元不定方程组的解，这个跟逆元有关，对任意的a，b和它俩的gcd(a,b),总能找到一组解使得ax+by=gcd(a,b),同时利用求gcd的方法我们知道，bx1+(a%b)y1=gcd(b,a%b),我们知道的是gcd(a,b)=gcd(b,a%b),所以将方程组化简就得到ax+by=bx1...
2018-12-21 15:46:52
198
原创 1040 最大公约数之和
这个题最开始直接tl了，其实我们知道这a[n]个数与n的gcd就是n的因子，所以直接求出n的所有因子的个数然后就可以得出答案了；这是刚开始学欧拉函数，当作一个模板。#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm...
2018-12-20 21:49:23
245
原创 Vasya and Petya's Game
这个题刚开始看的时候是一脸懵逼，不过后来就读懂了，一看这道题就知道这道题是在考素因子分解，他说一个人心中想了一个数让另一个人来猜这个数是啥，求最少的次数和猜的数。换个想法，我们都知道任何一个数都可以分解成一长串素数的乘积。所以，我们只需来求1到n之间的素数种类存下来然后再再对每一个素数挨着去尝试问它的次幂，这样这个数就会花最少的次数猜出来了。#include<iostream>...
2018-12-18 21:31:09
418
原创 Dima and Lisa
这是一道初等数论的题。特别注意的是题目中说了给的数一定是个基数（自己英语太渣）首先我们知道的是它最多只能分解成3个素数的和，所以我们只需要分别考虑分成一个数两个数三个数的情况。分成一个数就只能是它自己是个素数。如果分成两个数，那么只能是一个奇数一个偶数，偶数是素数的就只有2，判断n-2就ok，分成3个数的话，有可能是3个奇数或者说一个奇数两个2，注意，素因子分解中两个素数最大距离不超过300，看了...
2018-12-17 21:56:06
158
原创 G - 传递 HDU - 5961
这道题刚看的时候觉扽它是一条最短路的问题，以为用flyod把每两个点之间的距离跑出来就欧克了，结果数据量太大是不行的，所以去看了一下大佬的代码，结果直接用搜索就可以了，不过就是有个优化的细节就是用的vector邻接表来存的边，然后从1到n遍历每一个顶点，然后再遍历下一个顶点邻接的下个顶点，看他们的距离是否大于二，这样每次搜索就能卡过时间。唉，比赛的时候一定要注意这些细节。#include&l...
2018-12-09 11:15:46
183
原创 War Chess
这个题我做的时候错了很多次，这种没有固定的终点的题一般来说都得用优先队列，有固定的终点的直接用队列搜索出其最短的距离就ok了，这道题有个坑点就是当你走到那一步的时候，如果它周围的四个方向上有敌人的话，那么它的hp就会直接更新为零。所以，当你走到下一步的时候我们得再搜一下它的四个方向是不是有有敌人，然后判断它的hp的值，当然前提是得你能走到那个位置，不然的话其它的东西都是白搭，以后做题的时候一定要分...
2018-12-05 14:50:41
315
原创 Telephone Lines架设电话线
写了快两个礼拜的最短路和生成树，也不算是入门，遇见这个题，发先要用二分。我在二分方面就是一个白痴，后面才知道因为题目的要求是只给你提供k个电线杆的连接，所以我们只需要用二分来求得所需买的最短长度就ok。FarmerJohn打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。FJ的农场周围分布着N(1<=N<=1,000...
2018-11-28 20:26:09
421
原创 免费馅饼
首先应该明白他在当前的这个位置有3种选择，在下一秒的时候他可以选择向左或者向右或者呆在原地不动，而且在当前的这一秒他会接住落在当前这一秒的数目。所以dp方程就写出来了；dp[i][j]=max(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]+data[i][j],表示为在第i秒的j位置它应该如何选择。 都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，...
2018-11-13 16:54:04
361
原创 Piggy-Bank
这是一道完全背包模板题。它的大意就是说给你一个硬币罐子的容量，然后给你不同种类的硬币，价值和重量各不相同。然后采取01背包的思想，不过要先将dp设置为最大值，然后再按照从小的重量到极限的重量来dp就可以了；Before ACM can do anything, a budget must be prepared and the necessary financial support obtai...
2018-11-07 20:24:47
133
原创 饭卡
这是一道01背包的一道变形的题。首先，它要求的是大于5快的时候价值任何大的物品都可以买，小于五块的时候价值任何小的东西都不能买，所以，我先对他进行了排序。把价值最大那个保留下来，让它最后一个大于等于五块的时候再减。然后就是利用01背包的一半思路来解决这个问题就电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（...
2018-11-06 16:14:53
170
原创 Common Subsequence
这道题就是典型的dp求最长公共子序列。主要的判断条件就是：1.如果m=n，那么就在dp[i-1][j-1]的基础上加1； 如果不是就是在之前的数上取得最大值。A subsequence of a given sequence is the given sequence with some elements (poss...
2018-11-06 15:55:46
136
原创 Max Sum
这道题是一道很基础的dp题，就是求简单的最大子段和然后找出是从哪到哪。只需要新开一个数组pre来记录它的开始点就可以了。 Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), ...
2018-11-06 15:52:02
151
转载 Almost Union-Find
这个题是一个合并并查集节点的一道题，首先要明白的是并起来的元素就相当于一颗二叉树一样，所以不可能随便的将一个二叉树的根节点删除掉，所以我们只能让它保持在她的原位但是废弃掉它所有的功能。所以，我们需要给每一个节点都给他一张能识别它的身份证，当我们要废除掉一个节点的时候，先废除掉她的功能，然后新开一个点来表示它，再把它和别的节点合并起来。#include<bits/stdc++.h>...
2018-11-02 20:31:51
285
原创 Fire Game
这道题最开始的时候不太明白它讲的什么意思，后来看了下大神的讲解才算是懂了一点。他是从任意同时选中两块草地，将两块草地同时push进入队列，然后再进行广搜就行。#include<cstdio>#include<iostream>#include<cstring>#include<queue>using namespace std;int...
2018-11-02 20:27:13
150
原创 Dungeon Master
这是一个三维立体图的一道搜索题。和普通的二维搜索差不多，不过就是多了一个纵坐标z，然后设置结构体将他放入结构体中，按照以前的方式按部就班的做就可以AC,不过一定要注意它的越界条件，当它>=边界的时候就会算作是越界了。You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is...
2018-11-01 21:24:39
230
原创 Catch That Cow
首先一看这道题让求最小的步数所以显然是用广搜。题目中吧给了三种方式：1.+1 2.-1 3.*2 所以，我们采取广搜的时候就要用这三种方式挨着去搜。水题，大体就是这样了。Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He ...
2018-10-31 21:35:05
100
原创 Lara Croft and the New Game
You might have heard about the next game in Lara Croft series coming out this year. You also might have watched its trailer. Though you definitely missed the main idea about its plot, so let me lift t...
2018-06-02 17:17:28
383
原创 Minimum Inversion Number
The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj. For a given sequence of numbers a1, a2, ..., an, if we move the fi...
2018-05-29 21:04:09
172
原创 Protecting the Flowers
Farmer John went to cut some wood and left N (2 ≤ N ≤ 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cluster of cows was in his garden eating his beautiful...
2018-05-25 21:23:13
152
原创 Booking System
Innovation technologies are on a victorious march around the planet. They integrate into all spheres of human activity!A restaurant called "Dijkstra's Place" has started thinking about optimizing the ...
2018-05-24 22:08:07
431
原创 The War
A war had broken out because a sheep from your kingdom ate some grasses which belong to your neighboring kingdom. The counselor of your kingdom had to get prepared for this war. There are N (1 <= N...
2018-05-24 22:01:18
190
原创 Banana
Piegirl is buying stickers for a project. Stickers come on sheets, and each sheet of stickers contains exactly n stickers. Each sticker has exactly one character printed on it, so a sheet of stickers ...
2018-05-09 21:27:09
257
原创 Prime Ring Problem
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime. Note: the number of f...
2018-05-04 11:51:55
80
原创 GZS与小公园（广搜）
Description某天GZS漫步在学校新建的小公园，他发现那里建成了一些水池和小河道。我们暂且把它们统一看成水池。假设公园旁有一张小公园的地图，上面仅标识了此处是否是水池，你能帮GZS计算出该地图中一共有几个水池吗。Input第一行输入一个整数N，表示共有N组测试数据 每一组数据都是先输入该地图的行数m(0<m<100)与列数n(0<n<100)，然后，输入接下来的m行...
2018-04-30 19:51:02
137
原创 GZS与小公园（深搜）
Description某天GZS漫步在学校新建的小公园，他发现那里建成了一些水池和小河道。我们暂且把它们统一看成水池。假设公园旁有一张小公园的地图，上面仅标识了此处是否是水池，你能帮GZS计算出该地图中一共有几个水池吗。Input第一行输入一个整数N，表示共有N组测试数据 每一组数据都是先输入该地图的行数m(0<m<100)与列数n(0<n<100)，然后，输入接下来的m行...
2018-04-30 19:49:30
179
原创 Magic Numbers
A magic number is a number formed by concatenation of numbers 1, 14 and 144. We can use each of these numbers any number of times. Therefore 14144, 141414 and 1411 are magic numbers but 1444, 514 and ...
2018-04-20 11:20:24
483
原创 C - Bash游戏
有一堆石子共有N个。A B两个人轮流拿，A先拿。每次最少拿1颗，最多拿K颗，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N和K，问最后谁能赢得比赛。例如N = 3，K = 2。无论A如何拿，B都可以拿到最后1颗石子。Input第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000) 第2 - T + 1行：每行2个数N，K...
2018-04-19 18:28:29
145
原创 C - Candies
Polycarpus has got n candies and m friends (n ≥ m). He wants to make a New Year present with candies to each friend. Polycarpus is planning to present all candies and he wants to do this in the faires...
2018-04-17 16:57:02
490
原创 B - Pythagorean Theorem II
n mathematics, the Pythagorean theorem — is a relation in Euclidean geometry among the three sides of a right-angled triangle. In terms of areas, it states:In any right-angled triangle, the area of th...
2018-04-17 16:38:08
171
原创 B - 数字1的数量
给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数。例如：n = 12，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。Input输入N(1 <= N <= 10^9)Output输出包含1的个数Sample Input12Sample Output5#include<stdio.h>int main(void){ ...
2018-04-17 16:22:30
299
原创 蚂蚁
n只蚂蚁以每秒1cm的速度在长为Lcm的竿子上爬行。当蚂蚁爬到竿子的端点时就会掉落。由于竿子太细，两只蚂蚁相遇时，它们不能交错通过，只能各自反向爬回去。对于每只蚂蚁，我们知道它距离竿子左端的距离xi，但不知道它当前的朝向。请计算各种情况当中，所有蚂蚁落下竿子所需的最短时间和最长时间。 例如：竿子长10cm，3只蚂蚁位置为2 6 7，最短需要4秒(左、右、右)，最长需要8秒（右、右、右）。Inpu...
2018-04-15 16:15:19
363
原创 母牛的故事
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？Input输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。 n=0表示输入数据的结束，不做处理。Output对于每个测试实例，输出在第n年的时候母牛的数量。 每个输出占一行。Sample Input24...
2018-04-14 19:56:47
129
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人