我的征尘是星辰大海。。。

The dirt and dust from my pilgrimage forms oceans of stars...

-------当记忆的篇章变得零碎，当追忆的图片变得模糊，我们只能求助于数字存储的永恒的回忆

作者:黄教授

十月二十七日等待变化等待机会

#include <vector>
#include <string>
using namespace std;
class ABCPath
{
public:
    int length(vector <string> grid)
    {
        row=grid.size();
        col=grid[0].size();
        vector<pair<size_t,size_t> > v;
        locate(grid, 'A', v);
        if (v.size()==0)
        {
            return 0;
        }
        char ch, maxCh='A';
        for (size_t i=0; i<v.size(); i++)
        {
            ch=walk(v[i], grid);
            if (ch>maxCh)maxCh=ch;
        }
        return maxCh-'A'+1;                
    }
private:
    size_t row,col;
    void locate(const vector<string>& grid, char ch, vector<pair<size_t,size_t> >& v)
    {
        for (size_t i=0; i<grid.size(); i ++)
        {
            for (size_t j=0;j<grid[i].size(); j++)
            {
                if (grid[i][j]==ch)
                {
                    v.push_back(make_pair(i,j));
                }
            }
        }
    }  
    char walk(pair<size_t,size_t> pos, const vector<string>& grid)
    {
        char current=grid[pos.first][pos.second];
        char maxCh=current;
        pair<size_t, size_t> res;
        if (left(pos, res) && grid[res.first][res.second]-current==1)
        {
            char ch=walk(res, grid);
            if (ch>maxCh) maxCh=ch;
        }
        if (right(pos, res)&& grid[res.first][res.second]-current==1)
        {
            char ch=walk(res, grid);
            if (ch>maxCh) maxCh=ch;
        }
        if (up(pos, res)&& grid[res.first][res.second]-current==1)
        {
            char ch=walk(res, grid);
            if (ch>maxCh) maxCh=ch;
        }
        if (down(pos, res)&& grid[res.first][res.second]-current==1)
        {
            char ch=walk(res, grid);
            if (ch>maxCh) maxCh=ch;
        }        
        if (upleft(pos, res)&& grid[res.first][res.second]-current==1)
        {
            char ch=walk(res, grid);
            if (ch>maxCh) maxCh=ch;
        }    
       if (downright(pos, res)&& grid[res.first][res.second]-current==1)
        {
            char ch=walk(res, grid);
            if (ch>maxCh) maxCh=ch;
        }  
        if (downleft(pos, res)&& grid[res.first][res.second]-current==1)
        {
            char ch=walk(res, grid);
            if (ch>maxCh) maxCh=ch;
        }             
        if (upright(pos, res)&& grid[res.first][res.second]-current==1)
        {
            char ch=walk(res, grid);
            if (ch>maxCh) maxCh=ch;
        } 
        return maxCh;
    }
    bool up(const pair<size_t, size_t>&pos, pair<size_t,size_t>&res)
    {
        if (pos.first>0) {
            res.first=pos.first-1;
            res.second=pos.second;
            return true;
        }
        return false;
    }
    bool down(const pair<size_t, size_t>&pos, pair<size_t,size_t>&res)
    {
        if (pos.first<row-1) {
            res.first=pos.first+1;
            res.second=pos.second;
            return true;
        }
        return false;
    }
    bool left(const pair<size_t, size_t>&pos, pair<size_t,size_t>&res)
    {
        if (pos.second>0) {
            res.first=pos.first;
            res.second=pos.second-1;
            return true;
        }
        return false;
    }
    bool right(const pair<size_t, size_t>&pos, pair<size_t,size_t>&res)
    {
        if (pos.second<col-1) {
            res.first=pos.first;
            res.second=pos.second+1;
            return true;
        }
        return false;
    }
    bool upleft(const pair<size_t, size_t>&pos, pair<size_t,size_t>&res)
    {
        if (pos.first>0 && pos.second>0) {
            res.first=pos.first-1;
            res.second=pos.second-1;
            return true;
        }
        return false;
    }
    bool downright(const pair<size_t, size_t>&pos, pair<size_t,size_t>&res)
    {
        if (pos.first<row-1&&pos.second<col-1) {
            res.first=pos.first+1;
            res.second=pos.second+1;
            return true;
        }
        return false;
    }
   bool upright(const pair<size_t, size_t>&pos, pair<size_t,size_t>&res)
    {
        if (pos.first>0 && pos.second<col-1) {
            res.first=pos.first-1;
            res.second=pos.second+1;
            return true;
        }
        return false;
    }
    bool downleft(const pair<size_t, size_t>&pos, pair<size_t,size_t>&res)
    {
        if (pos.first<row-1&&pos.second>0) {
            res.first=pos.first+1;
            res.second=pos.second-1;
            return true;
        }
        return false;
    }    
};

十月二十八日等待变化等待机会

这不是topcoder的题目仅仅是我自己的练习。

namespace test53_namespace
{

bool flag=true;
std::mutex mtx;
std::condition_variable cv;

void produce(int num)
{
	while (num>0)
	{
		{
			std::unique_lock<std::mutex> lck(mtx);
			cv.wait(lck, [](){return flag;});
		}
		cout<<"It is producer "<<num--<<" turn to write log now..."<<endl;
		flag=false;
		cv.notify_one();
	}
}

void consume(int num)
{
	while (num>0)
	{
		{
			std::unique_lock<std::mutex> lck(mtx);
			cv.wait(lck, [](){return !flag;});
		}

cout<<"It is consumer " << num-- << " turn to read log now..."<<endl;
		flag=true;
		cv.notify_one();
	}
}
void test53()
{
	std::thread consumer_thread(consume, 10);
	std::thread producer_thread(produce, 10);
	consumer_thread.join();
	producer_thread.join();
}
}

namespace test54_namespace
{
std::atomic_flag flag=ATOMIC_FLAG_INIT;
bool done=true;
void produce(int num)
{
	while (num>0)
	{
		while (flag.test_and_set())
		{
			std::this_thread::yield();
		}
		if (!done)
		{
			cout<<"It is producer "<<num--<<" turn to write log now..."<<endl;
			done=true;
			flag.clear();
		}
		else
		{
			flag.clear();
			std::this_thread::yield();
		}

}
}

void consume(int num)
{
	while (num>0)
	{
		while (flag.test_and_set())
		{
			std::this_thread::yield();
		}
		if (done)
		{
			cout<<"It is consumer " << num-- << " turn to read log now..."<<endl;
			done=false;
			flag.clear();
		}
		else
		{
			flag.clear();
			std::this_thread::yield();
		}
	}
}
void test54()
{
	std::thread consumer_thread(consume, 10);
	std::thread producer_thread(produce, 10);

consumer_thread.join();
	producer_thread.join();
}
}

十月二十九日等待变化等待机会

namespace test53_namespace
{
bool flag=true;
std::mutex mtx;
std::condition_variable cv;
std::chrono::high_resolution_clock::time_point c1, c2, p1,p2;
void produce(int num)
{
	p1=std::chrono::high_resolution_clock::now();
	while (num>0)
	{
		{
			std::unique_lock<std::mutex> lck(mtx);
			cv.wait(lck, [](){return flag;});
		}
		cout<<"It is producer "<<num--<<" turn to write log now..."<<endl;
		flag=false;
		cv.notify_one();
	}
	p2=std::chrono::high_resolution_clock::now();
}
void consume(int num)
{
	c1=std::chrono::high_resolution_clock::now();
	while (num>0)
	{
		{
			std::unique_lock<std::mutex> lck(mtx);
			cv.wait(lck, [](){return !flag;});
		}
		cout<<"It is consumer " << num-- << " turn to read log now..."<<endl;
		flag=true;
		cv.notify_one();
	}
	c2=std::chrono::high_resolution_clock::now();
}
void test53()
{
	std::thread consumer_thread(consume, 10);
	std::thread producer_thread(produce, 10);
	consumer_thread.join();
	producer_thread.join();
	std::cout <<"consumer total:"<< std::chrono::duration_cast<std::chrono::nanoseconds>(c2-c1).count()<<endl;
	std::cout <<"producer total:"<< std::chrono::duration_cast<std::chrono::nanoseconds>(p2-p1).count()<<endl;
}
}
namespace test54_namespace
{
std::atomic_flag flag=ATOMIC_FLAG_INIT;
bool done=true;
std::chrono::high_resolution_clock::time_point c1, c2, p1,p2;
void produce(int num)
{
	p1=std::chrono::high_resolution_clock::now();
	while (num>0)
	{
		while (flag.test_and_set())
		{
			std::this_thread::yield();
		}
		if (!done)
		{
			cout<<"It is producer "<<num--<<" turn to write log now..."<<endl;
			done=true;
			flag.clear();
		}
		else
		{
			flag.clear();
			std::this_thread::yield();
		}
	}
	p2=std::chrono::high_resolution_clock::now();
}
void consume(int num)
{
	c1=std::chrono::high_resolution_clock::now();
	while (num>0)
	{
		while (flag.test_and_set())
		{
			std::this_thread::yield();
		}
		if (done)
		{
			cout<<"It is consumer " << num-- << " turn to read log now..."<<endl;
			done=false;
			flag.clear();
		}
		else
		{
			flag.clear();
			std::this_thread::yield();
		}
	}
	c2=std::chrono::high_resolution_clock::now();
}
void test54()
{
	std::thread consumer_thread(consume, 10);
	std::thread producer_thread(produce, 10);
	consumer_thread.join();
	producer_thread.join();
	std::cout <<"consumer total:"<< std::chrono::duration_cast<std::chrono::nanoseconds>(c2-c1).count()<<endl;
	std::cout <<"producer total:"<< std::chrono::duration_cast<std::chrono::nanoseconds>(p2-p1).count()<<endl;
}
}
int main()
{
	test53_namespace::test53();
	test54_namespace::test54();
	return 0;
}

十月三十日等待变化等待机会

这个答案是被否定的因为这个根本是一个概率计算的问题，我却答不上通项公式变成了搜索问题，自然是无法应对大数据量的递归了。_{可以说这个是一个典型的计算机语言能力无法替代算法的例子。}

