leetcode 几何题 位运算 面试编程
[BZOJ][CQOI2014]数三角形
Description
给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。
注意三角形的三点不能共线。
Input
输入一行，包含两个空格分隔的正整数m和n。
Output
输出一个正整数，为所求三角形数量。
Sample Input
2 2
Sample Output
76
数据范围
1<=m,n<=1000
首先答案就是所有取出三个点的方案数减去会三点共线的方案数
显然n*m的网格上有(n+1)*(m+1)个整点，然后令t=(n+1)*(m+1)，那么取三个点的方案数就是t*(t-1)*(t-2)/6（就是排列组合啦）
然后要考虑怎么算三点共线的方案数
然后有一个结论是在(a,b) (x,y)两点构成的线段上有gcd(a-x,b-y)-1个整点(a>x,b>y)
我们固定(a,b) (x,y)为共线的三点中左边两个，那么第三个点的方案数就是gcd(a-x,b-y)-1
但是这样枚举abxy的复杂度是O(n^2*m^2)
优化是把这线段平移到原点处，那么会发现其实只要枚举(0,0) (x-a+1,y-b+1)，其他的线段平移就可以了（这里强烈建议自己动手画一画！）
画完很容易发现这样(0,0) (x-a+1,y-b+1)的线段可以平移出(n-i+1)*(m-j+1)种不同方案，在 (x-a+1,y-b+1)的时候如果不在坐标轴上还要算两次
#include<cstdio> #define LL long long int gcd[1010][1010]; int n,m; LL t,ans; inline int getgcd(int a,int b) { if (gcd[a][b])return gcd[a][b]; if (!a)return gcd[a][b]=b; if (!b)return gcd[a][b]=a; return gcd[a][b]=getgcd(b,a%b); } inline void calc() { for(int i=1;i<=m;i++)gcd[0][i]=i; for(int i=1;i<=n;i++)gcd[i][0]=i; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) getgcd(i,j); } int main() { scanf("%d%d",&n,&m); calc(); t=(n+1)*(m+1); ans=t*(t-1)*(t-2)/6; for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) if (i||j) { if (!i||!j)ans-=(LL)(gcd[i][j]-1)*(n-i+1)*(m-j+1); else ans-=(LL)2*(gcd[i][j]-1)*(n-i+1)*(m-j+1); } printf("%lld",ans); }
最多不重叠的非空区间xor=0
给出ｎ个数字a_1, …., a_n，求最多有多少个不重叠的非空区间，使得每个区间内数字的异或(xor)都为0。
即找出最大的k，使得存在k个区间(l(i),r(i))，满足
1<=l(i)<=r(i)<=n (1<=i<=k)， r(i)<l(i+1) (1<=i<k)，且
a[l(i)] xor a[l(i)+1] xor …. xor a[r(i)] ==0 (1<=i<=k)
例如：
当输入为[3, 0, 2, 2]时，答案为2，存在2个区间[1] 和 [2, 2]满足；
当输入为[2, 2, 0, 2, 2]时，答案为3，[2, 2],[0] 和[2, 2]满足。
解题思路：首先要读懂题意，不重叠的区间，区间需要连续，某些数可以不选，划分为最多的区间，区间的所有的数异或结果为0。
然后我们解题的时候可以保存从头开始一直异或到当前位置i的值，如果后面位置j有出现异或的值和位置i的值一样的话，那么区间[i, j]就是一个异或结果为0的区间。
所以我们可以用一个set或者map更新一下。每重复出现一次就清空一下所有信息并且答案++，然后重新保存set或map。开始的时候要放一个map[0]为了考虑边界条件（也就是一开始就是0的情况）。
#include <iostream> #include <map> using namespace std; int main() { int n, x; while(cin >> n) { map<int, bool> M; int res = 0, ans = 0; M[0]++;//M[0]=1 while(n--) { cin >> x; res^=x; if(M[res])//后面位置j有出现异或值和位置i的值一样 { M.clear(); ans++;//每重复出现一次就清空一下所有信息并且答案++ } M[res] = true; } cout << ans << endl; } return 0; }
非均匀的概率生成器=>等概率
非均匀的概率生成器myRandom，能够不等概率的生成0 or 1
现在给定数值n，利用上述myRandom函数，等概率的生成1~n-1中的任意一个数值
public void get(){ int m=myRandom(); int n=myRandom(); while(1){ if(m==1&&n==0) return 1; else if(m==0&&n==1) return 0; } } public static void main(String[] args){ Scanner sca=new Scanner(System.in); int n=sca.nextInt(); int i=0; int num=0; while(n%2=0){ n=n/2; num++; } StringBuffer str=new StringBuffer(); int j=0; while(j<num){ str.append(get()+""); } return Integer.parseInt(str.toString(),2); }
n个[0,n)的数，求每个数的出现次数（不能开辟额外空间）
这里关键是看清楚题意，n个数，然后是左闭右开的区间，也就是说每个数都不会大于等于n，那么思路就来了：如果我们给一个索引i下的数不管加上多少个n，那么这个数a[i]对n取余的话，我们就能知道这个数原来是多少；另一方面，如果一个数出现一次，我们就在对应索引i位置下的数加上n，那么每个数对应索引位置上的数a[i]除以n的话，就是这个数出现的次数。这样就做到了没有开辟额外的空间。