选取计数问题CSU 1759: Triangle（选三条边构成三角形）
目录
CSU 1759: Triangle（选三条边构成三角形）
题目：
Description
给你长度为1～n n条边，请你求出有多少种组合方法数可以选出三条边构成三角形
Input
多组数据输入输出(数据组数考虑为最大可能性)
每组数据输入一个正整数n，表示有n条长度的边可供选择(n<=10000)
Output
每组数据输出可构成三角形的边的选择方法数
Sample Input
2
4
Sample Output
0
1
代码：
-
#include<iostream>
-
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<iostream>
-
#include<stdio.h>
-
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<<a/gcd(a,b)<<'/'<<b/gcd(a,b)<<endl;
-
}
-
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<iostream>
-
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<iostream>
-
#include<string.h>
-
#include<algorithm>
-
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;
-
}
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/115922107
- 点赞
- 收藏
- 关注作者
评论（0）