题目大意
给定两个三位整数$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;
}
|
题目大意
有$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
有三个点$(0,0)$、$(1,2)$、$(2,1)$。
有$2$对符合条件的点。
样例输入2
样例输出2
只有$1$个点，无法组成对，输出$0$。
样例输入3
1
2
3
4
5
6
7
8
9
10
11
| 10
-31 -35
8 -36
22 64
5 73
-14 8
18 -58
-41 -85
1 -88
-21 -85
-11 82
|
样例输出3
分析
$(x_1,y_1)$到$(x_2,y_2)$的斜率是$\frac{y_1-y_2}{x1-x2}$。
推理过程：
$$-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;
}
|
题目大意
给你$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
$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
没有符合条件的字符串。
分析
如果暴力去枚举两个字符串（如，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;
}
|
题目大意
题目大意略，请自行前往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
2
3
4
5
| 4
2 1
2 2
5 1
1 3
|
样例输出1
Takahashi在第三个城市演讲后，Aoki和Takahashi将分别得到$5$和$6$个投票。
样例输入2
1
2
3
4
5
6
| 5
2 1
2 1
2 1
2 1
2 1
|
样例输出2
在任意三个城市演讲后，Aoki和Takahashi将分别得到$4$和$9$个投票。
样例输入3
样例输出3
分析
换句话说，我们的目的就是使得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;
}
|