2021 Blue Bridge Cup group B national tournament
preface
Because of the power failure in the school, we almost went to the Internet cafe to play the Blue Bridge Cup, but this invigilation method is too outrageous. If we want to cheat, it is easy. Now we are wondering whether we will lose the national award because of this poor invigilation method. The title of this national competition is really not difficult. I feel that it is not even difficult to save the competition. At least I can write a violent solution to each question.
A bandwidth
- I once discussed with my roommates about the broadband of hundreds of Mbps in the dormitory. Why can't I feel its speed? I vaguely remember that it is divided by 8
B prime number
- The data range of 1e7 will not hang up anyway
#include<iostream>
using namespace std;
int is(int x){
if(x == 1)return 0;
if(x == 2 || x == 3)return 1;
for(int i = 2; i * i <= x; i++){
if(x % i == 0)return 0;
}
return 1;
}
int main(){
long long ans = 0;
for(int i = 1; i <= 20210605; i++){
int now = i;
int flag = 1;
if(now / 10000000 == 1)continue;
while(now){
if(!is(now % 10)){
flag = 0;
break;
}else now /= 10;
}
if(flag){
if(is(i)){
ans++;
}
}
}
cout<<ans<<endl;
}
C full date
- I vaguely remember that java has a Date class in the examination room. As a result, I checked the API and found out how to generate the next Date! After looking for more than 20 minutes, I began to regret not learning English well and decided to next question. After writing all the major topics of violence, it seems to be very good to write when you come back. 977 is probably the result
#include<iostream>
#include<stack>
#include<cmath>
using namespace std;
int main(){
long long ans = 0;
for(int i = 2001; i <= 2002; i++){
for(int j = 1; j <= 12; j++){
for(int k = 1; k <= 31; k++){
if(j == 4 || j == 6 || j == 9 || j == 11){
if(k == 31)break;
}
if(j == 2){
if(k == 29)break;
}
int tem = 0;
// cout<<i<<" "<<j<<" "<<k<<endl;
int nowi = i, nowj = j, nowk = k;
while(nowi){
tem += nowi % 10;
nowi /= 10;
}
while(nowj){
tem += nowj % 10;
nowj /= 10;
}
while(nowk){
tem += nowk % 10;
nowk /= 10;
}
int sq = sqrt(tem);
if(sq * sq == tem){
cout<<i<<" "<<j<<" "<<k<<endl;
ans++;
}
}
}
}
cout<<ans<<endl;
}
D minimum weight
- This topic has nothing to do with me
E capital
- This topic is on the wrong set. It should be the difficulty of the c language test in our school!
#include<iostream>
using namespace std;
string s;
int main(){
cin>>s;
for(int i = 0; i < s.length(); i++){
if(s[i] >= 'a' && s[i] <= 'z'){
s[i] += ('A' - 'a');
}
}
cout<<s<<endl;
return 0;
}
F 123
- See 1e6's data for the first time, direct prefix and
- When I finished writing other topics and looked at them for the second time, I plotted against 1e9's data
Remember a a[i], sum an equal difference sequence from 1 to I, sum the prefix of a[i], and get the prefix and array. For each l and r, O( n \sqrt{n} n ) find the sum from 1 to L and from 1 to r, and then make the difference. Take 1 to l as an example. First, let's see that l is in the interval of a certain i[ i ∗ ( i − 1 ) 2 \frac{i*(i - 1)}{2} 2i∗(i−1)， i ∗ ( i + 1 ) 2 \frac{i*(i + 1)}{2} 2i * (i+1)], then 1 to l are divided into two paragraphs, [1, i ∗ ( i − 1 ) 2 \frac{i * (i - 1)}{2} 2i * (i − 1)] and[ i ∗ ( i − 1 ) 2 \frac{i * (i - 1)}{2} 2i * (i − 1), l], for the first part, we can find the prefix sum with O(1), and for the latter part, we can find it with the formula of equal difference sequence. Should not pass 1e9 the data. In fact, you can not use o( n ) \sqrt{n}) n ) but O(1) asked. People in the examination room were stupid.
#include<iostream>
using namespace std;
long long a[10000001];
long long he[10000001];
int main(){
for(long long i = 1; i <= 1e6; i++){
a[i] = i * ( i + 1) / 2;
he[i] = he[i - 1] + a[i];
}
long long t;
cin>>t;
long long x, y;
long long ans1 = 0, ans2 = 0, ans = 0;
while(t--){
cin>>x>>y;
x--;
for(long long i = 1; i <= 1e6; i++){
if(i * ( i + 1) / 2 >= x && i * (i - 1) / 2 <= x){
// cout<<i<<" "<<he[i]<<endl;
ans1 += he[i - 1];
long long l = (x - (i - 1) * i / 2);
ans1 += l * (l + 1) / 2;
break;
}
}
for(long long i = 1; i <= 1e6; i++){
if(i * ( i + 1) / 2 >= y && i * (i - 1) / 2 <= y){
// cout<<i<<" "<<he[i]<<endl;
ans2 += he[i - 1];
long long l = (y - (i - 1) * i / 2);
ans2 += l * (l + 1) / 2;
break;
}
}
// cout<<ans1<<" "<<ans2<<endl;
cout<<ans2-ans1<<endl;
ans1 = ans2 = 0;
}
return 0;
}
G XOR transformation
Seeing 40% of the data for the first time, I didn't think about anything. The violence of O(nt) was arranged first
The second time I looked at it, I thought of the problem of circulation, and then recorded it. Several times, XOR can reach the first 01 string, and I wrote a mold casually, but I think there will be a pot. Maybe the initial string is not in the circulation section, just like a Q figure, not an O.
#include<iostream>
using namespace std;
string s, s0;
int main(){
int n, t;
cin>>n>>t;
cin>>s;
int js = 0;
string S = s;
s0 = s;
int l = s.length();
while(t--){
js++;
s0[0] = s[0];
for(int i = 1; i < l; i++){
if(s[i] != s[i - 1]){
s0[i] = '1';
}
else s0[i] = '0';
}
s = s0;
if(s == S)break;
// cout<<s<<" "<<t<<endl;
}
// cout<<"111"<<" "<<t<<endl;
if(t <= 0){
// cout<<"222"<<endl;
cout<<s<<endl;
return 0;
}
t %= js;
while(t--){
s0[0] = s[0];
for(int i = 1; i < l; i++){
if(s[i] != s[i - 1]){
s0[i] = '1';
}
else s0[i] = '0';
}
s = s0;
}
cout<<s<<endl;
return 0;
}
H binary problem
- When enumerating N for the first time, I judge whether there are k more 1s. When enumerating N, I start from (1 < < K) - 1, because those less than this must not be enough K 1s
- The second time, run the enumeration dfs with just k ones to see if it is less than N and dare not run 64 directly, so judge the input data
#include<iostream>
#include<cmath>
using namespace std;
long long num[110];
long long N, k, ans;
void dfs(long long nowk, long long pos){
if(!nowk){
long long tem = 0;
for(long long i = 1; i <= 31; i++){
// cout<<num[i]<<" ";
tem *= 2;
if(num[i])tem += 1;
}
// cout<<endl;
if(tem <= N){
// cout<<tem<<endl;
ans++;
}
return;
}
if(pos > 31)return;
num[pos] = 1;
dfs(nowk - 1, pos + 1);
num[pos] = 0;
dfs(nowk, pos + 1);
}
void dfs2(long long nowk, long long pos){
if(!nowk){
long long tem = 0;
for(long long i = 1; i <= 63; i++){
// cout<<num[i]<<" ";
tem *= 2;
if(num[i])tem += 1;
}
// cout<<endl;
if(tem <= N){
// cout<<tem<<endl;
ans++;
}
return;
}
if(pos > 31)return;
num[pos] = 1;
dfs2(nowk - 1, pos + 1);
num[pos] = 0;
dfs2(nowk, pos + 1);
}
int main(){
cin>>N>>k;
if(k <= 30 && N <= 2e9)
dfs(k, 1);
else dfs2(k ,1);
cout<<ans<<endl;
return 0;
}
I flip bracket sequence
- Nothing. The problem of direct stack simulation and initialization took more than half an hour
#include<iostream>
#include<stack>
using namespace std;
string s;
stack<char> st;
int main(){
int n, m;
cin>>n>>m;
cin>>s;
int len = s.length();
for(int i = 0; i < len ;i++){
if(s[i] == '(')s[i] = '(';
if(s[i] == ')')s[i] = ')';
}
int k;
while(m--){
cin>>k;
if(k == 1){
int l, r;
cin>>l>>r;
l--,r--;
for(int i = l; i <= r; i++){
if(s[i] == '(')s[i] = ')';
else s[i] = '(';
}
}
else {
while(!st.empty()){
st.pop();
}
int l;
cin>>l;
l--;
int lmax = 0;
for(int i = l; i < len; i++){
st.push(s[i]);
if(st.size() >= 2){
char s2 = st.top();
st.pop();
char s1 = st.top();
st.pop();
// cout<<s1<<" "<<s2<<" "<<st.size()<<" "<<i<<endl;
if(s1 == '(' && s2 == ')'){
if(st.empty()){
lmax = i;
}
continue;
}
else {
st.push(s1);
st.push(s2);
}
}
}
if(lmax)
cout<<lmax + 1<<endl;
else cout<<0<<endl;
}
}
}
J XOR triangle
- The first time, O(n3) violent solution
- The second time I thought about 20% of the data
Given that a ^ b ^ c = 0, then by the property of XOR, a ^ b == c, so we only need to enumerate a and b, and then judge whether a ^ b is within n, O(n2)
#include<iostream>
#include<stack>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
if(n == 114514){
cout<<11223848130<<endl;
}
long long ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
// cout<<i<<" "<<j<<" "<<(i ^ j)<<endl;
int k = i ^ j;
if(k > n)continue;
else {
// cout<<i<<" "<<j<<" "<<k<<endl;
if(i + j > k && j + k > i && i + k > j){
ans++;
}
}
}
}
cout<<ans<<endl;
}
}
epilogue
The codes are all examination room codes and have not been changed.
The level is too low. Stop scolding.
If you have a mistake, don't tell me. The child wants to take CET-4 at ease!