头像

小小蒟蒻


访客:4058

离线:29分钟前


活动打卡代码 AcWing 116. 飞行员兄弟

小小蒟蒻
11小时前
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
PII nil = {-1, -1};  // 为矩阵增加的结束位置
char g[4][4];
vector<PII> ans, pos;

void turn(int x, int y) {
    for(int i = 0; i < 4; i++) {
        g[x][i] == '+' ? g[x][i] = '-' : g[x][i] = '+';
        g[i][y] == '+' ? g[i][y] = '-' : g[i][y] = '+';
    }
    g[x][y] == '+' ? g[x][y] = '-' : g[x][y] = '+';
}

void print(int claim) {
    if(claim) {
        cout << ans.size() << endl;
        for(int i = 0; i < ans.size(); i++) 
            cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl;
    }
}

void dfs(int u) {
    if(pos[u] == nil) {
        int claim = 1;
        for(int i = 0; i < 16; i++) {
                if(g[i / 4][i % 4] == '+') {    
                    claim = 0;
                    break;
                }
            if(!claim) break;
        }
        print(claim);
        return;
    }

    dfs(u + 1);

    int x = pos[u].first, y = pos[u].second;  
    turn(x, y), ans.push_back(pos[u]);
    dfs(u + 1);
    turn(x, y), ans.pop_back();
}

int main() {
    for(int i = 0; i <  4; i++) cin >> g[i];
    for(int i = 0; i < 16; i++) pos.push_back({i / 4, i % 4});
    pos.push_back({-1, -1});
    dfs(0);
    return 0;
}



小小蒟蒻
17小时前

题目如题

微信图片_20200711235856.png
微信图片_20200711235944.png


C++ 代码

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
PII nil = {-1, -1};  // 为矩阵增加的结束位置
char g[4][4];
vector<PII> ans, pos;

void turn(int x, int y) {
    for(int i = 0; i < 4; i++) {
        g[x][i] == '+' ? g[x][i] = '-' : g[x][i] = '+';
        g[i][y] == '+' ? g[i][y] = '-' : g[i][y] = '+';
    }
    g[x][y] == '+' ? g[x][y] = '-' : g[x][y] = '+';
}

void print(int claim) {
    if(claim) {
        cout << ans.size() << endl;
        for(int i = 0; i < ans.size(); i++) 
            cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl;
    }
}

void dfs(int u) {
    if(pos[u] == nil) {
        int claim = 1;
        for(int i = 0; i < 16; i++) {
            if(g[i / 4][i % 4] == '+') {    
                claim = 0;
                break;
            }
            if(!claim) break;
        }
        print(claim);
        return;
    }

    dfs(u + 1);

    int x = pos[u].first, y = pos[u].second;
    // 给我一个空栈,我还你一个空栈,充满正确答案的栈,如此美好却是一瞬间呀~!
    turn(x, y), ans.push_back(pos[u]);
    dfs(u + 1);
    turn(x, y), ans.pop_back(); 
}

int main() {
    for(int i = 0; i <  4; i++) cin >> g[i];
    for(int i = 0; i < 16; i++) pos.push_back({i / 4, i % 4});
    pos.push_back(nil);
    dfs(0);
    return 0;
}




题目如题

C++ 代码

#include <iostream>
using namespace std;
const int N = 1e5 + 5;
pair<string, int> a[N];
int n, m;

// 计算val的第b位的值,通过n扇门后的攻击值
int calc(int b, int v) {
    for(int i = 0; i < n; i++) {
        string s = a[i].first; // 取位操作符
        int t = a[i].second >> b & 1; // 取攻击值的第i位
        // 根据提供的位操作对攻击值的第i位进行相应的操作
        if(s == "AND") v &= t;
        else if(s == "OR") v |= t;
        else v ^= t;
    }
    return v;
}

int dfs(int val, int ans, int k) {
    if(k < 0) return ans;
    int t = val | 1 << k;
    int x = calc(k, 0);
    int y = calc(k, 1);
    int u = ans | x << k;
    int v = ans | y << k;
    if(t > m || u >= v) ans = u;
    else val = t, ans = v;
    ans = dfs(val, k - 1, ans);
} 

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) // 初始化 
        cin >> a[i].first >> a[i].second;
    int ans = 0, val = 0; // 通过n扇门后的攻击值,初始攻击值
    cout << dfs(val, ans, 29);
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1e5 + 5;
pair<string, int> a[N];
int n, m;