In most states, gamblers can choose from a wide variety of different lottery games. The rules of a lottery are defined by two integers (choices and blanks) and two boolean variables (sorted and unique). choices represents the highest valid number that you may use on your lottery ticket. (All integers between 1 and choices, inclusive, are valid and can appear on your ticket.) blanks represents the number of spots on your ticket where numbers can be written.

The sorted and unique variables indicate restrictions on the tickets you can create. If sorted is set to true, then the numbers on your ticket must be written in non-descending order. If sorted is set to false, then the numbers may be written in any order. Likewise, if unique is set to true, then each number you write on your ticket must be distinct. If unique is set to false, then repeats are allowed.

Here are some example lottery tickets, where choices = 15 and blanks = 4:

{3, 7, 12, 14} -- this ticket is unconditionally valid.

{13, 4, 1, 9} -- because the numbers are not in nondescending order, this ticket is valid only if sorted = false.

{8, 8, 8, 15} -- because there are repeated numbers, this ticket is valid only if unique = false.

{11, 6, 2, 6} -- this ticket is valid only if sorted = false and unique = false.

Given a list of lotteries and their corresponding rules, return a list of lottery names sorted by how easy they are to win. The probability that you will win a lottery is equal to (1 / (number of valid lottery tickets for that game)). The easiest lottery to win should appear at the front of the list. Ties should be broken alphabetically (see example 1).

void test62()
{
	class Lottery
	{
	struct Rule
	{
	string m_name;
	int m_choice;
	int m_blank;
	bool m_sorted;
	bool m_unique;
	int m_count;
	operator string()
		{
		stringstream ss;
		ss<<"m_name:"<<m_name<<endl<<"m_choice:"<<m_choice<<endl
				<<boolalpha
				<<"m_blank:"<<m_blank<<endl<<"m_sorted:"<<m_sorted<<endl
				<<"m_unique:"<<m_unique<<endl;
		return ss.str();
		}
	};
	void parseRule(const string& str, Rule& rule)
	{
		size_t pos= str.find_first_of(':');
		rule.m_name=str.substr(0, pos);
		stringstream ss;
		ss<<str.substr(pos+1);
		char chSort, chUnique;
		ss>>rule.m_choice>>rule.m_blank>>chSort>>chUnique;
		rule.m_sorted=chSort=='T';
		rule.m_unique=chUnique=='T';
	}
	void parseRules(const vector<string>& rules, vector<Rule>&vectRules)
	{
		std::function<int(int,int,bool,bool)> countValid;
		countValid = [&countValid](int choice, int blank,bool sorted, bool unique)->int
		{
			if (blank==1 || (blank>1&&choice==0)){
				return choice;
			}
			if (!sorted) {
				return choice*countValid(choice-(unique?1:0), blank-1,sorted,unique);
			}else {
				int result=0;
				for (int i=1; i<=choice; i ++){
					result+=countValid(choice-i+(unique?0:1), blank-1,sorted,unique);
				}
				return result;
			}
		};
		for (auto str: rules)
		{
			Rule rule;
			parseRule(str, rule);
			cout<<(string)(rule);
			rule.m_count=countValid(rule.m_choice, rule.m_blank, rule.m_sorted, rule.m_unique);
			vectRules.push_back(rule);
		}
	}
	public:
	vector<string> sortByOdds(vector<string> rules)
	{
		vector<Rule> vectRules;
		parseRules(rules, vectRules);
		std::sort(vectRules.begin(), vectRules.end(),[](Rule it1, Rule it2)
		{
			if (it1.m_count==it2.m_count)
			{
				return it1.m_name<it2.m_name;
			}
			return it1.m_count<it2.m_count;
		}
		);
		vector<string> result;
		for (auto rule: vectRules)
		{
			result.push_back(rule.m_name);
		}
		return result;
	}
	};
	vector<string> rules={
	"INDIGO: 93 8 T F",
	"ORANGE: 29 8 F T",
	"VIOLET: 76 6 F F",
	"BLUE: 100 8 T T",
	"RED: 99 8 T T",
	"GREEN: 78 6 F T",
	"YELLOW: 75 6 F F"
	};
	auto results=Lottery().sortByOdds(rules);
	for (auto str:results)
	{
		cout<<str<<endl;
	}
}

十一月二日等待变化等待机会

这个问题确实比较难，我花了整整一天来调试。

You work for an electric company, and the power goes out in a rather large apartment complex with a lot of irate tenants. You isolate the problem to a network of sewers underneath the complex with a step-up transformer at every junction in the maze of ducts. Before the power can be restored, every transformer must be checked for proper operation and fixed if necessary. To make things worse, the sewer ducts are arranged as a tree with the root of the tree at the entrance to the network of sewers. This means that in order to get from one transformer to the next, there will be a lot of backtracking through the long and claustrophobic ducts because there are no shortcuts between junctions. Furthermore, it's a Sunday; you only have one available technician on duty to search the sewer network for the bad transformers. Your supervisor wants to know how quickly you can get the power back on; he's so impatient that he wants the power back on the moment the technician okays the last transformer, without even waiting for the technician to exit the sewers first. You will be given three vector <int>'s: fromJunction, toJunction, and ductLength that represents each sewer duct. Duct i starts at junction (fromJunction[i]) and leads to junction (toJunction[i]). ductlength[i] represents the amount of minutes it takes for the technician to traverse the duct connecting fromJunction[i] and toJunction[i]. Consider the amount of time it takes for your technician to check/repair the transformer to be instantaneous. Your technician will start at junction 0 which is the root of the sewer system. Your goal is to calculate the minimum number of minutes it will take for your technician to check all of the transformers. You will return an int that represents this minimum number of minutes

这个是一个复杂的test，结果是600

RegularSeason

这个不过是500分的题目没有太多的难度，只是理解和改错的问题，对于概率计算的简化让我感到迷惑而已。

A new basketball season will start this autumn, and you want to predict its results. You have been watching the tournaments for ages and following the teams closely, so you can exactly determine the probability that a particular team will win a match vs some other team. Now you want to know, given these probabilities, how many games each of the teams is expected to win in the upcoming tournament.

You will be given a vector <string>, teams. Each element of teams will be formatted as "NAME P1 P2 ... PN", where NAME is the name of the team, and P1, P2, ..., PN are the probabilities that this team will win home games against the 1st, 2nd, ..., Nth teams, respectively (the ith probability for the ith team will always be equal to 0). Ties are not possible due to the rules, so if the ith team has a probability p of beating the jth team in a home game, then the jth team has a probability of (100-p) of beating the ith team when the ith team is at home. Finally, you will be given an int rounds, which gives you the number of rounds in the championship. This means that team A will play 2*rounds games against each other team B (rounds as the visitors and rounds as the home team). You should predict the expected number of games each team will win in the tournament. You should round your prediction to the nearest integer (.5 rounds up).

The return value should be a vector <string>, with each element formatted as "NAME NUMBER", where NAME is the name of the team, and NUMBER is the predicted number of wins. NUMBER should have no extra leading zeroes. The return value should be sorted by NUMBER in decreasing order (so the first element of the result will represent the most probable champion). If several teams have the same rounded number of wins, sort them using predicted number of wins before rounding (again in decreasing order); if a tie still remains, sort the tied teams by NAME in ascending alphabetical order.

void test64()
{
	class RegularSeason
	{
	struct Team
	{
	string name;
	vector<int> probabilities;
	int wins=0;
	int points=0;
	};
	int m_rounds;
	vector<Team> m_teams;
	void parse(const vector<string>& teams)
	{
		for (const string& str: teams)
		{
			Team team;
			stringstream ss;
			ss<<str;
			ss>>team.name;
			for (size_t i=0; i<teams.size(); i++)
			{
				int num;
				ss>>num;
				team.probabilities.push_back(num);
			}
			m_teams.push_back(team);
		}
	}
	void calculate()
	{
		for (size_t i=0; i<m_teams.size(); i++)
		{
			Team& team=m_teams[i];

for (size_t j=0; j<m_teams.size(); j++)
			{
				if (i!=j)
				{
					Team&other=m_teams[j];
					int wins=(team.probabilities[j]+(100-other.probabilities[i]))*m_rounds;
					team.points+=wins;
				}
			}
		}
		for (Team& t:m_teams)
		{
			t.wins=t.points/100;
			if (t.points%100>=50)
			{
				t.wins++;
			}
		}
	}
	void sortTeam()
	{
		std::sort(m_teams.begin(), m_teams.end(), [](const Team& t1, const Team& t2)
			{
				if (t1.wins!=t2.wins)
				{
					return t1.wins>t2.wins;
				}
				else
				{
					if (t1.points!=t2.points)
					{
						return t1.points>t2.points;
					}
					else
					{
						return t1.name<t2.name;
					}
				}
			}
		);
	}
	public:
	vector<string> finalStandings(vector<string> teams, int rounds)
	{
		m_rounds=rounds;
		parse(teams);
		calculate();
		sortTeam();
		vector<string> result;
		for (auto t: m_teams)
		{
			stringstream ss;
			ss<<t.name<<" "<<t.wins;
			result.push_back(ss.str());
		}
		return result;
	}
	};
	vector<string> teams={
	"A 0 10 50",
	"B 100 0 100",
	"C 50 10 0"
	};
	auto v=RegularSeason().finalStandings(teams, 5);
	for (auto s: v)
	{
		cout<<s<<endl;
	}
}

十一月八日等待变化等待机会

原本以为是一个很简单的二分法搜索却折腾了好久，看来脑子是锈死了。话说一个有序数组里所有的数字都是两两成对的，除了一个，也就是说数组一定是奇数个数字，并且是排序的，并且有(size-1)/2个unique的数字，这个条件很重要，我一开始没有意识到结果debug了好久。首先就是正确产生这样子的数组，这里我也懒得讲究什么效率了，就是先产生一个排序的不重复的，然后合并（其实应该调用merge，应该比append再sort来的有效率），最后随机抽调一个数字。二分法的关键是要意识到递归搜索的数组的长度一定是奇数的，我一开始没有意识到。

