您现在的位置是:首页 > 正文

安大计算机学院ACM,【题解】2019年安徽大学ACM/ICPC实验室新生赛

2024-02-01 02:05:18阅读 2

2019年安徽大学ACM/ICPC实验室新生赛题解

A. 素数分布

对于给定的

equation?tex=n(n%5Cle%201000)&preview=true,求出不超过

equation?tex=n&preview=true 的素数的个数。

卡掉了最最暴力的做法,但是你只需要记录一个1000以内的素数表,然后每次在这个素数表里面统计就不会超时了。

#include

using namespace std;

int main() {

vector isPrime(1001);

isPrime[2] = true;

for (int i = 3; i <= 1000; i++) {

int sqt = sqrt(i);

bool flag = true;

for (int j = 2; flag && j <= sqt; j++)

if (i % j == 0) flag = false;

if (flag) isPrime[i] = true;

}

int T;

cin >> T;

while (T--) {

int n;

cin >> n;

int ans = 0;

for (int i = 2; i <= n; i++)

if (isPrime[i]) ans++;

cout << ans << endl;

}

return 0;

}

难度定位:codeforces rating 800

B.食物分配

给定四个正整数,判断这四个正整数能否被恰好划分成三组,每一组数的和相等。

设这四个数分别为

equation?tex=A%2CB%2CC%2CD(A%5Cle%20B%5Cle%20C%5Cle%20D)&preview=true,如果满足划分条件,则必然有

equation?tex=A%2BB%3DC&preview=true

equation?tex=C%3DD&preview=true,因此只需要对这四个数排序后判断即可。

#include

using namespace std;

int main() {

int T;

cin >> T;

while (T--) {

vector nps(4);

for (auto& i : nps) cin >> i;

sort(nps.begin(), nps.end());

if (nps[0] + nps[1] == nps[2] && nps[2] == nps[3])

cout << nps[2] << endl;

else

cout << -1 << endl;

}

return 0;

}

难度定位:codeforces rating 1000

C.AHUICPC(Easy Version)

询问只会有10种情况(1到10),其中只有10的情况下暴力构造的长度会超过15,对于这种情况只需要2个A和5个H就可以构造出10个子序列"AH",然后再后面补"UICPC"即可。

#include

using namespace std;

int main() {

int n;

cin >> n;

if (n <= 9) {

for (int i = 0; i < n; i++) cout << 'A';

cout << "HUICPC\n";

} else {

cout << "AAHHHHHUICPC\n";

}

return 0;

}

难度定位:codeforces rating 800

D.不定方程

根据题意,

equation?tex=c_%7Bmin%7D&preview=true 即为

equation?tex=a%2Cb&preview=true 的最小公倍数

equation?tex=a%5Ccdot%20b%2Fgcd(a%2Cb)&preview=true,于是有

equation?tex=x%3Db%2Fgcd(a%2Cb)%2Cy%3Da%2Fgcd(a%2Cb)&preview=true 。可见

equation?tex=x%2Cy&preview=true 一定是互质的,即

equation?tex=gcd(x%2Cy)%3D1&preview=true。而此时只需要令

equation?tex=a%3Dy%2Cb%3Dx&preview=true 即可构造出答案。

注意因为

equation?tex=x%2Cy&preview=true 最大会到

equation?tex=10%5E5&preview=true,所以两者之积有可能超过int的范围。

#include

using namespace std;

int main() {

int T;

cin >> T;

while (T--) {

long long x, y;

cin >> x >> y;

if (__gcd(x, y) != 1)

cout << -1 << endl;

else

cout << y << ' ' << x << ' ' << x * y << endl;

}

return 0;

}

难度定位:codeforces rating 1400

E.蕊蕊识数

因为数据量极大,所以直接用python暴力计算是会超时的。

注意到对于任意的

equation?tex=10%5Ek%20(k%5Cge%200%20%E4%B8%94%E4%B8%BA%E6%95%B4%E6%95%B0)&preview=true ,其被3除的余数都是1,因此

equation?tex=a%5Ccdot%2010%5Ek&preview=true

equation?tex=a&preview=true 对3同余。

任何十进制非负整数都可以表示成

equation?tex=%5Csum%7Ba_i%5Ccdot%2010%5Ek%7D&preview=true 的多项式形式,其中

equation?tex=a_i&preview=true 恰好是该十进制数的各个数位。因此任意十进制非负整数被3除的余数,都等于将它的各个十进制位的数相加后被3除的余数。换而言之,3满足所有情况的

equation?tex=m&preview=true,而比3小的可能的答案只有2。

所以只需要判断一下2是否是答案,如果不是输出3即可。

#include

using namespace std;

int main() {

int T;

cin >> T;

int _max = 0;

while (T--) {

string str;

cin >> str;

int num = 0;

for (auto &i : str) num += i - '0';

int check = (str.back() - '0') % 2;

bool flag = true;

while (num >= 10) {

if (num % 2 != check) {

flag = false;

break;

}

str = to_string(num);

num = 0;

for (auto &i : str) num += i - '0';

}

if (flag && num % 2 == check)

cout << 2 << endl;

else

cout << 3 << endl;

}

return 0;

}

python的AC代码

T = int(input())

while T:

T -= 1

n = input()

check = int(n[-1]) % 2

n = sum([int(i) for i in n])

flag = True

