"War epidemic Cup" online invitational tournament -- solution to game 5

"War epidemic Cup" online invitational tournament -- solution to game 5

Topic details - 1 where is the source of infection (pintia.cn)

Through a recent nucleic acid test, the epidemic prevention and control team detected several positive persons. By retrieving the trip code data, the prevention and control team obtained the places where these cases had been. Now we hope to analyze the source possibility of these sites to find out which sites are more likely to be the source of the epidemic.

For a case, if it has been to locations a, B and C, the possible score of the three locations will increase by 1 / 3. If a case has been to locations a and C, the score of the two locations as the source will increase by 1 / 2. If it has only been to one location, the probability of the location as the source is very high, and we will increase the score of this location by 1.

In short, if a case has been to n locations, all n locations will get a score of 1/n. Now give you the location of all cases. Can you analyze the order of the possibility of each location as the source?

Input format:

The first line is an integer n(1 ≤ n ≤ 1000), indicating the number of records
Next n lines, two non empty strings a and b (1 ≤∣ a ∣, ∣ b ∣ ≤ 10) in each line, containing only lowercase letters. Where a represents the name of the case and b represents the location.

Note: when someone goes to the same place many times, it is only calculated once

Output format:

Output several lines, each line represents a location name, which represents the result of ranking the scores of all locations as the source from high to low. If more than one place has the same score, the place with the smaller place name will be preferred.

Input sample:

6
xiaoa adian
xiaob adian
xiaob bdian
xiaoc adian
xiaoc bdian
xiaoc cdian

Output example:

adian
bdian
cdian

Problem analysis

(Note: this method is easy to hack)

The main problem here is to allocate scores. If a person goes to n places, then this place will get 1/n scores. I tried to use double to calculate the scores of each place, but wa made one shot, and then changed a very rough and dangerous method in a rage.

Assuming that there are m different places in this question, a person will only go to m places at most. The possible ways to allocate scores are 1 / 1, 1 / 2, 1 / 3... 1/m. I directly use a longlong variable ans as the total score. We don't have to calculate 1/m, but can be ans/m, that is to say, for a person's different points to the ground, we can divide them into ans/1,ans/2,ans/2,..., ans/m. So as long as this ans can be divided by the number of 1... M, the problem will become very simple.

