3 fly_tzf

尚未进行身份认证

暂无相关简介

等级
TA的排名 10w+

HDU 4388(博弈)

思路:假设任取一堆石子,个数为n。每次操作就是把n变为k和k XOR n(0<k<n)这两堆。我们发现当n=2^i时,就不能再分了。因为n异或上一个小于n的数肯定大于n。那么最后n可以分成t堆,并且这t堆的个数都满足tn = 2^i,tn的二进制中1的个数为1,那么t就等于n的二进制中1的个数。现在考虑把(k XOR n)换为(2*k XOR n),二进制中1的个数奇偶性不变。所以我们...

2018-04-16 19:18:07

Java结构体排序

使用ArrayList容器存放数据。使用Collections.sort()方法排序。class Node{ String name; int grade; Node(String name, int grade){ this.name = name; this.grade = grade; }}例如对Node结构体按grade大小排序升序Collection

2018-01-21 19:50:33

Gym 101201J Shopping(RMQ +二分 )

思路:因为每次除余一个数,那么每次至少减少一半,发现这个后就可以直接暴力。例如对于a, 每次找区间中第一个小于等于a的数进行除余。用RMQ+二分时间复杂度(qlogloglogn).#includeusing namespace std;typedef long long LL;const int maxn = 2e5 + 10;int n, q;LL d[maxn << 2][20

2017-09-30 10:38:39

POJ - 3678(2-sat)

思路:很明显是一个2-sat问题。对于顶点A,B,如果A & B = 1,那么A,B必须都是真,让A取假时矛盾,即 !A->A, !B->B.     如果A & B = 0,那么A、B一真一假,即A->!B, B->!A.     如果A | B = 1,那么A取假时B为真,B取假时A为真,即!A->B, !B->A.     如果A | B = 0,那么A,B必须都是假,让A取

2017-09-30 10:01:20

Gym 101201F Illumination(2-sat)

题意:给定一个n*n的格子,其中有l盏灯,每盏灯能照亮(2 *r+1)的一行或一列,每个格子只能被一行的一盏灯和一列的一盏灯照亮,否则就不满足条件,问是否存在一种方案,打开所有的灯并且满足条件?思路:每个格子有两种状态,用A1表示被行中的灯照亮,A2表示被列中的灯照亮。那么对于同一行的可以互相照射两盏灯A,B,则有A1->B2, B1->A1.对于同一列的可以互相照射两盏灯A,B,则有

2017-09-30 09:43:54

CodeForces - 842C Ilya And The Tree

思路:比赛时,写了个树dp,情况考虑少了,赛后才知道gcd的个数是很少的,可以直接暴力,每访问到一个点可以直接去掉这个点或者不去掉这个点,两种情况。开个vector保存这个点gcd的情况,算完之后要去重。#include#include#include#include#include#include#include#include#include#include#inc

2017-08-30 20:39:19

FZU 1911 Construct a Matrix(矩阵快速幂+构造)

思路:S(n) = S(n-1) + f(n),通过构造矩阵可以求出S(n),主要问题就是构造一个S(n) * S(n)的矩阵满足条件。自己写一写就能找出构造方法,因为矩阵只包括0,1,-1,那么一个n*n的矩阵,每一行的sum在-n到n之间,又因为-n和n不能同时存在,所以我们可以让每一行的和在-n到n-1之间,一共2*n个数,刚好对应n行,n列,每一行每一列的sum都不相同,然后构造就行了

2017-08-29 09:22:21

hdu - 6125 Free from square (状态压缩+分组背包)

思路:考虑到n最多为500,小于sqrt(n)的素因子有八个,可以用二进制表示,而大于sqrt(n)的质因子每个数只可能出现一次,即一个数分为两部分,小于sqrt(n)的质因子状压, 大于sqrt(n)的质因子至多有一个用分组背包。那么含有大于sqrt(n)的素因子的数可以分组。例如71,142,213,355,426,497为一组,因为任意两个选了之后都能被71整除 。组与组之间是不冲突的,因为

2017-08-16 17:29:52

LightOJ - 1095 Arrange the Numbers(错排数)

