[usaco] castle

IOI’94 – Day 1
In a stroke of luck almost beyond imagination, Farmer John was sent a ticket to the Irish Sweepstakes (really a lottery) for his birthday. This ticket turned out to have only the winning number for the lottery! Farmer John won a fabulous castle in the Irish countryside.

Bragging rights being what they are in Wisconsin, Farmer John wished to tell his cows all about the castle. He wanted to know how many rooms it has and how big the largest room was. In fact, he wants to take out a single wall to make an even bigger room.

Your task is to help Farmer John know the exact room count and sizes.

The castle floorplan is divided into M (wide) by N (1 <=M,N<=50) square modules. Each such module can have between zero and four walls. Castles always have walls on their “outer edges” to keep out the wind and rain.

Consider this annotated floorplan of a castle:

     1   2   3   4   5   6   7
   #############################
 1 #   |   #   |   #   |   |   #
   #####—#####—#—#####—#  
 2 #   #   |   #   #   #   #   #
   #—#####—#####—#####—#
 3 #   |   |   #   #   #   #   #  
   #—#########—#####—#—#
 4 # ->#   |   |   |   |   #   #  
   #############################

#  = Wall     -,|  = No wall
-> = Points to the wall to remove to
     make the largest possible new room

By way of example, this castle sits on a 7 x 4 base. A “room” includes any set of connected “squares” in the floor plan. This floorplan contains five rooms (whose sizes are 9, 7, 3, 1, and 8 in no particular order).

Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by removing a single wall.

The castle always has at least two rooms and always has a wall that can be removed.

PROGRAM NAME: castle
INPUT FORMAT
The map is stored in the form of numbers, one number for each module, M numbers on each of N lines to describe the floorplan. The input order corresponds to the numbering in the example diagram above.

Each module number tells how many of the four walls exist and is the sum of up to four integers:

1: wall to the west
2: wall to the north
4: wall to the east
8: wall to the south
Inner walls are defined twice; a wall to the south in module 1,1 is also indicated as a wall to the north in module 2,1. Line 1:  Two space-separated integers: M and N
Line 2..:  M x N integers, several per line. 

SAMPLE INPUT (file castle.in)
7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

OUTPUT FORMAT
The output contains several lines: Line 1:  The number of rooms the castle has. 
Line 2:  The size of the largest room
Line 3:  The size of the largest room creatable by removing one wall 
Line 4:  The single wall to remove to make the largest room possible

Choose the optimal wall to remove from the set of optimal walls by choosing the module farthest to the west (and then, if still tied, farthest to the south). If still tied, choose ‘N’ before ‘E’. Name that wall by naming the module that borders it on either the west or south, along with a direction of N or E giving the location of the wall with respect to the module.

SAMPLE OUTPUT (file castle.out)
5
9
16
4 1 E

————————————————————————————————-
本题的关键点
1:如果保存点和边的信息。
 把每个小的格子看成一个点,如果两个格子同属于一个房间的话,表明两个点之间存在一个边。
 由于题目中已经给出了明确的信息:每个格子四周的墙是用二进制数来表示的。因此,只需要M*N个点的信息,
 每个点要储存:点是否被访问过,点所属的连通分量,点四周的墙信息。
2:如何查找room的数量和最大的room的面积。
 利用BFS,遍历所有的节点,把每个节点所属的component进行初始化。
3:寻找可能连接两个房间构成一个最大房间的墙
 遍历每一个墙,找出最大的。
我的代码:
————————————————————————————————–
/*
ID: yunleis2
PROG: castle
LANG: C++
*/

#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
using namespace std;
typedef unsigned int uint;
class vertex
{
public:
 uint wall;
 int component;
 int visited;
 vertex()
 {
  component=-1;
  visited=0;
 }
};
static uint WALL=1;
static uint CROSS=2;
 
