SMU Summer 2023 Contest Round 6
A. There Are Two Types Of Burgers
从0枚举到汉堡的最大个数,取最大值
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin >> T;
while(T--){
int b,p,f,h,c;
cin >> b >> p >> f >> h >> c;
int ans = 0;
for(int i = 0;i <= min(b / 2, p);i ++){
ans = max(ans, i * h + min((b - i * 2) / 2, f) * c);
}
cout << ans << endl;
}
return 0;
}
B. Square Filling
每次要取一个$2 \times 2 $的矩阵,在A中找到这样的矩阵后,在B中也构造出来,最后看A和B是否是相同即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int n,m;
cin >> n >> m;
vector<vector<int>> B(n , vector<int> (m, 0)),A(n,vector<int>(m));
for(int i = 0;i < n;i ++)
for(int j = 0;j < m;j ++)
cin >> A[i][j];
if(A == B){
cout << 0 << endl;
return 0;
}
vector<PII> ans;
for(int i = 1;i < n;i ++){
for(int j = 1;j < m;j ++){
if(A[i][j] == 1 && A[i][j] == A[i - 1][j] && A[i][j - 1] == A[i][j] && A[i][j] == A[i - 1][j - 1]){
B[i - 1][j - 1] = B[i - 1][j] = B[i][j - 1] = B[i][j] = 1;
ans.emplace_back(i ,j );
}
}
}
if(A != B){
cout << -1 << endl;
}else{
cout << ans.size() << endl;
for(auto [x,y] : ans){
cout << x << ' ' << y << endl;
}
}
return 0;
}
C. Gas Pipeline(动态规划)
\(dp[i][0/1]\)表示当前柱子为低/高柱子时的最小花费
若当前为十字路口,则它的右边一定是高柱子
若当前为普通路口,则它的右边可以是高柱子也可以是低柱子
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin >> T;
while(T--){
int n,a,b;
string s;
cin >> n >> a >> b >> s;
s = " " + s;
vector<vector<int> > dp(n + 1, vector<int>(2,0x3f3f3f3f3f3f));
dp[0][0] = b;
for(int i = 1;i <= n;i ++){
if(s[i] == '1'){
dp[i][1] = min(dp[i][1], dp[i - 1][1] + a + 2 * b);
}else{
dp[i][0] = min({dp[i][0], dp[i - 1][0] + a + b, dp[i - 1][1] + 2 * a + b});
dp[i][1] = min({dp[i][1], dp[i - 1][0] + 2 * a + 2 * b, dp[i - 1][1] + a + 2 * b});
}
}
cout << dp[n][0] << endl;
}
return 0;
}
D. Number Of Permutations(容斥原理,数学)
想要直接算出两关键字不升序排序的个数是很很困难的,但是,正难则反!
因此我们可以去算两关键字的升序排序数,若tmp1为第一关键字的升序排序数,tmp2为第二关键字的升序排序数,
再用全排列的情况减去他们就行了,但是如果x和y是同时递增,那么我们就会多减掉他们重复的部分,这时候加上就好了
参考:D. Number Of Permutations(容斥定理)_小菜鸡加油的博客-CSDN博客
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int mod = 998244353;
map<int,int> vis1,vis2;
map<PII,int> mpi;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
vector<int> fac(3e5 + 10,1);
for(int i = 1;i <= (int)3e5 ; i ++)//计算阶乘
fac[i] = fac[i - 1] * i % mod;
int n;
cin >> n ;
vector<PII> Group(n + 1);
for(int i = 1;i <= n;i ++){
cin >> Group[i].first >> Group[i].second;
vis1[Group[i].first]++, vis2[Group[i].second]++;
}
for(int i = 1;i <= n;i ++){//如果有一个元素刚好有n个,那么说明无法组成不排序数列
if(vis1[i] == n || vis2[i] == n){
cout << 0 << endl;
return 0;
}
}
int ans = 0, tmp1 = 1, tmp2 = 1;
for(int i = 1;i <= n;i++){
if(vis1[i])
tmp1 = (tmp1 % mod * fac[vis1[i]] % mod) % mod;
if(vis2[i])
tmp2 = (tmp2 % mod * fac[vis2[i]] % mod) % mod;
}
ans = (tmp1 % mod + tmp2 % mod) % mod;
sort(Group.begin(),Group.end());
bool f = true;
for(int i = 1;i <= n;i ++){//判断x,y是否是同时递增
if(Group[i].second < Group[i - 1].second){
f = false;
break;
}
}
if(f){
for(int i = 1;i <= n;i++)
mpi[Group[i]]++;
int res = 1;
for(auto [x,y] : mpi)
res = (res % mod * fac[y] % mod) % mod;
cout << (fac[n] - ans + res + mod) % mod << endl;
}else
cout << (fac[n] - ans + mod) % mod << endl;
return 0;
}
E. XOR Guessing(交互题)
\(x\)在\(0 \sim 2^{14}-1\)的范围内,所以可以先用\(1\sim100\)的数去得到一个res1,那它的二进制前7位就是x的二进制的前7位,然后第二轮将\(1\sim100\)的数左移7位,这样第二次得到res2它的后7位就是x的二进制的后7位,然后x再去取res2的后七位和res1的前7位就能得到x了
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
signed main() {
// ios::sync_with_stdio(false);cin.tie(nullptr);
int res1,res2;
cout << '?';
for(int i = 1;i <= 100;i ++)
cout << ' ' << i;
cout << endl;
cin >> res1 ;
cout << '?';
for(int i = 1;i <= 100;i ++)
cout << ' ' << (i << 7);
cout << endl;
cin >> res2 ;
int x = 0;
x |= (res2 & ((1 << 7) - 1));
x |= (res1 &(((1 << 7) - 1) << 7));
cout << "! " << x << endl;
return 0;
}
F. Remainder Problem(根号分治)
设置一个整数N,操作1时,对模数\(x\)的所有结果都进行修改,操作2时,若模数\(x < N\),直接查询对应的\(sum[x][y]\),否则就去暴力统计答案
一次操作的最坏时间复杂度为\(\mathcal{O}(max(N, \frac{500000}{N}))\),所以当\(N = \sqrt{500000}\)时,一次操作的时间复杂度最优,这个时候对于操作2可以取\(x = N\),好像\(\sqrt{500000}\)是707来着,不过我这取得750,所以就取小于了,总时间复杂度\(\mathcal{O}(q\sqrt{N})\).
#include <bits/stdc++.h>
using namespace std;
const int N = 750;
int a[N * N],sum[N][N];
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int q;
cin >>q;
while(q--){
int op,x,y;
cin >> op >> x >> y;
if(op == 1){
a[x] += y;
for(int i = 1;i < N;i ++)
sum[i][x % i] += y;
}else{
if(x < N){
cout << sum[x][y] << endl;
}else{
int ans = 0;
for(int i = y;i <= 500000;i += x)
ans += a[i];
cout << ans << '\n';
}
}
}
return 0;
}