"Wei Lai Cup" 2022 Niuke summer multi school training camp 2 personal problem sets

D.Link with Game Glitch

Topic analysis

Yes $m$ A recipe , Each recipe can be used $k\times a_i$ individual $b_i$ Raw material generation $k\times c_i$ individual $d_i$ Grow raw materials . Now the request is $k$ Multiply by a weight $w$, So that there is no situation that infinite items can be generated circularly among all recipes . Demand maximum $m$.

Obviously, it is necessary to generate infinite items , There needs to be a ring and the number of items generated along the ring is more than the original , That is, all edges on the ring have $k(c[i]-a[i])>0$ That is to say $k\frac{c[i]}{a[i]}>1$.

Since there may be multiple rings , We just need to ensure that the maximum ring will not be generated circularly . Obviously, you can do it with two answers .

Code

#include <bits/stdc++.h>
//#pragma gcc optimize(2)
#define double long double
#define endl '\n'
using namespace std;

const int N = 2e3 + 10, MOD = 1e9 + 7;
const double EPS = 1e-8;

struct node{
     int v; double w; };

vector<node> g[N];
int n, m, cnt[N];
double dis[N];
bitset<N> vis;

bool check(double x){
    
    queue<int> q;
    x = -log(x);
    vis.set();
    memset(dis, 0, sizeof(dis));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 1; i <= n; i++) q.emplace(i);
    while(q.size()){
    
        int u = q.front(); q.pop();
        vis.reset(u);
        for(auto nxt : g[u]){
    
            int v = nxt.v;
            double w = nxt.w;
            if(dis[v] > dis[u] + w + x){
    
                dis[v] = dis[u] + w + x;
                cnt[v] = cnt[u] + 1;
                if(cnt[v] > n) return true;
                if(!vis[v]){
    
                    q.emplace(v);
                    vis.set(v);
                }
            }
        }
    }
    return false;
}   

inline void solve(){
    
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
    
        int a, b, c, d; cin >> a >> b >> c >> d;
        g[b].emplace_back(node{
    d, -log((1.0 * c) / a)});
    }
    double l = 0, r = 1;
    for(int i = 1; i <= 300; i++){
    
        double mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid;
    }
    cout << l << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

G. Link with Monotonic Subsequence structure

Topic analysis

It is required to construct a length of $n$ Sequence , Make the sequence $\max (\text{lis}(p),\text{lds}(p))$ As small as possible .

Dilworth theorem ： Pair poset $<A,\le >$, set up A The length of the longest chain in is $n$, Will $A$ The elements in are divided into disjoint inverse chains , The number of anti chains is at least $n$.

So there are $\text{lds}(p)=cnt(\text{lis(p)})$, So clearly $\max (\text{lis}(p),\text{lds}(p))\ge \max (k,\frac{k}{n})\ge \sqrt{n}$ . Therefore, direct construction $\sqrt{n}$ Just one block .

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;


