AtCoder Beginner Contest 249 （A ~ D）

A - Jogging

题意：

两个人跑步， $TakahashiTakahashi$ 以 $BB$ 米每秒跑 $AA$ 秒，然后休息 $CC$ 秒， $AokiAoki$ 以 $EE$ 米每秒跑 $DD$ 秒，然后休息 $FF$ 秒，求 $XX$ 秒时，谁跑得远，输出他的名字，如果一样远就输出 $DrawDraw$

分析：

可以在 $XX$ 秒内循环模拟一下，也可以直接计算得出结果，时间复杂度分别为 $O(X)O(X)$ 和 $O(1)O(1)$

代码：

$O(X)O(X)$ :

#include <bits/stdc++.h>
using namespace std;
int resa, resb;
int main()
{
	int a, b, c, d, e, f, x;
	cin >> a >> b >> c >> d >> e >> f >> x;
	
	for (int i = 0;i < x;i ++)
	{
	    if (i % (a + c) < a) resa += b;
	    if (i % (d + f) < d) resb += e;
	}
	
	if (resa > resb) cout << "Takahashi";
	else if (resa < resb) cout << "Aoki";
	else cout << "Draw";
	
	return 0;
}

$O(1)O(1)$ :

#include <bits/stdc++.h>
using namespace std;
int resa, resb;
int main()
{
	int a, b, c, d, e, f, x;
	cin >> a >> b >> c >> d >> e >> f >> x;
	
	int t1 = x / (a + c), t2 = x / (d + f);
	int r1 = x % (a + c), r2 = x % (d + f);
	
	resa = b * a * t1 + min(r1 * b, a * b);
	resb = e * d * t2 + min(r2 * e, d * e);
	
	if (resa > resb) cout << "Takahashi";
	else if (resa < resb) cout << "Aoki";
	else cout << "Draw";
	
	return 0;
}

B - Perfect String

题意：

满足以下条件的字符串为完美字符串，判断一个字符串是不是完美字符串

• 至少有一个大写英文字母
• 至少有一个小写英文字母
• 字符串中没有相同的英文字母

分析：

遍历一遍字符串，用数组判一下重，再标记一下有没有大小写英文字母

代码：

#include <bits/stdc++.h>
using namespace std;
bool st[200];
int main()
{
	string s;
	cin >> s;
	
	bool fa = false, fb = false;
	for (int i = 0;i < s.size();i ++)
	{
	    if (!st[s[i]])
	    {
	        st[s[i]] = true;
	        if (s[i] >= 'a' && s[i] <= 'z') fa = true;
	        if (s[i] >= 'A' && s[i] <= 'Z') fb = true;
	    }
	    else
	    {
	        cout << "No";
	        return 0;
	    }
	}
	if (fa && fb) cout << "Yes";
	else cout << "No";
	
	return 0;
}

C - Just K

题意：

没读懂！寄！

分析：

代码：

D - Index Trio

题意：

给定一个数组，求有多少三元组 $(i,j,k)(i,\; j,\; k)$ 满足 $A_i=A_j\times A_{k}A\_i\; =\; A\_j\; \backslash times\; A\_k$

分析：

暴力枚举铁定超时，但是我们发现 $AA$ 的范围为 $1\le A\le 2\times 10^{5}1\; \backslash le\; A\; \backslash le\; 2\; \backslash times\; 10^5$，所以可以直接统计 $A_{i}A\_i$ 出现的次数，然后我们依然采取枚举的方法，对于每一个 $A_{i}A\_i$ ，如果要满足以上的条件，可以发现， $A_{j}A\_j$ 可以整除 $A_{i}A\_i$ ，所以我们枚举 $jj$ 的时候可以直接按照 $ii$ 的倍数枚举

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int a[N];
int main()
{
	int n;
	cin >> n;
	for (int i = 1;i <= n;i ++)
	{
	    int t;
	    cin >> t;
	    a[t] ++;
	}
	long long ans = 0;
	for (int i = 1;i < N;i ++)
    {
        for (int j = 1;j * i < N;j ++)
        {
            ans += (long long)a[i] * a[j] * a[i * j];
        }
    }
    
    cout << ans;
	
	return 0;
}