Question A:String Similarity
Question: Given a 01 string S with a length of 2n-1, you are required to construct a string with a length of n such that the string is the same as s[1..n], s[2..n + 1] , s[3..n + 2], …, s[n..2n?1]. At least one bit is equal
Solution
Observe that each string has s[n], so you only need to change all the strings to s[n]
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(0); cout. tie(0); cin. tie(0);
int t; cin >> t;
while (t--)
{
int n; cin >> n;
string s; cin >> s;
s = ' ' + s;
for (int i = 1; i <= n; i ++ )
cout<<s[n];
cout << endl;
}
return 0;
}
Question B: RPG Protagonist
The meaning of the question: Two backpacks have different capacities, given the quantity, weight and value of the two items, ask the maximum sum of the two items that can be taken away
Solution
At first I thought it was a backpack. I thought about it for a long time, but the data range is too large. I will know the solution later.
Enumerate the quantity of the first item purchased in the first backpack, then the quantity of the second item purchased in the first backpack is fixed. For the second backpack (first make the weight of the first item the smallest), since only the quantity is considered The most, so buy the one with the smallest weight first, and only buy the second one if the first one is sold out
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int v1, v2, n1, n2, w1, w2;
int num2, num3, num4;
int ans;
signed main()
{
ios::sync_with_stdio(0); cout. tie(0); cin. tie(0);
int t; cin >> t;
while (t--)
{
cin >> v1 >> v2 >> n1 >> n2 >> w1 >> w2;
ans = -9;
if (w1 > w2)swap(n1, n2), swap(w1, w2);
for (int i = 0; i <= n1; i ++ )
{
if (i * w1 > v1)break;
num2 = min(n2, (v1 - i * w1) / w2);
num3 = min(n1 - i, v2 / w1);
num4 = min(n2 - num2, (v2 - num3 * w1) / w2);
ans = max(ans, i + num2 + num3 + num4);
}
cout << ans << endl;
}
return 0;
}
Question C:Binary String Reconstruction
Question C is less difficult than question B, which is a basic mock question
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(0); cout. tie(0); cin. tie(0);
int t; cin >> t;
while (t--)
{
int p = 0;
string s; cin >> s;
int x; cin >> x;
s = ' ' + s;
string s1(s. size() - 1, '1');
s1 = ' ' + s1;
for (int i = 1; i < s. size(); i ++ )
{
if (i - x < 1 & amp; & amp; i + x >= s.size() & amp; & amp; s[i] == '1')
{
p = 1;
break;
}
if (s[i] == '0')
{
if (i - x >= 1)s1[i - x] = '0';
if (i + x < s.size())s1[i + x] = '0';
}
}
for (int i = 1; i < s. size(); i ++ )
{
if (s[i] == '1')
{
int k = 0;
if (i - x >= 1)
if (s1[i - x] == '1')k = 1;
if (i + x < s. size())
if (s1[i + x] == '1')k = 1;
if (!k)
{
p = 1;
break;
}
}
}
if (p)cout << -1 << endl;
else
{
for (int i = 1; i < s.size(); i ++ )cout << s1[i];
cout << endl;
}
}
return 0;
}
Question D:Zigzags
The meaning of the question: Given a sequence a, ask the number of quadruples in sequence a that satisfy the condition
Solution
The four-tuple enumerates the two variables in the middle. For each enumeration, the number of four-tuples that meet the conditions of the current intermediate variable can be obtained from the principle of multiplication. The left side of the first variable in the middle is equal to the value of the second variable in the middle. Quantity * The right side of the second variable in the middle is equal to the value of the first variable in the middle. Note that the size of the number is very small, so you only need to open a prefix quantity array record, from left to right each time to the left of each position All the values of are recorded once, and the number on the right can be obtained by subtracting the prefix
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int num[3030][3030];
int a[3030];
int ans;
int n;
void cal(int x, int y)
{
ans + = num[x - 1][a[y]] * (num[n][a[x]] - num[y][a[x]]);
}
signed main()
{
ios::sync_with_stdio(0); cout. tie(0); cin. tie(0);
int t; cin >> t;
while (t--)
{
cin >> n;
ans=0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
num[i][j] = 0;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
for (int j = 1; j <= n; j ++ )
num[i][a[j]] = num[i - 1][a[j]];
num[i][a[i]] + + ;
}
for (int i = 2; i <= n - 2; i ++ )
for (int j = i + 1; j <= n - 1; j + + )
cal(i, j);
cout << ans << endl;
}
return 0;
}
Similar to this problem, but the solution is different: Acwing triplet
Solution
The difference is that each number is very large. If the number is large but the number is small, we can use unordered_map to record, but the number of questions is also large, so a new method must be considered.
Because we only need to record the number of the previous and next variable of the intermediate variable, we can traverse it from the front to the back, and use unordered_map to record the number of each number each time. If there is an intermediate variable (that is, it can be divisible k), the number of a[i]/k or a[i]*k at this time is the number of its left variable or right variable, which can be recorded with two arrays l[], r[], and finally by the principle of multiplication Calculate it
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int l[N], r[N];
int a[N];
signed main()
{
ios::sync_with_stdio(0); cout. tie(0); cin. tie(0);
int n, k; cin >> n >> k;
unordered_map<int, int>num;
unordered_map<int, int>num1;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
if (a[i] % k == 0)
l[i] = num[a[i] / k];
num[a[i]] + + ;
}
for (int i = n; i>=1; i--)
{
if (a[i] % k == 0)
r[i] = num1[a[i]*k];
num1[a[i]] + + ;
}
int ans = 0;
for (int i = 1; i <= n; i ++ )
{
ans + = (l[i] * r[i]);
}
cout << ans;
return 0;
}