思路:首先前m个数中有k个位置是不变的,所以先选出来有C(n, k)种,然后在前m个数中肯定有(m - k)个数是错排的,后边(n - m)个数不确定,那么可以枚举后边(n - m)个数有i个数没有参与错排,那么没有参与错排的共有k+i个,参与错排的就有n-k-i个,共有C(n-m, i)* d(n - k - i)种。那么答案就是C(n,k) * ∑(C(n-m, i)* d(n - k -

2017-08-15 09:47:27

POJ 2288 Islands and Bridges(状压dp)

思路:所求的哈密顿路径由三部分组成,一,所有节点的权值之和,二,每条边的权值之和,三,三元环的权值和。设集合S为拜访的点的集合,当向集合S中加入一个点,与上一条边的起点和终点有关。所以令dp[s][i][j]表示集合S通过边(i, j)加入j点之后的最大权值。那么 dp[s][i][j] = max(dp[s][i][j], dp[p][k][i] + tmp). p表示未加入j点的集合,tm

2017-08-07 12:30:46

HDU 6069(素数筛法)

思路:设n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}n=p​1​c​1​​​​p​2​c​2​​​​...p​m​c​m​​​​,则d(n^k)=(kc_1+1)(kc_2+1)...(kc_m+1)d(n​)=(c​1​​+1)(c2+1)...(cm+1)则d(n^k)=(kc_1+1)(kc_2+1)...(kc_m+1)d(n​k​​)=(kc​1​​+1)(kc​

2017-08-04 09:57:55

HDU - 6038 F - Function

思路:求出a和b中各个循环的长度。要使a中的某个循环满足,那么b中必须存在一个循环它的长度为a的因子,因为只有b中循环长度是a中的因子,才能被a整除,最后a置换回来才不变。#include#include#include#include#include#include#include#include#include#include#include#include#inc

2017-07-25 21:07:31

HDU - 4424 Conquer a New Region(Kruskal的应用)

思路:类似Kruskal算法,将边按权值从大到小排序,每次加入一条边AB,如果以A所在的集合为中心城市,那么总权值为A所在集合的权值加上B所在集合点的数量乘以这条边的权值,因为A、B所在集合中的边肯定大于AB的权值,如果B所在的集合为中心城市,可以以同样的方法计算,取两者中大的那一个。

2017-07-24 21:15:33

HDU - 5072(容斥原理)

题意:给你a,b,n,问区间[a, b]内有多少数与n互素?解题思路:问题可以转化为求1到b内与n互素的个数减去1到a-1内与n互素的问题,那么现在的问题就是求1到x内与n互素的个数。要求1到x内与n互素的个数,可以先求不与n互素的个数。不与n互素的个数可以将n质因数分解,n的质因子的倍数肯定不与n互素。例如x = 15, n = 10。n的质因子有2、5.。(2、4、6、8、10、12、

2017-07-03 17:34:10

Linux操作系统实验(3)(模拟实现请求分页虚存页面替换算法)

数据结构:typedefstruct_Page{//页面intpageID;//页号}Page;typedefstruct_PageQueue{//页面队列Pagepage;struct_PageQueue*next;//下一页面}PageQueue;typedefstruct_Block{//块记录结构

2017-07-01 10:35:06

Linux操作系统实验(2)

内核模块的结构:                      头文件声明。头文件module.h和init.h是必不可少的。module.h是加载模块所需要的函数和符号定义;init.h中包含初始化和清楚函数的定义。如果加载是允许用                                                          户传递参数,模块还应包括moduleparam

2017-07-01 09:51:41

poj3254(状态压缩DP)

解题思路:考虑到m比较小并且每块地有两种状态,故可以将状态压缩,用一个数表示一行的状态。从上一行到下一行转移时有两个限制,第一,同一行相邻的地不能同时种,上下两行相邻的地不能同时种。例如样例,第一行有5中状态,000,001,010,100,101.第二行有两种状态000,010.那么第二行中000可以由第一行的5中转移有5中,010不能有第一行的010转移故有4种,共九种。#incl

2017-06-27 21:14:06

Linux操作系统实验初学(1)(生产者消费者问题)

数据类型:sem_t :信号量的数据类型,本质上是一个长整型。   pthread_t:用于声明线程的ID。pthread_mutex_t:互斥锁函数:int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t * attr):用于初始化互斥锁。int sem_init(sem_t *se

2017-06-27 11:49:31

hdu 2059 龟兔赛跑(DP)

思路:用dp[i][0]表示到第i个加油站不加油所用的最小时间,dp[i][1]表示到第i个加油站加油所用的最小时间。将终点设为第n+1个站,则答案为dp[n+1][0].具体细节看代码。#include#include#include#includeusingnamespacestd;typedeflonglongLL;constLLINF=1000000000

2017-05-31 21:46:15

UVA - 11552 Fewest Flops (dp)

思路;用dp[i][j]表示到第i组末尾为字母j块的最小值,那么dp[i][j]=min(dp[i][j],dp[i-1][l]+f[i]-1),第i组和第i-1组含有字母l,并且l和j不同,否则dp[i][j]=min(dp[i][j],dp[i-1][l]+f[i]).f[i]为每组的不同字母数。#include#include#include#include

2017-05-16 16:26:12

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!