
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
const int maxn=1e2+10;
 
ll ans=0;
void dfs(int sum1,int sum2,int cnt)
{
    if(sum1<0||sum2<0)return;
    if(cnt==7)
    {
        if(sum1==0&&sum2==0)ans++;
        return;
    }
    for(int i=0;i<=sum1;i++)
    {
        for(int j=0;j<=sum2;j++)
        {
            if(i+j>=2&&i+j<=5)
            {
                dfs(sum1-i,sum2-j,cnt+1);
            }
        }
    }
}
void solve()
{
    dfs(9,16,0);
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tn=1;
    //cin>>tn;
    while(tn--)
    {
        solve();
    }
    return 0;
}

试题 C: 三国游戏

时间限制 : 3.0s

内存限制 : 512.0MB

本题总分： 10 分

【问题描述】

小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵

X , Y , Z ( 一开始可以认为都为 0 ) 。游戏有 n 个可能会发生的事件，每个事件之

间相互独立且最多只会发生一次，当第 i 个事件发生时会分别让 X , Y , Z 增加

A i , B i , C i 。

当游戏结束时 ( 所有事件的发生与否已经确定 ) ，如果 X , Y , Z 的其中一个大

于另外两个之和，我们认为其获胜。例如，当 X > Y + Z 时，我们认为魏国获

胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件 ?

如果不存在任何能让某国获胜的情况，请输出 − 1 。

【输入格式】

输入的第一行包含一个整数 n 。

第二行包含 n 个整数表示 A i ，相邻整数之间使用一个空格分隔。

第三行包含 n 个整数表示 B i ，相邻整数之间使用一个空格分隔。

第四行包含 n 个整数表示 C i ，相邻整数之间使用一个空格分隔。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

3

1 2 2

2 3 2

1 0 7

【样例输出】

2

【样例说明】

发生两个事件时，有两种不同的情况会出现获胜方。

发生 1 , 2 事件时蜀国获胜。

发生 1 , 3 事件时吴国获胜。

【评测用例规模与约定】

对于 40 % 的评测用例， n ≤ 500 ；

对于 70 % 的评测用例， n ≤ 5000 ；

对于所有评测用例， 1 ≤ n ≤ 10 5 ， 1 ≤ A i , B i , C i ≤ 10 9 。

贪心，对于每个国家我们都重新排序这n个事件，比如我是魏国，那我按照x-y-z从大到小排序，

然后统计答案即可


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
const int maxn=1e5+10;
 
struct node
{
    ll x,y,z;
};
bool cmp1(node &a,node &b)
{
   return a.x-(a.y+a.z)>b.x-(b.y+b.z);
}
bool cmp2(node &a,node &b)
{
   return a.y-(a.x+a.z)>b.y-(b.x+b.z);
}
bool cmp3(node &a,node &b)
{
   return a.z-(a.y+a.x)>b.z-(b.y+b.x);
}
int n;
node a[maxn],b[maxn],c[maxn];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x;
        b[i].x=c[i].x=a[i].x;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].y;
        b[i].y=c[i].y=a[i].y;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].z;
        b[i].z=c[i].z=a[i].z;
    }
    sort(a+1,a+n+1,cmp1);
    sort(b+1,b+n+1,cmp2);
    sort(c+1,c+n+1,cmp3);
    ll ans=-1;
    for(ll i=1,x=0,y=0,z=0;i<=n;i++)
    {
        x+=a[i].x;
        y+=a[i].y;
        z+=a[i].z;
        if(x>y+z)
        {
            ans=max(ans,i);
        }
    }
    for(ll i=1,x=0,y=0,z=0;i<=n;i++)
    {
        x+=b[i].x;
        y+=b[i].y;
        z+=b[i].z;
        if(y>x+z)
        {
            ans=max(ans,i);
        }
    }
    for(ll i=1,x=0,y=0,z=0;i<=n;i++)
    {
        x+=c[i].x;
        y+=c[i].y;
        z+=c[i].z;
        if(z>y+x)
        {
            ans=max(ans,i);
        }
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tn=1;
    //cin>>tn;
    while(tn--)
    {
        solve();
    }
    return 0;
}

