- 博客(88)
- 收藏
- 关注
RSS订阅原创 XOR HDU - 3949
题意：给一堆数，可以将其中一些数拿出来异或，一个单独的也可以，有m个询问，给一个k，问第k小的异或的数是多大？思路：弱的不行。。。看来博客才知道了线性基这个东西线性基能相互异或得到原集合的所有相互异或得到的值。线性基是满足性质1的最小的集合线性基没有异或和为0的子集。（百度百科）每个数展开数位，可以变成一个矩阵
2017-11-16 19:57:23
321
原创 Painter's Problem POJ - 1681
题意：涂色，每涂一个格子就会将其临近的格子都改变，黄的变成白的，白的变成黄的，给出画板初始情况，问最少多少次操作可以使得画板全部变成黄色思路：消元后，自由变元的取值情况的变化会造成后边的解的变化剩下最后n个变元，遍历每种取值情况后，回溯找到解中操作次数最少的#include#include#include#includeusing namespace std;co
2017-11-16 17:47:18
283
原创 开关问题 POJ - 1830
题意：灯泡对应开关，有些开关的拨动会影响其他的开关，给出灯泡初始状态，给出灯泡结束状态，问有几种操作可以完成思路：建立矩阵，消元后有n个自由变元，答案就是2^n个#include#include#include#includeusing namespace std;const int MAXN=50;int a[MAXN][MAXN];//????int s[MAXN
2017-11-16 17:35:23
471
原创 EXTENDED LIGHTS OUT POJ - 1222
题意：按下一个按钮，会不小心碰到与其邻接的按钮，每个按钮对应着一个灯泡，现在给出灯泡情况，问如果操作可以将灯泡全部关掉思路：高斯消元基础题消除到最后进行回溯求解将灯泡进行编号，（x1,x2,....xn）b表示开关的解矩阵每行表示该灯泡与几号开关有关的方程#include#include#include#includeusing namespace std;
2017-11-16 17:30:48
303
原创 GCD HDU - 1695
题意：和Gcd HYSBZ - 2818几乎一样，在区间[ a , b ] 取一个x，在区间[ c , d ] 取一个y，求 得gcd（x,y）=k的对数同时 （x，y） 与（y,x）为一对，斌且这里a=c=1。思路：这里我们可以延续上次的套路，分段去取莫比乌斯前缀和，但是这里怎么去除 （y,x）？我是这样想的 当只有x与y的区间相同，除去gcd（1，1），其他的都有
2017-11-15 19:01:55
236
原创 Magic Bracelet POJ - 2888
题意：不同项链个数，长度n，（n，m思路：n过多的时候就自然的想到 有 euler（n/i）个 间隔为j的置换群，可以直接得到 循环节个数gcd（j，n）等于i的个数统计n的约数就可以在O（sqrt（n））的复杂度完成，我们知道 gcd 为循环节个数 ，也即是一个旋转的原串（个人的理解）如图 gcd=5，只要这个串是合法的就可以是一种方案，合法的方案是
2017-11-07 21:00:54
296
原创 Color POJ - 2154
题意：n个珠子的环，之多着n种颜色，考虑旋转，不考虑翻转。问模P的方案数。思路：1））；T这里我们知道[0，n-1]中有许多gcd为1的数据不必一一遍历这些数据有euler（n）个我们还能得出gcd为2的有euler（n/2）个只要一一遍历n的约数即可O（sqrt(n)）的时间复杂度#include#include#define long long intus
2017-11-06 20:18:29
170
原创 Count the Tetris HDU - 1812
题意：给出n,c,给N*N方格，涂色，方格可以旋转，反转，对角线反转思路：要分奇偶讨论：应为奇偶的指环群是不一样的最后千万不要忘记对折n,c过大要开java大数import java.io.*;import java.util.*;import java.math.*;public class Main { public static void main(S
2017-11-06 19:18:03
181
原创 Necklace UVA - 11255
题意：给定特定个数的 黑色，灰色，白色珠子形成一个手串，手串可以翻转，旋转思路：利用burnside定理，计算各种置换群下的不动点个数旋转：gcd计算循环节个数，得倒每个的循环节长度，反转：分开奇偶，对称轴#include#define ll long longusing namespace std;int a,b,c;ll C[45][45];void
2017-11-06 19:16:44
204
原创 Cubes UVA - 10601
题意：给你12根等长的木棒，颜色给出，并且不超过6种颜色，拼出正方体，正方体可以旋转，有多少种不同的正方体思路：由于不是无限根，所以无法用polya定理，我从新学习了burnside定理。明确操作后
2017-11-06 18:44:38
200
原创 Who's Aunt Zhang HDU - 4633
题意：有k种颜色给3*3*3的魔方的54的面，8个点，12条棱涂色,有多少种不同的思路：要清楚正方体有多少种变换？1）不动k^( 54+12+8)2）以面的中心旋转 （90 ，180， 270 ）X 3条对称轴3*K^(9+6+3+2)3*K^(9*2+10+4+6)3*K^(9+6+3+2)3）以棱中心为对称轴旋转 6条对称轴6*
2017-11-05 20:27:38
261
原创 Arif in Dhaka (First Love Part 2) UVA - 10294
#includeusing namespace std;#define ll long longll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);}ll qpow[100];ll s1(ll n, ll t){ ll ans=0; for(ll i=0;i<n;i++) { ans+=qpow[gcd(i,n)]; } retu
2017-11-05 19:58:48
216
转载 Polya定理，burnside引理
Polya定理设 是n个对象的一个置换群, 用m种颜色染图这n个对象，则不同的染色方案数为：其中 ， 为 的循环节数解题主要在于写出置换群， 明确置换群的个数，每个置换群的循环节数比如正四面体：应用（正多面体的刚体旋转问题）甲烷CH4的支链结构为正四面体，若4个H键用H,CL
2017-11-05 19:48:23
1198
原创 UVALive 7040 Color 容斥原理 + 组合数学递推公式 +lucas
题意： 给你m种颜色，你要选出其中k种并全部用上去给那朵花涂颜色，相邻两朵花的颜色要不同有几种方案 思路： 设dp[k]为刚好用k种颜色的答案 如果k种颜色不用完则ans=k*(k-1)^（n-1） 则 dp[k]=ckk*f(k)-ckk-1*f(k-1)+ckk-2*f(k-2)-….#include<bits/stdc++.h>using namespace std;#defi
2017-10-25 16:49:27
230
原创 HDU 4793 Collision
几何题：分析如下图：三种边界情况：碰撞不碰撞但过大圆不过大圆尤其注意速度方向可能使得他远离原点#includeusing namespace std;const double eps =1e-8;int sgn(double x){ if(fabs(x)<eps )return 0; if(x>0) return 1; return -1;}i
2017-09-29 10:35:33
205
原创 HDU 4801 Pocket Cube
题意：问魔方在N步内，最多可以还原几个面思路：暴力#includeusing namespace std;int p[3][3][4]={ {{1,21,17,7},{8,9,15,14},{3,23,19,13}},{{1,4,18,15},{23,22,20,21},{0,10,19,9}},{{23,8,6,4},{0,1,3,2},{22,9,7,5}}};
2017-09-29 10:15:50
190
原创 2017 ACM-ICPC GSM Base Station Identification
题意：建立400个六边形，给出10个点的坐标，问点在哪个六边形内思路：刚开始的时候想了一堆东西发现都不怎么好然后想可以遍历每个六边形的中心点，可以贴一个点是否在多边形内的板子但是转念一想，六边形比较像一个圆，点又都是整数点，试了一下离点距离小于5，2.5sqrt（3），发现都过了，数据还是太水了晚上想了想最稳的应该是遍历400个中心点，找出离给定点距离最近的那个
2017-09-25 15:24:21
217
原创 HDU 4336 Card Collector 动态规划-概率DP
题意：给出每张卡片的概率，求集齐卡片要买的方便面的包数的期望思路：太弱了，不会写，看了大佬们的博客才明白，争取下次能自己想粗来。。。将一个数j二进制表示第i位代表第i张卡，0表示未得倒卡，1相反dp[j]表示当下获得卡的情况为j，此时集齐卡片要买的包数的期望显然dp[ 111111...1(2) ]=0.0;对于一个数 jdp[j]=sigma（p[1dp[j]
2017-09-22 14:14:57
224
原创 Zhu and 772002 HDU - 5833 高斯消元
题意：给出一堆数（300个以内），每个数的最大素因子不超过2000，从中取一些数，使得乘积为一个完全平方数，问有多少种取法？思路:2000以内的素数有303个不多，把每个素数素因子分解，存在一个310*310的矩阵中，因子数为偶数存0，奇数个存1我们知道要想几个数的乘积为完全平方数，就要那几个数的因子数的和为偶数a11x1+a12x2+...+a1mxm=0a21x1+
2017-09-21 10:42:28
214
原创 2017 ACM-ICPC 西安网络赛 Trig Function
题意:f(cos(x))=cos(n∗x) 对任意x都成立，问x^m在f（x）中的系数是多少？思路：由于网络赛，马上想到了傅里叶展开，或者泰勒展开，发现好像都不行干脆直接百度到倍角公式lucas定理可以求出较大的组合数，这里求和，i+1的项可以由第i项简单的得到，不必每次求一次组合数#includeusing namespace std;typede
2017-09-19 12:13:25
341
原创 2017 ACM-ICPC 亚洲区(西安赛区)网络赛 Coin
题意:抛掷一枚硬币，正面朝上的概率是p/q （p/q \frac{q}{p}(\frac{q}{p} \le \frac{1}{2})X/Ymod(1e9+7)思路：这是一个二项分布，高中数学题#include#define ll long long#define N 1000000007using namespac
2017-09-19 10:44:27
388
原创 Help Me Escape ZOJ - 3640
题意：cain在山洞里，自身有战力 f，有n条路可以粗去，随机选一条路走，路的难度为 c[i]，如果c[i]>=f，一天后cain回到山洞，战力变为c[i]+f否则经过v[i]天，cain可以通过这条路离开，问cain离开洞穴需要天数的期望思路：dp[i]存战斗力为i时离开的数学期望遍历每条路，如果f>e[i],dp[f]+=(1/n)*v[i[;不然递归解决求出dp[
2017-09-15 15:28:06
244
原创 Scout YYF I POJ - 3744
题意：有一个无限长的路，路上布满地雷，初始在位置1，每次 p 的概率到下一格，（1- p）的概率到下二格给出 p 以及地雷坐标a[i]，问安全走过的概率是多少？思路：递推，用矩阵快速幂推，p[ a[i] +1 ] 推到 p[ a[i+1] -1 ] ，于是p[ a[i+1] +1 ] = p[ a[i+1] -1 ] *（1-p） #include
2017-09-14 15:09:08
200
原创 Maze HDU - 4035 hdu
题意：一道过程很有趣的概率dp在一棵树上你在节点1（根节点），每个节点有一定概率k[i]被杀回到1号根节点，和一定概率e[i]逃离迷宫还有剩下的概率往下一步走可以走向相邻的任何节点问离开迷宫走的步数的期望是多少？思路：这个题目和 ZOJ 3329 One Person Game(概率DP,求期望)一样每一部都是可以通过一定概率回到第一步的即每一步的期望都有根
2017-09-13 15:43:26
264
原创 POJ2151：Check the difficulty of problems(概率DP)
题意：有T支队伍，M道题,每队最少做一题，冠军最少做n道题，给出第i队出第j题的概率思路：不会写看了别人的题解才过的我觉得s[i][k]表示的是比赛结束时第i队最多出k题目的概率#include#define N 32#define T 1003#define M 32double dp[T][M][N];double s[T][M];double p[T][M]
2017-09-12 13:48:31
192
原创 hdu 6202 cube cube cube 沈阳区域赛网络赛 （膜拟）
题意：给一个特殊魔方的颜色图案，问你能不能在三步内还原魔方如果不懂魔方的转动可以看这个视频http://www.bilibili.com/video/av8452301/?from=search&seid=11750270100959783079思路：emmmm。。。。。比赛的时候有随机数交过的。。。模拟魔方转动过程。。。这可能不太好想所以拿起身边的草稿纸开始动
2017-09-11 16:57:26
597
原创 HDU3853:LOOPS
题意：进入迷宫，从（1，1）走到（n,n）花费2个magic power，可以改变自己的位置在(i,j)时，有一定几率留在原地，有一定几率到达（i+1，j），有一定几率到达（i，j+1）问到达（n，n）花费magic power的期望思路：e[i][j]= e[i][j]*p1 + e[i+1][j]*p2 + e[i][j+1]*p3+2e[i][j]= (1/(1
2017-09-07 17:19:43
148
原创 poj2096 Collecting Bugs
题意：据说是一道经典老题了一个程序员一次操作可以找到一个bug和一个subcomponent问找到n个bug和n个subcomponent操作次数的数学期望是多少思路：又是套路我们e[i][j]保留的是 当找到 i个 bug 与 j 个 subcomponent 时还需要多少操作可以完成任务的期望a=i/n;b=j/s;e[i][j]=a*b*e[i]
2017-09-07 16:41:27
136
原创 ZOJ 3329 One Person Game(概率DP,求期望)
题意：抛三个色子，三个色子分别为k1,k2,k3个面，如果抛出的色子第一个为a，第二个为b，第三个为c这counter置0，否则加上（a+b+c）思路：还是不会啊果然太弱了看了大佬们的博客慢慢的学会了点东西同样e[i]表示从i到n的期望e[i]=sigma(p[j]*e[i+j])+p[0]*e[0]+1e[i]=A[i]*e[0]+B[i];
2017-09-07 15:22:34
142
原创 HDU 4405 Aeroplane chess
题意：飞行棋n+1个格子m条 flight lines ，每条表示 a，b可以直接到达问从0到 n，掷色子的次数d
2017-09-06 17:03:30
139
原创 Codeforces 148D：Bag of mice
水题注意下递推#include#define N 1001using namespace std;double p[N][N];int main(){ int w,b; double ans,t,t1,t2;while(~scanf("%d%d",&w,&b)) { ans=0.0; memset(p,0,sizeof(p)); p[w][b]=1.00;
2017-09-06 15:10:03
133
原创 uva11551experienced endeavour
题意：给你个长为n的数列 a给你一个变换n行，第一个数为，后跟着几个数，表示经过一次变换后的数由原序列哪几个数组成#includeusing namespace std;const long long N=1000;int n;struct node{ long long a[55][55];};node cheng(node a,node b){ no
2017-09-04 16:12:08
204
原创 hdu5728PowMod
题目：给定 n,m,p先得到 k=∑mi=1φ(i∗n) mod 1000000007k=∑mi=1φ(i∗n) mod 1000000007其中n为非平方数再计算ans=kkkk...k mod p这里有无穷个k思路：1。求k欧拉函数是非完全积性函数，φ(a*b)=φ(a)*φ(b)，当gcd(a,b)=1;φ(i*n)=φ(a)*φ(b)
2017-08-29 15:37:23
259
原创 HDU 6134 Battlestation Operational
题意：求 f(n)=∑i=1n∑j=1i⌈ij⌉[(i,j)=1]思路:比赛的时候不会写，看了别人的博客半天才看懂，看来理解还是不够深啊这里就不推导了重新对欧拉函数，莫比乌斯函数，还有那个因子数的积性有了新的理解欧拉函数：我们知道由于欧拉筛法，每次我们都遍历一个素数 j如果 n%j==0 说明 n中存在素因子j ，那么在euler[n]中已经
2017-08-29 10:12:53
224
原创 uva 10518 How Many Calls?
题意：递归求斐波那契数列，求递归次数，即节点个数思路：我们分析可以得到递归次数同样是前两个答案的和加1ans[i] =ans[i-1]+ans[i-2]+11 ， 1， 3，5，9，15，25。。。。。同时又发现 ans[i]是第i个斐波那契数的两倍减1#includeusing namespace std;long long N;struct node
2017-08-24 11:45:48
233
原创 HDU - 4565 So Easy!
题意：给出a,b,n,m;0求思路：不会写，看来别人的博客补的。。。。。。题目重点在于(a-1) 2即 a-1(a−√b) (a−√b)^n 令 cn= (a+√b)^n + (a−√b)^n 这里提到 (a+√b)^n 与 (a−√b)^n 共轭，所以二者相加的cn为整数 又因为 (a-sqrt(b
2017-08-18 14:33:15
234
原创 uva 10870 Recurrences
题意：给你d,n,m,a1,a2,a3,......f(1),f(2),f(3),f(4).......定义：f(n) = a1f(n − 1) + a2f(n − 2) + a3f(n − 3) + . . . + ad f(n − d), for n > d求 f（n）%m思路：不多说水题#includeusing namespace std;struct
2017-08-18 13:43:36
152
原创 (2017多校训练第七场)HDU - 6129 Just do it
题意：给出 n,m , 和 a1,a2.........an每次操作都会有，bi=a1^a2^a3^...ai ('^'为异或)求m次操作后的序列思路：比赛的时候一直在想找规律，发现了循环，就觉得这是正确方向，最后可以在O（n）的复杂度，知道m后bi由那些数异或而成，这时才发现即使知道了也要O（n2）的遍历才可以得出最后的序列，这时发现方向错了。。。。期间队友还提过组合数
2017-08-16 15:47:44
223
原创 uva 10655 Contemplation! Algebra（矩阵快速幂）
题意：给出p=a+b ,q=a*b ,n求 a^n+b^n思路：由于在矩阵快速幂的专题里一开始就想a2+b2 =(a+b)(a+b)-2ab又往下推发现a3+b3=(a2+b2)(a+b)-a2b-ab2 =(a2+b2)(a+b)-(a+b)ab又继续往下推
2017-08-16 13:54:26
213
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人