开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 代码源每日一题 div1 (701-707) -> 正文阅读

[数据结构与算法]代码源每日一题 div1 (701-707)

代码源每日一题 div1 (701-707)

画画

[Link](画画 - 题目 - Daimayuan Online Judge)

思路

倒序模拟

发现我们一定有一些操作涂抹了某个正方形后其它的操作不会再碰这个正方形了（最起码最后一步涂的正方形一定是这样的）。

因此我们可以考虑倒着考虑，找到上面说的那些操作的块，将他们涂上，然后打个标记，接下来这些打标记的涂什么都可以，因为最后会被上一次的操作覆盖掉，所以如果有解，就可以不断的打标机，将整个图覆盖，最后方案就是将我们记录的倒过来即可。

如果发现某个点没打标记，就代表无解了。

附一个原题链接，代码源上过不了。

[Link](Problem - D - Codeforces)

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1010, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int g[N][N];
vector<array<int, 3>> res;

void dfs(int x, int y) {
    if (x < 1 || x > n - 1 || y < 1 || y > m - 1) return ;
    
    int tag = 0;
    for (int i = x; i <= x + 1; i ++)
        for (int j = y; j <= y + 1; j ++)
            if (g[i][j]) {
                if (tag && tag != g[i][j]) return ;
                else if (!tag) tag = g[i][j];
            }

    if (tag) {
        res.push_back({x, y, tag});
        for (int i = x; i <= x + 1; i ++)
            for (int j = y; j <= y + 1; j ++)
                g[i][j] = 0;
        for (int i = x - 1; i <= x + 1; i ++) 
            for (int j = y - 1; j <= y + 1; j ++)  
                dfs(i, j);
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            cin >> g[i][j];

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            if (g[i][j])
                dfs(i, j);
    
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            if (g[i][j]) {
                cout << -1 << '\n';
                return 0;
            }
    
    reverse(res.begin(), res.end());
    cout << res.size() << '\n';
    for (auto t : res)
        cout << t[0] << ' ' << t[1] << ' ' << t[2] << '\n';
    return 0;
}

数字替换

[Link](数字替换 - 题目 - Daimayuan Online Judge)

思路

并查集维护

如果每次从头到尾遍历修改复杂度太高。因为是对于一个相同数的操作，也就是对于集合的操作，我们可以用并查集来维护（选取集合代表元素），记录每个位置是什么数，每个数在哪个位置，即可。

对于一个新加的数，如果前面出现过就直接将其合并到前面，否则就初始化这个数在的位置。

对于要修改的 $x$ 变 $y$ ，如果 $y$ 出现过直接将 $x$ 的代表元素合并到 $y$ 上，将 $x$ 置为不存在，如果 $y$ 没出现过那就将 $y$ 置为 $x$ 的位置，将 $x$ 位置的数改为 $y$ ，置 $x$ 不存在即可。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 5e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
	e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
int f[N], vis[N], num[N];
int find(int x) {
	return x == f[x] ? x : f[x] = find(f[x]);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int T; cin >> T;
	for (int i = 1; i <= T; i ++) {
		int op; cin >> op;
		if (op == 1) {
			int x; cin >> x;
			a[++n] = i, f[i] = i, vis[i] = x;
			if (num[x]) 				f[i] = num[x];			
			else num[x] = i;
		}
		else {
			int x, y; cin >> x >> y;
			if (x != y && num[x]) {
				if (num[y]) {
				f[num[x]] = num[y];
				num[x] = 0;
			}
			else {
				num[y] = num[x];
				vis[num[x]] = y;
				num[x] = 0;
			}
			}
		}
	}
	for (int i = 1; i <= n; i ++) cout << vis[find(a[i])] << ' ';
	cout << endl;
	return 0;
}

倒序模拟

因为每个数可能会变多次，所以我们倒着来模拟， $f [y] : y 变成什么$ ，对于插入操作如果 $f [x]! = 0$ 我们直接插入 $f [x]$ 即可，对于改变操作，如果 $f [y] = = 0$ 代表后面 $y$ 不会改变， $f [x] = y$ 即可，如果 $f [y]! = 0$ 代表后面 $f [y]$ 变了 $f [x] = f [y]$ 即可（当前操作被后面影响了），也有点路径压缩的感觉，最后正序输出即可。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 5e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
	e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N][3];
