恢复战场的第一站模拟

youhualiuh / 2024-03-01 / 原文

A - 玩数字

思路:原题链接:https://atcoder.jp/contests/abc111/tasks/abc111_b

ABC 中首次亮相三个相同数字的比赛 -》也就是输出三个相同的数,且>=本身输入的(= 代表着输入的数就是三个相同数字的),得到公式(n - 110) / 110即可

Code:

#include<iostream>

using namespace std;

int main() {
    int n; cin >> n;
    int x = (n + 110) / 111;
    cout << x << x << x;
}

B - 玩字母

思路:原题链接:http://poj.org/problem?id=1256

输出从小到大排序的字符串字母明显按照A<a<B<b<....题意简单

Code:

#include<iostream>
#include<string>
#include <algorithm>

using namespace std;

bool cmp(char &a, char &b) {
    if (tolower(a) != tolower(b)) { return tolower(a) < tolower(b); }
    return a < b;
}

void solve() {
    string s; cin >> s;
    sort(s.begin(), s.end(), cmp);
    do {
        cout << s << '\n';
    } while (next_permutation(s.begin(), s.end(), cmp));
}

int main() {
    int t; cin >> t;
    while (t--) {
        solve();
    }
}

Code:DFS

#include<iostream>
#include<string.h>
#include<algorithm>

using namespace std;
char tmp[15], s[15];
bool vis[15];
int n;

bool cmp(char &a, char &b) {
    if (tolower(a) != tolower(b)) return tolower(a) < tolower(b);
    return a < b;
}

void dfs(int step) {
    bool ok[100] = {0};
    if (step == n) {
        tmp[n] = '\0';
        cout << tmp << '\n';
        return ;
    }
    for (int i = 0; i < n; i++) {
        if (!vis[i] && !ok[s[i] - 'A']) {
            vis[i] = 1;
            tmp[step] = s[i];
            ok[s[i] - 'A'] = 1;
            dfs(step + 1);
            vis[i] = 0;
        }
    }
}

int main() {
    int t; cin >> t;
    while (t--) {
        cin >> s; n = strlen(s);
        sort(s, s + n, cmp);
        memset(vis, 0, sizeof(vis));
        dfs(0);
    }
}

C - 玩数组

思路:原题链接:https://codeforces.com/problemset/problem/1669/C

奇数位的值+1 -1 偶数位的值+1 -1使其所有都变成奇数,所以只要统计奇数位的值都是奇数或者偶数偶数位都是奇数或者偶数即可

Code:

#include<iostream>
#include<vector>

using namespace std;

int main() {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        int odd1 = 0, odd2 = 0, even1 = 0, even2 = 0;
        for (int i = 0, x; i < n; i++) {
            cin >> x;
            if (i & 1) {
                if (x & 1) {
                    odd1 = 1;
                }
                else {
                    even1 = 1;
                }
            }
            else {
                if (x & 1) {
                    odd2 = 1;
                }
                else {
                    even2 = 1;
                }
            }
        }
        if (odd1 && even2) {
            cout << "No\n";
        }
        else if (odd2 && even2) {
            cout << "No\n";
        }
        else {
            cout << "Yes\n";
        }
    }
}

D - BFS

思路:bfs原题链接:http://poj.org/problem?id=3278

第一个方法:+1 -1 步数+1 第二个方法*2 步数+1 bfs搜索即可

Code:BFS

#include<iostream>
#include<queue>

using namespace std;
const int N = 1e6;//边界N and 0

struct node {
    int step, count;
};

int start, ed;//start->起点 ed ->end终点
bool vis[N];//位置是否走过

int bfs() {
    node now, x;
    now.step = start, now.count = 0;
    vis[start] = 1;
    queue<node> q;
    q.push(now);
    while (!q.empty()) {
        now = q.front();
        q.pop();
        if (now.step == ed) {
            return now.count;
        }
//第一种
        x.step = now.step + 1;
        x.count = now.count + 1;

        if (x.step <= N && !vis[x.step]) {
            q.push(x); vis[x.step] = 1;
        }
//第二种
        x.step = now.step - 1;
        x.count = now.count + 1;

        if (x.step >= 0 && !vis[x.step]) {
            q.push(x); vis[x.step] = 1;
        }
//第三种
        x.step = now.step * 2;
        x.count = now.count + 1;
        if (x.step <= N && !vis[x.step]) {
            q.push(x); vis[x.step] = 1;
        }
    }
    return 0;
}

int main() {
    cin >> start >> ed;
    cout << bfs();
}

Code:DP

#include<iostream>
#include<math.h>

using namespace std;
const int N = 1e6 + 5;

int dp[N], n, k;

int main() {
    cin >> n >> k;
	for (int i = 0; i <= k; i++)
	{
		dp[i] = abs(i - n);
	}
    //dp[i]->5 4 3 2 1 0 1 2 3 4 5 6 7 8 9 10 11 12 
	for (int i = n + 1; i <= k; i++)
	{
		if (i % 2 == 0)
		{
			dp[i] = min(dp[i], dp[i / 2] + 1);
			dp[i] = min(dp[i], dp[i - 1] + 1);
		}
		else
		{
			dp[i] = min(dp[i], dp[(i-1) / 2] + 2);
			dp[i] = min(dp[i], dp[i - 1] + 1);
			dp[i] = min(dp[i], dp[(i + 1) / 2] + 2);
		}
	}
	cout << dp[k];
}

