比較煩人的模擬
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