Educational Codeforces Round 72 (Rated for Div. 2)

Solutaion

A. Creating a Character

Title:
Give The initial physical strength value \(str\) and the intelligence value \(int\), then you can put the \(str\) class=”math inline”>\(exp\) are assigned to these two values ​​respectively, so that after the assignment \(str> int\), ask for How many distribution schemes.
Idea:

• Special judgment is impossible: \(str + exp <= int\)
• \(str <= int\), mess with it
• \(str> int\), messing around

Positive solution:
Assume that the values ​​assigned to \(str,int\) are \(Adds,Addi\), then there is
\[ \begin{align*} & str + Adds> int + Addi \ {\Rightarrow}{\quad} & str + Adds> int + (exp-Adds)\{\Rightarrow}{\quad} &2{\ast}Adds> int + exp-str\{\Rightarrow}{\quad} &2{\ast}Adds\ {\geq}\ int + exp-str + 1\{\Rightarrow}{\quad} &Adds\ {\geq}\ {\lceil}{\frac{int + exp-str + 1 }{2}}{\rceil}\{\Rightarrow}{\quad} &Adds\ {\geq}\ {\frac{int + exp-str + 1 + 1}{2}} \end{align*} \ ]
Because it is non-negative, so \(Adds=max(0,{\frac{int + exp-str + 2}{2}})\)< /span>, define this value as \(minAdds\), and the range of assigned value is \([minAdds,exp]\) , then the answer is \(ans=max (0,exp-minAdds + 1)\).

//#define DEBUG#includeusing namespace std;const int N = 100010;const int inf = 0X3f3f3f3f;const long long INF = 0x3f3f3f3f3f3f3f3f;const double eps = 1e-6;const double pi = acos(-1.0);const int mod = 1000000007;typedef long long ll;int _;int main() {#ifdef DEBUG freopen("in.txt", "r" , stdin); #endif for (scanf("%d", &_); _; _--) {ll str, intt, exp; scanf("%lld %lld %lld", &str, &intt, &exp); if (str + exp <= intt) puts("0"); else if (str <= intt) {ll x = exp-(intt-str); printf("%lld\n", x% 2? x / 2 + 1: x / 2);} else {if (intt + exp-str <0) printf("%lld\n", exp + 1); else {ll x = (intt + exp-str) / 2 + 1; printf("%lld\n", exp-x + 1);}}} }

//#define DEBUG#include using namespace std;const int N = 100010;const int inf = 0X3f3f3f3f;const long long INF = 0x3f3f3f3f3f3f3f3f;const double eps = 1e-6;const double pi = acos(-1.0);const int mod = 1000000007;typedef long long ll;int _;int main() {#ifdef DEBUG freopen("in.txt" , "r", stdin); #endif for (scanf("%d", &_); _; _--) {int st, in, ex, tmp; scanf("%d %d %d", &st , &in, &ex); tmp = max(0, (in + ex-st + 2) / 2); printf("%d\n", max(ex-tmp + 1, 0)); }} 
B. Zmei Gorynich
 
The meaning of the question: 
 Let you kill the Hydra and give the number of heads\(x\) and the types you can kill \(n\). Each type contains two numbers \(d,h\), which means that each kill can kill \(d\)  He will grow up \(h\) if he is not dead. Ask the minimum number of kills. 
 Idea: 
 First of all, if you can kill with the largest "Mao Kill" for the first time, it will be over. If you can't kill, use the largest "Pure Kill" to kill. 
 
