Code source daily question div1 (301-307)

Continuous subsequences

[Link]( Continuous subsequences - subject - Daimayuan Online Judge)

Ideas

• $dp$

​ Violent to set $f_i:WithijunctiontailOfmostLongSonorderColumn$, For one $a_i$ We want to see it $f_{a_i-1}$ Whether there is , The existence is connected to the back , Set the maximum length to $mx$, We $dp$ After completing the journey, traverse $f$, For the first $f_i=mx$ The position of must be the smallest in the dictionary . Because the value range is too large, we can't open an array to store , So open a $map$ Just do 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];
map<int, int> f;
int main() {
    
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    int mx = 0;
    for (int i = 1; i <= n; i ++) {
    
        int x; cin >> x;
        f[x] = f[x - 1] + 1;
        mx = max(mx, f[x]);
    }    
    for (auto it : f) 
        if (it.second == mx) {
    
            cout << mx << '\n';
            for (int i = it.first - mx + 1; i <= it.first; i ++)
                cout << i << ' ';
            cout << '\n';
            return 0;
        }
    return 0;
}

Work arrangement

[Link]( Work arrangement - subject - Daimayuan Online Judge)

Ideas

• greedy

​ Sort tasks by time , For each task , If the current time is not enough , If the income of a previous point is less than that of the current point , We will replace that point with the current point , Maintaining the minimum value of the previously selected weight can be done with a priority queue .

The small root heap should be overloaded with a greater than sign .

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;
PII a[N];
int main() {
    
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i].y >> a[i].x;
    sort(a + 1, a + 1 + n,[&](PII a, PII b) {
    
        return a.y < b.y;
    });
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    for (int i = 1; i <= n; i ++) {
    
        if (a[i].y <= 0) continue ;
        if (pq.size() < a[i].y) pq.push(a[i]);
        else if (pq.top().x < a[i].x) {
    
            pq.pop();
            pq.push(a[i]);
        }        
    }
    LL res = 0;
    while (pq.size()) {
    
        res += pq.top().first;
        pq.pop();
    }

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

Trigonometric fruit count

[Link]( Trigonometric fruit count - subject - Daimayuan Online Judge)

Ideas

• Tree form $dp$

​ It is found that when three points have no solution on a path of the tree , Other situations are solved , Because it is not on the same path, there must be an intermediate node connected with these points respectively , Suppose that the edge weights of this point and the other three points are $a,b,c$, be $a+b+b+c>a+c$, Prove that it has nothing to do with the weight path weight .

​ Next, consider how to count , We can divide the scheme in this way to point $u$ Is the number of schemes at the middle point , Such a scheme consists of two parts ：

1. $u$ Choose one of the two different subtrees of , Not $u$ Select one from the subtree of, so it will not form a path
2. $u$ Choose three different subtrees , This will not constitute a path

​ set up $sz[u]:WithubyrootOfSonTreesOfsectionspotCount$, For scheme 1, we require $NotuSonTreessectionspotCount\times {\sum }_{i=1}^n{\sum }_{j=i+1}^{n}sz[i]\times sz[j]$, The later connection can be optimized into $O(n)$, because $(a+b{)}^2=a^2+b^2+2ab\to ab=\frac{(a+b{)}^2-(a^2+b^2)}{2}$, Generalized to $n$ A variable , We can $O(n)$ My request $(a+b{)}^2$ and $a^2+b^2$, Similarly, in scheme 2, we require ${\sum }_{i=1}^{i=n}{\sum }_{j=i+1}^{j=n}{\sum }_{k=j+1}^{k=n}sz[i]\times sz[j]\times sz[k]$, This equation can also be deformed to $O(n)$, So direct one $dfs$ that will do .

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 = 2e5 + 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];
LL sz[N];
LL res;
LL clac1(vector<int>&ve, int u) {
    
    if (ve.size() < 2) return 0;
    LL sum1 = 0, sum2 = 0;
    for (auto v : ve) sum1 += sz[v], sum2 += sz[v] * sz[v];
    return (LL)(n - sz[u]) * (sum1 * sum1 - sum2) / 2;
}
LL clac2(vector<int>&ve) {
    
    if (ve.size() < 3) return 0;
    LL sum1 = 0, sum2 = 0, sum = 0;
    for (auto v : ve) sum += sz[v];
    for (auto v : ve) sum1 += sz[v] * sz[v] * sz[v], sum2 += 3 * sz[v] * sz[v] * (sum - sz[v]);

    return (sum * sum * sum - sum1 - sum2) / 6;
}
void dfs(int u, int fa) {
    
    vector<int> ve;
    sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
    
        int j = e[i];
        if (j == fa) continue ;
        dfs(j, u);
        sz[u] += sz[j];
        ve.push_back(j);
    }
    res += clac1(ve, u);
    res += clac2(ve);
}
int main() {
    
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++) {
    
        int x, y, z; cin >> x >> y >> z;
        add(x, y, z), add(y, x, z);
    }
    dfs(1, -1);
    cout << res << '\n';
    return 0;
} 

