2023牛客暑期多校训练营9

D.Non-Puzzle: Error Permutation

题意：给出一个排列，计算其有多少个子区间，满足区间内的第\(i\)个数不是第\(i\)小的数

Solution

首先明白一点，对于一个数，它的大小排序只会变大而不会变小，变大的要求是后面遇到比它小的数。

所以我们可以发现，对于一个数，它会有以下几种情况：

1.在开始的一段区间内不是第\(i\)小的数，在中间的一段区间内是第\(i\)小的数，在后面的区间内不是第\(i\)小的数

2.在开始的一段区间内是第\(i\)小的数，在后面的区间内不是第\(i\)小的数

于是我们可以通过枚举左端点，然后遍历从左端点开始的每一个数，处理出哪些点是不合法的，剩下的就是合法的答案了。

真ex，被卡常了，还以为思路错了

int a[5005];
int e[5005][5005];
int g[5005];
int cnt[5005][5005];
int vis[5005];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        g[i]=0;
        vis[i] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (a[i] < a[j])e[j][g[j]++]=i;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            cnt[i][j] = cnt[i][j - 1];
            if (a[j] < a[i])
                cnt[i][j] += 1;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            int pos = cnt[j][j] - cnt[j][i - 1] + 1, num = j - i + 1;
            // cout<<a[j]<<":"<<pos<<"\n";
            int l = num - pos;
            if (l == 0)
                vis[j]--;

            if (g[j] < l)
                continue;

            if (l == 0)
            {
                if (g[j] == 0)
                    continue;
                int posr = e[j][0];
                vis[posr]++;
            }
            else if (g[j] == l)
            {
                int posl = e[j][l - 1];
                vis[posl]--;
            }
            else
            {
                int posl = e[j][l - 1], posr = e[j][l];
                vis[posl]--;
                vis[posr]++;
            }
           /* for (int k = i; k <= n; k++)
            {
                cout << vis[k] << " \n"[k == n];
            }*/
        }

        for (int j = i; j <= n; j++)
        {
            vis[j] += vis[j - 1];
            if (vis[j] >= 0)
                ans++;
        }
        for (int j = 1; j <= n; j++)
            vis[j] = 0;
       // cout << ans << "\n";
    }
    cout << ans << "\n";
}

E.Puzzle: Square Jam

题意：给出一个\(n\times m\)的矩形，要求把它分成若干个正方形，使得每个点（包括正方形上的不被四个正方形所包含）

Solution

贪心，看长和宽，哪个短一些就取了作为正方形边长，然后递归即可

struct node
{
	int sx,sy,a;
};

vector<node>ans;
void dfs(int sx,int sy,int x,int y)
{
	//cout<<sx<<" "<<sy<<" "<<x<<" "<<y<<"\n";
	if(x==1&&y==1)
	{
		ans.push_back({sx,sy,1});
		return;
	}
	if(x==y)
	{
		ans.push_back({sx,sy,x});
	}
	else if(x>y)
	{
		for(int i=1;i<=x/y;i++)
		{
			ans.push_back({sx+(i-1)*y,sy,y});
		}
		if(x%y)dfs(sx+(x/y)*y,sy,x%y,y);
	}else
	{
		for(int i=1;i<=y/x;i++)
		{
			ans.push_back({sx,sy+(i-1)*x,x});
		}
		if(y%x)dfs(sx,sy+(y/x)*x,x,y%x);
	}
}


void solve()
{
	ans.clear();
	int x,y;cin>>x>>y;
	dfs(0,0,x,y);
	cout<<"YES\n";
	cout<<ans.size()<<"\n";
	for(auto it:ans)
	{
		cout<<it.sx<<" "<<it.sy<<" "<<it.a<<"\n";
	}
}

I.Non-Puzzle: Segment Pair

题意：给出\(n\)对区间，每对可以选择其中的一个，问有多少种选法，可以使得选出的\(n\)个区间至少有一个点重合。

Solution

把所有区间用差分操作的形式表示，考虑枚举每一段区间，定义数组\(b[0/1/2]\)表示当前这段区间被某一组区间所覆盖的个数为\(0/1/2\)个，那么当且仅当\(b[0]\)为\(0\)的时候才对答案有贡献，贡献为\(2^{b[2]}\)

懵哥真厉害，完全想不到的维护操作

int b[3];

struct node
{
    int x, y, id;
    bool operator<(const node &t) const &
    {
        if (x != t.x)
            return x < t.x;
        return y < t.y;
    }
};
int a[N];//表示第i组区间对当前区间的覆盖数
void solve()
{
    int n;
    cin >> n;
    int maxx = 0;
    vector<node> v;
    for (int i = 1; i <= n; i++)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        v.push_back({l1, 1, i});
        v.push_back({r1 + 1, -1, i});
        v.push_back({l2, 1, i});
        v.push_back({r2 + 1, -1, i});
    }
    sort(v.begin(), v.end());

    int ans = 0;
    b[0] = n;
    for (auto it : v)
    {
        b[a[it.id]]--;
        a[it.id] += it.y;
        if (it.y == 1 && !b[0])
        {
            ans = (ans + ksm(2, b[2])) % mod;
        }
        b[a[it.id]]++;
    }

    cout << ans << "\n";
}