十一月九日等待变化等待机会

这个是我做的一个小实验来检验sdl_ttf库能否正确显示中文。需要链接sdl2_ttf

#include <SDL2/SDL.h>
#include <SDL2/SDL_ttf.h>
#include <stdio.h>
#define SCREEN_WIDTH 640
#define SCREEN_HEIGHT 480
int main(int argc, char* args[]) {
  SDL_Window* window = NULL;
  SDL_Surface* screenSurface = NULL;
  if (SDL_Init(SDL_INIT_VIDEO) < 0) {
    fprintf(stderr, "could not initialize sdl2: %s\n", SDL_GetError());
    return 1;
  }
  window = SDL_CreateWindow(
			    "hello_sdl2",
			    SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED,
			    SCREEN_WIDTH, SCREEN_HEIGHT,
			    SDL_WINDOW_SHOWN
			    );
  if (window == NULL) {
    fprintf(stderr, "could not create window: %s\n", SDL_GetError());
    return 1;
  }
  screenSurface = SDL_GetWindowSurface(window);
  SDL_FillRect(screenSurface, NULL, SDL_MapRGB(screenSurface->format, 0xFF, 0xFF, 0xFF));
  if (TTF_Init() < 0) {
      // Error handling code
	  printf("TTF_Init: %s\n", TTF_GetError());
  }
  // load font.ttf at size 16 into font
  TTF_Font *font;
  //font=TTF_OpenFont("/home/nick/eclipse-workspace-06/sdlTest/Debug/unifont.ttf", 24);
  font=TTF_OpenFont("/home/nick/Downloads/FZHTJW.TTF", 24);
  //font=TTF_OpenFont("/usr/share/fonts/truetype/liberation/LiberationSans-Regular.ttf", 24);
  if(!font) {
      printf("TTF_OpenFontRW: %s\n", TTF_GetError());
      // handle error
  }
  SDL_Color color={100,100,100};
  SDL_Surface *text_surface;
  if(!(text_surface=TTF_RenderUTF8_Solid(font, "你好世界！",color))) {
      //handle error here, perhaps print TTF_GetError at least
  } else {
	  SDL_Rect rect{50,50, 50, 50};
      SDL_BlitSurface(text_surface,NULL,screenSurface, &rect);
      //perhaps we can reuse it, but I assume not for simplicity.
      SDL_FreeSurface(text_surface);
  }
  SDL_UpdateWindowSurface(window);
  SDL_Delay(2000);
  SDL_DestroyWindow(window);
  SDL_Quit();
  return 0;
}

十一月十二日等待变化等待机会

对于昨天的遭遇感到有些愤愤不平，可是也无可奈何。这个是一个头条看到的问题，就是所谓的寻找most closest ancester的问题，定义是两个节点的最近的共同祖先，解释起来不如使用实例来看：这个程序还是花了不少的时间的，首先是怎么定义二叉树，我感觉内存回收是一个头疼的问题，所以决定使用shared_ptr 其次是如何产生二叉树，这个似乎是一个简单的问题，可是开始的时候我没有使用bfs，而是dfs，结果树的形状就不好看了作为一个小工具你需要把二叉树好看的打印出来，那么这个也是一个分层打印的BFS，为了分层打印我使用了一个TreeValues的容器可以把每一层的数值存在一个map里，它的key是层数，value是一个数值的vector 再次是搜索共同祖先，这个化简为首先搜索一个节点的所有祖先那么所谓的最近的共同祖先就是按照两个祖先链条找到第一个相同的节点这个是总的测试程序，因为我现在习惯于把代码都写成一个测试函数里的lambda，所以才会有这么多的lambda递归的定义的麻烦事情。

十一月二十日等待变化等待机会

这个是结果

十一月二十一日等待变化等待机会

我只是想先验证一下这样子操作sub matrix是否方便来搜索sudoku，结果比较失望。这个是一个简单的问题就是给你一个数组要求你找出所有的数字的和是总数一半的。运行结果

十一月二十三日等待变化等待机会

我第一次尝试用lower/upper bound但是发现很麻烦，还不如直接遍历，但是，我懒得debug了。

void test170()
{
	struct MyPair
	{
		MyPair(int f, int s)
		{
			first=std::min(f, s);
			second=std::max(f, s);
		}
		MyPair()
		{
			while (first==second)
			{
				first=rand()%100+1;
				second=rand()%100+1;
			}
			if (second<first)
			{
				swap(first, second);
			}
		}
		bool operator < (const MyPair& other) const
		{
			return second<other.first;
		}
		int first=0, second=0;
		operator string() const
		{
			stringstream ss;
			ss<<"["<<first<<","<<second<<"]";
			return ss.str();
		}
	};
	srand(time(nullptr));
	set<MyPair> s;
	for (int i=0; i<10; i++)
	{
		int first=rand()%100+1;
		int second=first+rand()%20;
		while (first==second)
		{
			first=rand()%100+1;
			second=first+rand()%20;;
		}
		MyPair p(first, second);
		bool b;
		std::tie(std::ignore, b)=s.insert(p);
		if (!b)
		{
			cout<<"insert "<<p.operator string()<<" failed"<<endl;
		}
	}
	for (auto p:s)
	{
		cout<<string(p)<<",";
	}
	MyPair np;
	cout<<endl<<"about to insert new range:"<<np.operator string()<<endl;

int first=np.first, second=np.second;
	set<MyPair>::iterator low, up;
	std::tie(low, up)=s.equal_range(np);
	if (low!=s.end())
	{
		cout<<"lower bound:"<<low->operator string()<<endl;
		first=std::min(low->first, np.first);
		second=std::max(low->second, np.second);
	}
	else
	{
		cout<<"lower bound: not found"<<endl;
		first=std::min(s.begin()->first, np.first);
		second=std::max(s.begin()->second, np.second);
	}
	if (up!=s.end())
	{

auto ptr=up;
		ptr--;
		cout<<"upper bound(adjust):"<<ptr->operator string()<<endl;
		first=std::min(np.first, ptr->first);
		second=std::max(np.second, ptr->second);
	}
	else
	{
		auto ptr=s.begin();
		for (size_t i=0; i<s.size()-1; i++, ptr++)
		{
			;
		}
		cout<<"upper bound(calculated):"<<ptr->operator string()<<endl;
		first=std::min(np.first, ptr->first);
		second=std::max(np.second, ptr->second);
	}
	MyPair newPair(first, second);
	s.erase(low, up);
	s.insert(newPair);

for (auto p:s)
	{
		cout<<string(p)<<",";
	}
	cout<<endl;
}
void test171()
{
	struct MyPair
	{
		MyPair(int f, int s)
		{
			first=std::min(f, s);
			second=std::max(f, s);
		}
		MyPair()
		{
			while (first==second)
			{
				first=rand()%100+1;
				second=rand()%100+1;
			}
			if (second<first)
			{
				swap(first, second);
			}
		}
		bool operator < (const MyPair& other) const
		{
			return second<other.first;
		}
		int first=0, second=0;
		operator string() const
		{
			stringstream ss;
			ss<<"["<<first<<","<<second<<"]";
			return ss.str();
		}
	};
	srand(time(nullptr));
	set<MyPair> s;
	for (int i=0; i<10; i++)
	{
		int first=rand()%100+1;
		int second=first+rand()%20;
		while (first==second)
		{
			first=rand()%100+1;
			second=first+rand()%20;;
		}
		MyPair p(first, second);
		bool b;
		std::tie(std::ignore, b)=s.insert(p);
		if (!b)
		{
			cout<<"insert "<<p.operator string()<<" failed"<<endl;
		}
	}
	for (auto p:s)
	{
		cout<<string(p)<<",";
	}
	MyPair np;
	cout<<endl<<"about to insert new range:"<<np.operator string()<<endl;
	int first=np.first, second=np.second;
	if (np < *s.begin())
	{
		s.insert(np);
	}
	else
	{
		set<MyPair>::iterator low=s.end(), up=s.end();
		for (auto it=s.begin(); it!=s.end(); it++)
		{
			if (!(np<*it) && !(*it<np))
			{
				if (low==s.end())
				{
					low=it;
					cout<<"found lower bound:"<<low->operator string()<<endl;
				}
				first=std::min(np.first, it->first);
				second=std::max(np.second, it->second);
			}
			else
			{
				if (np<*it)
				{
					up=it;
					cout<<"found upper bound:"<<up->operator string()<<endl;
					break;
				}
			}
		}
		MyPair newPair(first, second);
		s.erase(low, up);
		s.insert(newPair);
	}
	for (auto p:s)
	{
		cout<<string(p)<<",";
	}
	cout<<endl;
}

十一月二十四日等待变化等待机会

结果是这样子的，注意这里忽略了空集，所以，可以很容易验证2⁹=512