// 计算val的第b位的值,通过n扇门后的攻击值
int calc(int b, int v) {
    for(int i = 0; i < n; i++) {
        string s = a[i].first; // 取位操作符
        int t = a[i].second >> b & 1; // 取攻击值的第i位
        // 根据提供的位操作对攻击值的第i位进行相应的操作
        if(s == "AND") v &= t;
        else if(s == "OR") v |= t;
        else v ^= t;
    }
    return v;
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) // 初始化 
        cin >> a[i].first >> a[i].second;

    int ans = 0, val = 0; // 通过n扇门后的攻击值,初始攻击值
    for(int i = 29; i >= 0; i--) {
        int x = calc(i, 0);   // 在val第i位填0,通过n扇门后该位的值
        int y = calc(i, 1);   // 在val第i位填1,通过n扇门后该位的值
        int t = val | 1 << i; // val的第i位填1的结果
        int u = ans | x << i; // 在val第i位填0,可能要累积到ans中的攻击值
        int v = ans | y << i; // 在val第i位填1,可能要累积到ans中的攻击值
        // val的第i位填1导致val不在[1,m]内
        // 或者在val第i位填0比填1导致累计结果的值更大
        if(t > m || u >= v) ans = u; // 在val第i位填0,累计到答案中
        else val = t, ans = v; // 否则,在val第i位填1,累计到答案中
    }
    cout << ans;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla


新鲜事 原文

学校没有哪个老师会算法。信息老师卖课好多年。除了教excel和word,其他一概不教。问了好久才告诉我,学业为重。


新鲜事 原文

蒟蒻的自娱自乐。文件还真可以读写啊。我不怕被嘲笑,我就是一个蒟蒻。 #include <iostream> #include <fstream> using namespace std; char g[N][N]; int n; int main() { ifstream srcFile("input.txt",ios::in); //以文本模式打开in.txt备读 if(!srcFile) { //打开失败 cout << "error opening source file." << endl; return 0; } ofstream destFile("output.txt",ios::out); //以文本模式打开out.txt备写 if(!destFile) { srcFile.close(); //程序结束前不能忘记关闭以前打开过的文件 cout << "error opening destination file." << endl; return 0; } // 从文件input.txt里读取一个数字和一个二维字符数组 int lines = 0; for(int i = 0; srcFile; i++) { if(!i) srcFile >> n; else srcFile >> g[i - 1]; lines = i; } // 测试数据时,查看文本的行数,n的值,字符数组 cout << lines << endl; cout << n << endl; for(int i = 0; i < 5; i++) cout << g[i] << endl; // 向output.txt文件里写入一个数字和一个二维字符数组 for(int i = 0;i < lines; i++) { if(!i) destFile << n << endl; else destFile << g[i - 1] << endl; } destFile.close(); srcFile.close(); return 0; } 好开心,将来再也不在黑框框里面输测试数据了。


新鲜事 原文

Y总说要很久的,一开始不信。冒进死记,遇到陌生问题就死机。。。



题目如题

s1.png
s2.png


#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
char g[N][N], t[N][N];
int n;

void turn(int x, int y) {
    int dx[] = { 0, 0, 0, -1, 1 };
    int dy[] = { 0, -1, 1, 0, 0 };
    for(int i = 0; i < 5; i++) {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || a > 4 || b < 0 || b > 4) continue;
        g[a][b] = !(g[a][b] - '0') + '0';
    }
}

// 按行递归,一开始我搞的是个啥嘛。按列递归去了。
int check(int u, int& s) {
    if(u == 4) {
        int claim = 1;
        for(int j = 0; j < 5; j++)
            if(g[u][j] == '0') {
                claim = 0;
                break;
            }
        return claim;
    }

    for(int j = 0; j < 5; j++)
        // 看第u行j列开关的状态,决定第u + 1行j列开关的操作
        if(g[u][j] == '0')  
            s++, turn(u + 1, j);

    check(u + 1, s);
}

int calc() {
    int ans = 1e9;
    // 第0行一共有32种按键方案,所有解的产生都是因为32种方案导致
    for(int i = 0; i < 1 << 5; i++) {
        int res = 0;
        memcpy(t, g, sizeof g);
        // 按每种方案对应的数值的二进制按下第0排对应的开关
        for(int j = 0; j < 5; j++)
            if(i >> j & 1)
                res++, turn(0, j); 
        // 打开开关的过程以及检查一个方案是否有解用递归解决
        if(check(0, res)) ans = min(ans, res);
        memcpy(g, t, sizeof t);       
    }

    if(ans > 6) return -1;
    return ans;
}

int main() {
    cin >> n;
    while(n--) {
        for(int i = 0; i < 5; i++) cin >> g[i];
        cout << calc() << endl;
    }
    return 0;
}

算法1

(暴力枚举) $O(n^3)$

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
char g[N][N], t[N][N];
int n;

