1.使用顶点的数据结构存储图

[c language=”++”]
//使用顶点的结构来存储图
vector<vector<int>> graph(n, vector<int>(0));
[/c]

2.使用BFS遍历每个顶点，对每个顶点的邻居进行判断，未染色则进行染色，如果染色了则判断是否合理。

3.图有可能不连通，因此使用sum来记录已经遍历过的顶点数，如果发现没有完全遍历，则再次寻找没有染色的节点，染色后重复步骤2

样例输入

2
5 5
1 2
1 3
3 4
5 2
1 5
5 5
1 2
1 3
3 4
5 2
3 5

样例输出

Wrong
Correct

 
AC代码：
[c language=”++”]
//#include<string>
//#include<stack>
//#include<unordered_set>
//#include <sstream>
//#include "func.h"
//#include <list>
#include <iomanip>
#include<unordered_map>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include <algorithm>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
#include<stack>
using namespace std;

int main(void) {

int t;
cin >> t;
while (t–)
{
int n, m;
scanf("%d %d", &n, &m);
n++;

//使用顶点的结构来存储图
vector<vector<int>> graph(n, vector<int>(0));
for (int i = 0; i < m; i++)
{//读取顶点关系
int a, b;
scanf("%d %d", &a, &b);
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<int> sex(n, -1);//定义大小为n的sex数组，用来标记用户的性别，0为男，1为女
sex[1] = 0;
queue<int> q;
q.push(1);
bool flag = true;
int sum = 1;//染色的总个数
//使用BFS进行搜索
while (1)
{
int p = q.front();
for (int i = 0; i < graph[p].size(); i++)
{
if (sex[graph[p][i]] == -1)
{//如果还没染色，就进行染色
sex[graph[p][i]] = 1 – sex[p];//相邻顶点性别不同
q.push(graph[p][i]);
sum++;
}
else if (sex[graph[p][i]] != -1 && sex[graph[p][i]] == sex[p])
{//如果已经染色，并且性别相同，则Wrong，直接跳出循环
flag = false;
break;
}
}
q.pop();
if (q.empty() && sum == n – 1) break;//已经全部遍历完毕
else if (q.empty() && sum < n – 1)
{//队列为空，但是还有没有遍历的顶点，证明不是连通图
for (int i = 1; i < n; i++)
{
if (sex[i] == -1)
{//图可能不连通,找出其他分支的一个点进行染色，并马上break
sex[i] = 1;
q.push(i);
sum++;
break;//break
}
}
}
}
if (flag) cout << "Correct" << endl;
else cout << "Wrong" << endl;
}
return 0;
}

[/c]

转自：http://www.cnblogs.com/fly1988happy/archive/2012/04/26/2470542.html

1. malloc()函数

1.1 malloc的全称是memory allocation，中文叫动态内存分配。

原型：extern void *malloc(unsigned int num_bytes); 

说明：分配长度为num_bytes字节的内存块。如果分配成功则返回指向被分配内存的指针，分配失败返回空指针NULL。当内存不再使用时，应使用free()函数将内存块释放。

1.2 void *malloc(int size); 

说明：malloc 向系统申请分配指定size个字节的内存空间，返回类型是 void* 类型。void* 表示未确定类型的指针。C,C++规定，void* 类型可以强制转换为任何其它类型的指针。 　　

备注：void* 表示未确定类型的指针，更明确的说是指申请内存空间时还不知道用户是用这段空间来存储什么类型的数据（比如是char还是int或者…）

1.3 free

void free(void *FirstByte)： 该函数是将之前用malloc分配的空间还给程序或者是操作系统，也就是释放了这块内存，让它重新得到自由。

1.4注意事项

1）申请了内存空间后，必须检查是否分配成功。

2）当不需要再使用申请的内存时，记得释放；释放后应该把指向这块内存的指针指向NULL，防止程序后面不小心使用了它。 

3）这两个函数应该是配对。如果申请后不释放就是内存泄露；如果无故释放那就是什么也没有做。释放只能一次，如果释放两次及两次以上会出现错误（释放空指针例外，释放空指针其实也等于啥也没做，所以释放空指针释放多少次都没有问题）。

4）虽然malloc()函数的类型是(void *),任何类型的指针都可以转换成(void *),但是最好还是在前面进行强制类型转换，因为这样可以躲过一些编译器的检查。

1.5  malloc()到底从哪里得到了内存空间？

答案是从堆里面获得空间。也就是说函数返回的指针是指向堆里面的一块内存。操作系统中有一个记录空闲内存地址的链表。当操作系统收到程序的申请时，就会遍历该链表，然后就寻找第一个空间大于所申请空间的堆结点，然后就将该结点从空闲结点链表中删除，并将该结点的空间分配给程序。

2. new运算符

2.1 C++中，用new和delete动态创建和释放数组或单个对象。

动态创建对象时，只需指定其数据类型，而不必为该对象命名，new表达式返回指向该新创建对象的指针，我们可以通过指针来访问此对象。

int *pi=new int;

这个new表达式在堆区中分配创建了一个整型对象，并返回此对象的地址，并用该地址初始化指针pi 。

2.2 动态创建对象的初始化

动态创建的对象可以用初始化变量的方式初始化。

int *pi=new int(100); //指针pi所指向的对象初始化为100

string *ps=new string(10,’9’);//*ps 为“9999999999”

如果不提供显示初始化，对于类类型，用该类的默认构造函数初始化；而内置类型的对象则无初始化。

也可以对动态创建的对象做值初始化：

int *pi=new int( );//初始化为0

int *pi=new int;//pi 指向一个没有初始化的int

string *ps=new string( );//初始化为空字符串 （对于提供了默认构造函数的类类型，没有必要对其对象进行值初始化）

2.3 撤销动态创建的对象

delete表达式释放指针指向的地址空间。

delete pi ;// 释放单个对象

delete [ ]pi;//释放数组

如果指针指向的不是new分配的内存地址，则使用delete是不合法的。

2.4 在delete之后，重设指针的值

delete p; //执行完该语句后，p变成了不确定的指针，在很多机器上，尽管p值没有明确定义，但仍然存放了它之前所指对象的地址，然后p所指向的内存已经被释放了，所以p不再有效。此时，该指针变成了悬垂指针（悬垂指针指向曾经存放对象的内存，但该对象已经不存在了）。悬垂指针往往导致程序错误，而且很难检测出来。

一旦删除了指针所指的对象，立即将指针置为0，这样就非常清楚的指明指针不再指向任何对象。（零值指针：int *ip=0;）

2.5 区分零值指针和NULL指针

零值指针，是值是0的指针，可以是任何一种指针类型，可以是通用变体类型void*也可以是char*，int*等等。

空指针，其实空指针只是一种编程概念，就如一个容器可能有空和非空两种基本状态，而在非空时可能里面存储了一个数值是0，因此空指针是人为认为的指针不提供任何地址讯息。参考：http://www.cnblogs.com/fly1988happy/archive/2012/04/16/2452021.html

2.6 new分配失败时，返回什么？

1993年前，c++一直要求在内存分配失败时operator   new要返回0，现在则是要求operator   new抛出std::bad_alloc异常。很多c++程序是在编译器开始支持新规范前写的。c++标准委员会不想放弃那些已有的遵循返回0规范的代码，所以他们提供了另外形式的operator   new(以及operator   new[])以继续提供返回0功能。这些形式被称为“无抛出”，因为他们没用过一个throw，而是在使用new的入口点采用了nothrow对象: 

class   widget   {   …   };

widget   *pw1   =   new   widget;//   分配失败抛出std::bad_alloc  

if   (pw1   ==   0)   … //   这个检查一定失败

widget   *pw2   =   new   (nothrow)   widget;   //   若分配失败返回0

if   (pw2   ==   0)   … //   这个检查可能会成功

3. malloc和new的区别

3.1 new 返回指定类型的指针，并且可以自动计算所需要大小。

比如： 　　

1) int *p; 　　

