学步园

PROB Milking Cows [ANALYSIS] 对于区间的问题的求法

//最长连续区间。
/* 考虑：	区间两端点相等的情况。
 * 		区间如何排序
 * 		每次区间要求的值改变的情况都去吃max
 *		每次都要考虑区间最初和最后
 */
struct cmp{
	bool operator () (PII a,PII b) {
		if(a.first == b.first) return a.second > b.second;
		// 递增
		return a.first > b.first;
	}
};
int n;
priority_queue<PII,vector<PII>,cmp> Q;

int main() {
	//FOPEN
	FOPENTI
	FOPENTO
	int a,b,sum=0,maxx = 0,maxf = 0;
	SCF(n);
	F(i,n) {
		SCFD(a,b);
		Q.push(make_pair(a,b));
	}
	PII tmp;
	int f,t;
	tmp = Q.top();Q.pop();
	f = tmp.first;t = tmp.second;
	sum += t-f;
	maxx = max(maxx,sum);
	while(!Q.empty()) {

		tmp = Q.top();Q.pop();
		//DB(tmp.first<<" "<<tmp.second);
		if(t >= tmp.first) {
			if(t >= tmp.second) {
				continue;
			} else {
				sum += tmp.second - t;
				maxx = max(maxx,sum);
				t = tmp.second;
			}
		} else {
			maxx = max(maxx,sum);
			maxf = max(maxf,tmp.first - t);
			f = tmp.first;t = tmp.second;
			sum = t-f;
			maxx = max(maxx,sum);
		}

	}
	printf("%d %d\n",maxx,maxf);
}

PROB Transformations [ANALYSIS]---对于这个题目确实挺无语的，题目要求的很多东西，比如步骤必须按照#1-7顺心来。（程序不能有return语句，不然就强制退出了，不知道为什么。）

考察矩阵基本变换。

//    矩阵的基本操作：
/*     旋转
*     镜像
*/

//pre -> change;
void way_1(int n,char matC[][MAXN],char matP[][MAXN])
{
	//顺时针 90°
	F(i,n) F(j,n) {
		matC[j][n-i-1] = matP[i][j];
	}
}
//镜像
void way_4(int n,char matC[][MAXN],char matP[][MAXN])
{
	F(i,n) F(j,n) {
		matC[i][n - j -1] = matP[i][j];
	}
}

答案确实够简洁的！

 

PROB Name That Number [ANALYSIS] ---- hash_map + dfs枚举排列过掉的，WA了一次因为none没有+上，没认真对题目！

There are two ways to do this problem. One is, given the number, to generate all possible strings that encode to that number and look them up in the dictionary. Since there are 3 letters for each number and 12 digits in the string, that's 3¹² = 531441 lookups into a dictionary of size 5000, which although manageable would be a little on the long side (binary search can help this).

有两种方法做这个题目。一个是，给一个数，找出所以可能的字符串，然后去dictionary找是否存在。因为每个有3个字符总共12位，那么字符串共有3¹² = 531441 种，字典的大小是5000，虽然比较好实现，但是时间会有的长（二分搜索可以帮助你）。（我用的hash_map 最长的一组时间140MS，还算可以。）（两个答案都提交了一下，发现全是0.000s，- - ！ 很强大 mark！

Technorati 标签: mark强大

）

Or, we can examine each word in the dictionary to see if it maps to the digits of the number in question. This has the the advantage of a shorter program that probably will work right first time.

或者，我们也能对每个单词在dictionary查找他是否被映射成询问中的某个数的一位。这个快速程序的优势或许会让他跑第一！（这里翻译的不好。）

struct str_hash {
	size_t operator () (const string & str) const {
		unsigned long __h =0;
		for(size_t i =0;i<str.size();i++)
			__h =5 * __h + str[i];
		return size_t(__h);
	}
};

hash_map<string,int,str_hash> hsi;
map<string,int> mpsi;
char hsh[10][3]={
	{'\0','\0','\0'},
	{'\0','\0','\0'},
	{'A','B','C'},
	{'D','E','F'},
	{'G','H','I'},
	{'J','K','L'},
	{'M','N','O'},
	{'P','R','S'},
	{'T','U','V'},
	{'W','X','Y'}};
char ss[MAXNT],sst[MAXNT];
int len,flag=0;
void dfs(int x)
{
	if(x == len) {
		sst[x]='\0';
		if(hsi.find(sst) != hsi.end()) {
			flag=1;
			puts(sst);
		}
		return;
	}
	for(int i = 0;i<3;i++){
		sst[x] = hsh[ss[x]-'0'][i];
		dfs(x + 1);
	}
}


int main() {

	FOPENTI
	FOPENTO
	FILE *fin  = fopen ("dict.txt", "r");
/* 	     2: A,B,C     5: J,K,L    8: T,U,V
 *           3: D,E,F     6: M,N,O    9: W,X,Y
 *           4: G,H,I     7: P,R,S
 */

	while(~fscanf(fin," %s",ss)) {
		hsi[ss] = 1;
	}
	//DB(hsi.size())
	while(~SCFS(ss)){
		flag =0;
		len = strlen(ss);
		dfs(0);
		if(!flag) puts("NONE");
	}
}

 

PROB Palindromic Squares [ANALYSIS]   -----  进制转换 + 判断palindromic

这次终于和analysis差不多了

char ss[MAXN];
int kk=0;
void fun(int n,int r)
{
        if(n) {
                fun(n/r,r);
                ss[kk++] = (n%r>9? n%r-10+'A':n%r+'0');
        }
}

bool is_palind(char ss[])
{
	int len = strlen(ss);
	int i = 0,j = len-1;
	bool flag = 1;
	while(i < j) if(ss[i++] != ss[j--]) flag = 0;

	return flag;
}

int main()
{
	FOPENTI
	FOPENTO
	int b;SCF(b);
	for(int i = 1;i<=300;i++) {
		fun(i * i,b);
		ss[kk] = '\0';kk=0;
		if(is_palind(ss)) {
			fun(i,b);ss[kk] = '\0';
			printf("%s ",ss);kk=0;
			fun(i*i,b);ss[kk] = '\0';
			puts(ss);kk=0;
		}
	}
}

 

PROB Dual Palindromes [ANALYSIS]  ---- 进制转换 +判断＋　流程控制。。。可以打表的，给忘了。

char ss[MAXN];
int kk=0;
void fun(int n,int r)
{
        if(n) {
                fun(n/r,r);
                ss[kk++] = (n%r>9? n%r-10+'A':n%r+'0');
        }
}

void transi_(int n,int b)
{
	memset(ss,'\0',sizeof(ss));
	kk=0;
	fun(n,b);
}

bool is_palind(char ss[])
{
	int len = strlen(ss);
	int i = 0,j = len-1;
	bool flag = 1;
	while(i < j) if(ss[i++] != ss[j--]) flag = 0;

	return flag;
}

int main()
{
	FOPENTI
	FOPENTO
	int s,n,k=0,flag;
	while(~SCFD(s,n)){
		k=0;
		n++;
		while(k != s) {
			//DB(n)
			flag = 0;
			FOR(i,2,10) {
				transi_(n,i);
				if(is_palind(ss)){
					flag++;
				}
				if(flag == 2) break;
			}
			if(flag == 2) {
				PCFLN(n);
				k++;
			}
			n++;
		}
	}
}

１.２　小结：

• 认真读题，不然ｔｒｉｃｋ发现不了。
• 反向思考啊，第三个题目就是个例子。
• 不要忘记打表。
• 认真思考题目在考察什么，总结自己的方法。

希望一段时间后通关的日子。