官方解題報告：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: 131072/131072 K (Java/Others)
Total Submission(s): 1138 Accepted Submission(s): 152
Special Judge
Problem Description
There are m soda and today 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 complete in the m parts. Each cake must belong to exact one of m parts.
Input
There 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 guaranteed that the total number of soda in the input doesn’t exceed 1000000. The number of test cases in the input doesn’t exceed 1000.
Output
For each test case, output "YES" (without the quotes) if it is possible, otherwise output "NO" in the first line.
If it is possible, then output m lines denoting the m parts. The first number si of i -th line is the number of cakes in i -th part. Then si numbers follow denoting the size of cakes in i -th part. If there are multiple 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
Source
2015 Multi-University Training Contest 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\n");
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\n");
continue;
}
for(i = 1;i<=n;i++)
{
k = path[i];
ans[k][len[k]++] = i;
}
printf("YES\n");
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("\n");
}
}
return 0;
}
1006題 連結：http://acm.hdu.edu.cn/showproblem.php?pid=5358
First One
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 757 Accepted Submission(s): 230
Problem Description
soda has an integer array a1,a2,…,an . Let S(i,j) be the sum of ai,ai+1,…,aj . Now soda wants to know the value below: ∑i=1n∑j=in(⌊log2S(i,j)⌋+1)×(i+j)
Note: In this problem, you can consider log20 as 0.
Input
There 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 line contains n integers a1,a2,…,an (0≤ai≤105) .
Output
For each test case, output the value.
Sample Input
1
2
1 1
Sample Output
12
Source
2015 Multi-University Training Contest 6
題意：求
思路：利用S(i,j)單調性， log2(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*log2(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\n",ans);
}
return 0;
}
1008題 連結：http://acm.hdu.edu.cn/showproblem.php?pid=5360
Hiking
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 544 Accepted Submission(s): 290
Special Judge
Problem Description
There are n soda conveniently 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 him is no less than li and no larger than ri . beta will follow the rules below to invite soda one by one:
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 if the number he hears is no less than li and no larger than ri , otherwise he will disagree. Once soda agrees to go hiking he will not regret even if the final total number fails to meet some soda's will.
Help beta design an invitation order that the number of soda who agree to go hiking is maximum.
Input
There 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 l1,l2,…,ln . The third line constains n integers r1,r2,…,rn . (0≤li≤ri≤n)
It is guaranteed that the total number of soda in the input doesn't exceed 1000000. The number of test cases in the input doesn't exceed 600.
Output
For each test case, output the maximum number of soda. Then in the second line output a permutation of 1,2,…,n denoting the invitation order. If there are 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
Source
2015 Multi-University Training Contest 6
題意：問邀請的順序，使得最終去的人最多，每個人有一個區間[l,r]的人數要求
分析：用優先隊列維護，按照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\n\n");*/
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\n",now.id);
i++;
ff=1;
}
if(ff)i--;
while(!q.empty())
{
now=q.top(); q.pop();
if(now.r<ans)continue;
//printf("out = %d\n",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\n",now.id);
ans++;
id[ans]=now.id;
vist[now.id]=1;
}
bool fff=0;
printf("%d\n",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("\n");
}
}
1011題 連結：http://acm.hdu.edu.cn/showproblem.php?pid=5363
Key Set
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 420 Accepted Submission(s): 275
Problem Description
soda has a set S with n integers {1,2,…,n} . A set is called key set if the sum of integers in the set is an even number. He wants to know how many nonempty subsets of S are key set.
Input
There 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 1000000007.
Sample Input
4
1
2
3
4
Sample Output
0
1
3
7
Source
2015 Multi-University Training Contest 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\n",ppow(2,n-1)-1);
}
return 0;
}