勿躁

　　汝有田舍翁，家资殷盛，而累世不识“之”“乎”。一岁，聘楚士训其子，楚士始训之搦管临朱，书一画，训曰“一”字；书二画，训曰“二”字；书三画，训曰“三”字。其子辄欣欣然，掷笔归告其父曰：“儿得矣，儿得矣；可无烦先生矣，重费馆谷也，请谢去。”其父喜，从之，具币谢遣楚士。
　　逾时，其父拟征召姻友万氏姓者饮，令子晨起治状，久之不成，父趣之。其子恚曰：“天下姓字伙矣，奈何姓万，自晨至今，才完五百画也。”
  初机士偶一解，而即以訑訑自矜有得。殆类是已。

《应谐录》刘元卿

知识共享许可协议
于衡的鱼缸(个人博客)中的相关文章
转载请注明出处

构造有序的单链表与逆置操作

构造有序（升序）的单链表

并实现单链表的逆置

（可以采用结构化的程序设计方法实现，即不必定义类）

输入输入链表中的数据。（用0表示输入的结束，0不能添加到链表中）输出按顺序输出有序链表中的数据样例输入

4 1 6 8 2 0

样例输出

1 2 4 6 8
8 6 4 2 1

继续阅读构造有序的单链表与逆置操作

【循环链表】约瑟夫问题

描述约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。输入8 1 3 (n=8 k=1 m=3 )输出7 (剩下的那个)

样例输入

8 1 3

样例输出

7

 

#include <cstdio>
#include <iostream>
using namespace std; 
struct Node
{
  int data;
  Node *next;
};
int main() 
{
  int n, k, m;
  cin >> n >> k >> m;//n个人，第k出列，第m开始。
  if (m == 1)
  {
    int left = k - 1;
    if (left == 0)
      left = n;
    cout << left;
    return 0;
  }
  Node *first = new Node();
  first->data = 1;
  Node *p=first, *q;
  for (int i = 2; i <= n; i++)
  {
    q = new Node();
    q->data = i;
    p->next = q;
    p = p->next;
  }
  p->next = first;
  p = first;
  for (int i = 1; i <= k - 1; i++)
  {
    p = p->next;
  }

  while (p!=p->next)
  {
    for (int i = 1; i < m - 1; i++)
    {
      p = p->next;
    }
    q = p->next;
    p->next = q->next;
    delete q;
    p = p->next;
  }
  cout << p->data << endl;
  return 0;
}

 

Making the Grade DP

Description

A straight dirt road connects two fields on FJ‘s farm, but it changes elevation more than FJ would like. His cows do not mind climbing up or down a single slope, but they are not fond of an alternating succession of hills and valleys. FJ would like to add and remove dirt from the road so that it becomes one monotonic slope (either sloping up or down).

You are given N integers A1, … , AN (1 ≤ N ≤ 2,000) describing the elevation (0 ≤ Ai ≤ 1,000,000,000) at each of N equally-spaced positions along the road, starting at the first field and ending at the other. FJ would like to adjust these elevations to a new sequence B1, . … , BN that is either nonincreasing or nondecreasing. Since it costs the same amount of money to add or remove dirt at any position along the road, the total cost of modifying the road is

|A1 – B1| + |A2 – B2| + … + |AN – BN |

Please compute the minimum cost of grading his road so it becomes a continuous slope. FJ happily informs you that signed 32-bit integers can certainly be used to compute the answer.

继续阅读Making the Grade DP

【数据结构】动态单链表

#include <iostream>
#include <string>
#include <cstring>
#include <queue>
using namespace std; 
template<class T>
struct Node
{
  T data;
  Node<T> *next_pos;
};

template<class T>
class LinkedList
{
public:
  LinkedList();
  LinkedList(T arr[], int n);
  ~LinkedList() {};
  T Get(int i);
  int Locate(T x);
  void Insert(T x,int i);
  T Delete(int i);
  void PrintList();
  int length();
private:
  Node<T> *first,*p,*s;
};

template<class T>
LinkedList<T>::LinkedList()
{
  first = new Node <T>;
  first->next_pos = NULL;
}

