2018-2019 ICPC southwest Europe Regional Programming Competition (SWERC 2018)

A - City of Lights

Gym - 102465A
Water question
Meaning:
Give n lights, give m numbers, for each number k[i]
Reverse the status of the lamp with an integral multiple of k[i] (turn off the lamp that has been lit or turn on the lamp that has not been lit)
The initial status lights are on
Ask how many lights are on at most at the same time.
Idea: violence is enough, with the prefix and?

code:

Thinking questions, prefixes and

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int, int>
#define x first
#define y second
const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll M = 1e9 + 7;
const int N = 110;
int vis[maxn];
int main()
{
  int n; cin>>n;
  int k; cin>>k;
  int ans=0;
   int cnt=0;
  for(int i=0;i<k;i++){
     int t; cin>>t;
    
     for(int j=t;j<=n;j+=t){
        // cout<<j;
         if(vis[j]==1){
             vis[j]=0;  
               cnt--;
         }
         else {
             vis[j]=1;
              cnt++;
         }
     }
    // cout<<endl;
     ans=max(ans,cnt);
  }
  cout<<ans<<endl;
    return 0;
}

B - Blurred Pictures

Gym - 102465B
Meaning:
Give me a picture, there are 1 × 1, but some pixels are damaged,
Give the starting coordinates of undamaged pixels in each row, and cut off the largest undamaged square photo.
Moreover: any horizontal or vertical line between two non blurred pixels is a non blurred pixel.
That is:
Give the starting point coordinates of line m and judge the number of the largest squares formed.
Idea:
because

Any horizontal or vertical line between two non blurred pixels is a non blurred pixel.

Therefore, you only need to care about the upper and lower bounds, and then enumerate violence.

code:

Intermediary operation

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int, int>
#define x first
#define y second
const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll M = 1e9 + 7;
const int N = 10010;
int l[maxn];
int r[maxn];
int main()
{
     int n;cin>>n;
     int ans=1;
     for(int i=0;i<n;i++) cin>>l[i]>>r[i];
     for(int i=0;i<n;i++){
         while(1){
             if(r[i]-l[i]<=ans-1) break;//If it is less than ans, just go to the next line
             int topX=i+ans-1+1;
             if(topX>=n) break;//If the upper boundary is exceeded, end
             int L=max(l[i],l[topX]);
             int R=min(r[i],r[topX]);
             if(R-L>=ans) ans++;
             else break;

         }
     }
     cout<<ans<<endl;
    return 0;

}

D - Monument Tour

Gym - 102465D
Meaning:
Enter from any road (east-west direction) on the left of the rectangle, and then visit all the monuments and museums. You can only move up or down. After visiting the monuments and museums, return to the road when you enter, so as to find the shortest way out of the city.
Idea:
Traverse the x coordinate axis, find the maximum and minimum y values in each x coordinate, and store them in array a.
Sort array a and find the median, which is the y coordinate when the car enters the city,
Then calculate the distance from 0-X bus to visit each museum.

code:

Thinking problem

#include<bits/stdc++.h>
using namespace std;
int l[100100];
int r[100100];
int a[200100];
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    memset(l,0x3f3f3f,sizeof(l));
    memset(r,-1,sizeof(r));
    for(int i=1;i<=k;i++)
    {
        int x;
        cin>>x>>a[i];
        l[x]=min(l[x],a[i]);
        r[x]=max(r[x],a[i]);
    }
    k=0;
    for(int i=0;i<n;i++)
    {
        if(r[i]<0) continue;
        a[++k]=l[i];
        a[++k]=r[i];
    }
    sort(a+1,a+k+1);
    long long res=n-1;
    for(int i=0;i<n;i++)
    {
        if(r[i]<0) continue;
        if(a[k/2]<=l[i]) res+=(r[i]-a[k/2])*2;
        else if(a[k/2]>=r[i]) res+=(a[k/2]-l[i])*2;
        else res+=(r[i]-l[i])*2;
    }
    cout<<res<<endl;
    return 0;
}

E - Rounding

Gym - 102465E
Meaning:
A total of 10000 people did a survey and counted the data, but all the results of this data were rounded. I asked you to find out the maximum and minimum values of the results. There are also cases where the results are wrong
Idea:
The others are the largest, and this value itself is the smallest.
The others are the smallest, and this value itself is the largest.
Then judge the boundary and look at the code

code:

thinking

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int, int>
#define x first
#define y second
const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll M = 1e9 + 7;
const int N = 10010;
int n;
string str[N];
double cnt = 0.00;
double ans[N][3];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> str[i];
        cin >> ans[i][0];
        cnt += ans[i][0];
    }
    double maxcnt = cnt + n * 0.49;
    double minicnt = cnt - n * 0.50;
    // cout<<minicnt<<" "<<maxcnt  <<endl;
    if (minicnt > 100.00 || maxcnt < 100.00)
    {
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }
    for (int i = 0; i < n; i++)
    {

        double t = ans[i][0];
        ans[i][1] = max(t - 0.50, 100 - (maxcnt - t - 0.49)); //Small
        ans[i][2] = min(t + 0.49, 100 - (minicnt - t + 0.5)); //large
        if( ans[i][2]>=100) ans[i][2]=100.0;
         if( ans[i][1]<=0)  ans[i][1]=0.00;
        cout << str[i] << " ";
        printf("%.2lf %.2lf\n", ans[i][1], ans[i][2]);
    }

    return 0;
}