HDU3687 National Day Parade

Posted on February 14, 2012 by Greenmoon55

国庆游行，学生们本来排成n*n的队形，休息时他们仅左右移动，现在求在什么位置恢复n*n队形，使所有学生当前位置到目标位置的距离的和最短。
n<=56,m<=200，左上角为(1, 1)，右下角为(n, m)，每位学生的位置 1<=Xi<=n,1<= Yi<=m

最开始以为是平均数，后来发现就是枚举目标位置。
每行一个vector，存该行点的y坐标。读入后排序，然后枚举队伍最左边的那一列。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int MAX = 2147483647;
 
int main()
{
    int n, m;
    int a, b;
    int count;
    while (true)
    {
        cin >> n >> m;
        if (!n && !m) break;
        vector<int> line[60];
        count = n * n;
 
        while (count--)
        {
            cin >> a >> b;
            line[a].push_back(b);
        }
        for (int i = 1; i <= n; i++) sort(line[i].begin(), line[i].end());
 
        int sum, ans = MAX;
        //起始位置
        for (int i = 1; i <= m - n; i++)
        {
            sum = 0;
            //行
            for (int j = 1; j <= n; j++)
            {
                //列
                for (int k = 0; k < n; k++)
                sum += abs(line[j][k] - i - k); //-(i+k)
            }
            if (sum < ans) ans = sum;
        }
        cout << ans << endl;
    }
    return 0;
}

HDU3682 To Be an Dream Architect

Posted on February 14, 2012 by Greenmoon55

题意：一个 n x n x n 的立方体，每次消除一行（平行于坐标轴），共消除 m 次，求共消除了多少 1 * 1 * 1 的小块。(1 <= n <= 1000, 0 <= m <= 1000)

第一想法是三维布尔数组数组存状态，然后模拟。不会超时但会MLE。
北大的题解里说了两种方法，第一种是考虑线段的交点，然后用容斥原理，我还没想具体怎么写。第二种是一层一层考虑，把垂直于某层的线和在这个面上的线分开考虑，比较好理解。

经过搜索，搜到了这两个题解：
http://blog.csdn.net/liuwei_nefu/article/details/6009644
http://www.cnblogs.com/FreeAquar/archive/2011/09/15/2178029.html

做法就是把点坐标映射为int，比如x * 1000000 + y * 1000 + z。然后把所有直线上的点丢到一个vector里，排序后再用unique函数，然后删去不需要的部分，求出vector的大小，这就是真正删掉的点。用set做会超时，而且内存占用很多。。
这几个函数只是知道名字，用法一点都不熟悉。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
inline bool illegal(const int &x)
{
    return !(x <= 1000 && x > 0);
}
inline int getint(const int &x, const int &y, const int &z)
{
    //cout<<x * 1000000 + y * 1000 + z<<endl;
    return x * 1000000 + y * 1000 + z;
}
int main()
{
    int t, m, n;
    char ch1, ch2;
    int a, b;
    cin >> t;
    while(t--)
    {
        vector<int> myvector;
        cin >> n >> m;
        getchar();
        while (m--)
        {
            scanf("%c=%d,%c=%d\n", &ch1, &a, &ch2, &b);
            if (illegal(a) || illegal(b)) continue;
            a--;
            b--;
            if (ch1 == 'X')
                if (ch2 == 'Y')
                    {
                        for (int i = 0; i < n; i++) myvector.push_back(getint(a, b, i));
                    }
                else //X=a,Z=b
                {
 
                    for (int i = 0; i < n; i++) myvector.push_back(getint(a, i, b));
                }
            if (ch1 == 'Y')
                if (ch2 == 'X')
                {
                    for (int i = 0; i < n; i++)
                    {
                        myvector.push_back(getint(b, a, i));
                    }
                }
                else //Y=a,Z=b
                {
 
                    for (int i = 0; i < n; i++)
                    {
                        myvector.push_back(getint(i, a, b));
                    }
                }
            if (ch1 == 'Z')
                if (ch2 == 'X')
                {
                    for (int i = 0; i < n; i++)
                    {
                        myvector.push_back(getint(b, i, a));
                    }
                }
                else
                {
                    for (int i = 0; i < n; i++)
                    {
                        myvector.push_back(getint(i, b, a));
                    }
                }
        }
        sort(myvector.begin(), myvector.end());
        myvector.erase(unique(myvector.begin(), myvector.end()), myvector.end());
        cout << myvector.size() << endl;
    }
    return 0;
}

HDU4119 Isabella’s Message

Posted on February 12, 2012 by Greenmoon55

给定密文和密文中可能出现的单词，按题意输出原文。

 
#include <iostream>
#include <cstdio>
#include <cstring>
 
using namespace std;
 
int n;
char map[55][55],temp[55][55],newmap[55][55],mask[55][55];
char word[5][2555];
char list[105][25];
char s[5][10100];
int ans[5][10100];
 
void rotate()
{
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    newmap[j][n-i+1]=temp[i][j];
}
void getword(int num)
{
    int pos=0;
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    {
        if (newmap[i][j]=='*') word[num][pos++]=map[i][j];
    }
}
int main()
{
    int t;
    int wordnum;
 
    freopen("1009.txt","r",stdin);
 
    scanf("%d",&t);
    for (int tcase=1; tcase<=t;tcase++)
    {
        memset(s,0,sizeof(s));
        memset(word,0,sizeof(word));
        memset(ans,0,sizeof(ans));
        scanf("%d",&n);
        for (int i=1;i<=n;i++) scanf("%s",map[i]+1);
        for (int i=1;i<=n;i++) scanf("%s",mask[i]+1);
        scanf("%d",&wordnum);
        for (int i=0;i<wordnum;i++) scanf("%s",list[i]);
 
        memcpy(temp,mask,sizeof(mask));
        memcpy(newmap,mask,sizeof(mask));
        getword(0);
        for (int i=1;i<4;i++)
        {
            rotate();
            getword(i);
            memcpy(temp,newmap,sizeof(newmap));
        }
 
        //连接四句话
        for (int i=0;i<4;i++)
        {
            for (int j=i;j<i+4;j++)
            {
                strcat(s[i],word[j%4]);
            }
        }
 
        char tempword[10100];
        /*
        strcpy(s[0],"the..love..you....forever");
        strcpy(s[1],"love..you..forever");
        strcpy(s[2],"..love.the.forever");
        strcpy(s[3],"the.forver..love");
        */
 
        for (int i=0;i<4;i++)
        {
            int j=0;
            while (s[i][j]=='.' && j<strlen(s[i])) j++; //找到第一个单词...
            if (j>=strlen(s[i])) continue;
 
            int tpos;
            while (j<strlen(s[i]))
            {
                memset(tempword,0,sizeof(tempword));
                tpos=0;
                while (j<strlen(s[i]) && s[i][j]!='.')
                {
                    tempword[tpos++]=s[i][j++];
                }
                bool find = false;
                for (int k=0;k<wordnum;k++)
                {
                    if (!strcmp(tempword,list[k]))
                    {
                        find = true;
                        ans[i][0]++; //单词个数
                        ans[i][ans[i][0]]=k; //第几个单词
                        break;
                    }
                }
                if (!find)
                {
                    ans[i][0]=0;
                    break;
                }
		//多余的点
                while (j<strlen(s[i]) && s[i][j]=='.')
                {
                    j++;
                }
            }
        }
        bool find = false;
        int ar[10]; //存符合条件的方向
        memset(ar,0,sizeof(ar));
        int arsize=0;
        for (int i=0;i<4;i++)
        {
            if (ans[i][0])
            {
                find =true;
                ar[++arsize]=i;
            }
        }
        printf("Case #%d:",tcase);
        if (!find)
        {
            printf(" FAIL TO DECRYPT\n");
            continue;
        }
 
        int nar[10];
        int index =1;
        int minnode;
        while (arsize>1)
        {
            minnode=1; //字典序最小的序号
            //不停地找出字典序最小的那个...
            for (int j=1;j<=arsize;j++)
            {
                if (strcmp(list[ans[ar[j]][index]],list[ans[ar[minnode]][index]])<0) minnode=j;
            }
            int p=0;
	    //生成新数组（第一个单词是字典序最小的单词，且相同...）
            for (int j=1;j<=arsize;j++)
            {
                if (strcmp(list[ans[ar[j]][index]],list[ans[ar[minnode]][index]])==0) nar[++p]=ar[j];
            }
            arsize=p;
            memcpy(ar,nar,sizeof(nar));//新数组覆盖旧数组
            index++;
        }
        for (int i=1;i<=ans[ar[1]][0];i++)
        {
            printf(" %s",list[ans[ar[1]][i]]);
        }
        printf("\n");
    }
    return 0;
}

模拟题。
以前写的，我是怎么写出这么恶心的代码的…

HDU4112 Break the Chocolate

Posted on February 12, 2012 by Greenmoon55

将N*M*K的巧克力分成1*1*1，用刀切可以同时切多块，用手掰每次只能将一块掰成两块。

思路：用刀切显然是log2(m)+log2(n)+log2(k)（每个都取上整），手掰的话，首先n-1次掰成n块，然后m-1次掰成m*n块，最后k-1次掰成m*n*k块，(n-1)+n*(m-1)+m*n*(k-1)，整理得m*n*k-1。后来看到一种想法，每掰一块多一个，所以就是m*n*k-1次。

 
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
 
int ans(int n, int m, int k)
{
    return ceil(log(double(n))/log(2.0)) + ceil(log(double(m))/log(2.0)) + ceil(log(double(k))/log(2.0));
}
int main()
{
    int t;
    int n, m, k;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cin >> n >> m >> k;
        printf("Case #%d: %lld %d\n", i, (long long)n * m * k - 1, ans(n, m, k));
    }
    return 0;
}

写的时候把t和k弄混过……
还要注意用long long。

HDU4121 Xiangqi

Posted on February 2, 2012 by Greenmoon55

只有四种棋子：将、车、马、炮，黑方只有一个将，现在被红方将，红方有2至7个棋子，判断黑方是否被将死。

考虑黑将的四个行动方向，判断每个位置是否被将死即可。

将：判断两个将之间是否有棋子
车：同上
马：八个方向，容易出错，详见代码
炮：将与炮之间是否只有一个棋子

//不考虑黑方飞将也能过，不知道到底该不该考虑。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct point
{
    int x,y;
}g[10], r[10], h[10], c[10]; //bg:black general
int gcount, rcount, hcount, ccount;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
 
const int hx[] = {-2, -2, -1, 1, 2, 2, 1, -1};
const int hy[] = {1, -1, 2, 2, 1, -1, -2, -2};
bool map[10][10]; //红旗子
 
//将是否在范围内
bool isValid(int x, int y)
{
    return y >= 4 && y <= 6 && x >= 1 && x <= 3;
}
 
//[a,y]到[b,y]的棋子个数（不含端点）
int betweenX(int y, int a, int b)
{
    int sum = 0;
    if (a < b)
    {
        for (int i = a + 1; i < b; i++)
        {
            if (map[i][y]) sum++;
        }
    }
    else
    {
        for (int i = b + 1; i < a; i++)
        {
            if (map[i][y]) sum++;
        }
    }
    return sum;
}
 
//[x,a]到[x,b]的棋子个数（不含端点）
int betweenY(int x, int a, int b)
{
    int sum = 0;
    if (a < b)
    {
        for (int i = a + 1; i < b; i++)
        {
            if (map[x][i]) sum++;
        }
    }
    else
    {
        for (int i = b + 1; i < a; i++)
        {
            if (map[x][i]) sum++;
        }
    }
    return sum;
}
 
//将的新位置newbg是否会被红方飞将
bool isSafeGeneral(point const &newbg)
{
    //其实只有一个嘛
    for (int i = 0; i < gcount; i++)
    {
        if (newbg.y == g[i].y)
        {
            if (betweenX(newbg.y, newbg.x, g[i].x) == 0) return false;
        }
    }
    return true;
}
 
//是否会被车吃（中间没有其他棋子）
bool isSafeChariot(point const &newbg)
{
    for (int i = 0; i < rcount; i++)
    {
        if (newbg.x == r[i].x && newbg.y == r[i].y) continue; //这就是吃掉了
        if (newbg.x == r[i].x)
        {
            if (betweenY(newbg.x, newbg.y, r[i].y) == 0) return false;
        }
        if (newbg.y == r[i].y)
        {
            if (betweenX(newbg.y, newbg.x, r[i].x) == 0) return false;
        }
    }
    return true;
}
 
//是否会被炮打（中间棋子为1）
bool isSafeCannon(point const &newbg)
{
    for (int i = 0; i < ccount; i++)
    {
        if (newbg.x == c[i].x && newbg.y == c[i].y) continue; //这就是吃掉了
        if (newbg.x == c[i].x)
        {
            if (betweenY(newbg.x, newbg.y, c[i].y) == 1) return false;
        }
        if (newbg.y == c[i].y)
        {
            if (betweenX(newbg.y, newbg.x, c[i].x) == 1) return false;
        }
    }
    return true;
}
 
bool isSafeHorse(point const &newbg)
{
    int newx, newy;
    for (int i = 0; i < hcount; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            newx = h[i].x + dx[j / 2];
            newy = h[i].y + dy[j / 2];
            if (map[newx][newy]) continue; //别马腿
            newx = h[i].x + hx[j];
            newy = h[i].y + hy[j];
            if (newx == newbg.x && newy == newbg.y) return false;
        }
    }
    return true;
}
 
//如果不被将，返回真
bool check(point const &newbg)
{
    return isSafeGeneral(newbg) && isSafeCannon(newbg) && isSafeHorse(newbg) && isSafeChariot(newbg);
}
 
int main()
{
    int n;
    char ch;
    int a, b;
    while (true)
    {
        point bg, newbg; //bg:black general
        gcount = 0, rcount = 0, hcount = 0, ccount = 0;
        memset(map, 0, sizeof(map));
        bool checkmate = true;
        cin >> n >> bg.x >> bg.y;
        if (!n) break;
        for (int i = 0; i < n; i++)
        {
            cin >> ch >> a >> b;
            map[a][b] = true;
            if (ch == 'G')
            {
                g[gcount].x = a;
                g[gcount].y = b;
                gcount++;
            } else
            if (ch == 'R')
            {
                r[rcount].x = a;
                r[rcount].y = b;
                rcount++;
            } else
            if (ch == 'H')
            {
                h[hcount].x = a;
                h[hcount].y = b;
                hcount++;
            } else
            if (ch == 'C')
            {
                c[ccount].x = a;
                c[ccount].y = b;
                ccount++;
            }
        }
        //不考虑飞将也能过
        /*
        if (!isSafeGeneral(bg))
        {
            puts("NO");
            continue;
        }
        */
        //将的四个方向
        for (int i = 0; i < 4; i++)
        {
            newbg.x = bg.x + dx[i];
            newbg.y = bg.y + dy[i];
            if (!isValid(newbg.x, newbg.y)) continue;
            if (check(newbg))
            {
                checkmate = false;
                break;
            }
        }
        if (checkmate) puts("YES");
        else puts("NO");
    }
    return 0;
}

敲代码的时候曾经把g、r、h、c数组弄混过。。以后这种题还是用拼音算了。
测了样例和马的情况就交了。
第一次WA错在puts里面写了\n…
又测了几个数据都正常，然后看了一遍代码，还是没发现错误。
试了黑棋直接飞将，还是WA，看别人题解突然想到我还考虑将走斜线的情况了。。
最后，似乎是否考虑黑棋直接飞将都可以。

这题我没着急慢慢写的，如果现场的话至少两小时吧，很有可能有个小错找不出来，不确定到底能不能写好。
还是边写边想，还好没犯大错误，betweenX等是写了很多之后才想到单独写个函数的。。

只有两周了，时间好紧张= =

用字符数组存int

Posted on December 9, 2011 by Greenmoon55

EUYUIL告诉我可以用字符数组存int。挺好玩。

unsigned char test[100];
memset(test, 0, sizeof(test));
int a = 2147483647;
int *p = (int*)&test;
*p = a;
int b = *p;
cout << b << endl;

此时test数组为{255, 255, 255, 127, 0…}
当然，如果a是1的话，test就是{1, 0, 0, 0, 0…}
这是VS2010编译的结果。。不知道其他编译器其他平台结果怎么样。。

刚刚在stackoverflow搜到这个问题，以后有空再看看吧。

总感觉我C++好弱，指针几乎没用过= =

Update @ 2011/12/13 23:39
如果放入TCHAR里，就是{65535, 32767, …}。

ICPC 2011

Posted on October 13, 2011 by Greenmoon55

随便写个标题吧。。算不算标题党？整理一下最近写的题目。

大连网络赛：
To Miss Our Children Time
背包问题，排个序就行了，题目描述不清。。

Find Metal Mineral
树形动归，f[x][j]表示以x为根的树，前i个子树放j个机器人不回来的最小值，DFS的感觉。f[x][0]表示放一个再出来。做的第一个树形动归，参照别人的代码，很巧妙的写法嘛。刚才看题目忘了具体怎么写了= =

void work(int x,int prev)
{
    for (int i=head[x];i!=-1;i=edge[i].next)
    {
        if (edge[i].y==prev) continue;
        work(edge[i].y,x);
        for (int j=k;j>=0;j--)
        {
            f[x][j]+=f[edge[i].y][0]+edge[i].w*2;
            for (int l=0;l<j;l++)
            f[x][j]=min(f[x][j],f[x][l]+edge[i].w*(j-l)+f[edge[i].y][j-l]);
        }
    }
}

PS：原来这个叫做分组背包= =

The Frog’s Games
比赛的时候以为是DP，结果就是个二分…

The kth great number
最简单的办法就是弄一个最小堆，堆顶就是答案，priority_queue用起来很爽。

priority_queue <int, vector<int>, greater<int> > heap;
 
if (heap.size()<k) heap.push(temp);
else if (temp>heap.top())
    {
        heap.pop();
        heap.push(temp);
    }

还可以写个treap..treap的删除还不会写= =

Dave
注意正方形的顶点不一定是题中的点。
把点分别按x和y排序，四条线扫描，写得比较乱= =

The 36th ACM/ICPC Asia Regional Shanghai Site —— Warmup
Working in Beijing
Parsing URL
两道水题，第一题题目说明不清楚= = 做做调节心情

上海网络赛
24 Puzzle
如果空位在角上则挪到中间的正方形里，然后比较8个角是否相同，相同才有可能有解。对于4*4，左右交换不改变逆序对，上下交换时逆序数的奇偶性改变一次(0-3,3-0,1-2,2-1)。
http://zhyu.me/acm/hdu-4021.html
觉得这个证明不完备，没想好怎么证。

Bombing
multiset真的很爽…

typedef map<int, multiset<int> > dict;
 
void work(dict &a, dict &b, int &x)  //delete a(x) from b
{
    printf("%d\n",a[x].size());
    for (multiset<int>::iterator iter=a[x].begin();iter!=a[x].end();iter++)
    {
        b[*iter].erase(x);
    }
    a[x].clear();
}
 
int main()
{
    int n,m,x,y;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        if (n==0 && m==0) break;
        dict a,b;
        for (int i=0;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            a[x].insert(y);
            b[y].insert(x);
        }
        for (int i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            if (x==0) work(a,b,y);
            else work(b,a,y);
        }
        printf("\n");
    }
    return 0;
}

Game
比较简单的博弈问题，比赛的时候没静下心来想。
分组讨论，注意一个细节，9、10如果竖着的放好了，对方就不用抢这种了。

成都网络赛
Graph
给最短边求原图，原来可以这样写

void work(const int n)
{
    for (int k=0;k<n;k++)
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
    {
        if (i==j || i==k || k==j) continue;
        if ((!visited[i][j]) && map[i][k]+map[k][j]==map[i][j])
        {
            ++c;
            visited[i][j]=true;
        }
    }
}

printf("%d\n",n*(n-1)-c);

Rolling Hongshu
物理题，考虑顶点和所有bitter potato。题目描述挺好玩…

The Social Network
第一次用map。

map<string,int> num;

读入：

cin>>s1>>s2;
if (num.count(s1)) n1=num.find(s1)->second;
else
    {
        num.insert(make_pair(s1, ++count));
        n1=count;
        sn[n1]=s1;
    }
if (num.count(s2)) n2=num.find(s2)->second;
else
    {
        num.insert(make_pair(s2, ++count));
        n2=count;
        sn[n2]=s2;
    }
f[n1][++f[n1][0]]=n2;//f[n1]存n1的朋友们
f[n2][++f[n2][0]]=n1;

接下来就慢慢弄吧…

北京网络赛
Eliminate Witches!
模拟，递归处理，WA好几次= =
不过这个是我在今年网络赛时作出的第一道题= =

Panda
树状数组。a[i]表示以i开头的是不是wbw。自己没想到这种方法。

if (s[i]=='w' && s[i+1]=='b' && s[i+2]=='w') add(i,1);

Tourism Planning
第一个状态压缩DP，把某人去不去用二进制表示。
f[15][1030];//f[i][j]前i个景点，第j个状态的最大值
预处理当前状态能由哪些状态得到，如果不预处理HDU可以很快AC，BOJ会TLE= =

wolf5x
概率DP。
比赛时就想对了方法，读题不认真，以为第一步左右概率相同呢。
赛后写好，发现还是看错题了，以为是求停止位置，原来是求步数的期望，可以直接把所有状态的概率加起来！

int main()
{
    int t;
    int n,a,b;
    int i,j;
    double ans;
    double p[2010][4];
    double f[2010][4];
    double temp1,temp2,temp3;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d%d",&n,&a,&b);
        ans=0;
        for (i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&p[i][0],&p[i][1],&p[i][2],&p[i][3]);
        memset(f,0,sizeof(f));
        temp1=1;
        for (i=a;i<=b;i++)
        {
            if (i>n)
            {
                ans+=temp1;
                break;
            }
            for (j=1;j<=3;j++) f[i][j]=temp1*p[i][j];
            temp1*=p[i][0];
        }
        for (i=a;i<=n;i++)
        {
            temp1=temp2=temp3=1;
            for (j=i+a;j<=i+b;j++)
            {
                if (j>n)
                {
                    ans+=f[i][1]*temp1+f[i][2]*temp2+f[i][3]*temp3;
                    break;
                }
                else
                {
                    f[j][1]+=(f[i][2]*temp2+f[i][3]*temp3)*p[j][1]; //表示以这种状态踩在j
                    f[j][2]+=(f[i][1]*temp1+f[i][3]*temp3)*p[j][2];
                    f[j][3]+=(f[i][1]*temp1+f[i][2]*temp2+f[i][3]*temp3)*p[j][3];
                    temp1*=p[j][0]+p[j][1];  //tempi表示f[prev][i]不能走的概率
                    temp2*=p[j][0]+p[j][2];
                    temp3*=p[j][0];
                }
            }
            ans+=f[i][1]+f[i][2]+f[i][3];
        }
        printf("%.8lf\n",ans);
    }
    return 0;
}

大连现场赛
The Last Puzzle
对于任意一段，都是从任意一端开始到中间，因为如果从中间开始，还是要先到两端再到最终节点。想通了这个就很好写了。
f[i][j][k]表示从i到j这一段，k表示从左或从右开始，所需的最短时间。不可能则记为-1。

Hexadecimal View
水题，不知道可以用 %x 输出…

Number String
f[i][j]存当前所有可能情况，即i=n时只有f[n][1]。表示字符串中第i位是，表中第j个有几种情况。f[i+1]保存的数量比f[i]少一个，因为有一个数字被选走了。

for (i=1;i<=n;i++) f[1][i]=1;
for (int ii=0;ii<n;ii++)
{
    i=ii+2;
    if (str[ii]=='I')
    {
        f[i][1]=f[i-1][1];
        for (j=2;j<=n-i+1;j++) f[i][j]=(f[i-1][j]+f[i][j-1])%MOD;
    }
    else if (str[ii]=='D')
    {
        f[i][n-i+1]=f[i-1][n-i+2];
        for (j=n-i;j>=1;j--) f[i][j]=(f[i-1][j+1]+f[i][j+1])%MOD;
    }
    else
    {
        sum=0;
        for (j=1;j<=n-i+2;j++) sum=(sum+f[i-1][j])%MOD;
        for (j=1;j<=n-i+1;j++) f[i][j]=sum;
    }
}
printf("%d\n",f[n][1]);

福州网络赛
SanguoSHA
当时不爽，写这题写了好久= = 最后写好了觉得会WA，于是没交，回宿舍交了发现过了。
STL里居然有全排列… next_permutation 和 prev_permutation。

===
仔细想想有些题还是可以做的，并不是不会算法，而是想不到。另外数学太烂了。

大二，作业没大一多了，更加觉得时间不够用。平时训练做题效率很低。还有好多想学的东西呢。

Greenmoon55′s Blog

Just another WordPress weblog

Category Archives: Programming