about 1 year ago

嘟噜噜... 还有一个月就NOIP了,AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧

简单写点弱鸡题解, 第一是督促一下作业进度,第二呢也可以来熟悉一下输入法。岂不是很妙。


ArcadeManao

关键词:并查集

题目简述

很久很久以前,有一个的网格,其中有一些格子上是可以停留的,有一些是悬空的。

这是一个有重力存在的世界。

有一个可爱的小朋友,他现在在网格的底部(保证底部的每一个格子都是可以停留的),需要到达一个特定的可停留的格子。

现在有两种移动方式:左右移动和上下移动。

左右移动:左右紧挨的两个格子,如果都可以停留,就可以在这两个格子之间自由移动。

上下移动:同一条竖直线上的两个可停留的格子(可以不紧挨)可以互相移动,不过你需要拥有一
把长度至少为两个格子纵坐标之差的绝对值的梯子。

梯子可以重复使用,问从网格底部到达目标点,需要的梯子的最短长度。

算法简述

可以暴力枚举答案,然后用并查集判断

一点点小代码

const int N = 60;
int n, m;
int id[N][N], a[N][N];
int f[N * N];
int x, y;
int get(int a) {
    if (a == f[a]) return a;
    return f[a] = get(f[a]);
}

int join(int a, int b) {
    f[get(a)] = get(b);
}

bool check(int H) {//判断梯子的长度不超过H的时候是否有解 
    REP(i, 1, n * m) f[i] = i;
    REP(i, 1, n) REP(j, 1, m - 1) if (a[i][j] && a[i][j + 1]) join(id[i][j], id[i][j + 1]);
    REP(i, 1, n) REP(j, 1, m) REP(k, 1, min(n - i, H))
        if (a[i][j] && a[i + k][j]) join(id[i][j], id[i + k][j]);//用并查集判断
    return get(id[n][1]) == get(id[x][y]);//如果起点和终点在一个连通块里就可以
}

class ArcadeManao {
    public:
        int shortestLadder(vector<string> level, int X, int Y) {
            x = X, y = Y;
            n = level.size(); m = level[0].size();
            int tot = 0;
            REP(i, 1, n) REP(j, 1, m) id[i][j] = ++tot;
            REP(i, 1, n) REP(j, 1, m) a[i][j] = (level[i - 1][j - 1] == 'X');
            REP(i, 0, n) if (check(i)) return i;//从小到大枚举答案 
     }
};

CountPlacements

关键词:动态规划

算法简述

显然,每个海绵能够接到的水滴一定是连续的一段,所以的思路是从左往右把这些水龙头切成一段又一段,分给各个脸盆(当然也可以落到地面上)。

我们考虑怎样的切割方法是合法的。

首先,以被浪费的水龙头为界,将没有被浪费的水龙头分成了若干块(每一块是连续的一段没有被浪费的水龙头),各块互相独立。每一块被该块内部接水区间紧挨的若干个脸盆瓜分。每一块内部一定存在一个高度最高的脸盆(废话),它不被任何其他脸盆所阻挡,于是正好能够接住个水龙头的。这一块内部的其他脸盆,接到的部分长度都小于等于(废话,总共也就那么长)。而且只要满足以上条件,方案一定能够实现,因为只要确定了那么正好接住个水龙头的最高的脸盆,其余脸盆都可以以阶梯状从中心向两边排出任何你想要的区间。

于是。区间切割分配的方案(也就是要求的方案)合法当且仅当每一个联通块(紧挨即联通)内部都至少存在一个区间长度正好为,且其他的长度均小于等于

一点点小代码

const int N = 610;
int f[N][N][3];
int s[N];
int a[N], n, m;
int A, B, L;
class TheExperiment {
    public:
        int countPlacements(vector<string> intensity, int M, int L, int A, int B) {
            n = 0, m = M;
            REP(i, 0, intensity.size() - 1) REP(j, 0, intensity[i].size() - 1) a[++n] = intensity[i][j] - '0';
            ::A = A, ::B = B;
            ::L = L;
            REP(i, 1, n) s[i] = s[i - 1] + a[i];
            CL(f, 0);
            f[0][0][0] = 1;
            REP(i, 1, n) {
                REP(j, 0, m) {
                    f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][2]) % mo; // 要么是前面也是空的,要么是前面是组好的一段
                    if (j)  {
                        PER(k, i - 1, max(0, i - L +  1)) if (s[i] - s[k] <= B && s[i] - s[k] >= A) // 枚举这一段的长度
                            f[i][j][1] = ((f[i][j][1] + f[k][j - 1][1]) % mo + f[k][j - 1][0]) % mo;//有可能是新的一个连续段

                        PER(k, i - 1, max(0, i - L + 1)) if (s[i] - s[k] <= B && s[i] - s[k] >= A) // 枚举这一段的长度
                            f[i][j][2] = (f[i][j][2] + f[k][j - 1][2]) % mo;//有可能是新的一个连续段

                        if (i >= L && s[i] - s[i - L] >= A &&  s[i] - s[i - L] <= B) { // 这一段长度为L
                            f[i][j][2] = (f[i][j][2] + f[i - L][j - 1][2]) % mo;
                            f[i][j][2] = (f[i][j][2] + f[i - L][j - 1][1]) % mo;
                            f[i][j][2] = (f[i][j][2] + f[i - L][j - 1][0]) % mo;
                        }

                    }
                }
            }
            int ans = 0;
            REP(i, 1, n) ans = (ans + f[i][m][2]) % mo;
            return ans;
        }
};

