話說終于上200了，然而還是沒有到平均分谴古。切油。
Pro 1 貓鼠游戲 (catch.pas/cpp/c)
題目描述：
貓和老鼠在10*10的方格中運(yùn)動(dòng)，例如：
*...*.....
......*...
...*...*..
..........
...*.C....
*.....*...
...*......
..M......*
...*.*....
.*.*......
C=貓（CAT） M=老鼠（MOUSE） *=障礙物 .=空地
貓和老鼠每秒中走一格简软，如果在某一秒末他們在同一格中，我們稱他們“相遇”述暂。
注意痹升，“對穿”是不算相遇的。貓和老鼠的移動(dòng)方式相同：平時(shí)沿直線走畦韭，下一步如果會(huì)走到障礙物上去或者出界疼蛾，就用1秒的時(shí)間做一個(gè)右轉(zhuǎn)90度。一開始他們都面向北方艺配。 編程計(jì)算多少秒以后他們相遇据过。
【輸入文件】 10行，格式如上妒挎。
【輸出文件】 相遇時(shí)間T。如果無解西饵，輸出-1酝掩。
【樣例輸入】
*...*.....
......*...
...*...*..
..........
...*.C....
*.....*...
...*......
..M......*
...*.*....
.*.*......
【樣例輸出】
49
看一眼，這不是usaco模擬題嘛眷柔。期虾。然后隨手打了一個(gè)模擬就過了原朝。。還是欣慰自己沒有忘記的镶苞。喳坠。
#include <iostream>
#include <cstdio>
using namespace std;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int a[20][20],d[11][11][11][11][4][4];
char c[20][20];
int flag,ok=1,ans;
void dfs(int cx,int cy,int mx,int my,int cf,int mf,int step)
{
// cout<<cx<<" "<<cy<<" "<<mx<<" "<<my<<endl;
if(flag) return;
if(d[cx][cy][mx][my][cf][mf]){
flag=1; ok=0;
return;
}
if(cx==mx&&cy==my) {
flag=1;
ans=step;
return;
}
d[cx][cy][mx][my][cf][mf]=1;
int cxx=cx+dx[cf];
int cyy=cy+dy[cf];
int mxx=mx+dx[mf];
int myy=my+dy[mf];
if(!a[cxx][cyy]&&!a[mxx][myy]) dfs(cx,cy,mx,my,(cf+1)%4,(mf+1)%4,step+1);
else if(!a[cxx][cyy]) dfs(cx,cy,mxx,myy,(cf+1)%4,mf,step+1);
else if(!a[mxx][myy]) dfs(cxx,cyy,mx,my,cf,(mf+1)%4,step+1);
else dfs(cxx,cyy,mxx,myy,cf,mf,step+1);
}
int main()
{
freopen("catch.in","r",stdin);
freopen("catch.out","w",stdout);
int cx,cy,mx,my;
for(int i=1;i<=10;i++)
{
scanf("%s",c[i]+1);
for(int j=1;j<=10;j++)
{
if(c[i][j]=='.') a[i][j]=1;
else if(c[i][j]=='C') cx=i,cy=j,a[i][j]=1;
else if(c[i][j]=='M') mx=i,my=j,a[i][j]=1;
// cout<<a[i][j];
}
// puts("");
}
// cout<<cx<<" "<<cy<<" "<<mx<<" "<<my<<endl;
dfs(cx,cy,mx,my,0,0,0);
if(!ok) puts("-1");
else printf("%d",ans);
return 0;
}
/*
..........
..........
..........
..*.*.*...
..*M.C*...
..*.*.*...
..........
..........
..........
..........
*/
沒有刷完（guo）試煉場的mj同志表示他的程序能過1000*1000
（然而zz并沒有過樣例由于算法太過玄學(xué)(本蒟蒻理解不了，請移步到pfy的題解
Pro 2 牛語 (cowlpha.pas/cpp/c)
題目描述：
像很多琶荆科動(dòng)物一樣壕鹉，農(nóng)夫John的奶牛會(huì)說一種特定的“牛語”。像很多語言一樣聋涨，這種語言的每個(gè)單詞包含一串大寫或小寫的字母 (A-Z以及a-z).一個(gè)單詞是合法的當(dāng)且僅當(dāng)單詞中每一對有序臨近字母是合法的晾浴。
農(nóng)夫John擔(dān)心他的奶牛在預(yù)謀反對他，因而最近竊聽了奶牛們的交流牍白。他為了不被發(fā)現(xiàn)只偶然聽到了一些單詞脊凰，又因?yàn)?牛語"語速實(shí)在太快，所以農(nóng)夫John實(shí)際只能分辨出一個(gè)單詞里大寫字母的總數(shù)(1≤U≤250)和小寫字母總數(shù)(1≤L≤250).
輸入格式：
第一行：3個(gè)由1個(gè)空格隔開的整數(shù)U,L,和P茂腥；
第2~p+1行：兩個(gè)字母(每一個(gè)都有可能是大寫或者小寫)狸涌，定義一對“牛語”合法有序臨近對；
輸出格式：
第一行：一個(gè)數(shù)最岗，農(nóng)夫John可能的聽到的單詞數(shù)帕胆，對97654321取模.
樣例輸入：
2 2 7
AB
ab
BA
ba
Aa
Bb
bB
樣例輸出：
7
樣例解釋：
AabB
ABba
abBA
BAab
BbBb
bBAa
bBbB
一看完這題表示（這肯定是dp啊，那豈不是要爆蛋了仑性。惶楼。想了一回dp寫不出就去打暴力
（超級(jí)優(yōu)秀啊，過了兩個(gè)點(diǎn)呢看來要開始刷dp題了啊诊杆。歼捐。
一下bb正解
設(shè)f[i][j][k] 為枚舉到第i位，當(dāng)前位為j晨汹，大寫字母個(gè)數(shù)為k的方案數(shù)
/*
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
string t;
map<string,bool> vis;
bool exi[5000];
int bi,sm,n,ans;
struct arr{
int s,b;
char fi,se;
}ss[3000000];
bool check(string a)
{
for(int i=0;i<a.length()-1;i++)
{
int t=a[i]*10+a[i+1];
if(!exi[t]) return false;
}
return true;
}
void dfs(int rt,int s,int b)
{
if(!check(t)&&t.length()!=0) return;
if(s==sm&&b==bi)
{
if(!vis[t]) vis[t]=1,ans++;
return;
}
if(rt>n) return;
if(ss[rt].s+s<=sm&&ss[rt].b+b<=bi)
{
string tem=t;
t+=ss[rt].fi;
t+=ss[rt].se;
for(int i=1;i+rt<=n;i++)
dfs(rt+i,s+ss[rt].s,b+ss[rt].b);
dfs(rt,s+ss[rt].s,b+ss[rt].b);
for(int i=1;i<rt;i++)
dfs(rt-i,s+ss[rt].s,b+ss[rt].b);
t=tem;
}
dfs(rt+1,s,b);
// dfs(rt,s,b);
// dfs(rt-1,s,b);
}
int main()
{
freopen("cowlpha.in","r",stdin);
freopen("cowlpha.out","w",stdout);
scanf("%d%d%d",&bi,&sm,&n);
for(int i=1;i<=n;i++)
{
cin>>ss[i].fi>>ss[i].se;
exi[ss[i].fi*10+ss[i].se]=1;
if(ss[i].fi>='A'&&ss[i].fi<='Z')ss[i].b++; else ss[i].s++;
if(ss[i].se>='A'&&ss[i].se<='Z')ss[i].b++; else ss[i].s++;
}
dfs(0,0,0);
printf("%d",ans);
return 0;
}
3 3 7
AB
ab
BA
ba
Aa
Bb
bB
*/
#include <iostream>
#include <cstdio>
using namespace std;
const int p=97654321;
int turn(char ch){
if(ch>='A'&&ch<='Z') return ch-'A'+27;
else if(ch>='a'&&ch<='z') return ch-'a'+1;
}
int a[1001][1001],f[530][54][500];
int main()
{
freopen("cowlpha.in","r",stdin);
freopen("cowlpha.out","w",stdout);
int n,m,pp;
char ch,ch1;
scanf("%d%d%d",&n,&m,&pp);
for(int i=1;i<=pp;i++){
cin>>ch>>ch1;
a[turn(ch)][turn(ch1)]=1;
}
for(int i=1;i<=52;i++) f[1][i][(i>26)]=1;//單個(gè)字母初始化一下
for(int i=2;i<=n+m;i++)//現(xiàn)在是第i位
for(int j=1;j<=52;j++)//當(dāng)前是哪個(gè)字符
for(int k=1;k<=52;k++)//之前是哪個(gè)字符
if(a[k][j]){
for(int b=0;b<=n;b++)//大寫字母個(gè)數(shù)
f[i][j][b]=(f[i][j][b]+f[i-1][k][b-(j>26)])%p;//大力轉(zhuǎn)移
}
int ans=0;
for(int i=1;i<=52;i++) ans=(ans+f[n+m][i][n])%p;
printf("%d",ans)%p;
}
看完標(biāo)程就覺得dp可想但是還需修煉啊
Pro 3 漢諾塔 (han.pas/cpp/c)
題目描述：
小T在寂寞的玩漢諾塔……漢諾塔豹储，眾所周知，用3個(gè)桿和n個(gè)大小不同的圓盤來玩淘这，要把n個(gè)在第一個(gè)桿上的從上到下一次從小到大的圓盤在第三個(gè)桿的幫助下全部轉(zhuǎn)移到第二個(gè)桿上剥扣，轉(zhuǎn)移過程中要遵循一個(gè)法則就是大的圓盤不能放到小的上面。
現(xiàn)在小T在玩自然是遵循最優(yōu)步數(shù)的铝穷，也就是n個(gè)盤子一定要用最少的2^n -1步完成钠怯，自然，在這個(gè)前提下圓盤的移動(dòng)也是確定的曙聂，如2個(gè)圓盤一定是：
現(xiàn)在小T想知道她當(dāng)前玩到的局面是否遵循了最優(yōu)解晦炊，如果是，她想確定自己已經(jīng)玩了多少步.
輸入格式：
第1行兩個(gè)個(gè)整數(shù)n（1≤n≤31），接下來n行断国，每行一個(gè)數(shù)字wi表示第i小的圓盤在第wi跟桿上（wi∈[1,2,3]）
輸出格式：
輸出文件包含僅一行一個(gè)整數(shù)贤姆，如果到此局面已經(jīng)不符合最優(yōu)解則輸出-1，否則輸出已經(jīng)玩了多少步稳衬。
樣例輸入：
2
3
1
樣例輸出：
1
表示連普通漢諾塔都寫不出霞捡。”【危基礎(chǔ)GG 然后就爆蛋了
還是和著代碼理解吧
#include <iostream>
#include <cstdio>
using namespace std;
int a[1000],ans,flag;
void dfs(int s,int f,int now)
{
if(!now) return;
if(a[now]!=s&&a[now]!=f){
//顯然最大的那根柱子只會(huì)在起點(diǎn)和終點(diǎn)碧信。如果跑到另外一個(gè)上就可以判-1了
flag=1;
return;
}
if(a[now]==s)//大柱子還在原來那里，就把上面的移掉
dfs(s,6-s-f,now-1);
if(a[now]==f){//大柱子到了目標(biāo)输涕，統(tǒng)計(jì)答案并繼續(xù)把上面的移過來
ans+=1<<(now-1);
dfs(6-s-f,f,now-1);
}
}
int main()
{
freopen("han.in","r",stdin);
freopen("han.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
dfs(1,2,n);//表示把第n個(gè)圓盤從1移到2（mj好像這里看錯(cuò)題目了音婶。。
if(flag) puts("-1");
else printf("%d",ans);
return 0;
}
Pro4 數(shù)學(xué)游戲 (maga.pas/cpp/c)
題目描述：
小T又發(fā)腦殘了莱坎，沒錯(cuò)衣式，她又要求奇怪的東西，這次她想知道[X,Y]之間整數(shù)有多少可以表示成K個(gè)不同的B的冪的和形勢檐什。如x,y,k,b=15,20,2,2,則有：
17=24+20
18=24+21
20=24+22 共3個(gè)符合要求的數(shù)
輸入格式：
輸入僅包含一行4個(gè)空格隔開的整數(shù)X碴卧，Y，K乃正，B（1≤X≤Y≤2^31 -1,1≤K≤20）
輸出格式：
輸出文件包含一行一個(gè)即為所求合法數(shù)字個(gè)數(shù)住册。
樣例輸入：
15 20 2 2
樣例輸出：
3
超級(jí)自信地打了暴力。瓮具。于是拿到了78的好成績（據(jù)說是數(shù)據(jù)范圍的鍋荧飞。。原來k是10名党。叹阔。然后暴力就能過。传睹。
baoli代碼
#include <iostream>
#include <cstdio>
#define int long long
#include <map>
using namespace std;
int bin[100];
map<int,bool> vis;
int x,y,k,kk,b,ans;
void dfs(int rt,int gs,int sum)
{
// cout<<rt<<" "<<gs<<" "<<sum<<endl;
if(rt>kk+1) return;
if(gs==k)
{
// cout<<sum<<endl;
if(sum>=x&&sum<=y)
{
ans++;
}
return;
}
dfs(rt+1,gs+1,sum+bin[rt]);
dfs(rt+1,gs,sum);
}
signed main()
{
freopen("maga.in","r",stdin);
freopen("maga.out","w",stdout);
scanf("%lld%lld%lld%lld",&x,&y,&k,&b);
bin[0]=1;
for(kk=1;bin[kk-1]*b<=y;kk++)
bin[kk]=bin[kk-1]*b;
kk--;
// cout<<kk<<endl;
dfs(0,0,0);
printf("%lld",ans);
return 0;
}
/*
2
234566156
6
5
*/
滿分算法是數(shù)位dp耳幢。。
考場上：x到y(tǒng)欧啤？怕不是數(shù)位dp睛藻？k個(gè)數(shù)加起來？不會(huì)轉(zhuǎn)移放棄放棄邢隧，還是打暴力去吧
正解：把這個(gè)數(shù)轉(zhuǎn)化成b進(jìn)制數(shù)店印，這樣問題就轉(zhuǎn)化成了x到y(tǒng)有多少個(gè)數(shù)有且只有k個(gè)1，其余都為0倒慧。據(jù)說b=1的時(shí)候要判一下按摘。讥邻。1進(jìn)制數(shù)？不存在的院峡。不判不判。
#include <iostream>
using namespace std;
int x,y,k,b;
int dp[40][2][50],a[50];
int dfs(int len,int sx,int gs)//數(shù)位dp當(dāng)然是選擇記搜啊
{
if(gs>k) return 0;
if(len==0)
{
if(gs==k) return 1;
return 0;
}
if(!sx&&dp[len][sx][gs]) return dp[len][sx][gs];
int mx=sx?a[len]:1;//
if(mx>1) mx=1;//
//這里有點(diǎn)玄學(xué)系宜。照激。因?yàn)轭}目要求不能重復(fù)。盹牧。所以每一個(gè)數(shù)字的最高位枚舉到1就好了俩垃。。當(dāng)然也有可能上界是0
int ans=0;
for(int i=0;i<=mx;i++)
ans+=dfs(len-1,sx&&(i==a[len]),gs+(i==1));
return dp[len][sx][gs]=ans;
}
int sol(int x)
{
int len=0;
while(x)
{
a[++len]=x%b;
x/=b;
}
dfs(len,1,0);
}
int main()
{
freopen("maga.in","r",stdin);
freopen("maga.out","w",stdout);
scanf("%d%d%d%d",&x,&y,&k,&b);
printf("%d",sol(y)-sol(x-1));
}
話說這年頭寫題解的大佬好多啊汰寓。口柳。蒟蒻只能瑟瑟發(fā)抖
