Solutaion A. Creating a Character 題意：\(str\) 和智力值\(int\) ，然后你可以把\(exp\) 分別分配給這兩個(gè)數(shù)值，使得分配后\(str > int\) ，求有多少種分配方案。
特判不可能情況：\(str + exp <= int\) \(str <= int\) ，亂搞\(str > int\) ，亂搞正解：\(str,int\) 的數(shù)值為\(Adds,Addi\) ，那么有\[ \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*} \] \(Adds=max(0,{\frac{int + exp - str + 2}{2}})\) ，定義這個(gè)值為\(minAdds\) ，分配值的區(qū)間為\([minAdds,exp]\) ，那么答案為\(ans=max(0,exp - minAdds + 1)\) 。
//#define DEBUG
#include<bits/stdc++.h>
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 DEBUGfreopen("in.txt", "r", stdin);#endiffor (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<bits/stdc++.h>
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 DEBUGfreopen("in.txt", "r", stdin);#endiffor (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 題意：\(x\) 和你可以斬殺的類型\(n\) 。每種類型包含兩個(gè)數(shù)\(d,h\) ，代表每次斬殺能斬掉\(d\) 個(gè)頭，如果沒(méi)死的話，他會(huì)長(zhǎng)出\(h\) 個(gè)頭。問(wèn)最少斬殺次數(shù)。
//#define DEBUG
#include<bits/stdc++.h>
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 DEBUGfreopen("in.txt", "r", stdin);#endiffor (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 題意：\(f(t)=val\) ，其中\(t\) 為\(01\) 字符串，\(val\) 為其代表的二進(jìn)制值，比如\(f(011)=3，f(00101) = 5\) 。給出一個(gè)\(01\) 字符串，求有多少個(gè)子串使得\(f(s_l,s_{l+1},{\dots},s_r) = r - l + 1\) \(2e5\) ，所以可以每次枚舉20位去判斷。預(yù)處理出\(nxt[i]\) ，表示\(1{\dots}i\) 中最后一個(gè)\(1\) 的位置，\(nxt[i]=-1\) 。枚舉\(i\) 前\(20\) 位，定義\(sum\) 為當(dāng)前長(zhǎng)度子串所代表的二進(jìn)制的值。如果當(dāng)前\(sum<=r-nxt[l]\) ，貢獻(xiàn)\(+1\) 。
//#define DEBUG
#include<bits/stdc++.h>
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 _;
char s[2 * N];
int nxt[2 * N];int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);#endiffor (scanf("%d", &_); _; _--) {scanf("%s", s);int len = strlen(s);for (int i = 0; i < len; i++) {if (s[i] == '0') nxt[i] = (i == 0 ? -1 : nxt[i - 1]);else nxt[i] = i;}int ans = 0;for (int i = 0; i < len; i++) {int sum = 0;for (int j = i; j >= 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 題意：\(n\) 個(gè)點(diǎn)\(m\) 條邊的有向圖，然后給邊染色，用最少種類的顏料，使得環(huán)上的邊不是純色。求最少種類。\(dfs\) 先一次標(biāo)記該點(diǎn)，用顏料1一直染邊，如果遇到某點(diǎn)被一次標(biāo)記，說(shuō)明存在環(huán)，該邊染為顏料2。如果遇到二次標(biāo)記點(diǎn)，該邊染為顏料1。
//#define DEBUG
#include<bits/stdc++.h>
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;vector<pair<int, int> > 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 DEBUGfreopen("in.txt", "r", stdin);#endifflag = 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? 題意：\(0\) 數(shù)字，則說(shuō)明該可重復(fù)元素集合是\(unbalanced\) 。換句話說(shuō)，就是如果放置后，對(duì)應(yīng)位的數(shù)字有兩個(gè)非\(0\) 數(shù)字，就說(shuō)明\(unbalanced\) 。可單點(diǎn)修改某一位置的值，求每次詢問(wèn)區(qū)間的不平衡集合的最小和。\(0\) 的數(shù)字，然后求最小和。因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(a_i{\leq}10^9\)網(wǎng)上都是說(shuō)開\(10\) 棵線段樹，我不是很理解這個(gè)說(shuō)法，把數(shù)字\(x\) 拆分開。如果某位數(shù)字不為0，就設(shè)為\(x\) ，否則設(shè)為\(inf\) ，然后維護(hù)每一位的最小值，維護(hù)答案。初始為\(inf\) ，單點(diǎn)更新和建樹差不多。\(pushup\) 操作就\(Min[rt][i]\) 為左右兒子的對(duì)應(yīng)的最小值，\(val[rt]\) 就是左右兒子對(duì)應(yīng)為都不為\(inf\) 時(shí)的和，同時(shí)也是左右兒子的答案的最小值。\(query\) 操作用\(res[i]\) 保存這次查詢歷史對(duì)應(yīng)位的最小值，然后\(ans=min(ans,res[i]+Min[rt][i])\) ，每次再更新\(res[i]\) 。用我的\(inf\) 會(huì)WA5，小于\(2e9\) 。
//#define DEBUG
#include<bits/stdc++.h>
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;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) query(L, R, mid + 1, r, rt << 1 | 1);
}int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);#endifscanf("%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);}}
}
轉(zhuǎn)載于:https://www.cnblogs.com/ACMerszl/p/11517315.html
總結(jié)
以上是生活随笔 為你收集整理的Educational Codeforces Round 72 (Rated for Div. 2) 的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
