当前位置：网站首页>Code source daily question div1 (701-707)

Code source daily question div1 (701-707)

2022-04-23 09:40:00 【In vain】

Code source daily question div1 (701-707)

Drawing a picture

[Link]( Drawing a picture - subject - Daimayuan Online Judge)

Ideas

  • Reverse order simulation

    It is found that we must have some operations that smear a square, and other operations will not touch the square again （ At least the square painted in the last step must be like this ）.

    So we can think backwards , Find the blocks of operations mentioned above , Paint them , And make a mark , Next, these marked can be painted with anything , Because the last operation will be overwritten , So if there is a solution , You can keep the marking machine , Overlay the whole picture , The final solution is to reverse what we recorded .

    If you find that a point is not marked , It means there is no solution .

Attach a link to the original question , The source code can't pass .

[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;
}

Number substitution

[Link]( Number substitution - subject - Daimayuan Online Judge)

Ideas

  • And check and maintain

If the complexity of each traversal is too high . Because it's for the same number of operations , That is, the operation of the set , We can use and query sets to maintain （ Select the set to represent the element ）, Record what number each location is , Where is each number , that will do .

For a newly added number , If it appears in the front, merge it directly into the front , Otherwise, initialize the position of this number in .

For the to be modified x x x change y y y, If y y y There has been a direct x x x The representative elements of are merged into y y y On , take x x x Set to nonexistent , If y y y If it doesn't appear, it will y y y Set as x x x The location of , take x x x Change the number of positions to y y y, Set up x x x If it doesn't exist .

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;
}
  • Reverse order simulation

Because each number may change many times , So let's simulate it backwards , f [ y ] : y change become What Well f[y]:y Into what f[y]:y change become What Well , For insert operation, if f [ x ] ! = 0 f[x]!=0 f[x]!=0 Let's just insert f [ x ] f[x] f[x] that will do , For change operations , If f [ y ] = = 0 f[y]==0 f[y]==0 Represents the back y y y Will not change , f [ x ] = y f[x]=y f[x]=y that will do , If f [ y ] ! = 0 f[y]!=0 f[y]!=0 Represents the back f [ y ] f[y] f[y] Changed f [ x ] = f [ y ] f[x]=f[y] f[x]=f[y] that will do （ The current operation is affected later ）, There is also a sense of path compression , Finally, output in positive order .

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;
}

game

[Link]( game - subject - Daimayuan Online Judge)

Ideas

  • game

    First of all, if n , m n,m n,m All less than 2 k 2k 2k Then the first person in the middle must win , Otherwise n , m n,m n,m The first winner in odd numbers , The first person left to lose .

    Specific proof does not understand , Take time to see .

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;
}

Appropriate number pair （ Data plus ）

[Link]( Appropriate number pair （ Data plus ） - subject - Daimayuan Online Judge)

Ideas

  • Decomposing prime factor

​ Decomposing each number into prime factors is called x 1 p 1 x 2 p 2 . . . x k p k x_1^{p_1}x_2^{p^2}...x_k^{p_k} x1p1​​x2p2​...xkpk​​, If we let two numbers a l × a r = x k a_l\times a_r=x^k al​×ar​=xk, Then the power of each of their prime factors must be k k k Multiple , So let's first power m o d   k mod\ k mod k, Greater than k k k It doesn't work .

​ So we traverse from front to back for i i i We find the power of each prime factor about k k k The complement of , Find the corresponding number to be checked , Determine whether this number exists .

​ Decompose each into prime factors , The simple way is $\sqrt n $ Of , We can find the prime factor of each number while sifting prime numbers , Trade space for time , Optimize the constant again, regardless of 2 2 2 Multiple , It will be much faster .

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 - subject - Daimayuan Online Judge)

Ideas

  • simulation , greedy

​ First, deal with all the pieces that are not dyed correctly , Let's look at every painter , If the color that the artist wants to paint is wrong, we can directly paint it to the corresponding position , If it doesn't exist, let's judge whether the color is right or whether a color is painted to the corresponding position in front , We just apply it to that position , In this way, the operation at this later position will cover it .

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;
}

Prime interval

Link

Ideas

  • The prefix and , Two points

​ Find the minimum length , Obviously, if the length is l e n len len accord with , that l e n + 1 len+1 len+1 Must also meet , So direct dichotomy , Judge whether the current answer is valid , To determine the answer, directly enumerate each starting point to determine whether there is a range after the current starting point ≥ k \ge k ≥k Just a prime number .

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;
}

The longest interesting subsequence

[Link]( The longest interesting subsequence - subject - Daimayuan Online Judge)

Ideas

  • d p dp dp

​ Find the longest subsequence , We follow the practice of the longest ascending subsequence , set up f [ i ] : With a i junction tail Of most Long Yes boring Son order Column f[i]: With a_i The longest interesting subsequence at the end f[i]: With ai​ junction tail Of most Long Yes boring Son order Column , The only difference is that the conditions of transfer are different , The idea of violence is that we all from the front a i & a j ! = 0 a_i\&a_j!=0 ai​&aj​!=0 Transfer your point , This is a O ( n 2 ) O(n^2) O(n2) Complexity , Change the angle , The position we can transfer must be binary and one of the binary of the current point is 1 1 1, So we can directly enumerate which bit is transferred from the binary , For a certain person, we only need to record the longest interesting series that this person has , So the complexity is reduced .

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;
}

版权声明
本文为[In vain]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204230936088162.html

边栏推荐

猜你喜欢

随机推荐