p = new int; //返回类型为int* 类型(整数型指针)，分配大小为 sizeof(int); 　　

或： 　　

int* parr; 　　

parr = new int [100]; //返回类型为 int* 类型(整数型指针)，分配大小为 sizeof(int) * 100; 　　

2) 而 malloc 则必须要由我们计算字节数，并且在返回后强行转换为实际类型的指针。 　　

int* p; 　　

p = (int *) malloc (sizeof(int)*128);//分配128个（可根据实际需要替换该数值）整型存储单元，并将这128个连续的整型存储单元的首地址存储到指针变量p中  

double *pd=(double *) malloc (sizeof(double)*12);//分配12个double型存储单元，并将首地址存储到指针变量pd中

3.2 malloc 只管分配内存，并不能对所得的内存进行初始化，所以得到的一片新内存中，其值将是随机的。

除了分配及最后释放的方法不一样以外，通过malloc或new得到指针，在其它操作上保持一致。

4.有了malloc/free为什么还要new/delete？

1) malloc与free是C++/C语言的标准库函数，new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。

2) 对于非内部数据类型的对象而言，光用maloc/free无法满足动态对象的要求。对象在创建的同时要自动执行构造函数，对象在消亡之前要自动执行析构函数。由于malloc/free是库函数而不是运算符，不在编译器控制权限之内，不能够把执行构造函数和析构函数的任务强加于malloc/free。

