qq_41703679的博客

原创 gym100851

https://codeforces.com/gym/100851/my 打表可以发现任何一个可能的答案，它的后缀也是正确答案。所以可以通过搜索求得解。初始的正解集合是{0，1}，然后枚举这些正解，在它的前面加上0，判断是否满足要求，将其加入到集合p中。再次枚举正解，在前面加上1，判断是否满足要求。如果满足，那么正确答案数加一，将其加入到集合p中。将p作为下一次的正解集合，重复...

原创 2017 CERC

https://codeforces.com/gym/101620/解题报告：https://www.cnblogs.com/GerynOhenz/p/8418171.htmlProblem J:Justified Jungle题目描述：给定一个有n个节点的数，找出所有的整数k，满足在树上删掉k条边后，形成的每棵树的节点数相同。solution首先，k+1一定是n的因...

原创 Gym 101078

A题比较两个由数字1~n组成的序列，输出每段最短的相似的序列。（相似代表这段中两个序列包含的数字相同，顺序可以不同）Input2101 2 3 6 4 7 5 8 9 103 2 1 4 5 6 7 8 10 952 1 4 5 32 4 5 3 1Output1-3 4-7 8-8 9-101-1 2-5用一个hash数组来标记某数字出现的次数，每扫描到一个数字...

原创 2018-2019 ICPC 沈阳站

https://codeforces.com/gym/101955C题题意：输入n，k，q，问有多少1~n的排列，使得在把前k个按升序排好序后，最长上升子序列的长度不低于n-1.暴力打表找规律，得出方程。打表代码：#include <iostream>#include <algorithm>#include <cstdio>#in...

转载 G - A Question of Ingestion 动态规划

 题意： 起始饭量 = m， 你可以吃n次饭， 当你连续吃时，饭量是上次的2/3; 当你休息一次时, 饭量和上次相同; 当你连续休息两次时，饭量恢复到起始值m.dp[i][j]表示准备吃第i个，已经吃了j个的最大卡路里和也就是在第i天，吃饭的饭量等级是j的状态状态转移分为：从昨天转移过来，从前天转移过来，从大前天转移过来。初始值：饭量等级为1，能吃多少吃多少。https://v...

原创 Dream 费马小定理 构造

https://vjudge.net/problem/HDU-6440题目大意：给你一个式子 ，让你构造一个p*p的乘法表和加法表，使得所有的在（0，p-1）内的m，n都满足这个式子。题目给定的p是素数。Sample Input12Sample Output0 11 00 00 1分析：因为给定的p是素数，根据费马小定理得因此，当m+n不等于p时，有 同时...

原创 YJJ's Salesman CCPC网络赛 离散化+树状数组 简单DP

https://vjudge.net/problem/HDU-6447题目大意：有一个1e9*1e9的网格，其中一些点上有一些村庄，从（0，0）点出发，想到达右下角的格子，可以向右走，向下走或向右下走，只有当向右下走的时候才能获得村庄的财富值。问最多能获得多少财富值？分析：DP方程很好画，dp[i][j] = max{dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+v...

原创 POJ3690 字符串哈希 星座

https://vjudge.net/contest/247319#problem/C题目大意就是给出一个n * m的矩阵，矩阵中只有一些*或者0，n <= 1000, m <= 1000然后有t (t <= 100)个询问，每次询问给出一个p * q的矩阵，p,q是提前固定的数值。问这些询问中是大矩阵的子矩阵的有几个 如果暴力查询，时间复杂度为t*n*m*p...

原创 HDU - 2473 并查集删点

Recognizing junk mails is a tough task. The method used here consists of two steps:1) Extract the common characteristics from the incoming email.2) Use a filter matching the set of common characteri...

原创 递推 2017CCPC杭州站现场赛B题 Master of Phi 欧拉函数

http://acm.hdu.edu.cn/showproblem.php?pid=62652017CCPC杭州站现场赛B题题目大意：给你一个数n的因数及其指数pi,qi,对于其所有的因数d，求 题解：题中给了一个求欧拉函数的公式欧拉函数的公式可以变形为下面这种形式，即 把 m 拆分成 pi 的 hi 次方的乘积后，把每个质因子pi都乘进去一个。其中 pi 是 ...

原创 读入字符串时对换行符和空行的处理

读入数据的时候要注意，行末有换行符和空行之类，这里直接用cin和cout，避免了这些可能导致错误的地方。也可以用 scanf("%s", &s) 读入字符串，它也会自动忽略换行符和空行。但 scanf("%c", &s[i][j]) 就不会忽略，需要加一个getchar函数来读入换行符和空行。...

原创 Word Puzzle Tri树

Word PuzzleTime Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 886    Accepted Submission(s): 226 Problem DescriptionDid you heard of a litt...

原创 Tri树 统计难题

统计难题Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others)Total Submission(s): 56022    Accepted Submission(s): 19568 Problem DescriptionIgnatius最近遇到一个难题,老师交给他很多单...

原创 GYM 101606 K.Knightsbridge Rises（最大流-Dinic）

Problem KKnightsbridge RisesDescription现在有m个重量分别为Ti的物品需要吊到楼上，有n个吊车，第i个吊车的重量为Wi，可以吊起的重量为Li，重量为0表示该吊车可以无代价的先放置在楼上以吊起重物或其他吊车，问如果安排吊车可以把这m个重物都吊到楼上，一个吊车只能用一次Input第一行一整数n表示吊车数量，之后n行每行两个整数Li,...

原创 带权并查集 How Many Answers Are Wrong HDU - 3038

TT and FF are ... friends. Uh... very very good friends -________-bFF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game. To begin with, TT should w...