试题 D: 平均

时间限制 : 3.0s

内存限制 : 512.0MB

本题总分： 10 分

【问题描述】

有一个长度为 n 的数组（

n 是 10 的倍数），每个数 a i 都是区间 [0 , 9] 中的

整数。小明发现数组里每种数出现的次数不太平均，而更改第 i 个数的代价为

b i ，他想更改若干个数的值使得这 10 种数出现的次数相等（都等于

n

10

），请问

代价和最少为多少。

【输入格式】

输入的第一行包含一个正整数 n 。

接下来 n 行，第 i 行包含两个整数 a i , b i ，用一个空格分隔。

【输出格式】

输出一行包含一个正整数表示答案。

【样例输入】

10

1 1

1 2

1 3

2 4

2 5

2 6

3 7

3 8

3 9

4 10

【样例输出】

27

【样例说明】

只更改第 1 , 2 , 4 , 5 , 7 , 8 个数，需要花费代价 1 + 2 + 4 + 5 + 7 + 8 = 27 。

【评测用例规模与约定】

对于 20 % 的评测用例， n ≤ 1000 ；

对于所有评测用例， n ≤ 100000 , 0 < b i ≤ 2 × 10 5 。

贪心,按找b从小到大，然后遇到大于n/10的我就把它变成其他数


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
const int maxn=1e5+10;
 
struct node
{
    int a,b;
    bool operator<(const node &o)const
    {
        return b<o.b;
    }
};
int n;
node ai[maxn];
int cnt[20];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>ai[i].a>>ai[i].b;
        cnt[ai[i].a]++;
    }
    sort(ai+1,ai+n+1);
    ll ans=0,f=n/10;
    for(int i=1;i<=n;i++)
    {
        if(cnt[ai[i].a]>f)
        {
            for(int j=0;j<=9;j++)
            {
                if(cnt[j]<f)
                {
                    cnt[ai[i].a]--;
                    cnt[j]++;
                    ans=ans+ai[i].b;
                    break;
                }
            }
        }
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tn=1;
    //cin>>tn;
    while(tn--)
    {
        solve();
    }
    return 0;
}

试题 E: 填充

时间限制 : 3.0s

内存限制 : 512.0MB

本题总分： 15 分

【问题描述】

有一个长度为 n 的 01 串，其中有一些位置标记为 ? ，这些位置上可以任意

填充 0 或者 1 ，请问如何填充这些位置使得这个 01 串中出现互不重叠的 00 和

11 子串最多，输出子串个数。

【输入格式】

输入一行包含一个字符串。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

1110?0

【样例输出】

2

【样例说明】

如果在问号处填 0 ，则最多出现一个 00 和一个 11 ： 111000 。

【评测用例规模与约定】

对于所有评测用例， 1 ≤ n ≤ 1000000 。

贪心，其实由于不交叉，那么遇到？我们就当作0，1都加了就可以，然后遇到0，1计数等于2就统计答案并清空


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
const int maxn=1e6+10;
 
int n;
char a[maxn];
int f[maxn];
void solve()
{
    cin>>a+1;
    n=strlen(a+1);
    int ans=0,cnt1=0,cnt0=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]=='1')
        {
           cnt1++;cnt0=0;
        }else if(a[i]=='0')
        {
            cnt0++;cnt1=0;
        }else if(a[i]=='?')
        {
            if(cnt1==1)
            {
                cnt1++;
            }else if(cnt0==1)
            {
                cnt0++;
            }else
            {
                cnt1++;cnt0++;
            }
        }
        //cout<<cnt1<<" "<<cnt0<<endl;
        if(cnt1==2||cnt0==2)
        {
            ans++;
            cnt1=0;cnt0=0;
        }
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tn=1;
    //cin>>tn;
    while(tn--)
    {
        solve();
    }
    return 0;
}

试题 F: 棋盘

时间限制 : 3.0s

内存限制 : 512.0MB

本题总分： 15 分

【问题描述】

小蓝拥有 n × n 大小的棋盘，一开始棋盘上全都是白子。小蓝进行了 m 次

操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反 ( 也就是白色棋

子变为黑色，黑色棋子变为白色 ) 。请输出所有操作做完后棋盘上每个棋子的颜