//#define DEBUG#includeusing namespace std;const int N = 100010;const int inf = 0X3f3f3f3f;const long long INF = 0x3f3f3f3f3f3f3f3f;const double eps = 1e-6;const double pi = acos(-1.0);const int mod = 1000000007;typedef long long ll;int _;int main() {#ifdef DEBUG freopen("in.txt", "r" , stdin); #endif for (scanf("%d", &_); _; _--) {int m, n; scanf("%d %d", &m, &n); int val = -inf, maxx = -inf; while (m--) {int u, v; scanf("%d %d", &u, &v); val = max(val, u-v); maxx = max(maxx, u) ;} ll ans = 1; n -= maxx; if (n> 0) {if (val <= 0) ans = -1; else ans += (n + val-1) / val;} printf("% lld\n", ans); }}
C. The Number Of Good Substrings
 Assuming \(f(t)=val\), where \(t\) is \(01\) string, \(val\) represents the binary value, such as \(f(011)=3, f(00101) = 5\). Given a string of \(01\), find how many substrings make \(f(s_l,s_{l+1 },{\dots},s_r) = r-l + 1\)
 Idea: 
 Because the string length does not exceed \(2e5\)< /span>, so you can enumerate 20 bits at a time to judge. Preprocess out \(nxt[i]\), which means \(1{\dots}i\) The position of the last \(1\), \(nxt[i]=-1\). Enumerate the first \(20\) bits of \(i\), define \(sum\) is the binary value represented by the current length substring. If currently \(sum<=r-nxt[l]\), contribute \(+1\). 
//#define DEBUG#includeusing namespace std;const int N = 100010;const int inf = 0X3f3f3f3f;const long long INF = 0x3f3f3f3f3f3f3f3f;const double eps = 1e-6;const double pi = acos(-1.0);const int mod = 1000000007;typedef long long ll;int _;char s[2 * N];int nxt[2 * N];int main( ) {#ifdef DEBUG freopen("in.txt", "r", stdin); #endif for (scanf("%d", &_); _; _--) {scanf("%s", s) ; int len ​​= strlen(s); for (int i = 0; i = 0 && i-j + 1 <= 20; j--) {if (s[j] == '0') continue; sum += 1 << (i-j); if (sum <= i-( j == 0? -1: nxt[j-1])) ans++;}} printf("%d\n", ans);} }
D. Coloring Edges
Question meaning:
 Give \(n\) points\ (m\) A directed graph with edges, and then color the edges, using the least kinds of pigments, so that the edges on the ring are not pure colors. Seek the least variety. 
 Idea: 
 Draw a picture and you can analyze it. It is obvious that there is no ring. If rings are present, at most two pigments are required. Change the color when you find the ring. It seems to have done a similar topic before. But this question was not looked at during the competition. \(dfs\) first mark the point once, and dye the edge with paint 1 all the time. If a certain point is marked once, it means there is a ring, and the edge is dyed with paint 2. . If a secondary mark is encountered, the edge is dyed as pigment 1. 
//#define DEBUG#includeusing namespace std;const int N = 100010;const int inf = 0X3f3f3f3f;const long long INF = 0x3f3f3f3f3f3f3f3f;const double eps = 1e-6;const double pi = acos(-1.0);const int mod = 1000000007;typedef long long ll;vector> G[5010];int n, m;int colour[ 5010];int res[5010];bool flag;void dfs(int u) {colour[u] = 1; for (auto it: G[u]) {int to = it.first, id = it.second; if (!colour[to]) {res[id] = 1; dfs(to);} else if (colour[to] == 1) {res[id] = 2; flag = true;} else {res[ id] = 1;}} colour[u] = 2;}int main() {#ifdef DEBUG freopen("in.txt", "r", stdin); #endif flag = false; scanf("%d% d", &n, &m); for (int i = 1; i <= m; i++) {int u, v; scanf("%d %d", &u, &v); G[u].push_back(make_pair (v, i));} for (int i = 1; i <= n; i++) {if (!colour[i]) dfs(i);} if (flag) puts("2"); else puts("1"); for (int i = 1; i <= m; i++) printf("%d%c", res[i], i == m?'\n': '');}
E. Sum Queries?
Question meaning:
 If there is The elements are placed right-aligned, and the sum of the numbers appearing in the corresponding bits is not equal to the non-\(0\) numbers of the corresponding bits, indicating that the set of repeatable elements is \(unbalanced\). In other words, if the corresponding digit has two non-\(0\) digits after placing it, it means that \( unbalanced\). The value of a certain position can be modified at a single point, and the minimum sum of the unbalanced set of each query interval can be calculated. 
 Idea: 
 Find two numbers whose corresponding digits are not \(0\) in the interval, and then find the minimum sum. Because \(a_i{\leq}10^9\) all talk about \(10\) Line segment tree, I don’t understand this statement very much, split the number \(x\). If a digit is not 0, set it to \(x\), otherwise set it to \(inf\), and then maintain the minimum value of each digit and maintain the answer. The initial is \(inf\), and single-point update is similar to building a tree. \(pushup\) The operation \(Min[rt][i]\) corresponds to the left and right sons The minimum value, \(val[rt]\) means that the left and right sons are not corresponding to \(inf\) The sum of time is also the minimum value of the left and right son's answers. \(query\) The operation uses \(res[i]\) to save the smallest corresponding bit of the query history Value, and then \(ans=min(ans,res[i]+Min[rt][i])\), and then update \(res[i]\). Using my \(inf\) will WA5, which is smaller than \(2e9\). 
