2015 Multi-University Training Contitt 6 solutions BY ZJU（一部解題報告）
公式解題報告：http://bestcoder.hdu.edu.cn/blog/2015-multi-university-training-contest-6-solutions-by-zju/
醜いです。。。orz
1003番です リンク:http://acm.hdu.edu.cn/showproblem.php?pid=5355
Cake
Time Limit：2000/1000 MS（Java/Others） Memory Limit:13131313137272 K(Java/Others)Total Submission(s):1138 Acctepted Submission（s）：152 Special Jdge
Problem Description
The re are
m
soda and toda is their birthday.The
1-st soda has prepared
n
cakes with size
1，2，…，n.Now
1-st soda wants to divide the cakes into
m
parts so that the total size of each part is equal.
Note that you cannot divide a whole cake into small pieces that is each cake must be coplete in the
m
parts.Each cake must belong to exact one of
m
パーティー.
Input
The re are multiple test cases.The first line of input contains an integer
T，indicating the number of test cases.For each test case:
The first contains two integers
n
and
m
（1≦n≦105,2≦m≦10）、the number of cakes and the number of soda.
It is garanted that the total number of soda in the input doesn’t exceed 1000.The number of test cases in the input doesn’t exced 1000.
Output
For each test case，output「YES」if it is possible，others wise out put「NO」in the first line.
If it is possible，then output
m
lines denoting the
m
parts.The first number
シンプル
保存先
i-th line is the number of cakes in
i-th part.The n
シンプル
numbers follow denoting the size of cakes in
i-th part.If there re multile solutions，print any of them.
Sample Input
4
1 2
5 3
5 2
9 3
Sample Output
NO
YES
1 5
2 1 4
2 2 3
NO
YES
3 1 5 9
3 2 6 7
3 3 4 8
ソurce
2015 Multi-University Training Conteest 6
n個のケーキ（サイズ1～n）をm個人に分けて、ケーキの大きさを合計して等しくするように要求します。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;
#define ls 2*i
#define rs 2*i+1
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define N 100005
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define rank rank1
const int mod = 1000000007;
int t,n,m;
int a[N];
int ans[15][N],tem[N],path[N],len[N];
LL sum;
int main()
{
int i,j,k;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
sum = (n+1)*n/2;
if(sum%m)
{
printf("NO
");
continue;
}
sum/=m;
MEM(tem,0);
MEM(len,0);
for(i = n;i>=1;i--)
{
for(j = 0;j<m;j++)
{
if(tem[j]+i<=sum)
{
tem[j]+=i;
path[i]=j;
break;
}
}
}
for(i = 0;i<m;i++)
{
if(tem[i]!=sum)
break;
}
if(i!=m)
{
printf("NO
");
continue;
}
for(i = 1;i<=n;i++)
{
k = path[i];
ans[k][len[k]++] = i;
}
printf("YES
");
for(i = 0;i<m;i++)
{
printf("%d %d",len[i],ans[i][0]);
for(j = 1;j<len[i];j++)
{
printf(" %d",ans[i][j]);
}
printf("
");
}
}
return 0;
}1006番です リンク:http://acm.hdu.edu.cn/showproblem.php?pid=5358
First One
Time Limit：4000/2000 MS（Java/Others） Memory Limit:13131313137272 K(Java/Others)Total Submission(s):757 Accepted Submission(s)：230
Problem Description
soda has an integer array
a 1,a 2,…，an.Let
S(i，j)
be the sum of
ai，ai+1，…，aj.Now soda wants to know the value below:
Σi=1 nΣj=in(⌊ロゴ2 S(i，j)_;+1)×(i+j)
Note:In this problem，you can consider
ロゴ20
as 0.
Input
The re are multiple test cases.The first line of input contains an integer
T，indicating the number of test cases.For each test case:
The first line contains an integer
n
（1≦n≦105）、the number of integers in the array.
The nextラインcontains
n
integers
a 1,a 2,…，an
（0≦ai≦105）
Output
For each test case，output the value.
Sample Input
1
2
1 1
Sample Output
12
ソurce
2015 Multi-University Training Conteest 6
を求めます。考え方：S（i，j）を利用した単調性、 ロゴ2(S(i，j)+1= k=2^(k-1)<=S(i，j)<2^k
エニュメレート・log（sum（i，j）＋1の値を考慮して、kとして記録し、（i＋j）の和を統計すれば良い。
各kについては、2^(k-1)<=sum(i，j)<=2^k-1(i+j)を満たすすべてのものが見つかり、
k<=2*log 2(10^5)<34
出所を明記してください。探してください。星空の子供。
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define LL long long
using namespace std;
LL num[100005];
LL sum[100005];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
LL n;
scanf("%lld",&n);
num[0]=sum[0]=0;
for(int i=1; i<=n; i++)
{
scanf("%lld",&num[i]);
sum[i]=sum[i-1]+num[i];
}
LL ans=0;
for(LL k=1; k<=34; k++)
{
LL l=1,r=0;// r l ； 1 !
LL KL=1LL<<(k-1);
if(k==1) KL--;
LL KR=1LL<<(k);
for(LL i=1; i<=n; i++)
{
l=max(i,l);//
while(l<=n&&sum[l]-sum[i-1]<KL) l++;//
r=max(l-1,r);// , r l l-1
while(r+1<=n&&sum[r+1]-sum[i-1]>=KL&&sum[r+1]-sum[i-1]<KR) r++;//
if(r<l) continue;
ans+=k*((i+l)+(i+r))*(r-l+1)/2;
}
}
printf("%lld
",ans);
}
return 0;
}
1008題 リンク:http://acm.hdu.edu.cn/showproblem.php?pid=5360
ハイキング
Time Limit：6000/3000 MS（Java/Others） Memory Limit:13131313137272 K(Java/Others)Total Submission(s):544 Acceepted Submission（s）：290 Special Jdge
Problem Description
The re are
n
soda conventiently labeled by
1，2，…，n.beta，their best friends，wants to invite some soda to go hiking.The
i-th soda will go hiking if the total number of soda that go hiking except hi isのless than
li
andのlarger than
ri.beta will follow the rules below to invite soda one by:
1.he selects a soda not invited before；
2.he tells soda the number of soda who agree to go hiking by now；
3.soda will agree or disagree according to the number he hears.
Note:beta will always tell the truth and soda will agree if and only the number he hears isのless than
li
andのlarger than
リ、othewise he will disagree.Onece soda agrees to go hiking he will not regret even ft the final total number fails to meet some soda's will.
Help beta design n invitation order that the number of soda who agree to go hiking is maximm.
Input
The re are multiple test cases.The first line of input contains an integer
T，indicating the number of test cases.For each test case:
The first contains an integer
n
（1≦n≦105）、the number of soda.The second line constains
n
integers
l 1,l 2,…，ln.The third line constains
n
integers
r 1,r 2,…，rn.
（0≦li≦ri≦n）
It is garanted that the total number of soda in the input doesn't exced 100000.The number of test cases in the input doesn't exceed 600.
Output
For each test case，output the maximnumber of soda.The n in the second line output a permutation of
1,2,…，n
denoting the invitation order.If there re multiple solutions，print any of them.
Sample Input
4
8
4 1 3 2 2 1 0 3
5 3 6 4 2 1 7 6
8
3 3 2 0 5 0 3 6
4 5 2 7 7 6 7 6
8
2 2 3 3 3 0 0 2
7 4 3 6 3 2 2 5
8
5 6 5 3 3 1 2 4
6 7 7 6 5 4 3 5
Sample Output
7
1 7 6 5 2 4 3 8
8
4 6 3 1 2 5 8 7
7
3 6 7 1 5 2 8 4
0
1 2 3 4 5 6 7 8
ソurce
2015 Multi-University Training Conteest 6
招待の順番を聞くと、最終的に行く人が一番多くなります。一人に一つの区間の人数が要求されます。
分析：優先列でメンテナンスして、rによって小さい時から大きい時まで、詳細に注意するのは難しいです。
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;
const int N = 100005;
struct nnn
{
int l,r,id;
}node[N];
struct NNNN
{
int r,id;
friend bool operator<(NNNN aa,NNNN bb)
{
return aa.r>bb.r;
}
};
priority_queue<NNNN>q;
bool cmp1(nnn aa, nnn bb)
{
return aa.l<bb.l;
}
int id[N];
bool vist[N];
int main()
{
int T,n,ans;
NNNN now;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
ans=0;
/*for(int i=1; i<=n; i++)
printf("%d ",i);
printf("=id
");*/
for(int i=0; i<n; i++)
{
scanf("%d",&node[i].l);
node[i].id=i+1;
}
for(int i=0; i<n; i++)
scanf("%d",&node[i].r);
sort(node,node+n,cmp1);
memset(vist,0,sizeof(vist));
int i=0;
while(i<n)
{
bool ff=0;
while(i<n&&ans>=node[i].l&&ans<=node[i].r)
{
now.r=node[i].r;
now.id=node[i].id;
q.push(now);
//printf("in = %d
",now.id);
i++;
ff=1;
}
if(ff)i--;
while(!q.empty())
{
now=q.top(); q.pop();
if(now.r<ans)continue;
//printf("out = %d
",now.id);
ans++;
id[ans]=now.id;
vist[now.id]=1;
if(node[i+1].l<=ans)
break;
}
i++;
}
while(!q.empty())
{
now=q.top(); q.pop();
if(now.r<ans)continue;
//printf("out = %d
",now.id);
ans++;
id[ans]=now.id;
vist[now.id]=1;
}
bool fff=0;
printf("%d
",ans);
for( i=1; i<=ans; i++)
if(i>1)
printf(" %d",id[i]);
else if(i==1)
printf("%d",id[i]);
if(ans)fff=1;
for( i=1; i<=n; i++)
if(vist[i]==0&&fff)
printf(" %d",i);
else if(vist[i]==0)
printf("%d",i),fff=1;
printf("
");
}
}1011題 リンク:http://acm.hdu.edu.cn/showproblem.php?pid=5363
Keyセット
Time Limit：2000/1000 MS（Java/Others） Memory Limit:13131313137272 K(Java/Others)Total Submission(s):420 Acceepted Submission(s)：275
Problem Description
soda has a set
S
with
n
integers
｛1，2，…n｝.A set is caled key set if the sum of integers in the set is an even number.He wants to know how many nonempty subsets of
S
arkey set.
Input
The re are multiple test cases.The first line of input contains an integer
T
（1≦T≦105）、indicating the number of test cases.For each test case：
The first line contains an integer
n
（1≦n≦109）、the number of integers in the set.
Output
For each test case，output the number of key sets modulo 100000万07.
Sample Input
4
1
2
3
4
Sample Output
0
1
3
7
ソurce
2015 Multi-University Training Conteest 6
#include<stdio.h>
#define LL long long
#define mod 1000000007
LL ppow(LL a,LL b)
{
LL c=1;
while(b)
{
if(b&1) c=c*a%mod;
b>>=1;
a=a*a%mod;
}
return c;
}
int main()
{
int T;
LL n;
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
printf("%lld
",ppow(2,n-1)-1);
}
return 0;
}