Location>code7788 >text

Niuke Weekly Scheme Question 91

Popularity：403 ℃/2025-04-29 10:56:43

Niuke Weekly Tournament 91

/acm/contest/108038#question

/acm/contest/108038/A

Sign-in question: Just judge the current string andwhileThere are only a few different characters in the positions.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;cin>>s;
    int ans=0;
    if(s[0]!='w') ans++;
    if(s[1]!='h') ans++;
    if(s[2]!='i') ans++;
    if(s[3]!='l') ans++;
    if(s[4]!='e') ans++;
    cout<<ans;
    return 0;
}

/acm/contest/108038/B

Check in questions, use prefix and solve them.

#include<bits/stdc++.h>
using namespace std;
#define LL long long
int main()
{
    int n;cin>>n;
    vector<LL> a(n+1,0),s(n+1,0);
    for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
    LL ans=0;
    for(int i=1;i<=n;i++){
        if(i<=9) ans=max(ans,s[i]);
        else ans=max(ans,s[i]-s[i-10]);        
    }
    cout<<ans;
    return 0;
}

C. Reverse pairs of benzene

/acm/contest/108038/C

Idea: Preprocess the value of the largest number among the previous i numbersp[i], then enumerate the subscript\(i\),likep[i-1]>a[i], that is, the value before the subscript i has a part of >a[i], then it can form a reverse order pair because the maximum requireda[i]+a[j], so we can process the largest value of the previous i number.

#include<bits/stdc++.h>
 using namespace std;
 void solve(){
     int n;cin>>n;
     //The maximum value of i before preprocessing
     vector<int> a(n+1,0),p(n+1,0);
     for(int i=1;i<=n;i++){
         cin>>a[i];
         p[i]=max(p[i-1],a[i]);
     }
     int ans=0;
     for(int i=1;i<=n;i++){
         if(p[i-1]>a[i]) ans=max(p[i-1]+a[i],ans);
     }
     cout<<ans<<"\n";
 }

 int main()
 {
     int t=1;cin>>t;
     while(t--) solve();
     return 0;
 }

D.Array 4.0

/acm/contest/108038/D

Idea: After sorting the elements in the array, calculate the "number of segments", then the answer is "number of segments" -1. How to calculate the number of segments? When we take a numberxWhen a new period is opened, it meansx-1It must not exist in the array, so we only need to usemapTo store the frequency of each number (as for why you use map, don't use set, there is an explanation later.)x-1If the frequency of occurrence is 0, then a new section will be opened.

So why do we usemapNot usedsetWoolen cloth? We have a special case, similar to the following example:

[1,2,4,4,6,7,8]We need to use this example in2,4A side is connected between them, and it also needs to be4,4and4-6Connect one edge between, that is,x+1When it does not exist in the array, we need to connect all x, and the price of connecting all x is:The frequency of x occurrence -1；

#include<bits/stdc++.h>
 using namespace std;
 void solve(){
     int n;cin>>n;
     map<int,int> mp;
     for(int i=1;i<=n;i++){
         int x;cin>>x;
         mp[x]++;
     }
     int ans=0;
     for(auto & [x,y] : mp){
         //x-1 does not exist, just open a new section
         if(!(x-1)){
             ans++;
             //If x+1 does not exist, then all x needs to be connected by itself...
             if(!(x+1)) ans+=y-1;
         }
     }
     //The answer is "number of segments" -1;
     cout<<ans-1<<"\n";
 }
 int main()
 {
     int t=1;cin>>t;
     while(t--) solve();
     return 0;
 }

E. Matrix inversion of benzene

/acm/contest/108038/E

Idea: If we give us a 01 matrix and let us judge whether it can become a full 0 matrix, it may be a bit troublesome and there are many situations that need to be discussed. Then we might as well think about it in reverse and give us a full 0 matrix. After these operations, what kind of matrix can be turned into, and then match this matrix with our original 01 matrix. If the match is successful, then output it.YES, otherwise outputNO;
Then give us a 01 matrix. After performing these operations, there are four situations:

  1. Select a row (column) with all 0 and flip it twice. The resulting matrix is ​​still a matrix of all 0.
  2. Select two rows with all 0 (the two rows are different) to flip them once, and the resulting matrix is: only two rows are all 1, and the rest are all 0;
  3. Select two columns with all 0s (the two columns are different) to flip them once, and the resulting matrix is: only two columns are all 1, and the rest are all 0;
  4. Select a row and a column to operate and flip it once. Then what you get will be a cross-type figure, except for the intersection point, the rest of the points are 1;

So how do you write code to make judgments?

  1. It is easy to judge if all 0s are required, only the number of numeric characters 1 is needed.c1,likec1==0, then this 01 matrix is ​​originally a full 0 matrix

  2. Select two rows to flip, then after flip, the number of 1 in the obtained matrix must bem*2, and the other rows are 0, we only need to use one variableCrTo record all 0 is the number of rows, ifCr==2 && c1==m*2, then it is in line with our situation.

  3. Select two columns to flip, the same as the second one. We useCcTo record the number of columns with all 0, ifCc==2 && c1==n*2, then it is in line with the situation

  4. The cross-type graph, in this case, because the intersection point is 0, then we only need to enumerate the positions of 0, assuming that the positions of the current row and column are respectivelyi,j. Then we just need to judgeIs the number of 1 in line i m-1as well asIs the number of 1 in column j n-1,as well asThe number of characters 1 is n+m-2;If all three items are met, then this situation is in line with it. We need to use it herer[i]To record the number of 1 in line i, you need to use itc[j]To record the number of 1 in column j

//There is a backlash if it is a tough one
 //Think about four situations
 //1. It was originally all 0
 //2. There are two columns/behavior 1
 //3. There is a cross-shaped shape (there are all 1 except intersection points);

 #include<bits/stdc++.h>
 using namespace std;
 void solve(){
     int n,m;cin>>n>>m;
     vector<string> a(n);
     //r[i] represents the number of 1 in the i-th row, and..c[i] represents the number of 1 in the i-th column
     vector<int> r(n),c(m);
     for(int i=0;i<n;i++) cin>>a[i];
     //Count the number of 1
     int c1=0;
     for(int i=0;i<n;i++){
         for(int j=0;j<m;j++){
             if(a[i][j]=='1'){
                 c1++;
                 //Line i, column j
                 r[i]++;
                 c[j]++;
             }
         }
     }
     //Calculate the number of rows all 1
     int Cr = 0;
     for(int i = 0; i < n; i++) {
         Cr += (r[i] == m);
     }
     //Calculate the number of columns with all 0
     int Cc = 0;
     for(int i = 0; i < m; i++) {
         Cc += (c[i] == n);
     }
     //There are also figures similar to crosses, enumerating the positions of 0.. Then the number of 1 in that row is m-1, the number of 1 in that column is n-1.. and the total number of 1 is n+m-2;
     bool flag=0;
     for(int i=0;i<n;i++){
         for(int j=0;j<m;j++){
             if(a[i][j]=='1') continue;
             if(r[i]==m-1&&c[j]==n-1&&c1==n+m-2) flag=true;
         }
     }
     //Satisfies one situation, then output YES, otherwise it is NO;
     if(c1==0||(c1==2*m && Cr==2)||(c1==2*n && Cc==2)||flag) cout<<"YES\n";
     else cout<<"NO\n";
 }
 int main()
 {
     int t=1;cin>>t;
     while(t--) solve();
     return 0;
 }

F. Factor query of benzene

/acm/contest/108038/F

To be updated...

<Previous