while n > 9:

if n % 2 != check:

flag = False

break

n = str(n)

n = sum([int(i) for i in n])

if flag and n % 2 == check:

print(2)

else:

print(3)

难度定位:codeforces rating 1700

F.蕊蕊乘车去上学

题目所求即为等车的时间期望,我们设该期望为

equation?tex=p_a%5Ccdot%20a%2Bp_b%5Ccdot%20b&preview=true,其中

equation?tex=p_a&preview=true 表示遇到发车间隔为

equation?tex=a&preview=true 的公交车的概率,

equation?tex=p_b&preview=true 表示遇到发车间隔为

equation?tex=b&preview=true 的公交车的概率。

注意到这个概率是时间上的概率,假设一辆公交车刚刚离开,那么距离下一辆公交车到达需要

equation?tex=t(t%5Cin%20%5C%7Ba%2Cb%5C%7D)&preview=true 分钟,而在这段时间内等车遇到的公交车的发车间隔都是

equation?tex=t&preview=true。由于两种发车间隔出现的可能性是相等的,因此遇到的公交车发车间隔是

equation?tex=a&preview=true 的概率为

equation?tex=a%2F(a%2Bb)&preview=true,遇到的公交车发车间隔是

equation?tex=b&preview=true 的概率为

equation?tex=b%2F(a%2Bb)&preview=true。最终的答案是

equation?tex=(a%5E2%2Bb%5E2)%2F(a%2Bb)&preview=true

#include

using namespace std;

int main() {

int a, b;

cin >> a >> b;

cout << fixed << setprecision(2) << (double)(a * a + b * b) / (a + b) << endl;

return 0;

}

难度定位:codeforces rating 1600

G.AHUICPC(Hard Version)

我们令

equation?tex=n%3D%5Csum%7Ba_i%5Ccdot%20b_i%7D&preview=true,且

equation?tex=b_i%5Cle%20b_%7Bi%2B1%7D&preview=true,如果我们构造出所有的恰好有

equation?tex=a_i%5Ccdot%20b_i&preview=true 个“AH”的字符串,并且它们之间互不影响,然后再在其后面接上"UICPC",那么就可以得到答案。且长度为

equation?tex=sqrt(n)&preview=true 数量级。

事实上我们每一次都用

equation?tex=a_i&preview=true 个A和

equation?tex=b_i&preview=true 个H来构造,由于我们保证了

equation?tex=b_i%5Cle%20b_%7Bi%2B1%7D&preview=true,所以我们可以把较小的

equation?tex=i&preview=true 放在后面,把较大的

equation?tex=i&preview=true 放在前面,这样我们可以重复利用较小的

equation?tex=i&preview=true 的“H”。更形象地说,我们先取最后一项

equation?tex=a_i%5Ccdot%20b_i&preview=true,此时会有

equation?tex=a_i&preview=true 个A和

equation?tex=b_i&preview=true 个H,接下来考虑前一项

equation?tex=a_%7Bi-1%7D%5Ccdot%20b_%7Bi-1%7D&preview=true,我们在恰好其后有

equation?tex=b_%7Bi-1%7D&preview=true 个H的位置插入

equation?tex=a_%7Bi-1%7D&preview=true 个A。如此不断重复。

#include

using namespace std;

vector> res;

int main() {

int num;

cin >> num;

while (num > 0) {

int tmp1 = sqrt(num), tmp2 = num / tmp1;

while (tmp1 * tmp2 <= num) {

tmp2++;

}

while (tmp1 * tmp2 > num) {

tmp2--;

}

res.push_back(make_pair(tmp1, tmp2));

num -= tmp1 * tmp2;

}

string str = "UICPC";

res.push_back(make_pair(0, 0));

for (int i = 0; i < res.size() - 1; i++) {

for (int j = 0; j < res[i].second; j++) {

str = "H" + str;

}

for (int j = 0; j < res[i].first - res[i + 1].first; j++) {

str = "A" + str;

}

}

cout << str << endl;

return 0;

}

难度定位:codeforces rating 1900

H.无尽大军

抽象来说,对于起始的数字1,可以消耗2使其翻倍,即乘以2;而后既可以选择消耗2使其再乘以2,也可以消耗1使得上一次乘以

equation?tex=x&preview=true 的操作变为乘以

equation?tex=x%2B1&preview=true

因此对于

equation?tex=n&preview=true,我们的操作其实是构造一个等式

equation?tex=a_1%5Ccdot%20a_2%5Ccdot%20a_3%5Ccdots%20a_m%3Dn&preview=true,而操作的总消耗即等于

equation?tex=%5Csum%20a_i&preview=true

不难发现对于最小的总消耗,

equation?tex=a_1%2Ca_2%2Ca_3%2C%5Ccdots%20%2Ca_m&preview=true 恰好为

equation?tex=n&preview=true 的全体质因数,因此将

equation?tex=n&preview=true 质因数分解之后把所有因子相加即可得到答案。

#include

using namespace std;

vector> res;

int main() {

long long n;

cin >> n;

long long sqt = sqrt(n);

long long ans = 0;

for (long long i = 2; i <= sqt; i++) {

while (n % i == 0) {

ans += i;

n /= i;

}

}

if (n != 1) ans += n;

cout << ans << endl;

return 0;

}

难度定位:codeforces rating 2000

网站文章