[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[][];
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=;i<=m;i++)gcd[][i]=i;
for(int i=;i<=n;i++)gcd[i][]=i;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
getgcd(i,j);
}
int main()
{
scanf("%d%d",&n,&m);
calc();
t=(n+)*(m+);
ans=t*(t-)*(t-)/;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (i||j)
{
if (!i||!j)ans-=(LL)(gcd[i][j]-)*(n-i+)*(m-j+);
else ans-=(LL)*(gcd[i][j]-)*(n-i+)*(m-j+);
}
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 = , ans = ;
M[]++;//M[0]=1
while(n--)
{
cin >> x;
res^=x;
if(M[res])//后面位置j有出现异或值和位置i的值一样
{
M.clear();
ans++;//每重复出现一次就清空一下所有信息并且答案++
}
M[res] = true;
} cout << ans << endl;
}
return ;
}
非均匀的概率生成器=>等概率
非均匀的概率生成器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的话，就是这个数出现的次数。这样就做到了没有开辟额外的空间。