I use a map container res to record the number of different places, and then use ans=1 to multiply from 1 to res.size(), so that ans will be divided by any number of 1... Res.size(). Use mymap to record where everyone has gone. cnt is to prevent repeated recording of where a person has gone (for example, if a has gone to bdian twice, we only record once, and we don't record the second time).

Then we assign scores according to the places where everyone goes, and then sort them according to the scores of places and output them.

(the maximum number of longlong can be saved is 1e19, which means that if there are 20 different places, I will send it this way)

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n';
typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 3e5 + 50;

bool cmp(pair<ll, string>& a, pair<ll, string>& b)
{
    if (a.first != b.first)return a.first > b.first;
    return a.second < b.second;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s1, s2;
    cin >> n;
    map<string, vector<string>>mymap;
    map<string, map<string, int>>cnt;
    map<string, ll>res;
    for (int i = 0; i < n; i++)
    {
        cin >> s1 >> s2;
        if (cnt[s1][s2] != 0)continue;
        mymap[s1].push_back(s2);
        cnt[s1][s2] = 1;
        res[s2] = 0;
    }
    ll ans = 1;
    for (int i = 1; i <= res.size(); i++)
    {
        ans *= i;
    }
    for (auto i : mymap)
    {
        int len = i.second.size();
        for (auto j : i.second)
        {
            res[j] += ans / len;
        }
    }
    vector<pair<ll, string>>v;
    for (auto i : res)
    {
        v.push_back({ i.second,i.first });
    }
    sort(v.begin(), v.end(), cmp);
    int len = v.size();
    for (int i = 0; i < len; i++)
    {
        cout << v[i].second;
        if (i != n - 1)cout << endl;
    }
    return 0;
}

Title details - 2 virus sequence (pintia.cn)

Up to now, the epidemic has not ended and the fighting has not stopped! Nowadays, the epidemic is raging all over the world, and the spread of the epidemic has accelerated the variation of the virus, α virus β virus δ Viruses, one after another

Xiao A is interested in the variation of the virus. With the biological knowledge learned in high school, Xiao A understands that the virus can be expressed as A gene sequence composed of four bases A, u, C and G, and the variation of the virus comes from the combination of different gene sequences. Here, we define the combination of two different gene sequences as: the two gene sequences are arranged up and down, so that some bases of the two gene sequences can correspond through certain dislocation. If A and U of the two gene sequences correspond, three hydrogen bonds will be formed, and if C and g of the two sequences correspond, two hydrogen bonds will be formed, as shown in the figure:

In order to ensure the stability of its structure, stubborn viruses always choose the way with the largest number of hydrogen bonds in the process of mutation. Now, given two gene sequences, how many hydrogen bonds do they bind?

PS: the "combination" of the topic description is only defined by the topic description and does not necessarily conform to the real biological properties.

Input format:

Two lines, one string per line, are two gene sequences to be combined. (ensure that the string is only composed of a, u, C and G, and the length of the string is less than or equal to 5000)

Output format:

One integer per line indicates the maximum number of hydrogen bonds after combination.

Input sample:

AGC
UUCG

Output example:

7

Example explanation

There are six possible combinations

AGC
UUCG

AGC
 UUCG
    
AGC
  UUCG
         
 AGC
UUCG

  AGC
UUCG

   AGC
UUCG

The number of hydrogen bonds is 3,0,0,7,0,0
Then the virus sequence will be combined in the way that the number of hydrogen bonds is 7

Problem analysis

The explanation of this example is very clear, that is, two strings start matching at different positions, and then see which position starts matching with the highest score.

Take the example, we can match as follows:

   AGC  -->s1
UUCG  -->s2

  AGC
UUCG

 AGC
UUCG

AGC
UUCG

AGC
 UUCG
    
AGC
  UUCG

Through the above process, we can start matching from the ass of s2, and then move the position forward gradually. When the ass of s1 reaches the head of s2, it is the last step. Then we maintain the maximum score in this process, and finally output the score. For convenience, I added useless characters equivalent to the length of s1 to the tail of s2, and then we matched it in the way of tail to tail. After each matching, the tail characters of s2 were removed. When s2 was deleted, the matching ended. The simulation is as follows:

   AGC  
UUCG**  

  AGC
UUCG*

 AGC
UUCG

AGC
UUC

AGC
 UU
    
AGC
  U

Personally, I think it's more convenient. Of course, it's better to have a more suitable method.

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n';
typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 3e5 + 50;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s1, s2;
    cin >> s1 >> s2;
    int res = 0, ans = 0;
    for (int i = 0; i < s1.size(); i++)
        s2 += '*';
    int l = 0, r = 0;
    while (s2.size() != 0)
    {
        l = s1.size(), r = s2.size();
        ans = 0;
        while (l >= 0 && r >= 0)
        {
            if (s1[l] == 'A' && s2[r] == 'U')
            {
                ans += 3;
            }
            else if (s1[l] == 'U' && s2[r] == 'A')
            {
                ans += 3;
            }
            else if (s1[l] == 'C' && s2[r] == 'G')
            {
                ans += 2;
            }
            else if (s1[l] == 'G' && s2[r] == 'C')
            {
                ans += 2;
            }
            l--, r--;
        }
        res = max(res, ans);
        s2.pop_back();
    }
    cout << res;
    return 0;
}

Title details - 3 strange shapes (pintia.cn)

Xiao Fan has a square white paper with a side length of 2, which is painted with 2 × Two grids with side length of 1. Cubes with edge length of 1 can be placed on each grid. Xiao Fan has several cubes with edge length of 1 in his hand. He randomly places some cubes on each grid to find the surface area of the geometry composed of these cubes.

Input format:

Enter two lines, each with two positive integers no more than 100, representing the number of cubes on each grid drawn on white paper from a top view.

Output format:

Output a row containing an integer representing the surface area of the geometry.

Input sample:

The input data corresponding to the above figure is as follows:

2 1
1 1

Output example:

20

Problem analysis:

This question is actually quite warm. Due to the limitations of conditions, this question is very simple.

First, the topic ensures that the bottom of the object is 2 * 2.

According to the input number, we use the variable abcd to receive:

a:2  b:1
c:1  d:1

The surface area is the area of the part that can be seen directly by us, and then we look at it in six directions: up, down, left, right, front and back

First of all, since its bottom is fixed by 2 * 2, the figure you can see from top to bottom and from bottom to top is a 2 * 2 square, so the surface area of the bottom and the surface area of the top are 4, and now the surface area is 8.

Then we look from front to back and see the following figure:

The surface area is: 3, and now the surface area is 11

The figure from the back to the front is actually the same as that from the back to the front (only the opposite):

The surface area is still 3: now the surface area is 14

The figure seen from left to right is:

The surface area is: 3. Now the surface area is 17

The figure seen from right to left is opposite to the figure seen from left to right:

The surface area is: 3, and now the surface area is 20

Therefore, the 4 * 2 points at the top and bottom of the calculated surface area have been fixed, and the front, back, left and right depends on the height of its placement.

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n';
typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 3e5 + 50;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int res = 8;
    //This is the area from front to back and from back to front
    res += (max(a, c) + max(b, d))*2;
    //This is the area from left to right and from right to left
    res += (max(d, c) + max(a, b))*2;
    cout << res;
    return 0;
}

Tags: Algorithm Graph Theory

Posted by torvald_helmer on Sat, 14 May 2022 00:40:22 +0300