首页 > ACM题库 > HDU-杭电 > HDU 3670-A Sequence of Numbers[解题报告]HOJ
2014
11-30

HDU 3670-A Sequence of Numbers[解题报告]HOJ

A Sequence of Numbers

问题描述 :

You are given a sequence of N integers (each within the range [0, 2^16 - 1] ) along with P operations and in order to solve this problem you need to process the operations instructed as follows.

There are two kinds of operations that you will be instructed to perform:

1) Modification
– Given a non-negative number T , you need to increase the value of every number in the sequence by T . If the value of any number in the sequence is larger than 2^16 – 1 after the operation, you should divide its value by 216 and take the remainder as its value;
2) Query
– Given a non-negative number T , query how many numbers in the sequence satisfies the condition that its bitwise and result with 2^T is greater than zero.

For simplicity, all you need to do here is to output the sum ( sum < 10, 000, 000, 000 ) of the answers to all queries.

输入:

There are multiple test cases in the input file. Each test case starts with one integer N (N<=10^5) , the number of integers in the sequence. The following N line consists of one integer P (0<=P<=2^16 – 1) , the value on i -th line being the value of the i -th number in the sequence.

Each of the following lines is either of the format “C delta " (0<=delta) , meaning that you should increase the value of every number by delta, or “Q i " (0<=i<=15) , meaning that you should calculate the answer to the query (as explained in the problem description). Every test case ends with one character `E’ on a single line, followed by a blank line.

N = – 1 indicates the end of input file and should not be processed by your program. It is guaranteed that the total number of operations in each test case does not exceed 200,000.

输出:

There are multiple test cases in the input file. Each test case starts with one integer N (N<=10^5) , the number of integers in the sequence. The following N line consists of one integer P (0<=P<=2^16 – 1) , the value on i -th line being the value of the i -th number in the sequence.

Each of the following lines is either of the format “C delta " (0<=delta) , meaning that you should increase the value of every number by delta, or “Q i " (0<=i<=15) , meaning that you should calculate the answer to the query (as explained in the problem description). Every test case ends with one character `E’ on a single line, followed by a blank line.

N = – 1 indicates the end of input file and should not be processed by your program. It is guaranteed that the total number of operations in each test case does not exceed 200,000.

样例输入:

3 
1 
2 
4 
Q 1 
Q 2 
C 1 
Q 1 
Q 2
E

-1

样例输出:

Case 1: 5

#include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;
typedef __int64 ll;
#define MOD 65536
int dp[20][1<<17],sum_dp[20][1<<17];
int calc_dp()
{
	int k,vk;
 for(k=16;k>=2;k--)
	{
		for(vk=0;vk<(1<<k);vk++)
			dp[k-1][vk%(1<<(k-1))]+=dp[k][vk];
	}
 memset(sum_dp,0,sizeof(sum_dp));
	for(k=1;k<=16;k++)
	{
		sum_dp[k][0]=dp[k][0];
		for(vk=1;vk<(1<<k);vk++)
			sum_dp[k][vk]=sum_dp[k][vk-1]+dp[k][vk];
	}
	return 0;
}
int main()
{
 int n,i,j,x,c,cc,ans,cas=0;
 char query[100];
 int q;
 while(scanf("%d",&n)!=EOF)
 {
	 if (n==-1) break;
	 memset(dp,0,sizeof(dp));
	 for(i=1;i<=n;i++)
	 {
		 scanf("%d",&x);
		 dp[16][x%MOD]++;
	 }
	 calc_dp();
	 c=0;
	 ll ans=0;
 while(scanf("%s",query)!=EOF)
	 {
		 if (query[0]=='E') break;
		 if (query[0]=='C') {scanf("%d",&q);c=(c+q)%MOD;}
		 if (query[0]=='Q') 
		 {
			 scanf("%d",&q);
			 q++;
			 int flag=((1<<(q-1))&c);
			 cc=c%(1<<(q-1));
			 if (flag==0)
			 {
			 ans+=sum_dp[q][(1<<(q-1))-1]-sum_dp[q][(1<<(q-1))-cc-1];
			 ans+=sum_dp[q][(1<<(q-1))+(1<<(q-1))-1-cc]-sum_dp[q][(1<<(q-1))-1];
			 }
			 else
			 {
				ans+=sum_dp[q][(1<<(q-1))+(1<<(q-1))-1]-sum_dp[q][(1<<(q-1))+(1<<(q-1))-cc-1];
			 ans+=sum_dp[q][(1<<(q-1))-1-cc];
			 }
			 // printf("%I64d\n",ans);
		 }
	 }
 printf("Case %d: %I64d\n",++cas,ans);
 }
}
/*
16
1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
Q 0
C 1
Q 0
*/

  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }