A - Crossword Answers

比较麻烦的一道模拟题。

我写的比较麻烦，应该有更简洁的写法

#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;

const int MAXN = 15;
int a[MAXN][MAXN], n, m, id;
char s[MAXN][MAXN], str[MAXN];

inline bool judge(char x) { return 'A' <= x && x <= 'Z' || 'a' <= x && x <= 'z'; }

int main()
{
    int kase = 0;
    while(~scanf("%d", &n) && n)
    {
        if(kase) puts("");
        memset(a, 0, sizeof(a));
        printf("puzzle #%d:
", ++kase);
        
        id = 0;
        scanf("%d", &m);
        _for(i, 1, n) scanf("%s", s[i] + 1);
        _for(i, 1, n)
            _for(j, 1, m)
            {
                if(s[i][j] == '*') { a[i][j] = -1; continue; };
                if(!judge(s[i-1][j]) || !judge(s[i][j-1])) a[i][j] = ++id;
            }
        
        puts("Across");
        _for(i, 1, n)
        {
            id = 0;
            _for(j, 1, m)
            {
                if(a[i][j] == -1)
                {
                    if(id != 0) printf("%3d.%s
", a[i][j-id], str);
                    id = 0;
                    memset(str, 0, sizeof(str));
                }
                else str[id++] = s[i][j];
                
                if(j == m && id)
                {
                    printf("%3d.%s
", a[i][j-id+1], str);
                    memset(str, 0, sizeof(str));
                }
            }
        }
        
        string word;
        vector<pair<int, string> > words;
        puts("Down");
        _for(j, 1, m)
        {
            id = 0;
            _for(i, 1, n)
            {
                if(a[i][j] == -1)
                {
                    if(id != 0) words.push_back(make_pair(a[i-id][j], word));
                    id = 0;
                    word = "";
                }
                else word += s[i][j], id++;
                
                if(i == n && id)
                {
                    words.push_back(make_pair(a[i-id+1][j], word));
                    word = "";
                }
            }
        }
        sort(words.begin(), words.end());
        REP(i, 0, words.size())
        {
            printf("%3d.", words[i].first);
            cout << words[i].second << endl;
        }
    }
    
    return 0;
}

D - Optimal Symmetric Paths

一开始直接暴搜

然后突然看到方案数模1000000009，突然醒悟（没认真看题浪费了好多时间）

那么再想想了想，这不就是很裸的动规吗，类似数字三角形

只不过加了个对称，统计方案而已

唯一也要想的地方就是推一下对称的公式

然后我粗心大意推反了……

下标从1开始的话

(i, j)的对称点是(n - j + 1, n - i + 1)

然而我推成了(n - i + 1, n - j + 1)

卡了好久好久，一直WA，就因为这个……

还是太弱。

#include<bits/stdc++.h>
#define add(a, b) a = (a + b) % mod
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;

const int MAXN = 100 + 10;
const int mod = 1000000009;
int a[MAXN][MAXN], n;
int f[MAXN][MAXN][2];

inline int val(int i, int j) 
{ 
    if(i + j == n + 1) return a[i][j];
    return a[i][j] + a[n+1-i][n+1-j]; 
}

int main()
{
    while(~scanf("%d", &n) && n)
    {
        _for(i, 1, n)
            _for(j, 1, n)
                scanf("%d", &a[i][j]);
                
        memset(f, 0, sizeof(f));
        _for(i, 1, n) f[0][i][0] = f[i][0][0] = 1e8;
        
        f[1][1][0] = val(1, 1), f[1][1][1] = 1;
        _for(i, 1, n)
            _for(j, 1, n)
            {
                if(i + j > n + 1 || i == 1 && j == 1) continue;
                f[i][j][0] = val(i, j) + min(f[i-1][j][0], f[i][j-1][0]);
                
                if(f[i-1][j][0] < f[i][j-1][0]) add(f[i][j][1], f[i-1][j][1]);
                else if(f[i-1][j][0] > f[i][j-1][0]) add(f[i][j][1], f[i][j-1][1]);
                else add(f[i][j][1], (f[i][j-1][1] + f[i-1][j][1]) % mod);
            }
        
        int mint = 1e9, ans = 0;
        _for(i, 1, n)
        {
            int j = n + 1 - i;    
            if(mint > f[i][j][0])
            {
                mint = f[i][j][0];
                ans = f[i][j][1];
            }
            else if(mint == f[i][j][0])
                add(ans, f[i][j][1]);
        }
        
        printf("%d
", mint, ans);
    }
    
    return 0;
}

待补……