做页面设计的网站,怎么注销网站,企业历史展厅设计,西安哪家公司做网站好前言
今天第一次正式C组题#xff0c;不过……比较恐怖。 正题 题目1#xff1a;公牛和母牛#xff08;jzoj1292#xff09;
有n头牛#xff0c;可以是公牛或母牛#xff0c;每头公牛之间至少得有k头母牛。求方案数。
输入输出#xff08;建议跳过#xff09;
Inpu…前言
今天第一次正式C组题不过……比较恐怖。 正题 题目1公牛和母牛jzoj1292
有n头牛可以是公牛或母牛每头公牛之间至少得有k头母牛。求方案数。
输入输出建议跳过
Input
第一行两个空格隔开的整数NN100000和K。
Output
输出一个整数表示方法总数答案可能很大所以只需输出mod 5,000,011的值即可。
Sample Input
4 2
Sample Output
6
解题思路
推出动态转移方程用f[i]来表示i头牛的方案数。
f[i]f[i−1]1(ik1)f[i]f[i−1]1(ik1)
f[i]=f[i-1]+1 (i f[i]f[i−k]f[i−1](ik1)f[i]f[i−k]f[i−1](ik1)
f[i]=f[i-k]+f[i-1] (i>k+1) 因为如果在i处放置了公牛那么前k个就不能放所以是f[i-k]放母牛的话就累加之前的方案数f[i-1]代码
#includecstdio
using namespace std;
int n,k,f[100001];
int main()
{scanf(%d%d,n,k);k;//加f[0]1;//初始化for (int i1;in;i){if (ik){f[i](f[i-k]f[i-1])%5000011;//动态转移}else{f[i](1f[i-1])%5000011;//动态转移}}printf(%d,f[n]);//输出
} 题目2最短路jzοj3777
每个点的权值遵守以下规律 f[1][1]1 f[i][j]f[i-1][j]f[i][j-1] 然后求(1,1)到(m,n)的最小权值 mod 10000000007。
输入输出建议跳过
Input
一行两个正整数N,M表示图的大小。
Output
一行一个整数Ans表示答案模1000000007后的值。
Sample Input
1 2
Sample Output
6
解题思路
杨辉三角也就是组合然后用快速幂求组合公式
cnmn!m!(n−m)!cmnn!m!(n−m)!
c_m^n=\frac{n!}{m!(n-m)!} 然后取膜的快速幂 cnm(modp)((m!(n−m)!)∗m!(p−2)(modp)n)(modp)cmn(modp)((m!(n−m)!)∗m!(p−2)(modp)n)(modp)
c_m^n(modp)=((m!(n-m)!)*m!^(p-2)(modp)+n)(modp)代码
#includecstdio
#includealgorithm
#define mod 1000000007
using namespace std;
long long n,m,s,x,y;
long long qsm(long long x,long long c)//快速幂
{long long ans1;while (c){if (c1) {ans(ans*x)%mod;}x(x*x)%mod;c1;}return ans;
}
int main()
{scanf(%lld%lld,n,m);if (nm) swap(n,m);x1;y1;for (long long in2;inm1;i) x(x*i)%mod;//求m!(n-m)!for (long long i1;im;i) y(y*i)%mod;//m!printf(%lld,(x*qsm(y,mod-2)%modn)%mod);//公式
} 题目3Magical GCDjzoj3780
给出一个长n的序列i到j的价值为i到j的最大公约数乘以它的长度。求最大价值
输入输出建议无视
Input
单个测试点包含多组数据。 输入的第一行是一个整数T表示数据组数。 每组数据的第一行是一个整数N描述序列长度。 接下来N个数字描述这个序列元素A[i]。
Output
对于每组测试数据输出一行包含一个整数表示序列最大的 Magical GCD。
Sample Input
1 5 30 60 20 20 20
Sample Output
80
解题思路
暴力枚举左到右会超时所以我们用g[i]表示从i到r的gcd。 然后我们会发现这样会有许多重复的只要我们过滤掉重复的gcd就好了。 所以我们先用一个右指针和左指针发现重复时就可以利用指针在下次枚举时无视自己
代码
#includecstdio
#includeiostream
#define ll long long
using namespace std;
int ls[100001],nx[100001],t,n;
ll a[100001],g[100001],maxs;
ll gcd(ll x,ll y)//辗转相除法
{if (x%y0) return y;else return gcd(y,x%y);
}
int main()
{scanf(%d,t);for (int ti1;tit;ti){maxs0;scanf(%d,n);for (int i1;in;i){scanf(%lld,a[i]);g[i]a[i];nx[i]i1;//左指针ls[i]i-1;//右指针}for (int r1;rn;r)for (int i1;ir;inx[i]){g[i]gcd(g[i],a[r]);//求最大公约maxsmax(g[i]*(r-i1),maxs);//求最大值if (g[i]g[i-1])//发现重复{nx[ls[i]]nx[i];//修改指针让下次无视自己ls[nx[i]]ls[i];//同上}}printf(%lld\n,maxs);}
} 题目4Multisetjzoj3781
有一个数0有以下两种操作 让一个数增加xx1 将一个数分裂为两个非负整数 给出一个序列求出至少要多少次操作才可以变为这个序列
输入输出建议无视
Input
第一行为一个整数N描述最终集合的大小。 第二行为N个非负整数为最终集合的每一个元素。
Output
输出唯一一行Alice 最少玩的轮数。
Sample Input
Sample Input 1 1 0
Sample Input 2 4 1 1 1 1
Sample Input 3 5 0 3 0 3 0
Sample Output
Sample Output 1 0 Sample Output 2 3 Sample Output 3 5
解题思路
首先感谢纪中dalao的帮助 反推就变成了减去1和合并这两种操作。 然后贪心用桶w[i]来表示在第i步有多少个数会变为0
代码
#includecstdio
#includeiostream
using namespace std;
int n,x,maxs,s;
int w[1000001];
int main()
{scanf(%d,n);for (int i1;in;i){scanf(%d,x);w[x];//桶maxsmax(maxs,x);//记录最大值}sw[0];//0的个数for (int i1;imaxs;i){s(s1)/2w[i];//合并0并加入新的0}while (s1) {s(s1)/2;maxs;}//合并剩余部分printf(%d,maxs);//输出
}
