首页 > ACM题库 > HDU-杭电 > hdu 2683 TCE-frep number system[解题报告]C++
2014
02-13

hdu 2683 TCE-frep number system[解题报告]C++

TCE-frep number system

问题描述 :

  Number theory is one of the oldest branches of pure mathematics, and one of the largest. Of course, it concerns questions about numbers, usually meaning whole numbers or rational numbers (fractions).
Elementary number theory involves divisibility among integers — the division "algorithm", the Euclidean algorithm (and thus the existence of greatest common divisors), elementary properties of primes (the unique factorization theorem, the infinitude of primes), congruences, including Fermat’s little theorem and Euler’s theorem extending it. But the term "elementary" is usually used in this setting only to mean that no advanced tools from other areas are used — not that the results themselves are simple.
Topics in elementary number theory — the solutions of sets of linear congruence equations (the Chinese Remainder Theorem), or solutions of single binary quadratic equations (Pell’s equations and continued fractions), or the generation of Fibonacci numbers or Pythagorean triples — turn out in retrospect to be harbingers of sophisticated tools and themes in other areas. The remaining parts of number theory are more or less closely allied with other branches of mathematics, and typically use tools from those areas.
Also there lots of branches, such as Combinatorial Number Theory, Algebraic Number Theory, Analytic Number Theory, additive number theory, Geometric number theory, Transcendental number theory, etc.
Today give you a function g(n) whose value is the sum of all the divisors of n .
If n satisfies following rule:

We call n is a TCE-frep number,your task is easy,detail to input and output.

输入:

Two ways of input:
A x y
(x, y <= 2^63-1)
Q n
(1 <= n <= 2^63-1)

输出:

Two ways of input:
A x y
(x, y <= 2^63-1)
Q n
(1 <= n <= 2^63-1)

样例输入:

A 5 70 
A 6 6
Q 6
Q 1

样例输出:

2
1
1
0



Magic-Pen3






Time limit: 1sec. Submitted: 139
Memory limit: 64M Accepted: 100



Source: lilu0355







lilu为他自己发明的魔法笔而高兴,但是对于艺术他有着很执着的精神,为此他又发明了一种更强大的魔法笔。当在白色线段上画线时,白色线段就会变成红色;当在红色线段上画线时,红色线段就会变成黑色,当在黑色线段上画线时,黑色线段就会变成白色。

 

Input

 

有多组case,每组case第一行输入两个整数:N(1 ≤ N ≤ 10000)和M(1 ≤ M ≤
10000)。N表示线段N条单位线段,标号从1开始。接下来有M行输入,表示M条线段。每行包含两个整数X,Y(X ≤
Y)。表示从第X条单位线段到第Y条单位线段之间用魔法笔画线。起始线段为白色。

 

Output

 

每组case包含三个整数分别表示白色,红色和黑色线段的个数。

 

Sample Input

 

 


10 2
5
7
1
2

 

 

Sample Output

 

 


2
0

 普通模擬會超時..

 我過的時候是複制了prayan1988的代碼..用到了樹狀數組

 有空學習下數狀數組

現在我的智商還不足以看懂樹狀數組




代碼中含有全角空格,請勿直接copy,否則會compilation error
 


#include <iostream>


using
 namespace std;


const
 int 10005;


int
 c[N];


int
 Lowbit(int m)


{


    
return m&(-m);


}


void
 Change(int k,int m,int num)


{


   
while(k<=num){


    c
[k] += m;


    += Lowbit
(k);


   
}


}


int
 Getsum(int k)


{


    
int sum 0;


    
while(k>0){


        sum += c
[k];


        -= Lowbit
(k);


    
}


    
return sum;


}


 


int
 main()


{


    
int n, m;


    
int from, to;


    
while(scanf("%d%d"&n, &m) == 2)


    
{


        
memset(c, 0sizeof(c));


        
for(int 0m; i++)


        
{


            
scanf("%d%d"&from, &to);


            Change
(from, 1n);


            Change
(to 1-1n);


        
}


        
int 000;


        
for(int 1<= n; i++)


        
{


            
int Getsum(i) 3;


            
if(== 0)


                w++; 


            
else if(== 1)


                r++;


            
else if(== 2)


                b++;


        
}


        
printf("%d %d %d\n"w, r, b);


    
}


    
return 0;


}


 




解题转自:http://blog.sina.com.cn/s/blog_6d186d330100pote.html


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  3. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确