因此C++语言需要一个能完成动态内存分配和初始化工作的运算符new，以及一个能完成清理与释放内存工作的运算符delete。注意new/delete不是库函数。

我们不要企图用malloc/free来完成动态对象的内存管理，应该用new/delete。由于内部数据类型的“对象”没有构造与析构的过程，对它们而言malloc/free和new/delete是等价的。

3) 既然new/delete的功能完全覆盖了malloc/free，为什么C++不把malloc/free淘汰出局呢？这是因为C++程序经常要调用C函数，而C程序只能用malloc/free管理动态内存。

如果用free释放“new创建的动态对象”，那么该对象因无法执行析构函数而可能导致程序出错。如果用delete释放“malloc申请的动态内存”，结果也会导致程序出错，但是该程序的可读性很差。所以new/delete必须配对使用，malloc/free也一样。

问题描述：

一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数

字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。

 

一、思路：

• 以数字1为例子，我们把求1出现的次数，转化为求1~n中，各个位出现1的次数的总和。即个位上出现1的次数，十位上出现1的次数，百位上出现1的次数……的总和。

取变量m，当m=1时，即求个位上出现1的总次数，m=100时，即求百位上出现1的总次数。假设n=3141592，求百位上1出现的总次数，我们把n分为两部分，分别是整除m后得到部分a=n/100=31415,和整除m后的余数部分b=n%100=92。

• 对于31415，我们求0~31415中，个位1出现的次数，即31415/10=3141，又因为31415%10=5大于1，所以0~31415中，各位出现1的总次数为3141+1=3142.实际上，31415是除以100后得到的数，所以每个1，出现了100次。如3141100~3141199，百位上的1出现了100次，所以这时候百位上的1出现次数为(31415/10+1)*100=314200次。

• 再考察第二部分b=92.因为a%10=5，而不是1。所以第二部分没有贡献1。假设n=9999150，那么a=n/100=99991，由a部分计算得百位上出现1的次数为a/10*100=9999000次。而a%10=1，那么第二部分b=50将会有作用，贡献的1的次数为b+1，即9999100~9999150百位上供50+1，即51次1.所以当n=9999150时，百位上出现1的次数为9999050次。

• 通过上述思路，我们可以分别计算个位出现1的次数，十位出现1的次数……，通过相加，我们可以得到1~n中，1出现的总次数。

• 通过上述思路，我们可以分别计算0~9出现的总次数。

• 数字0的情况有点特殊，进行特殊处理。因为不会出现01，02，03等等0开头的数字，所以在统计数字零时，每个位计算出来的count，如果count>=1，则需要先count–，再进行计算。

 

