2018-06-06

话说终于上200了，然而还是没有到平均分。。

---

Pro 1 猫鼠游戏 (catch.pas/cpp/c)
题目描述：
猫和老鼠在10*10的方格中运动，例如：

 *...*..... 
 ......*... 
 ...*...*.. 
 .......... 
 ...*.C....
 *.....*...
 ...*......
 ..M......*
 ...*.*....
 .*.*......

C=猫（CAT） M=老鼠（MOUSE） *=障碍物 .=空地
猫和老鼠每秒中走一格，如果在某一秒末他们在同一格中，我们称他们“相遇”。
注意，“对穿”是不算相遇的。猫和老鼠的移动方式相同：平时沿直线走，下一步如果会走到障碍物上去或者出界，就用1秒的时间做一个右转90度。一开始他们都面向北方。 编程计算多少秒以后他们相遇。
【输入文件】 10行，格式如上。
【输出文件】 相遇时间T。如果无解，输出-1。
【样例输入】

*...*.....
......*...
...*...*..
..........
...*.C....
*.....*...
...*......
..M......*
...*.*....
.*.*......

【样例输出】
49

看一眼，这不是usaco模拟题嘛。。然后随手打了一个模拟就过了。。还是欣慰自己没有忘记的。。

#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并没有过样例由于算法太过玄学(本蒟蒻理解不了，请移步到pfy的题解

---

Pro 2 牛语 (cowlpha.pas/cpp/c)
题目描述：
像很多牛科动物一样，农夫John的奶牛会说一种特定的“牛语”。像很多语言一样，这种语言的每个单词包含一串大写或小写的字母 (A-Z以及a-z).一个单词是合法的当且仅当单词中每一对有序临近字母是合法的。
农夫John担心他的奶牛在预谋反对他，因而最近窃听了奶牛们的交流。他为了不被发现只偶然听到了一些单词，又因为"牛语"语速实在太快，所以农夫John实际只能分辨出一个单词里大写字母的总数(1≤U≤250)和小写字母总数(1≤L≤250).
输入格式：
第一行：3个由1个空格隔开的整数U,L,和P；
第2~p+1行：两个字母(每一个都有可能是大写或者小写)，定义一对“牛语”合法有序临近对；
输出格式：
第一行：一个数，农夫John可能的听到的单词数，对97654321取模.
样例输入：
2 2 7
AB
ab
BA
ba
Aa
Bb
bB
样例输出：
7
样例解释：
AabB
ABba
abBA
BAab
BbBb
bBAa
bBbB

一看完这题表示（这肯定是dp啊，那岂不是要爆蛋了。。想了一回dp写不出就去打暴力（超级优秀啊，过了两个点呢看来要开始刷dp题了啊。。
一下bb正解
设f[i][j][k] 为枚举到第i位，当前位为j，大写字母个数为k的方案数

/*
#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;//单个字母初始化一下
 for(int i=2;i<=n+m;i++)//现在是第i位
    for(int j=1;j<=52;j++)//当前是哪个字符
    for(int k=1;k<=52;k++)//之前是哪个字符
    if(a[k][j]){
        for(int b=0;b<=n;b++)//大写字母个数
        f[i][j][b]=(f[i][j][b]+f[i-1][k][b-(j>26)])%p;//大力转移
    }
    int ans=0;
    for(int i=1;i<=52;i++) ans=(ans+f[n+m][i][n])%p;
    printf("%d",ans)%p;
}

看完标程就觉得dp可想但是还需修炼啊

---

Pro 3 汉诺塔 (han.pas/cpp/c)

题目描述：

小T在寂寞的玩汉诺塔……汉诺塔，众所周知，用3个杆和n个大小不同的圆盘来玩，要把n个在第一个杆上的从上到下一次从小到大的圆盘在第三个杆的帮助下全部转移到第二个杆上，转移过程中要遵循一个法则就是大的圆盘不能放到小的上面。

现在小T在玩自然是遵循最优步数的，也就是n个盘子一定要用最少的2^n -1步完成，自然，在这个前提下圆盘的移动也是确定的，如2个圆盘一定是：

现在小T想知道她当前玩到的局面是否遵循了最优解，如果是，她想确定自己已经玩了多少步.

输入格式：

第1行两个个整数n（1≤n≤31），接下来n行，每行一个数字wi表示第i小的圆盘在第wi跟杆上（wi∈[1,2,3]）

输出格式：

输出文件包含仅一行一个整数，如果到此局面已经不符合最优解则输出-1，否则输出已经玩了多少步。

样例输入：
2
3
1
样例输出：
1

表示连普通汉诺塔都写不出。。基础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){
//显然最大的那根柱子只会在起点和终点。如果跑到另外一个上就可以判-1了
        flag=1;
        return;
    }
    if(a[now]==s)//大柱子还在原来那里，就把上面的移掉
        dfs(s,6-s-f,now-1);
    if(a[now]==f){//大柱子到了目标，统计答案并继续把上面的移过来
        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个圆盘从1移到2（mj好像这里看错题目了。。
    if(flag) puts("-1");
    else printf("%d",ans);
    return 0;
}

Pro4 数学游戏 (maga.pas/cpp/c)
题目描述：
小T又发脑残了，没错，她又要求奇怪的东西，这次她想知道[X,Y]之间整数有多少可以表示成K个不同的B的幂的和形势。如x,y,k,b=15,20,2,2,则有：
17=2⁴⁺²0
18=2⁴⁺²1
20=2⁴⁺²2 共3个符合要求的数

输入格式：
输入仅包含一行4个空格隔开的整数X，Y，K，B（1≤X≤Y≤2^31 -1,1≤K≤20）

输出格式：
输出文件包含一行一个即为所求合法数字个数。

样例输入：
15 20 2 2

样例输出：
3

超级自信地打了暴力。。于是拿到了78的好成绩（据说是数据范围的锅。。原来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
*/

满分算法是数位dp。。
考场上：x到y？怕不是数位dp？k个数加起来？不会转移放弃放弃，还是打暴力去吧
正解：把这个数转化成b进制数，这样问题就转化成了x到y有多少个数有且只有k个1，其余都为0。据说b=1的时候要判一下。。1进制数？不存在的。不判不判。

#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)//数位dp当然是选择记搜啊
{
    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;//
//这里有点玄学。。因为题目要求不能重复。。所以每一个数字的最高位枚举到1就好了。。当然也有可能上界是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));
} 

话说这年头写题解的大佬好多啊。。蒟蒻只能瑟瑟发抖

本学期第一次上200然而还是GG