AtCoder Beginner Contest 143
October 23, 2019
前三道签到
A. Curtain
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#define M 1001
using namespace std;
int main()
{
int A, B;
cin >> A >> B;
if (A - B * 2 <= 0)
cout << 0 << endl;
else
cout << A - B * 2 << endl;
return 0;
}
B. TAKOYAKI FESTIVAL 2019
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#define M 101
using namespace std;
int d[M];
int main()
{
int n, sum = 0;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> d[i];
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
sum += d[i] * d[j];
cout << sum << endl;
return 0;
}
C. Slimes
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#define M 101
using namespace std;
int main()
{
int n, tot = 1;
char ch,last;
cin >> n;
cin >> last;
for (int i = 2; i <= n; i++)
{
cin >> ch;
if (ch == last)
continue;
else
{
tot++;
last = ch;
}
}
cout << tot << endl;
return 0;
}
D. Triangles
从一个数组中选三个数，问最多能组成多少个三角形。
本来是很简单的题，先排序，然后枚举两条边，二分查找第三条边就行了，复杂度O(n2log n)，结果二分写了半天，还没考虑到重复的情况，WA了３次，浪费了大量时间，真是醉了。早知道还不如用upper_bound。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#define M 2001
long long L[M];
long long n;
using namespace std;
long long check(long long i, long long j)
{
long long ans = L[i] + L[j] - 1;
long long l = j + 1, r = n;
while (l <= r)
{
long long mid = (l + r) / 2;
if (L[mid] == ans)
{
return mid;
}
else if (L[mid] < ans)
l++;
else
r--;
}
return r;
}
int main()
{
long long tot = 0;
cin >> n;
for (long long i = 1; i <= n; i++)
cin >> L[i];
sort(L + 1, L + n + 1);
for (long long i = 1; i <= n - 2; i++)
for (long long j = i + 1; j <= n - 1; j++)
{
long long num = 0;
long long pos = check(i, j);
for (long long k = 1; k <= n; k++)
if (L[pos] == L[pos + k])
num++;
else
break;
pos += num;
tot += pos - j;
}
cout << tot << endl;
return 0;
}
upper_bound版：代码又少，速度还快，我佛辣。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#define M 2001
long long L[M];
long long n;
using namespace std;
int main()
{
long long tot = 0;
cin >> n;
for (long long i = 1; i <= n; i++)
cin >> L[i];
sort(L + 1, L + n + 1);
for (long long i = 1; i <= n - 2; i++)
for (long long j = i + 1; j <= n - 1; j++)
{
long long tmp = L[i] + L[j] - 1;
long long pos = upper_bound(L + j + 1, L + n + 1, tmp) - L;
pos -= 1;
tot += pos - j;
}
cout << tot << endl;
return 0;
}
E. Travel by Car
考场上没时间想这道题了（虽然感觉有时间也想不出来）。题解的思路非常巧妙，如果要在路上加k次油，那么整条路径被加油点分为了k+1段，因此我们可以把每一段当成一个整体看待。具体的做法是先用Floyd求最短路，然后枚举所有路径，如果这条路径的长度小于等于L，就把它设置为1，如果大于就设置为Inf。然后再跑一遍Floyd，dis[from][to]-1就是加油的次数。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#define M 301
#define MA 1e9+1
using namespace std;
int dis[M][M];
int main()
{
int n, m, l;
cin >> n >> m >> l;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = MA;
for (int i = 1; i <= m; i++)
{
int from, to, cost;
cin >> from >> to >> cost;
dis[from][to] = dis[to][from] = cost;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (dis[i][j] <= l)
dis[i][j] = 1;
else
dis[i][j] = MA;
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int q;
cin >> q;
for (int i = 1; i <= q; i++)
{
int from, to;
cin >> from >> to;
if (dis[from][to] == MA)
cout << -1 << endl;
else
cout << dis[from][to] - 1 << endl;
}
return 0;
}
F. Distinct Numbers
给出一个长度为N的序列，求对于所有k∈[1,N] ，每次从序列中取出k个互不相同的数，最多能取多少次。
首先我们发现数字具体的数值是没有意义的，关键是其出现的次数，所以可以先用一个桶排序计数，然后把出现的次数排序得到数组a。假设取出k个数的操作数为x，那么一共会取出k*x个数。而理论上能取出的数量上限是：对于出现次数小于等于x的数，将其全部取出，对于出现次数大于x的数，每个取x个出来。显然k*x必定小于等于这个上限，我们要找的就是满足这个条件的最大的x，因此可以二分答案，即对于每个x，检查它是否满足这个条件，满足就放大，不满足就缩小。为了寻找a中小于等于x的数的总和，我们可以先求一个前缀和，再在a中二分查找它的位置，最后的复杂度是O(nlog2n)。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#define M (long long)3e5 + 10
using namespace std;
long long cnt[M], a[M], sum[M];
int main()
{
long long n, tot = 0;
cin >> n;
for (long long i = 1; i <= n; i++)
{
long long tmp;
cin >> tmp;
cnt[tmp]++;
}
for (long long i = 1; i <= n; i++)
{
if (cnt[i] != 0)
a[++tot] = cnt[i];
}
sort(a + 1, a + tot + 1);
sum[1] = a[1];
for (long long i = 2; i <= tot; i++)
sum[i] = sum[i - 1] + a[i]; //前缀和
for (long long k = 1; k <= n; k++)
{
long long l = 1, r = n;
while (l <= r)
{
long long mid = (l + r) >> 1;
long long pos = upper_bound(a + 1, a + tot + 1, mid) - a; //返回数组中第一个大于或等于被查数的值的下标
pos--; //小于等于mid的数的个数
if (sum[pos] + (tot - pos) * mid < k * mid)
r = mid - 1;
else
l = mid + 1;
}
cout << r << endl;
}
return 0;
}
About The Author