//#define DEBUG#includeusing namespace std;const int N = 100010;const int inf = 0X3f3f3f3f;const long long INF = 0x3f3f3f3f3f3f3f3f;const double eps = 1e-6;const double pi = acos(-1.0);const int mod = 1000000007;typedef long long ll;ll val[2 * N * 4], Min[2 * N * 4][15]; int a[2 * N];int n, m;ll res[15];ll ans;void pushup(int rt) {val[rt] = INF; for (int i = 0; i <= 12; i++) {if (Min[rt << 1][i] != INF && Min[rt << 1 | 1][i] != INF) {val[rt] = min(val[rt], Min[rt < <1][i] + Min[rt << 1 | 1][i]);} Min[rt][i] = min(Min[rt << 1][i], Min[rt << 1 | 1][i]);} val[rt] = min(val[rt], min(val[rt << 1], val[rt << 1 | 1]));}void build(int l, int r, int rt) {val[rt] = INF; if (l == r) {int tmp = a[l]; for (int i = 0; i <= 12; i++) {int x = tmp% 10 ; if (x == 0) Min[rt][i] = INF; else Min[rt][i] = a[l]; tmp /= 10;} return;} int mid = l + r >> 1; build(l, mid, rt << 1); build(mid + 1, r, rt << 1 | 1); pushup(rt);)void modify(int pos, int x, int l, int r, int rt) {if (l == r) {int tmp = x; for (int i = 0; i <= 12; i++) {int y = tmp% 10; if (y == 0) Min[rt][i] = INF; else Min[rt][i] = x; tmp /= 10;} return;} int mid = l + r >> 1; if (pos <= mid ) modify(pos, x, l, mid, rt << 1); else modify(pos, x, mid + 1, r, rt << 1 | 1); pushup(rt);)void query(int L, int R, int l, int r, int rt) {if (L <= l && r <= R) {for (int i = 0; i <= 12; i++) {if (Min[rt][i] != INF && res[i] != INF) {ans = min(ans, Min[rt][i] + res[i]);}} for (int i = 0; i <= 12; i++) { res[i] = min(res[i], Min[rt][i]);} ans = min(ans, val[rt]); return;} int mid = l + r >> 1; if (L <= mid) query(L, R, l, mid, rt << 1); if (R> mid) que ry(L, R, mid + 1, r, rt << 1 | 1); }int main() {#ifdef DEBUG freopen("in.txt", "r", stdin); #endif scanf("% d %d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); build(1, n, 1); while (m- -) {int op, l, r, pos, x; scanf("%d", &op); if (op == 1) {scanf("%d %d", &pos, &x); modify(pos, x, 1, n, 1);} else {scanf("%d %d", &l, &r); ans = INF; for (int i = 0; i <= 12; i++) res[i] = INF ; query(l, r, 1, n, 1); printf("%lld\n", ans == INF? -1: ans);}} }