vector<int> ve;
int f[N];
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i][0];
		if (a[i][0] == 1) cin >> a[i][1];
		else cin >> a[i][1] >> a[i][2];
	}

	for (int i = n; i; i --) {
		if (a[i][0] == 1) {
			if (!f[a[i][1]]) ve.push_back(a[i][1]);
			else ve.push_back(f[a[i][1]]);
		}
		else {
			if (!f[a[i][2]]) f[a[i][1]] = a[i][2];
			else 		     f[a[i][1]] = f[a[i][2]];
		}
	} 
	
	reverse(ve.begin(), ve.end());
	for (auto x : ve) cout << x << ' ';
	cout << endl;
	return 0;
}

游戏

[Link](游戏 - 题目 - Daimayuan Online Judge)

思路

博弈

首先如果 $n, m$ 均小于 $2 k$ 则第一个人放中间一定必胜，否则的话 $n, m$ 均为奇数第一个人胜，剩下第一个人败。

具体证明不懂，抽时间再看。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m >> k;
    if (n < 2 * k && m < 2 * k) cout << "Alice\n";
    else {
        if (n & 1 && m & 1) cout << "Alice\n";
        else cout << "Bob\n";
    }
    return 0;
}

合适数对（数据加强版）

[Link](合适数对（数据加强版） - 题目 - Daimayuan Online Judge)

思路

分解质因数

? 将每个数分解质因数会称为 $x_1^{p_1}x_2^{p^2}...x_k^{p_k}$ ，我们如果让两个数 $a_l\times a_r=x^k$ ，那么他们的每一个质因子的次幂一定是 $k$ 的倍数，因此先将次幂 $mod\ k$ ，大于 $k$ 的部分没有用。

? 因此我们从前往后遍历对于 $i$ 我们找到它的每个质因子次幂关于 $k$ 的补数，将它要查的对应的数找到，判断这个数是否存在。

? 将每个是分解质因子，朴素的做法是$\sqrt n $的，我们可在筛质数的时候顺便求出每个数的质因子，用空间换一下时间，再优化一下常数不考虑 $2$ 的倍数，这样会快很多。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e6 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int primes[N * 10], cnt;
bool st[N * 10];
int mn[N * 10];
void get(int x) {
    primes[cnt ++] = 2;
    mn[2] = 2;
    for (int i = 3; i <= x; i += 2) {
        if (!st[i]) primes[cnt ++] = i, mn[i] = i;
        for (int j = 0; primes[j] <= x / i; j ++) {
            st[primes[j] * i] = true;
            mn[primes[j] * i] = primes[j];
            if (i % primes[j] == 0) break;
        }   
    }
}
LL qmi(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
int mp[N * 10];
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    get(10000000);
    cin >> n >> k;
    LL res = 0;
    for (int i = 1; i <= n; i ++) {
        int x; cin >> x;
        LL p = 1, q = 1;
        while (x != 1) {
            int t = x % 2 ? mn[x] : 2;
            int cnt = 0;
            while (x % t == 0) {
                cnt ++, cnt %= k;
                x /= t;
            }      
            p *= qmi(t, cnt);
            if (cnt) q *= qmi(t, k - cnt);
            if (q < 0 || q > 10000000) q = 0;
        }
    
        res += mp[q];
        mp[p] ++;
    }

    cout << res << '\n';
    return 0;
}

Fence Painting

[Link](Fence Painting - 题目 - Daimayuan Online Judge)

思路

模拟，贪心

