北京培训记day4

智商题QAQ……

T1：求>=n的最小素数,n<=10^18

　　 暴力枚举n-n+100,miller-rabin筛法

T2：给定一个01矩阵，每次选择一个1并将(x,y)到(1,1)颜色反转，求先手是否必胜

　　 考虑最终状态(1,1)点一定为0，且每次翻转时点(1,1)一定会被翻转

　　 所以若(1,1)为1，先手必胜，否则先手必败

T3：给定一个长度为3*k的数组s (s[i]>=i-1)，要求构造出两个数组a,b，使a[i]+b[i]=s[i]，且a,b各删去k个数后a[i]互不相同,b[i]互不相同

　　 将s从小到大排序后分成3组，使a[i] (from 1~k)=i-1，b[i] (from k~2*k)=i-1 ,b[i] (from 2*k~3*k)=3*k-i

　　 例:s=0 1 2 | 3 4 5 | 6 7 8

　　　  a=0 1 2 | 0 0 0 | 4 6 8

　　　  b=0 0 0 | 3 4 5 | 2 1 0

T4：给定区间[l,r]以及次数k，要求至多选出k个位于[l,r]的数，使其亦或和最小

　　 分类讨论...

　　  r-l<=10：直接暴力枚举选不选

　　  r-l>10:

　　　　　　　k=1：ans=l

　　　　　　　k=2：ans=1 (相邻两个数亦或=1)

　　　　　　　k=3：ans<=1

　　　　　　　k>=4：ans=0 (两对相邻的数亦或)

　　 考虑k=3时，考虑3个数亦或是否可以为零

　　 构造：选出一个较小的数，和两个在2进制下比其高一位的数，使前一个数尽量小且后两个数尽量平衡

　　　　　 则较小的数为l，若l某位为0，则其余两数此位为0，否则其余两数此位为0,1，最后若3个数都<=r，ans=0，否则ans=1

　　　　　 例：l=100101

　　　　　　    num1=1100000

　　　　　　　 num2=1000101

T5：给定n个点m条边 (n为偶数)，点有点权，边有边权，每次两人轮流取一个点，收益为点权，若一个人同时得到了一条边两端的点，则获得边权，问先手-后手的最大收益

　　 考虑每次选一个点代表获得此点的点权和与此点相邻的边的边权的1/2，贪心选取即可