subset size:511 { 1}{ 2}{ 3}{ 4}{ 5}{ 6}{ 7}{ 8}{ 9}{ 1 2}{ 1 3}{ 1 4}{ 1 5}{ 1 6}{ 1 7}{ 1 8}{ 1 9}{ 2 3}{ 2 4}{ 2 5}{ 2 6}{ 2 7}{ 2 8}{ 2 9}{ 3 4}{ 3 5}{ 3 6}{ 3 7}{ 3 8}{ 3 9}{ 4 5}{ 4 6}{ 4 7}{ 4 8}{ 4 9}{ 5 6}{ 5 7}{ 5 8}{ 5 9}{ 6 7}{ 6 8}{ 6 9}{ 7 8}{ 7 9}{ 8 9}{ 1 2 3}{ 1 2 4}{ 1 2 5}{ 1 2 6}{ 1 2 7}{ 1 2 8}{ 1 2 9}{ 1 3 4}{ 1 3 5}{ 1 3 6}{ 1 3 7}{ 1 3 8}{ 1 3 9}{ 1 4 5}{ 1 4 6}{ 1 4 7}{ 1 4 8}{ 1 4 9}{ 1 5 6}{ 1 5 7}{ 1 5 8}{ 1 5 9}{ 1 6 7}{ 1 6 8}{ 1 6 9}{ 1 7 8}{ 1 7 9}{ 1 8 9}{ 2 3 4}{ 2 3 5}{ 2 3 6}{ 2 3 7}{ 2 3 8}{ 2 3 9}{ 2 4 5}{ 2 4 6}{ 2 4 7}{ 2 4 8}{ 2 4 9}{ 2 5 6}{ 2 5 7}{ 2 5 8}{ 2 5 9}{ 2 6 7}{ 2 6 8}{ 2 6 9}{ 2 7 8}{ 2 7 9}{ 2 8 9}{ 3 4 5}{ 3 4 6}{ 3 4 7}{ 3 4 8}{ 3 4 9}{ 3 5 6}{ 3 5 7}{ 3 5 8}{ 3 5 9}{ 3 6 7}{ 3 6 8}{ 3 6 9}{ 3 7 8}{ 3 7 9}{ 3 8 9}{ 4 5 6}{ 4 5 7}{ 4 5 8}{ 4 5 9}{ 4 6 7}{ 4 6 8}{ 4 6 9}{ 4 7 8}{ 4 7 9}{ 4 8 9}{ 5 6 7}{ 5 6 8}{ 5 6 9}{ 5 7 8}{ 5 7 9}{ 5 8 9}{ 6 7 8}{ 6 7 9}{ 6 8 9}{ 7 8 9}{ 1 2 3 4}{ 1 2 3 5}{ 1 2 3 6}{ 1 2 3 7}{ 1 2 3 8}{ 1 2 3 9}{ 1 2 4 5}{ 1 2 4 6}{ 1 2 4 7}{ 1 2 4 8}{ 1 2 4 9}{ 1 2 5 6}{ 1 2 5 7}{ 1 2 5 8}{ 1 2 5 9}{ 1 2 6 7}{ 1 2 6 8}{ 1 2 6 9}{ 1 2 7 8}{ 1 2 7 9}{ 1 2 8 9}{ 1 3 4 5}{ 1 3 4 6}{ 1 3 4 7}{ 1 3 4 8}{ 1 3 4 9}{ 1 3 5 6}{ 1 3 5 7}{ 1 3 5 8}{ 1 3 5 9}{ 1 3 6 7}{ 1 3 6 8}{ 1 3 6 9}{ 1 3 7 8}{ 1 3 7 9}{ 1 3 8 9}{ 1 4 5 6}{ 1 4 5 7}{ 1 4 5 8}{ 1 4 5 9}{ 1 4 6 7}{ 1 4 6 8}{ 1 4 6 9}{ 1 4 7 8}{ 1 4 7 9}{ 1 4 8 9}{ 1 5 6 7}{ 1 5 6 8}{ 1 5 6 9}{ 1 5 7 8}{ 1 5 7 9}{ 1 5 8 9}{ 1 6 7 8}{ 1 6 7 9}{ 1 6 8 9}{ 1 7 8 9}{ 2 3 4 5}{ 2 3 4 6}{ 2 3 4 7}{ 2 3 4 8}{ 2 3 4 9}{ 2 3 5 6}{ 2 3 5 7}{ 2 3 5 8}{ 2 3 5 9}{ 2 3 6 7}{ 2 3 6 8}{ 2 3 6 9}{ 2 3 7 8}{ 2 3 7 9}{ 2 3 8 9}{ 2 4 5 6}{ 2 4 5 7}{ 2 4 5 8}{ 2 4 5 9}{ 2 4 6 7}{ 2 4 6 8}{ 2 4 6 9}{ 2 4 7 8}{ 2 4 7 9}{ 2 4 8 9}{ 2 5 6 7}{ 2 5 6 8}{ 2 5 6 9}{ 2 5 7 8}{ 2 5 7 9}{ 2 5 8 9}{ 2 6 7 8}{ 2 6 7 9}{ 2 6 8 9}{ 2 7 8 9}{ 3 4 5 6}{ 3 4 5 7}{ 3 4 5 8}{ 3 4 5 9}{ 3 4 6 7}{ 3 4 6 8}{ 3 4 6 9}{ 3 4 7 8}{ 3 4 7 9}{ 3 4 8 9}{ 3 5 6 7}{ 3 5 6 8}{ 3 5 6 9}{ 3 5 7 8}{ 3 5 7 9}{ 3 5 8 9}{ 3 6 7 8}{ 3 6 7 9}{ 3 6 8 9}{ 3 7 8 9}{ 4 5 6 7}{ 4 5 6 8}{ 4 5 6 9}{ 4 5 7 8}{ 4 5 7 9}{ 4 5 8 9}{ 4 6 7 8}{ 4 6 7 9}{ 4 6 8 9}{ 4 7 8 9}{ 5 6 7 8}{ 5 6 7 9}{ 5 6 8 9}{ 5 7 8 9}{ 6 7 8 9}{ 1 2 3 4 5}{ 1 2 3 4 6}{ 1 2 3 4 7}{ 1 2 3 4 8}{ 1 2 3 4 9}{ 1 2 3 5 6}{ 1 2 3 5 7}{ 1 2 3 5 8}{ 1 2 3 5 9}{ 1 2 3 6 7}{ 1 2 3 6 8}{ 1 2 3 6 9}{ 1 2 3 7 8}{ 1 2 3 7 9}{ 1 2 3 8 9}{ 1 2 4 5 6}{ 1 2 4 5 7}{ 1 2 4 5 8}{ 1 2 4 5 9}{ 1 2 4 6 7}{ 1 2 4 6 8}{ 1 2 4 6 9}{ 1 2 4 7 8}{ 1 2 4 7 9}{ 1 2 4 8 9}{ 1 2 5 6 7}{ 1 2 5 6 8}{ 1 2 5 6 9}{ 1 2 5 7 8}{ 1 2 5 7 9}{ 1 2 5 8 9}{ 1 2 6 7 8}{ 1 2 6 7 9}{ 1 2 6 8 9}{ 1 2 7 8 9}{ 1 3 4 5 6}{ 1 3 4 5 7}{ 1 3 4 5 8}{ 1 3 4 5 9}{ 1 3 4 6 7}{ 1 3 4 6 8}{ 1 3 4 6 9}{ 1 3 4 7 8}{ 1 3 4 7 9}{ 1 3 4 8 9}{ 1 3 5 6 7}{ 1 3 5 6 8}{ 1 3 5 6 9}{ 1 3 5 7 8}{ 1 3 5 7 9}{ 1 3 5 8 9}{ 1 3 6 7 8}{ 1 3 6 7 9}{ 1 3 6 8 9}{ 1 3 7 8 9}{ 1 4 5 6 7}{ 1 4 5 6 8}{ 1 4 5 6 9}{ 1 4 5 7 8}{ 1 4 5 7 9}{ 1 4 5 8 9}{ 1 4 6 7 8}{ 1 4 6 7 9}{ 1 4 6 8 9}{ 1 4 7 8 9}{ 1 5 6 7 8}{ 1 5 6 7 9}{ 1 5 6 8 9}{ 1 5 7 8 9}{ 1 6 7 8 9}{ 2 3 4 5 6}{ 2 3 4 5 7}{ 2 3 4 5 8}{ 2 3 4 5 9}{ 2 3 4 6 7}{ 2 3 4 6 8}{ 2 3 4 6 9}{ 2 3 4 7 8}{ 2 3 4 7 9}{ 2 3 4 8 9}{ 2 3 5 6 7}{ 2 3 5 6 8}{ 2 3 5 6 9}{ 2 3 5 7 8}{ 2 3 5 7 9}{ 2 3 5 8 9}{ 2 3 6 7 8}{ 2 3 6 7 9}{ 2 3 6 8 9}{ 2 3 7 8 9}{ 2 4 5 6 7}{ 2 4 5 6 8}{ 2 4 5 6 9}{ 2 4 5 7 8}{ 2 4 5 7 9}{ 2 4 5 8 9}{ 2 4 6 7 8}{ 2 4 6 7 9}{ 2 4 6 8 9}{ 2 4 7 8 9}{ 2 5 6 7 8}{ 2 5 6 7 9}{ 2 5 6 8 9}{ 2 5 7 8 9}{ 2 6 7 8 9}{ 3 4 5 6 7}{ 3 4 5 6 8}{ 3 4 5 6 9}{ 3 4 5 7 8}{ 3 4 5 7 9}{ 3 4 5 8 9}{ 3 4 6 7 8}{ 3 4 6 7 9}{ 3 4 6 8 9}{ 3 4 7 8 9}{ 3 5 6 7 8}{ 3 5 6 7 9}{ 3 5 6 8 9}{ 3 5 7 8 9}{ 3 6 7 8 9}{ 4 5 6 7 8}{ 4 5 6 7 9}{ 4 5 6 8 9}{ 4 5 7 8 9}{ 4 6 7 8 9}{ 5 6 7 8 9}{ 1 2 3 4 5 6}{ 1 2 3 4 5 7}{ 1 2 3 4 5 8}{ 1 2 3 4 5 9}{ 1 2 3 4 6 7}{ 1 2 3 4 6 8}{ 1 2 3 4 6 9}{ 1 2 3 4 7 8}{ 1 2 3 4 7 9}{ 1 2 3 4 8 9}{ 1 2 3 5 6 7}{ 1 2 3 5 6 8}{ 1 2 3 5 6 9}{ 1 2 3 5 7 8}{ 1 2 3 5 7 9}{ 1 2 3 5 8 9}{ 1 2 3 6 7 8}{ 1 2 3 6 7 9}{ 1 2 3 6 8 9}{ 1 2 3 7 8 9}{ 1 2 4 5 6 7}{ 1 2 4 5 6 8}{ 1 2 4 5 6 9}{ 1 2 4 5 7 8}{ 1 2 4 5 7 9}{ 1 2 4 5 8 9}{ 1 2 4 6 7 8}{ 1 2 4 6 7 9}{ 1 2 4 6 8 9}{ 1 2 4 7 8 9}{ 1 2 5 6 7 8}{ 1 2 5 6 7 9}{ 1 2 5 6 8 9}{ 1 2 5 7 8 9}{ 1 2 6 7 8 9}{ 1 3 4 5 6 7}{ 1 3 4 5 6 8}{ 1 3 4 5 6 9}{ 1 3 4 5 7 8}{ 1 3 4 5 7 9}{ 1 3 4 5 8 9}{ 1 3 4 6 7 8}{ 1 3 4 6 7 9}{ 1 3 4 6 8 9}{ 1 3 4 7 8 9}{ 1 3 5 6 7 8}{ 1 3 5 6 7 9}{ 1 3 5 6 8 9}{ 1 3 5 7 8 9}{ 1 3 6 7 8 9}{ 1 4 5 6 7 8}{ 1 4 5 6 7 9}{ 1 4 5 6 8 9}{ 1 4 5 7 8 9}{ 1 4 6 7 8 9}{ 1 5 6 7 8 9}{ 2 3 4 5 6 7}{ 2 3 4 5 6 8}{ 2 3 4 5 6 9}{ 2 3 4 5 7 8}{ 2 3 4 5 7 9}{ 2 3 4 5 8 9}{ 2 3 4 6 7 8}{ 2 3 4 6 7 9}{ 2 3 4 6 8 9}{ 2 3 4 7 8 9}{ 2 3 5 6 7 8}{ 2 3 5 6 7 9}{ 2 3 5 6 8 9}{ 2 3 5 7 8 9}{ 2 3 6 7 8 9}{ 2 4 5 6 7 8}{ 2 4 5 6 7 9}{ 2 4 5 6 8 9}{ 2 4 5 7 8 9}{ 2 4 6 7 8 9}{ 2 5 6 7 8 9}{ 3 4 5 6 7 8}{ 3 4 5 6 7 9}{ 3 4 5 6 8 9}{ 3 4 5 7 8 9}{ 3 4 6 7 8 9}{ 3 5 6 7 8 9}{ 4 5 6 7 8 9}{ 1 2 3 4 5 6 7}{ 1 2 3 4 5 6 8}{ 1 2 3 4 5 6 9}{ 1 2 3 4 5 7 8}{ 1 2 3 4 5 7 9}{ 1 2 3 4 5 8 9}{ 1 2 3 4 6 7 8}{ 1 2 3 4 6 7 9}{ 1 2 3 4 6 8 9}{ 1 2 3 4 7 8 9}{ 1 2 3 5 6 7 8}{ 1 2 3 5 6 7 9}{ 1 2 3 5 6 8 9}{ 1 2 3 5 7 8 9}{ 1 2 3 6 7 8 9}{ 1 2 4 5 6 7 8}{ 1 2 4 5 6 7 9}{ 1 2 4 5 6 8 9}{ 1 2 4 5 7 8 9}{ 1 2 4 6 7 8 9}{ 1 2 5 6 7 8 9}{ 1 3 4 5 6 7 8}{ 1 3 4 5 6 7 9}{ 1 3 4 5 6 8 9}{ 1 3 4 5 7 8 9}{ 1 3 4 6 7 8 9}{ 1 3 5 6 7 8 9}{ 1 4 5 6 7 8 9}{ 2 3 4 5 6 7 8}{ 2 3 4 5 6 7 9}{ 2 3 4 5 6 8 9}{ 2 3 4 5 7 8 9}{ 2 3 4 6 7 8 9}{ 2 3 5 6 7 8 9}{ 2 4 5 6 7 8 9}{ 3 4 5 6 7 8 9}{ 1 2 3 4 5 6 7 8}{ 1 2 3 4 5 6 7 9}{ 1 2 3 4 5 6 8 9}{ 1 2 3 4 5 7 8 9}{ 1 2 3 4 6 7 8 9}{ 1 2 3 5 6 7 8 9}{ 1 2 4 5 6 7 8 9}{ 1 3 4 5 6 7 8 9}{ 2 3 4 5 6 7 8 9}{ 1 2 3 4 5 6 7 8 9}