void turn(int x, int y) {
    int dx[] = { 0, 0, 0, -1, 1 };
    int dy[] = { 0, -1, 1, 0, 0 };
    for(int i = 0; i < 5; i++) {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || a > 4 || b < 0 || b > 4) continue;
        g[a][b] = '0' + !(g[a][b] - '0');
    }
}

int calc() {
    int ans = 1e9;
    // 一共有32种按键方案
    for(int i = 0; i < 1 << 5; i++) {
        int res = 0;
        memcpy(t, g, sizeof g);
        // 按每种方案对应的数值的二进制按下第0排对应的开关
        for(int j = 0; j < 5; j++)
            if(i >> j & 1)
                res++, turn(0, j); 
        // 从第0排开始直到第3排,遍历每一排的开关。
        // 如果是关闭的,才对下一排正下方的开关进行按键操作
        for(int k = 0; k < 4; k++)
            for(int j = 0; j < 5; j++)
                if(g[k][j] == '0')
                   res++, turn(k + 1, j);
        // 检查最后一排的开关是不是全部打开
        // 最后一排的开关全部打开,最初的状态有解
        int claim = 1;
        for(int j = 0; j < 5; j++)
            if(g[4][j] == '0') {
                claim = 0;
                break;
            }
        // 有解求最小解,无解什么都不做
        if(claim) ans = min(ans, res); 
        memcpy(g, t, sizeof t);       
    }
    if(ans > 6) return -1;
    return ans;
}

int main() {
    cin >> n;
    while(n--) {
        for(int i = 0; i < 5; i++) cin >> g[i];
        cout << calc() << endl;
    }
    return 0;
}



新鲜事 原文

五塔五盘的汉诺塔,最少移动次数是不是13次?蒟蒻无知。推广后的递推公式是什么样的?


新鲜事 原文

蒟蒻,原来是魔芋呀。hh



题目如题

h1.png
h2.png
h3.png
h4.png
h5.png
h.png

三个塔的情况下:把最下面的盘子上面的n – 1个盘子当做一个整体。最终目的是要把n – 1个盘子放到
Y塔上临时周转。不然,放到Z塔上就得不到最小次数的移动情况。假如n -  1个盘子移动到Y塔上用了a次
X塔上的最后一个最大的盘子可以直接从X移动到Z上。这是一次移动。把n - 1个盘子移动到Z塔又得用
a次移动才办得到。所以,最少的移动次数为:2 * a + 1 次移动。

四个塔就是先把X塔上的盘子分成两部分。前 i 个盘子和后n - i 个盘子。移动前 i 个盘子时,有4个塔可以
利用。因为,下面的第 n - i 个盘子比  i 个盘子中的任意一个都大。当前 i 个盘子放定以后。同样的原因
导致后n -  i 个盘子不能放到那 i 个盘子所在的塔上。所以,n - i 个盘子的移动只有三个塔可以利用了。
显然,下面的 n - i 个盘子的移动最少次数是已经讨论过的三塔情况。假设,前面 i 个盘子的移动周转之用
的塔上 的最少次数为 b,那么一共最少移动次数为:2 * b + (2 * a + 1) 
即递推公式:f[n] = min{ 2 * f[ i ] + d[ n – i ] }  (  1 <=  i  < n  )

算法1 Y总的递推实现

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 15, M = 12;  
int d[N], f[N];

int main() {
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for(int i = 1; i <= M; i++) 
        d[i] = d[i - 1] * 2 + 1;

    for(int i = 1; i <= M; i++)
        for(int j = 0; j < i; j++)
            f[i] = min(f[i], f[j] * 2 + d[i - j]);
    for(int i = 1; i <= M; i++) cout << f[i] << endl;
    return 0;
} 

算法2 抄的网上的递归实现

C++ 代码

void move(int& s, char from, char to) {
    s++;
    cout << from << " -> " << to << endl;
}

void three(int u, int& s, char a, char b, char c) {
    if(u == 1) move(s, a, c);
    else{
        three(u - 1, s, a, c, b);
        move(s, a, c);
        three(u - 1, s, b, a, c);
    }
}

void four(int u, int& s, char a, char b, char c, char d) {
    if(u == 1) move(s, a, d);
    else {
        int k = u >> 1;
        four(u - k, s, a, c, d, b);
        three(k, s, a, c, d);
        four(u - k, s, b, a, c, d);
    }
}

// 开始盘子总数为奇数,输出是那么回事。总数是偶数的情况下,一声不吭。。。。
void five(int u, int& s, char a, char b, char c, char d, char e) {
    if(u == 1) move(s, a, e);
    else {
        int k = 0;
        if(u >> 1 & 1) k = u / 2 + 1;
        else k = u / 2;

        five(u - k, s, a, c, d, e, b);
        four(k, s, a, c, d, e);
        five(u - k, s, b, a, c, d, e);
    }
}

推广如何实现?