template<class T>
LinkedList<T>::LinkedList(T arr[], int n) 
{
  first = new Node<T>;
  first->next_pos = NULL;
  for (int i = 0; i < n; i++)
  {
    p = new Node<T>;
    p->data = arr[i];
    p->next_pos = first->next_pos;
    first->next_pos = p;
  }
/*尾插法
        first = new Node<T>;
	first->next_pos = NULL;
	p = first;
	for (int i = 1; i <= n; i++)
	{
		s = new Node<T>;
		s->data = arr[i];
		s->next_pos = NULL;
		p->next_pos = s;
		p = p->next_pos;
	}*/
}

template<class T>
T LinkedList<T>::Get(int n)
{
  p = first->next_pos;
  for (int i = 0; i < n - 1 && p != NULL; i++)
  {
    p = p->next_pos;
  }
  return p == NULL ? -1 : p->data;
}

template<class T>
int LinkedList<T>::Locate(T x)
{
  p = first->next_pos;
  int count = 1;
  while (p!=NULL)
  {
    if (p->data == x)
    {
      return count;
    }
  }
  return p == NULL ? -1 : p->data;
}

template<class T>
void LinkedList<T>::Insert(T x,int i)
{
  p = first->next_pos;
  int count = 1;
  while (p!=NULL && count <= i-1)
  {
    p = p->next_pos;
    count++;
  }
  if (p == NULL) throw "error";
  else {
    s = new Node<T>;
    s->data = x;
    s->next_pos = p->next_pos;
    p->next_pos = s;
  }
}

template<class T>
T LinkedList<T>::Delete(int i)
{
  p = first->next_pos;
  int count = 0;
  while (p != NULL && count < i - 1)
  {
    p = p->next_pos;
    count++;
  }
  if (p == NULL||p->next_pos == NULL) throw "error";
  else {
    s = p->next_pos;
    p->next_pos = p->next_pos->next_pos;
    T ans=s->data;
    delete s;
    return ans;
  }

}

template<class T>
void LinkedList<T>::PrintList()
{
  p=first->next_pos;
  while (p != NULL)
  {
    cout << p->data << " ";
    p = p->next_pos;
  }
  cout << endl;
}


template<class T>
int LinkedList<T>::length()
{
  p = first->next_pos;
  long long int count = 0;
  while (p != NULL) 
  { 
    p = p->next_pos; count++; 
  }
  return count;
}
int main()
{
  int a[9999];
  for (int i = 0; i < 100; i++)
    a[i] = i;
  LinkedList<int> ab(a, 10);
  ab.PrintList();
  ab.Insert(100, 2);
  ab.PrintList();
  cout << ab.length() << endl;
  cout << ab.Get(2) << endl;
  ab.Delete(2);
  ab.PrintList();
  cout << ab.length() << endl;
  cout << ab.Get(2) << endl;
  ab.PrintList();
}

 

村上春树选摘

1、哪里会有人喜欢孤独，不过是不喜欢失望罢了。
——《挪威的森林》

2、鱼说，你看不到我眼中的泪，因为我在水中。水说，我能感觉到你的泪，因为你在我心中。
——《鱼和水的爱恋》

3、白昼之光，岂知夜色之深。
——《且听风吟》

4、孤独一人也没关系，只要能发自内心地爱着一个人，人生就会有救。哪怕不能和他生活在一起。
——《1Q84》

5、我一直以为人是慢慢变老的，其实不是，人是一瞬间变老的。
——《舞！舞！舞！》

继续阅读村上春树选摘

【二分图最大匹配】Machine Schedule

 

As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem.

There are two machines A and B. Machine A has n kinds of working modes, which is called mode_0, mode_1, …, mode_n-1, likewise machine B has m kinds of working modes, mode_0, mode_1, … , mode_m-1. At the beginning they are both work at mode_0.

For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode_3 or in machine B at mode_4, job 1 can either be processed in machine A at mode_2 or in machine B at mode_4, and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y), which means it can be processed either in machine A at mode_x, or in machine B at mode_y.

Obviously, to accomplish all the jobs, we need to change the machine’s working mode from time to time, but unfortunately, the machine’s working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.

InputThe input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n, m (n, m < 100) and k (k < 1000). The following k lines give the constrains of the k jobs, each line is a triple: i, x, y.

The input will be terminated by a line containing a single zero.
OutputThe output should be one integer per line, which means the minimal times of restarting machine.
Sample Input

5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0

Sample Output

3

继续阅读【二分图最大匹配】Machine Schedule