在这个基础上我们来实现固定大小的子集的产生

vector<int> v{1,2,3,4,5,6,7,8,9};
	auto generateN=[](size_t N, const vector<int>& src, vector<vector<int>>& subset)
	{
		for (size_t i=0; i<src.size(); i++)
		{
			auto nextSubset=subset;
			for (size_t j=0; j<nextSubset.size(); j++)
			{
				auto v=nextSubset[j];
				if (v.size()<N)
				{
					v.push_back(src[i]);
					subset.push_back(v);
				}
			}
			subset.push_back(vector<int>{src[i]});
		}
		// now trim
		std::sort(subset.begin(), subset.end(), [](auto&a,auto&b){return a.size()>b.size();});
		size_t pos;
		for (size_t i=0; i<subset.size(); i++)
		{
			if (subset[i].size()<N)
			{
				pos=i;
				break;
			}
		}
		subset.resize(pos);
	};
	auto print=[](const vector<vector<int>>& v)
		{
			for (auto vi:v)
			{
				cout<<"{";
				for (auto i:vi)
				{
					cout<<setw(2)<<i;
				}
				cout<<"}";
			}
		};
	vector<vector<int>> subsets;
	generateN(5, v, subsets);
	cout<<"subset size:"<<subsets.size()<<endl;
	std::sort(subsets.begin(), subsets.end(),[](auto& a, auto& b)
		{
			if (a.size()!=b.size())
			{
				return a.size()<b.size();
			}
			else
			{
				return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
			}
		});
	print(subsets);

这个纯粹是好奇的实验，假如sudoku的9个数字里有重复的数字，我们能否依靠加总他们的和来发现是什么数字重复了几次呢？这个纯粹是不可能，用脚趾头想也知道无意义，我却想看看也许有什么特殊的分布可以利用？实际上完全没有

void test176()
{
	vector<int> v{1,2,3,4,5,6,7,8,9};
	auto generateN=[](size_t N, const vector<int>& src, vector<vector<int>>& subset)
	{
		for (size_t i=0; i<src.size(); i++)
		{
			auto nextSubset=subset;
			for (size_t j=0; j<nextSubset.size(); j++)
			{
				auto v=nextSubset[j];
				if (v.size()<N)
				{
					v.push_back(src[i]);
					subset.push_back(v);
				}
			}
			subset.push_back(vector<int>{src[i]});
		}
		std::sort(subset.begin(), subset.end(), [](auto&a,auto&b)
				{
					if (a.size()!=b.size()) return a.size()>b.size();
					else return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
				});
		auto p=std::find_if(subset.begin(),subset.end(), [&N](auto& s){return s.size()<N;});
		if (p!=subset.end())
		{
			subset.resize(p-subset.begin());
		}
	};
	struct Struct
	{
		std::set<int> sums;
		std::pair<int, int> id;
	};
	vector<Struct> results;
	for (int size=2; size<8; size++)
	{
		vector<vector<int>> subsets;
		generateN(9-size, v, subsets);
		for (int num=1; num<=9; num++)
		{
			Struct numStruct;
			numStruct.id=make_pair(num, size);
			for (auto vi:subsets)
			{
				int sum=0;
				bool bFound=false;
				for (size_t i=0; i <vi.size(); i++)
				{
					if (num!=vi[i])
					{
						sum+=vi[i];
					}
					else
					{
						bFound=true;
						break;
					}
				}
				if (!bFound)
				{
					numStruct.sums.insert(sum+num*size);
				}
			}
			results.push_back(numStruct);
		}
	}
	auto printStruct=[](const vector<Struct>&vs)
	{
		for (auto& s:vs)
		{
			cout<<"{num:"<<s.id.first<<",size:"<<s.id.second<<",sums:";
			for (auto i:s.sums)
			{
				cout<<setw(4)<<i;
			}
			cout<<"}\n";
		}
	};
	printStruct(results);
}

从这个结果来看完全没有办法

{num:1,size:2,sums:  37  38  39  40  41  42  43  44}
{num:2,size:2,sums:  38  39  40  41  42  43  44  46}
{num:3,size:2,sums:  39  40  41  42  43  44  46  47}
{num:4,size:2,sums:  40  41  42  43  44  46  47  48}
{num:5,size:2,sums:  41  42  43  44  46  47  48  49}
{num:6,size:2,sums:  42  43  44  46  47  48  49  50}
{num:7,size:2,sums:  43  44  46  47  48  49  50  51}
{num:8,size:2,sums:  44  46  47  48  49  50  51  52}
{num:9,size:2,sums:  46  47  48  49  50  51  52  53}
{num:1,size:3,sums:  30  31  32  33  34  35  36  37  38  39  40  41  42}
{num:2,size:3,sums:  32  33  34  35  36  37  38  39  40  41  42  43  44  45}
{num:3,size:3,sums:  34  35  36  37  38  39  40  41  42  43  44  45  46  48}
{num:4,size:3,sums:  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50}
{num:5,size:3,sums:  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52}
{num:6,size:3,sums:  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54}
{num:7,size:3,sums:  42  44  45  46  47  48  49  50  51  52  53  54  55  56}
{num:8,size:3,sums:  45  46  47  48  49  50  51  52  53  54  55  56  57  58}
{num:9,size:3,sums:  48  49  50  51  52  53  54  55  56  57  58  59  60}
{num:1,size:4,sums:  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39}
{num:2,size:4,sums:  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43}
{num:3,size:4,sums:  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47}
{num:4,size:4,sums:  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  51}
{num:5,size:4,sums:  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54}
{num:6,size:4,sums:  39  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57}
{num:7,size:4,sums:  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60}
{num:8,size:4,sums:  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63}
{num:9,size:4,sums:  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66}
{num:1,size:5,sums:  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35}
{num:2,size:5,sums:  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40}
{num:3,size:5,sums:  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45}
{num:4,size:5,sums:  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50}
{num:5,size:5,sums:  35  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  55}
{num:6,size:5,sums:  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59}
{num:7,size:5,sums:  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63}
{num:8,size:5,sums:  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67}
{num:9,size:5,sums:  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71}
{num:1,size:6,sums:  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30}
{num:2,size:6,sums:  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36}
{num:3,size:6,sums:  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42}
{num:4,size:6,sums:  30  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48}
{num:5,size:6,sums:  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54}
{num:6,size:6,sums:  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  60}
{num:7,size:6,sums:  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65}
{num:8,size:6,sums:  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70}
{num:9,size:6,sums:  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75}
{num:1,size:7,sums:  12  13  14  15  16  17  18  19  20  21  22  23  24}
{num:2,size:7,sums:  18  19  20  21  22  23  24  25  26  27  28  29  30  31}
{num:3,size:7,sums:  24  26  27  28  29  30  31  32  33  34  35  36  37  38}
{num:4,size:7,sums:  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45}
{num:5,size:7,sums:  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52}
{num:6,size:7,sums:  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59}
{num:7,size:7,sums:  52  53  54  55  56  57  58  59  60  61  62  63  64  66}
{num:8,size:7,sums:  59  60  61  62  63  64  65  66  67  68  69  70  71  72}
{num:9,size:7,sums:  66  67  68  69  70  71  72  73  74  75  76  77  78}

