比完赛就没做题了，现在补上
Hdu 5407 CRB and Candies
链接
CRB and Candies
题意
给定一个数N,求LCM(C(N,0),C(N,1),…,C(N,N))
分析
令g(N) = LCM(C(N,0),C(N,1),…,C(N,N))，f(n) = LCM(1,2,…,n)
则g(n) = f(n+1)/(n+1) 为所求答案 (虽然不知道怎么证明…)
求最小公倍数可以用分解素因子思想，最小公倍数等于它们所有的质因数的乘积(如果有几个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数)
也可以用结论：$f(1)=1,若n=p^k,f(n)=f(n-1)*p,否则f(n)=f(n-1)$
这个结论也是用的分解质因子的思想，设num[i]为数1到n素因子i的最大个数，
若$n=p^k$，则num[i]=k,而num[n-1]=k-1,所以只需在f(n-1)基础上乘一个p即可，
否则$n=p_1^{k_1}*p_2^{k_2}* \cdots *p_n^{k_n},则num[ p_i ] >= k_i$,即不需要乘上额外的素因子
求完LCM还需要除以(n+1),最终答案还要取余，本题数据量较大，还涉及到除法和取余，可以用费马小定理，由定理得：a^(p-1)≡1%p —> a^(p-2)≡(1/a)%p，因为p很大，需要用快速幂取余来做
利用分解素因子代码(390MS)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1000001;
const LL mod=1000000007;
int m,a[N+10]={1,1,0},b[N+10],num[N+10];
LL lcm[N+10];
LL powMod(LL a,LL b)
{
LL ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
void init()
{
m=0;
for(int i=2;i<=N;i++){
if(!a[i]){
num[m]=1;
b[m++]=i;
for(int j=i+i;j<=N;j+=i)
a[j]=1;
}
}
lcm[1]=1;
for(int i=2;i<=N;i++){
lcm[i]=lcm[i-1];
int temp=i;
if(!a[temp]){
lcm[i]=lcm[i]*temp%mod;
continue;
}
for(int j=0;j<m&&b[j]*b[j]<=temp;j++){
int cnt=0;
while(temp%b[j]==0){
cnt++;
temp/=b[j];
}
if(cnt>num[j]){
for(int k=1;k<=cnt-num[j];k++)
lcm[i]=lcm[i]*b[j]%mod;
num[j]=cnt;
}
}
}
}
int main()
{
int T,n;
init();
scanf("%d",&T);
while(T--){
scanf("%d",&n);
LL ans=lcm[n+1]*powMod(n+1,mod-2)%mod;
printf("%I64d\n",ans);
}
return 0;
}
|
利用结论代码(31MS)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1000001;
const LL mod=1000000007;
bool a[N+10]={1,1,0};
int m,b[N+10];
LL lcm[N+10];
LL powMod(LL a,LL b)
{
LL ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
void init()
{
memset(b,-1,sizeof(b));
for(int i=2;i<=N;i++){
if(!a[i]){
for(int j=i+i;j<=N;j+=i)
a[j]=1;
for(LL j=i;j<=N;j*=i)
b[j]=i;
}
}
lcm[1]=1;
for(int i=2;i<=N;i++){
lcm[i]=lcm[i-1];
if(b[i]!=-1)
lcm[i]=lcm[i]*b[i]%mod;
}
}
int main()
{
int T,n;
init();
scanf("%d",&T);
while(T--){
scanf("%d",&n);
LL ans=lcm[n+1]*powMod(n+1,mod-2)%mod;
printf("%I64d\n",ans);
}
return 0;
}
|
Hdu 5410 CRB and His Birthday
链接
CRB and His Birthday
题意
CRB有M块钱，要去商店买礼物，商店有N种礼品，第i种礼品单价为Wi,若买x个，
将获得Ai*x+Bi块糖果，求CRB最多可获得多少糖果？
分析
可以用背包思想来做，对于第i种礼品，可拆分成两种礼品，第一种费用为Wi,价值为Ai+Bi
只有一个，为01背包问题，第二种费用为Wi,价值为Ai，有无限个，为完全背包问题
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<stdio.h>
#include<string.h>
#include<algorithm>
const int N=2010;
using namespace std;
int m,f[N];
void zeroOne(int cost,int weight)
{
for(int i=m;i>=cost;i--)
f[i]=max(f[i],f[i-cost]+weight);
}
void complete(int cost,int weight)
{
for(int i=cost;i<=m;i++)
f[i]=max(f[i],f[i-cost]+weight);
}
int main()
{
int n,T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&m,&n);
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++){
int W,A,B;
scanf("%d%d%d",&W,&A,&B);
zeroOne(W,A+B);
complete(W,A);
}
printf("%d\n",f[m]);
}
return 0;
}
|
Hdu 5414 CRB and String
链接
CRB and String
题意
给定两个字符串s,t，CRB没次可选择串s中的任意一个字符c,在其后插入任意字符d(d ≠ c),
问CRB是否能将字符串s转化为t?
分析
要由s串添加字符变为t,必须满足如下条件
1.t串的长度len(t)>=s,s串与t串相等是可以的
2.t串必须包含s序列(可以不连续即相对位置相同即可)，如s=”abc”,t=”axbrcy”
3.s串和t串的第一个字母相同，且若x为s串从第一个字符开始连续相同字母的个数，
y为t串从第一个字符开始连续相同字母的个数，则x>=y
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<stdio.h>
#include<string.h>
const int N=100010;
char s[N],t[N];
bool judge()
{
int m=strlen(s);
int n=strlen(t);
if(m>n||s[0]!=t[0]) return false;
int i=0,j=0;
while(i<m&&s[i]==s[0]) i++;
while(j<n&&t[j]==t[0]) j++;
if(i<j) return false;
i=0,j=0;
while(j<n){
if(i<m&&s[i]==t[j])
i++;
j++;
}
return i<m?false:true;
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
scanf("%s%s",s,t);
if(judge())
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
|
Hdu 5416 CRB and Tree
链接
CRB and Tree
题意
已知一个包含N个结点N-1条边的树，每一条边有一个权值，对于任何两个结点u,v(u可以等于v)，f(u,v)为从u到v这条路径上边的权值的异或和，给定Q个询问，每个询问输出有多少个无序对(u,v)满足f(u,v) = s
分析
设结点u和v的最近公共祖先为fa,树的根结点为root，则f(u,v)=f(u,fa)^f(fa,v)
由于 f(fa,root)^f(root,fa)=0,
所以 f(u,v)=f(u,fa)^f(fa,root)^f(root,fa)^f(fa,v)=f(u,root)^f(root,v)
即可以用dfs求出根结点root到每一个结点的异或和，并统计不同异或和的个数，再计算答案即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include<stdio.h>
#include<string.h>
#include<algorithm>
typedef long long LL;
using namespace std;
const int N=100005;
int n,m,maxXor,head[N],num[N*2];
bool vis[N];
struct stu{
int to,w,next;
}edge[N*2];
void addEdge(int u,int v,int w)
{
edge[m].to=v;
edge[m].w=w;
edge[m].next=head[u];
head[u]=m++;
}
void dfs(int pos,int sum)
{
num[sum]++;
if(sum>maxXor) maxXor=sum;
for(int i=head[pos];i!=-1;i=edge[i].next){
int v=edge[i].to,w=edge[i].w;
if(!vis[v]){
vis[v]=true;
dfs(v,sum^w);
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
m=0;
memset(head,-1,sizeof(head));
for(int i=1;i<n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
addEdge(a,b,c);
addEdge(b,a,c);
}
memset(num,0,sizeof(num));
memset(vis,false,sizeof(vis));
vis[1]=true;
maxXor=0;
dfs(1,0);
int Q;
scanf("%d",&Q);
while(Q--){
int s;
scanf("%d",&s);
LL ans=0;
if(s==0){
for(int i=0;i<=maxXor;i++)
ans+=(LL)num[i]*(num[i]-1)/2+num[i];
}
else{
for(int i=0;i<=maxXor;i++){
int temp=s^i;
if(temp>maxXor)
continue;
ans+=(LL)num[i]*num[temp];
}
ans>>=1;
}
printf("%I64d\n",ans);
}
}
return 0;
}
|