原创 Brainman 归并排序求逆序对

Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie wo...

原创 Tree POJ1741 树的分治 重心分解

Give a tree with n vertices,each edge has a length(positive integer less than 1001).Define dist(u,v)=The min distance between node u and v.Give an integer k,for every pair (u,v) of vertices is calle...

原创 有序数组里，两两一组和不超过k的数字组数 经典求法 双向搜索

sort(dis, dis + num); int i = 0, j = num - 1; while (i < j) //经典 { while (dis[i] + dis[j] > k && i < j) j--; ret += j-i; i++; }首先将数组按升序排序固定i后求出a[i]+a[j]不超...

原创 区间DP

HDU - 5115 Dire wolves, also known as Dark wolves, are extraordinarily large and powerful wolves. Many, if not all, Dire Wolves appear to originate from Draenor.Dire wolves look like normal wolves,...

原创 最大矩形 —— 单调栈

https://cn.vjudge.net/contest/245662#problemA histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heigh...

原创 求a~b中与n互质的数的个数

https://cn.vjudge.net/contest/243561#problem/F首先我们要会求1~m中与n不互质的数的个数。然后用b-(a-1)-(solve(b)-solve(a-1))即可。solve(b)是指1~b中与n不互质的数的个数。不互质就说明有公共的质因子。那么solve(b)怎么求呢？先把n的质因子全都筛出来存在一个vector数组里，然后用容斥原理求即可。...

原创 硬币游戏1 博弈

原创 Chess sg值 Nim游戏

Alice and Bob are playing a special chess game on an n × 20 chessboard. There are several chesses on the chessboard. They can move one chess in one turn. If there are no other chesses on the right adj...

原创 Euclid's Game

Two players, Stan and Ollie, play, starting with two natural numbers. Stan, the first player, subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, prov...

原创 A funny Game

Alice and Bob decide to play a funny game. At the beginning of the game they pick n(1 <= n <= 10 6) coins in a circle, as Figure 1 shows. A move consists in removing one or two adjacent coins, l...

原创 C(n,k) 的质因子分解 POJ - 2992

Your task in this problem is to determine the number of divisors of Cnk. Just for fun -- or do you need any special reason for such a useful computation?InputThe input consists of several instance...

原创 hdu 1576 A/B

要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。Input数据的第一行是一个T，表示有T组数据。每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。Output对应每组数据输出(A/B)%9973。Sample Input2...

原创 Dual Core CPU POJ - 3469 最大流 最小割 Dinic算法

As more and more computers are equipped with dual core CPU, SetagLilb, the Chief Technology Officer of TinySoft Corporation, decided to update their famous product - SWODNIW.The routine consists of ...

原创 食物，牛，和饮料 Dining 最大流 拆点 （Dinic）

Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others.Farmer John has cooked fabulous meals for his cows, but he forgot to check his me...

原创 Evacuation 二分图匹配 + 最短路

Fires can be disastrous, especially when a fire breaks out in a room that is completely filled with people. Rooms usually have a couple of exits and emergency exits, but with everyone rushing out at t...

原创 Landscaping 最大流 / 最小割

Preparations for a good harvest in Spring start now and farmer John is preparing his field for a good season. He went over budget last year, as the tractors moving up and down the hills needed more fu...

原创 Billboard 巧妙运用线段树

在学校的入口处有一个巨大的矩形广告牌，高为h，宽为w。所有种类的广告都可以贴，比如ACM的广告啊，还有餐厅新出了哪些好吃的，等等。。在9月1号这天，广告牌是空的，之后广告会被一条一条的依次贴上去。每张广告都是高度为1宽度为wi的细长的矩形纸条。贴广告的人总是会优先选择最上面的位置来帖，而且在所有最上面的可能位置中，他会选择最左面的位置，而且不能把已经贴好的广告盖住。如果没有合适的位...

原创 debug

RE：数组开小了/main函数里数组开多了

原创 尺取+二进制 WiFi Password

Just days before the JCPC, your internet service went down. You decided to continue your training at the ACM club at your university. Sadly, you discovered that they have changed the WiFi password. On...

转载 D - Reversed LCS DP+DFS

https://agc021.contest.atcoder.jp/tasks/agc021_dDescripion: 给定一个字符串，可以更改其中的kk个字符，要求最大化该字符串与其翻转字符串的LCSLCS长度，求该长度。Solution: dpi,j,kdpi,j,k表示区间[i,j][i,j]修改了kk个字符最长的LCSLCS。很明显如果没有修改最长的LCSLCS为最长回文子序列，那么每次考...

原创 Median

Given N numbers, X1, X2, ... ,XN, let us calculate the difference of every pair of numbers: ∣Xi- Xj∣ (1 ≤ i ＜ j ≤ N). We can getC(N,2) differences through this work, and now your task is to find

原创 如何判断二分的边界（完善中）

边界一定不能写成死循环。多画几次就能看出来的。

原创 如何输入多组测试数据（Output Limit Exceeded错误）

当scanf读取成功时返回读取到的参数数量，否则返回EOF。EOF是一个宏，定义在stdio.h里，值为-1。以下面代码为例，正确的判断方式有：scanf("%d-%d-%d", &year, &month, &day) != EOFscanf("%d-%d-%d", &year, &month, &day) == 3或~scanf("%d-%d-%...

原创 Robin Hood 二分

We all know the impressive story of Robin Hood. Robin Hood uses his archery skills and his wits to steal the money from rich, and return it to the poor. There are n citizens in Kekoland, each person ...

原创 Web Navigation（stl-栈）

Standard web browsers contain features to move backward and forward among the pages recently visited. One way to implement these features is to use two stacks to keep track of the pages that can be re