A - Large Digits

题目大意

给定两个三位整数$A$和$B$，求它们数位和的最大值。
数位和：例如，$123$的数位和是$1+2+3=6$。

$100\le A,B\le 999$

输入格式

$A~~B$

输出格式

一行，即$A$和$B$数位和的最大值。

样例

输入	输出
123 234	9
593 953	17
100 999	27

分析

直接按题目照做即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


#include <cstdio>
#include <algorithm>
using namespace std;

int main(int argc, char** argv)
{
	char a[10], b[10];
	scanf("%s%s", a, b);
	int as = 0, bs = 0;
	for(int i=0; a[i]; i++)
		as += a[i] - '0';
	for(int i=0; b[i]; i++)
		bs += b[i] - '0';
	printf("%d\n", max(as, bs));
	return 0;
}

B - Gentle Pairs

题目大意

有$N$个点，每个点的坐标是$(x_i,y_i)$，$x$坐标互不相同。
有多少对符合“$-1\le斜率\le1$”的点？

$1\le N\le 10^3$
$|x_i|,|y_i|\le 10^3$
$x_i \ne x_j$ ($i < j$)

输入格式

$N$
$x_1~y_1$
$\vdots$
$x_n~y_n$

输出格式

输出答案。

样例

样例输入1

样例输出1

1

2

有三个点$(0,0)$、$(1,2)$、$(2,1)$。

$(0,0)$到$(1,2)$，斜率为$2$；
$(0,0)$到$(2,1)$，斜率为$\frac12$；
$(1,2)$到$(2,1)$，斜率为$-1$。

有$2$对符合条件的点。

样例输入2

样例输出2

1

0

只有$1$个点，无法组成对，输出$0$。

样例输入3

样例输出3

1

11

分析

$$-1 \le \frac{y_1-y_2}{x_1-x_2} \le 1$$$$|\frac{y_1-y_2}{x_1-x_2}| \le 1$$$$\frac{|y_1-y_2|}{|x_1-x_2|}\le 1$$$$|y_1-y_2|\le|x1-x2|$$

这时，就可以写代码了。

代码

枚举所有对点即可。

 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


#include <cstdio>
#include <cmath>
#define maxn 1005
using namespace std;
 
int x[maxn], y[maxn];
 
inline bool slope_check(int x1, int y1, int x2, int y2)
{
	int dx = abs(x1 - x2), dy = abs(y1 - y2);
	return dy <= dx;
}
 
int main(int argc, char** argv)
{
	int n, cnt = 0;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
		scanf("%d%d", x + i, y + i);
	for(int i=0; i<n-1; i++)
		for(int j=i+1; j<n; j++)
			if(slope_check(x[i], y[i], x[j], y[j]))
				cnt ++;
	printf("%d\n", cnt);
	return 0;
}

C - 1-SAT

题目大意

给你$N$个字符串$S_1,S_2,...,S_N$。每个字符串都由小写字母组成，前面有至多$1$个!。
找到$S_1,S_2,...,S_N$中任意一个字符串，使$S$中出现了“!+这个字符串”（没有引号）。如果没有符合条件的字符串，输出satisfiable。

$1\le N\le 10^5$
$1\le |S_i|\le 10$

输入格式

$N$
$S_1$
$\vdots$
$S_N$

输出格式

如果有符合条件的字符串，输出任意一个；
否则，输出satisfiable。

样例

样例输入1

1
2
3
4
5
6
7


6
a
!a
b
!c
d
!d

样例输出1

1

a

$S_1$为a，$S_2$为!a，所以$S_1$符合条件；
$S_5$为d，$S_6$为!d，所以$S_5$也符合条件，输出d也会被判为正确。

样例输入2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


10
red
red
red
!orange
yellow
!blue
cyan
!green
brown
!gray

样例输出2

1

satisfiable

没有符合条件的字符串。

分析

如果暴力去枚举两个字符串（如，a和!a），需要两重循环，复杂度为$\mathcal O(N^2)$（由于字符串太短可以忽略字符串比较），这里$N$最大为$10^5$，所以，枚举法不可用。
我们再考虑$\mathcal O(n\log n)$。
可以每次输入字符串时判断一下，如果它以!开头将它的!后面的内容放入set中，否则将整个字符串放入vector中。最后，循环遍历vector（$\mathcal O(n)$），每次在set中查找这个字符串（$\mathcal O(\log n)$）。总时间复杂度为$\mathcal O(n\log 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


#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

vector<string> v;
set<string> s;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	while(n--)
	{
		string x;
		cin >> x;
		if(x[0] == '!')
			s.insert(x.substr(1));
		else v.push_back(x);
	}
	for(int i=0; i<v.size(); i++)
		if(s.find(v[i]) != s.end())
		{
			cout << v[i] << endl;
			return 0;
		}
	cout << "satisfiable\n";
	return 0;
}

D - Choose Me

题目大意

题目大意略，请自行前往AtCoder查看。
数据范围：
$1\le N\le 10^5$
$1\le A_i,B_i\le 10^9$

输入格式

$N$
$A_1~B_1$
$\vdots$
$A_N~B_N$

输出格式

输出答案。

样例

样例输入1

样例输出1

1

1

Takahashi在第三个城市演讲后，Aoki和Takahashi将分别得到$5$和$6$个投票。

样例输入2

样例输出2

1

3

在任意三个城市演讲后，Aoki和Takahashi将分别得到$4$和$9$个投票。

样例输入3

样例输出3

1

1

分析

换句话说，我们的目的就是使得Aoki和Takahashi的票数差距逐渐减少。
最开始，票数的差距是Aoki票数的和，也就是$\sum\limits_{i=1}^nA_i$。
每去第$i$个城市，差距减少$2A_i+B_i$，因此，我们可以贪心地先前往差距减少多的城市。这一点可以用数组+排序、set、priority_queue三种方法实现（我选择的是priority_queue，set和priority_queue更快一些）。

代码

注意：一定不能忘记使用long long！！！

 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


#include <cstdio>
#include <queue>
using namespace std;

typedef long long LL;

priority_queue<LL> q;

int main(int argc, char** argv)
{
	int n;
	scanf("%d", &n);
	LL diff = 0;
	while(n--)
	{
		LL ao, ta;
		scanf("%lld%lld", &ao, &ta);
		diff += ao;
		q.push(ao + ao + ta);
	}
	int ans = 0;
	while(!q.empty())
	{
		ans ++;
		if((diff -= q.top()) < 0)
		{
			printf("%d\n", ans);
			return 0;
		}
		q.pop();
	}
	return 0;
}