E - path

思路:原题链接:https://darkbzoj.cc/problem/1647

0是白面 1是黑面选择翻转的时候相邻都会翻转问多少次翻转使得所有的白面向上如果可以输入字典序最小如果不行输出IMPOSSIBLE

1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
->
1)
0 0 0 1
1 0 1 0
1 1 1 0
1 0 0 1
->
2)
0 0 0 0
1 0 0 1
1 1 1 1
1 0 0 1
->
3)
0 0 0 0
0 0 0 1
0 0 1 1
0 0 0 1
->
4)
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
ok我们可以观察到
0 1 1 0
0 0 0 0
0 0 0 0
0 1 1 0
or 
0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0这两个情况可以完成这个操作所以通过搜索来实现

Code:DFS

#include<iostream>

using namespace std;
const int N = 20;
const int inf = 1e9 + 7;

int n, m, a[N][N], ans[N][N], p[N][N], f[N][N], mn = inf;

void dfs(int x) {
    if (x > m) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                p[i][j] = a[i][j];
            }
        }
        for (int i = 1; i <= m; i++) {
            if (f[1][i]) {
                p[1][i] ^= 1, p[2][i] ^= 1;
                p[1][i + 1] ^= 1, p[1][i - 1] ^= 1;
            }
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[i - 1][j] == 1) {
                    f[i][j] = 1; p[i][j] ^= 1; p[i][j + 1] ^= 1;
                    p[i][j - 1] ^= 1; p[i + 1][j] ^= 1; p[i - 1][j] ^= 1;
                }
                else {
                    f[i][j] = 0;
                }
                if (p[i - 1][j]) {
                    return ;
                }
            }
        }
        bool ok = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[i][j]) {
                    ok = 1; break;
                }
            }
        }
        if (!ok) {
            int tot = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (f[i][j]) {
                        tot++;
                    }
                }
            }
            if (tot >= mn) {
                return ;
            }
            mn = tot;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    ans[i][j] = f[i][j];
                }
            }
        }
        return ;
    }
    for (int i = 0; i <= 1; i++) {
        f[1][x] = i;
        dfs(x + 1);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    dfs(1);
    if (mn == inf) {
        cout << "IMPOSSIBLE";
    }
    else {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cout << ans[i][j] << ' ';
            }
            cout << '\n';
        }
    }
}

F - free

思路:原题链接:https://acm.hdu.edu.cn/showproblem.php?pid=1224

自定义旅途路线，1和n+1结点权值为0 剩下结点权值给定有向图，求最长路

学习链接:https://edwardzcn.github.io/post/cd18de84.html主up十分感谢

https://github.com/luojilab/algorithm/blob/master/doc/Graph/Dijkstra/Dijkstra%E7%AE%97%E6%B3%95.md

Code:

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;

struct Edge {
    int u, v, w;
    Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
};

vector<Edge> edges[N];
int dis[N], path[N], num[N], ans[N];
bool vis[N];
int n, m, uu, vv, ww, t;

void init() {
    for (int i = 0; i < N; i++) {
        edges[i].clear();
    }
    memset(vis, false, sizeof(vis));
    memset(dis, -INF, sizeof(dis));
    memset(path, 0, sizeof(path));
    memset(num, 0, sizeof(num));
}

void addEdge(int u, int v, int w) {
    edges[u].push_back(Edge(u, v, w));
}

struct Node {
    int Id, W;
    Node(int _Id, int _W) : Id(_Id), W(_W) {}
    bool operator < (const Node &b) const {
        return W < b.W;
    }
};

void Dijkstra(int s) {
    priority_queue<Node> q;
    q.push(Node(s, 0));
    dis[s] = 0;
    while (!q.empty()) {
        Node now = q.top();
        q.pop();
        int index = now.Id;
        if (dis[index] != now.W) continue;
        for (auto &edge : edges[index]) {
            if (dis[edge.v] < dis[index] + edge.w) {
                dis[edge.v] = dis[index] + edge.w;
                q.push(Node(edge.v, dis[edge.v]));
                path[edge.v] = index;
            }
        }
    }
}

int main() {
    cin >> t;
    for (int T = 1; T <= t; T++) {
        if (T != 1) cout << '\n';
        cin >> n;
        init();
        for (int i = 1; i <= n; i++) {
            cin >> num[i];
        }
        cin >> m;
        for (int i = 1; i <= m; i++) {
            cin >> uu >> vv;
            addEdge(uu, vv, num[uu]);
        }
        Dijkstra(1);
        int cnt = 0, ini = n + 1;
        while (1) {
            ans[cnt++] = ini;
            ini = path[ini];
            if (ini == 1) break;
        }
        ans[cnt] = 1;
        cout << "CASE " << T << "#\n";
        cout << "points : " << dis[n + 1] << '\n';
        cout << "circuit : ";
        for (int i = cnt; i > 0; i--) cout << ans[i] << "->";
        cout << 1 << '\n';
    }
}