色。

【输入格式】

输入的第一行包含两个整数 n , m ，用一个空格分隔，表示棋盘大小与操作

数。

接下来 m 行每行包含四个整数 x 1 , y 1 , x 2 , y 2 ，相邻整数之间使用一个空格分

隔，表示将在 x 1 至 x 2 行和 y 1 至 y 2 列中的棋子颜色取反。

【输出格式】

输出 n 行，每行 n 个 0 或 1 表示该位置棋子的颜色。如果是白色则输出 0

，否则输出 1 。

【样例输入】

3 3

1 1 2 2

2 2 3 3

1 1 3 3

【样例输出】

001

010

100

【评测用例规模与约定】

对于 30 % 的评测用例， n m ≤ 500 ；

对于所有评测用例， 1 ≤ n , m ≤ 2000 ， 1 ≤ x 1 ≤ x 2 ≤ n ， 1 ≤ y 1 ≤ y 2 ≤ m 。

二维差分对于每个矩阵，我们都让矩阵内的值+1，最后如果这个位置是奇数就是黑棋，否则白棋


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
const int maxn=2e3+10;
 
int n,m;
int a[maxn][maxn];
void solve()
{
    cin>>n>>m;
    for(int i=1,x1,y1,x2,y2;i<=m;i++)
    {
        cin>>x1>>y1>>x2>>y2;
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2);
        a[x1][y1]++;
        a[x1][y2+1]--;
        a[x2+1][y1]--;
        a[x2+1][y2+1]++;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            if(a[i][j]&1)cout<<"1";
            else cout<<"0";
        }
        cout<<endl;
    }
 
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tn=1;
    //cin>>tn;
    while(tn--)
    {
        solve();
    }
    return 0;
}

试题 G: 子矩阵

时间限制 : 5.0s

内存限制 : 512.0MB

本题总分： 20 分

【问题描述】

给定一个 n × m （

n 行 m 列）的矩阵。

设一个矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的

所有大小为 a × b （

a 行 b 列）的子矩阵的价值的和。

答案可能很大，你只需要输出答案对 998244353 取模后的结果。

【输入格式】

输入的第一行包含四个整数分别表示 n , m , a , b ，相邻整数之间使用一个空

格分隔。

接下来 n 行每行包含 m 个整数，相邻整数之间使用一个空格分隔，表示矩

阵中的每个数 A i , j 。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

2 3 1 2

1 2 3

4 5 6

【样例输出】

58

【样例说明】

1 × 2 + 2 × 3 + 4 × 5 + 5 × 6 = 58 。

【评测用例规模与约定】

对于 40 % 的评测用例， 1 ≤ n , m ≤ 100 ；

对于 70 % 的评测用例， 1 ≤ n , m ≤ 500 ；

对于所有评测用例， 1 ≤ a ≤ n ≤ 1000 1 ≤ b ≤ m ≤ 1000 1 ≤ A i , j ≤ 10 9 。

单调队列，或者线段树

先维护每个位置前b列的最大最小值，然后再在新矩阵上跑，每个位置前a行的最大最小值，那么不就求的了以每个位置为右下角的a*b的矩阵了嘛

单调队列维护复杂度O(N*N)，线段树O(N*N*logN)


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
#define big __int128
const ll mod=998244353 ;
const int maxn=1e3+10;
 
