目录
瞎编乱造第一题
瞎编乱造第二题
瞎编乱造第三题
瞎编乱造第四题
瞎编乱造第五题
不是很想编了但还是得编的第六题
不是很想编了但还是得编的第七题
还差三道题就编完了的第八题
还差两道题就编完了的第九题
太好啦终于编完了
为啥一周六天早八阿
瞎编乱造第一题
因为偶数因子的操作是可逆，所以我们只要匹配奇数因子就可以了
输入的时候我们就把每个偶数元素一直除到奇数
之后我们枚举b数组每一位右移
匹配上就标记一下
如果全匹配上就是Yes，否则就是No
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int a, bb, b[MAXN];
bool vis[MAXN];
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
{
vis[i] = 0;
}
multiset<int> sa;
for (int i = 1; i <= n; ++i)
{
cin >> a;
while ((a & 1) == 0)
{
a >>= 1;
}
sa.insert(a);
}
for (int i = 1; i <= n; ++i)
{
cin >> bb;
while ((bb & 1) == 0)
{
bb >>= 1;
}
b[i] = bb;
}
for (int j = 0; j < 32; ++j)
{
for (int i = 1; i <= n; ++i)
{
if (vis[i])
{
continue;
}
auto it = sa.find(b[i] >> j);
if (it != sa.end())
{
sa.erase(it);
vis[i] = 1;
}
}
}
cout << (sa.empty() ? "YES\n" : "NO\n");
return;
}
signed main(){
int tt;
cin>>tt;
while(tt--){
solve();
}
}瞎编乱造第二题
对区间总体加减可以转化为差分问题
第一个操作可以转化为第一个数差分-1，选一个位置差分+1
第二个操作可以转化为选一个位置差分-1
第三个操作可以转化为第一个数差分加1
我们把所有的差分求出来后，先将从2-n所有差分归零，在将第一个数归零即可
代码如下
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n, m, k;
int a[N], d[N];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int T;
cin >> T;
while (T -- ) {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++) d[i] = a[i] - a[i - 1];
int res = 0;
for (int i = 2; i <= n; i ++)
if (d[i] < 0) {
res -= d[i];
d[1] += d[i];
}
else res += d[i];
res += abs(d[1]);
cout << res << '\n';
}
return 0;
}瞎编乱造第三题
只要从2-n的每个a[i]都是a[1]的倍数即可满足条件
反之则不行
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int T;
int t=1;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a1;
cin>>a1;
int flag=1;
for (int i=2; i<=n; i++)
{
int x;cin>>x;
if (x%a1!=0)flag=0;
}
if(flag==1) cout<<"Yes";
else cout<<"No";
cout << endl;
}
return 0;
}瞎编乱造第四题
当n为奇数时候，先手必胜，因为只要先手第一轮全拿走，第二轮后手就会拿到你的位置，他就输了
当n为偶数时，因为每个人拿的堆是固定的，所以只要看一下谁最少的堆个数少，谁就会先拿完
谁就输了
要是都相等，就是先手输
代码如下
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
std::array<i64, 2> step{};
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
if (n % 2 == 1) {
std::cout << "Mike\n";
return;
}
for (int t = 0; t < 2; t++) {
int min = std::numeric_limits<int>::max();
int j = -1;
for (int i = t; i < n; i += 2) {
if (a[i] < min) {
min = a[i];
j = i / 2;
}
}
step[t] = 1LL * (n / 2) * min + j;
}
if (n % 2 == 1 || step[0] > step[1]) {
std::cout << "Mike\n";
} else {
std::cout << "Joe\n";
}
}
int main() {
// freopen("9.in","r",stdin);
// freopen("9.out","w",stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}瞎编乱造第五题
只要这个字符串的最后两位不相等，这个字符串就一定满足条件
所以只要遍历一遍，找两个不相等的字符，贡献就是遍历到他的索引（这个代码里有解释）
之后再加上n（每个单独的字符串都满足条件）
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
signed main() {
// ios::sync_with_stdio(false), cin.tie(0);
int T;
cin>>T;
while(T--)
{
long long sum = 0;
int n;
scanf("%lld", &n);
string s = " ";
cin >> s;
for(int i = 1; i < n; i++){
if(s[i] != s[i - 1]){
//+ i的原因在于
//以i这个位置的字符结尾的子串恰好是这么多
//↑比如说"1001"的"01"，以他们结尾的子串是"1001" "001" "01"正好对应索引3
//如果末位2字符成立，所有子串都成立，反之亦然
//而这里是没有把"1"和"0"算进去的，他们必然是成立的，所以直接在外面加就行了
sum += i;
}
}
printf("%lld\n", (sum + n));
}
return 0;
}不是很想编了但还是得编的第六题
只要找到x的最低位一并保留即可
如果x只有唯一一位1，答案就要再加1（最低位保留一个1，保证异或大于0）
特判一下1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define INF 0x3f3f3f3f
#define lowbit(x) ((x)&(-x))
const ll MOD = 1000000007;
// const ll MOD = 998244353;
const int N = 500010;
void slove()
{
int n;
cin >> n;
if(n == 1)
{
cout << 3 << '\n';
return;
}
ll ans = lowbit(n);
if(ans != n)
cout << ans << '\n';
else
cout << ans+1 << '\n';
}
int main(void)
{
// freopen("9.in","r",stdin);
// freopen("9.out","w",stdout);
IOS;
int tt = 1;
cin >> tt;
while(tt--)
{
slove();
}
return 0;
}不是很想编了但还是得编的第七题
我们找到一个最先变成奇数的数（如果本来就有奇数，那就不需要这步）
把他变成奇数
之后所有的偶数加上这个奇数变成奇数
代码如下
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
#define lowbit(x) ((x)&(-x))
int a[N];
signed main() {
// ios::sync_with_stdio(false), cin.tie(0);
int T;
cin>>T;
while(T--)
{
int n;
cin >> n;
for(int i=1;i<=n;++i)
{
cin >> a[i];
}
int ans = 0;
for(int i=1;i<=n;++i)
{
if(a[i]&1)
ans++;
}
if(ans)
{
cout << n-ans << '\n';
continue;
}
int minn = 1e9+7;
for(int i=1;i<=n;++i)
{
int tmp = lowbit(a[i]);
int cnt = 0;
while(tmp != 1)
{
tmp/=2;
cnt++;
}
minn = min(minn , cnt);
}
cout << minn+n-1 << '\n';
}
return 0;
}还差三道题就编完了的第八题
就把所有数像山一样排起来就好了，中间大两边小
>2数量的x对答案的贡献是1
（假如这样一个数组，1 1 2 2 3 3 4 4，这样排好之后答案就是4，每个数都有两个以上，每个数都贡献1，排好之后1 2 3 4 4 3 2 1）
其他=1的x对答案贡献是总的这样的数/2上取整
（假如这样一个数组，1 2 3 4 5，排好之后答案是3，因为贡献是5/2上取整，排好之后1 3 5 4 2）
这两组贡献加起来
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
std::map<int, int> cnt;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
if (cnt[x] < 2) {
cnt[x]++;
}
}
int ans = 0, v = 0;
for (auto [x, c] : cnt) {
if (c == 2) {
ans++;
} else {
v++;
}
}
ans += (v + 1) / 2;
std::cout << ans << "\n";
}
int main() {
// freopen("10.in","r",stdin);
// freopen("10.out","w",stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}还差两道题就编完了的第九题
每个陷阱最初的贡献是a[i]-(n-i)，先按这个排好序
（躲掉的伤害减去之后增加的伤害）
接下来考虑陷阱之间相互作用
前面每跳过一个陷阱，后面陷阱躲掉的伤害就+1，贡献也+1
所以是排好序的数组遍历前k个
满足a[i]-(n-i)+(前面跳过的陷阱数)>0这个等式，就可以跳
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
#define lowbit(x) ((x)&(-x))
int a[N];
signed main() {
// ios::sync_with_stdio(false), cin.tie(0);
int T;
cin>>T;
while(T--)
{
long long sum = 0;
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
sum += a[i];
a[i] -= n - i;
}
sort(a + 1, a + 1 + n, greater<long long>());
for (int i = 1; i <= k; ++i)
{
if (a[i] > -i)
{
sum -= a[i] + i - 1;
}
else
{
break;
}
}
cout << sum << '\n';
}
return 0;
}太好啦终于编完了
对于每个前面是>后面是<的位置，把它称之为山谷
也包括第一个<左边的位置和最后一个>右边的位置
我们让每个山谷都是0
之后向两边扩散，每层加1
每个取max就好
代码如下
#include <bits/stdc++.h>
using namespace std;
string a;
int arr[500002]= {0,};
int main()
{
cin>>a;
int n = a.size();
for(int i=0;i<n;i++)
{
if(a[i]== '<')
arr[i+1] = max(arr[i+1],arr[i]+1);
}
for(int i=n-1;i>=0;i--)
{
if(a[i]== '>')
arr[i] = max(arr[i+1]+1,arr[i]);
}
long long sum = 0;
for(int i=0;i<=n;i++)
{
sum += arr[i];
}
cout<<sum;
}
