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;
}