Solutions
A. Creating a Character
题意：
给出初始体力值(str)和智力值(int)，然后你可以把(exp)分别分配给这两个数值，使得分配后(str > int)，求有多少种分配方案。
思路：
- 特判不可能情况：(str + exp <= int)
- (str <= int)，乱搞
- (str > int)，乱搞
正解：
假设分别分配给(str,int)的数值为(Adds,Addi)，那么有
[egin{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}}{
ceil}\
{Rightarrow}{quad} &Adds {geq} {frac{int + exp - str + 1 + 1}{2}}
end{align*}
]
因为非负，所以(Adds=max(0,{frac{int + exp - str + 2}{2}}))，定义这个值为(minAdds)，分配值的区间为([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 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
", x % 2 ? x / 2 + 1 : x / 2);
} else {
if (intt + exp - str < 0) printf("%lld
", exp + 1);
else {
ll x = (intt + exp - str) / 2 + 1;
printf("%lld
", 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 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
", max(ex - tmp + 1, 0));
}
}
B. Zmei Gorynich
题意：
让你斩杀多头蛇，给出头数(x)和你可以斩杀的类型(n)。每种类型包含两个数(d,h)，代表每次斩杀能斩掉(d)个头，如果没死的话，他会长出(h)个头。问最少斩杀次数。
思路：
首先，如果第一次用最大“毛斩杀”可以杀死就结束了，如果不能杀死，就用最大“纯斩杀”来斩。
//#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 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
", ans);
}
}
C. The Number Of Good Substrings
题意：
假定(f(t)=val)，其中(t)为(01)字符串，(val)为其代表的二进制值，比如(f(011)=3，f(00101) = 5)。给出一个(01)字符串，求有多少个子串使得(f(s_l,s_{l+1},{dots},s_r) = r - l + 1)
思路：
因为字符串长度不超过(2e5)，所以可以每次枚举20位去判断。预处理出(nxt[i])，表示(1{dots}i)中最后一个(1)的位置，(nxt[i]=-1)。枚举(i)前(20)位，定义(sum)为当前长度子串所代表的二进制的值。如果当前(sum<=r-nxt[l])，贡献(+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 DEBUG
freopen("in.txt", "r", stdin);
#endif
for (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
", ans);
}
}
D. Coloring Edges
题意：
给出(n)个点(m)条边的有向图，然后给边染色，用最少种类的颜料，使得环上的边不是纯色。求最少种类。
思路：
画出图可以分析出，不存在环显然一种即可。若存在环，最多需要两种颜料。在发现环的时候换色即可。好像之前做过类似的题目。但是比赛时没有看这个题。(dfs)先一次标记该点，用颜料1一直染边，如果遇到某点被一次标记，说明存在环，该边染为颜料2。如果遇到二次标记点，该边染为颜料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 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 ? '
' : ' ');
}
E. Sum Queries?
题意：
如果集合内元素右对齐放置，对应位出现的数字之和不等于对应位的非(0)数字，则说明该可重复元素集合是(unbalanced)。换句话说，就是如果放置后，对应位的数字有两个非(0)数字，就说明(unbalanced)。可单点修改某一位置的值，求每次询问区间的不平衡集合的最小和。
思路：
就是区间找两个对应位都不为(0)的数字，然后求最小和。因为(a_i{leq}10^9)网上都是说开(10)棵线段树，我不是很理解这个说法，把数字(x)拆分开。如果某位数字不为0，就设为(x)，否则设为(inf)，然后维护每一位的最小值，维护答案。初始为(inf)，单点更新和建树差不多。(pushup)操作就(Min[rt][i])为左右儿子的对应的最小值，(val[rt])就是左右儿子对应为都不为(inf)时的和，同时也是左右儿子的答案的最小值。(query)操作用(res[i])保存这次查询历史对应位的最小值，然后(ans=min(ans,res[i]+Min[rt][i]))，每次再更新(res[i])。用我的(inf)会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 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
", ans == INF ? -1 : ans);
}
}
}