难得的一次Div4，从头写到尾
A. Division?
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
void mian()
{
int n;
cin >> n;
if (n <= 1399)
cout << "Division 4" << endl;
else if (n <= 1599)
cout << "Division 3" << endl;
else if (n <= 1899)
cout << "Division 2" << endl;
else
cout << "Division 1" << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
mian();
}
}
B. Triple
找三个相同的数然后输出，没有就输出-1
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <unordered_map>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
unordered_map<int, int> t;
void mian()
{
int n;
cin >> n;
t.clear();
bool flag = true;
for (int i = 1; i <= n; i++)
{
int a;
cin >> a;
t[a]++;
if (flag && t[a] >= 3)
{
cout << a << endl;
flag = false;
}
}
if (flag)
cout << -1 << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
mian();
}
}
C. Odd/Even Increments
可以给所有奇数位或偶数位加1，如果能最终把所有数都变成奇数或者偶数，就输出YES
判断当前所有奇数位的数的奇偶性是不是一样，然后判断所有偶数位
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
void mian()
{
int n;
cin >> n;
int a, b, c;
cin >> a >> b;
bool flag = true;
for (int i = 3; i <= n; i++)
{
cin >> c;
if (i & 1)
{
if (a % 2 != c % 2)
flag = false;
}
else
{
if (b % 2 != c % 2)
flag = false;
}
}
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
mian();
}
}
D. Colorful Stamp
可以给连续两张邮票染色，必须染不同的色，可以重复染，但是一次必须连续两张。
从头到尾扫描一遍，以w分割，每个子串中如果有R和B那就是合法的。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
void mian()
{
int n;
string s;
cin >> n >> s;
int b = 0, r = 0;
bool flag = true;
for (int i = 0; i < n; i++)
{
if (s[i] == 'W')
{
if (b == 0 && r != 0 || b != 0 && r == 0)
flag = false;
b = 0, r = 0;
}
else if (s[i] == 'B')
{
b++;
}
else if (s[i] == 'R')
{
r++;
}
}
if (b == 0 && r != 0 || b != 0 && r == 0)
flag = false;
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
mian();
}
}
E. 2-Letter Strings
题意：给n个长度为2字符串，找出多少对同一个位置字符相同，另一个位置字符不同的字符串。
思路：存一下第一个位置为x的字符中字符y的个数，然后对应相乘，再加到一起。然后第二个字符同理。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 30;
struct node
{
vector<int> num;
node()
{
num.resize(30, 0);
}
};
void mian()
{
node a[N], b[N];
int n;
cin >> n;
string s;
for (int i = 1; i <= n; i++)
{
cin >> s;
a[s[0] - 'a'].num[s[1] - 'a']++;
b[s[1] - 'a'].num[s[0] - 'a']++;
}
ll res = 0;
for (int i = 0; i <= 'k' - 'a'; i++)
{
for (int j = 0; j <= 'k' - 'a'; j++)
{
for (int k = j + 1; k <= 'k' - 'a'; k++)
{
res += 1ll * a[i].num[j] * a[i].num[k];
}
}
}
for (int i = 0; i <= 'k' - 'a'; i++)
{
for (int j = 0; j <= 'k' - 'a'; j++)
{
for (int k = j + 1; k <= 'k' - 'a'; k++)
{
res += 1ll * b[i].num[j] * b[i].num[k];
}
}
}
cout << res << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
mian();
}
}
F. Eating Candies
题意：两人分别从左边右边开始吃糖果，不能跳着吃，问他们想要吃的重量一样，他们一共要吃多少个。
双指针枚举即可
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
void mian()
{
int n;
cin >> n;
vector<int> a(n + 1, 0);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int res = 0, cnt = 0;
int l = 1, r = n;
int alice = 0, bob = 0;
while (l <= r)
{
if (alice == bob)
{
res = cnt;
alice += a[l++];
cnt++;
}
else if (alice > bob)
{
bob += a[r--];
cnt++;
}
else
{
alice += a[l++];
cnt++;
}
}
if (alice == bob)
{
res = cnt;
}
cout << res << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
mian();
}
}
G. Fall Down
有三种东西，.是空气*是石头，o不知道是啥，反正不能掉下来，石头能掉下来，掉到石头上或者o上。
一层一层跑，如果跑一遍没变化就是跑完了，可以退出了。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#define endl '\n'
using namespace std;
const int N = 60;
void mian()
{
int n, m;
string a[N];
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] = " " + a[i];
}
bool flag = true;
while (flag)
{
flag = false;
for (int i = n; i > 1; i--)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] == '.' && a[i - 1][j] == '*')
{
a[i][j] = '*';
a[i - 1][j] = '.';
flag = true;
}
}
}
}
for (int i = 1; i <= n; i++)
{
cout << a[i] << endl;
}
cout << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
mian();
}
}
H. Maximal AND
就是可以给数组中一个数的二进制任意一位变成1，求这一堆数求与最大能变为多少。可以变k次。
存一下所有数的二进制位的每一位到一个数组，如果数组中的那一个达到n了，说明最终的这一位是1，然后k次就贪心的添加，如果全加进去不能到n，那就换低一位的。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
void mian()
{
int a[40] = {0};
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
int t;
cin >> t;
int idx = 0;
while (t)
{
a[idx++] += (t & 1);
t >>= 1;
}
}
for (int i = 30; i >= 0; i--)
{
if (a[i] + k >= n)
{
k -= n - a[i];
a[i] = n;
}
if (k <= 0)
break;
}
int res = 0;
int t = 1;
for (int i = 0; i <= 30; i++)
{
if (a[i] == n)
res += t;
t <<= 1;
}
cout << res << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
mian();
}
}
