過兩天就是國慶了，我本來不打算寫的，但是覺得現在狀況一定要記錄一下，以后可以借鑒！前幾天丟了工作，很受打擊，苦悶，晚上也睡不好，不知道怎么辦，在家里也學不進東西！悶~~
posted @
2010-09-28 22:12 jince 閱讀(134) |
評論 (0) |
編輯 收藏高精度問題
Time Limit:1000MS Memory Limit:65536K
Total Submit:381 Accepted:107
Description
相信經過暑假一個月的培訓，大家應該已經掌握了高精度的算法了。但是往往比賽中涉及到高精度的問題并不多。而有些題目可能看起來需要高精度，而實際上并不需要。一個很好的例子就是3^p mod x, 初學者如果不知道同余的概念的話，可能會求出3^p先，然后再對x取余，然而這對p很大的時候是行不通的。。于是我們想到了邊乘邊取余，其基本的思想就是先把x的整數倍拿掉，因為他對最后的計算結果沒有影響，但是這種算法對于p超過1000000的時候就會顯得很慢了，你有沒有想到更好的辦法。
本題的任務就是給你一個p和x輸出3^p mod x
Input
每行一個數據 p和x，2 < p, x ≤ 1000000000, 輸入最后以0 0結束
Output
輸出3^p mod x
Sample Input
10 7
0 0
Sample Output
4
這個題目老師教了我好幾遍我也沒懂。。。悲劇！！！
代碼如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int modExp(int a, int b, int n)
{
__int64 t, y;
t=1;y=a;
while(b!=0)
{
if(b%2==1)
{
t=t*y%n;
}
y=y*y%n;
b=b/2;
}
return t;
}
int main()
{
int b,n;
while(scanf("%d %d",&b,&n)!=EOF&&(b!=0&&n!=0))
{
printf("%d\n",modExp(3,b,n));
}
return 0;
}
posted @
2010-09-19 14:21 jince 閱讀(199) |
評論 (0) |
編輯 收藏Ignatius and the Princess III
Time Limit:1000MS Memory Limit:65536K
Total Submit:86 Accepted:66
Description
"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.
"The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"
Input
The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.
Output
For each test case, you have to output a line contains an integer P which indicate the different equations you have found.
Sample Input
4
10
20
Sample Output
5
42
627
就是這個題目上次我寫整數劃分的時候半天也沒找到。。。直接用遞歸會超時！！
代買如下：
#include<cstdio>
int main()
{
int i,j,n,c[121][121];
for(i=1;i<121;i++)
for(j=1;j<121;j++)
{
if(i==1||j==1)
c[i][j]=1;
else if(i<j)
c[i][j]=c[i][i];
else if(i==j)
c[i][j]=c[i][j-1]+1;
else
c[i][j]=c[i][j-1]+c[i-j][j];
}
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",c[n][n]);
}
return 0;
}
posted @
2010-09-19 13:59 jince 閱讀(156) |
評論 (0) |
編輯 收藏
這是一個書上習題，求n個元素的非空子集劃分方案數。
我的代碼如下：
#include<stdio.h>
#include<string.h>
int m[10][10];//m[i][j]代表i個元素分成j個集合分法
int main()
{
int i,j;
memset(m,0,sizeof(m));
for(i=1;i<10;i++)//初始化
{
m[i][1]=1;
m[i][i]=1;
}
for(i=2;i<10;i++)//構造m解
{
for(j=2;j<i;j++)
{
m[i][j]=m[i-1][j]*j+m[i-1][j-1];
}
}
for(i=1;i<10;i++)//輸出結果
{
for(j=1;j<=i;j++)
printf("%d ",m[i][j]);
printf("\n");
}
return 0;
}
運行結果：
posted @
2010-09-19 13:23 jince 閱讀(462) |
評論 (0) |
編輯 收藏騎士問題
Time Limit:1000MS Memory Limit:65536K
Total Submit:160 Accepted:71
Description
在一個標準8*8的國際象棋棋盤上，棋盤中有些格子可能是有障礙物的。已知騎士的初始位置和目標位置，你的任務是計算出騎士最少需要多少步可以從初始位置到達目標位置。
有障礙物的格子當然不可以到達。
標準的8*8的國際象棋棋盤中每個格子可以用唯一的編號確定。行用1~8這8個數字一次表示，列用a~h這8個字母依次表示如a4,b5等。騎士走日字型。
Input
多組測試數據。
每個測試數據的第一行是一個整數b( -1 <= b <= 62)表示棋盤中有障礙物的格子的數目，當b=-1時表示輸入結束。
第二行含b個不同的有障礙物的格子編號，用空格隔開，當b=0時，此行為空行。
第三行是騎士的初始格子和目標格子的編號，也用空格隔開。
Output
每組輸出一行格式：
Board n: m moves
其中n表示數據的序號，m表示最少步數
如果騎士無法到達，則輸出
Board n: not reachable
Sample Input
10
c1 d1 d5 c2 c3 c4 d2 d3 d4 c5
a1 f1
0
c1 b3
2
b3 c2
a1 b2
-1
Sample Output
Board 1: 7 moves
Board 2: 1 moves
Board 3: not reachable
廣度搜索！
代碼如下：
#include<stdio.h>
#include<string.h>
int a[8]={-2,-2,-1,-1,1,1,2,2};
int b[8]={1,-1,2,-2,2,-2,1,-1};
int p[2][1000];
int s[9][9];
int head;
int tail;
int count;
int x3,y3;
int temp;
#define cr(x) memset(x,0,sizeof(x));
int fun(int x,int y)
{
int x1,y1;
int i;
int x2,y2;
while(head<tail)
{
x1=p[0][head];
y1=p[1][head];
for(i=0;i<8;i++)
{
x2=x1+a[i];
y2=y1+b[i];
if(x2==x3&&y2==y3)
{
return 1;
}
else if(s[x2][y2]==0&&x2>0&&y2>0&&x2<9&&y2<9)
{
p[0][tail]=x2;
p[1][tail]=y2;
tail++;
s[x2][y2]=1;
}
}
if(head==temp)//統計步數
{
temp=tail-1;
count++;
}
head++;
}
return 0;
}
int main()
{
int x,y;
int i,j;
int d;
char c[2];
int x1,y1;
int z=0;
while(scanf("%d",&d)!=EOF&&d!=-1)
{
z++;
for(i=1;i<9;i++)
for(j=1;j<9;j++)
{
s[i][j]=0;
}
for(i=0;i<d;i++)
{
scanf("%s",c);
x=c[1]-48;
y=c[0]-96;
s[x][y]=1;
}
scanf("%s",c);
x1=c[1]-48;
y1=c[0]-96;
scanf("%s",c);
x3=c[1]-48;
y3=c[0]-96;
p[0][0]=x1;
p[1][0]=y1;
s[x1][y1]=1;
count=0;
head=0;
tail=1;
temp=0;
if(fun(x1,y1)==1)
{
printf("Board %d: %d moves\n",z,count+1);
}
else
{
printf("Board %d: not reachable\n",z);
}
}
return 0;
}
posted @
2010-09-19 10:11 jince 閱讀(335) |
評論 (0) |
編輯 收藏馬的走法
Time Limit:1000MS Memory Limit:65536K
Total Submit:127 Accepted:80
Description
在一個4*5的棋盤上，輸入馬的起始位置坐標（縱、橫），求馬能返回初始位置的所有不同走法的總數（馬走過的位置不能重復,馬走“日”字）。
Input
多個測試數據。
每組2個數字
Output
輸出不同走法的總數。
Sample Input
2 2
Sample Output
4596
窮舉法！也可以看做深搜！角度不同。。這與前面一題過河卒不同，在過河卒中如果用深搜的話會超時，我試過了。。。
代碼如下：
#include<stdio.h>
#include<string.h>
int count;
int s[4][5];
int a[8]={-2,-2,-1,-1,1,1,2,2};
int b[8]={1,-1,2,-2,2,-2,1,-1};
int x1,y1;
void fun(int x,int y)
{
int i;
int x2,y2;
for(i=0;i<8;i++)
{
x2=x+a[i];
y2=y+b[i];
if((x2>=0)&&(y2>=0)&&(y2<=4)&&(x2<=3)&&(s[x2][y2]==0))
{
s[x2][y2]=1;
fun(x2,y2);
s[x2][y2]=0;
}
else if((x2==x1)&&(y2==y1))
count++;
}
}
int main()
{
while((scanf("%d %d",&x1,&y1)!=EOF))
{
count=0;
if((x1<=4)&&(y1<=5)&&(y1>0)&&(x1>0))
{
x1=x1-1;
y1=y1-1;
memset(s,0,sizeof(s));
s[x1][y1]=1;
fun(x1,y1);
printf("%d\n",count);
}
else
{
printf("%d\n",count);
}
}
return 0;
}
posted @
2010-09-19 10:03 jince 閱讀(793) |
評論 (2) |
編輯 收藏過河卒
Time Limit:1000MS Memory Limit:65536K
Total Submit:691 Accepted:155
Description
棋盤上A點有一個過河卒，需要走到目標B點。卒行走的規則：可以向下、或者向右。同時在棋盤上的任一點有一個對方的馬（如C點），該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點，如圖中的C點和P1，……，P8，卒不能通過對方馬的控制點。棋盤用坐標表示，A點(0,0)、B點(n, m) (n,m為不超過20的整數),同樣馬的位置坐標是需要給出的，C≠A且C≠B。現在要求你計算出卒從A點能夠到達B點的路徑的條數。
1 2 3 4 5 6 7 8
A +---+---+---o---+---o---+---+----+--------->Y
| | | | | | | | |
1 +---+---o---+---+---+---o---+----+
| | | | | | | | |
2 +---+---+---+---C---+---+---+----+
| | | | | | | | |
3 +---+---o---+---+---+---o---+----+
| | | | | | | | |
4 +---+---+---o---+---o---+---+----+ B(4,8)
|
|
V
X
Input
多個測試案例，每個案例一行，處理到文件末尾
B點坐標（n,m）以及對馬的坐標（X,Y）{不用判錯}
Output
一個整數(路徑的條數)
Sample Input
6 6 3 2
Sample Output
17
這個題目還是不錯的。。。
代碼如下：
#include<stdio.h>
int s[21][21];
__int64 c[21][21];
int a0[8]={-2,-2,-1,-1,1,1,2,2};
int b0[8]={1,-1,2,-2,2,-2,1,-1};
int x1,y1;
int x3,y3;
int main()
{
int x2,y2;
int i,j;
int test;
while((scanf("%d %d %d %d",&x1,&y1,&x3,&y3)!=EOF))
{
for(i=0;i<21;i++)
for(j=0;j<21;j++)
{
s[i][j]=1;
c[i][j]=0;
}
s[x3][y3]=0;
for(i=0;i<8;i++)//計算受馬控制的點
{
x2=x3+a0[i];
y2=y3+b0[i];
if((x2>=0)&&(y2>=0)&&(y2<=20)&&(x2<=20))
{
s[x2][y2]=0;
}
}
test=1;
for(j=0;j<21;j++)//初始化邊上的走法
{
if(test)
{
if(s[0][j]==0)
{
test=0;
}
else
{
c[0][j]=1;
}
}
}
test=1;
for(j=0;j<21;j++)
{
if(test)
{
if(s[j][0]==0)
{
test=0;
}
else
{
c[j][0]=1;
}
}
}
for(i=1;i<21;i++)//計算一個點上的走法，上方點的走法數+左方點的走法數
for(j=1;j<21;j++)
{
if(s[i][j])
{
c[i][j]=c[i-1][j]*s[i-1][j]+c[i][j-1]*s[i][j-1];
}
}
printf("%I64d\n",c[x1][y1]);
}
return 0;
}
posted @
2010-09-19 09:45 jince 閱讀(2125) |
評論 (2) |
編輯 收藏最少硬幣問題
設有n 種不同面值的硬幣，各硬幣的面值存于數組T［1:n］中。現要用這些面值的硬幣來找錢。可以使用的各種面值的硬幣個數存于數組Coins［1:n］中。
對任意錢數0≤m≤20001，設計一個用最少硬幣找錢m的方法。
編程任務：
對于給定的1≤n≤10，硬幣面值數組T和可以使用的各種面值的硬幣個數數組Coins，以及錢數m，0≤m≤20001，編程計算找錢m的最少硬幣數。
Input
輸入包括多組測試數據，每組輸入的第一行中只有1 個整數給出n的值,第2 行起每
行2 個數，分別是T[j]和Coins[j]。每組輸入最后1 行是要找的錢數m。
Output
對于每組輸入數據，輸出一行，即計算出最少硬幣數。問題無解時輸出-1。
Sample Input
3
1 3
2 3
5 3
18
Sample Output
5
動態規劃題。
代碼如下：
#include<cstdio>
int main()
{
int t[11],coins[11],c[11][20002];//c[i][j]前i種硬幣找j塊錢最少硬幣數
int i,j,n,m,k;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%d %d",&t[i],&coins[i]);
}
scanf("%d",&m);
for(i=1;i<=n;i++) //初始化
for(j=0;j<=m;j++)
{
if(j==0)
c[i][j]=0;
else if(i==1)
if(j%t[i]==0&&j/t[i]<=coins[i])
c[1][j]=j/t[i];
else
c[1][j]=1000000;
else
c[i][j]=1000000;
}
for(i=2;i<=n;i++) //構造c數組
for(j=1;j<=m;j++)
for(k=0;k<=coins[i];k++)
{
if(c[i][j]>(c[i-1][j-k*t[i]]+k)&&(j-k*t[i])>=0)
c[i][j]=c[i-1][j-k*t[i]]+k;
}
if(c[n][m]!=1000000)
{
printf("%d\n",c[n][m]);
}
else
printf("-1\n");
}
return 0;
}
題目地址：http://acm.nankai.edu.cn/p1132.html
posted @
2010-09-17 13:32 jince 閱讀(3765) |
評論 (0) |
編輯 收藏 我們學校的ACM網站進不去了。。。
滑雪，這個題目是稍微復雜一些的動態規劃題，基本思路是先求的一個點上，上下左右上的最優值，然后再做判斷。。該題一定要抓住這種思想，不然會很迷惑。
在代碼實現的時候，用了一個中間值temp，用來存貯最優解。。。
代碼如下：
#include<stdio.h>
#include<string.h>
int s[101][101],map[101][101];
int d[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int n,m;
int dfs(int x,int y) //計算x,y點上的最大深度，事實上它可以計算出所有他可以到達點上的最優值
{
int sum=0;
int temp=0;
int i,x0,y0;
if(s[x][y]!=0)
return s[x][y];
for(i=0;i<4;i++) //從上下左右四個最優值中選擇
{
x0=d[i][0]+x;
y0=d[i][1]+y;
temp=1; //最小深度為1。。
if((map[x0][y0]<map[x][y])&&x0>=0&&y0>=0&&x0<n&&y0<m)//滿足條件的點，重置temp
{
temp=dfs(x0,y0)+1;
}
if(temp>sum) //更新最大深度
{
sum=temp;
}
}
s[x][y]=sum; //置最優值
return sum; //返回最優值
}
int main()
{
int sum,i,j;
while(scanf("%d %d",&n,&m)!=EOF)
{
memset(s,0,sizeof(s));
sum=0;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&map[i][j]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
dfs(i,j);
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(s[i][j]>sum)
sum=s[i][j];
//printf("%d ",s[i][j]);
}
// printf("\n");
}
printf("%d\n",sum);
}
return 0;
}
這段代碼可能是我自己寫的，我記得當時我不理解這個，網上找了很多代碼來看，結果還是看不懂。。。現在我看著這段代碼還是覺得虛，雖然我理解他的意思。。。總結經驗我覺得以前沒有好好理解這個題目，然后盲目的看代碼，結果毀了這個題目！！！以后一定要抓住思路再寫代碼！！！其實這個題目可以看做是最長不下降子序列擴展到二維的情況！！可能這也是我解決不了這個題目的一個因素，除了思路不清晰外，在寫代碼的時候直接用最優數組去迭代是不能成功的！！要用到中間變量！！最后總結為：1、盲目看\寫代碼。。2、經驗主義。。
posted @
2010-09-17 10:29 jince 閱讀(504) |
評論 (0) |
編輯 收藏最長不下降序列
Time Limit:1000MS Memory Limit:65536K
Total Submit:488 Accepted:197
Description
有由n個不相同的整數組成的數列，記為a(1)、a(2)、...a(n),當i!=j時，a(i)!=a(j)。若存在i1 < i2 < i3 < ... < ie,且有a(i1) < a(i2) < ... < a(ie), 則稱為長度為e的不下降序列。
如 3，18，7，14，10，12，23，41，16，24
則有3，18，23，24是一個長度為4的不下降子序列
3，7，10，12，23，24是長度為6的不下降子序列。
現要求你求最長的不下降子序列。
Input
多組測試數據
每組一行，先輸入一個數列長度n （1 <= n <= 1000),然后是n個整數
處理到文件末尾
Output
輸出最長不下降子序列的長度
Sample Input
10 3 18 7 14 10 12 23 41 16 24
Sample Output
6
簡單動態規劃題，給予我們一種思想！！
代碼如下：
#include<stdio.h>
int Longest_Increasing(int num[],int List[],int n)//List[i]為包含i項在內的最長不下降子序列
{
int i,j;
for(i=1;i<n;i++)
{
for(j=0;j<i;j++)
{
if(num[i]>num[j]&&List[i]<List[j]+1)
List[i]=List[j]+1;
}
}
return 0;
}
int main()
{
int n,i,ans;
int num[1001],List[1001];
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
List[i]=1;
scanf("%d",&num[i]);
}
Longest_Increasing(num,List,n);
/**//* printf("最優解：\n");
for(i=0;i<n;i++)
printf("%d ",List[i]);
printf("\n");*/
ans=0;
for(i=0;i<n;i++)
if(List[i]>ans)
ans=List[i];
printf("%d\n",ans);
}
return 0;
}
posted @
2010-09-16 13:16 jince 閱讀(987) |
評論 (0) |
編輯 收藏