|
|
2011年10月22日
所谓表达式求值就是用计算机计算加减乘除式子，说的装逼一点，就是计算中缀表达式的值。 5 + ((1 + 2) * 4) − 3
我们把这个式子添上括号，保持计算顺序不变。 ( 5+((1+2)*4))-3)
运算符夹在数字中间，“中缀”之名由此得来。 人脑可以很快判断计算先后顺序，其实这个过程不是那么显然。因为*/+-有优先级，括号的加入又会打破这个规则。我们可以找出一个式子中最后进行的一步运算，对它的两边分别计算，在根据运算符进行合并。 (5+((1+2)*4))-3)
下面挂的代码是递归实现的。不要骂我标题党，不久会更新真正的栈实现代码，这需要时间，时间~再说递归才符合思维习惯，也更便于记忆~！//表达式求值（递归实现）
/*Author:naeioi
Prog:C++
Time:11.10.22
*/
#include <cstdio>
#include <cstring>
using namespace std;
const int maxl=100;
char s[maxl];
#define isnum(a) (a>='0'&&a<='9')
#define isop(a) (a=='+'||a=='-'||a=='*'||a=='/')
int match(int i)
{
int count=1;
while(count!=0){
i++;
if(s[i]=='(') ++count;
if(s[i]==')') --count;
}
return i;
}
int ston(int p)//下标从p开始
{
int ans=0,positive=1;//符号
if(s[p]=='-'){++p; positive=-1;}
while(isnum(s[p])){
ans*=10;
ans+=s[p++]-'0';
}
return ans*positive;;
}
int div(int l,int r)//求l~r（下标）表示的式子的值
{
while(s[l]=='('&&match(l)==r){++l; --r;}//去除多余括号。不能写成s[l]=='('&&s[r]=')'，形如(1+2)*(3+4)的式子会错误
if(l>r) return 0;
int pos,prior=3;//优先级，2==*/,1==+-
for(int i=l;i<=r;i++){//找优先级最小的运算符
if(s[i]=='(')
if((i=match(i)+1)>r)
break;
if(s[i]=='*'||s[i]=='/')
{ if(prior>=2){pos=i; prior=2;}}
else if(s[i]=='+'||s[i]=='-')
if(prior>=1&&i!=l&&!isop(s[i-1])){pos=i; prior=1;}//-接在运算符后时看成符号。否则看成减号
}
if(prior==3)//是一个数
return ston(l);
int a=div(l,pos-1),b=div(pos+1,r),ans;
switch(s[pos])
{
case '+':
ans=a+b;
break;
case '-':
ans=a-b;
break;
case '*':
ans=a*b;
break;
case '/':
ans=a/b;
break;
}
return ans;
}
int main()
{
freopen("eval.in","r",stdin);
freopen("eval.out","w",stdout);
scanf("%s",s);
printf("%d",div(0,strlen(s)-1));
fclose(stdin);
fclose(stdout);
return 0;
}
2011年10月21日
下个月NOIP复试。初三一年奋战中考直升考，OI基本停滞。暑假宅在家里沉静于异世界也没怎么打代码，只帮人调了几个简单的程序，手生疏得很。于是打算用剩下一个月时间复习基本代码，建立一个标准代码库，让自己重新熟悉那些最最经典的算法实现，同时也为日后编码提供方便。
这个标准代码库我都会亲自编码调试，努力保证正确性，力求简洁易读，注释完整。BUG在所难免，希望大家能在回复中帮助我改进XD.日后会不断更新各个方面（主要是涉及NOI）的基本代码。下面是预计的代码目录。
——————————————————————————————————————————————
1.基本数据结构
高精
二分
哈希（也算查找）
并查集
队列、栈
表达式计算
2.排序、查找
堆
快排
归并排序
选排、插排、冒排（冒牌………）
基数排序
3.图论
宽度、深度优先遍历
Dijkstra、Floyd
Prim、Kruskal
SPFA
最大流&最小最小费用最大流
4.其他
（未完待补充）
——————————————————————————————————————————————————
高精度模板（无压位）
//高精无压位
/*Author:naeioi
Prog:C++
Time:11-10-20
*/
#include <cstdio>
#include <string.h>
//#include <conio.h>
using namespace std;
const int maxlen=105+1;
#ifndef max
#define max(a,b) ((a)>(b)?a:b)
#endif
/*结构说明
1.len代表实际长度
2.s[]从1开始 逆序存储
3.默认长度105
*/
/*注意事项
1.一定要将clear()函数放在赋值函数头，将数据清零
2. 赋值运算符优先级低，跟比较运算符在一起注意打括号
3.基本函数定义形式
Bign operator *(const Bign &b)const{}
注意返回Bign以及那两个const防改写
4. 函数都应写在struct里面
*/
struct Bign{//函数后打//的是二级函数
int len,s[maxlen];
//函数部分
//初始化
void clear(){len=1;memset(s,0,sizeof(s));}//必要，赋值前必须清空
Bign(){clear();}
//赋值
Bign operator = (const char *a){
clear();//只需在此clear()，其他所有赋值函数都要调用它
len=strlen(a);
for(int i=1;i<=len;i++)
s[i]=a[len-i]-'0';
return *this;
}
Bign operator = (int num){//用sprintf巧妙转化，减少代码量
char tmp[maxlen];
sprintf(tmp,"%d",num);
return *this=tmp;
}
Bign(int num){*this=num;}//
Bign(const char *a){*this=a;}//
//运算符
//c++备注：形参const表示不改变形参，末尾const表示不改变*this.运算返回bign供操作
Bign operator + (const Bign &b)const{
Bign c=*this;
c.len=max(len,b.len);
for(int i=1;i<=c.len;i++)
if((c.s[i]+=b.s[i]) >= 10){//!!!赋值运算符比比较运算符优先度低!!!
c.s[i+1]+=c.s[i]/10;
c.s[i]%=10;
}
if(c.s[c.len+1]>0) c.len++;
return c;
}
Bign operator += (const Bign &b){
return (*this=*this+b);
}//
Bign operator + (int b)const{
Bign t=b;
return t+*this;
}//
Bign operator - (const Bign &b)const{//须保证b比*this小
Bign c=*this;
for(int i=1;i<=len;i++)
if((c.s[i]-=b.s[i]) < 0){
c.s[i+1]--;
c.s[i]+=10;
}
while(c.s[c.len]==0) c.len--;
return c;
}
Bign operator - (int b)const{
Bign t=b;
return *this-t;
}//
Bign operator * (const Bign &b)const{
Bign c;
c.len=len+b.len;
for(int i=1;i<=len;i++)
for(int j=1;j<=b.len;j++)
if((c.s[i+j-1]+=s[i] * b.s[j]) >= 10){
c.s[i+j]+=c.s[i+j-1]/10;
c.s[i+j-1]%=10;
}
if(c.s[c.len]==0) c.len--;
return c;
}
Bign operator *= (const Bign &b){
return (*this=*this*b);
}//
Bign operator / (int b)const{//必须整除（TODO:另用函数实现取余)
Bign t=*this,c;
c.len=len;
for(int i=len;i>=1;i--){
t.s[i-1]+=(t.s[i]%b)*10;
c.s[i]=t.s[i]/b;
}
while(c.s[c.len]==0) c.len--;
//remain=t.s[0];
return c;
}
int operator % (int b)const{
Bign t=*this,c;
c.len=len;
for(int i=len;i>=2;i--){
t.s[i-1]+=(t.s[i]%b)*10;
t.s[i-1]%=b;//优化防溢出
}
return t.s[1]%b;
}
//大小比较
bool operator > (const Bign &b)const{
if(len>b.len)
return 1;
else if(len<b.len)
return 0;
else{
for(int i=len;i>=1;i--)
if(s[i]>b.s[i])
return 1;
return 0;
}
}
bool operator > (int b)const{
Bign t=b;
return *this>t;
}//
//输出并换行
void print(){
for(int i=len;i>=1;i--)
printf("%d",s[i]);
printf("\n");
}
};//OK
2010年11月12日
原题在这里.小心指针!!!#include <cstdio>
#include <string.h>
using namespace std;
const int maxn=15,maxl=300;
char key[2][maxn][maxl],str[maxl];
int l[maxn],N;
bool match(char *s,char *k)
{
while (*k)
{
if (*s!=*k)
return false;
++s;
++k;
}
return true;
}
void replace(int cur,int i)
{
char tmp[maxl]= {0};
memcpy(tmp,str,cur);
strcat(tmp,key[1][i]);
strcat(tmp,str+cur+l[i]);
memcpy(str,tmp,sizeof(str));
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("10115.in","r",stdin);
freopen("10115.out","w",stdout);
#endif
while (scanf("%d",&N)&&N!=0)
{
memset(str,0,sizeof(str));
getchar();
for (int i=0; i<N; i++)
{
gets(key[0][i]);
gets(key[1][i]);
l[i]=strlen(key[0][i]);
}
gets(str);
for (int i=0; i<N; i++)
for (int j=0; str[j+l[i]-1]; j++)
if (match(str+j,key[0][i]))
{
replace(j,i);
j=0;
}
puts(str);
}
fclose(stdin);
fclose(stdout);
return 0;
}
这道题交了4遍才AC,也不懂是什么原因 #include <cstdio>
#include <string.h>
using namespace std;
const int maxn=20;
char a[maxn][maxn],tmp[maxn];
int tot=-1,count=0;
int main()
{
#ifndef ONLINE_JUDGE
freopen("644.in","r",stdin);
freopen("644.out","w",stdout);
#endif
while (scanf("%s",a[++tot])==1)
{
if (a[tot][0]!='9')continue;
bool is=true;
--tot;
for (int i=0; i<=tot&&is; i++)
for (int j=0; j<=tot&&is; j++)
if (i!=j&&strlen(a[j])>=strlen(a[i]))
{
sprintf(tmp,"%.*s",strlen(a[i]),a[j]);
if (strcmp(tmp,a[i])==0)
is=false;
}
printf("Set %d is ",++count);
if (is)
printf("immediately decodable\n");
else printf("not immediately decodable\n");
tot=-1;
}
fclose(stdin);
fclose(stdout);
return 0;
}
原题在这里。代码写的比较乱
#include <cstdio>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
using namespace std;
const int maxn=5005,maxl=205;
int tot=0;
char word[maxn][maxl],now[maxl];
bool find(void)
{
for (int i=0; i<tot; i++)
if (!strcmp(now,word[i]))
return true;
return false;
}
int cmp(const void *a,const void *b)
{
return strcmp((char*)a,(char*)b);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("10815.in","r",stdin);
freopen("10815.out","w",stdout);
#endif
for (;;)
{
do
{
*now=getchar();
}
while (!isalpha(*now)&&*now!=EOF);
now[1]=0;
if (scanf("%[qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM]",now+1)==EOF)
break;
for (int i=0; now[i]; i++)
now[i]=tolower(now[i]);
if (!find())
memcpy(word[tot++],now,sizeof(now));
}
qsort(word,tot,sizeof(word[0]),cmp);
for (int i=0; i<tot; i++)
printf("%s\n",word[i]);
fclose(stdin);
fclose(stdout);
return 0;
}
2010年11月11日
原题在这里。字符串匹配，写起来稍稍有些繁琐
1 #include <cstdio>
2 #include <string.h>
3 #include <ctype.h>
4 #include <vector>
5 using namespace std;
6
7 const int maxk=100,maxl=100;
8 char key[maxk][maxl],str[maxl],str2[maxl],ans[maxk][maxl];
9 int K,E,n=0,Max,l;
10
11 bool find(int x,int y)
12 {
13 for(int i=0;i<K;i++){
14 int j;
15 for(j=0;x+j<=y&&key[i][j];j++)
16 if(str[x+j]!=key[i][j])
17 break;
18 if(x+j>y&&!key[i][j])
19 return true;
20 }
21 return false;
22 }
23
24 int main()
25 {
26 #ifndef ONLINE_JUDGE
27 freopen("409.in","r",stdin);
28 freopen("409.out","w",stdout);
29 #endif
30
31 while(scanf("%d%d",&K,&E)==2){
32 l=Max=0;
33 printf("Excuse Set #%d\\n",++n);
34 getchar();
35
36 for(int i=0;i<K;i++)
37 gets(key[i]);
38 for(int i=0;i<E;i++){
39 scanf("%[^\\r\\n]",str);
40 memcpy(str2,str,sizeof(str));
41 getchar();
42 int a=0,b,count=0;
43 while(str[a]){
44 while(!isalpha(str[a])&&str[a])++a;
45 b=a;
46 while(isalpha(str[b])){str[b]=tolower(str[b]);++b;}
47 if(find(a,b-1))count++;
48 a=b;
49 }
50 if(count>Max){
51 Max=count;
52 memset(ans,0,sizeof(ans));
53 l=1;
54 memcpy(ans[l-1],str2,sizeof(str));
55 }
56 else if(count==Max)
57 memcpy(ans[l++],str2,sizeof(str));
58 }
59 for(int i=0;i<l;i++)
60 printf("%s\\n",ans[i]);
61 printf("\\n");
62 }
63
64 fclose(stdin);
65 fclose(stdout);
66 return 0;
67 }
68
|
2010年11月10日
没什么好说的，锻炼编程能力，注意善用scanf :) 1 #include <cstdio>
2 using namespace std;
3
4 int N;
5 double a[260];
6
7 int main()
8 {
9 #ifndef ONLINE_JUDGE
10 freopen("537.in","r",stdin);
11 freopen("537.out","w",stdout);
12 #endif
13
14 scanf("%d",&N);
15 getchar();
16
17 for(int i=1;i<=N;i++){
18 a['U']=a['I']=a['P']=0.0;
19 for(int j=0;j<=1;j++){
20 char last=getchar(),now;
21 while((now=getchar())!='=')last=now;
22 scanf("%lf%c",&a[last],&now);
23 switch(now){
24 case 'm':
25 a[last]/=1000.0;
26 break;
27 case 'k':
28 a[last]*=1000.0;
29 break;
30 case 'M':
31 a[last]*=1000000.0;
32 break;
33 }
34 }
35
36 printf("Problem #%d\\n",i);
37
38 if(a['U']&&a['I'])
39 printf("P=%.2lfW",a['U']*a['I']);
40 else if(a['U']&&a['P'])
41 printf("I=%.2lfA",a['P']/a['U']);
42 else if(a['I']&&a['P'])
43 printf("U=%.2lfV",a['P']/a['I']);
44 printf("\\n\\n");
45 }
46
47 fclose(stdin);
48 fclose(stdout);
49 return 0;
50 }
51
2010年11月7日
在一个n*m的字符矩阵中寻找给定的字符串，字符串可以是上下、下上、左右、右左等8个方向。输出每个字符串第一个字符首次出现的位置。要注意的是换行问题，对一个少一个都判作WA 1 #include <cstdio>
2 #include <string.h>
3 #include <ctype.h>
4 using namespace std;
5
6 const int maxn=60,dx[]= {1,1,1,0,-1,-1,-1,0},dy[]= {-1,0,1,1,1,0,-1,-1};
7 char G[maxn][maxn];
8 int N,M,K;
9
10 int main()
11 {
12 #ifndef ONLINE_JUDGE
13 freopen("10010.in","r",stdin);
14 freopen("10010.out","w",stdout);
15 #endif
16
17 int C,t=0;
18 scanf("%d",&C);
19
20 while(C--) {
21 if(t!=0)printf("\\n");
22 ++t;
23
24 scanf("%d%d",&N,&M);
25 for(int i=1; i<=N; i++)
26 for(int j=1; j<=M; j++) {
27 char tmp;
28 do {
29 tmp=getchar();
30 }
31 while(!isalpha(tmp));
32 G[i][j]=tolower(tmp);
33 }
34
35 scanf("%d",&K);
36 getchar();
37 while(K--) {
38 char str[maxn];
39 gets(str);
40 int len=strlen(str);
41
42 for(int i=0; i<len; i++)
43 str[i]=tolower(str[i]);
44
45 bool ok=false;
46 for(int i=1; i<=N&&!ok; i++)
47 for(int j=1; j<=M&&!ok; j++)
48 for(int k=0; k<8&&!ok; k++) {
49 int x=i,y=j,count=0;
50 while(x>=1&&y>=1&&x<=N&&y<=M&&count<len&&str[count]==G[x][y]) {
51 ++count;
52 x+=dx[k];
53 y+=dy[k];
54 }
55 if(count==len) {
56 ok=true;
57 printf("%d %d\\n",i,j);
58 }
59 }
60 }
61 //printf("\\n");
62 }
63
64 fclose(stdin);
65 fclose(stdout);
66 return 0;
67 }
68
|