T6：给一个n*m的01矩阵 (n,m<=1000)，其中有k位被确定 (k<(max(n,m))，求使每行每列亦或和都为1的方案数%1e9+7

　    因为k<max(n,m)，所以一定有某行或某列全部为空，假设是最后一行

　    那么其余n-1行中每一行需要一位保证正确性，其余位可以随意填，方案数为2^(k[i]-1)，k[i]=0时方案数为0或1，k[i]表示此行的空余位数

　    所以总方案数=∏2^(k[i]-1)

　    考虑无解：①k=0的时候此行亦或和=0

　　　　　  　  ②n,m不同奇偶 (最后一行亦或和=0)

T7：有m个鸡蛋n层楼，问测出鸡蛋的硬度需要至多多少次，n<=1000000000

　　 dp[i][j]表示用i个鸡蛋摔了j次能能测出的最高楼高

　　 初始状态：dp[1][j]=j，dp[i][0]=0

　　 转移方程：dp[i][j]=dp[i-1][j-1]+dp[i][j-1]+1

　　 复杂度分析：当i=2时，分块摔鸡蛋，所以至多O(sqrt(n))

T8：给定数组a，求(a1,a1),(a1,a2),(a1,a3)...,(a1,an)的次大公因数，(n<=10w)

　　 首先次大公因数=最大公因数/最小质因子

　　 先将a1质因数拆分，然后去匹配a2~an，直接求即可。

T9：Noip2014解方程，各种黑科技&白科技自行百度QAQ

T10：多组询问(<=1w)某个数各个位数和为n，平方和为m，求该数最小值 (大于100位当做无解处理)，n,m<=w

　　   考虑dp，0肯定不填，因为位数<=100，所以n<=900,m<=8100,其余输出无解

　　　dp[i][j]表示和为i，平方和为j的最小位数，转移为dp[i][j]=min(dp[i-k][j-k^2])，(k=1~9)

　　   询问时查询dp[i][j]，枚举每一位即可，复杂度O(T*9*100+9*900*8100)

T11：给一个n*m的区域，有总共p个白球和q个黑球，白球单独占1行1列，黑球每行或列最多再放一个黑球，求方案数

　　　考虑对于一个黑球，只有三种可能：单独占一行一列，与另一个黑球共占一行，与另一个黑球共占一列

　　   考虑dp

T12：给定一颗n个节点的树，每个节点可以为0,1或null，每个叶子的颜色由离它最近的祖先决定，已知所有叶子的颜色，任选一个根，使非空节点个数最少

　　   根节点选哪个呢QwQ~

　　   所以任选一个根，考虑dp，dp[i][0/1]表示以i为根的子树根节点为0/1的最小代价

　　   转移：dp[i][0]=Σ { min(dp[son[i]][0]-1,dp[son[i]][1]) }+1，dp[i][1]同理

　　　ans=min(dp[root][0],dp[root][1])

　　   复杂度：O(n)

T13：给定3个互质的数a,b,c和一个数m，构造出一组解x,y,z，使x^a+y^b=z^c (%m)

　　　显然2^(k*a*b)+2^(k*a*b)=2^(k*a*b+1)

　　   当m不为2的幂次时，

　　　根据上式，构造一个k使(k*a*b+1)%c=0，即(k*a*b+1)=c*l，用exgcd求出

　　　则x=2^(k*b),y=(2^k*a),z=2^l

　　　否则

　　　若a>1,则x=m/2,y=z=1;b>1同理

　　　若c>1,则x=y=z=m/2

　　　若a=b=c=1,则x=y=1,z=2

T14：给一个n*m的区域和c种颜色，每种颜色有a[i]个，将颜色填入方格中，使一行一列不存在不相同的颜色(可以不填)，求方案数

　　   考虑dp，dp[i][j][k]表示前i种颜色占了j行k列的方案数

　　   枚举i+1,x,y，表示第i+1种颜色占满x行y列，即可转移到dp[i+1][j+x][k+y]

　　   引入g[x][y]表示放满x行y列的方案数

　　　则转移时dp[i+1][j+x][k+y]=dp[i][j][k]*(C(x*y,a[i+1])-Σ(g[i][j] (i!=x||j!=y)*C(x,i)*C(y,j))*C(j+x,x)*(k+y,y)

　　　复杂度O(c^4*n*m)

T15：给定一个n*m的矩阵，找出一个子矩阵，使4个端点最小值最大，n,m<=1000

　　　 考虑二分答案，将其转化为一个01矩阵，利用扫描线，维护列上的二元组，如果出现两个相同的二元组则ans成立

T16：给定一张n个点m条有向边的图，构造每一条边的边权，使得1~x的最短路d[x]存在i，满足d[1]<d[2]<...<d[i]>d[i+1]>..>d[n]

　　　题目可以转化为是否存在一个拓扑序满足以上遍历条件

　　　即维护一个two-pointers，找到l+1或r-1，使已选集合可以连向它

　　　复杂度O(m)

T17：长度为len的环上有n个苹果，每次最多能背x个，可以在原点卸下，求最小时间

　　　走法一共有三种：左边上去再下来，右边上去再下来，绕一个圈

　　　预处理左边取i个的时间，右边取i个的时间

　　　考虑绕圈只可能有一次(或者没有)，且一定是还剩下x个时绕圈

　　　直接拿two-pointers维护，贪心即可

　　　复杂度O(n)

T18：T组数据(T<=12w)，已知x+y=a，lcm(x,y)=b，求x,y

　　　设gcd(x,y)=l，则x=i*l，y=j*l，则i*l+j*l=a,i*j*l=b

　　　因为i,j互质，所以gcd(i,j)=1，即gcd(a,b)=l

　　　联立{i+j=a/l,i*j=b/l}解i,j即可

T19：给定点集S，一个点(x,y)可以被取当且仅当对于已取点集T，x>∀xi∈T或y>∈yi∈T，两个人轮流取点，不能取的人输，问先手必胜or必败

　　　考虑如果有一个x最大且y最大的点，则先手必胜

　　　否则，所有x最大的点集以及y最大的点集都不能取(取了就输)，视为将其删掉

　　　递归

T20：给定一张图，占领一个点需要a[i]的兵力，占领一条边当且仅当此边两端的点的兵力和>=b[i]，空降1兵力到一个点需要c[i]的代价，求占领所有点的最小代价

　　　先做一遍最小生成树，考虑并查集，按边权从小到大加边，考虑加边i~j把两个联通块S,T联通的代价，dp[i]=min(dp[S]+dp[T],min(c[S∪T]*b[edge]))