十一月二十五日等待变化等待机会

给定一个数列，寻找任何一条最长的钟摆其实难度在于寻找所有的最长的钟摆，这个有些麻烦在于stl里没有tree，需要自己定义就很麻烦，因此我只能返回所有的中间过程然后再删除保留最长的。

int size=rand()%20+10;
	vector<int> v(size);
	for (auto&i:v){i=rand()%20+1;}
	v.assign(initializer_list<int>{1,17,5,10,13,15,10,5,16,8});
	for (auto i:v)cout<<i<<",";
	cout<<endl;
	std::function<void(vector<vector<int>>&, vector<int>&, const vector<int>&)> recurse;
	recurse=[&recurse](vector<vector<int>>&results, vector<int>&left, const vector<int>&right)
	{
		if (right.empty())
		{
			return;
		}
		int candidate=right.front();
		vector<int> rightCopy{right.begin()+1, right.end()};
		if (left.size()==1 && left.back()==candidate)
		{
			return;
		}
		if (left.size()>1)
		{
			int prev=left[left.size()-2]-left.back();
			int next=left.back()-candidate;
			if (prev*next>=0)
			{
				return;
			}
		}
		vector<int>leftHolder=left;
		recurse(results, left, rightCopy);
		vector<int>leftCopy=left;
		left=leftHolder;
		left.push_back(candidate);
		recurse(results, left, rightCopy);

if (left.size()>leftCopy.size())
		{
			results.push_back(left);
		}
		else if (leftCopy.size()>left.size())
		{
			results.push_back(leftCopy);
		}
		else
		{
			results.push_back(left);
			results.push_back(leftCopy);
		}
	};
	auto verify=[](const vector<int>vect)
		{
			vector<int>vi;
			std::adjacent_difference(vect.begin(), vect.end(), std::back_inserter(vi));
			std::vector<int> vr;
			std::adjacent_difference(vi.begin()+1, vi.end(), std::back_inserter(vr), [](auto a,auto b){return a*b;});
			return std::none_of(vr.begin()+1, vr.end(), [](auto a){return a>=0;});
		};
	vector<vector<int>> results;
	vector<int>left;
	recurse(results, left, v);
	std::sort(results.begin(), results.end(),[](auto& a, auto&b){return a.size()>b.size();});
	std::unique(results.begin(), results.end());
	auto p=std::find_if(results.begin(),results.end(),[&results](auto& i){return i.size()<results.front().size();});
	results.resize(p-results.begin());
	for (auto vi:results)
	{
		if (!verify(vi))
		{
			cout<<"found unexpected result:";
		}
		for (auto i:vi)
		{
			cout<<i<<",";
		}
		cout<<endl;
	}

这个是题目里的例子1,17,5,10,13,15,10,5,16,8,的结果对于最大连续子数组的问题比较简单在于连续，所以比上面的问题来的容易些。有人对于子数组的起始去做优化寻找正数作为开始点，可是对于数组全部为负数这个“贪心”算法不成立。这个是我的改进以便返回最大的子数组。

十一月三十日等待变化等待机会

这是一个不难的小题目，可是我却花了好长时间，就是bit的操作很久不用生疏了。

十二月二日等待变化等待机会

这个关于“墙和灯光”的著名的问题，我似乎以前听说过，真的做起来花了很多时间，主要是我想找到一个好的处理二维数组的方式，现在看起来还是valarray有一些优势。

srand(time(nullptr));
	size_t Row=rand()%10+5, Col=rand()%10+5;
	size_t Stride=Col;
	valarray<char> grid(Row*Col);
	valarray<int> ary(Row*Col);
	size_t Walls=rand()%(Row*Col/4)+1;
	size_t Lights=rand()%(Row*Col/4)+1;
	auto print=[&Row, &Col, &Stride](auto& aArray)
	{
		for(size_t r=0; r<Row; r++)
		{
			for (size_t c=0; c<Col; c++)
			{
				cout<<setw(4)<<aArray[r*Stride+c];
			}
			cout<<endl;
		}
		cout<<endl;
	};

for (size_t i=0; i<grid.size(); i++)
	{
		if (Walls)
		{
			grid[i]='W';
			Walls--;
		}
		else if (Lights)
		{
			grid[i]='L';
			Lights--;
		}
		else
		{
			grid[i]='E';
		}
	}
	std::random_shuffle(std::begin(grid), std::end(grid));
	std::function<void(size_t, size_t c)> calcRow;
	calcRow=[&Row, &Col, &Stride, &grid, &ary, &calcRow](size_t r, size_t c)
	{
		if (r>=Row||c>=Col)
		{
			return;
		}
		auto row=valarray(grid[slice(r*Stride+c, Col-c, 1)]);
		auto p=find_if(std::begin(row), std::end(row), [](auto ch)
		{
			return ch=='W';
		});
		size_t sum=std::count_if(std::begin(row), p, [](auto ch){return ch=='L';});
		size_t offset=std::distance(std::begin(row), p);
		ary[slice(r*Stride+c, offset, 1)]=sum;
		if (p!=std::end(row))
		{
			calcRow(r, c+offset+1);
		}
	};
	std::function<void(size_t, size_t c)> calcCol;
	calcCol=[&Row, &Col, &Stride, &grid, &ary, &calcCol](size_t r, size_t c)
	{
		if (r>=Row||c>=Col)
		{
			return;
		}
		auto col=valarray(grid[slice(r*Stride+c, Row-r, Col)]);
		auto p=find_if(std::begin(col), std::end(col), [](auto ch)
		{
			return ch=='W';
		});
		size_t sum=std::count_if(std::begin(col), p, [](auto ch){return ch=='L';});
		size_t offset=std::distance(std::begin(col), p);
		for (size_t i=0; i<offset; i++)
		{
			size_t index=r*Stride+c+i*Stride;
			ary[index]+=sum-(grid[index]=='L'?1:0);
		}

if (p!=std::end(col))
		{
			calcCol(r+offset+1, c);
		}
	};
	print(grid);
	for (size_t r=0; r<Row; r++)
	{
		calcRow(r, 0);
	}
	print(ary);
	for (size_t c=0; c<Col; c++)
	{
		calcCol(0, c);
	}
	print(ary);
	cout<<"max:"<<ary.max()<<endl;

这个是测试的例子这个是一个cross-word的小游戏程序

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

class Solution {
	public:
	    vector<string> findWords(vector<vector<char>>& board, vector<string>& words)
	    {
	        auto up=[&board](size_t r, size_t c, char ch, const vector<vector<bool>>&path)
	        {
	            if (r==0) return false;
	            return (board[r-1][c]==ch&&!path[r-1][c]);
	        };
	        auto down=[&board](size_t r, size_t c, char ch, const vector<vector<bool>>&path)
	        {
	            if (r==board.size()-1) return false;
	            return (board[r+1][c]==ch&&!path[r+1][c]);
	        };
	        auto left=[&board](size_t r, size_t c, char ch, const vector<vector<bool>>&path)
	        {
	            if (c==0)return false;
	            return (board[r][c-1]==ch &&!path[r][c-1]);
	        };
	        auto right=[&board](size_t r, size_t c, char ch, const vector<vector<bool>>&path)
	        {
	            if (c==board[0].size()-1)return false;
	            return (board[r][c+1]==ch &&!path[r][c+1]);
	        };
	        std::function<bool(size_t, size_t, const string&, vector<vector<bool>>&)> search;
	        search=[&search,&board,&up,&down,&left,&right](size_t r, size_t c, const string& word,
	        		vector<vector<bool>>&path)->bool
	        {
	            path[r][c]=true;
	            if (word.empty())
	            {
	                return true;
	            }
	            if (up(r, c, word[0], path))
	            {
	                vector<vector<bool>>subPath(path);
	                if (search(r-1, c, word.substr(1), subPath))
	                {
	                    return true;
	                }
	            }
	            if (down(r, c, word[0], path))
	            {
	                vector<vector<bool>>subPath(path);
	                if (search(r+1, c, word.substr(1), subPath))
	                {
	                    return true;
	                }
	            }
	            if (left(r, c, word[0], path))
	            {
	                vector<vector<bool>>subPath(path);
	                if (search(r, c-1, word.substr(1), subPath))
	                {
	                    return true;
	                }
	            }
	            if (right(r, c, word[0], path))
	            {
	                vector<vector<bool>>subPath(path);
	                if (search(r, c+1, word.substr(1), subPath))
	                {
	                    return true;
	                }
	            }
	          return false;
	        };
	        auto startSearch=[&board,&search](const string& word)->bool
	        {
	            for (size_t r=0; r<board.size(); r++)
	            {
	                for (size_t c=0; c<board[0].size(); c++)
	                {
	                    if (board[r][c]==word[0])
	                    {
	                        vector<vector<bool>>path;
	                        for (size_t i=0; i<board.size(); i++)
	                        {
	                            vector<bool> item(board[0].size(), false);
	                            path.push_back(item);
	                        }
	                        if (search(r, c, word.substr(1), path))
	                        {
	                            return true;
	                        }
	                    }
	                }
	            }
	            return false;
	        };
	        vector<string> result;
	        for (auto word:words)
	        {
	            if (startSearch(word))
	            {
	                result.push_back(word);
	            }
	        }
	        return result;
	    }
	};