• mathematics

​ If the current point $u$ We can get several subtrees by removing them , The problem is to select three trees from these trees, one node for each tree , Let the number of nodes in each tree be $sz[i]$, It's equivalent to asking for ${\sum }_{i=1}^{i=n}{\sum }_{j=i+1}^{j=n}{\sum }_{k=j+1}^{k=n}sz[i]\times sz[j]\times sz[k]$, Optimize this formula , We can enumerate the middle points $j$ For each of these $j$ We are equivalent to seeking $({\sum }_{i=1}^{i=j-1}sz[i])\times sz[j]\times ({\sum }_{k=j+1}^{k=n}sz[k])$, That is, we can enumerate one of the points , Then make sure the increment in front of this point , The following decrement can , In other words, it is equivalent to that we have obtained $u$ This point is the left half of the existing point , The current enumeration is as $j$, What is not enumerated is the right half , So you can $O(n)$ Please .

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];
LL sz[N];
LL res;
void dfs(int u, int fa) {
    
    sz[u] = 1;    
    for (int i = h[u]; ~i; i = ne[i]) {
    
        int j = e[i];
        if (j == fa) continue ;
        dfs(j, u);
        res += (sz[u] - 1) * sz[j] * (n - sz[u] - sz[j]);
        sz[u] += sz[j];
    }
}
int main() {
    
    ios::sync_with_stdio(false), cin.tie(0);
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i < n; i ++) {
    
        int x, y, z; cin >> x >> y >> z;
        add(x, y), add(y, x);
    }
    dfs(1, -1);
    cout << res << '\n';
    return 0;
}

Neat array 2

[Link]( Neat array 2 - subject - Daimayuan Online Judge)

Ideas

• enumeration , number theory

​ First order the original array , If there is a general number greater than or equal to the same, there is no solution .

​ First, if I give you one $k$, How to judge whether it is in harmony with the law , For two numbers $a_i+xk=a_j+yk\to a_i\equiv a_j(modk)$, So you can open a $map$, Count this $n$ Number $modk$ Then iterate over $map$ See if it exists $\ge n/2$ Value .

​ So how to enumerate our $k$ Well , Because we want to make half the number the same , hypothesis $a_i>a_j$ So when $a_i$ Reduce to equal $a_j$ There's no need to reduce when you're , set up $d=a_i-a_j$, We can enumerate $d$ All divisors of , For greater than $d$ It's impossible to make them the same, so there's no need to enumerate , For non $d$ The divisor of $a_i$ It must not be reduced to $a_j$ We don't need to enumerate . Suppose the optimal solution is $k_1$, Then it must be some $a_i$ It's changed to $a_j$ Therefore, it must be possible to enumerate .

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 gcd(int a, int b) {
    
    return b ? gcd(b, a % b) : a;
}
bool check(int x) {
    
    map<int, int> mp;
    for (int i = 1; i <= n; i ++) mp[(a[i] % x + x) % x] ++;
    for (auto it : mp)
        if (it.second >= n / 2) return true;
    return false;
}
int main() {
    
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T -- ) {
    
        cin >> n;
        for (int i = 1; i <= n; i ++) cin >> a[i];
        sort(a + 1, a + 1 + n);
        bool ok = false;
        for(int i = 1; i <= n; i ++) {
    
            int j = i;
            while (j <= n && a[j] == a[i]) j ++;
            if (j - i >= n / 2) {
    
                ok = true;
                break;
            }
            i = j - 1;
        }

        if (ok) {
    
            cout << -1 << '\n';
            continue ;
        }

        int res = 1;
        for (int i = 1; i <= n; i ++)
            for (int j = i + 1; j <= n; j ++) {
    
                int d = abs(a[j] - a[i]);
                for (int k = 1; k <= d / k; k ++) {
    
                    if (d % k == 0) {
    
                        if (check(k)) res = max(res, k);
                        if (check(d / k)) res = max(res, d / k);
                    }
                }
            }

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

Ternary loop

Ideas

• Tree form $dp$

​ Process the longest length in the order and reverse order with each point as the subtree , then $dp$ Determine the relationship between the current point and the parent node , Find the longest length of the current point and add 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 = 5e5 + 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 d[N], p[N];
void dfs(int u, int fa) {
    
    d[u] = p[u] = 1;    
    for (int i = h[u]; ~i; i = ne[i]) {
    
        int j = e[i];
        if (j == fa) continue ;
        dfs(j, u);
        if ((a[j] + 1) % 3 == a[u]) p[u] = max(p[u], p[j] + 1);
        if ((a[u] + 1) % 3 == a[j]) d[u] = max(d[u], d[j] + 1);
    }
}
int res;
void dp(int u, int fa) {
    
    if (fa == -1) res = max(res, d[u] + p[u] - 1);
    else if ((a[u] + 1) % 3 == a[fa]) res = max(res, p[u] + max(d[u], d[fa] + 1) - 1);
    else if ((a[fa] + 1) % 3 == a[u]) res = max(res, d[u] + max(p[u], p[fa] + 1) - 1);
    else res = max(res, d[u] + p[u] - 1);
    for (int i = h[u]; ~i; i = ne[i]) {
    
        int j = e[i];
        if (j == fa) continue ;
        dp(j, u);
    }
}
int main() {
    
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++) {
    
        int x, y; cin >> x >> y;
        add(x, y), add(y, x);
    }
    for (int i = 1; i <= n; i ++) cin >> a[i];
    dfs(1, -1);
    dp(1, -1);

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

Reverse order on the tree

[Link]( Reverse order on the tree - subject - Daimayuan Online Judge)

Ideas

• offline , Tree array

​ It's obvious that simulation won't work , We can find out $k$ In the case of a fork tree, the situation of each node is different from that of the node $i$ The node interval corresponding to its subtree is $[k(i-1),ki+1]$, Then the contribution of this point is the number of values in these intervals less than its number , We can preprocess all the interval numbers , For each interval, we require this interval to be less than the number of a certain number , We can use the method of counting this problem , Offline tree array to do .

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 = 2e5 + 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];
PII b[N];
int res[N];
struct Node {
    
