比较烦人的模拟
1
#include<stdio.h>
2#include<string.h>
3char xy[30][30],yx[30][30],use[30][30];
4int n,m;
5void di(int x,int y)
6
{
7
if(x>=m||y>=n)return;
8 use[x][y]=0;
9 //printf("%d %d\n",x,y);
10 if(xy[x][y+1]&&use[x-1][y])di(x-1,y);
11 if(xy[x+1][y+1]&&use[x+1][y])di(x+1,y);
12 if(yx[y+1][x+1]&&use[x][y+1])di(x,y+1);
13 if(yx[y][x+1]&&use[x][y-1])di(x,y-1);
14
}
15int main()
16{
17 int ans,i,k,x1,x2,y1,y2,t,j;
18 while(scanf("%d%d",&n,&m),n)
19
{
20 memset(xy,1,sizeof(xy));
21 memset(use,1,sizeof(use));
22 memset(yx,1,sizeof(yx));
23 ans=0;
24 for(i=1;i<=m;i++)yx[0][i]=0;
25 for(i=1;i<=m;i++)yx[n][i]=0;
26 for(i=1;i<=n;i++)xy[0][i]=0;
27 for(i=1;i<=n;i++)xy[m][i]=0;
28 scanf("%d",&k);
29 while(k--)
30 {
31 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
32 if(x1>x2){t=x1;x1=x2;x2=t;}
33 if(y1>y2){t=y1;y1=y2;y2=t;}
34 // printf("asdasdasdas%d %d\n",x1,y1);
35 for(i=y1+1;i<=y2;i++)xy[x1][i]=0;
36 for(i=y1+1;i<=y2;i++)xy[x2][i]=0;
37 for(i=x1+1;i<=x2;i++)yx[y1][i]=0;
38 for(i=x1+1;i<=x2;i++)yx[y2][i]=0;
39
}
40 // printf("asdasdasdas%d\n",xy[1][1]);
41 for(i=0;i<m;i++)
42 for(j=0;j<n;j++)
43 {
44 if(use[i][j] && (xy[i][j+1] || xy[i+1][j+1] || yx[j][i+1] || yx[j+1][i+1]))
45 {
46 //printf("******************\n");
47 di(i,j);
48 ans++;
49 }
50 }
51 for(i=0;i<m;i++)
52 for(j=0;j<n;j++)if(use[i][j])ans++;
53 printf("%d\n",ans);
54
55 }
56 return 0;
57}
58
59
超多的if
1#include<stdio.h>
2char str[500];
3int a[50],ans,j,m,l,t,f[50];
4int main()
5{
6 int KASE,i;
7 scanf("%d",&KASE);
8 gets(str);
9 while(KASE--)
10 {
11 ans=0;j=0;m=0;l=0,t=0;
12 for(i=1;i<=26;i++){a[i]=i;f[i]=0;}
13 gets(str);
14 i=-1;
15 while(str[++i])
16 {
17 if(str[i]==' ');
18 else if(str[i]=='+'){j++;t=1;}
19 else if(str[i]=='-'){m++;t=-1;}
20 else
21 {
22
23 if(j+m==3)
24 {
25 if(j==2)
26 {
27 if(t==1){a[str[i]-'a'+1]++;ans-=a[str[i]-'a'+1];}
28 if(t==-1){a[l]++;ans-=a[str[i]-'a'+1];}
29 }
30 if(j==1)
31 {
32 if(t==1){a[l]--;ans+=a[str[i]-'a'+1];}
33 if(t==-1){a[str[i]-'a'+1]--;ans+=a[str[i]-'a'+1];}
34 }
35 //printf("*******%d\n",ans);
36 }
37 else if(j+m==2)
38 {
39 a[str[i]-'a'+1]+=t;
40 }
41 else if(j+m==1)
42 {
43 ans=ans+a[str[i]-'a'+1]*t;
44 }
45 if(!l)ans=a[str[i]-'a'+1];
46 l=str[i]-'a'+1;
47 f[l]=1;
48 j=0;m=0;
49 //printf("afadfadfadfadf%d %d\n",l,ans);
50 }
51 if(j==2 && m==0 && l){a[l]++;j=0;}
52 if(m==2 && j==0 && l){a[l]--;m=0;}
53 }
54 printf("Expression: %s\n",str);
55 printf("value = %d\n",ans);
56 for(i=1;i<=26;i++)
57 if(f[i])
58 printf("%c = %d\n",i+'a'-1,a[i]);
59 }
60 return 0;
61}
62
63
摘要: 最短路径问题。把每个点出发的所有路都存下然后每一个点中按每一个路的出发时间降序排序。然后就做超多遍最短路径就可以了
1#include<stdio.h> 2#include<map> 3#include<string> 4#include<string.h>&...
阅读全文
dfs就可以了。加一个剪枝
1。如果这个人被捉弄后会回到编号小于当前编号的点那么这人在这点肯定被捉弄。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char use[110];
int x[110],y[110],t[110],SUM[110];
int best=0;
int KASE,n,f,totle=0;
void di(int k,int sum)
{
totle++;
if(totle>100000000)return;
if(k==n)
{
if(sum>best)best=sum;
return;
}
if(use[k])
{
use[k]=0;
if(k<t[k] && (SUM[t[k]]-SUM[k]+x[k]-x[t[k]]>y[k]));
else di(t[k],sum+y[k]);
use[k]=1;
}
if(use[k]&&t[k]<k);
else di(k+1,sum+x[k]);
}
int main()
{
int i;
srand(406);
scanf("%d",&KASE);
while(KASE--)
{
scanf("%d",&n);
memset(use,1,sizeof(use));
for(i=0;i<n;i++)
{
scanf("%d%d%d",&x[i],&y[i],&t[i]);
t[i]--;
}
SUM[0]=x[i];
for(i=1;i<n;i++)SUM[i]=SUM[i-1]+x[i];
best=0;
di(0,0);
printf("%d\n",best);
}
return 0;
}
高精度的题目
一个高精的的数乘以int
然后统计里面k出现的次数就好了
1#include<stdio.h>
2#include<string.h>
3int a[400][1000];
4int l[400];
5int n,m;
6int main()
7{
8 int t,KASE,ans,i,j;
9 scanf("%d",&KASE);
10 memset(l,-1,sizeof(l));
11 memset(a,0,sizeof(a));
12 a[0][0]=1;l[0]=1;
13 for(i=1;i<=365;i++)
14 {
15 t=l[i-1];
16 for(j=0;j<t;j++)a[i][j]=a[i-1][j]*i;
17 //for(j=t-1;j>=0;j--)printf("%d",a[i][j]);printf("\n");
18 for(j=0;j<t-1;j++)
19 {
20 a[i][j+1]+=a[i][j]/10;
21 a[i][j]%=10;
22 }
23 l[i]=l[i-1];
24/**//*
25 for(j=0;j<t-1;j++)
26 {
27 a[i][j+1]+=a[i][j]/10;
28 a[i][j]%=10;
29 }
30*/
31 while(a[i][l[i]-1]>10)
32 {
33 // printf("asdasdasdasd\n");
34 a[i][l[i]]+=a[i][l[i]-1]/10;
35 a[i][l[i]-1]%=10;
36 l[i]++;
37 }
38 }
39 //printf("%dasdasda",a[4][1]);
40
41 for(i=0;i<KASE;i++)
42 {
43 scanf("%d%d",&n,&m);
44 ans=0;
45 for(j=0;j<l[n];j++)if(a[n][j]==m)ans++;
46 printf("%d\n",ans);
47 }
48 return 0;
49}
50
51
摘要: 很烦人的字符串处理。需要考虑的东西很多用c++写比较麻烦。自己用c++写的wa了3次才过。java的话直接正则表达式就可以了下面分别有c++和java的代码c++的代码属于自己原创java是转来别人的了
1#include<stdio.h> 2int main() 3{ 4 int&nb...
阅读全文
转自：
http://www.ccw.com.cn/htm/app/aprog/01_7_31_4.asp
| 如果你曾经用过Perl或任何其他内建正则表达式支持的语言，你一定知道用正则表达式处理文本和匹配模式是多么简单。如果你不熟悉这个术语，那么“正则表达式”（Regular Expression）就是一个字符构成的串，它定义了一个用来搜索匹配字符串的模式。 |
| 许多语言，包括Perl、PHP、Python、JavaScript和JScript，都支持用正则表达式处理文本，一些文本编辑器用正则表达式实现高级“搜索-替换”功能。那么Java又怎样呢？本文写作时，一个包含了用正则表达式进行文本处理的Java规范需求（Specification Request）已经得到认可，你可以期待在JDK的下一版本中看到它。 |
| 然而，如果现在就需要使用正则表达式，又该怎么办呢？你可以从Apache.org下载源代码开放的Jakarta-ORO库。本文接下来的内容先简要地介绍正则表达式的入门知识，然后以Jakarta-ORO API为例介绍如何使用正则表达式。 |
| 我们先从简单的开始。假设你要搜索一个包含字符“cat”的字符串，搜索用的正则表达式就是“cat”。如果搜索对大小写不敏感，单词“catalog”、“Catherine”、“sophisticated”都可以匹配。也就是说： |
| 假设你在玩英文拼字游戏，想要找出三个字母的单词，而且这些单词必须以“t”字母开头，以“n”字母结束。另外，假设有一本英文字典，你可以用正则表达式搜索它的全部内容。要构造出这个正则表达式，你可以使用一个通配符——句点符号“.”。这样，完整的表达式就是“t.n”，它匹配“tan”、“ten”、“tin”和“ton”，还匹配“t#n”、“tpn”甚至“t n”，还有其他许多无意义的组合。这是因为句点符号匹配所有字符，包括空格、Tab字符甚至换行符： |
| 为了解决句点符号匹配范围过于广泛这一问题，你可以在方括号（“[]”）里面指定看来有意义的字符。此时，只有方括号里面指定的字符才参与匹配。也就是说，正则表达式“t[aeio]n”只匹配“tan”、“Ten”、“tin”和“ton”。但“Toon”不匹配，因为在方括号之内你只能匹配单个字符： |
| 如果除了上面匹配的所有单词之外，你还想要匹配“toon”，那么，你可以使用“|”操作符。“|”操作符的基本意义就是“或”运算。要匹配“toon”，使用“t(a|e|i|o|oo)n”正则表达式。这里不能使用方扩号，因为方括号只允许匹配单个字符；这里必须使用圆括号“()”。圆括号还可以用来分组，具体请参见后面介绍。 |
| 表一显示了表示匹配次数的符号，这些符号用来确定紧靠该符号左边的符号出现的次数： |
| 假设我们要在文本文件中搜索美国的社会安全号码。这个号码的格式是999-99-9999。用来匹配它的正则表达式如图一所示。在正则表达式中，连字符（“-”）有着特殊的意义，它表示一个范围，比如从0到9。因此，匹配社会安全号码中的连字符号时，它的前面要加上一个转义字符“\”。 |
|
图一：匹配所有123-12-1234形式的社会安全号码
|
| 假设进行搜索的时候，你希望连字符号可以出现，也可以不出现——即，999-99-9999和999999999都属于正确的格式。这时，你可以在连字符号后面加上“？”数量限定符号，如图二所示： |
|
图二：匹配所有123-12-1234和123121234形式的社会安全号码
|
| 下面我们再来看另外一个例子。美国汽车牌照的一种格式是四个数字加上二个字母。它的正则表达式前面是数字部分“[0-9]{4}”，再加上字母部分“[A-Z]{2}”。图三显示了完整的正则表达式。 |
| “^”符号称为“否”符号。如果用在方括号内，“^”表示不想要匹配的字符。例如，图四的正则表达式匹配所有单词，但以“X”字母开头的单词除外。 |
| 假设要从格式为“June 26, 1951”的生日日期中提取出月份部分，用来匹配该日期的正则表达式可以如图五所示： |
| 新出现的“\s”符号是空白符号，匹配所有的空白字符，包括Tab字符。如果字符串正确匹配，接下来如何提取出月份部分呢？只需在月份周围加上一个圆括号创建一个组，然后用ORO API（本文后面详细讨论）提取出它的值。修改后的正则表达式如图六所示： |
|
图六：匹配所有Month DD,YYYY格式的日期，定义月份值为第一个组
|
| 为简便起见，你可以使用一些为常见正则表达式创建的快捷符号。如表二所示： |
| 例如，在前面社会安全号码的例子中，所有出现“[0-9]”的地方我们都可以使用“\d”。修改后的正则表达式如图七所示： |
|
图七：匹配所有123-12-1234格式的社会安全号码
|
| 有许多源代码开放的正则表达式库可供Java程序员使用，而且它们中的许多支持Perl 5兼容的正则表达式语法。我在这里选用的是Jakarta-ORO正则表达式库，它是最全面的正则表达式API之一，而且它与Perl 5正则表达式完全兼容。另外，它也是优化得最好的API之一。 |
| Jakarta-ORO库以前叫做OROMatcher，Daniel Savarese大方地把它赠送给了Jakarta Project。你可以按照本文最后参考资源的说明下载它。 |
| 我首先将简要介绍使用Jakarta-ORO库时你必须创建和访问的对象，然后介绍如何使用Jakarta-ORO API。 |
| 首先，创建一个Perl5Compiler类的实例，并把它赋值给PatternCompiler接口对象。Perl5Compiler是PatternCompiler接口的一个实现，允许你把正则表达式编译成用来匹配的Pattern对象。 |
| 要把正则表达式编译成Pattern对象，调用compiler对象的compile()方法，并在调用参数中指定正则表达式。例如，你可以按照下面这种方式编译正则表达式“t[aeio]n”： |
| 默认情况下，编译器创建一个大小写敏感的模式（pattern）。因此，上面代码编译得到的模式只匹配“tin”、“tan”、 “ten”和“ton”，但不匹配“Tin”和“taN”。要创建一个大小写不敏感的模式，你应该在调用编译器的时候指定一个额外的参数： |
| 创建好Pattern对象之后，你就可以通过PatternMatcher类用该Pattern对象进行模式匹配。 |
| PatternMatcher对象根据Pattern对象和字符串进行匹配检查。你要实例化一个Perl5Matcher类并把结果赋值给PatternMatcher接口。Perl5Matcher类是PatternMatcher接口的一个实现，它根据Perl 5正则表达式语法进行模式匹配： |
| 使用PatternMatcher对象，你可以用多个方法进行匹配操作，这些方法的第一个参数都是需要根据正则表达式进行匹配的字符串： |
| · boolean matches(String input, Pattern pattern)：当输入字符串和正则表达式要精确匹配时使用。换句话说，正则表达式必须完整地描述输入字符串。 |
| · boolean matchesPrefix(String input, Pattern pattern)：当正则表达式匹配输入字符串起始部分时使用。 |
| · boolean contains(String input, Pattern pattern)：当正则表达式要匹配输入字符串的一部分时使用（即，它必须是一个子串）。 |
| 另外，在上面三个方法调用中，你还可以用PatternMatcherInput对象作为参数替代String对象；这时，你可以从字符串中最后一次匹配的位置开始继续进行匹配。当字符串可能有多个子串匹配给定的正则表达式时，用PatternMatcherInput对象作为参数就很有用了。用PatternMatcherInput对象作为参数替代String时，上述三个方法的语法如下： |
| · boolean matches(PatternMatcherInput input, Pattern pattern) |
| · boolean matchesPrefix(PatternMatcherInput input, Pattern pattern) |
| · boolean contains(PatternMatcherInput input, Pattern pattern) |
| 下面我们来看看Jakarta-ORO库的一些应用实例。 |
| 任务：分析一个Web服务器日志文件，确定每一个用户花在网站上的时间。在典型的BEA WebLogic日志文件中，日志记录的格式如下： |
| 分析这个日志记录，可以发现，要从这个日志文件提取的内容有两项：IP地址和页面访问时间。你可以用分组符号（圆括号）从日志记录提取出IP地址和时间标记。 |
| 首先我们来看看IP地址。IP地址有4个字节构成，每一个字节的值在0到255之间，各个字节通过一个句点分隔。因此，IP地址中的每一个字节有至少一个、最多三个数字。图八显示了为IP地址编写的正则表达式： |
| IP地址中的句点字符必须进行转义处理（前面加上“\”），因为IP地址中的句点具有它本来的含义，而不是采用正则表达式语法中的特殊含义。句点在正则表达式中的特殊含义本文前面已经介绍。 |
| 日志记录的时间部分由一对方括号包围。你可以按照如下思路提取出方括号里面的所有内容：首先搜索起始方括号字符（“[”），提取出所有不超过结束方括号字符（“]”）的内容，向前寻找直至找到结束方括号字符。图九显示了这部分的正则表达式。 |
| 现在，把上述两个正则表达式加上分组符号（圆括号）后合并成单个表达式，这样就可以从日志记录提取出IP地址和时间。注意，为了匹配“- -”（但不提取它），正则表达式中间加入了“\s-\s-\s”。完整的正则表达式如图十所示。 |
| 现在正则表达式已经编写完毕，接下来可以编写使用正则表达式库的Java代码了。 |
| 为使用Jakarta-ORO库，首先创建正则表达式字符串和待分析的日志记录字符串： |
| 这里使用的正则表达式与图十的正则表达式差不多完全相同，但有一点例外：在Java中，你必须对每一个向前的斜杠（“\”）进行转义处理。图十不是Java的表示形式，所以我们要在每个“\”前面加上一个“\”以免出现编译错误。遗憾的是，转义处理过程很容易出现错误，所以应该小心谨慎。你可以首先输入未经转义处理的正则表达式，然后从左到右依次把每一个“\”替换成“\\”。如果要复检，你可以试着把它输出到屏幕上。 |
| 初始化字符串之后，实例化PatternCompiler对象，用PatternCompiler编译正则表达式创建一个Pattern对象： |
| 现在，创建PatternMatcher对象，调用PatternMatcher接口的contain()方法检查匹配情况： |
| 接下来，利用PatternMatcher接口返回的MatchResult对象，输出匹配的组。由于logEntry字符串包含匹配的内容，你可以看到类如下面的输出： |
| 下面一个任务是分析HTML页面内FONT标记的所有属性。HTML页面内典型的FONT标记如下所示： |
| 程序将按照如下形式，输出每一个FONT标记的属性： |
| 在这种情况下，我建议你使用两个正则表达式。第一个如图十一所示，它从字体标记提取出“"face="Arial, Serif" size="+2" color="red"”。 |
| 第二个正则表达式如图十二所示，它把各个属性分割成名字-值对。 |
| 现在我们来看看完成这个任务的Java代码。首先创建两个正则表达式字符串，用Perl5Compiler把它们编译成Pattern对象。编译正则表达式的时候，指定Perl5Compiler.CASE_INSENSITIVE_MASK选项，使得匹配操作不区分大小写。 |
| 接下来，创建一个执行匹配操作的Perl5Matcher对象。 |
| 假设有一个String类型的变量html，它代表了HTML文件中的一行内容。如果html字符串包含FONT标记，匹配器将返回true。此时，你可以用匹配器对象返回的MatchResult对象获得第一个组，它包含了FONT的所有属性： |
| 接下来创建一个PatternMatcherInput对象。这个对象允许你从最后一次匹配的位置开始继续进行匹配操作，因此，它很适合于提取FONT标记内属性的名字-值对。创建PatternMatcherInput对象，以参数形式传入待匹配的字符串。然后，用匹配器实例提取出每一个FONT的属性。这通过指定PatternMatcherInput对象（而不是字符串对象）为参数，反复地调用PatternMatcher对象的contains()方法完成。PatternMatcherInput对象之中的每一次迭代将把它内部的指针向前移动，下一次检测将从前一次匹配位置的后面开始。 |
| 下面我们来看看另一个处理HTML的例子。这一次，我们假定Web服务器从widgets.acme.com移到了newserver.acme.com。现在你要修改一些页面中的链接： |
| 如果能够匹配这个正则表达式，你可以用下面的内容替换图十三的链接： |
| 注意#字符的后面加上了$1。Perl正则表达式语法用$1、$2等表示已经匹配且提取出来的组。图十三的表达式把所有作为一个组匹配和提取出来的内容附加到链接的后面。 |
现在，返回Java。就象前面我们所做的那样，你必须创建测试字符串，创建把正则表达式编译到Pattern对象所必需的对象，以及创建一个PatternMatcher对象： |
| 接下来，用com.oroinc.text.regex包Util类的substitute()静态方法进行替换，输出结果字符串： |
| Util.substitute()方法的语法如下： |
| 这个调用的前两个参数是以前创建的PatternMatcher和Pattern对象。第三个参数是一个Substiution对象，它决定了替换操作如何进行。本例使用的是Perl5Substitution对象，它能够进行Perl5风格的替换。第四个参数是想要进行替换操作的字符串，最后一个参数允许指定是否替换模式的所有匹配子串（Util.SUBSTITUTE_ALL），或只替换指定的次数。 |
| 【结束语】在这篇文章中，我为你介绍了正则表达式的强大功能。只要正确运用，正则表达式能够在字符串提取和文本修改中起到很大的作用。另外，我还介绍了如何在Java程序中通过Jakarta-ORO库利用正则表达式。至于最终采用老式的字符串处理方式（使用StringTokenizer，charAt，和substring），还是采用正则表达式，这就有待你自己决定了。 |
最小路径问题。
求完以后排序就可以了。
这题wa了一次。因为最近写了好多有向图的然后这个在读入数据的时候忘记考虑这个是一个无向图了。
1#include<stdio.h>
2#include<string.h>
3int data[300][300],aa,bb,cc,a[300],b[300],n,m,i,j,k,t;
4int main()
5{
6 while(1)
7 {
8 scanf("%d",&n);
9 if(n==0)break;
10 scanf("%d",&m);
11 memset(data,3,sizeof(data));
12 for(i=0;i<m;i++)
13 {
14 scanf("%d%d%d",&aa,&bb,&cc);
15 data[aa][bb]=cc;
16 data[bb][aa]=cc;
17 }
18 for(i=0;i<n;i++)data[i][i]=0;
19 for(k=0;k<n;k++)
20 for(i=0;i<n;i++)
21 for(j=0;j<n;j++)
22 if(data[i][k]+data[k][j]<data[i][j])
23 data[i][j]=data[i][k]+data[k][j];
24 for(i=0;i<n;i++)a[i]=data[0][i];
25 for(i=0;i<n;i++)b[i]=i;
26 for(i=0;i<n;i++)
27 for(j=0;j<n-1;j++)
28 if((a[j]>a[j+1]) || ((a[j]==a[j+1])&& b[j]>b[j+1]))
29 {
30 t=a[j];
31 a[j]=a[j+1];
32 a[j+1]=t;
33 t=b[j];
34 b[j]=b[j+1];
35 b[j+1]=t;
36 }
37
38 scanf("%d",&k);
39 printf("%d\n",b[k]);
40 }
41 return 0;
42}
43