A.Contest for Robots（贪心）
题意：有n道题。事先知道两个机器人（R，B）分别能答对哪几道。现在要分配每题得分使得机器人R一定能赢（至少1分），问怎么分配使得所有题的最高分最低。
题解：贪心。分别计算R对B错和R错B对的数量，然后把R错B对的题全部设置为1分。所以R对B错的题尽可能平均分且超过R错B对的题数即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
int r[105], b[105];
int main()
{
int n;
scanf("%d", &n);
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; i++)
scanf("%d", &r[i]);
for (int i = 0; i < n; i++)
{
scanf("%d", &b[i]);
if (r[i] > b[i])
cnt1++;
if (r[i] < b[i])
cnt2++;
}
if (cnt1 == 0)
puts("-1");
else
printf("%d\n", cnt2 / cnt1 + 1);
return 0;
}B.Journey Planning
题意：n个地点编号1~n。每个地点有一个美丽指数bi。现在要制定一个浏览顺序使得浏览过的城市的美丽指数之和最大。要求如下（1）浏览顺序必须为严格递增序列（2）相邻浏览的城市必须满足编号的差等于美丽指数的差
题解：bi-bj=i-j，即bi-i=bj-j，将bi转移为bi-i即可，map记录总和，最后扫描一遍取最大值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
map<int, ll> mp;
int main()
{
int n;
scanf("%d", &n);
for (int i = 1, x; i <= n; i++)
{
scanf("%d", &x);
mp[x - i] += 1ll * x;
}
ll ans = 0;
for (auto i : mp)
ans = max(ans, i.second);
printf("%lld\n", ans);
return 0;
}C.Remove Adjacent
题意：给定一个小写字母字符串。具体操作规则如下：若一个字母的相邻字母为它字典序中的前一个字母，则可以将这个字母删除。问最多能操作几次。
题解：注意到字符串长度仅100，所以暴力解决。顺序从z扫描到a。每次删除一个字母后记得重新扫描一遍即可。理论上最坏复杂度10010026
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
map<int, ll> mp;
int main()
{
int n;
scanf("%d", &n);
string s;
cin >> s;
bool flag = true;
while (flag)
{
flag = false;
for (char i = 'z'; i > 'a'; i--)
{
for (int j = 0; j < s.length(); j++)
if (s[j] == i)
if ((j > 0 && s[j - 1] == i - 1) || (j + 1 < s.length() && s[j + 1] == i - 1))
{
s.erase(s.begin() + j);
flag = true;
break;
}
if (flag)
break;
}
}
printf("%d\n", n - s.length());
return 0;
}D.Navigation System
题意：给定一个单向图和一个规划完的s~t路径。有一个导航仪会实时显示当前点到t的最短路径（但并不会已经规划完的路径产生影响）。如果规划的路径和导航路径不同，那么走到下一个点后，导航仪会重新规划路径。问导航仪最少和最多重新规划几次。
题解：
设p为规划路径。dis[p[i]]为p[i]~t的最短距离。导航仪在如下几种情况下会重新规划：
（1）dis[p[i]]-1≠dis[p[i+1]]。即一定不是最短路径。
（2）存在一个不为p[i+1]的点w使得dis[p[i]]-1=dis[w]。即存在一条其他的路径为最短路径。
不难发现如果第一种情况发生，那么第二种情况一定存在。所以满足第一条即为最少的规划次数，满足第二条的即为最多的规划次数。
对于dis数组的获得逆向bfs一下即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
vector<int> G1[maxn], G2[maxn];
int p[maxn], dis[maxn];
int n, m, k;
void bfs(int s)
{
queue<int> q;
memset(dis, INF, sizeof(dis));
q.push(s);
dis[s] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
for (auto v : G2[u])
{
if (dis[v] == INF)
{
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
G1[x].push_back(y);
G2[y].push_back(x);
}
scanf("%d", &k);
for (int i = 1; i <= k; i++)
scanf("%d", &p[i]);
bfs(p[k]);
int ans1 = 0, ans2 = 0;
for (int i = 1; i < k; i++)
{
int u = p[i], v = p[i + 1];
if (dis[u] - 1 != dis[v])
ans1++;
for (auto j : G1[u])
{
if (j != v && (dis[u] - 1) == dis[j])
{
ans2++;
break;
}
}
}
printf("%d %d\n", ans1, ans2);
return 0;
}E.World of Darkraft: Battle for Azathoth（二维偏序+线段树）
题意：有n把武器，m件防具，p只怪物，每把武器有攻击值ai和价格cai，每件防具有防御值bi和价格cbi，怪物有防御值xi、攻击值yi和奖励zi。勇者可以(必须)选择购买一把武器和一件防具，当勇者的攻击值大于怪物的防御值且勇者防御值大于怪物攻击值，则勇者可以击杀这只怪物并获得其对应的奖励。勇者可以击杀多只怪物，每只怪物只能被击杀一次。求勇者能获得的最大收益(打怪奖励-武器价格-防具价格)。
题解：
二维偏序，可以先按武器的攻击值从小到大排序，怪物的防御值从小到大排序，那么对于每把武器，利用双指针可以求出所有防御值比这把武器攻击值低的怪物
然后考虑防具和怪兽的攻击值也就是第二维，首先先定义lb数组，lb[i]表示所选防具至少为i的最少花费
可以发现如果选到防御值为i的防具，那么所有当前可以打败的怪兽中，只要攻击值小于i都可以累加到答案中那么考虑mx[i]表示维护防御值最大为i的最大获利（包含防具的开支，武器的开支在最后计算）对于一只新增的怪兽只要i大于其防御值，那么mx[i]都可以加上这只怪兽的获利，而这可以用线段树来维护
线段树内存的值为防御值至少为i的最大获利
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int MAXN = 1e6 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
int n, m, p;
ll lb[MAXN], ans, mxb;
struct tool
{
ll f, cost;
bool operator<(const tool &C) const
{
return f < C.f;
}
} a[maxn], b[maxn];
struct monsters
{
ll x, y, z;
bool operator<(const monsters &C) const
{
return x < C.x;
}
} c[maxn];
struct node
{
ll sum, lazy;
} tr[MAXN << 2];
void pushup(int rt)
{
tr[rt].sum = max(tr[rt << 1].sum, tr[rt << 1 | 1].sum);
}
void pushdown(int rt)
{
if (tr[rt].lazy != 0)
{
tr[rt << 1].sum += tr[rt].lazy;
tr[rt << 1].lazy += tr[rt].lazy;
tr[rt << 1 | 1].sum += tr[rt].lazy;
tr[rt << 1 | 1].lazy += tr[rt].lazy;
tr[rt].lazy = 0;
}
}
void build(int l, int r, int rt)
{
if (l == r)
{
tr[rt].sum = -lb[l];
return;
}
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
pushup(rt);
}
void update(int rt, int l, int r, int L, int R, int val)
{
if (L <= l && r <= R)
{
tr[rt].sum += val;
tr[rt].lazy += val;
return;
}
pushdown(rt);
int mid = l + r >> 1;
if (L <= mid)
update(rt << 1, l, mid, L, R, val);
if (R > mid)
update(rt << 1 | 1, mid + 1, r, L, R, val);
pushup(rt);
}
int main()
{
scanf("%d%d%d", &n, &m, &p);
for (int i = 1; i <= n; i++)
scanf("%lld%lld", &a[i].f, &a[i].cost);
for (int i = 1; i <= m; i++)
scanf("%lld%lld", &b[i].f, &b[i].cost);
for (int i = 1; i <= p; i++)
scanf("%lld%lld%lld", &c[i].x, &c[i].y, &c[i].z);
sort(a + 1, a + n + 1);
sort(c + 1, c + p + 1);
for (int i = 1; i <= m; i++)
mxb = max(mxb, b[i].f);
for (int i = 1; i <= mxb; i++)
lb[i] = INF;
for (int i = 1; i <= m; i++)
lb[b[i].f] = min(lb[b[i].f], b[i].cost);
for (int i = mxb - 1; i >= 1; i--)
lb[i] = min(lb[i], lb[i + 1]);
ans = -INF;
build(1, mxb, 1);
for (int i = 1, j = 1; i <= n; i++)
{
while (c[j].x < a[i].f && j <= p)
{
if (c[j].y < mxb)
update(1, 1, mxb, c[j].y + 1, mxb, c[j].z);
j++;
}
ans = max(ans, -a[i].cost + tr[1].sum);
}
printf("%lld\n", ans);
return 0;
}
京公网安备 11010502036488号