80 + 20 + 0 + 70 = 170 The third question should have 10 points for violence, but I didn't hit it.
T1 Star Trek (US TV and film series)
headline translation
There are a total of n nodes and m paths, m-2 of them are required to be traveled twice and the remaining 2 paths are traveled only once, ask what is the total number of paths that are different, and if the two edges that are traveled only once are different then the paths will be considered different.
Sample #1
Sample Input #1
5 4
1 2
1 3
1 4
1 5
Sample Output #1
6
Sample #2
Sample Input #2
5 3
1 2
2 3
4 5
Sample Output #2
0
analyze
Conclusion questions 🤣
There's no output in the exam room.\(0\) of that sample, and so obviously couldn't think of a non-connected kind of program. It was me who was too\(Vegetable)Up.
Playing a few samples (1h) with multiple hands reveals this:
- For the case where there is no self-loop, it is assumed that the\(rt\) as the starting point for that route, then a bit of hand playing reveals that the number of legal routes that can be generated is the number of\(rt\) Look at the picture.
The lines labeled red are the possible edges that will be walked only once, and the lines labeled green are the possible walks. That is, every time you start from\(rt\) Departure eventually returns to some son of a son of a son of a son of a son of a son of a son of a son with a\(rt\) A connected edge is an edge that goes only once. Then\(rt\) The contribution to the answer is:
Among them.\(size\) Indicates how many points this point is directly connected to, minus one since it cannot be counted as a father. The total contribution is then:
- For the presence of self-loops, two cases are considered: self-loops with self-loops, and self-loops with normal edges.
- Self-loop with self-loop: the number of schemes is the combination of two randomly taken from all self-loops:\({\large\binom{cir}{2}}\)。\(cir\) is the number of self-loops.
- Self-ring with plain edge: the number of schemes is i.e. one randomly chosen from all self-rings and one randomly chosen from plain edges. Apply the multiplication principle:\(cir\times(m-cir)\)。
Finished? Guess why there's an example.\(0\)? If there exists an edge that is disjoint from all other edges, then it is impossible to walk through the\(m\) The edges of the strip. So to determine whether the edges are connected or not. Just use the concatenation set.
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 1e5 + 5;
int n, m, cir, ans1, ans2, f[N], x[N];
vector<int> G[N];
inline int find(int k){
if(!f[k]) return k;
return f[k] = find(f[k]);
}
signed main(){
// freopen("", "r", stdin);
ios::sync_with_stdio(0), (0), (0);
cin>>n>>m;
for(int i=1, y; i<=m; ++i){
cin>>x[i]>>y;
int fa = find(x[i]), fb = find(y);
if(fa != fb) f[fb] = fa;
if(x[i] == y){ ++cir; continue; }
G[x[i]].push_back(y), G[y].push_back(x[i]);
} int bg = find(x[1]);
for(int i=2; i<=m; ++i) if(find(x[i]) != bg) return cout<<0, 0;
if(cir) ans2 = cir * (cir-1) / 2 + cir * (m - cir);
for(int i=1; i<=n; ++i) for(int v : G[i]) ans1 += G[v].size() - 1;
ans1 >>= 1; return cout<<ans1 + ans2, 0;
}
T2 Tree felling
title page
Mr. Lin bought it.\(n\) A sapling, planted in a straight line, is used to decorate his garden. Initially the height of all saplings is\(0\)each time\(1\) Every sapling grows taller by the day.\(1\) meters. For each sapling, Mr. Lin wants the final height to be\(a_i\)He therefore regularly checks the condition of the saplings and cuts down the over-height ones in a timely manner. Specifically, from the time all the saplings are planted, every d days (i.e., day 1), the trees will be removed.\(d\) Day 1, Day 2\(2d\) Days, . . . (and so on) Mr. Lin will check all the saplings once, and if there are any saplings that are not lower than his desired height, Mr. Lin will take the higher part (which could be\(0\)) is cut down, after which the sapling will not grow any taller. Since cutting down trees is hard work, he wants to cut down no more than k meters of the total length of the sapling. On this premise, in order to be lazy, Mr. Lin wants to know the maximum possible length of the sapling.\(d\) Value.
sample
3 4
1 3 5
3
analyze
Winnie the Pooh question
I pulled a bubble of two-point answers on the exam, but I didn't care about it after the sample, so I'm glad to have it!\(20\) The score. Taking a toe hold after the next exam and thinking that there is no monotonicity in the second score. 👀
Consider such a thing. What we're looking for.\(d\) All meet such a lion:
Shift the term to get:
This is clear. It can be noticed that we can enumerate\(\left \lceil \frac{a_i}{d} \right \rceil\) cap (a poem)\(d\) of all possible values, a violent enumeration judgment is sufficient. Suppose now that we enumerate a possible\(d'\) Value. Then the current\(d\) The range of values can then be expressed as:
in the event that\(d'\) Within this range, then the range is legal. Just update the answer with the maximum value of this range.
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, k, a[101], ans;
vector<int> vec;
signed main(){
ios::sync_with_stdio(0), (0), (0);
cin>>n>>k;
for(int i=1; i<=n; ++i){
cin>>a[i]; k += a[i];
for(int j=1; j*j<=a[i]; ++j){
vec.push_back(j);
vec.push_back((a[i] + j - 1) / j);
}
}
sort((), ());
(unique((), ()), ());
for(int it : vec){
int sum = 0, d;
for(int i=1; i<=n; ++i){
sum += (a[i] + it - 1) / it;
} d = k / sum;
if(d >= it) ans = max(ans, d);
} return cout<<ans, 0;
}
For future situations like this question. Provide two solution ideas:
- Enumeration samples + hand play. Finding patterns.
- List the expressions for the answers. Observe + Violently dismantle the lion.
T3 Supertrees
T4 report card
Title Description
When the final exams are over, the class teacher, Mr. L, has to distribute the report cards to each student.\(n\) The transcripts, numbered from\(1\) until (a time)\(n\) are stacked on the table in the order in which the numbered\(i\) The transcript scores for the\(W_i\)。
Report cards are issued in batches. When a report card is issued, Mr. L takes a consecutive paragraph from the current stack of report cards and allows those students to pick up their report cards. When this batch is complete, Mr. L takes a consecutive paragraph from the remaining report cards for the next batch of students to pick up. After several batches, the report cards will be distributed to all students.
However, distributing report cards is a headache, on the one hand, we have to take care of the psychological emotions of the students, so that students whose scores are too far apart cannot receive their report cards in the same batch; on the other hand, we have to consider the cost of time, and try to minimize the number of batches for receiving report cards. For a program of distributing report cards, we define its cost as:
included among these\(k\) is the number of batches distributed, for the first\(i\) The report card, which was circulated\(max_i\) is the highest score that\(min_i\) is the minimum score.\(a\) cap (a poem)\(b\) is a given evaluation parameter. Now, help Teacher L find the least costly solution for distributing report cards and tell Teacher L about this minimal cost. Of course, the number of batches of report cards to be distributed\(k\) It's your decision.
input format
The first line contains a positive integer\(n\), represents the number of transcripts. The second line contains two non-negative integers\(a,b\), indicating the given evaluation parameters. The third line contains\(n\) a positive integer.\(w_i\) denote\(i\) scores on a report card.
output format
A positive integer only, indicating what the minimum cost is.
Sample #1
Sample Input #1
10
3 1
7 10 9 10 6 7 10 7 1 2
Sample Output #1
15
draw attention to sth.
\(n \leq 50\)，\(a \leq 1500\)，\(b \leq 10\)，\(w_i \leq 1000\)。
analyze
for(int l=1, r=len; r<=len; ++l, ++r)Next time it happens just refactor 🤮
A quick glance at the interval DP, but the state wasn't set right, still too 🥬. The exam instantly thought of a DP and set the\(dp[l][r][k]\) away\(k\) subelimination interval\(l\sim r\) Minimum spend required. Thinking nothing of pulling a pile of dP, I didn't realize that the small sample passed and achieved a noble\(70pts\). But in hindsight, it's obvious that it's a fake.
Fake code.
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, a, b, res[51], dp[51][51][51], ans = LONG_MAX;
struct SquareTable{
int mx[51][10], mn[51][10];
inline void init(){
for(int i=1; i<=n; ++i) mx[i][0] = mn[i][0] = res[i];
for(int j=1; j<=__lg(n); ++j) for(int i=1; i+(1<<j)-1<=n; ++i){
mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
mn[i][j] = min(mn[i][j-1], mn[i+(1<<(j-1))][j-1]);
}
}
inline int QueryMx(int l, int r){
if(l > r) return -1;
int k = __lg(++r - l);
return max(mx[l][k], mx[r-(1<<k)][k]);
}
inline int QueryMn(int l, int r){
if(l > r) return INT_MAX;
int k = __lg(++r - l);
return min(mn[l][k], mn[r-(1<<k)][k]);
}
} st;
signed main(){
ios::sync_with_stdio(0), (0) ,(0);
cin>>n>>a>>b; for(int i=1; i<=n; ++i) cin>>res[i]; ();
if(b == 0) return cout<<a, 0;
memset(dp, 0x7f, sizeof(dp));
for(int len=1; len<=n; ++len) for(int l=1, r=len; r<=n; ++l, ++r)
dp[l][r][1] = a + b * ((l, r) - (l, r)) * ((l, r) - (l, r));
for(int len=2; len<=n; ++len){
for(int l=1, r=len; r<=n; ++r, ++l){
for(int k=2; k<=len; ++k){
for(int lenn=1; lenn<len; ++lenn){
for(int ln=l, rn=l+lenn-1; rn<=r; ++ln, ++rn){
// printf("l = %lld r = %lld ln = %lld rn = %lld ", l, r, ln, rn);
int lmx = (l, ln-1), lmn = (l, ln-1);
int rmx = (rn+1, r), rmn = (rn+1, r);
int mx, mn;
if(l == ln) mx = rmx, mn = rmn;
else if(r == rn) mx = lmx, mn = lmn;
else mx = max(lmx, rmx), mn = min(lmn, rmn);
// printf("mx = %lld mn = %lld\n", mx, mn);
dp[l][r][k] = min(dp[l][r][k], dp[ln][rn][k-1] + a + b * (mx - mn) * (mx - mn));
}
}
}
}
}
for(int i=1; i<=n; ++i) ans = min(ans, dp[1][n][i]);
return cout<<ans, 0;
}
Like this interval, for example, my dP can only be extended one segment at a time, and I can't make the number of times the\(k\) cap (a poem)\(p\) The two intervals are merged. That is, my dP can't be deducted in a whole segment, but constantly from both sides. So it's bogus. The data is watered down.
correct solution (a math. equation)
Soul DP
giving you\(n\le 50\) There is a reason for this. We find that the DP state is only\(l\) cap (a poem)\(r\) Two dimensions are hard to transfer. So consider adding states. Because the cost of each interval is only related to the\(max\) cap (a poem)\(min\) Related. So set\(g[l][r][mx][mn]\) It means it's gone.\(l\sim r\) The most valuable of the scattered blocks remaining in some portion of this interval are\(mx\) cap (a poem)\(mn\)and then eliminate them all (by putting\(l\sim r\) (full elimination) of the minimum spend. Setting\(f[l][r]\) denote\(l\sim r\) Minimum cost of total elimination. For the multi-state DP equation, it is now necessary to establish the relationship between the two states.
It can be found that for\(g[l][r][mx][mn]\) The loose blocks are actually eliminated all in one step of the operation, so there's that:
Consider it now.\(g\) The extension of the Suppose a new point is added to the right\(r+1\). Then there will be two scenarios:
-
Add the new point to the part that has been eliminated, then there will be no effect on the existing state:
\[g[l][r+1][mx][mn]=min\{g[l][r][mx][mn]+f[r][r] \} \]But it was found that for\(r\) Any of the latter points will satisfy this transfer equation, and it is clear that the table needs to be brushed. Consider the interval to be extended to\(l\sim k\)So there:
\[g[l][k][mx][mn]=min\{g[l][r][mx][mn]+f[r+1][k] \} \]Bad transfer? Put\(r\) cap (a poem)\(k\) Switch it up:
\[g[l][r][mx][mn]=min\{g[l][k][mx][mn]+f[k+1][r] \} \] -
Adding a new point to a bulk block that has not been eliminated requires updating the current state:
\[g[l][r+1][max(mx, a_{r+1})][min(mn,a_{r+1})]=min\{g[l][r][mx][mn] \} \]Still considering a change:
\[g[l][r][max(mx, a_{r})][min(mn,a_{r})]=min\{g[l][r-1][mx][mn] \} \]
At this point all transfers have been completed. However.\(a\) The range is a bit large and needs to be discretized. Complexity\(\mathcal{O}(n^5)\)。
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, a, b, res[51], pos[51], g[51][51][51][51], f[51][51];
signed main(){
ios::sync_with_stdio(0), (0), (0);
cin>>n>>a>>b; for(int i=1; i<=n; ++i) cin>>res[i], pos[i] = res[i];
sort(pos+1, pos+1+n); int cnt = unique(pos+1, pos+1+n) - pos - 1;
for(int i=1; i<=n; ++i) res[i] = lower_bound(pos+1, pos+1+cnt, res[i]) - pos;
memset(f, 0x3f, sizeof(f)), memset(g, 0x3f, sizeof(g));
for(int i=1; i<=n; ++i) f[i][i] = a, g[i][i][res[i]][res[i]] = 0;
for(int len=2; len<=n; ++len) for(int l=1, r=len; r<=n; ++l, ++r){
for(int mx=1; mx<=cnt; ++mx) for(int mn=1; mn<=mx; ++mn)
g[l][r][max(mx, res[r])][min(mn, res[r])] = min(g[l][r][max(mx, res[r])][min(mn, res[r])], g[l][r-1][mx][mn]);
for(int mx=1; mx<=cnt; ++mx) for(int mn=1; mn<=mx; ++mn){
for(int k=l; k<r; ++k) g[l][r][mx][mn] = min(g[l][r][mx][mn], g[l][k][mx][mn] + f[k+1][r]);
f[l][r] = min(f[l][r], g[l][r][mx][mn] + a + b * (pos[mx]-pos[mn]) * (pos[mx]-pos[mn]));
}
} return cout<<f[1][n], 0;
}