A-Tokitsukaze and Bracelet
根据手环的三个属性值判断手环的等级。
- 对攻击百分比来说,+0为100%,+1为150%,+2为200%
- 对体力和精神来说,+0在29,30,31,32里选择,+1在34,36,38,40里选择,+2固定为45
n(1≤n≤100)
ai,bi,ci(ai∈100,150,200;bi,ci∈29,30,31,32,34,36,38,40,45)
模拟即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| void solve() {
int lv1[3] = { 100,150,200 };
int lv2[9] = { 29,30,31,32,34,36,38,40,45 };
int a, b, c;cin >> a >> b >> c;
int ans = 0;
for (int i = 0;i < 3;i++) {
if (a == lv1[i]) { ans += i; break; }
}
for (int i = 0;i < 9;i++) {
if (b == lv2[i]) {
if (i < 4)ans += 0;
else if (i < 8)ans += 1;
else ans += 2;
break;
}
}
for (int i = 0;i < 9;i++) {
if (c == lv2[i]) {
if (i < 4)ans += 0;
else if (i < 8)ans += 1;
else ans += 2;
break;
}
}
cout << ans << endl;
}
|
B-Tokitsukaze and Cats
关猫,每个猫被限制在一个单元格内就算被关住了,如图:

给猫的坐标,询问至少需要多少片防猫网能把他们全都关住。
n,m,k(1≤n,m≤300;1≤k≤n⋅m)
xi,yi(1≤xi≤n;1≤yi≤m)
遍历坐标点判断它上下左右是否有隔板,如果没有则补充。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void solve() {
int n, m, k;cin >> n >> m >> k;
map<pair<int, int>, bool>cats;
int ans = 0;
while (k--) {
int x, y;cin >> x >> y;
cats[{ x, y }] = true;
pair<int, int>pu = { x - 1,y }, pd = { x + 1,y }, pl = { x,y - 1 }, pr = { x,y + 1 };
int cnt = 4;
if (cats.count(pu) != 0)cnt -= 1;
if (cats.count(pd) != 0)cnt -= 1;
if (cats.count(pl) != 0)cnt -= 1;
if (cats.count(pr) != 0)cnt -= 1;
ans += cnt;
}
cout << ans << endl;
}
|
E&F-Tokitsukaze and Eliminate
有一排n个宝石,第i个的颜色是coli,可以进行如下的操作:
选一种颜色x,将颜色为x的最右边的那颗宝石及其右边的所有宝石全部消除。
T(1≤T≤2∗105)
n(1≤n≤2∗105)
easy:1≤coli≤min(n,2)
hard:1≤coli≤n
贪心,从右边枚举,当找到最后一种达到两次出现的颜色后,进行一次对该颜色的操作,直到所有宝石都被消除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| void solve() {
int n;cin >> n;
vector<int>col(n + 1);
set<int>cls;
for (int i = 1;i <= n;i++) {
cin >> col[i];
cls.insert(col[i]);
}
int tn = cls.size(); // 颜色种数
map<int, int>clrs;
map<int, int>colors;
int ans = 0;
int cnt = 0;
int pi = n;
while (tn != 0) {
for (int i = n;i > 0;i--) {
colors[col[i]]++;
if (colors[col[i]] == 1) {
cnt++; // 达到两次及以上的颜色数
if (cnt == tn) {
ans++;
cnt = 0;
colors = clrs;
pi = i - 1;
}
}
}
tn = colors.size();
colors = clrs;
n = pi;cnt = 0;
}
cout << ans << endl;
}
|
I-Tokitsukaze and Short Path (plus)
有一个n个顶点的完全图G,顶点编号是1到n,编号为i的顶点值是ai,边权的计算方式如下:
$$
w_{u,v}=
\begin{cases}
0& \text{u=v}\\
|a_u+a_v|+|a_u-a_v|& \text{u ≠ v}
\end{cases}
$$
dist(i,j)定义为以i为起点到j的最短路。
求:
i=1∑nj=1∑ndist(i,j)
T(1≤T≤2×105)
n(1≤n≤2×105)
ai(1≤ai≤2×105)
∣ai+aj∣+∣ai−aj∣={ai+aj+ai−ajai+aj+aj−ai=2×ai=2×ajai≥ajai<aj
对a进行排序,计算每个数对总和的贡献,也就是比某数小的数的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
| void solve() {
int n;cin >> n;
vector<ll>a(n);
for (int i = 0;i < n;i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
ll ans = 0;
for (int i = 0;i < n;i++) {
ans += a[i] * i;
}
cout << 4 * ans << '\n';
}
|
J-Tokitsukaze and Short Path (minus)
有一个n个顶点的完全图G,顶点编号是1到n,编号为i的顶点值是ai,边权的计算方式如下:
$$
w_{u,v}=
\begin{cases}
0& \text{u=v}\\
|a_u+a_v|-|a_u-a_v|& \text{u ≠ v}
\end{cases}
$$
dist(i,j)定义为以i为起点到j的最短路。
求:
i=1∑nj=1∑ndist(i,j)
T(1≤T≤2×105)
n(1≤n≤2×105)
ai(1≤ai≤2×105)
∣ai+aj∣−∣ai−aj∣={ai+aj−ai+ajai+aj−aj+ai=2×aj=2×aiai≥ajai<aj
如果u到v的直接路径的长度大于dist(u,w)+dist(v,w),则取后者,假设dist(u,v)=2×av,则有dist(u,w)+dist(v,w)=2×av+2×av=4×av,则只有当2×aw的值小于av时取后者找到数组中的最小值。
对a进行排序,计算每个数对总和的贡献次数,也就是比某数或2×最小ai大的数的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void solve() {
int n;cin >> n;
vector<ll>a(n);
ll mn = 1e18;
for (int i = 0;i < n;i++) {
cin >> a[i];
mn = min(mn, a[i]);
}
sort(a.begin(), a.end());
ll ans = 0;
for (int i = 0;i < n;i++) {
ans += min(mn * 2, a[i]) * (n - i - 1);
}
cout << 4 * ans << '\n';
}
|