? 首先处理出来所有染色不对的块，倒来看每个画家，如果当前这个画家要涂的色存在不对的我们直接涂到对应位置，如果不存在我们判断一下这个颜色是否本来就是对的或者是否前面有某个颜色涂到了对应的位置，我们直接将它涂到那个位置即可，这样后面这个位置的操作就会将其覆盖掉。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N], c[N], b[N], res[N];
stack<int> q[N];
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T -- ) {
        cin >> n >> m;
        map<int, int> mp;
        int cnt = 0;
        bool ok = true;
        for (int i = 1; i <= n; i ++) cin >> a[i];
        for (int i = 1; i <= n; i ++) {
            cin >> b[i];
            if (b[i] != a[i]) {
                ok = false;
                cnt ++;
                q[b[i]].push(i);
            }
            else mp[a[i]] = i;
        }
        for (int i = 1; i <= m; i ++) cin >> c[i];

        if (ok) {
            ok = false;
            int pos = 0;
            for (int i = 1; i <= n; i ++)
                if (a[i] == c[m]) {
                    ok = true;
                    pos = i;
                    break;
                }
            if (ok) {
                cout << "YES\n";
                for (int i = 1; i <= m; i ++)
                    cout << pos << ' ';
                cout << '\n';
            }
            else cout << "NO\n";
        }
        else {
            ok = true;
            int pre = -1;
            for (int i = m; i; i --) {
                if (mp.find(c[i]) == mp.end() && !q[c[i]].size() && pre == -1) {
                    ok = false;
                    break;
                }
                else {
                    if (pre == -1 && !q[c[i]].size()) pre = mp[c[i]];
                    if (!q[c[i]].size()) res[i] = pre;
                    else {
                        auto t = q[c[i]].top();
                        if (q[c[i]].size()) q[c[i]].pop(), cnt --;
                        res[i] = t;
                        pre = t; 
                    }
                }
            }
            for (int i = 1; i <= n; i ++)
                while (q[b[i]].size()) q[b[i]].pop();

            if (cnt > 0) cout << "NO\n";
            else {
                cout << "YES\n";
                for (int i = 1; i <= m; i ++)
                    cout << res[i] << ' ';
                cout << '\n';
            }
            }
        
    }
    return 0;
}

质数区间

Link

思路

前缀和，二分

? 求最小长度，很显然如果长度为 $l e n$ 符合，那么 $l e n + 1$ 一定也符合，因此直接二分答案，判断当前答案是否成立即可，判断答案就直接枚举每个起点判断当前起点往后的这个区间是否有 $\ge k$ 个质数即可。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e6 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int primes[N], cnt;
bool st[N];
void get(int x) {
    st[1] = true;
    for (int i = 2; i <= x; i ++) {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] <= x / i; j ++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
int tr[N];
void add(int x) {
    for (; x <= 1000000; x += (x & -x)) tr[x] ++;
}
int sum(int x) {
    int res = 0;
    for (; x; x -= (x & -x)) res += tr[x];
    return res;
}
int L, R; 
bool check(int len) {
    for (int i = L; i + len - 1 <= R; i ++)
        if (sum(i + len - 1) - sum(i - 1) < k) 
            return false;
    return true;
} 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    get(1000000);
    cin >> L >> R >> k;
    for (int i = L; i <= R; i ++)
        if (!st[i])
            add(i);

    int l = 1, r = R - L + 1;
    if (sum(R) - sum(L - 1) < k) {
        cout << -1 << '\n';
        return 0;
    }     
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1; 
    }
    cout << r << '\n';
    return 0;
}

最长有趣子序列

[Link](最长有趣子序列 - 题目 - Daimayuan Online Judge)

思路

$d p$

? 求最长什么子序列，我们仿照最长上升子序列的做法，设 $f[i]:以a_i结尾的最长有趣子序列$ ，唯一不同的就是转移的条件不同，暴力的想法是我们从前面所有 $a_i\&a_j!=0$ 的点转移过来，这样是 $O(n^2)$ 的复杂度，换一个角度，我们可以转移过来的位置一定是二进制和当前这个点的二进制有某一位都是 $1$ ，因此我们可以直接枚举从二进制的哪一位转移过来，对于某一位我们只需要记录这一位有的最长有趣系序列即可，这样复杂度就降下来了。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e6 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
int f[N], bit[31];
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    int res = 0;
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= 30; j ++)
            if (a[i] >> j & 1) 
                f[i] = max(f[i], bit[j] + 1);
        res = max(res, f[i]);

        for (int j = 0; j <= 30; j ++)
            if (a[i] >> j & 1)
               bit[j] = max(bit[j], f[i]); 
    }        
    cout << res << '\n';
    return 0;
}