int n,m,x,y;
ll a[maxn][maxn];
ll heng[maxn][maxn];
ll shu[maxn][maxn];
ll st[maxn],id[maxn];
int s=0,e=0;
void solve()
{
    cin>>n>>m>>x>>y;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)//维护i,j位置(j-b+1,j)之间最小值
    {
        s=1;e=1;
        st[e]=a[i][1];
        id[e]=1;
        for(int j=1;j<=m;j++)
        {
            while(s<=e&&id[s]<j-y+1)s++;
            while(s<=e&&st[e]>=a[i][j])e--;
            st[++e]=a[i][j];
            id[e]=j;
            heng[i][j]=st[s];
        }
    }
    for(int j=1;j<=m;j++)//维护i,j位置往上a，b矩阵的之间最小值
    {
        s=1;e=1;
        st[e]=heng[1][j];
        id[e]=1;
        for(int i=1;i<=n;i++)
        {
            while(s<=e&&id[s]<i-x+1)s++;
            while(s<=e&&st[e]>=heng[i][j])e--;
            st[++e]=heng[i][j];
            id[e]=i;
            shu[i][j]=st[s];
        }
    }
    for(int i=1;i<=n;i++)//维护i,j位置(j-b+1,j)之间最大值
    {
        s=1;e=1;
        st[e]=a[i][1];
        id[e]=1;
        for(int j=1;j<=m;j++)
        {
            while(s<=e&&id[s]<j-y+1)s++;
            while(s<=e&&st[e]<=a[i][j])e--;
            st[++e]=a[i][j];
            id[e]=j;
            heng[i][j]=st[s];
        }
    }
    ll ans=0;
     for(int j=1;j<=m;j++)//维护i,j位置往上a，b矩阵的之间最大值，并计算答案
    {
        s=1;e=1;
        st[e]=heng[1][j];
        id[e]=1;
        for(int i=1;i<=n;i++)
        {
            while(s<=e&&id[s]<i-x+1)s++;
            while(s<=e&&st[e]<=heng[i][j])e--;
            st[++e]=heng[i][j];
            id[e]=i;
            if(i>=x&&j>=y)ans=(ans+shu[i][j]*st[s]%mod)%mod;
        }
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tn=1;
    //cin>>tn;
    while(tn--)
    {
        solve();
    }
    return 0;
}

试题 H: 公因数匹配

时间限制 : 3.0s

内存限制 : 512.0MB

本题总分： 20 分

【问题描述】

给定 n 个正整数 A i ，请找出两个数 i , j 使得 i < j 且 A i 和 A j 存在大于 1 的

公因数。

如果存在多组 i , j ，请输出 i 最小的那组。如果仍然存在多组 i , j ，请输出 i

最小的所有方案中 j 最小的那组。

【输入格式】

输入的第一行包含一个整数 n 。

第二行包含 n 个整数分别表示 A 1 A 2 · · · A n ，相邻整数之间使用一个空格

分隔。

【输出格式】

输出一行包含两个整数分别表示题目要求的 i , j ，用一个空格分隔。

【样例输入】

5

5 3 2 6 9

【样例输出】

2 4

【评测用例规模与约定】

对于 40 % 的评测用例， n ≤ 5000 ；

对于所有评测用例， 1 ≤ n ≤ 10 5 ， 1 ≤ A i ≤ 10 6 。

正常暴力N*N是不行的，然后我们考虑优化，其实只用枚举质数，然后通过埃氏筛选择这样就可以

在O(K*N*lnN)复杂度下实现，这里K是这个数的质因子个数，最坏情况就是全是这个质因子个数的数


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
const int maxn=1e6+10;
 
int n;
int f[maxn];
vector<int>v[maxn];
void solve()
{
    cin>>n;
    for(int i=1,j;i<=n;i++)
    {
        cin>>j;
        v[j].pd(i);
    }
    for(int i=1;i<=1000000;i++)
    {
        sort(v[i].begin(),v[i].end());
    }
    int l=maxn,r=maxn;
    for(int i=2;i<=1000000;i++)
    {
        if(!f[i])
        {
            vector<int>ans;
            for(auto id:v[i])
            {
                ans.pd(id);
            }
            for(int j=i+i;j<=1000000;j+=i)
            {
                f[j]=1;
                for(auto id:v[j])
                {
                    ans.pd(id);
                }
            }
            if(ans.size()>=2)
            {
                sort(ans.begin(),ans.end());
                if(l>ans[0])
                {
                    l=ans[0];
                    r=ans[1];
                }else if(l==ans[0]&&r>ans[1])
                {
                    r=ans[1];
                }
            }
        }
    }
    cout<<l<<" "<<r;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tn=1;
    //cin>>tn;
    while(tn--)
    {
        solve();
    }
    return 0;
}

试题 I: 异或和之差

时间限制 : 3.0s

内存限制 : 512.0MB

本题总分： 25 分

【问题描述】

