過(guò)兩天就是國(guó)慶了，我本來(lái)不打算寫(xiě)的，但是覺(jué)得現(xiàn)在狀況一定要記錄一下，以后可以借鑒！前幾天丟了工作，很受打擊，苦悶，晚上也睡不好，不知道怎么辦，在家里也學(xué)不進(jìn)東西！悶~~
高精度問(wèn)題
Time Limit:1000MS Memory Limit:65536K
Total Submit:381 Accepted:107
Description
相信經(jīng)過(guò)暑假一個(gè)月的培訓(xùn)，大家應(yīng)該已經(jīng)掌握了高精度的算法了。但是往往比賽中涉及到高精度的問(wèn)題并不多。而有些題目可能看起來(lái)需要高精度，而實(shí)際上并不需要。一個(gè)很好的例子就是3^p mod x, 初學(xué)者如果不知道同余的概念的話(huà)，可能會(huì)求出3^p先，然后再對(duì)x取余，然而這對(duì)p很大的時(shí)候是行不通的。。于是我們想到了邊乘邊取余，其基本的思想就是先把x的整數(shù)倍拿掉，因?yàn)樗麑?duì)最后的計(jì)算結(jié)果沒(méi)有影響，但是這種算法對(duì)于p超過(guò)1000000的時(shí)候就會(huì)顯得很慢了，你有沒(méi)有想到更好的辦法。
本題的任務(wù)就是給你一個(gè)p和x輸出3^p mod x
Input
每行一個(gè)數(shù)據(jù) p和x，2 < p, x ≤ 1000000000, 輸入最后以0 0結(jié)束
Output
輸出3^p mod x
Sample Input
10 7
0 0
Sample Output
4
這個(gè)題目老師教了我好幾遍我也沒(méi)懂。。。悲?。。。?/pre>
代碼如下：
#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;
}
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
就是這個(gè)題目上次我寫(xiě)整數(shù)劃分的時(shí)候半天也沒(méi)找到。。。直接用遞歸會(huì)超時(shí)??！
代買(mǎi)如下：
#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;
}
這是一個(gè)書(shū)上習(xí)題，求n個(gè)元素的非空子集劃分方案數(shù)。
我的代碼如下：
#include<stdio.h>
#include<string.h>
int m[10][10];//m[i][j]代表i個(gè)元素分成j個(gè)集合分法
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++)//構(gòu)造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++)//輸出結(jié)果
{
for(j=1;j<=i;j++)
printf("%d ",m[i][j]);
printf("\n");
}
return 0;
}
運(yùn)行結(jié)果：
騎士問(wèn)題
Time Limit:1000MS Memory Limit:65536K
Total Submit:160 Accepted:71
Description
在一個(gè)標(biāo)準(zhǔn)8*8的國(guó)際象棋棋盤(pán)上，棋盤(pán)中有些格子可能是有障礙物的。已知騎士的初始位置和目標(biāo)位置，你的任務(wù)是計(jì)算出騎士最少需要多少步可以從初始位置到達(dá)目標(biāo)位置。
有障礙物的格子當(dāng)然不可以到達(dá)。
標(biāo)準(zhǔn)的8*8的國(guó)際象棋棋盤(pán)中每個(gè)格子可以用唯一的編號(hào)確定。行用1~8這8個(gè)數(shù)字一次表示，列用a~h這8個(gè)字母依次表示如a4,b5等。騎士走日字型。
Input
多組測(cè)試數(shù)據(jù)。
每個(gè)測(cè)試數(shù)據(jù)的第一行是一個(gè)整數(shù)b( -1 <= b <= 62)表示棋盤(pán)中有障礙物的格子的數(shù)目，當(dāng)b=-1時(shí)表示輸入結(jié)束。
第二行含b個(gè)不同的有障礙物的格子編號(hào)，用空格隔開(kāi)，當(dāng)b=0時(shí)，此行為空行。
第三行是騎士的初始格子和目標(biāo)格子的編號(hào)，也用空格隔開(kāi)。
Output
每組輸出一行格式：
Board n: m moves
其中n表示數(shù)據(jù)的序號(hào)，m表示最少步數(shù)
如果騎士無(wú)法到達(dá)，則輸出
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)//統(tǒng)計(jì)步數(shù)
{
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;
}
馬的走法
Time Limit:1000MS Memory Limit:65536K
Total Submit:127 Accepted:80
Description
在一個(gè)4*5的棋盤(pán)上，輸入馬的起始位置坐標(biāo)（縱、橫），求馬能返回初始位置的所有不同走法的總數(shù)（馬走過(guò)的位置不能重復(fù),馬走“日”字）。
Input
多個(gè)測(cè)試數(shù)據(jù)。
每組2個(gè)數(shù)字
Output
輸出不同走法的總數(shù)。
Sample Input
2 2
Sample Output
4596
窮舉法！也可以看做深搜！角度不同。。這與前面一題過(guò)河卒不同，在過(guò)河卒中如果用深搜的話(huà)會(huì)超時(shí)，我試過(guò)了。。。
代碼如下：
#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;
}
過(guò)河卒
Time Limit:1000MS Memory Limit:65536K
Total Submit:691 Accepted:155
Description
棋盤(pán)上A點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)B點(diǎn)。卒行走的規(guī)則：可以向下、或者向右。同時(shí)在棋盤(pán)上的任一點(diǎn)有一個(gè)對(duì)方的馬（如C點(diǎn)），該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱(chēng)為對(duì)方馬的控制點(diǎn)，如圖中的C點(diǎn)和P1，……，P8，卒不能通過(guò)對(duì)方馬的控制點(diǎn)。棋盤(pán)用坐標(biāo)表示，A點(diǎn)(0,0)、B點(diǎn)(n, m) (n,m為不超過(guò)20的整數(shù)),同樣馬的位置坐標(biāo)是需要給出的，C≠A且C≠B?，F(xiàn)在要求你計(jì)算出卒從A點(diǎn)能夠到達(dá)B點(diǎn)的路徑的條數(shù)。
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
多個(gè)測(cè)試案例，每個(gè)案例一行，處理到文件末尾
B點(diǎn)坐標(biāo)（n,m）以及對(duì)馬的坐標(biāo)（X,Y）{不用判錯(cuò)}
Output
一個(gè)整數(shù)(路徑的條數(shù))
Sample Input
6 6 3 2
Sample Output
17
這個(gè)題目還是不錯(cuò)的。。。
代碼如下：
#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++)//計(jì)算受馬控制的點(diǎn)
{
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++)//計(jì)算一個(gè)點(diǎn)上的走法，上方點(diǎn)的走法數(shù)+左方點(diǎn)的走法數(shù)
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;
}
最少硬幣問(wèn)題
設(shè)有n 種不同面值的硬幣，各硬幣的面值存于數(shù)組T［1:n］中。現(xiàn)要用這些面值的硬幣來(lái)找錢(qián)。可以使用的各種面值的硬幣個(gè)數(shù)存于數(shù)組Coins［1:n］中。
對(duì)任意錢(qián)數(shù)0≤m≤20001，設(shè)計(jì)一個(gè)用最少硬幣找錢(qián)m的方法。
編程任務(wù)：
對(duì)于給定的1≤n≤10，硬幣面值數(shù)組T和可以使用的各種面值的硬幣個(gè)數(shù)數(shù)組Coins，以及錢(qián)數(shù)m，0≤m≤20001，編程計(jì)算找錢(qián)m的最少硬幣數(shù)。
Input
輸入包括多組測(cè)試數(shù)據(jù)，每組輸入的第一行中只有1 個(gè)整數(shù)給出n的值,第2 行起每
行2 個(gè)數(shù)，分別是T[j]和Coins[j]。每組輸入最后1 行是要找的錢(qián)數(shù)m。
Output
對(duì)于每組輸入數(shù)據(jù)，輸出一行，即計(jì)算出最少硬幣數(shù)。問(wèn)題無(wú)解時(shí)輸出-1。
Sample Input
3
1 3
2 3
5 3
18
Sample Output
5
動(dòng)態(tài)規(guī)劃題。
代碼如下：
#include<cstdio>
int main()
{
int t[11],coins[11],c[11][20002];//c[i][j]前i種硬幣找j塊錢(qián)最少硬幣數(shù)
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++) //構(gòu)造c數(shù)組
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
我們學(xué)校的ACM網(wǎng)站進(jìn)不去了。。。
滑雪，這個(gè)題目是稍微復(fù)雜一些的動(dòng)態(tài)規(guī)劃題，基本思路是先求的一個(gè)點(diǎn)上，上下左右上的最優(yōu)值，然后再做判斷。。該題一定要抓住這種思想，不然會(huì)很迷惑。
在代碼實(shí)現(xiàn)的時(shí)候，用了一個(gè)中間值temp，用來(lái)存貯最優(yōu)解。。。
代碼如下：
#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) //計(jì)算x,y點(diǎn)上的最大深度，事實(shí)上它可以計(jì)算出所有他可以到達(dá)點(diǎn)上的最優(yōu)值
{
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++) //從上下左右四個(gè)最優(yōu)值中選擇
{
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)//滿(mǎn)足條件的點(diǎn)，重置temp
{
temp=dfs(x0,y0)+1;
}
if(temp>sum) //更新最大深度
{
sum=temp;
}
}
s[x][y]=sum; //置最優(yōu)值
return sum; //返回最優(yōu)值
}
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;
}
這段代碼可能是我自己寫(xiě)的，我記得當(dāng)時(shí)我不理解這個(gè)，網(wǎng)上找了很多代碼來(lái)看，結(jié)果還是看不懂。?！，F(xiàn)在我看著這段代碼還是覺(jué)得虛，雖然我理解他的意思。。。總結(jié)經(jīng)驗(yàn)我覺(jué)得以前沒(méi)有好好理解這個(gè)題目，然后盲目的看代碼，結(jié)果毀了這個(gè)題目?。?！以后一定要抓住思路再寫(xiě)代碼?。?！其實(shí)這個(gè)題目可以看做是最長(zhǎng)不下降子序列擴(kuò)展到二維的情況??！可能這也是我解決不了這個(gè)題目的一個(gè)因素，除了思路不清晰外，在寫(xiě)代碼的時(shí)候直接用最優(yōu)數(shù)組去迭代是不能成功的?。∫玫街虚g變量！！最后總結(jié)為：1、盲目看\寫(xiě)代碼。。2、經(jīng)驗(yàn)主義。。
最長(zhǎng)不下降序列
Time Limit:1000MS Memory Limit:65536K
Total Submit:488 Accepted:197
Description
有由n個(gè)不相同的整數(shù)組成的數(shù)列，記為a(1)、a(2)、...a(n),當(dāng)i!=j時(shí)，a(i)!=a(j)。若存在i1 < i2 < i3 < ... < ie,且有a(i1) < a(i2) < ... < a(ie), 則稱(chēng)為長(zhǎng)度為e的不下降序列。
如 3，18，7，14，10，12，23，41，16，24
則有3，18，23，24是一個(gè)長(zhǎng)度為4的不下降子序列
3，7，10，12，23，24是長(zhǎng)度為6的不下降子序列。
現(xiàn)要求你求最長(zhǎng)的不下降子序列。
Input
多組測(cè)試數(shù)據(jù)
每組一行，先輸入一個(gè)數(shù)列長(zhǎng)度n （1 <= n <= 1000),然后是n個(gè)整數(shù)
處理到文件末尾
Output
輸出最長(zhǎng)不下降子序列的長(zhǎng)度
Sample Input
10 3 18 7 14 10 12 23 41 16 24
Sample Output
6
簡(jiǎn)單動(dòng)態(tài)規(guī)劃題，給予我們一種思想??！
代碼如下：
#include<stdio.h>
int Longest_Increasing(int num[],int List[],int n)//List[i]為包含i項(xiàng)在內(nèi)的最長(zhǎng)不下降子序列
{
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("最優(yōu)解：\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;
}