2023年ACM竞赛班 2023.3.20题解

 目录

瞎编乱造第一题

瞎编乱造第二题

瞎编乱造第三题

瞎编乱造第四题

瞎编乱造第五题

不是很想编了但还是得编的第六题

不是很想编了但还是得编的第七题

还差三道题就编完了的第八题

还差两道题就编完了的第九题

太好啦终于编完了

---

为啥一周六天早八阿

瞎编乱造第一题

因为偶数因子的操作是可逆，所以我们只要匹配奇数因子就可以了

输入的时候我们就把每个偶数元素一直除到奇数

之后我们枚举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';elsecout << 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;
}