选取计数问题CSU 1759: Triangle（选三条边构成三角形）

目录

CSU 1759: Triangle（选三条边构成三角形）

CSU 1799 小Z的黑白棋

CSU 2049: 象棋

CodeForces 702B Powers of Two

CSU 1759: Triangle（选三条边构成三角形）

题目：

Description

给你长度为1～n n条边，请你求出有多少种组合方法数可以选出三条边构成三角形

Input

多组数据输入输出(数据组数考虑为最大可能性)

每组数据输入一个正整数n，表示有n条长度的边可供选择(n<=10000)

Output

每组数据输出可构成三角形的边的选择方法数

Sample Input

2

4

Sample Output

0

1

代码：

#include

using namespace std;

int main()

{

long long n;

while (cin >> n)cout << ((n - 1)*(n - 2)*(n - 3) / 6 + (n - 1) / 2 * (n / 2 - 1)) / 2 << endl;

return 0;

}

CSU 1799 小Z的黑白棋

题目：

Description

小Z有一些黑白棋，他觉得黑白混杂在一起极具美感，所以他总喜欢将这些棋子排成一排序列S1，但是小Y就喜欢跟小Z作对，她会趁小Z不注意偷偷将小Z最右边的棋子拿走，往他棋子序列的最左边添加一个白色的棋子形成一个新的序列S2来破坏小Z的美感。

S2(1~n) = 白棋+S1(i=1~n-1)

小Z总相信第一感，他认为他自己最初排好的序列S1是最完美的，新的序列S2会造成一定的破坏美感指数 = damage(S1) = S1与S2有多少个位置黑色与白色互不对应

Exp:

令白棋为a，黑棋为b :S1 = ababa  S2=aabab   damage(S1)=4

因为小Z有很多种摆放序列的方式，现在他希望让你帮他求所有摆放序列的方式会造成的damage(S1)的平均值

Input

多组数据输入输出

每组数据输入一个整数n和m表示白棋和黑棋的数量 0<=n , m<=1000,000,000 , 保证n+m>=1

Output

每组输出一个平均值答案，用最简分数表示，如果可以化简到整数，就用整数表示

Sample Input

1 1

Sample Output

3/2

这个题目的思想大约就是富比尼原理了。

n个白棋和m个黑棋有C(m+n,n)种排列。

其中，第一个棋子为黑棋的，有C(m+n-1,n)种

第i（i=1,2,3......m+n-1）个棋子和第i+1个棋子颜色不同的，有2*C(m+n-2,n-1)种

2*C(m+n-2,n-1)*(m+n-1)=2*n*C(m+n-1,n)

所以，本题答案是(1+2*n)*C(m+n-1,n)/C(m+n,n)=(1+2*n)*m/(m+n)

代码：

#include

#include

using namespace std;

long long gcd(long long a,long long b)

{

if(b==0)return a;

return gcd(b,a%b);

}

int main()

{

int m,n;

long long a,b;

while(scanf("%d%d",&n,&m)!=EOF)

{

a=n+n+1;

a*=m;

b=m+n;

if(a%b==0)printf("%d\n",a/b);

else cout<

}

return 0;

}

CSU 2049: 象棋

题目：

Description

車是中国象棋中的一种棋子，它能攻击同一行或同一列中没有其他棋子阻隔的棋子。一天，小度在棋盘上摆起了许多車……他想知道，在一共N×M个点的矩形棋盘中摆最多个数的車使其互不攻击的方案数。他经过思考，得出了答案。但他仍不满足，想增加一个条件：对于任何一个車A，如果有其他一个車B在它的上方（車B行号小于車A），那么車A必须在車B的右边（車A列号大于車B）。

现在要问问你，满足要求的方案数是多少 。

Input

第一行一个正整数T，表示数据组数。( T<=10)

对于每组数据：一行，两个正整数N和M（N<=100000，M<=100000）。

Output

对于每组数据输出一行，代表方案数模1000000007（10^9+7）。

Sample Input

1

1 1

Sample Output

1

就是简单的计算组合数

代码：

#include

using namespace std;

const int m = 100000;

int list[m], p[9592];//9592个素数

void getp()//在p数组中存所有不超过m的素数

{

p[0] = 2;

int key = 0;

for (int i = 0; i < m; i++)list[i] = i % 2;

for (int i = 3; i < m; i += 2)if (list[i])

{

p[++key] = i;

for (int j = i + i; j < m; j += i)list[j] = 0;

}

}

int degree(int m, int p)//求m！中素数p的次数

{

if (m)return degree(m / p, p) + m / p;

return 0;

}

int main()

{

getp();

int t, n, m, mi;

cin >> t;

while (t--)

{

cin >> n >> m;

if (n < m)n ^= m ^= n ^= m;

long long ans = 1;

for (int i = 0; i < 9592; i++)

{

mi = degree(n, p[i]) - degree(m, p[i]) - degree(n - m, p[i]);

while (mi--)ans = ans * p[i] % 1000000007;

}

cout << ans << endl;

}

return 0;

}

CodeForces 702B Powers of Two

题目：

Description

You are given n integers a1, a2, ..., an. Find the number of pairs of indexes i, j (i < j) that ai + aj is a power of 2 (i. e. some integer xexists so that  ai + aj = 2^x).

Input

The first line contains the single positive integer n (1 ≤ n ≤ 10^5) — the number of integers.

The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 10^9).

Output

Print the number of pairs of indexes i, j (i < j) that ai + aj is a power of 2.

Sample Input

Input

4

7 3 2 1

Output

2

Input

3

1 1 1

Output

3

#include

#include

#include

using namespace std;

int list1[100001];

int list2[100001];

int n;

long long f(int m)

{

for (int i = 0; i < n; i++)list2[i] = m - list1[n-1-i];

long long sum = 0;

long long temp1, temp2;

for (int i = 0, j = 0; i < n && j < n;)

{

if (list1[i] < list2[j])i++;

else if (list1[i] > list2[j])j++;

else

{

temp1 = 1;

temp2 = 1;

while (i + 1 < n && list1[i + 1] == list2[j])

{

i++;

temp1++;

}

while (j + 1 < n && list2[j + 1] == list1[i])

{

j++;

temp2++;

}

sum += temp1*temp2;

i++;

j++;

}

}

return sum;

}

int main()

{

cin >> n;

int max = 0;

for (int i = 0; i < n; i++)cin >> list1[i];

sort(list1, list1 + n);

int mi = 1;

long long sum = 0;

for (int i = 0; i < 30; i++)

{

mi *= 2;

sum += f(mi);

}

for (int i = 0; i < n; i++)

if (list1[i] == (list1[i] & (-list1[i])))sum--;

cout << sum / 2;

return 0;

}

数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。