2021-2022-2 ACM training team weekly Programming Competition (8) problem solution

A. 21 Click game

The question ：
Here are three numbers A1 , A2 , A3 ,
If A1 + A2 + A3 >= 22 , Output bust
Otherwise output win
Ideas ：
simulation
Time complexity ：$O1$

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6 + 10 ;

int main()
{
    
    int a , b , c ;
    cin >> a >> b >> c; 
    int s = a + b + c ;
    if(s >= 22) puts("bust") ;
    else puts("win") ;
    
    return 0 ;
}

B. Palindrome game

The question ：
Give you a string S,
You can modify S Any character of ,
Ask at least how many times you need to modify , bring S Become a palindrome string .
Ideas ：
Double pointer
Time complexity ：$On$

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6 + 10 ;
char s[N] ;

int main()
{
    
    cin >> s + 1 ;
    int n = strlen(s + 1) ;
    int res = 0 ;
    for(int i = 1 , j = n ; i < j ; i ++ , j --)
    {
    
        if(s[i] != s[j]) res ++ ;
    }
    cout << res ;
    
    return 0 ;
}

C. A good man or The bad guys ？

The question ：
Yes n Someone is playing a game ,
The game is like this , We will n Individuals are divided into good people and bad people , May also be n Everyone is good or bad
What good people say must be right , What the bad guys say may be right , Maybe not .
Now let's give you everyone's judgment of others ,
Ask how many good people there are at most
Ideas ：
be aware n At most 15 personal , Everyone is either good or bad , So violence enumerates all the possibilities , The time complexity is $2^{15}$,
You can use it here State compression To enumerate , Or use dfs enumeration .
For each case , everyone Both good and bad people are known .
So what good people say It must be right , If There was a conflict , It means that this situation is not good .
If you can , Just update the number of good people .
Time complexity ：$O(2^{15}\ast n^2)$

#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,z;
vector<pair<int ,int> > a[20];
int main(){
    
	cin>>n;
	for (int i=0;i<n;i++){
    
		cin>>m;
		for (int j=0;j<m;j++){
    
			cin>>x>>y;
			a[i].push_back(make_pair(x-1,y));
		}
	}
	for (int i=0;i<1<<n;i++){
    
		int f=1;
		for (int j=0;j<n;j++){
    
			if (i>>j&1){
    
				for (pair<int,int>k:a[j]){
    
					if ((i>>k.first&1)!=k.second) f=0;
				}
			}
		}
		if (f) z=max(z,__builtin_popcount(i));
	}
	cout<<z<<endl;
	return 0;
}

D. Exclusive or and

The question ：
Here you are. n Array of Numbers
$a_1$ $a_2$ …$a_n$
seek （${\sum }_{i=1}^{n-1}{\sum }_{j=i+1}^n(a[i]\oplus a[j])$） % ($10^9$ + 7)
$A\oplus B$ Express A Exclusive or B , It also means (a ^ b)
Ideas ：
Bit operation requires Disassemble everyone to see ,
We assume that $b[k][i]$ An array of said $a_i$ The second... Under the binary representation of $k$ Is it $1$ still $0$

So we Just find out every bit On ${\sum }_{i=1}^{n-1}{\sum }_{j=i+1}^n(b[k][i]\oplus b[k][j])$ Value
The answers add up $2^k\ast {\sum }_{i=1}^{n-1}{\sum }_{j=i+1}^n(b[k][i]\oplus b[k][j])$ that will do

Now consider only one 0/1 Array of , How to find ${\sum }_{i=1}^{n-1}{\sum }_{j=i+1}^n(b[k][i]\oplus b[k][j])$

Because only $0/1$ Two cases
Even number $1$ Exclusive or equal to $0$
An odd number $1$ Exclusive or equal to $1$

therefore
${\sum }_{i=1}^{n-1}{\sum }_{j=i+1}^n(b[k][i]\oplus b[k][j])=1OfindividualCount\ast 0OfindividualCount$

Time complexity ：$Onlogn$

#include<bits/stdc++.h>
using namespace std ;
#define int long long 
const int N = 1e6 + 10 , mod = 1e9 + 7 ;
int res , n , a[N] ;

