Summary of supplementary questions for 2019 Shandong provincial competition

Digression

After the game, I did what my teammates did and what I didn't do
I feel it's actually quite simple. I just don't think about it. In other words, I'm not proficient in this algorithm.

H Title Link

meaning of the title

Give you several line segments, and then you can find a point on each line segment (this point must be in the y-axis direction, and no other point is parallel to it, that is, there can only be one point on a vertical line), and then ask how many line segments you have this point (this line segment has at least one point, and there is no problem with multiple)

thinking

Once you see the left and right endpoints of a line segment, you must consider sorting the left endpoint and then the right endpoint

  • Because this question may give you several line segments with the same x point and different Y point (example: 1,2,2,2 (his y is i according to the title, which starts from i =1) is (1,1) (2,1) (1,2) (2,2) (1,3) (2,3)), we need to judge whether the Y axis is occupied at the position where the previous point moves,
    • Use without
    • If yes, move the current point (as long as the current point x is still less than the current y) + +. If it exceeds the right endpoint of this line segment, it will jump to another line segment
  • Through the above analysis, we only need to use a priority queue and overload < on the line

code

#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>
#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)

using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
const LL Max = 9.1e10;
const int N =3.1e5;
const int maxn = 200010;

void clear(unsigned char *pta, int size )
{//Structure initialization
    while(size>0)
    {
        *pta++ = 0;
        size --;
    }
}

LL   n, k, m ;
LL ar[N],br[N];
LL i,j,g;
LL MOD = 998244353 ;
struct node {
    int l ,r ;
    bool operator < (const node & x)const {
        if(l==x.l)return r > x.r;
        return l>x.l;
    }

};

priority_queue<node > q;

void answer(){
    cin >>n ;

    for(int i=1 ;i<=n;i++){
        node  no;
        cin >>no.l>>no.r;
        q.push(no);
    }
    LL cnt =0  , h = 0;
    while(!q.empty()){
        node New = q.top();
        q.pop();
        if(New.l>h){
            cnt ++ ;
            h = New.l;
        }
        else if(New.l < New.r){
            New.l++ ;
            q.push(New);
        }
    }
    cout<<cnt<<endl;

   return ;
 }


int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0), cout.tie(0);
//       pre();
    LL t;sld(t);
    while(t--)
        answer();


    return 0;

}

L Title Link

meaning of the title

Give you some points, then tell you that the left side of these points is strictly larger than the right side, and ask you how many points can become the middle point

thinking

Because the condition is greater than, we can think of this as a directed graph (the point on the left points to the point on the right)

  • In this way, we only need to consider under what circumstances can this directed graph be a little in the middle?
    • First of all, according to the discrete knowledge (data structure is OK), we know that the directed graph with self ring cannot be established (either the graph cannot be connected, or the graph becomes a ring)
    • Then, at this time, we only need to consider what algorithm can solve the closure problem and find the floyed algorithm, but because its complexity is too high, look at the data and find that the data range is OK, so we can start directly!
  • After finding the algorithm and ideas, you only need to finally judge whether the out degree and in degree of each point are greater than or equal (equal to because the problem surface says that n must be an odd number) (n+1) / 2

code

#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>
#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)

using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
const LL Max = 9.1e10;
const int N =3.1e5;
const int maxn = 200010;

void clear(unsigned char *pta, int size )
{//Structure initialization
    while(size>0)
    {
        *pta++ = 0;
        size --;
    }
}

LL   n, k, m ;
LL ar[N],br[N];
LL i,j,g;
LL MOD = 998244353 ;

LL floyed[110][110];
LL in[maxn],out[maxn];



LL fac[N],inv_fac[N];
//Counting 
LL qpow(LL x, LL y ){
    x%=MOD;
    long long res=1%MOD;
    while(y){
        if(y&1)res=res*x%MOD;
        y>>=1;
        x=x*x%MOD;
    }
    return res;

}

void pre(){
    fac[0] =1 ;
    for(int i=1;i<N;i++){
        fac[i] =fac[i-1] * i %MOD;
    }
    inv_fac[N - 1 ] = qpow(fac[N - 1] , MOD-2 ) ;

    for(int i =N-2 ;i>=0 ;i--){
        inv_fac[i] = inv_fac[i+1] * (i+1) %MOD;
    }

}

LL C (LL a ,LL b){
    if(a<0 || b> a )//Because it is C (a, b), B = a
    {
        return 0;
    }

    return fac[a] * inv_fac[b] % MOD *inv_fac[a-b]%MOD;//Factorial of a / (factorial of B * (factorial of a-b))

}

void answer(){
    sld(n); sld(m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            floyed[i][j] =0 ;
        }
    }
    for(int i=1;i<=m;i++){
        int x, y ;s(x);s(y);
        floyed[x][y] =1 ;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int g=1;g<=n;g++){
                floyed[j][g] |= floyed[j][i]&floyed[i][g];
            }
        }
    }
    cl(in),cl(out);int flag = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(floyed[i][j]){
                if(i == j){
                    flag = 1 ;
                    break;
                }
                in[j]++;
                out[i] ++;
            }

        }
        if(flag)break;
    }
    if(flag){
        for(int i=1;i<=n;i++)p(0);pn;
        return ;
    }

    for(int i=1;i<=n;i++){
        if(in[i]>=((n+1)/2)||out[i]>=((n+1)/2)){
            p(0);
        }
        else {
            p(1);
        }

    }pn;
   return ;
 }


int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0), cout.tie(0);
//       pre();
    LL t;sld(t);
    while(t--)
        answer();


    return 0;

}

Posted by guymrodgers on Sat, 14 May 2022 13:50:39 +0300