目录
今日知识点:
基于涂色问题的组合数
求所有数的最大公约数
阶乘质因数分解
哥德巴赫猜想
越狱
找朋友
全部相同
方形
tax
越狱
监狱有n个房间,每个房间关一个犯人,有m种宗教,一个犯人信仰一种。如果相邻的房间犯人信仰同一种宗教就会越狱。问有多少种可能发生越狱
输入
2 3
输出:6
思路:
直接反正做:把总情况数减去不会发生越狱的情况数。
总情况数是m^n。
不会发生越狱的情况数是m*(m-1)^(n-1)。因为只有第一个人可以随意信仰宗教,其余人只需要和上一个人的不同即可。反正就是高中学过的涂色问题
#includeusing namespace std; typedef long long ll; const int mod=1007; ll ans,m,n; ll qpow(ll a,ll b){ ll res=1; while(b){ if(b&1){ res=res*a%mod; } a=a*a%mod; b>>=1; } return res; } int main(){ cin>>m>>n; ans=qpow(m,n)-qpow(m-1,n-1)*m%mod; ans=(ans%mod+mod)%mod; cout<
找朋友
n个人分成m组,每组至少一个人,在比赛结束的时候同一组的人两两之间就会成为朋友,不同的分组方案得到的朋友对数不同。求出最小和最大的朋友对数。
输入:
5 1
输出:10 10
思路:
很明显最大的朋友对数,一定是其余组只有一个人,剩余的人都在一个组中。
最小的朋友对数,一定是每组人数尽量相同。即可
#includeusing namespace std; typedef long long ll; int n,m,maxn,minn,tmp,tmp2; int main(){ cin>>n>>m; tmp=n-(m-1); maxn=tmp*(tmp-1)/2; tmp=n/m; tmp2=n%m; minn=(tmp*(tmp-1))/2*(m-tmp2)+(tmp*(tmp+1))/2*tmp2; cout<
全部相同
一共有n个整数组成的数组a1,a2,……现任取一个正整数k进行下面操作:
从数列中取出一个数ai减去k。一共进行了若干次(可能是0次)操作后,数列中所有的数都相等了。请你找出k的最大可能取值。(如果k可以任意大输出-1)
输入 输出:2
3 1
6 1100
1 5 3 1 1 5
8
-1 0 1 -1 0 1 -1 0
4
100 -1000 -1000 -1000
思路:
很明显我们要把其余的数都变成最小的数。那么k必然是那些数的最大公约数才行。然后当原数据就已经完全相等的时候自然只需要操作0次就行,那么k可以任意大
#includeusing namespace std; int t,n,a[50]; int gcd(int a,int b){return b==0?a:gcd(b,a%b);} int main(){ cin>>t; while(t--){ cin>>n; for(int i=0;i >a[i]; sort(a,a+n);//默认升序 for(int i=1;i
方形
思路:
只需要用上高中的知识不难发现是:C(m,m+n)。然后就是计算了。这里肯定是要用上高精度了 。
C(m,m+n)=(m+n)! / (m)! / (m+n-m)!=(m+n)…(n) / (m)!
然后计算阶乘完全可以写成质因数分解的形式,然后高精度除法就被转化成了质因数的次方相减。
最后再进行高精度乘法即可。
#includeusing namespace std; const int N=1e5+5,N2=105; int n,m; int fac[N],a[N2]={1},c[N2]; void clear(int c[]){ for(int i=0;i =10){ c[i+1]+=c[i]/10; c[i]%=10; } } } int main(){ cin>>m>>n; n=n+m;//求C(m,m+n) for(int i=n-m+1;i<=n;i++){//计算分子的阶乘 int tmp=i;//对每个数进行质因数分解 for(int j=2;j*j<=tmp;j++){ while(tmp%j==0){ fac[j]++; tmp/=j; } } if(tmp>1) fac[tmp]++; } for(int i=1;i<=m;i++){ int tmp=i; for(int j=2;j*j<=tmp;j++){ while(tmp%j==0){ fac[j]--; tmp/=j; } } if(tmp>1) fac[tmp]--; } for(int i=2;i =0;i--){ if(i%10==0) cout<
tax
一个人前来交税,交的税钱是收入n的最大因子(不等于n的最大因数),但是现在这个人为了避税,把前拆成几份(每份至少为2),使得交税最少,输出税钱。
输入4
输出2
思路:
首先这个数据量极大,没法模拟!然后我们也不需要模拟
根据哥德巴赫猜想,偶数都可以分解成两个质数,那么大于2的偶数只需要交2即可
如果这个是质数,那么交1即可
如果这个数是奇数,那么必然可以拆成一个质数和一个偶数,也就是交3即可
#includeusing namespace std; int prime(int n){ for(int i=2;i*i<=n;i++){ if(n%i==0){ return 0; } } return 1; } int main(){ int n;cin>>n; if(n%2==0&&n>2){cout<<2;return 0;} if(n==2){cout<<1;return 0;} if(prime(n)){cout<<1;return 0;} if(n%2){cout<<3;return 0;} }