CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)(A - E)
CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)
A. MEXanized Array(分类讨论)
可以发现当 n < k 或者 k > x + 1 的时候无法构成 , 其余的时候贪心的用 x 最大化贡献即可 , 注意特判 k == x 的情况。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , n , k , x; signed main(){IOScin >> t;while(t --) {cin >> n >> k >> x;if(n < k || k > x + 1) {cout << "-1\n";} else {int res = 0;int now = k - 1;res += (now + 1) * now / 2;if(k == x) res += (x - 1) * (n - k);else res += x * (n - k);cout << res << "\n";}}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
B. Friendly Arrays(位运算)
观察或运算发现 , 只有当前位为 1 的时候或运算才能对结果产生影响 , 且是把所有数当前位全部变成 1 , 不妨对 n 的奇偶进行讨论 ,模拟完可以发现这样的一个性质 , 当 n 为奇数的时候操作异或和会变大 , 偶数的时候操作异或和会变小 , 所以最大最小值一定是全操作和全不操作的 , 计算即可。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int n , m , t;
int a[N] , b[N];signed main(){IOScin >> t;while(t --) {cin >> n >> m;int mx = 0 , mn = 0 , k = 0;for(int i = 1 ; i <= n ; i ++) cin >> a[i];for(int i = 1 ; i <= m ; i ++) cin >> b[i] , k |= b[i];for(int i = 1 ; i <= n ; i ++) {mn ^= (a[i] | k);mx ^= a[i];}if(mn > mx) swap(mn , mx);cout << mn << " " << mx << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
C. Colorful Table(思维 ,排序)
不难发现对于每个数来说 , 我们要找大于等于本身的最靠左的位置和最靠右的位置 , 考虑按照值的大小升序排序 , 这样问题就转化成找排序后每个值右边序号的最大值和最小值 , 逆序扫一遍 , 边扫便维护即可。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , n , k , ans[N];
struct node {int x , id;
}a[N];signed main(){IOScin >> t;while(t --) {cin >> n >> k;for(int i = 1 ; i <= n ; i ++) {cin >> a[i].x ;a[i].id = i;}sort(a + 1 , a + 1 + n ,[&](node a, node b){return a.x < b.x;});int mx = -9e18 , mn = 9e18;for(int i = n ; i >= 1 ; i --){int now = a[i].x;int id = a[i].id;mx = max(mx , id);mn = min(mn , id);ans[now] = (mx - mn + 1) * 2;}for(int i = 1 ; i <= k ; i ++) {cout << ans[i] << " ";ans[i] = 0;}cout << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
D. Prefix Purchase(贪心)
首先不难想到,贪心的取次数最多且最靠右的位置 , 但这样显然不是最优的 , 因为有
3 4 5
11
这种情况 , 我们可以通过替换的方式更充分的利用余数 ,转化一下不难发现如何利用余数的问题和开始要求的问题是一样的(选 4 还是选 5去替换 3 就相当于 k = 2 时 , 选 1 还是 选 2 能让字典序变大) , 不断贪心的选把余数用完即可.
例如 :
3 4 5
11
第一次贪心之后会变成
0 1 2
2
第二次贪心之后会变成
0 0 1
0
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , n , k;
int a[N] , pre[N] , b[N];signed main(){IOScin >> t;while(t --) {cin >> n;pre[0] = 0;for(int i = 1 ; i <= n ; i ++) cin >> a[i] , pre[i] = 0;cin >> k;int id = 0;while(k && id != -1) {int maxx = 0 , id1 = -1;for(int i = n ; i >= id + 1 ; i --) {if((k / a[i]) > maxx) {maxx = k / a[i];id1 = i;} }k -= maxx * a[id1];for(int i = n ; i >= id1 + 1 ; i --) {a[i] -= a[id1];}pre[id] += maxx;pre[id1] -= maxx;id = id1;}int sum = 0;for(int i = 1 ; i <= n ; i ++) {sum += pre[i - 1];cout << sum << " ";}cout << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
E. Another MEX Problem(dp)
先考虑 O(n^3) 的解决方法
d p [ i ] [ j ] 表示前 i 个数是否能表示出 j dp[i][j] 表示前 i 个数是否能表示出 j dp[i][j]表示前i个数是否能表示出j
考虑转移
若当前位不选进区间 dp[i][j] = dp[i - 1][j];
若当前位选进区间 , 枚举以当前位为右边界的区间 , 进行转移
dp[i][j] |= dp[l - 1][j ^ mex[l][i]]
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 5e3 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , n ;signed main(){IOScin >> t;while(t --) {cin >> n; vector<int>a(n + 1);for(int i = 1 ; i <= n ; i ++) {cin >> a[i];}vector<vector<int>>mex(n + 1 , vector<int>(n + 1));vector<vector<bool>>dp(n + 1 , vector<bool>(1 << 13));for(int i = 1 ; i <= n ; i ++) {int now = 0;vector<bool>vis(n + 1);for(int j = i ; j <= n ; j ++) {vis[a[j]] = 1;while(vis[now]) now += 1;mex[i][j] = now; }}dp[0][0] = 1;for(int i = 1 ; i <= n ; i ++) {//从上一位自然转移dp[i] = dp[i - 1]; for(int l = 1 ; l <= i ; l ++) {for(int k = 0 ; k < (1 << 13) ; k ++) {if(dp[l - 1][k]) dp[i][k ^ mex[l][i]] = 1;}}}int res = 0;for(int i = 0 ; i < (1 << 13) ; i ++) {if(dp[n][i]) res = max(res , i);}cout << res << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
考虑优化:
1:首先对于相同的右边界 , 我们枚举左边界的时候从大到小 , 由于我们是先从大的范围开始枚举 , 所以每个 mex 只更新一次即可。
2.其次对于相同的左边界 , 每个 mex 更新一次即可 。
显然能凑出来的mex的数量级是O(n)的 , 更新次数也是O(n)的
总复杂度
O ( n 2 ) O(n^2) O(n2)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 5e3 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , n ;signed main(){IOScin >> t;while(t --) {cin >> n;vector<int>a(n + 1);for(int i = 1 ; i <= n ; i ++) {cin >> a[i];}vector<vector<int>>mex(n + 1 , vector<int>(n + 1));vector<vector<bool>>dp(n + 1 , vector<bool>(1 << 13));for(int i = 1 ; i <= n ; i ++) {int now = 0;vector<bool>vis(n + 1);for(int j = i ; j <= n ; j ++) {vis[a[j]] = 1;while(vis[now]) now += 1;mex[i][j] = now; }}dp[0][0] = 1;vector<vector<bool>>visl(n + 1 , vector<bool>(1 << 13));vector<vector<bool>>visr(n + 1 , vector<bool>(1 << 13));for(int i = 1 ; i <= n ; i ++) {//从上一位自然转移dp[i] = dp[i - 1];for(int l = i ; l >= 1 ; l --) {if(visr[i][mex[l][i]]) continue;if(visl[l][mex[l][i]]) continue;visl[l][mex[l][i]] = 1;visr[i][mex[l][i]] = 1;for(int k = 0 ; k < (1 << 13) ; k ++) {if(dp[l - 1][k]) dp[i][k ^ mex[l][i]] = 1;}}}int res = 0;for(int i = 0 ; i < (1 << 13) ; i ++) {if(dp[n][i]) res = max(res , i);}cout << res << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);