A - Century
题目大意
公元\(N\)年在第几个世纪中?
一个世纪是由\(100\)个年份组成的一个区间。如,\(1\)世纪为\([1,100]\)年,\(2\)世纪为\([101,200]\)年,……
\(1\le N\le 3000\)
输入格式
\(N\)
输出格式
将答案输出为一个整数。
样例
\(N\) | 输出 |
---|---|
\(2021\) | \(21\) |
\(200\) | \(2\) |
分析
根据本题条件我们可以推出:公元\(N\)年在世纪\(\lceil \frac N {100}\rceil\)。
代码
#include <cstdio>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
printf("%d\n", n % 100 == 0? n / 100: n / 100 + 1);
return 0;
}
B - 200th ABC-200
题目大意
对于整数\(N\),执行\(K\)次如下操作:
- 如果\(N\)是\(200\)的倍数,将\(N\)除以\(200\)。
- 否则,在\(N\)后面添上\(200\)。(如,\(123\)变为\(123200\))。
\(1\le N\le 10^5\)
\(1\le K\le 20\)
输入格式
\(N~K\)
输出格式
输出最终的\(N\)。
样例
\(N\) | \(K\) | 输出 |
---|---|---|
\(2021\) | \(4\) | \(50531\) |
\(40000\) | \(2\) | \(1\) |
\(8691\) | \(20\) | \(84875488281\) |
分析
本题我们按照题意模拟即可,但我们需要证明答案不会超过\(2^{63}-1\),这样才能使用long long
:
- 任何数\(N\)添上\(200\)都是\(200\)的倍数。证明:一个数只要是\(100\)和\(2\)的公倍数,它就是\(200\)的倍数。\(N\)添上\(200\)后以
00
结尾,就证明了它是\(200\)的倍数。 - 这样,\(N\)每次添上\(200\)后都要除以\(200\),相当于去掉两个零再将\(N\)除以\(2\)。
- 所以,\(N\)每次最多增加一位,还经常减少位数(除以\(200\)),肯定严格小于\(2^{63}\)。
代码
#include <cstdio>
using namespace std;
int main()
{
long long n;
int k;
scanf("%lld%d", &n, &k);
while(k--)
n = n % 200LL == 0LL? n / 200LL: n * 1000LL + 200LL;
printf("%lld\n", n);
return 0;
}
C - Ringo's Favorite Numbers 2
题目大意
给定序列\(A=(A_1,A_2,\dots,A_N)\),找到符合下列条件的所有\((i,j)\):
- \(1\le i < j\le N\);
- \(|A_i-A_j|\)是\(200\)的倍数。
\(2\le N\le 2\times 10^5\)
\(1\le A_i\le 10^9\)
输出格式
\(N\)
\(A_1~A_2~\dots~A_N\)
样例
\(A\) | 输出 |
---|---|
\((123,223,123,523,200,2000)\) | \(4\) |
\((1,2,3,4,5)\) | \(0\) |
\((199,100,200,400,300,500,600,200)\) | \(9\) |
分析
首先,最容易想到的\(\mathcal O(n^2)\)的暴力算法肯定不行,因为\(2\le N\le 2\times 10^5\)。
我们考虑用桶优化:
我们有\(200\)个桶,分别如下:
桶的编号 | 元素\(1\) | 元素\(2\) | 元素\(3\) | 元素\(4\) | …… | 元素除以\(200\)的余数 |
---|---|---|---|---|---|---|
\(0\) | \(0\) | \(200\) | \(400\) | \(600\) | …… | \(0\) |
\(1\) | \(1\) | \(201\) | \(401\) | \(601\) | …… | \(1\) |
\(2\) | \(2\) | \(202\) | \(402\) | \(602\) | …… | \(2\) |
…… | …… | …… | …… | …… | …… | …… |
\(198\) | \(198\) | \(398\) | \(598\) | \(798\) | …… | \(198\) |
\(199\) | \(199\) | \(399\) | \(599\) | \(799\) | …… | \(199\) |
这时,我们发现,每个桶中的每个元素都能与这个同种的其他元素组成一对,所以我们只要在将元素加入桶中前将答案加上桶目前的大小即可。 |
总时间复杂度\(\mathcal O(n)\)。
代码
我们的桶中不需要真正的元素,只需要记录桶的大小即可。
注意:答案的数据类型一定要用long long
!
#include <cstdio>
#define MOD 200
using namespace std;
int cnt[MOD];
int main()
{
int n;
scanf("%d", &n);
long long ans = 0LL;
while(n--)
{
int x;
scanf("%d", &x);
ans += cnt[x %= MOD] ++;
}
printf("%lld\n", ans);
return 0;
}
D - Happy Birthday! 2
题目大意
给定序列\(A=(A_1,A_2,\dots,A_N)\)。你要从中选出两个子序列\(B\)和\(C\)(下标不同,不要求连续),使得\(\sum B\equiv \sum C\pmod{200}\)。
\(2\le N\le 200\)
\(1\le A_i\le 10^9\)
输入格式
\(N\)
\(A_1~A_2~\dots~A_N\)
输出
如果没有合法的\(B\)和\(C\),输出No
。
如果有合法的\(B\)和\(C\),按下列格式输出,其中\(x\)为\(B\)的长度、\(y\)为\(C\)的长度,\(B'\)为\(B\)中元素对应的下标,\(C'\)为\(C\)中元素对应的下标:
\(\text{Yes}\)
\(x~B'_1~B'_2~\dots~B'_x\)
\(y~C'_1~C'_2~\dots~C'_y\)
样例
略,请自行前往AtCoder查看
分析
我们可以证明,只要\(N\ge 8\),那么就一定有解。证明如下:
- \(8\)个元素能组成的子序列有\(2^8-1=255\)种。(每个元素可以选或不选,去掉全不选的情况)
- 根据抽屉原理,我们将这\(255\)种子序列按照他们除以\(200\)的余数分别放入抽屉中,则至少有两个子序列在一个抽屉中,即必定有合法的\(A\)和\(B\)。
当\(N<8\)时,我们暴力枚举所有可能;
当\(N\ge8\)时,我们暴力枚举其中任意\(8\)个元素组成的所有可能即可找到解。
代码
#include <cstdio>
#include <vector>
#define maxn 10
#define MOD 200
using namespace std;
int a[maxn];
vector<int> bkt[MOD];
inline void print(const vector<int>& v)
{
printf("%llu", v.size());
for(int x: v)
printf(" %d", x + 1);
putchar('\n');
}
int main()
{
int n;
scanf("%d", &n);
if(n > 8) n = 8;
for(int i=0; i<n; i++)
scanf("%d", a + i);
int lim = 1 << n;
for(int st=0; st<lim; st++)
{
int s = 0;
vector<int> pos;
for(int i=0; i<n; i++)
if(st >> i & 1)
s = (s + a[i]) % MOD, pos.push_back(i);
if(!bkt[s].empty())
{
puts("Yes");
print(bkt[s]);
print(pos);
return 0;
}
else bkt[s] = pos;
}
puts("No");
return 0;
}
E - Patisserie ABC 2
题目大意
有\(N^3\)个三元组\((i,j,k)\)(\(1\le i,j,k\le N\)),按如下排序:
- \(i+j+k\)小的排在前面。
- 对于\(i+j+k\)相同的三元组,\(i\)小的排在前面,对于\(i\)相同的,\(j\)小的排在前面。
求第\(K\)个\((i,j,k)\)。
\(1\le N\le 10^6\)
\(1\le K\le N^3\)
输入格式
\(N~K\)
输出格式
输出第\(K\)个\((i,j,k)\),用空格分隔。
样例
\(N\) | \(K\) | 输出 |
---|---|---|
\(2\) | \(5\) | \(1~2~2\) |
\(1000000\) | \(1000000000000000000\) | \(1000000~1000000~1000000\) |
\(9\) | \(47\) | \(3~1~4\) |
分析
由于每个三元组的和都不会超过\(3N\),所以我们考虑暴力枚举三元组的和,这样就能快速算出第\(K\)个三元组的和。那么,问题来了:符合\(i+j+k=n\)的三元组\((i,j,k)\)(\(i,j,k\)均不超过\(N\))有多少个?
这可以用容斥原理解决。首先,我们发现,上述问题实际上就是在求如下方程解的个数:
如果我们将问题改成求如下方程解的个数(注意\(n\)和\(N\)的区别):
\[\begin{cases}i+j+k=n\\1\le i,j,k\le n\end{cases} \]这个可以用挡板法解决,在\(n-1\)个位置上任选\(2\)个插入挡板,挡板分开的就是\(i,j,k\),则公式为\(C_{n-1}^2\)。我们设\(f(n)=~\)上述方程解的个数(\(C_{n-1}^2=(n-1)(n-2)\)),则总方程解的个数为\(f(n)\)。
我们考虑一个、两个(不可能有三个)数大于\(N\)的情况,这样\(\begin{cases}i+j+k=n\\1\le i,j,k\le N\end{cases}\)这个方程解的个数就为\(f(n)+3f(n-2N)-3f(n-N)\)。
代码
计算\(f(n)\)时注意特判\(n\le 2\)的情况,否则可能会出现负数!
#include <cstdio>
using namespace std;
using LL = long long;
int n;
inline int max(int x, int y) { return x > y? x: y; }
inline int min(int x, int y) { return x < y? x: y; }
inline LL f(LL n) { return n-- > 2? n * (n - 1LL) >> 1LL: 0LL; }
inline LL count(int s) { return f(s) - 3 * (f(s - n) - f(s - (n << 1))); }
int main()
{
LL k;
scanf("%d%lld", &n, &k);
int lim = n * 3;
for(int sum=3; sum<=lim; sum++)
{
LL cnt = count(sum);
if(k > cnt) { k -= cnt; continue; }
for(int a=1; a<=n; a++)
{
int minb = max(1, sum - a - n), maxb = min(n, sum - a - 1);
if(minb > maxb) continue;
int num = maxb - minb + 1;
if(k <= num)
{
int b = minb + k - 1;
int c = sum - a - b;
printf("%d %d %d\n", a, b, c);
return 0;
}
k -= num;
}
}
return 0;
}
标签:AtCoder,le,return,200,int,题解,Contest,long,输出
From: https://www.cnblogs.com/stanleys/p/18403475/abc200