题目1
题目链接
题目大意：
有三个长度为n的字符串a、b、c，字符串都是小写字符；
有一个长度为n的模版t，模版会与字符串a、b、c匹配，匹配规则如下：
1、假如模版的字符为小写字母，则对应位置必须是相同字符才算匹配；
2、假如模版的字符为大写字母，则对应位置则不能是相同字符才算匹配；
比如说模板abc和字符串abc是匹配的，模板ABC和字符串def也是匹配的，模板ABC和字符串abc是不匹配的；
现在已知字符串a、b、c，问是否能够构造一个模板t，要求字符串a和b是匹配的，字符串c是不匹配的。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000)
每个样例4行
第一行，整数𝑛(1≤𝑛≤20)，字符串长度
第2、3、4行，分别是字符串a、b、c；
输出：
每个样例第一行，有解则输出YES，无解则输出NO；
Examples
input
4
1
a
b
c
2
aa
bb
aa
10
mathforces
luckforces
adhoccoder
3
acc
abd
abc
output
YES
NO
YES
NO
样例解释：
样例1，直接用模板C
样例3，可以用模板CODEforces
题目解析：
题目的意思比较绕，但是匹配规则还是比较清晰的，可以先简化题目。
先考虑字符串a和b，对于某个位置的字符：
如果a和b相同（假设都是字符x），那么模版可以字符x，也可以是字符X以外的大写字符；
如果a和b相同（假设是字符x和字符y），那么模版必须是字符X、Y以外的大写字符；
我们发现，不管字符串a和b的取值，总是可以找到满足要求的模版；
那么再考虑字符串c，要使得模版至少有一个配置是不匹配的，也就是至少有一个位置，字符串c该位置的字符与前面的都不同。
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string a, b, c;
cin >> a >> b >> c;
int ans = 0;
for (int i = 0; i < n; ++i) if (a[i] != c[i] && b[i] != c[i]) ans = 1;
cout << (ans > 0 ? "YES" : "NO") << endl;
}
}
}
ac;
题目2
题目链接
题目大意：
有n个棍子，长度分别为2^𝑎𝑖；
从这些棍子里面挑出3个，组成一个三角形；
想知道，一共有多少种选择。
（三个棍子，顺序不同算一个组合，比如说1、2、3 和 3、2、1）
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例2行
第一行 整数𝑛，表示n个棍子(1≤𝑛≤20)
第二行 n个整数，𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖≤𝑛 ).
输出：
每个样例第一行，输出能够组合成三角形的数量。
Examples
input
4
7
1 1 1 1 1 1 1
4
3 2 1 3
3
1 2 3
1
1
output
35
2
0
0
题目解析：
先分析题目的数据特点。
由题目知道，三个不同的数字是无法组合成三角；
那么，有且仅有两种可能：
1、三个数字相同；（这种情况就是组合数，C(x, 3) 从x个相同数组中选择3个）
2、两个数字相同，剩下一个更小的数字；
将整数排序，从小到大。情况2的数量，就可以选定当前数字的2个棍子，再乘以前面的所有数字的数量。
typedef long long lld;
class Solution {
static const int N = 301010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
map<int, int> h;
for (int i = 0; i < n; ++i) {
cin >> a[i];
h[a[i]]++;
}
lld ans = 0, sub = 0;
for (map<int, int>::iterator it = h.begin(); it != h.end(); ++it) {
int cnt = it->second;
if (cnt >= 3) {
ans += 1LL * cnt * (cnt - 1) * (cnt - 2) / 6;
}
if (cnt >= 2) {
ans += 1LL * cnt * (cnt - 1) / 2 * sub;
}
sub += cnt;
}
cout << ans << endl;
}
}
}
ac;
题目3
题目链接
题目大意：
有一个整数数组a，数组每个元素的乘积是2023；
数组移除了k个整数，剩下长度为n的数组b；
现在已知数组长度n和数组b，问能否找到原来的数组a。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100)
每个样例2行
第一行，整数𝑛和k (1≤𝑛,𝑘≤5)
第二行，n个整数𝑏1,𝑏2,…,𝑏𝑛(1≤𝑏𝑖≤2023)
输出：
每个样例第一行，无解输出NO，有解输出YES；
如果有解，则第二行再输出被移除的k个整数；
Examples
input
7
2 2
5 2
3 1
7 17 7
4 2
1 289 1 1
3 1
7 17 17
1 1
289
1 1
2023
1 3
1
output
1
1 0
0
0
1
3 0
题目解析：
题目的要求比较明确，当我们给出整数数组b时，假设最终的数组b乘积为m；
m能够被2023整数时，剩余的k个数组就可以是[2023/m, 1， 1， 1】这样的数组来组成。
如果m不能被整数，那么就无解了。
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
int ans = 2023, ok = 1;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
if (ans % x == 0) ans /= x;
else ok = 0;
}
if (ok) {
cout << "YES\n" << ans;
while (k > 1) {
k--;
cout << " " << 1;
}
cout << endl;
}
else {
cout << "NO" << endl;
}
}
}
}
ac;
题目4
题目链接
题目大意：
给出两个整数a和b，现在要找到整数x，满足条件：
1、1≤𝑎<𝑏<𝑥，且1≤𝑥≤1e9；
2、a和b是x的因数，且是因数（x不算）中最大的两个；
比如说12 的因数有 [1,2,3,4,6]，那么a和b就是4和6；
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例一行，整数𝑎 , 𝑏 (1≤𝑎<𝑏≤1e9)
输出：
每个样例一行，输出满足要求的x；（题目保证有解）
Examples
input
8
2 3
1 2
3 11
1 5
5 10
4 6
3 9
250000000 500000000
output
6
4
33
25
20
12
27
1000000000
题目解析：
先从小样例开始分析，容易知道当a=1的时候，答案是b^2；
当a=2的时候
[2, 3]=6
[2, 4]=8
[2, 5]=10
[2, 6]无解；（12的时候，3、4因子更大）
当a=3的时候
[3, 4]=12
[3, 5]=15
[3, 6]无解；（12的时候，因子4更大）
当a=4的时候
[4, 5]=20
[4, 6]=12
[4, 7]=28
[4, 8]=16
[4, 9]无解；（36的时候，因子3x12=36，12更大）
我们发现，有解/无解的时候，与a、b的因子有一个强关联，
比如说[2, 6]无解，实际上6=2x3，那不管乘以任何数字k，都容易产生2 * k、3 * k这样的因子，一定比2要大；
[4, 9]无解，也是同理4=2x2, 9=3x3，理论上的有4、9因子的最小值就是2x2x3x3=36，但是会产生很多较大因子。
比如说有解的时候，大多数值都是最小公倍数。
但是有例外是[2, 4]和[4, 8]，当他们b整除a的时候，最小公倍数是b，但是题目要求是x>b，所以x要乘以一个值k。
下面说明k的取值关系。
假设k=b/a，那么b=k * a, b * (b/a)=b * k=(a * k) * k
假如是b * 2的话，b * 2=a * k * 2，那么因子里面就会多出来一个2 * a，此时如果一旦b/a != 2，那么必会有一个2 * a的因子 大于原来的因子a；
假如是b * (b/a)的话，只会产生一个k * k的因子，a * k是等于b的，并且我们可以知道有解的条件是k * k<a
这样题目的大体思路就有了。
注意：最小公倍数的求法，可以用最大公约数来算。（我自己忘了，竟然尝试用因数分解去做，结果超时了）
typedef long long lld;
class Solution {
static const int N = 201010;
long gcd(lld a, lld b){
if (b==0) return a;
return gcd(b, a%b);
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
int n = a, m = b;
if (m % n == 0) {
// 表示b是a的倍数，此时只需要将m*(m / n)就行
// 假设k=m/n，那么m=k*n, m*(m/n)=m*k=(n*k)*k
// 假如是m*2的话，m*2=n*k*2，那么因子里面就会多出来一个2*n，此时如果一旦m/n != 2，那么必然会有一个2*n的因子 大于原来的因子n；
// 假如是m * (m/n)的话，只会产生一个k*k的因子，n*k是等于m的，并且我们可以知道有解的条件是k*k<n
cout << m * (m / n) << endl;
}
else {
lld ans = a * 1LL * b / gcd(a, b);
cout << ans << endl;
}
}
}
ac;
题目5
题目链接
题目大意：
有n个整数的数组a，现在有Alice和Bob两个人玩游戏，Alice先手。
游戏规则如下：
1、数组中只有一个元素时结束游戏，当前数字为最终结果；
2、每次可以选择数组2个整数，移除对应整数；然后将整数相加再除以2，向下取整，再乘以2，最终将数字重新加回去数组；（比如说[1,3]=4, [2,3]=4)
Alice的目标是让结果尽可能大，Bob的目标是让结果尽可能小。
现在想知道，当只有数组前k个数字参与游戏时（𝑘=1,2,…,𝑛），最终的游戏结果是什么。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例2行
第一行，整数𝑛(1≤𝑛≤1e5)
第二行，n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)
输出：
每个样例一行，共n个整数；第k个数字，表示只有前k个数字参与游戏时，最终的结果。
Examples
input
4
1
31
6
6 3 7 2 5 4
3
3 10 11
5
7 13 11 19 1
output
31
6 8 16 18 22 26
3 12 24
7 20 30 48 50
题目解析：
先不考虑k的取值情况，只看整个数组都参与游戏。
数组中的数字，我们可以分为奇数和偶数，已知偶数+偶数、奇数+奇数的操作只会合并数字，不会有任何变化。只有奇偶数相加，此时最终结果会-1。
这样， 我们假设有x个奇数；
先手每次优先消耗2个奇数，产出1个偶数；
后手每次优先消耗1个奇数+1个偶数，产出1个偶数；（偶数必然存在，因为先手会产出偶数）
这样我们就可以得到一个策略：
n=1，ans=sum（用sum来表示前n项和）
n=2，ans=sum
n=3=2+1，ans=sum-1
n=4=2+1 +1, ans=sum-2
n=5=2+1 +2, ans=sum-1
n=6=2+1 + 2+1, ans=sum-2
n=7=2+1 + 2+1 +1, ans=sum-3
...
依次类推，我们知道3个奇数是一个循环，最终ans= sum - (n + 2) / 3 + ((n + 1) % 3 == 0)
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<lld> ans;
lld sum = 0, cnt = 0;;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
sum += k;
if (k % 2) ++cnt;
if (i == 0) ans.push_back(sum);
else {
ans.push_back(sum - (cnt + 2) / 3 + ((cnt + 1) % 3 == 0));
}
}
for (int i = 0; i < n; ++i) {
cout << ans[i] << " ";
}
cout << endl;
}
}
}
ac;