给定一个含有 n 个元素的数组 A i ，你可以选择两个不相交的子段。求出这

两个子段内的数的异或和的差值的最大值。

【输入格式】

输入的第一行包含一个整数 n 。

第二行包含 n 个整数 A i ，相邻整数之间使用一个空格分隔。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

6

1 2 4 9 2 7

【样例输出】

14

【样例说明】

两个子段可以分别选 1 和 4 ， 9 ， 2 ，差值为 15 − 1 = 14 。

【评测用例规模与约定】

对于 40 % 的评测用例， n ≤ 5000 ；

对于所有评测用例， 2 ≤ n ≤ 2 × 10 5 ， 0 ≤ A i ≤ 2 20 。

01字典树，前缀和

01字典树内存前缀异或的值，然后查询最大最小值，不就得到了以这个位置为末尾的区间最大最小异或值，记得要先加入个0，表示区间不去

后缀异或同理


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
const int maxn=2e5+10;
 
struct tree01
{
    int tot;
    int ch[maxn<<5][2];
    void init()
    {
        for(int i=0;i<=tot;i++)ch[i][0]=ch[i][1]=0;
    }
    void add(int x)
    {
        int u=0;
        for(int i=20;i>=0;i--)
        {
            int t=(x>>i)&1;
            if(!ch[u][t])
            {
                ch[u][t]=++tot;
            }
            u=ch[u][t];
        }
    }
    int querymx(int x)
    {
        int u=0;
        int ans=0;
        for(int i=20;i>=0;i--)
        {
            int t=(x>>i)&1;
            if(ch[u][t^1])
            {
                u=ch[u][t^1];
                ans+=(1<<i);
            }else
            {
                u=ch[u][t];
            }
        }
        return ans;
    }
    int querymi(int x)
    {
        int u=0;
        int ans=0;
        for(int i=20;i>=0;i--)
        {
            int t=(x>>i)&1;
            if(ch[u][t])
            {
                u=ch[u][t];
            }else
            {
                u=ch[u][t^1];
                ans+=(1<<i);
            }
        }
        return ans;
    }
}tree01;
int n;
int a[maxn];
int rmx[maxn],rmi[maxn];//[1,R]区间内的异或最大值最小值
int lmx[maxn],lmi[maxn];//[L,n]区间内的异或最大值最小值
void solve()
{
    cin>>n;
    for(int i=0;i<=n+1;i++)
    {
        rmi[i]=lmi[i]=1e9;
    }
    tree01.tot=0;
    tree01.add(0);//先加个0表示区间不取
    for(int i=1,sum=0;i<=n;i++)
    {
        cin>>a[i];
        sum^=a[i];
        rmx[i]=max(rmx[i-1],tree01.querymx(sum));
        rmi[i]=min(rmi[i-1],tree01.querymi(sum));
        tree01.add(sum);
        //cout<<rmx[i]<<" "<<rmi[i]<<endl;
    }
    tree01.init();
    tree01.tot=0;
    tree01.add(0);//先加个0表示区间不取
    for(int i=n,sum=0;i>=1;i--)
    {
        sum^=a[i];
        lmx[i]=max(lmx[i+1],tree01.querymx(sum));
        lmi[i]=min(lmi[i+1],tree01.querymi(sum));
        tree01.add(sum);
        //cout<<rmx[i]<<" "<<rmi[i]<<endl;
    }
    int ans=0;
    for(int i=1;i<n;i++)
    {
        ans=max(ans,rmx[i]-lmi[i+1]);
        ans=max(ans,lmx[i+1]-rmi[i]);
//        cout<< rmx[i] << " "<< lmi[i+1] <<" "<< lmx[i]<<" "<<rmi[i-1]<<"\n"; 
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tn=1;
    //cin>>tn;
    while(tn--)
    {
        solve();
    }
    return 0;
}

试题 J: 太阳

时间限制 : 3.0s

内存限制 : 512.0MB

本题总分： 25 分

【问题描述】

这天，小蓝在二维坐标系的点 ( X , Y ) 上放了一个太阳，看做点光源。

他拿来了 n 条线段，将它们平行于 x 轴放置在了坐标系中，第 i 条线段的

左端点在 x i , y i ，长度为 l i 。线段之间不会有重合或部分重合的情况（但可能出

现端点相交）。小蓝想知道有多少条线段能被太阳照亮（一条线段有长度大于 0

的部分被照亮就算）。

【输入格式】

输入的第一行包含三个正整数 n , X , Y ，相邻整数之间使用一个空格分隔。

接下来 n 行，第 i 行包含三个整数 x i , y i , l i ，相邻整数之间使用一个空格分

隔。

【输出格式】

输出一行包含一个正整数表示答案。

【样例输入】

3 10 2000000

5 3 5

6 2 4

0 1 10

【样例输出】

2

【样例说明】

第一条线段在最上面被照亮，第二条线段被第一条完全挡住，第三条线段

左边的一段能被照亮。

【评测用例规模与约定】

对于 30 % 的评测用例， n ≤ 1000 ；

对于所有评测用例， 1 ≤ n ≤ 100000 , 0 ≤ x i , X ≤ 10 7 , 0 < y i ≤ 10 5 , 0 < l i ≤

100 , 10 6 < Y ≤ 10 7 。

把线段投射到y=0的位置，然后按照y排序，区间覆盖

由于区间端点会是小数，我采用了珂朵莉树


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second
#define pd push_back
#define pii pair<double,double>
#define It set<ran>::iterator
const int maxn=1e5+10;
const double inf=1e15;
 
struct ran{
    double l, r;
    mutable int v;//mutable 关键字定义一个强制可变量
    bool operator <(const ran &x)const{//运算符重载,用于set的排序
        return l < x.l;//按区间的左端点从小到大来排
    }
};
struct ODT
{
    set<ran>tr;//珂朵莉树的定义
    int ans=0;
 
    It split(double pos)
    {
        It it = tr.lower_bound({pos, -1, 0});//找到所需的pos的迭代器
        if(it != tr.end() && it->l == pos)return it;//看看这个迭代器的l是不是所需要的pos，是的话直接返回就行
        --it;//不是的话就说明肯定是在前一个里面
        double l = it->l;
        double r = it->r;
        int v = it->v;
        tr.erase(it);//我们删掉这个区间
        tr.insert({l, pos - 1, v});//重新塞入两个区间[l, pos -1 ],[pos, r]
        return tr.insert({pos, r, v}).first;//返回以pos开头的区间的迭代器
    }
    void emerge(double l, double r, int x)
    {
        It itr = split(r + 1e-15), itl = split(l);//先找到r+1的迭代器位置，再找l的迭代器位置
 
        //操作
        It it=itl;
        int f=0;
        for(;it!=itr;++it)
        {
            if((it->v)==0)f=1;
        }
        ans+=f;
        //操作
 
        tr.erase(itl, itr);//删掉这一段迭代器
        tr.insert({l, r, x});//重新插入所需区间
    }
 
}odt;
 
struct node
{
    double x1,x2,y;
    bool operator<(const node&o)const
    {
        return y>o.y;
    }
};
int n;
double X,Y;
node a[maxn];
double to0(int x,int y)
{
    if(x==X)return x;
    double k=(Y-y)/(X-x);
    double b=k*X-Y;
    return b/k;
}
void solve()
{
    cin>>n>>X>>Y;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x1>>a[i].y>>a[i].x2;
        a[i].x2+=a[i].x1;
        a[i].x1=to0(a[i].x1,a[i].y);
        a[i].x2=to0(a[i].x2,a[i].y);
    }
    sort(a+1,a+n+1);
    //区间覆盖，我选择珂朵莉树
    odt.tr.insert({-inf,inf,0});
    for(int i=1;i<=n;i++)
    {
        odt.emerge(a[i].x1,a[i].x2,1);
    }
    cout<<odt.ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tn=1;
    //cin>>tn;
    while(tn--)
    {
        solve();
    }
    return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/395298

第十四届蓝桥杯大赛软件赛省赛Java 大学 C 组_2.分糖果 两种糖果分别有9个和16个,要全部分给7个小朋友,每个小朋友得到的糖果总p

试题 A: 求和

试题 B: 分糖果