十二月三日等待变化等待机会

这个题目对我的帮助很大就在于我看了得分最高的大侠的方案大为叹服，不论内存消耗还是代码简洁清晰，算法的洗练都是当之无愧的高高手的杰作。首先我意识到了我长久依赖的一个毛病，我一直想改掉但是总是不成功，就是stack unwinding的问题，在搜索中维持一个context是非常的昂贵的，如果能够利用递归搜索中的栈的自然的“递归”本质，那么就可以用维护一个全局的状态随着递归深入更新状态与返回回归原来状态，这样子就不用给每一个搜索分支分配一份内存的状态。具体来说就是寻路的路径可以在递归开始的时候更新，在递归返回的时候恢复，这个是浅显的道理，之所以我以前一直很害怕这个简单的逻辑是担心走回头路的打转转，那么只要你能够保证你的选择没有回到上一级的出发地的机制，这个就是没有问题的。比如大侠的做法是连路径的一个记录都省却了，而是直接利用参数的“grid”既作为寻路的地图，也作为寻路的路径的辅助，这个当然是很巧妙，但是我不是特别的喜欢，因为作为极限编程固然节省了内存但是从维护的角度来看不是很好的做法。我的态度是欣赏但是不愿意模仿。我的代码不算优秀但是我自己看得懂，而且有一些中规中局的“大众”风格。

class Solution {    
public:
    int uniquePathsIII(vector<vector<int>>& grid) 
    {       
        int count=0;
        for (auto r:grid)
        {
            for (auto c:r)
            {
                if (c==0)count++;
            }
        }
        std::function<int(int, int, int, vector<vector<bool>>&)> Search;
        Search=[&grid, &Search](int r, int c, int step, vector<vector<bool>>&path)->int
        {
            if (r<0||c<0||r==grid.size()||c==grid[0].size()||grid[r][c]==1
                ||grid[r][c]==-1||path[r][c])
            {
                return 0;
            }    
            if (grid[r][c]==2)
            {
               if (step==0)
                    return 1;
                else
                    return 0;
            }            
            path[r][c]=true;
            int results= Search(r+1,c,step-1, path)+Search(r-1,c,step-1, path)
                +Search(r,c+1,step-1, path)+Search(r,c-1,step-1, path);                    
            path[r][c]=false;
            return results;
        };
        
        for (int r=0; r<grid.size(); r++)
        {
            for (int c=0; c<grid[0].size(); c++)
            {
                if (grid[r][c]==1)
                {
                    vector<vector<bool>> path;
                    for (size_t i=0; i<grid.size(); i++)
                    {
                        vector<bool> item(grid[0].size(), false);
                        path.push_back(item);
                    }
                    return Search(r+1, c, count, path)+Search(r-1,c,count, path)
                        +Search(r,c+1,count, path)+ Search(r,c-1, count, path);
                }
            }
        }
        return 0;
    }
};

这个题目是难度小一些的反而我花了更多的时间，因为看上去简单，实际上它的要求是不一样的，我使用深度优先的路径搜索是一个overkill，题目不允许因为不必要，有时间限制，所以，反而不是那么的简单，我决定使用广度搜索，因为照例说递归是比循环来的慢，所以，我希望使用deque来加快，看起来大多数人比这个来的快。

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and space is marked as 1 and 0 respectively in the grid.

我的解答我认为是中规中居的平均，但是看起来比平均还茶很多，需要看看别人的解答差距在哪里。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
    {
        int M=obstacleGrid.size(), N=obstacleGrid[0].size();
        std::vector<vector<int>> grid;
        for (auto v:obstacleGrid)
        {
            vector<int> item(N, 0);
            grid.push_back(item);
        }
        std::deque<pair<int,int>> q;
        if (obstacleGrid[0][0]==1||obstacleGrid[M-1][N-1]==1)
        {
            return 0;
        }
        grid[0][0]=1;
        q.push_back(make_pair(0,0));
        while (!q.empty())
        {
            int r, c;
            std::tie(r,c)=q.front();
            q.pop_front();
            if (r+1!=M&&obstacleGrid[r+1][c]!=1)
            {
                if (grid[r+1][c]==0)
                {
                    grid[r+1][c]=grid[r][c];
                    q.push_back(make_pair(r+1,c));
                }
                else
                {
                    grid[r+1][c]+=grid[r][c];
                }
            }
            if (c+1!=N&&obstacleGrid[r][c+1]!=1)
            {
                if (grid[r][c+1]==0)
                {
                    grid[r][c+1]=grid[r][c];
                    q.push_back(make_pair(r,c+1));
                }
                else
                {
                    grid[r][c+1]=grid[r][c];
                }
            }            
        }
        return grid[M-1][N-1];
    }
};

这个问题我一开始使用组合来做，可是速度太慢了。贪心算法是不对的！

void test194()
{
	class Solution {
	public:
	    int maxSumDivThree(vector<int>& nums)
	    {
	        int results=0;
	        std::multiset<int, std::greater<int>> s1,s2;
	        auto print=[&s1,&s2]()
			{
	        	cout<<"s1:"<<endl;
				for (auto i:s1)cout<<setw(6)<<i;
				cout<<endl;
				cout<<"s2:"<<endl;
				for (auto i:s2)cout<<setw(6)<<i;
				cout<<endl;
			};
	        for (int i: nums)
	        {
	            int mod=i%3;
	            switch (mod)
	            {
	            case 0:
	            results+=i;
	                break;
	            case 1:
	                s1.insert(i);
	                break;
	            case 2:
	                s2.insert(i);
	                break;
	            }
	        }

while (!s1.empty()&&!s2.empty())
	        {
	            int left3=0, right3=0;
	            int both1=*s1.begin()+*s2.begin();
	            if ((s1.size()==3&&s2.size()==2) || (s1.size()==2&&s2.size()==3))
	            {
	            	auto it1=s1.begin();
	            	auto it2=s2.begin();
	            	int left=*it1, right=*it2;;
	            	it1++;
	            	it2++;
	            	int both2=both1+*it1+*it2;
	            	it1++;
	            	it2++;
	            	if (s1.size()==3)
	            	{
	            		left+=*it1++;
	            	}
	            	if (s2.size()==3)
	            	{
	            		right+=*it2++;
	            	}
	            	if (both2>=std::max(left, right))
	            	{
	            		results+=*s1.begin()+*s2.begin();
	            		s1.erase(s1.begin());
	            		s2.erase(s2.begin());
	            	}
	            	else if (left>=right)
	            	{
	            		results+=left;
	            		s1.erase(s1.begin(),it1);
	            	}
	            	else if (right>left)
	            	{
	            		results+=right;
	            		s2.erase(s2.begin(), it2);
	            	}
	            }
	            else
	            {
					if (s1.size()>=3)
					{
						auto it=s1.begin();
						left3+=*it++;
						left3+=*it++;
						left3+=*it++;
					}
					if (s2.size()>=3)
					{
						auto it=s2.begin();
						right3+=*it++;
						right3+=*it++;
						right3+=*it++;
					}
					print();
					cout<<"both:"<<both1<<setw(6)<<"left3:"<<left3<<setw(6)<<"right3:"<<right3<<endl;
					if (both1>=std::max(left3,right3))
					{
						results+=both1;
						s1.erase(s1.begin());
						s2.erase(s2.begin());
					}
					else if (left3>=right3)
					{
						results+=left3;
						auto it=s1.begin();
						it++;
						it++;
						it++;
						s1.erase(s1.begin(), it);
					}
					else if(right3>left3)
					{
						results+=right3;
						auto it=s2.begin();
						it++;
						it++;
						it++;
						s2.erase(s2.begin(), it);
					}
	            }
	        }
	        while (s1.size()>=3)
	        {
	            auto it=s1.begin();
	            results+=*it++;
	            results+=*it++;
	            results+=*it++;
	            s1.erase(s1.begin(), it);
	        }
	        while (s2.size()>=3)
	        {
	            auto it=s2.begin();
	            results+=*it++;
	            results+=*it++;
	            results+=*it++;
	            s2.erase(s2.begin(), it);
	        }
	        return results;
	    }
	};
	vector<int> v{{366,809,6,792,822,181,210,588,344,618,341,410,121,864,191,749,637,
			169,123,472,358,908,235,914,322,946,738,754,908,272,267,326,587,267,803,281,586,707,94,627,724,469,568,57,
			103,984,787,552,14,545,866,494,263,157,479,823,835,100,495,773,729,921,348,871,91,386,183,979,716,806,639,
			290,612,322,289,910,484,300,195,546,499,213,8,623,490,473,603,721,793,418,551,331,598,670,960,483,154,317,
			834,352}};
	cout<<Solution().maxSumDivThree(v)<<endl;
}

答案是50487，而我的结果是50418，主要的原因就是怎么选择最后要剩下哪个，我的简单的贪心算法不成功。参考了大侠的算法，我自己改正我的错误，关键就是说无非最后要去掉至多两个数，这个就是“鸽子原理”，就是说如果需要去掉超过两个数，明显就是错的，因为剩下的三个数里面一定有和是三的倍数，所以是错的。明确的这一点就明白无非是找最后要裁掉谁的问题。我的想法是完全没有道理的，就是总数的余数如果是在1，那么当然我们不可能杜撰出余数是2的组合更小，这个似乎是很直观的，但是我很难证明给自己看。_{我忽然想明白了，我的想法也没有错只不过中间想差了。如果要裁掉的是余数余一，那么当然是一个余一或者两个余二。否则你硬要裁减出一个余二的话，你是做不到的，因为你拿出三个余二的数来与这个余一的反复组合也是徒劳的。因为还是两个余二。原则还是“鸽子原理”不可能超过三两个数。}