int main()
{

 fstream fin(“castle.in”,ios::in);
 int M,N;
 fin>>M>>N;
 vertex * src=new vertex[M*N];
 vector<int > rooms;
 for(int i=0;i<N;i++)
 {
  for(int j=0;j<M;j++)
  {
   fin>>src[i*M+j].wall;
  }
 }
 edge * lr1=new edge[(M-1)*N];
 edge * hl2=new edge [(N-1)*M];
 for(int i=0;i<N;i++)
 {
  for(int j=0;j<(M-1);j++)
  {
   uint wall=src[i*M+j].wall;
   if((wall&4)!=0)
    lr1[i*(M-1)+j].type=WALL;
   else
   { lr1[i*(M-1)+j].type=CROSS;
    lr1[i*(M-1)+j].left=j;
    lr1[i*(M-1)+j].right=j+1;
   }
  }
 }
 
 int g_cmpnt=1;
 int g_large=0;
 for(int i=0;i<(M*N);i++)
 {
   if(src[i].visited==0)
  {
   /************************************************************************/
   /* bfs                                                                     */
   /************************************************************************/
    queue<int> q;
   q.push(i);
   int t_large=0;
   int t_cmpnt=g_cmpnt++;
   src[i].component=t_cmpnt;
   while(!q.empty())
   {
    int tmp=q.front();
    q.pop();
    if(src[tmp].visited==0)
    {
     src[tmp].component=t_cmpnt;
     src[tmp].visited=1;
     t_large++;
     if((src[tmp].wall&1)==0)
     {
      q.push(tmp-1);
     }
     if((src[tmp].wall&2)==0)
     {
      q.push(tmp-M);
     }
     if((src[tmp].wall&4)==0)
     {
      q.push(tmp+1);
     }
     if((src[tmp].wall&8)==0)
     {
      q.push(tmp+M);
     }
    }
   }
   if(t_large>g_large)
    g_large=t_large;
   rooms.push_back(t_large);
  }
 }
 fstream fout(“castle.out”,ios::out);
 fout<<g_cmpnt-1<<endl;
 fout<<g_large<<endl;
 
 //search all the walls;
 int more_large=g_large;
 int r,c;
 char direc;
 for(int i=0;i<M;i++)
 {
  for(int j=N-1;j>0;j–)
  {
   if((src[j*M+i].wall&2)!=0)
   {
    if(src[j*M+i].component!=src[(j-1)*M+i].component)
    {
     int t1;
     if((t1=rooms.at(src[j*M+i].component-1)+rooms.at(src[(j-1)*M+i].component-1))>more_large)
     {
      more_large=t1;
      r=j+1;c=i+1;
      direc=’N’;
     }
    }
   }
  }
  if(i==(M-1))
   continue;
  for(int j=N-1;j>=0;j–)
  {
   if((src[j*M+i].wall&4)!=0)
   {
    if(src[j*M+i].component!=src[(j)*M+i+1].component)
    {
     int t1;
     if((t1=rooms.at(src[j*M+i].component-1)+rooms.at(src[(j)*M+i+1].component-1))>more_large)
     {
      more_large=t1;
      r=j+1;c=i+1;
      direc=’E’;
     }
    }
   }
  }
 }
 fout<<more_large<<endl;
 fout<<r<<” “<<c<<” “<<direc<<endl;

 
 

[usaco] 5.4.4 Betsy’s Tour

 好久没作usaco了。过了个年,人都懒了。

Betsy’s Tour
Don Piele
A square township has been divided up into N2 square plots (1 <= N <= 7). The Farm is located in the upper left plot and the Market is located in the lower left plot. Betsy takes her tour of the township going from Farm to Market by walking through every plot
exactly once. Shown below is one possible tour for Betsy when N=3.

—————-
|    |    |    |
| F**********  |
|    |    | *  |
————*—
|    |    | *  |
|  *****  | *  |
|  * | *  | *  |
—*—*—-*—
|  * | *  | *  |
|  M | ******  |
|    |    |    |
—————-

Write a program that will count how many unique tours Betsy can take in going from Farm to Market for any value of N.
PROGRAM NAME: betsy
INPUT FORMAT
Line 1: A single integer N (1 <= N <= 7)

SAMPLE INPUT (file betsy.in)
3

OUTPUT FORMAT
A single line with a single integer, the number of unique tours.
SAMPLE OUTPUT (file betsy.out)
2

这次的主要是减枝。

当到达一个格子后,下一个格子选择哪里呢?答案是,如果这个格子的旁边如果有个格子,该格子周围只有一个未访问格子时,就选择这个格子。
当然终点除外了。

Executing…
   Test 1: TEST OK [0.000 secs, 3180 KB]
   Test 2: TEST OK [0.000 secs, 3180 KB]
   Test 3: TEST OK [0.000 secs, 3180 KB]
   Test 4: TEST OK [0.000 secs, 3180 KB]
   Test 5: TEST OK [0.000 secs, 3180 KB]
   Test 6: TEST OK [0.011 secs, 3180 KB]
   Test 7: TEST OK [0.346 secs, 3180 KB]

/*
ID:yunleis2
PROG:betsy
LANG:C++
*/

#include<iostream>
#include<fstream>
using namespace std;
#define MAXN 10
#define  DEBUG
int N;
bool visited[MAXN][MAXN];
int nabor[MAXN][MAXN];
int total=0;
void travel(int x,int y,int n);
#define minusOne(nx,ny,one) {if(!visited[nx][ny]){	if((--nabor[nx][ny])==1&&!((nx==N&&ny==1)))		++one; }}
#define forwordOne(nx,ny,nth)    if(!visited[nx][ny]&&nabor[nx][ny]==1){ travel(nx,ny,nth+1);}
#define forword(nx,ny,nth)    if(!visited[nx][ny]){ travel(nx,ny,nth+1);}
#define rollback(nx,ny)   if(!visited[nx][ny]) nabor[nx][ny]++;
void print();
int main(){

	ifstream  fin("betsy.in");
	fin>>N;
	for(int i=1+1;i<N;++i){
		for(int j=1+1;j<N;++j){
			nabor[i][j]=4;
		}
	}
	for(int i=0;i<N+2;++i)
		visited[0][i]=visited[N+1][i]=true;
	for(int i=0;i<N+2;++i)
		visited[i][0]=visited[i][N+1]=true;
	for(int i=1+1;i<N;++i)
		nabor[1][i]=nabor[N][i]=3;
	for(int i=1+1;i<N;++i)
		nabor[i][1]=nabor[i][N]=3;
	nabor[1][1]=nabor[N][N]=nabor[N][1]=nabor[1][N]=2;
#ifdef DEBUG

	print();
	
#endif
	travel(1,1,1);
	ofstream fout("betsy.out");
	fout<<total<<endl;
	//system("pause");
}
void print(){
	for(int i=0;i<N+2;++i){
		for(int j=0;j<N+2;++j){
			cout<<nabor[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
	for(int i=0;i<N+2;++i){
		for(int j=0;j<N+2;++j){
			cout<<visited[i][j]<<" ";
		}
		cout<<endl;
	}
	
}
void travel(int x,int y,int nth){
	if(y==1&&x==(N)){
		if(nth!=N*N)
			return;
		++total;
		return;
	}
	
	visited[x][y]=true;
	int one=0;
	 minusOne(x-1,y,one);
	 minusOne(x,y-1,one);
	 minusOne(x+1,y,one);
	 minusOne(x,y+1,one);
//	cout<<x<<" ,"<<y<<endl;
//	print();
	if(one==1){		
		forwordOne(x-1,y,nth);
		forwordOne(x,y-1,nth);
		forwordOne(x+1,y,nth);
		forwordOne(x,y+1,nth);
	}
	else if(one==0)
	{
		forword(x-1,y,nth);
		forword(x,y-1,nth);
		forword(x+1,y,nth);
		forword(x,y+1,nth);
	}
	rollback(x-1,y);
	rollback(x,y-1);
	rollback(x+1,y);
	rollback(x,y+1);
	visited[x][y]=false;
	//roolback
}

 

[usaco] 回数中的素数Prime Palindromes

题目给出一个下限,一个上限,要求求出之间的所有既是回数又是素数的数。

下边是原文描述:

Prime Palindromes

The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that

finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .

PROGRAM NAME: pprime

INPUT FORMAT

Line 1:

Two integers, a and b

SAMPLE INPUT (file pprime.in)

5 500

OUTPUT FORMAT

The list of palindromic primes in numerical order, one per line.

SAMPLE OUTPUT (file pprime.out)

5
7
11
101
131
151
181
191
313
353
373
383
解题的要点在于:
首先构造回数,然后判断是不是素数。如果你从下限遍历到上限,然后判断是不是回数和素数的话,你会死的很惨。
构造回数也是有技巧的。
在这里有两种方法:
1:
- - - - - - Aw-1 Aw-2.......Ai......A0
↑ ↑                               | |
| |_______________________________↓ |
|___________________________________↓

  另一种方法:

Aw-1 Aw-2.......Ai......A0 - - - - - -
↓ ↓                                ↑ ↑
| |________________________________| |
|____________________________________|
 
如果有这样一个数:
101,的话,第一种方法是无法构造出来的。
所以采用第二种方法。

第二个关键点在于判断素数。

判断素数要从2开始,直到一个上限,但上限也是有窍门的,究竟遍历到什么地方才算节省时间呢?

注意到,如果a*b=n;

那么a<根n<b;或者相反,

因此,只需要遍历到sqrt(n)即可。

第三个要点在于构造回数的起点,如果给出的起点很高的话,从1遍历是很不合算的。

在测试用例中就分为这几种情况

low          high

非常小    非常小

非常小    非常大

非常大    非常大

这是我的解法:

/*
ID: yunleis2
PROG: pprime
LANG: C++
*/

#include<iostream>
#include<fstream>
#include<cmath>
#include<string.h>
#include<vector>
using namespace std;

int longest_size=0;
bool isprime(int n);
void  getNum1(int a,char * tmp,int *r1,int *r2);
void quicksort(int * a,int p,int r);
int main()
{

fstream fin(“pprime.in”,ios::in);

int low,high;

fin>>low>>high;

vector<int> v;

int t=high;

int lowsize=0;

while(t!=0)

{

  longest_size++;
  t/=10;

}
t=low;
while(t!=0)
{
  lowsize++;
  t/=10;
}
char * tmp=new char[longest_size*2];
/************************************************************************/
/* search from num that has (lowsize+1)/2  only search nums not divided by 2                                                                     */
/************************************************************************/
int from=pow((double)10,(lowsize+1)/2-1);
if(from%2==0)
  from++;
int to=pow((double)10,(longest_size+1)/2);
while(from<=to)
{
  int r1=0;

  int r2=0;

  getNum1(from,tmp,&r1,&r2);
  
/*  if(r1<=high&&r1>=low)
   cout<<r1;
  cout<<“\t”;

  if(r2<=high&&r2>=low)
   cout<<r2;
  cout<<endl;

  */
  from++;
 
  /************************************************************************/
  /* next step is to find where the num is prime                          */
  /************************************************************************/
  if(r1<=high&&r1>=low&&isprime(r1))
   v.push_back(r1);
  if(r2<=high&&r2>=low&&isprime(r2))
   v.push_back(r2);
}

int * result=new int[v.size()];
for(int i=0;i<v.size();i++)
{
//  cout<<v.at(i)<<endl;
  result[i]=v.at(i);
}

delete []tmp;
quicksort(result,0,v.size()-1);
fstream fout(“pprime.out”,ios::out);
for(int i=0;i<v.size();i++)
{
  fout<<result[i]<<endl;
}

  // system(“pause”);
}
void  getNum1(int a,char * tmp,int *r1,int *r2)
{
memset(tmp,0,longest_size);
int a1=a;
for(int i=0;a1!=0;i++)
{
  tmp[i]=’0’+a1%10;
  a1/=10;
}
int size=strlen(tmp);

 *r1=a*pow((double)10,size-1);

 *r2=*r1*10;
for(int i=1;i<size;i++)
{
  int tr=((int)pow((double)10,(size-1)-i))*(tmp[i]-‘0’);

  *r1+=tr;

  *r2+=tr;
}

 *r2+=(tmp[0]-‘0’)*pow(10.0,size-1);

}
bool isprime(int n)
{
int i;
for(i=2;i<=sqrt((double)n);i++)
  if(n%i==0) return false;
if(i>sqrt((double)n)) return true;

}
void swap(int * x,int * y)

{

int t=*x;
*x=*y;
*y=t;
}
int partition(int* a,int p,int r)
{
int i=p-1;
int x=a[r];
for(int j=p;j<r;j++)
{
  if(a[j]<=x)
  {
   i++;
   swap(a+j,a+i);
  }
}
swap(a+i+1,a+r);return i+1;
}
void quicksort(int * a,int p,int r)
{
if(p<r)
{

 

  int q=partition(a,p,r);
  quicksort(a,p,q-1);
  quicksort(a,q+1,r);
}
}

这是测试结果:

USER: Ma yunlei [yunleis2]
TASK: pprime
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3032 KB]
   Test 2: TEST OK [0.000 secs, 3032 KB]
   Test 3: TEST OK [0.000 secs, 3032 KB]
   Test 4: TEST OK [0.000 secs, 3032 KB]
   Test 5: TEST OK [0.000 secs, 3032 KB]
   Test 6: TEST OK [0.000 secs, 3032 KB]
   Test 7: TEST OK [0.081 secs, 3032 KB]
   Test 8: TEST OK [0.054 secs, 3032 KB]
   Test 9: TEST OK [0.081 secs, 3032 KB]

All tests OK.

Your program ('pprime') produced all correct answers! This is your

submission #4 for this problem. Congratulations!

Here are the test data inputs:

------- test 1 ----
5 500
------- test 2 ----
750 14000
------- test 3 ----
123456 1123456
------- test 4 ----
97000 1299000
------- test 5 ----
9878210 9978210
------- test 6 ----
9902099 9902100
------- test 7 ----
7 10000000
------- test 8 ----
1333331 9743479
------- test 9 ----
5 100000000

Keep up the good work!

这是uaco的解法:

The main problem here is that we need some way to generate palindromes. Since there are only about 10,000 palindromes less than 100,000,000, we can just test each one to see if it is prime and in the range.

To generate a palindrome, we start with the first half and reverse it. The trick is that we can repeat the middle character or not repeat the middle character. I call a palindrome with a repeated middle character “even” (because it is of even length) and one without “odd”. So from the string “123”, we can generate the even palindrome “123321” or the odd palindrome “12321”.

We can generate all palindromes by doing the following:

  • length 1: generate odd palindromes using 1..9
  • length 2: generate even palindromes using 1..9
  • length 3: generate odd palindromes using 10..99
  • length 4: generate even palindromes using 10..99

The “generate” function does exactly this, using “genoddeven” to first generate the odd palindromes for a range and then the even ones.

The “gen” function generates an even or odd palindrome for a number by converting it to a string, making a palindrome, and converting the resulting string back to a number. Then it tests to see if the number is in the range and prime. If so, it is printed.

We could speed this up in a number of ways: use a faster primality test, don’t generate palindromes past “b”, etc. But this is already plenty fast, and doing such things makes the program more complex and might introduce bugs.

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>

FILE *fout;
long a, b;
int isprime(long n)
{
    long i;

    if(n == 2)
	return 1;
    if(n%2 == 0)
	return 0;
    for(i=3; i*i <= n; i+=2)
	if(n%i == 0)
	    return 0;

    return 1;
}

void
gen(int i, int isodd)
{
    char buf[30];
    char *p, *q;
    long n;

    sprintf(buf, "%d", i);

    p = buf+strlen(buf);
    q = p - isodd;

    while(q > buf)
	*p++ = *--q;
    *p = '\0';

    n = atol(buf);
    if(a <= n && n <= b && isprime(n))
	fprintf(fout, "%ld\n", n);
}

void
genoddeven(int lo, int hi)
{
    int i;
    for(i=lo; i<=hi; i++)
        gen(i, 1);

    for(i=lo; i<=hi; i++)
        gen(i, 0);
}

void
generate(void)
{
    genoddeven(1, 9);
    genoddeven(10, 99);
    genoddeven(100, 999);
    genoddeven(1000, 9999);
}

void
main(void)
{
    FILE *fin;

    fin = fopen("pprime.in", "r");
    fout = fopen("pprime.out", "w");
    assert(fin != NULL && fout != NULL);

    fscanf(fin, "%ld %ld", &a, &b);

    generate();
    exit (0);
}
 

master_zed writes:

 

 

The problem can be simplified slightly by noticing that any even palindrome is divisible by 11. Therefore, 11 is the ONLY even prime palindrome. This eliminates the need to deal with 2 cases:

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>

FILE *fout;
long a, b;

int
isprime(long n)
{
    long i;

    if(n == 2)
        return 1;

    if(n%2 == 0)
        return 0;

    for(i=3; i*i <= n; i+=2)
        if(n%i == 0)
                return 0;

    return 1;
}

void
gen(int i)
{
    char buf[30];
    char *p, *q;
    long n;

    sprintf(buf, "%d", i);

    p = buf+strlen(buf);
    q = p - 1;

    while(q > buf)
            *p++ = *--q;
    *p = '\0';

    n = atol(buf);
    if(a <= n && n <= b && isprime(n))
        fprintf(fout, "%ld\n", n);
}

void
generate(void)
{
    int i;
    for (i = 1; i <= 9; i++)
      gen(i);
    if(a <= 11 && 11 <= b)
      fprintf(fout, "11\n");

    for (i = 10; i <= 9999; i++)
      gen(i);
}

void
main(void)
{
    FILE *fin;
    fin = fopen("pprime.in", "r");
    fout = fopen("pprime.out", "w");
    assert(fin != NULL && fout != NULL);

    fscanf(fin, "%ld %ld", &a, &b);
    generate();
    exit (0);
}

Coach Rob writes:

I guess I have a slightly different coding style than the previous two solutions. This is the same idea but coded a bit more tightly (thanks to Michael Coblenz for its kernel):

 

 

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
int primelist[100000];
int nprimes;

int isPrime(int num);
int reverse2(int i, int j);
int compare(const void *p, const void *q) { return *(int *)p-*(int *)q; }
void main (void) {
    ifstream infile("pprime.in");
    ofstream outfile("pprime.out"); 
    int i, j, begin, end, num;
    infile>>begin>>end;
    if (begin <= 11 && 11 <=end)
        primelist[nprimes++] = 11;
    for (j = 0; j <= 999; j++)
        for (i = 0; i <= 9; i++)  {
	    num = reverse2(j,i);
	    if (num >= begin && num <=end && isPrime(num)) 
  	        primelist[nprimes++] = num;
        }
    qsort(primelist, nprimes, sizeof(int), compare);
    for (i = 0; i < nprimes; i++)
	outfile << primelist[i] << "\n";
}

int
reverse2(int num, int middle) {
    int i, save=num, digit, combino = 1;
    for (i = 0; num; num /= 10) {
	digit = num % 10;
	i = 10 * i + digit;
	combino *= 10;
    }
    return i+10*combino*save+combino*middle;
}
	
int isPrime(int num) {
    int i;
    if (num <= 3) return 1;
    if (num%2 == 0 || num%3 ==0) return 0;
    for (i = 5; i*i <= num; i++)
	if (num %i ==0)
	    return 0;
    return 1;
}

And here is another tightly coded solution from Anton Titov:

 

I guess you may find intresting my solution to Prime Palindromes as I use a function to generate palindromes, that is purely arythmetical it does not use strings, sprintf, reversion or other things. It uses recursion, but my guess is that it will outpreform all other functions listed.

 

Function void genPalind(int num, int add, int mulleft, int mulright)

 

 

expects 4 parameters, first is the number (N) of digits you want for your palindromes, second should be 0 for direct calls, third should be 10^(N-1) for direct calls and last one should be 1 for direct calls.

 

 

#include <stdio.h>
#include <string.h>
 
#include <stdlib.h>
#include <math.h>
FILE *f;
int a, b;

int isPrime(int num);
void genPalind(int num, int add, int mulleft, int mulright);
void tryPalind(int num);
int main(){
  int i;
  char first;
  f=fopen("pprime.in", "r");
  fscanf(f, "%d%d", &a, &b);
  fclose(f);
  f=fopen("pprime.out", "w");
  if (a<=5)
    fprintf(f, "%i\n", 5);
  if (a<=7 && b>=7)
    fprintf(f, "%i\n", 7);
  if (a<=11 && b>=11)
    fprintf(f, "%i\n", 11);
 
  genPalind(3, 0, 100, 1);
  genPalind(5, 0, 10000, 1);
  genPalind(7, 0, 1000000, 1);
  fclose(f);
}

void tryPalind(int num){
  if (!(num&1))
    return;
  if (num<a || num>b)
    return;
  if (!(num%3) || !(num%5) || !(num%7))
    return;
  if (!isPrime(num))
    return;
  fprintf(f, "%d\n", num);
}

void genPalind(int num, int add, int mulleft, int mulright){
  int i, nmulleft, nmulright;
  if (num==2){
    for (i=0; i<10; i++)
      tryPalind(add+mulleft*i+mulright*i);
  }
  else if (num==1){
    for (i=0; i<10; i++)
      tryPalind(add+mulright*i);
  }
  else {
    nmulleft=mulleft/10;
    nmulright=mulright*10;
    num-=2;
    for (i=0; i<10; i++)
      genPalind(num, add+i*mulleft+i*mulright, nmulleft, nmulright);
  }
}

int isPrime(int num){
  int koren, i;
  koren=(int)sqrt(1.0*num);
  for (i=11; i<=koren; i+=2)
    if (!(num%i))
      return 0;
  return 1;
 
}


facebook静态代码检查工具开源了!

以前一直想写个静态代码的检查工具,能够根据语法分析自动找出内存泄露的问题,今天发现facebook开源了这样一个工具,可以检查Java , Object c  和c代码,美中不足的是不支持C++。

facebook的这款工具叫Infer,用于在发布移动应用之前对代码进行分析,找出潜在的问题。目前
Facebook 使用该工具来分析 Facebook 的 App,包括 Android 、iOS、Facebook Messenger 和 Instagram 等等

Facebook 称该工具帮助其每个月检查出数百个应用中潜在的 Bug,例如一些空指针访问、资源和内存泄漏等等。支持 Android 的 Java 和 iOS 的 C 和 Objective-C 代码,它可以在不运行代码(一般开发者的调试方式都是编译、运行,查看结果,然后人工分析代码)的方式下,

1.通过词法分析

2.语法分析

3.控制流

4.数据流分析等技术对程序代码进行扫描,来验证代码是否存在问题或满足技术指标。

简直是神器!



Mac OS X: https://github.com/facebook/infer/releases/download/v0.1.0/infer-osx-v0.1.0.tar.xz

Linux: https://github.com/facebook/infer/releases/download/v0.1.0/infer-linux64-v0.1.0.tar.xz

安装步骤:

1.如果你是在Mac OS X上,运行:tar xf infer-osx-v0.1.0.tar.xz

2.如果你是在Linux上运行:tar xf infer-linux64-v0.1.0.tar.xz

3.创建一个目录如:infer-osx-v0.1.0/ directory (or infer-linux64-v0.1.0/ directory)

4.将infer添加到您的PATH中

5.cd infer-*v0.\1.0 &&echo “export PATH=\”\$PATH:pwd/infer/infer/bin\””
\ >> ~/.bash_profile &&source ~/.bash_profile


你可以找出哪些你是在你的终端运行echo $ SHELL使用shell。根据需要调整上面的命令添加到特定的shell。如果你在Linux上运行bash,您可通过“〜/ .bashrc中”中,如果“〜/ .bash_profile中”不存在上面的命令来替换“〜/ .bash_profile中”。

源地址:http://fbinfer.com/docs/getting-started.html

【usaco】4.4.2最小割集PROB Pollutant Control

 
Pollutant Control
Hal Burch
It’s your first day in Quality Control at Merry Milk Makers, and already there’s been a catastrophe: a shipment of bad milk has been sent out. Unfortunately, you didn’t discover this until the milk was already into your delivery system on its way to stores.
You know which grocer that milk was destined for, but there may be multiple ways for the milk to get to that store.

The delivery system is made up of a several warehouses, with trucks running from warehouse to warehouse moving milk. While the milk will be found quickly, it is important that it does not make it to the grocer, so you must shut down enough trucks to ensure
that it is impossible for the milk to get to the grocer in question. Every route costs a certain amount to shut down. Find the minimum amount that must be spent to ensure the milk does not reach its destination, along with a set of trucks to shut down that
achieves this goal at that cost.

PROGRAM NAME: milk6
INPUT FORMAT
Line 1:  Two space separated integers, N and M. N (2 <= N <= 32) is the number of warehouses that Merry Milk Makers has, and M (0 <= M <= 1000) is the number of trucks routes run. Warehouse 1 is actually the productional facility, while warehouse N is the grocer
to which which the bad milk was destined. 
Line 2..M+1:  Truck routes: three space-separated integers, Si, Ei, and Ci. Si and Ei (1 <= Si,Ei <= N) correspond to the pickup warehouse and dropoff warehouse for the truck route. Ci (0 <= Ci <= 2,000,000) is the cost of shutting down the truck route. 

SAMPLE INPUT (file milk6.in)
4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80

OUTPUT FORMAT
The first line of the output should be two integers, C and T. C is the minimum amount which must be spent in order to ensure the our milk never reaches its destination. T is the minimum number of truck routes that you plan to shut down in order to achive this
goal. The next T lines sould contain a sorted list of the indexes of the truck routes that you suggest shutting down. If there are multiple sets of truck routes that achieve the goal at minimum cost, choose one that shuts down the minimum number of routes.
If there are still multiple sets, choose the one whose initial routes have the smallest index.

SAMPLE OUTPUT (file milk6.out)
60 1
3

 

——————————————————————————–
非常繁琐的一道题。
求最小割,不仅要求割的权值,还有求割包含的所有的边。

大致思路是这样的。
先求最大流,把每条边的权值作相应的变化,
当最大流求出来之后,运用flood进行寻找一个最小割。
主要注意的情况有下列几种:
1:两点之间可能存在重边。
2:如果存在多个割集,取数目最小或者其中边的index最小的情况。

求最大流的问题参见之前的日志

 

/*
ID:yunleis3
PROG:milk6
LANG:C++
*/

#include <fstream>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=33;
const int maxm=1001;
#define DEBUG1 0
int n,m;
class edge
{
public:
	int sec;
	edge * next;
	edge(int s,edge *n):sec(s),next(n){}
	edge(){sec=0;next=NULL;}
};
int  edges[maxm][4];
edge vertex[maxn];
bool visited[maxn];
int minie[maxn];
int preve[maxn];
int critedge[maxn];
int result[maxm];
int result1[maxm];
bool priodelete[maxm];
int minied[maxn];
int rptr=0;
int rptr1=0;
int totalpathvalue=0;
void quicksort(int * a,int p,int r);
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
int main()
{
	ifstream fin("milk6.in");
	fin>>n>>m;
	
	for(int i=1;i<=m;++i){
		int a,b,c;
		fin>>a>>b>>c;
		edges[i][0]=b;
		edges[i][1]=c;
		edges[i][2]=a;
		edges[i][3]=c;
		vertex[a].next=new edge(i,vertex[a].next);
	}
	bool flag=true;
	edges[0][0]=1;
	edges[0][1]=0;
	edges[0][2]=0;
	vertex[0].next=new edge(0,NULL);

	visited[0]=true;
	while(flag){
		for(int i=1;i<=n;++i){
			minie[i]=-1;
			visited[i]=false;
			preve[i]=-1;
		}
	//	minie[1]=1;//wight of the edge to the targe;
	//	preve[1]=0;
	//	int finale=-1;
		edge * etpm=&vertex[1];
		while(etpm->next!=NULL){
			int target=edges[etpm->next->sec][0];
			if(minie[target]==-1||minie[target]<edges[etpm->next->sec][1])
			{
				minie[target]=edges[etpm->next->sec][1];
				preve[target]=etpm->next->sec;
				critedge[target]=etpm->next->sec;
			}
			etpm=etpm->next;
		}
		visited[1]=true;
		while(true){
			//find the mini edge;
			int miniptr=-1;
			for(int i=1;i<=n;++i){
				if(!visited[i]&&minie[i]!=-1&&minie[i]!=0){
					if(miniptr==-1||minie[i]>minie[miniptr])
						miniptr=i;
					else if(minie[i]==minie[miniptr]&&priodelete[critedge[i]])
					{
						miniptr=i;
					}
				}
			}
			if(miniptr==-1)
			{
				flag=false;
				break;
			}
			if(miniptr==n)
			{ 
				break;
			}
			visited[miniptr]=true;
			
			edge * crit=&vertex[miniptr];
			while(crit->next!=NULL){
				int target=edges[crit->next->sec][0];
				if(!visited[target]&&(minie[target]==-1||(minie[target]<=min(minie[miniptr],edges[crit->next->sec][1])))){
					minie[target]=min(minie[miniptr],edges[crit->next->sec][1]);
					preve[target]=crit->next->sec;
					critedge[target]=minie[miniptr]>edges[crit->next->sec][1]?crit->next->sec:miniptr;
				} 
				crit=crit->next;
			}

		}
		if(!flag)
			break;
		int xptr=n;
		int pathvalue=-1;
		int xxptr=-1;
		
		while(xptr!=1){
			int pree=preve[xptr];
			if(pathvalue==-1||pathvalue>edges[pree][1])
			{
				pathvalue=edges[pree][1];
				xxptr=pree;				
			}
			else if(pathvalue==-1||(pathvalue==edges[pree][1]&&priodelete[pree]&&!priodelete[xxptr]))
			{
				//pathvalue=edges[pree][1];
				xxptr=pree;	
			}
			xptr=edges[pree][2];
		}
		xptr=n;
		if(pathvalue==-1||pathvalue==0)
			break; 
		result[rptr++]=xxptr;
		totalpathvalue+=pathvalue;
		while(xptr!=1){
			int pree=preve[xptr];
			edges[pree][1]-=pathvalue;
			priodelete[pree]=true;
			xptr=edges[pree][2];
		}
		
	}
	//flood fill
	queue<int> q;
	q.push(1);
	for(int i=0;i<=n;++i)
		visited[i]=false;
	queue<int> rs;
	while(true){
		while(!q.empty()){
			int xx=q.front();
			q.pop();
			if(visited[xx])
				continue;
			visited[xx]=true;
			edge * etmp=&vertex[xx];
			bool flag=false;
			while(etmp->next!=NULL){
				if(edges[etmp->next->sec][1]>0){
					q.push(edges[etmp->next->sec][0]);
					//flag=true;
				}
				etmp=etmp->next;
			}
			//if(!flag){
				//rs.push(xx);
			//}

		}
#if DEBUG1
		for(int i=1;i<=m;++i){
			if(edges[i][1]==0){
				cout<<i<<" "<< edges[i][2]<<" "<<edges[i][0]<<" "<<edges[i][1]<<" "<<visited[edges[i][2]]<<" "<<visited[edges[i][0]]<<endl;
			}
		}
#endif
		for(int i=1;i<n;++i){
			if(visited[i]){
				edge * etmp=&vertex[i];
				while(etmp->next!=NULL){
					if(!visited[edges[etmp->next->sec][0]]){
						rs.push(i);
						break;
					}
					etmp=etmp->next;
				}
			}
		}
		int tmp[maxm];
		int tmpptr=0;
		bool flag=false;
		while(!rs.empty()){
			int xx=rs.front();
			rs.pop();
			edge * etmp=&vertex[xx];
			
			while(etmp->next!=NULL){
				bool flag1=false;
				for(int i=0;i<tmpptr;++i)
					if(tmp[i]==etmp->next->sec)
						flag1=true;
				if(!flag){					
					q.push(edges[etmp->next->sec][0]);
				}
				if(edges[etmp->next->sec][1]==0){
					tmp[tmpptr++]=etmp->next->sec;
					if(edges[etmp->next->sec][0]==n)
						flag=true;
				}
				etmp=etmp->next;
				
			}
		}
		if(tmpptr==0)
			break;
		if(tmpptr!=0&&(rptr1==0||rptr1>tmpptr)){
			rptr1=0;
			for(int i=0;i<tmpptr;++i)
				result1[rptr1++]=tmp[i];
		}
		else if(rptr1==tmpptr){
			int i=0;
			while(result1[i]==tmp[i])
				++i;
			if(result1[i]>tmp[i])
				while(i<rptr1)
					result1[i++]=tmp[i];
		}
		if(flag)
			break;
	}
/*	for(int i=0;i<rptr;++i){
		int first=edges[result[i]][2], second=edges[result[i]][0];
		if(visited[first]&&!visited[second])
			result1[rptr1++]=result[i];
	}
	*/
	quicksort(result1,0,rptr1-1);
	ofstream fout("milk6.out");
 
	fout<<totalpathvalue<<" "<<rptr1<<endl;
	for(int i=0;i<rptr1;++i){
		fout<<result1[i]<<endl;
	}
	//system("pause");
	for(int i=1;i<=n;++i){
		while(vertex[i].next!=NULL){
			edge * ptr=vertex[i].next;
			vertex[i].next=ptr->next;
			delete ptr;
		} 
	}
}

void swap(int * a,int *b){
	if(a==b)
		return;
	int x=*a;
	*a=*b;
	*b=x;
}
int partition(int *a,int p,int r){
	int x=a[r];
	int i=p-1;
	for(int j=p;j<r;++j){
		if(a[j]<x){
			++i;
			swap(a+i,a+j);
		}
	}
	++i;
	swap(a+r,a+i);
	return i;
}
void quicksort(int * a,int p,int r){
	if(p<r){
		int q=partition(a,p,r);
		quicksort(a,p,q-1);
		quicksort(a,q+1,r);
	}
}

/*
int n,m;
int metri[maxn][maxn];
int trucknum[maxn][maxn];
int result[maxm];
int resultvalue=0;
bool visited[maxn];
int minial[maxn];
int preve[maxn];
int rptr=0;
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
int main()
{
	ifstream fin("milk6.in");
	fin>>n>>m;
	for(int i=0;i<=n;++i){
		for(int j=0;j<=n;++j)
			metri[i][j]=-1;
	}
	for(int i=0;i<m;++i){
		int a,b,c;
		fin>>a>>b>>c;
		metri[a][b]=c;
		trucknum[a][b]=i+1;
	}
	bool flag=true;

	while(flag){

		for(int i=1;i<=n;++i){
			visited[i]=false;
			minial[i]=metri[1][i];
			preve[i]=1;
		}
		visited[1]=true;
		while(true){
			int miniptr=-1;
			for(int i=1;i<=n;++i){
				if(!visited[i]&&minial[i]!=-1){
					if(miniptr==-1)
						miniptr=i;
					else if(minial[i]>minial[miniptr])
						miniptr=i;
				}
			}
			if(miniptr==n)
				break;
			if(miniptr==-1)
			{
				
				flag=false;
				break;
			}
			visited[miniptr]=true;
			 
			for(int i=1;i<=n;++i){
				if(!visited[i]){


					if(minial[i]==-1&&(minial[miniptr]!=1&&metri[miniptr][i]!=1))
					{
						//minial[i]=minial[miniptr]+metri[miniptr][i];
						preve[i]=miniptr;
						minial[i]=min(minial[miniptr],metri[miniptr][i]);
					}
					else if(minial[i]!=-1&&(minial[miniptr]!=1&&metri[miniptr][i]!=1))
					{
						//minial[i]=minial[miniptr]+metri[miniptr][i];
						
						if(min(minial[miniptr],metri[miniptr][i])<minial[i])
						{
							preve[i]=miniptr;
							minial[i]=min(minial[miniptr],metri[miniptr][i]);
						}
					}
				}
			}
		}
		//find the minial value;
		if(!flag)
			break;
		int pathvalue=-1;
		int miniptr1=n;
		int xptr=-1;
		while(miniptr1!=1){
			if(pathvalue==-1||(pathvalue>=metri[preve[miniptr1]][miniptr1]))
			{
				pathvalue=metri[preve[miniptr1]][miniptr1];
				xptr=miniptr1;
			}
			miniptr1=preve[miniptr1];
		}
		if(pathvalue==-1||pathvalue==0)
			break;
		result[rptr++]=trucknum[preve[xptr]][xptr];
		resultvalue+=pathvalue;
		miniptr1=n;
		//assert(pathvalue==-1);
		while(miniptr1!=1){
			 metri[preve[miniptr1]][miniptr1]-=pathvalue;
			 miniptr1=preve[miniptr1];
		}
	}
	ofstream fout("milk6.out");
	cout<<resultvalue<<" "<<rptr<<endl;
	for(int i=0;i<rptr;i++)
		cout<<result[i]<<endl;
	system("pause");
}
*/

 

c++中短路求值的妙用

c++中有这样一个特性,即对于与、或运算,如果能够通过第一个表达式计算出整个表达式的真值,那么就不会再去计算第二个表达式。

比如或运算

a || b,如果a的值是true,那么整个表达式也肯定是true,程序不会去计算第二个表达式。

与运算

a&&b,如果a的值是false,那么整个表达式也肯定是false,程序不会去计算第二个表达式。

于是就出现了一下妙用:

比如,对一个指针接引用,那么必须保证这个指针非空:

传统的做法是

if(ptr)

    ptr->value;

比较简洁的做法:

ptr && ptr->value;

经典的例子:

求n!,要求不能使用任何判断语句,不能使用任何循环语句

 

给你3秒钟哦亲。

 

 

公布答案:

int  func(int n)

{

int t=0;

n && t=func(n-1);

return t*n;

}

 

 

友元类

error:      is private

如果添加了friend之后,还是报错的话。不妨看看是不是名字空间搞错了。

[usaco] 4.1.4 PROB Cryptcowgraphy

Cryptcowgraphy
Brian Dean
The cows of Farmer Brown and Farmer John are planning a coordinated escape from their respective farms and have devised a method of encryption to protect their written communications.

Specifically, if one cow has a message, say, “International Olympiad in Informatics”, it is altered by inserting the letters C, O, and W, in random location in the message, such that C appears before O, which appears before W. Then the cows take the part
of the message between C and O, and the part between O and W, and swap them. Here are two examples:

            International Olympiad in Informatics
                              ->
            CnOIWternational Olympiad in Informatics
           
            International Olympiad in Informatics
                              ->
            International Cin InformaticsOOlympiad W

To make matters more difficult, the cows can apply their encryption scheme several times, by again encrypting the string that results from the previous encryption. One night, Farmer John’s cows receive such a multiply-encrypted message. Write a program to
compute whether or not the non-encrypted original message could have been the string:

            Begin the Escape execution at the Break of Dawn

PROGRAM NAME: cryptcow
INPUT FORMAT
A single line (with both upper and lower case) with no more than 75 characters that represents the encrypted message.

SAMPLE INPUT (file cryptcow.in)
Begin the EscCution at the BreOape execWak of Dawn

OUTPUT FORMAT
Two integers on a single line. The first integer is 1 if the message decodes as an escape message; 0 otherwise. The second integer specifies the number of encryptions that were applied (or 0 if the first integer was 0).

SAMPLE OUTPUT (file cryptcow.out)
1 1

—————————————————-
解法dfs+elfhash。
基本原理就是暴搜,但是要加上减枝。
以下减枝:
1. 由于添加的COW是一起的,因此给出的字符串的字符个数应该等于47(目标字符串的长度)+3*k。如果不满足就可直接判断无解。
2. 除了COW三个字符外,其他的字符的个数应该和目标串相一致。如果不一致也可直接判断无解。
   搜索中间肯定会出现很多相同的情况,因此需要开一个hash来记录搜索到过哪些字符串,每搜索到一个字符串,就判重。
   如果重复直接剪枝。这里的字符串的hash函数可以采用ELFhash,但由于ELFhash的数值太大,
   所以用函数值对一个大质数(我用的是35023)取余,这样可以避免hash开得太大,同时又可以减少冲突。
   实验证明,加上elfhash之后,最复杂的情况用时也只有0.243.
3. 对搜索到的字符串,设不包含COW的最长前缀为n前缀(同样也可以定义n后缀),那么如果n前缀不等于目标串的长度相同的前缀,
   那么当前字符串一定无解,剪枝。N后缀也可采取相同的判断方法。
4. 一个有解的字符串中,COW三个字母最早出现的应该是C,最后出现的应该是W,如果不满足则剪枝。
5 . 当前字符串中任意两个相邻的COW字母中间所夹的字符串一定在目标串中出现过。如果不符合可立即剪枝。
6. 首先枚举o的位置,那么c的位置已经在0和O之间了,w的位置已经在o之后。
7. 在判断当前串的子串是否包含在目标串中的时候,可以先做一个预处理:记录每一个字母曾经出现过的位置,然后可以直接枚举子串的第一个字母的位置。这样比用pos要快2倍左右。
8. 判断某个字符是否在原始串中。给每一个字符计算一个hash值,为其上一个字符左移n位加上当前字符的值。这样就很容易个判断是否含有这个字符串了

——————————————

/*
ID:yunleis2
PROG:cryptcow
LANG:C++
*/

#include<iostream>
#include<fstream>
#include<string.h>
#include<ctime>
using namespace std;
char origin[]="Begin the Escape execution at the Break of Dawn";
int hashvalue[60];
#define  HASHSIZE 871
int hashpos[3][HASHSIZE];
char encode[80];
int cnum,onum,wnum;
long begintime;
#define isencodechar(ch)   (ch=='C'||ch=='O'||ch=='W')
int length;
int orilen;
#define MAXHASH 35023
bool hashsearch[MAXHASH];
inline bool exists(char  enc[],int begin,int end){
	for(int i=begin+1;i<=end;i++){
		
		int hashvalue=enc[i-1]<<5;
		hashvalue+=enc[i];
		hashvalue%=HASHSIZE;
		bool flag=false;
		for(int j=0;j<3;j++){
			int pos=hashpos[j][hashvalue];
			if(pos==-1)
				break;
			if(pos!=-1&&origin[pos]==enc[i])
				flag=true;
		}
		if(!flag)
			return false;
	}
	return true;
}
fstream fin("cryptcow.in",ios::in );
fstream fout("cryptcow.out",ios::out);
void search(char * encode,int depth);
int main()
{
	
	fin.getline(encode,80);
	cout<<encode<<endl;
	//check header;
	cnum=onum=wnum=0;
	for(int i=0;i<3*HASHSIZE;i++){
		hashpos[i/HASHSIZE][i%HASHSIZE]=-1;
	}
	char value[70];
	length=strlen(encode);
	orilen=strlen(origin);
	for(int i=0;i<length;i++){
		if(encode[i]=='C')
			++cnum;
		if(encode[i]=='O')
			++onum;
		if(encode[i]=='W')
			++wnum;
		if(!isencodechar(encode[i])){
			if(encode[i]==' ')
				encode[i]=91;
			encode[i]-=64;
		}
		if(i<orilen){
			if(origin[i]==' ')
				origin[i]=91;
			origin[i]-=64;
			int value=0;
			if(i!=0){
				value=origin[i-1]<<5;
			}
			value+=origin[i];
			hashvalue[i]=value;
			value%=HASHSIZE;
			if(hashpos[0][value]==-1)
				hashpos[0][value]=i;
			else if(hashpos[1][value]==-1)
				hashpos[1][value]=i;
			else  if(hashpos[2][value]==-1)
				hashpos[2][value]=i;
			else
				cout<<"error"<<value<<" "<<i;
		}
	}
	if((length-orilen)%3!=0){
		fout<<0<<" "<<0<<endl;
		return 0;
	}
	int last=-1;
	for(int i=0;i<length;i++){
		 
		if(encode[i]=='C')
		{ 
			last=i;
		}
		if(encode[i]=='O')
		{
			if(!exists(encode,last+1,i-1)){
				fout<<0<<" "<<0<<endl;
				return 0;
			}
			last=i;
		}
		if(encode[i]=='W')
		{
			 
			if(!exists(encode,last+1,i-1)){
				fout<<0<<" "<<0<<endl;
				return 0;
			}
			last=i;
		}
	}

	if(cnum!=onum||cnum!=wnum){
		fout<<0<<" "<<0<<endl;
		return 0;
	}

	bool flag=true;
	for(int i=0;i<length&&i<orilen;i++){
		if(encode[i]=='C')
			break;
		else if(encode[i]!=origin[i])
		{
			fout<<0<<" "<<0<<endl;
			return 0;
		}
	}
	for(int i=0;i<length&&i<orilen;i++){
		if(encode[length-i-1]=='W')
			break;
		else if(encode[length-i-1]!=origin[orilen-i-1]){
			fout<<0<<" "<<0<<endl;
			return 0;
		}
	}

#if 0
	for(int i=0;i<length;i++){
		cout<<(int)encode[i]<<" ";
	}
	cout<<endl;
	for(int i=0;i<orilen;i++){
		cout<<(int)origin[i]<<" ";
	}
	cout<<endl;
	for(int i=0;i<orilen;i++){
		cout<<hashvalue[i]<<" ";
	}
#endif
	 begintime=clock();
	search(encode,cnum);
	
	fout<<0<<" "<<0<<endl;
	//system("pause");
}
unsigned long
	elf_hash( char *name)
{
	unsigned long       h = 0, g;

	while (*name) {
		h = (h << 4) + *name++;
		if (g = h & 0xf0000000)
			h ^= g >> 24;
		h &= ~g;
	}
	return h;
}
void search(char * encode,int depth){
 
	//cout<<<<endl;
	long hash =elf_hash(encode)%MAXHASH;
	if(hashsearch[hash])
	{
		cout<<encode<<endl;
		return;
	}
	hashsearch[hash]=true;
	char tmp[3];
	char *decode=new char[strlen(encode)+1];
	if(depth==0){
#if 0
		for(int i=0;i<strlen(encode);i++){
			if(encode[i]<65)
				cout<<(char)(encode[i]+64);
			else
				cout<<encode[i];
		}
		cout<<endl;
#endif
		if(exists(encode,0,strlen(encode)-1))
		{
			fout<<1<<" "<<cnum<<endl;
			long end=clock();
			cout<<end-begintime<<endl;
			//system("pause");
			exit(0);
		}
	}
	if((strlen(encode)-orilen)%3!=0){
		return ;
	}
	int cpos=-1,opos=-1,wpos=-1;
	for(int j=0;j<strlen(encode);j++){
		if(encode[j]=='O'){
			opos=j;
			for(int i=0;i<opos;i++){
				if(encode[i]=='C'){
					cpos=i;
					bool flag=true;
					if(cpos>opos)
						continue;
					if(cpos>0&&!isencodechar(encode[cpos-1])&&!(isencodechar(encode[opos+1]))){
						tmp[0]=encode[cpos-1];
						tmp[1]=encode[opos+1];
						tmp[2]=0;
						flag=exists(tmp,0,1);
						if(!flag)
							continue;
					}
					for(int s=strlen(encode)-1;s>opos;s--){
						if(encode[s]=='W'){
							wpos=s;
							if((cpos<opos&&opos<wpos)){
								bool flag=true;
								 
								if(cpos>0&&!isencodechar(encode[wpos-1])&&!(isencodechar(encode[cpos+1]))){
									tmp[0]=encode[wpos-1];
									tmp[1]=encode[cpos+1];
									tmp[2]=0;
									flag=exists(tmp,0,1);
									if(!flag)
										continue;
								}
								if(cpos>0&&!isencodechar(encode[opos-1])&&!(isencodechar(encode[wpos+1]))){
									tmp[0]=encode[opos-1];
									tmp[1]=encode[wpos+1];
									tmp[2]=0;
									flag=exists(tmp,0,1);
									if(!flag)
										continue;
								}
								int ptr=0;
								//cout<<cpos<<" "<<opos<<" "<<wpos<<"\t";
								for(int f=0;f<cpos;f++){
									decode[ptr++]=encode[f];
								}
								for(int f=opos+1;f<wpos;f++)
									decode[ptr++]=encode[f];
								for(int f=cpos+1;f<opos;f++)
									decode[ptr++]=encode[f];
								for(int f=wpos+1;f<strlen(encode);f++)
									decode[ptr++]=encode[f];
								decode[ptr]=0;
								search(decode,depth-1);
							}
						}


					}
				}
			}
		}
	}
	delete []decode;
} 

    Test 1: TEST OK [0.000 secs, 3076 KB]
   Test 2: TEST OK [0.000 secs, 3076 KB]
   Test 3: TEST OK [0.000 secs, 3076 KB]
   Test 4: TEST OK [0.000 secs, 3076 KB]
   Test 5: TEST OK [0.000 secs, 3076 KB]
   Test 6: TEST OK [0.081 secs, 3076 KB]
   Test 7: TEST OK [0.000 secs, 3076 KB]
   Test 8: TEST OK [0.054 secs, 3076 KB]
   Test 9: TEST OK [0.243 secs, 3076 KB]
   Test 10: TEST OK [0.243 secs, 3076 KB]

[usaco]5.3.4强联通分支,双联通分支 Network of Schools

 
Network of Schools
IOI ’96 Day 1 Problem 3
A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school
A, then A does not necessarily appear in the list of school B.

You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure
that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be
made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.

PROGRAM NAME: schlnet
INPUT FORMAT
The first line of the input file contains an integer N: the number of schools in the network (2<=N<=100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers
of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.

SAMPLE INPUT (file schlnet.in)
5
2 4 3 0
4 5 0
0
0
1 0

OUTPUT FORMAT
Your program should write two lines to the output file. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.

SAMPLE OUTPUT (file schlnet.out)
1
2

 

——————————————————————————–
算法:强联通分支,双联通分支
首先使用强联通分子算法,把同一个分支变成一个点,然后把有向图当成无向图,求得双联通分支。
求出每一个联通分量的入度为0的点和出度为0的点。
task A很好求,只需要把所有的入度为0的点加起来就是了;如果某个联通分量没有入度为0 的点,那么就加1.
task B要求把这些联通分量连接成一个连通图,最简单的办法是把这些联通分量连成环。
 假第i个联通分量出度为0的点有out个,第i+1个联通分量入度为0的点有in个,那么最少需要max(out,in)个遍才能把他们连接起来。
 由于要求最少的遍,那么当out和in最接近的时候,能节省很多边,
 考虑这个例子(in,out):(1,2),(1,1),(2,1);如果这样按顺序连接起来的话,需要2+1+2+1条边,但如果2和3颠倒一下顺序,则需要1+2+1+1条边
 因此,每次选取还未匹配的分量 出度最大的一个分量和入度最大的另一个分量,连接起来。
这题好麻烦,很多需要注意的问题。

这题是用java写的,运行速度比c++慢多了

Executing…
   Test 1: TEST OK [0.090 secs, 254972 KB]
   Test 2: TEST OK [0.090 secs, 254972 KB]
   Test 3: TEST OK [0.108 secs, 254972 KB]
   Test 4: TEST OK [0.126 secs, 254972 KB]
   Test 5: TEST OK [0.126 secs, 254972 KB]
   Test 6: TEST OK [0.126 secs, 255384 KB]
   Test 7: TEST OK [0.144 secs, 255248 KB]
   Test 8: TEST OK [0.162 secs, 255420 KB]
   Test 9: TEST OK [0.270 secs, 255792 KB]
   Test 10: TEST OK [0.144 secs, 255556 KB]
   Test 11: TEST OK [0.162 secs, 255240 KB]    

]———————————————————————————–

 

/*
 ID:yunleis3
 PROG:schlnet
 LANG:JAVA
 */
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
 
public class schlnet {
	private static final ArrayList<Integer> outdgree0 = null;
	static ArrayList<Integer>[] list;
	static ArrayList<Integer>[] reverse_list;
	static int current_cpnt=0;
	static int []dfs_nmbr;
	static int []cpnt_nmbr;
	static int []dfs_high;
	static int dfs_n;
	static LinkedList<Integer> dfs_stack=new LinkedList<Integer>();
	public static void main(String [] arg) throws IOException{
		File file=new File("schlnet.in");
		long begin=System.currentTimeMillis();
		Scanner scan=new Scanner(file);
		FileWriter w=new FileWriter(new File("schlnet.out"));
		int total =scan.nextInt();
		list=new ArrayList [total+1];
		reverse_list=new ArrayList [total+1];
		int out=0;
		int in=0;
		int[] indegree=new int [total+1];
		for(int i=1;i<total+1;i++){reverse_list[i]=new ArrayList<Integer>();}
		for(int i=1;i<total+1;i++){
			list[i]=new ArrayList<Integer>();
			while(true){
				int t=scan.nextInt();
				if(t==0) break;
				list[i].add(t);
				//indegree[t]++;
				reverse_list[t].add(i);
			}
			if(list[i].size()==0) out++;
		}
		dfs_nmbr=new int[total+1];
		cpnt_nmbr=new int[total+1];
		dfs_high=new int[total+1];
		dfs_n=total+1;
		for(int i=1;i<=total;++i){
			if(dfs_nmbr[i]==0)
				scc(i);
		}
		ArrayList<Integer>[] list1=new ArrayList[current_cpnt+1];
		ArrayList<Integer>[] reverse_list1=new ArrayList[current_cpnt+1];
		for(int i=1;i<current_cpnt+1;++i){
			list1[i]=new ArrayList<Integer>();
			reverse_list1[i]=new ArrayList<Integer>();
		}
		for(int i=1;i<=total;i++){
			int first=cpnt_nmbr[i];
			for(int j=0;j<list[i].size();++j){
				int next=cpnt_nmbr[list[i].get(j)];
				if(next==first)
					continue;
				boolean flag=false;
				for(int s=0;s<list1[first].size();++s){
					if(list1[first].get(s)==next)
					{
						flag=true;
						break;
					}
				}
				if(!flag)
				{
					list1[first].add(next);
					reverse_list1[next].add(first);
					indegree[next]++;
				}
			}
		}
		list=list1;
		reverse_list=reverse_list1;
		
		total=current_cpnt;
		
		
		for(int i=1;i<=total;i++){
			if(indegree[i]==0) in++;
		}
		
		
		
		boolean[] visited=new boolean[total+1];
		int [] componentnum=new int[total+1];
		for(int i=0;i<total+1;++i)
		{
			visited[i]=false;
			componentnum[i]=-1;
			componentnum[i]=-1;
		}
		LinkedList<Integer> stack=new LinkedList<Integer>();
		int cpnt_g=0;
		ArrayList<Integer> indgrees0=new ArrayList<Integer>();
		ArrayList<Integer> outdgrees0=new ArrayList<Integer>();
		while(true){
			boolean find0indgree=false;
			int root=0;
			boolean finished=true;
			ArrayList<Integer> nums=new ArrayList<Integer>();
			for(int i=1;i<total+1;++i){
				if(!visited[i]&&indegree[i]==0){
					root=i;
					find0indgree=true;
				}
				if(!visited[i])
					finished=false;
			}
			if(finished)
				break;
			if(!find0indgree){
				for(int i=1;i<total+1;++i)
					if(!visited[i])
						root=i;
			}
			stack.addFirst(root);
			visited[root]=true;
			int cmpnt_l=cpnt_g++;
			nums.add(root);
			componentnum[root]=cmpnt_l;
			while(!stack.isEmpty()){
				int r=stack.removeFirst();				
				for(int i=0,size=list[r].size();i<size;++i){
					int next=list[r].get(i);
					if(!visited[next])
					{
						visited[next]=true;
						stack.addFirst(next);
						componentnum[next]=cmpnt_l;
						nums.add(next);
					}
				}
				for(int i=0,size=reverse_list[r].size();i<size;++i){
					int next=reverse_list[r].get(i);
					if(!visited[next])
					{
						visited[next]=true;
						stack.addFirst(next);
						componentnum[next]=cmpnt_l;
						nums.add(next);
					}
				}
			}
			int ins0=0,outs0=0;
			for(int i=0;i<nums.size();++i){
				if(indegree[nums.get(i)]==0)
					++ins0;
				if(list[nums.get(i)].size()==0)
					++outs0;
			}
			indgrees0.add(ins0);
			outdgrees0.add(outs0);
			
		}
		int taska=0,taskb=0;
		if(total==1){
			taska=1;
			taskb=0;
		}
		else if(cpnt_g==1&&indgrees0.get(0)==0&&outdgrees0.get(0)==0){
			taska=1;
			taskb=0;
		}else if(cpnt_g==1){
			taska=indgrees0.get(0);
			if(taska==0)
				taska=1;
			taskb=indgrees0.get(0)>outdgrees0.get(0)?indgrees0.get(0):outdgrees0.get(0);
		}
		else{
			in=0;out=0;
			boolean[] outvisited=new boolean[cpnt_g];
			boolean[] invisited=new boolean[cpnt_g];
			for(int i=0;i<cpnt_g;++i){
				//pick the max out;
				int ptr=-1;
				for(int j=0;j<cpnt_g;++j){
					if(!outvisited[j]&&(ptr==-1||outdgrees0.get(ptr)>outdgrees0.get(ptr)))
						ptr=j;
				}
				int ptrin=-1;
				for(int j=0;j<cpnt_g;++j){
					if(!invisited[j]&&(ptrin==-1||indgrees0.get(ptrin)>indgrees0.get(ptrin)))
						ptrin=j;
				}
				outvisited[ptr]=true;
				invisited[ptrin]=true;
				in=indgrees0.get(ptrin);
				out=outdgrees0.get(ptr);
				if(in==0)
					in=1;
				if(out==0)
					out=1;
				taska+=in;
				taskb+=max(out,in);
			}
//			for(int i=0;i<cpnt_g;++i){
//				int next=(i+1)%cpnt_g;
//				out=outdgrees0.get(i);
//				if(out==0)
//					out=1;
//				in=indgrees0.get(next);
//				if(in==0)
//					in=1;
//				taska+=in;
//				taskb+=max(out,in);
//			}
			
		}
		
		
		FileWriter wr=new FileWriter(new File("schlnet.out"));
		wr.write(taska+"\n"+taskb+"\n");
		wr.flush();
		wr.close();
		System.out.print(taska+"\n"+taskb+"\n");
	}
	static void scc(int v){
		dfs_nmbr[v]=dfs_n--;
		dfs_stack.addFirst(v);
		dfs_high[v]=dfs_nmbr[v];
		for(int i=0;i<list[v].size();++i){
			int w=list[v].get(i);
			if(dfs_nmbr[w]==0){
				scc(w);
				dfs_high[v]=dfs_high[v]>dfs_high[w]?dfs_high[v]:dfs_high[w];				
			}
			else
				if(dfs_nmbr[w]>dfs_nmbr[v]&&cpnt_nmbr[w]==0)
					dfs_high[v]=max(dfs_high[v],dfs_nmbr[w]);
		}
		if(dfs_high[v]==dfs_nmbr[v]){
			++current_cpnt;
			while(!dfs_stack.isEmpty()){
				int x=dfs_stack.removeFirst();
				cpnt_nmbr[x]=current_cpnt;
				if(x==v){
					break;
				}
			}
		}
	}
	static int max(int x,int y){
		return x>y?x:y;
	}
}

 

如何修复Kindle频繁自动锁屏和解锁

12年入手kindle dxg,用了几年,看pdf的利器,感觉很不错,

2016年夏天的时候,kindle突然出现频繁的锁屏和解锁。在网上搜了一下,只有在贴吧找到一个类似的问题,但是没有解决方案,联系amazon的客服,客服也没办法解决。

没办法,只要自己捣鼓。刚开始的时候,从网上看到一些信息说kindle的皮套感应会受到磁铁的影响自动锁屏,于是把kindle拆开了看,把边上的一些线全都拔掉了,甚至把扬声器,音量键都把掉,这些外设本来也没什么作用。

这样搞了之后,还是不行,感觉很郁闷,kindle硬件都是好的,就这样吃灰了。

直到有一天,突然想到,我是不是可以越狱,然后把这个锁屏的功能给关掉,就不会频繁的锁屏和解锁了。网上搜索了一下,还真有相关的命令,就是在搜索框输入~ds

这个命令,在kindle的其他版本上可以,但是在dxg上不行。再深入搜索,找到这一条命令

lipc-set-prop -i com.lab126.powerd preventScreenSaver 1

(来源于https://bookfere.com/post/477.html )

这个文章中还提到kindle 系统是基于linux开发的,这让突然意识到,linux不就是我的老本行么,我直接登陆到kindle机器上看看是什么原因不就可以了么?

说干就干,以前我还折腾过把kindle作为电脑显示器,见这个博客 :
http://blog.csdn.net/sjtuyunlei/article/details/7671608
 。我知道如何越狱,以及如何通过usb作为网卡连接到kindle。

略过越狱和安装usbnetwork的过程。

登录到linux上后,找/var/log/messages这个文件,这是一个系统日志文件,一般系统发生什么事情,都会记录在这里。

在这个文件里,经常看到一些日志:

powerd[1875]: I lipc:evts:name=userShutdown, origin=com.lab126.powerd:Event sent   

powerd[1875]: I def:pbpress:time=209057.737:Power button pressed     

微笑这些日志表明,电源键被频繁的按下,每次按下,都会锁屏或者解锁,有时候还会出现长按的现象,于是就触发kindle关机,症状就是无响应的白屏。

我估计是电源键因为某些原因,导致短路,不停的触发系统事件,让kindle认为用户按下了电源键。

kindle的电源管理是powerd这个进程,经过搜索,找到了powerd的配置文件: 

/etc/powerd.conf

在这个配置文件里,有这两个选项:

## If fake suspend is defined, powerd does not suspend but it itself
## thinks device is suspended
fake_suspend: 0

## If you don't want your device to automatically suspend
## set the following to 1
no_suspend: 0

第一个是假装挂起系统,但实际上不挂起。

第二个是不自动挂起系统,

把这两个选项的0,改成1,重启系统。kindle再也不无脑的频繁锁屏了!吐舌头