signed main()
{
    
    cin >> n ;
    for(int i = 1 ; i <= n ; i ++)
        scanf("%lld" , &a[i]) ;
        
    for(int j = 0 ; j < 60 ; j ++)
    {
    
        int cnt = 0 , s ;
        for(int i = 1 ; i <= n ; i ++)
        {
    
            if(a[i] >> j & 1) cnt ++ ;
        }
        s = cnt * (n - cnt) % mod ;
        for(int i = 0 ; i < j ; i ++) s = s * 2 % mod ;
        res += s , res %= mod ;
    }
    
    cout << res ;
    return 0 ;
}

E. Eat food

The question ：
Yes n Dish , Each dish needs $a_i$ Time to eat , Yes $b_i$ Delicious degree of .
Now there are the following rules ：

• After ordering a dish , You can only order a dish after you finish it .
• t You can't order after the moment , But you can still eat vegetables .
• Each dish can only be ordered once .

Finally, what is the most delicious food you can get .
Ideas ：
If Don't consider Second rule , It's obviously a 01 knapsack problem ,
We assume that $f[j]$ The time is $j$ Maximum delicacy in the case of ,
$f[j]=f[j-a[i]]+b[i]$

Now? consider Add the second rule ,
That means we can stay $i<t$ At any moment of the day, add $b_i$,

obviously need Yes $a_i$ Sort from small to large , because Eating at the end of a long time is the most profitable .

Time complexity ：$O{n}^2$

#include<bits/stdc++.h>
using namespace std ;
#define pll pair<int,int> 
#define y second 
#define x first 
const int N = 1e6 + 10 ;

int n , m ;
pll q[N] ;
int f[N] ;
int res ;

signed main()
{
    
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i ++)
        cin >> q[i].x >> q[i].y ;

    sort(q + 1 , q + 1 + n) ;
    
    for(int i = 1 ; i <= n ; i ++)
    {
    
        for(int j = 0 ; j < m ; j ++)
        {
    
            res = max(res , f[j] + q[i].y) ;
        }
        for(int j = m ; j >= q[i].x ; j --)
        {
    
            f[j] = max(f[j] , f[j - q[i].x] + q[i].y) ;
        }
    }
    
    cout << max(res , f[m]) ;
    return 0;
}

F: rectangular

The question ：
Given n A point in a coordinate system ($x_i$,$y_i$)
If there are three points as shown in the figure below （ Black spot ） You can construct a new point （ Red dot ）. Find the maximum number of constructable points .
​

Ideas ：
A place that can be operated as long as it is a connected area , You can fill this area with dots .

Blue is the existing dot , Red is the point added later , You can add in a little bit .
As long as you're in this area , All points on the line can be filled in .
Find the... In each block , Number of horizontal and vertical lines at all points , Multiplication is all points .

How to find how many areas there are ？ We can use and search the set , Tie the abscissa and ordinate of each point into a set , In this way, those with the same vertical line and the same horizontal line will be tied in , Form a large collection , But when calculated separately , Only the vertical and horizontal lines are calculated separately .
Finally, subtract the existing points .
Time complexity ：$On$

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6 + 10 , M = 1e5 ;
int n ;
int p[N] , cnt1[N] , cnt2[N] ;

int find(int x)
{
    
    if(x != p[x]) p[x] = find(p[x]) ;
    return p[x] ;
}

int main()
{
    
    cin >> n ;
    for(int i = 1 ; i <= N - 10 ; i ++) p[i] = i ;
    
    for(int i = 1 ; i <= n ; i ++)
    {
    
        int x , y ;
        scanf("%d %d",&x , &y) ;
        p[find(x)] = find(y + M) ;
    }
    
    for(int i = 1 ; i <= M ; i ++) cnt1[find(i)] ++ ;
    for(int i = M + 1 ; i <= 2 * M ; i ++) cnt2[find(i)] ++ ;
    
    long long res = 0 ;
    for(int i = 1 ; i <= 2 * M ; i ++) res += (long long)cnt1[i] * cnt2[i] ;
    
    cout << res - n ;
    return 0 ;
}