class Solution {
	public:
	    int maxSumDivThree(vector<int>& nums)
	    {
	        int sums=0;
	        std::multiset<int, std::greater<int>> s1,s2;

for (int i: nums)
	        {
	            sums+=i;
	            int mod=i%3;
	            switch (mod)
	            {
	            case 1:
	                if(s1.size()<2)
					{
	                	s1.insert(i);
					}
	                else if (*s1.begin()>i)
	                {
	                    s1.erase(s1.begin());
	                    s1.insert(i);
	                }
	                break;
	            case 2:
	                if (s2.size()<2)
	                {
	                	s2.insert(i);
	                }
	                else if (*s2.begin()>i)
	                {
	                    s2.erase(s2.begin());
	                    s2.insert(i);
	                }
	                break;
	            }
	        }
	        int mod=sums%3;
	        int mini=std::numeric_limits<int>::max();
	        switch (mod)
	        {
	            case 0:
	                break;
	            case 1:
	                if (s1.size()>0)
	                {
	                    mini=*s1.rbegin();
	                }
	                if (s2.size()==2)
	                {
	                    mini=std::min(mini, *s2.begin()+*s2.rbegin());
	                }
	                sums-=mini;
	                break;
	            case 2:
	                if (s2.size()>0)
	                {
	                    mini=*s2.rbegin();
	                }
	                if (s1.size()==2)
	                {
	                    mini=std::min(mini, *s1.begin()+*s1.rbegin());
	                }
	                sums-=mini;
	                break;
	        }
	        return sums;
	    }
	};

十二月四日等待变化等待机会

难道这个题目很难吗？为什么我做了这么长时间？最后还是使用比较复杂的容器来存放长度，本来我还打算使用递归来搜索所有的increasing sequence，但是题目仅仅是要求最大长度，所以反而我不知道怎么解决才好。

十二月五日等待变化等待机会

怎么为link list排序呢？

十二月七日等待变化等待机会

这个题目很有意义在于让我练习了一下std::reference_wrapper

Given an array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

这个是参考这个例子来做试验检验reduce相对于inclusive_scan的加速

class dummy_iterator : public iterator<output_iterator_tag, void, void, void, void>{
		long long& res;
	public:
		dummy_iterator(long long&result):res(result){}
		constexpr dummy_iterator& operator*(){return *this;}
		constexpr dummy_iterator& operator++(){return *this;}
		constexpr dummy_iterator& operator++(int){return *this;}
		constexpr dummy_iterator& operator=(const dummy_iterator& other){
			res=other.res;
			return *this;
		}
		constexpr dummy_iterator& operator=(const long long& val){
			res=val;
			return *this;
		}
	};
	srand(time(nullptr));
	std::vector<long long> ary;
	for (int i=0; i<10000; i++)
	{
		ary.push_back(rand()%100+1);
	}
	for(auto&i:ary)cout<<i<<",";
	cout<<endl;
	{
		const auto t1 = std::chrono::high_resolution_clock::now();
		cout<<std::reduce(std::execution::par, std::begin(ary), std::end(ary), 0, std::plus<long long>())<<endl;
		const auto t2 = std::chrono::high_resolution_clock::now();
		cout<<std::chrono::duration<double, std::milli>(t2-t1).count()<<endl;
	}
	{
		long long result=0;
		dummy_iterator it(result);
		const auto t1 = std::chrono::high_resolution_clock::now();
		std::inclusive_scan(std::begin(ary), std::end(ary), it,	std::plus<long long>());
		const auto t2 = std::chrono::high_resolution_clock::now();
		cout<<result<<endl;
		cout<<std::chrono::duration<double, std::milli>(t2-t1).count()<<endl;
	}

运行结果是让人迷惑的，之前似乎有三倍左右的加速，现在看不到了

十二月十五日等待变化等待机会

这个是原来的题目

那么我的程序就是写一系列的约束条件。

void test241()
{
	struct Code
	{
		Code(int pos, int val):position(pos),value(val){;}
		int position=0;
		int value=0;
		operator string() const
		{
			stringstream ss;
			ss<<"position:"<<position<<" value:"<<value<<endl;
			return ss.str();
		}
	};
	vector<Code> data1={Code(1,2),Code(2,4),Code(3,6)};
	vector<Code> data2={Code(1,2),Code(2,5),Code(3,8)};
	vector<Code> data3={Code(1,6),Code(2,9),Code(3,2)};
	vector<Code> data4={Code(1,1),Code(2,7),Code(3,4)};
	vector<Code> data5={Code(1,4),Code(2,1),Code(3,9)};
	vector<vector<Code>>datas={data1,data2,data3,data4,data5};
	auto rule1=[&](const vector<Code>& solution) //one value, position correct
		{
			return (std::count_if(solution.begin(), solution.end(), [&](const Code&code)
					{
						return std::find_if(data1.begin(), data1.end(), [&code](const Code&c)
							{return c.value==code.value&&c.position==code.position;})!=data1.end();
					})==1)  &&
					(std::count_if(solution.begin(), solution.end(), [&](const Code&code)
					{
						return std::find_if(data1.begin(), data1.end(),
								[&code](const Code&c)
							{return c.value==code.value&&c.position!=code.position;}
								)!=data1.end();
					})==0);
		};
	auto rule2=[&](const vector<Code>& solution)
		{
			return (std::count_if(solution.begin(), solution.end(), [&](const Code&code)
				{
					return std::find_if(data2.begin(), data2.end(), [&code](const Code&c)
						{return c.value==code.value&&c.position!=code.position;})!=data2.end();
				})==1)  &&
				(std::count_if(solution.begin(), solution.end(), [&](const Code&code)
				{
					return std::find_if(data2.begin(), data2.end(),
							[&code](const Code&c)
						{return c.value==code.value&&c.position==code.position;}
							)!=data2.end();
				})==0);
		};
	auto rule3=[&](const vector<Code>& solution)
		{
			return (std::count_if(solution.begin(), solution.end(), [&](const Code&code)
				{
					return std::find_if(data3.begin(), data3.end(), [&code](const Code&c)
						{return c.value==code.value&&c.position!=code.position;})!=data3.end();
				})==2)
					&&
				(std::count_if(solution.begin(), solution.end(), [&](const Code&code)
				{
					return std::find_if(data3.begin(), data3.end(),
							[&code](const Code&c)
						{return c.value==code.value&&c.position==code.position;}
							)!=data3.end();
				})==0);
		};
	auto rule4=[&](const vector<Code>& solution)
		{
			return (std::count_if(solution.begin(), solution.end(), [&](const Code&code)
			{
				return std::find_if(data4.begin(), data4.end(), [&code](const Code&c)
					{
						return (c.value==code.value&&c.position==code.position)||
							(c.value==code.value&&c.position!=code.position);
					})!=data4.end();
			})==0);
		};
	auto rule5=[&](const vector<Code>& solution)
		{
		return (std::count_if(solution.begin(), solution.end(), [&](const Code&code)
		{
			return std::find_if(data5.begin(), data5.end(), [&code](const Code&c)
				{return c.value==code.value&&c.position!=code.position;})!=data5.end();
			})==1)
				&&
			(std::count_if(solution.begin(), solution.end(), [&](const Code&code)
			{
				return std::find_if(data5.begin(), data5.end(),
						[&code](const Code&c)
					{return c.value==code.value&&c.position==code.position;}
						)!=data5.end();
			})==0);
		};

for (int val1=1; val1<=9; val1++)
	{
		for (int val2=1; val2<=9; val2++)
		{
			if (val2==val1)
			{
				continue;
			}
			for (int val3=1; val3<=9; val3++)
			{
				if (val3==val1||val3==val2)
				{
					continue;
				}
				Code code1(1, val1), code2(2,val2), code3(3, val3);
				vector<Code>codes={code1,code2,code3};
				bool bResult=
						rule1(codes)
						&& rule2(codes)
						&& rule3(codes)
						&& rule4(codes)
						&& rule5(codes);
				if (bResult)
				{
					cout<<"found"<<endl;
					cout<<string(code1)<<string(code2)<<string(code3)<<endl;
					return;
				}
			}
		}
	}
}

十二月十六日等待变化等待机会

struct People: public enable_shared_from_this<People>
	{
		enum Gender{Male, Female};
		People(int nAge, bool bMan):age(nAge),gender(bMan?Male:Female){id=rand();}
		int age=0;
		Gender gender=Male;
		int id=0;
		operator string()const
		{
			stringstream ss;
			ss<<"id:"<<id<<" age:"<<age<<"  "<<"gender:"<<(gender==Male?"M":"F")<<endl;
			return ss.str();
		}
		struct Comp
		{
			bool operator()(const shared_ptr<People>&left, const shared_ptr<People>&right) const
			{
				return left->id<right->id;
			}
		};
		set<shared_ptr<People>, Comp> circle;
		void meet(shared_ptr<People>&other)
		{
			if (id==other->id)
			{
				return;
			}
			if (gender!=other->gender&&std::abs(age-other->age)<5&&((gender==Female&&other->age>age)||
					(gender==Male&&other->age<age)))
			{
				circle.insert(other->shared_from_this());
				other->circle.insert(shared_from_this());
			}
		}
		string request(People* from)
		{
			stringstream ss;
			ss<<this->operator string();
			for (auto& c:circle)
			{
				if (c.get()!=from)
				{
					ss<<"use_count:"<<c.use_count()<< c->request(this)<<endl;
				}
			}
			return ss.str();
		}
		string serialize()
		{
			stringstream ss;
			ss<<this->operator string();
			for (auto& c:circle)
			{
				ss<<"use_count:"<<c.use_count()<<c->request(this)<<endl;
			}
			return ss.str();
		}
	};
	srand(time(nullptr));
	auto person=make_shared<People>(30, true);
	for(int i=0; i<15; i++)
	{
		auto people=make_shared<People>(rand()%30+20, rand()%2==0);
		cout<<"people:"<<people.get()<<":"<<people->operator string()<<endl;
		person->meet(people);
	}
	cout<<person->serialize()<<endl;

十二月二十日等待变化等待机会

结果如下

十二月二十八日等待变化等待机会

这个不过是小小的验证一下++操作符不是一个atomic的操作，我以前对于这一点的认识不是很清楚认为这个是一个指令，其实牵涉到内存读写都不是，因为寄存器也许是一个指令可是内存load/store是十几甚至几十个指令周期啊。结果如下

counter should be 100000000 and counter=14070258