inline void solve(){
    
    int n = 0; cin >> n;
    int b = ceil(sqrt(n));
    while(n > 0){
    
        for(int i = max(1ll, n - b + 1); i <= n; i++) cout << i << " ";
        n -= b;
    }
    cout << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

H. Take the Elevator simulation

Topic analysis

Given $k$ Floor building , Now there is an elevator from $1$ Building departure , At most $m$ people , There is something wrong with the elevator , When running down, you must reach $1$ The building can change its direction . Yes $n$ I hope from $a_i$ The floor arrives $b_i$ floor , Ask how many times the elevator needs to run at least .

set up $ansup[i]$ It means the first $i$ The highest number of floors reached by the wheel ,$ansdown[i]$ It means the first $i$ The highest level of departure , Then the final answer is to enumerate rounds $i$,$ans+=\max (ansup[i],ansdown[i])\ast 2-2$, Get the final answer .

Then it can be divided into two processes , Save all endpoints separately ( Marked ), The number of rounds allocated to each passenger can pass $\lceil \frac{m+cnt}{m}\rceil$ obtain .

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

struct node{
     int s, t; }up[N], down[N];

int ansup[N], ansdown[N];

inline void solve(){
    
    int n = 0, m = 0, k = 0; cin >> n >> m >> k;
    int upcnt = 0, downcnt = 0;
    for(int i = 1; i <= n; i++){
    
        int a, b; cin >> a >> b;
        if(a < b) up[++upcnt] = node{
    .s = a, .t = 1}, up[++upcnt] = node{
    .s = b, .t = -1};
        else down[++downcnt] = node{
    .s = a, .t = -1}, down[++downcnt] = node{
    .s = b, .t = 1};
    }
    int upans = 0, downans = 0;
    sort(up + 1, up + 1 + upcnt, [](const node &x, const node &y){
     return x.s < y.s || x.s == y.s && x.t < y.t; });
    sort(down + 1, down + 1 + downcnt, [](const node &x, const node &y){
     return x.s < y.s || x.s == y.s && x.t < y.t; });
    int now = 0; 
    for(int i = 1; i <= upcnt; i++){
    
        if(up[i].t == -1)
            ansup[(now + m - 1) / m] = up[i].s;    
        now += up[i].t;
    }
    assert(now == 0);
    for(int i = 1; i <= downcnt; i++){
    
        if(down[i].t == -1)
            ansdown[(now + m - 1) / m] = down[i].s;
        now += down[i].t;
    }
    int ans = 0;
    for(int i = 1; i <= 200000; i++)
        ans += 2 * max({
    1ll, ansup[i], ansdown[i]}) - 2;
    cout << ans << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

I. let fat tension

Topic analysis

Definition $le(i,j)$ by $X_i,X_j$ Cosine similarity between ：
$$le(i,j)=\frac{X_i\cdot X_j}{|X_i||X_j|}$$
Ask for novelty $Y^{\prime }$,$Y_i^{new}={\sum }_{j=1}^{n}le(i,j)\times Y_j$.

It is found that violent calculation obviously does not work , But it can be transformed into matrix operation , Divide by the module length to normalize each row of the matrix , So the answer is ：
$$X^{\prime }{X}^{\prime T}Y$$
$X^{\prime }$ Is the matrix normalized by rows .

Then you can get the operation process ：$(n\times k)\times (k\times n)\times (n\times d)$.

It is found that the multiplication between the latter two matrices is done first , Complexity $O(nkd)$. Then calculate directly .

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
//#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

double X[10010][100], XT[100][10010], Y[10010][100], ans1[100][100], ans2[10010][100];



inline void solve(){
    
    int n, k, d; cin >> n >> k >> d;
    double sum = 0;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= k; j++) 
        cin >> X[i][j];
    for(int i = 1; i <= n; i++) for(int j = 1; j <= d; j++)
        cin >> Y[i][j];
    for(int i = 1; i <= n; i++){
    
        sum = 0;
        for(int j = 1; j <= k; j++) sum += X[i][j] * X[i][j];
        sum = sqrt(sum);
        for(int j = 1; j <= k; j++) X[i][j] = XT[j][i] = X[i][j] / sum;
    }
    for(int i = 1; i <= k; i++) for(int j = 1; j <= d; j++)
    for(int t = 1; t <= n; t++) ans1[i][j] += XT[i][t] * Y[t][j];
    for(int i = 1; i <= n; i++) for(int j = 1; j <= d; j++)
    for(int t = 1; t <= k; t++) ans2[i][j] += X[i][t] * ans1[t][j];
    for(int i = 1; i <= n; i++) for(int j = 1; j <= d; j++)
        cout << ans2[i][j] << " \n"[j == d];

}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

J.Link with Arithmetic Progression Linear regression

Topic analysis

Give a sequence $a[i]$, structure $b[i]$, bring $\sum (a[i]-b[i]{)}^2$ Minimum , For the minimum .

It is easy to find that it is a linear regression problem , So consider using machine learning High school math Knowledge solutions for .

According to Gauss - Markov Theorem ： Given the assumption of classical linear regression , The least squares estimator is a linear unbiased estimator with minimum variance .

For the function $f(X)=w_1{x}_1+w_2{x}_2+\cdots +w_m{x}_m$, Define its objective function as $J(w)={\sum }_{i=1}^n[y_i-\widehat{y_i}{]}^2$.

Bring in the linear regression formula ：
$$\begin{gathered} b=\frac{n{\sum }_{i=1}^n{x}_i{y}_i-({\sum }_{i=1}^n{x}_i)({\sum }_{i=1}^n{y}_i)}{n{\sum }_{i=1}^n{x}_i^2-{\sum }_{i=1}^n{x}_i} \\ a=\bar{y}-b\bar{x} \end{gathered}$$
Then calculate the error output .

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long
#define double long double
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

inline int read(){
    
    int f = 1, x = 0; char s = getchar(); 
    while(s < '0'||s > '9'){
     if(s == '-') f = -1; s = getchar(); } 
    while(s >= '0' && s <= '9'){
     x = x * 10 + s - '0'; s = getchar();}
    return x *= f; 
}

int a[N];

inline void solve(){
    
    int n = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    double sumx = 0, sumy = 0, da = 0, dc = 0;
    for(int i = 1; i <= n; i++){
    
        sumx += i, sumy += a[i];
        da += i * a[i], dc += i * i;
    }
    double db = sumx * sumy / n, dd = sumx * sumx / n, ans = 0;
    double B = (da - db)/(dc - dd);
    double A = sumy / n - B * sumx / n;
    for(int i = 1; i <= n; i++) ans += (B * i + A - a[i]) * (B * i + A - a[i]);
    cout << ans << endl;
}

signed main(){
    
    //ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    cout << fixed << setprecision(12);
    while(t--) solve();
    return 0;
}

K.Link with Bracket Sequence I (DP)

Topic analysis

Given length is $n$ The bracket sequence of ( No guarantee of legality ), The length generated on this basis is $m$ The number of schemes in the bracket sequence .

set up $dp[i][j][k]$ Indicates that the number of parentheses inserted is $i$、 The number of parentheses in the original sequence used is $j$, There are more left parentheses than right parentheses $k$ When the number of programs . Then the final answer is $dp[m-n][n][0]$. Then consider how to design state transition ：

First enumerate the number of parentheses inserted , The original parenthesis sequence and the number of left parentheses is more than that of right parentheses .

If the parentheses enumerated at present are left parentheses , And the number of original brackets used $<n$, You can put this bracket in the final sequence , That is to say ：
$$dp[i][j+1][k+1]=(dp[i][j+1][k+1]+dp[i][j][k])\%mod$$
If a right parenthesis is enumerated at this time , also $k>0$, That is, the number of left parentheses is greater than the number of right parentheses , And the number of original brackets used $<n$, Put the right parenthesis in the final sequence ：
$$dp[i][j+1][k-1]=(dp[i][j+1][k-1]+dp[i][j][k])\%mod$$
If the number of parentheses used is $n$, Or the current enumeration to the right bracket , The left parenthesis can be inserted ：
$$dp[i+1][j][k+1]=(dp[i+1][j][k+1]+dp[i][j][k])\%mod$$
When $k>0$ when , If the number of parentheses in the original sequence is $n$, Or the current enumeration to the left bracket , You can insert the right parenthesis ：
$$dp[i+1][j][k-1]=(dp[i+1][j][k-1]+dp[i][j][k])\%mod$$

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#pragma g++ optimize(2)
// #define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, mod = 1e9 + 7;
int dp[220][220][220];

inline void solve(){
    
    // memset(dp, 0, sizeof(dp));
    int m, n; cin >> n >> m;
    string s; cin >> s;
    // if(n & 1 || (m - n) & 1) { cout << 0 << endl; return; }
    dp[0][0][0]=1;
	for (int i = 0; i <= m - n; ++i)
    for (int j = 0; j <= n; ++j)
        for (int k = 0; k <= m; ++k){
    
            if (s[j] == '(' && j < n)
                dp[i][j + 1][k + 1] = (dp[i][j + 1][k + 1] + dp[i][j][k]) % mod;
            else
                dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % mod;
            if (k > 0){
    
                if (s[j] == ')' && j < n)
                    dp[i][j + 1][k - 1] = (dp[i][j + 1][k - 1] + dp[i][j][k]) % mod;
                else
                    dp[i + 1][j][k - 1] = (dp[i + 1][j][k - 1] + dp[i][j][k]) % mod;
            }
        }
	cout << dp[m - n][n][0] << endl;
    for(int i = 0; i <= m + 2; i++)
        for(int j = 0; j <= n + 2; j++)
            for(int k = 0; k <= m + 2; k++) dp[i][j][k] = 0;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

L.Link with Level Editor I

Topic analysis

remember $d{p}_{i,j}$ Said in the first $i$ Arrival point in the world $j$. Then use the rolling array to optimize the first dimension .

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#pragma g++ optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e3 + 5;
int dp[N], now[N];
void solve(){
    
    int n, m; cin >> n >> m;
    memset(dp, 0x3f, sizeof(dp));
    int ans = 1e9;
    while (n--){
    
        int k; cin >> k;
        dp[1] = 0;
        memset(now, 0x3f, sizeof(now));
        for (int i = 1; i <= k; i++){
    
            int u, v; cin >> u >> v;
            now[v] = min(now[v], dp[u] + 1);
        }
        for (int i = 1; i <= m; i++) dp[i] = min(dp[i] + 1, now[i]);
        ans = min(ans, dp[m]);
    }
    if (ans == 1e9) cout << "-1\n";
    else cout << ans << "\n";
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}