A. Integer Moves

解题思路

本题只存在三种情况:

  1. 给出点为(0,0)本身,则只需要0
  2. 给出点与(0,0)的距离为整数,则只需要1
  3. 给出点与(0,0)的距离不为整数的情况下,只需要2

对于第3种情况: 第1步移到原点的水平或垂直方向,第2步移到原点

Code

void solve() 
{
    int x, y;   cin >> x >> y;
    int s = sqrt(x * x + y * y);
    
    if (x == 0 && y == 0) puts("0");
    else if (s * s == x * x + y * y) puts("1");
    else puts("2");
}

B. XY Sequence(贪心)

题目大意

给定$n,b,x,y(x,y > 0)$,
对于$a[i]$可以赋值为$a[i-1] + x或者a[i - 1] - y$,但要满足$a[i] \le b$$(a[0] = 0)$。
要我们最大化数组$a$的元素和

解题思路

贪心即可,对于在不超过$b$的情况下我们可以选择一直加$x$, 超过的话就减$y$

Code

void solve()
{
    int n, b, x, y;	cin >> n >> b >> x >> y;
    
    int last = 0, res = 0;  // 不用开数组,直接两个变量记录
    for (int i = 1; i <= n; i++)
    	if (last + x <= b)	last += x, res += last;
    	else last -= y, res += last;
    
    cout << res << endl;
}

C. Bracket Sequence Deletion (模拟\规律)

题目大意

题意:现有一括号串。对于其每个前缀,若以下之一满足:

  • 它是合法括号串
  • 它是长度至少为2的回文串

则删去之。若同时有多个满足,只删去最小的前缀,然后继续以下操作,直到任意前缀都不满足要求。
问:进行了几次删除?最终剩余多少字符?

解题思路

首先我们观察长度为2的括号序列,((,(),))这三种情况都可消除,只有)(需要进行讨论
对于)(这种情况,假设后面出现了一个),则构成)(),因为是回文串,所以可以消除,
如果后面是(则不可删除

OS:感觉就是个找规律题,不过自己的做法并不是最优的,在p佬那里看到一个更优美代码,这里呈现一下

Code

void solve() 
{
    int n, res = 0;	string s;
    cin >> n >> s;
        
    vector<char> v;
    for (auto c : s)
    {
        v.push_back(c);
        if (v.size() == 1)	continue;
        if (*v.begin() == '(' || *v.begin() == v.back())	v.clear(), res++;
    }
    cout << res << ' ' << v.size() << endl;
}

D. For Gamers. By Gamers. (dp/二分)

题目大意

你有 $C(C \le 106)$个硬币来招募士兵攻打魔王,有 $n(n \le 3 * 105)$ 种士兵,招募一个第 $i$ 个士兵需要$cost[i]$个硬币,其攻击力为$d[i]$ 血量为 $h[i]$。但是招募的时候,只能招募一种士兵(可以招募多个同一个种士兵)。

有多个询问,每个询问给出魔王的攻击力$D$和血量 $H$,问你能否招募士兵击败魔王,并且使得没有士兵去世。

解题思路

对于魔王,它只要杀死一个士兵即胜利,即需要$\frac{h[i]}$秒,
而对于士兵,士兵是同时攻击的,因此我们可以把攻击力叠加,看为一个整体,
设有$k$个士兵,则它们击杀魔王需要$\frac{k * d[i]}$秒
为了保证士兵全部存活,我们需要让$\frac{k * d[i]} < $ $\frac{h[i]}$
移项 => $k * d[i] * h[i] > H * D$, 对于前面这个式子,只有$k$是变量,其他都为固定值, $k$这时可以理解为倍数,因此进行倍数遍历
我们可以将$d[i] * h[i]$看为整体$val$, 并另外构建新数组,记为$maxv[i] = k * d[i] * h[i]$, 含义为“花费$i$个金币可以得到的最大$val$"
如果士兵的$val$大于魔王的$val$,则可以保证战胜魔王的情况下全部存活

Problem1: 为什么最后是upper_bound而不是lower_bound?
Answer1: 因为lower_bound会找到魔王和士兵同时攻击的状态,这样魔王和士兵都会G

Problem2: 如何理解倍数遍历?
Answer2: 比如第1种类型士兵需要2元,第2种类型士兵需要4元,其他条件理想化,
现我们一共有4元钱,我们可以选择买2只第1种类型士兵或者买1只第2种类型士兵。
也就是通过maxv = max(maxv[2 * cost[1], maxv[cost[1]])这种方式来得到花同样价钱下能得到的最高价值

TIPS: 代码中阐述的test2测试数据点击此处

Code

void solve() 
{
	int n, c;	cin >> n >> c;
	for (int i = 1; i <= n; i++)
	{
		cin >> cost[i] >> d[i] >> h[i];
		maxv[cost[i]] = max(maxv[cost[i]], d[i] * h[i]);  // 预处理值
	}
	
	for (int i = 1; i <= c; i++)  // 倍数遍历
		for (int j = i; j <= c; j += i)
			maxv[j] = max(maxv[j], (j / i) * maxv[i]);
		
	
	// 这一步一定要做,因为可能出现花费比他少,但值比它大的情况
	// 否则会WA在第二个点,测试数据已在上面给出
	for (int i = 1; i <= c; i++)  
		maxv[i] = max(maxv[i - 1], maxv[i]);
		
	int m;	cin >> m;
	while (m--)
	{
		int D, H;	cin >> D >> H;
		if (D * H >= maxv[c])	cout << -1 << ' ';  // 如果花了c元还不能打败魔王,就失败了
		else cout << upper_bound(maxv + 1, maxv + 1 + c, D * H) - maxv << ' ';  // 单调序列,直接二分查找
	}
}

TIPS: 如果WA了,那一定是精度问题,本人代码头文件不同

上一篇 下一篇