二、复杂度分析

根据上述算法，我们通过逐渐计算n的个位，十位，百位……即每次m*=10，所以时间复杂度是O(lg n)，在空间方面，每次固定使用常量a和b，估空间负责度不依赖于n，所以空间复杂度啊为O(1)。

 

数据测试结果如下：采取了临界值1和1000000000（10^9）

	n=1	n=10^9	n=100	n=555555	n=99	n=200	201
0的个数	0	788888898	11	271605	9	31	21
1的个数	1	900000001	21	382716	20	140	141
2的个数	0	900000000	20	382716	20	41	42
3的个数	0	900000000	20	382716	20	40	40
4的个数	0	900000000	20	382716	20	40	40
5的个数	0	900000000	20	333336	20	40	40
6的个数	0	900000000	20	271605	20	40	40
7的个数	0	900000000	20	271605	20	40	40
8的个数	0	900000000	20	271605	20	40	40
9的个数	0	900000000	20	271605	20	40	40

 

三、程序运行截图如下：

 

四、源代码

代码中，通过类Solution封装了void calEveryDigitNumber（int n)函数：

[c language=”++”]

class Solution
{
private:
/**************************************
Author:siukwan
Date:2015-09-25
Description:计算digit出现的次数
***************************************/
static int calOneDigit(int n, int digit)
{
int ans = 0;//返回的结果
for (long long m = 1; m <= n; m *= 10)
{//m采用long long类型，避免溢出，从计算个位出现digit的次数开始
int a = n / m;
int b = n % m;
int count = a / 10;
if (a % 10 > digit) count++;//如果a的余数部分大于digit，则会多出现m个digit
if (digit == 0 && count >=1 ) count–;//0需要特殊处理，因为没有01，02，03……
ans += count * m;//计算a部分出现digit的次数
if (a % 10 == digit )
ans += (b + 1);//如果余数恰好等于digit，结合b部分统计额外出现digit的次数
}
return ans;
}
public:
/**************************************
Author:siukwan
Date:2015-09-25
Description:计算0~9出现的次数,并输出结果
***************************************/
static void calEveryDigitNumber(int n)
{
for (int i = 0; i < 9; i++)
{
int count = calOneDigit(n, i);
printf("%d出现的次数：%d\n", i, count);
}
}
};

[/c]

 

整个程序的代码如下：

[c language=”++”]
#include<stdio.h>
#include<iostream>
using namespace std;
class Solution
{
private:
/**************************************
Author:siukwan
Date:2015-09-25
Description:计算digit出现的次数
***************************************/
static int calOneDigit(int n, int digit)
{
int ans = 0;//返回的结果
for (long long m = 1; m <= n; m *= 10)
{//m采用long long类型，避免溢出，从计算个位出现digit的次数开始
int a = n / m;
int b = n % m;
int count = a / 10;
if (a % 10 > digit) count++;//如果a的余数部分大于digit，则会多出现m个digit
if (digit == 0 && count >=1 ) count–;//0需要特殊处理，因为没有01，02，03……
ans += count * m;//计算a部分出现digit的次数
if (a % 10 == digit )
ans += (b + 1);//如果余数恰好等于digit，结合b部分统计额外出现digit的次数
}
return ans;
}
public:
/**************************************
Author:siukwan
Date:2015-09-25
Description:计算0~9出现的次数,并输出结果
***************************************/
static void calEveryDigitNumber(int n)
{
for (int i = 0; i < 9; i++)
{
int count = calOneDigit(n, i);
printf("%d出现的次数：%d\n", i, count);
}
}
};
int main(void)
{
int n = 0;
while (1)
{
printf("算法实现题1-1：统计数字问题\n1）本程序会统计1~n的n个数字中，0~9分别出现的次数；\n2）n的取值范围为0<=n<=10^9；\n请输入页码n:");

cin >> n;
if (n <= 0 || n>1000000000)
{
printf("n的取值范围为0<=n<=10^9，请重新输入!\n");
continue;
}
Solution::calEveryDigitNumber(n);
}
return 0;
}
[/c]

