暑假过半,好想天天睡懒觉…
Hdu 5355 Cake
链接
Cake
题意
有n个大小为{1,2,3…n}的蛋糕,要将这些蛋糕分给m个人，每个人所得蛋糕的大小相等，
且每个完整蛋糕只属于某一个人，即蛋糕不允许切分
分析
n个蛋糕的和sum=n*(n+1)/2，平均数avg=sum/m
因为蛋糕不能切
1.sum%m!=0 即不能整除时，肯定不能平分
2.当avg<n,也不可能平分
3.若有2m个数{1,2,3…2m}肯定可以平分,即连续2m个数肯定可以
4.可以先构造,再dfs
构造：先正向递减构造,再逆向递减构造，这样先构造2*k*m个数
则每个人手上的蛋糕肯定相等，再将剩下的数 {1,2,3…,n-2km}搜索分配
如 n=23，m=3,
第1人：23 18 17 12
第2人：22 19 16 13
第3人：21 20 15 14
剩下{1,2,3…,11} dfs 分配给这三个人
代码
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
74
| #include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
const int N=100010;
bool vis[N],flag;
vector<int> ans[15];
long long n,m,avg,dis,cake[N];
bool dfs(int pos,int sum)
{
if(pos>m)
return true;
for(int i=n;i>=1;i--){
if(vis[i])
continue;
if(sum+i==dis){
cake[i]=pos;
vis[i]=true;
if(dfs(pos+1,0))
return true;
vis[i]=false;
return false;
}
else if(sum+i<dis){
cake[i]=pos;
vis[i]=true;
if(dfs(pos,sum+i))
return true;
vis[i]=false;
}
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
scanf("%I64d%I64d",&n,&m);
long long sum=n*(n+1)/2;
avg=sum/m;
if(sum%m||avg<n){
printf("NO\n");
continue;
}
printf("YES\n");
int x=n%(2*m);
if(x) x=min(x+2*m,n);
dis=avg;
while(n>x){
dis-=n;
for(int j=1;j<=m;j++)
ans[j].push_back(n--);
for(int j=m;j>=1;j--)
ans[j].push_back(n--);
dis-=n+1;
}
memset(vis,0,sizeof(vis));
memset(cake,0,sizeof(cake));
flag=false;
dfs(1,0);
for(int i=1;i<=n;i++)
ans[cake[i]].push_back(i);
for(int i=1;i<=m;i++){
int cnt=ans[i].size();
printf("%d",cnt);
for(int j=0;j<cnt;j++)
printf(" %d",ans[i][j]);
printf("\n");
ans[i].clear();
}
}
return 0;
}
|
Hdu 5358 First One
链接
First One
题意
给定长度为n的数组
$$ S(i,j) = \sum_{i=1}^{j} a_i $$
$求下列式子的值 ( 默认 \log_2 0 = 0) $
$$ \sum_{i=1}^{n} \sum_{j=i}^{n} (\lfloor \log_2 S(i,j) \rfloor + 1) \times (i + j) $$
分析
$ 若 2^{k-1} \leqslant x \leqslant 2^k ,则 $
$ A = \lfloor \log_2 x \rfloor + 1 = k $
$可以枚举 k，找所有满足 A=k 的区间，并求出对应式子的和$
$找A=k的区间时，可以枚举左区间 i,并找到最小的 l 符合 S(i,l)>=2^{k-1}$
$找到 最大的 r 符合 S(i,r) < 2^k,则 区间 [i,j] (l<=j<=r)的 A=k $
$其贡献值为 k*(i*(r-l+1)+(l+r)*(r-l+1)/2)$
参考代码
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
| #include<stdio.h>
#include<string.h>
const int N=100010;
int n;
long long bin[40],a[N],sum[N];
void init()
{
bin[0]=1;
for(int i=1;i<=35;i++)
bin[i]=bin[i-1]<<1;
bin[0]=0;
}
long long solve()
{
long long ans=0;
for(int k=0;k<=34;k++){
long long L=bin[k],R=bin[k+1];
if(sum[n]<L) break;
int l=1,r=1;
for(int i=1;i<=n;i++){
if(sum[n]-sum[i-1]<L) break;
if(a[i]>=R) continue;
if(l<i) l=i;
if(r<i) r=i;
while(l<=n&&sum[l]-sum[i-1]<L) l++;
while(r<=n&&sum[r]-sum[i-1]<R) r++;
if(l<=r-1){
long long cnt=r-l;
ans+=(k+1)*(i*cnt+(l+r-1)*cnt/2);
}
}
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
init();
while(T--){
scanf("%d",&n);
sum[0]=0;
for(int i=1;i<=n;i++){
scanf("%I64d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
long long ans=solve();
printf("%I64d\n",ans);
}
return 0;
}
|
Hdu 5360 Hiking
链接
Hiking
题意
beta准备邀请他最好的n个朋友 Hiking，
但是 只有当当前同意 Hiking的人数 不小于$ l_i,且不大于 r_i $
第i个朋友才会同意邀请,他会一个一个地邀请好友,
求最多同意Hiking的朋友人数,以及他邀请n个朋友的顺序
分析
贪心思想
先按l从小到大排序,再按r从小到大排序
对于当前满足同意邀请条件的朋友,选择最小的r邀请
参考代码
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
| #include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100010;
struct stu{
int l,r,id;
}a[N];
int order[N];
bool vis[N];
vector<int> num[N];
vector<int>::iterator it;
int cmp(stu x,stu y){
if(x.l!=y.l)
return x.l<y.l;
return x.r<y.r;
}
int main()
{
int T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].l);
a[i].id=i;
}
for(int i=1;i<=n;i++)
scanf("%d",&a[i].r);
sort(a+1,a+1+n,cmp);
bool flag=true;
int i=1,ans=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<=n;i++)
num[i].clear();
while(flag){
while(i<=n&&ans>=a[i].l){
num[a[i].r].push_back(a[i].id);
i++;
}
flag=false;
for(int j=ans;j<=n;j++){
if(num[j].size()){
order[ans++]=num[j][0];
vis[num[j][0]]=true;
it=num[j].begin();
num[j].erase(it);
flag=true;
break;
}
}
}
printf("%d\n",ans);
for(i=1;i<=n;i++)
if(!vis[i])
order[ans++]=i;
for(i=0;i<n-1;i++)
printf("%d ",order[i]);
printf("%d\n",order[n-1]);
}
return 0;
}
|
Hdu 5363 Key Set
链接
Key Set
题意
给定n个数的集合{1,2,…n}，求和为偶数的非空子集的个数
分析
大小为n的集合的子集有 $2^n$ 个
和为奇数的子集个数 与和为偶数的子集个数相等
即 和为偶数的子集个数为 $2^{n-1}$,其中有一个为空集
即 和为偶数的非空子集个数为$ 2^{n-1} - 1$
参考代码
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
| #include<stdio.h>
typedef long long LL;
const LL mod=1000000007;
LL powMod(LL a,LL b)
{
a%=mod;
LL ans=1;
while(b){
if(b&1)
ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int main()
{
int T;
LL n;
scanf("%d",&T);
while(T--){
scanf("%I64d",&n);
printf("%I64d\n",powMod(2,n-1)-1);
}
return 0;
}
|