    int l, r, h, id;
    bool operator<(Node t)const {
    
        return h < t.h;
    }
}q[4000000];
int tr[N];
int lowbit(int x) {
    
    return x & -x;
}
void add(int x) {
    
    for (; x <= n; x += lowbit(x)) tr[x] ++;
}
int sum(int x) {
    
    int res = 0;
    for (; x; x -= lowbit(x)) res += tr[x];
    return res;
}
int main() {
    
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i], b[i] = {
    a[i], i};
    sort(b + 1, b + 1 + n);
    for (int k = 1; k < n; k ++) {
    
        for (int i = 1; ; i ++) {
    
            int l = (i - 1) * k + 2, r = min(n, i * k + 1);
            if (l > n) break;
            q[++m] = {
    l, r, a[i], k};
        }
    }

    sort(q + 1, q + m + 1);
    int pos = 1;
    for (int i = 1; i <= m; i ++) {
    
        while (pos <= n && q[i].h > b[pos].x) add(b[pos ++].y);
        res[q[i].id] += sum(q[i].r) - sum(q[i].l - 1);
    }

    for (int i = 1; i < n; i ++)
        cout << res[i] << ' ';
    
    
    return 0;
}

Apposition

[link]( Apposition - subject - Daimayuan Online Judge)

Ideas

​ Binary violence enumerator deletes which bits , Find the corresponding denominator directly according to the simplest ratio , Judge whether the current denominator is legal , That is, whether it meets the deletion times , Whether you can delete the original number to get .

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;
LL a, b;
vector<int> get(LL x) {
    
    vector<int> res;
    while (x) {
    
        res.push_back(x % 10);
        x /= 10;
    }
    return res;
}
LL gcd(LL a, LL b) {
    
    return b ? gcd(b, a % b) : a;
}
int cnt[10];
int main() {
    
    ios::sync_with_stdio(false), cin.tie(0);   
    cin >> a >> b;
    vector<int> numa = get(a), numb = get(b);
    LL d =gcd(a, b), p = a / d, q = b / d;

    for (int j = 1; j < 1 << numa.size(); j ++) {
    
        for (int i = 0; i < 10; i ++) cnt[i] = 0;
        LL fz = 0, fm;
        for (int i = numa.size() - 1; i >= 0; i --)
            if (j >> i & 1) fz = fz * 10 + numa[i];
            else cnt[numa[i]] ++;
        
        if (!fz || fz % p) continue ;
        fm = fz / p * q;        
        
        for (int i = 0; i < numb.size(); i ++)
            if (fm % 10 == numb[i]) fm /= 10;
            else cnt[numb[i]] --;
        bool ok = false;
        for (int i = 0; i < 10; i ++)
            if (cnt[i]) {
    
                ok = true;
                break;
            }
        if (ok) continue ;        
        if (a > fz) a = fz, b = fz / p * q;
    }

    cout << a << ' ' << b << '\n';
    return 0;
}