hihoCoder 1039 字符消除

题目地址：http://hihocoder.com/problemset/problem/1039

时间限制:1000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi最近在玩一个字符消除游戏。给定一个只包含大写字母”ABC”的字符串s，消除过程是如下进行的：

1)如果s包含长度超过1的由相同字母组成的子串，那么这些子串会被同时消除，余下的子串拼成新的字符串。例如”ABCCBCCCAA”中”CC”,”CCC”和”AA”会被同时消除，余下”AB”和”B”拼成新的字符串”ABB”。
2)上述消除会反复一轮一轮进行，直到新的字符串不包含相邻的相同字符为止。例如”ABCCBCCCAA”经过一轮消除得到”ABB”，再经过一轮消除得到”A”

游戏中的每一关小Hi都会面对一个字符串s。在消除开始前小Hi有机会在s中任意位置(第一个字符之前、最后一个字符之后以及相邻两个字符之间)插入任意一个字符(‘A’,’B’或者’C’)，得到字符串t。t经过一系列消除后，小Hi的得分是消除掉的字符的总数。

请帮助小Hi计算要如何插入字符，才能获得最高得分。

输入

输入第一行是一个整数T(1<=T<=100)，代表测试数据的数量。
之后T行每行一个由’A”B”C’组成的字符串s，长度不超过100。

输出

对于每一行输入的字符串，输出小Hi最高能得到的分数。

提示

第一组数据：在”ABCBCCCAA”的第2个字符后插入’C’得到”ABCCBCCCAA”，消除后得到”A”，总共消除9个字符(包括插入的’C’)。
第二组数据：”AAA”插入’A’得到”AAAA”，消除后得到”“，总共消除4个字符。
第三组数据：无论是插入字符后得到”AABC”,”ABBC”还是”ABCC”都最多消除2个字符。

样例输入

3
ABCBCCCAA
AAA
ABC

样例输出

9
4
2

思路：

1.原来计划在某个位置插入的字母必须是和相邻的字母相同，譬如“AC”，在AC之间插入的是A。后来试过几个测试用例，输出正确，就拿去提交，结果发现WA。

2.后来发现在某个位置插入的字母不一定要和相邻字母相同，这涉及到一些策略的问题，譬如AAACA，按照我的理解，要么插入后变成AAAACA，最后消除后剩下CA，要么插入后变成AAACAA，消除后剩下C，要么插入后变成AAACCA，消除后剩下C，所以按照我原来的思路，输出的会是5.

3.实际上，对于AAACA这个例子，最好的插入方法是ACAACA。消除过程如下：ACAACA->ACCA->AA>”“，结果为6才正确。

4.最后采用的方法是，遍历所有的情况，在每个可插入的位置都尝试插入A,B,C（这也很可能为什么题目只提供了3种字母，而不是更多的字母）.

可以AC的代码：
[c language=”++”]
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include <algorithm>
using namespace std;
int main()
{
int n = 0;
cin >> n;
string *strCin = new string[n];

for (int h = 0; h < n; h++)
{
cin >> strCin[h];
string newStr = strCin[h];
int ans = 0;
int size = newStr.size();
for (int i = 0; i <size; i++)
{
for (int abc = 0; abc < 3; abc++)
{
string str;
char a = ‘A’ + abc;
str = newStr.substr(0, i + 1) + a + newStr.substr(i + 1);
string pre = str;
string now = str;
do
{
str = pre;
if (str.size() == 1) break;
pre = "";
if (str.size() == 0) break;
char c = str[0];
bool del = false;
for (int j = 1; j < str.size(); j++)
{
if (c == str[j])
{
del = true;
}
else
{
if (del)
{
del = false;
}
else
{
pre += c;
}
c = str[j];
if (j == str.size() – 1)
pre += c;
}
}
} while (pre != str);
int score = now.size() – str.size();
ans = max(ans, score);
}
}
cout << ans << endl;
}
return 0;
}
[/c]