CharacterBoard

关键词:数学

题目简述

很久很久以前,有一个活泼可爱的小朋友,他拥有一个棋盘,行从上至下以编号,列从左至右以编号。

后来,有一个长者给了他一个长度为​的字符串​,并让小朋友以以下伪代码去填充这个棋盘​。

int cursor = 0;
for (int i = 0; i < 1000000000; i++)   
  for (int j = 0; j < W; j++)    {       
    a[i][j] = s[cursor];        
    cursor = (cursor + 1) % L;    
  }

接着,小朋友在大棋盘中取出一个以为左上角,行数为,列数为的子矩阵。

现在已知取出的子矩阵,而对于那个用于循环节的字符串,连长度都不知道,更别提内容了,只知道只含有小写字母。小朋友想要猜出这个字符串究竟是啥。

于是问你有多少种可能的字符串

算法简述

首先可以考虑枚举字符串长度,然后判一下长度为的时候是否合法并且有多少种不同的方案。发现大多数时候,字符并不会循环出现,那么方案就是.什么时候会在矩阵中出现重复的位置呢,当且仅当两个位置的差正好是的倍数的时候。这样只要暴力枚举会重复的位置,去分解一下,就可以计算出所有可能导致重复的, 因为棋盘的大小有限所以两两位置的差最多只有种。

一点小代码

int w;
LL id(int x, int y) {
    return 1LL * w * x + y; //计算一个元素的位置
}
map<LL, char> S;
set<LL> A;
vector<LL> v[255];  //把所有相同的字符放在一起
int n, m;
void frac(LL x) { //寻找x的所有因子
    if (A.find(x) != A.end()) return; //总共不同的差的数量不会超过100
    for (LL i = 1; i * i <= x; ++i) if (x % i == 0) {
        A.insert(i);
        if (i * i != x) A.insert(x / i);
    }
}
int check(LL x) {//计算S长度为x的时候的合法的S的数量
    static map<LL, char> C; C.clear();
    for (map<LL, char> ::iterator it = S.begin(); it != S.end(); ++it) {
        if (C.find(it -> FR % x) == C.end()) C[it -> FR % x] = it -> SC;
        else if (C[it -> FR % x] != it -> SC) return 0;
    }
    return pow(26, (int)x - (int)C.size());
}

class CharacterBoard {
    public:
        int countGenerators(vector<string> fragment, int W, int i0, int j0) {
            S.clear();
            A.clear();
            w = W;
            n = fragment.size(), m = fragment[0].size();
            REP(i, 0, n - 1) REP(j, 0, m - 1) 
                S[id(i + i0, j + j0)] = fragment[i][j]; 
            int ans = 0;
            if (W >= n * m) 
                ans = 1LL * (pow(26, W - n * m + 1) - 1 + mo) % mo * pow(25, mo - 2) % mo; //先计算不会产生重叠部分的答案

            for (map<LL, char> ::iterator it = S.begin(); it != S.end(); ++it) 
                for (map<LL, char> ::iterator it2 = it; it2 != S.end(); ++it2) {//枚举所有两两重叠的时候可能的S的长度
                    if ((*it) == (*it2)) continue;
                    frac(it2 -> FR - it -> FR);
                }
            for (set<LL> ::iterator it = A.begin(); it != A.end(); ++it) {
                if (*it > W) break;
                int tmp = check(*it);
                ans = (ans + tmp) % mo;
                if ((*it) >= n * m) ans = (ans - pow(26LL, (*it) - n * m) + mo) %mo; //如果长度大于n * m那么就要把之前的计算给减去
            }


            return ans;
        }
};
← SRM 580 弱鸡题解 一些题目 →
 
comments powered by Disqus