rotate：
for(int i = 0; i<n; ++i)
for(int j=0; j<n; ++j)
a[j][n-i-1] = b[i][j];
reflect：
for(int i = 0; i<n; ++i)
for(int j =0; j<n; ++j)
a[i][n-j-1] = b[i][j];
/**//*
ID: lorelei3
PROG: transform
LANG: C++
*/
#include <fstream>
#include <iostream>
using namespace std;
const int MAX = 15;
typedef struct Board
{
int m_nSize;
char m_cBoard[MAX][MAX];
} Board, *pBoard;
Board rotate(Board b) {
Board nb = b;
for(int i=0; i<b.m_nSize; ++i)
for(int j=0; j<b.m_nSize; ++j)
nb.m_cBoard[j][b.m_nSize-1-i]=b.m_cBoard[i][j];
return nb;
}
Board reflect(Board b){
Board nb = b;
for(int i=0; i <b.m_nSize; ++i)
for(int j=0; j<b.m_nSize; ++j)
nb.m_cBoard[i][b.m_nSize-1-j] = b.m_cBoard[i][j];
return nb;
}
int eqBoard(Board a, Board b){
int size = 0;
if(a.m_nSize!=b.m_nSize)
return 0;
size = a.m_nSize;
for(int i=0; i<size; ++i)
for(int j=0; j<size; ++j)
if(a.m_cBoard[i][j]!=b.m_cBoard[i][j])
return 0;
return 1;
}
int main(){
int i,j,n;
int ans=0;
Board a,b;
ifstream in("transform.in");
ofstream out("transform.out");
in>>n;
a.m_nSize = n;
b.m_nSize = n;
for(i=0; i<n; ++i)
for(j=0; j<n; ++j)
in>>a.m_cBoard[i][j];
for(i=0; i<n; ++i)
for(j=0; j<n; ++j)
in>>b.m_cBoard[i][j];
if(eqBoard(b, rotate(a)))
ans = 1;
else if(eqBoard(b, rotate(rotate(a))))
ans = 2;
else if(eqBoard(b, rotate(rotate(rotate(a)))))
ans = 3;
else if(eqBoard(b, reflect(a)))
ans = 4;
else if(eqBoard(b, rotate(reflect(a)))
|| eqBoard(b, rotate(rotate(reflect(a))))
|| eqBoard(b, rotate(rotate(rotate(reflect(a))))))
ans = 5;
else if(eqBoard(b,a))
ans = 6;
else
ans = 7;
out<<ans<<endl;
return 0;
}posted @
2010-11-09 00:44 小阮 阅读(156) |
评论 (0) |
编辑 收藏
1. 应尽可能使用标准库，而不是其他的库和“手工打造的代码”；
2. 避免过于复杂的表达式；
3. 如果对运算符的优先级有疑问， 加括号；
4. 避免显示类型转换（强制）；
5. 若必须做显示类型转换，提倡使用特殊强制运算符，而不是C风格的强制；
6. 只对定义良好的构造使用T(e)记法；
7. 避免goto；
8. 避免do语句；
9. 在你已经有了去初始化某个变量的值之前，不要去声明他；
10. 避免带有无定义求值顺序的表达式；
11. 使注释简洁、清晰、有意义；
12. 保持一致的缩进风格；
13. 倾向于定义一个成果函数operator new() 取代全局的operator new()；
14. 在读输入的时候，总应考虑病态形势的输入。
posted @
2010-11-09 00:35 小阮 阅读(136) |
评论 (0) |
编辑 收藏
先对时间段排序.
设ans1 为最长至少有一人在挤奶的时间段（nBegin, nEnd ）， ans2为最长的无人挤奶的时间段。
遍历排序后的各个时间段（t[i]）：
如果 t[i].m_nBegin <= nEnd && t[i].m_nEnd >= nEnd) 更新 nEnd = t[i].m_nEnd；
否则 更新ans1, ans2, nBegin, nEnd, 看代码。
/**//*
ID: lorelei3
PROG: milk2
LANG: C++
*/
#include <fstream>
#include <algorithm>
using namespace std;
const int N = 5005;
int n;
typedef struct TimeNode{
int m_nBegin, m_nEnd;
bool operator < (const TimeNode& node)const{
return m_nBegin<node.m_nBegin || m_nBegin==node.m_nBegin && m_nEnd<node.m_nEnd;
}
}TimeNode, *pTimeNode;
TimeNode t[N];
int inline max(int a, int b){
return a>b?a:b;
}
int main(){
int i;
ifstream in("milk2.in");
ofstream out("milk2.out");
in>>n;
for(i=0;i<n;++i){
in>>t[i].m_nBegin>>t[i].m_nEnd;
}
sort(t, t+n);
bool f = false;
int nBegin=t[0].m_nBegin, nEnd=t[0].m_nEnd;
int ans1=nEnd-nBegin, ans2=0;
for(i=1;i<n;++i){
if(t[i].m_nBegin<=nEnd && t[i].m_nEnd>=nEnd){
nEnd = t[i].m_nEnd;
}else if(t[i].m_nBegin>nEnd){
ans1 = max(nEnd-nBegin, ans1);
ans2 = max(t[i].m_nBegin-nEnd, ans2);
nBegin = t[i].m_nBegin;
nEnd = t[i].m_nEnd;
}
}
out<<ans1<<" "<<ans2<<endl;
return 0;
}
posted @
2010-11-07 00:29 小阮 阅读(406) |
评论 (0) |
编辑 收藏
动态规划。 设bl, br, rl, rr 分别为项链 i 处向左、向右收集到蓝色、红色珠子数。项链是环形的，只要把两个同样的项链放在一起，则转换成线性。
bl[0] = rl[0] = 0
if necklace[i] = 'r' rl[i]=rl[i-1]+1, bl[i]=0;
if necklace[i] = 'b' bl[i]=bl[i-1]+1, rl[i] = 0;
if necklace[i] = 'w' rl[i] = rl[i-1]+1, bl[i]=bl[i-1]+1
result = max( max(bl[i], rl[i] ) + max(br[i+1], rr[i+1]) ) (0<= i <= 2*n -1)
/**//*
ID: lorelei3
PROG: beads
LANG: C++
*/
#include <fstream>
#include <string>
#include <iostream>
using namespace std;
int main(){
string s;
int max=0,len;
ifstream in("beads.in");
ofstream out("beads.out");
in>>len>>s;
s+=s;
len+=len;
for(int i=0; i<len-1; ++i){
int leftIndex=i, rightIndex=i+1;
char leftColor=s[leftIndex], rightColor=s[rightIndex];
while((leftIndex-1)>=0){
leftIndex--;
if(s[leftIndex]=='w')
continue;
else{
if(leftColor=='w'){
leftColor=s[leftIndex];
continue;
}else if(leftColor==s[leftIndex]){
continue;
}else{
leftIndex++;
break;
}
}
}
while((rightIndex+1)<len){
rightIndex++;
if(s[rightIndex]=='w')
continue;
else{
if(rightColor=='w'){
rightColor=s[rightIndex];
continue;
}else if(rightColor==s[rightIndex]){
continue;
}else{
rightIndex--;
break;
}
}
}
max = max>(rightIndex-leftIndex)? max : (rightIndex-leftIndex);
}
if(max+1>len/2)
out<<len/2<<endl;
else
out<<max+1<<endl;
return 0;
}
posted @
2010-11-04 21:30 小阮 阅读(539) |
评论 (0) |
编辑 收藏
1. 避免非平凡的指针运算；
2. 当心，不要超过数组的界限去写；
3. 尽量使用0而不是NULL；
4. 尽量使用vector和valarray而不是内部（C风格）的数组；
5. 尽量使用string 而不是以0结尾的char数组；
6. 尽量少用普通的引用参数；
7. 避免void* ，除了在某些低级代码里；
8. 避免在代码中使用非平凡的文字量。相反，应该定义和使用各种符号常量。
posted @
2010-11-04 21:22 小阮 阅读(215) |
评论 (0) |
编辑 收藏
题意：计算1900年1月1日至1900+N-1年12月31日中十三号落在周一到周日的次数
分析：
1. 用数组保存每个月的天数，外循环判断是否是闰年，若是闰年，二月天数为29。
2. 因为19001月13日是周六，用变量l 记录13日是周几，初始化为6，内循环 逐个加上每个月的天数，并通过模7得到是周几。
闰年的判断：
bool inline IsLeap(int year){
if((year%100!=0 && year%4==0)||year%400==0)
return true;
else
return false;
}
/**//*
ID: lorelei3
PROG: friday
LANG: C++
*/
#include <fstream>
using namespace std;
int day[7];
int mon[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
bool inline IsLeap(int year){
if((year%100!=0 && year%4==0)||year%400==0)
return true;
else
return false;
}
int main(){
int n,i,j,l=6;
ifstream in("friday.in");
ofstream out("friday.out");
in>>n;
n+=1900;
for(i=1900; i<n; ++i){
if(IsLeap(i))
mon[1]=29;
for(j=0; j<12; ++j){
day[l]++;
l+=mon[j];
l%=7;
}
mon[1]=28;
}
out<<day[6];
for(i=0;i<6;++i)
out<<" "<<day[i];
out<<endl;
return 0;
}
PS: 蔡勒公式
posted @
2010-11-02 22:17 小阮 阅读(234) |
评论 (0) |
编辑 收藏
题意：每个人都准备一些钱平均分给其他人，不能分的部分留给自己，计算每个人的得失。
分析：使用两个数组，一个计算得，一个计算失，result[i] = receive[i] - give[i]
PS: 用Map更简单些。
/**//*
ID: lorelei3
PROG: gift1
LANG:C++
*/
#include <fstream>
#include <string>
using namespace std;
const int NP = 15;
string names[NP];
int recieved[NP];
int gived[NP];
int np;
inline int find(string s){
for(int i=0; i<np; ++i)
if(s == names[i])
return i;
return -1;
}
int main(){
//init
int i;
ifstream in("gift1.in");
ofstream out("gift1.out");
in>>np;
for(i=0; i<np; i++)
in>>names[i];
//solve
for(i=0; i<np; i++){
string name;
int sum ,n;
in>>name>>sum>>n;
if(n==0)
continue;
int give = sum/n, stay = sum%n;
int loc = find(name);
recieved[loc] += stay;
gived[loc] += sum;
for(int j=0; j<n; ++j){
in>>name;
recieved[find(name)] += give;
}
}
//output
for(i=0; i<np; ++i)
out<<names[i]<<" "<<recieved[i] - gived[i]<<endl;
return 0;
}
posted @
2010-11-02 22:09 小阮 阅读(201) |
评论 (0) |
编辑 收藏
1. 保持较小的作用域。
2. 不要在一个作用域和它外围的作用域里采用同样的名字。、
3. 在一个声明中（只）声明一个名字。
4. 让常用的和局部的名字比较短， 让不常用的和全局名字比较长。
5. 避免看起来类似的名字。
6. 维持某种统一的命名风格。
7. 仔细选择名字， 反映其意义而不是反映实现方式。
8. 如果所用的内部类型表示某种可能变化的值， 请用typedef 为它定一个有意义的名字。
9. 用typedef 为类型定义同义词， 用枚举或类去定义新类型。
10. 切记每个声明中都必须描述一个类型（没有“隐事的int ”）。
11. 避免有关字符数值的不必要假设。
12. 避免有关整数大小的不必要假设。
13. 避免有关浮点类型表示范围的不必要假设。
14. 优先使用普通的int 而不是short int 或者long int。
15. 优先使用double 而不是float 或者long double。
16. 优先使用普通的char 而不是signed char 或者 unsigned char。
17. 避免做出有关对象大小的不必要假设。
18. 避免无符号算术。
19. 应该带着疑问去看待从signed 到unsigned，或者从unsigned到signed的转换。
20. 应该带着疑问去看待从浮点到整数的转换。
21. 应该带着疑问去看待向较小类型的转换，如将int 转换到char。
posted @
2010-11-02 22:02 小阮 阅读(255) |
评论 (0) |
编辑 收藏 题意：计算两个字符串对应的编码mod 47 之后是否相等。其中"A"=1，"Z"＝26
分析：对于每个字符ch，值ch-'A'+1。为了防止溢出，可利用，(a*b) mod n = (( a mod n ) *b ) mod n
如此类推。
/**//*
ID: lorelei3
LANG: C++
TASK: ride
*/
#include <fstream>
#include <string>
using namespace std;
inline long calc(char ch){
return ch-'A'+1;
}
inline long calc(string s){
long res = 1;
int len = s.length();
for(int i=0; i<len; ++i){
res *= calc(s[i]);
res %= 47;
}
return res;
}
int main(){
ifstream fin("ride.in");
ofstream fout("ride.out");
string s1,s2;
fin>>s1>>s2;
if(calc(s1)==calc(s2))
fout<<"GO"<<endl;
else
fout<<"STAY"<<endl;
return 0;
}
posted @
2010-11-02 21:51 小阮 阅读(221) |
评论 (0) |
编辑 收藏
摘要: // for pairsinline bool leq(int a1, int a2, int b1, int b2){ return (a1<b1 || a1==b1 &&am...
阅读全文
posted @
2010-11-02 21:47 小阮 阅读(173) |
评论 (0) |
编辑 收藏