D
首先考虑枚举一个左端点
然后我们就会发现，对于一个位置来说，会影响它的只有前缀和后缀比它小的数
于是让每个数字不合法的都是一个区间
可以预处理$[L,i]$这个范围内有几个比它小的数，设为$x$
然后就能知道第一个让它不合法的位置($i - L - x$)个比它小的数的位置
而让它重新合法只需要再有一个比它小的数即可
于是我们就定义$f[i][j]$表示$i$后第$j$个比$a_i$小的数的位置，预处理这个即可。
最后就是一个线段覆盖问题，扫描线瞎跑一下
$O(n^2)$
#include <bits/stdc++.h>
using namespace std;
int a[5005][5005];
int T;
const int mx = 5000;
int pp[5005];
int Tree[5005];
int aa[5005];
int Sum[5005][5005];
int main(){
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--){
int N;
cin >> N;
for (int i = 1 ; i <= N ; i ++)
cin >> aa[i];
for (int i = 1 ; i <= N ; i ++)
for (int j = 1 ; j <= N ; j ++)
a[i][j] = 0;
for (int i = 1 ; i <= N ; i ++){
int cnt = 0;
a[i][0] = i;
for (int j = i + 1 ; j <= N ; j ++){
if (aa[j] < aa[i]){
cnt ++;
a[i][cnt] = j;
}
}
}
for (int i = 1 ; i <= N ; i ++){
for (int j = 1 ; j <= i ; j ++){
if (aa[j] < aa[i]) Sum[i][j] = Sum[i][j-1] + 1;
else Sum[i][j] = Sum[i][j-1];
}
}
int ans = 0;
for (int i = 1 ; i <= N ; i ++){
for (int j = i ; j <= N ; j ++)
pp[j] = 0;
for (int j = i ; j <= N ; j ++){
int x = Sum[j][j] - Sum[j][i-1];
int Len = j-i+1;
int y = Len - x-1;
int y1 = Len - x;
int x1 = a[j][y];
int x2 = a[j][y1];
if (x1 == 0) x1 = N+1;
if (x2 == 0) x2 = N+1;
//cout << i << " " << j << " " << x1 << " " << x2 << endl;
pp[x1] ++;
pp[x2]--;
}
int cnt = 0;
for (int j = i ; j <= N ; j ++){
cnt = cnt + pp[j];
if (cnt == 0) ans ++;
}
}
cout << ans << endl;
}
return 0;
}
E
辗转相除一定能构造一个合法方案。
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define x first
#define y second
#define endl "\n"
using namespace std;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int INF = 0x3f3f3f3f;
vector<array<int, 3>> ans;
void dfs(int x, int y, int n, int m)
{
if (n == 0 || m == 0)
return;
if (n > m)
{
int t = n / m;
int d = n % m;
for (int i = 0; i < t; i++)
{
ans.push_back({x + m * i, y, m});
}
dfs(x + m * t, y, d, m);
}
else
{
int t = m / n;
int d = m % n;
for (int i = 0; i < t; i++)
{
ans.push_back({x, y + n * i, n});
}
dfs(x, y + n * t, n, d);
}
}
void solve()
{
int n, m;
cin >> n >> m;
ans.clear();
cout << "YES" << endl;
dfs(0, 0, n, m);
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++)
{
cout << ans[i][0] << ' ' << ans[i][1] << ' ' << ans[i][2] << endl;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
I
有点不好解释的一个题
首先考虑把所有线段端点都压到数轴上
然后每条线段的覆盖情况无非三个情况：
1、无线段覆盖
2、有一条
3、有两条
分开统计一下这三种情况，并且记录当前枚举的点被几个线段覆盖
然后我们就只需要在每个线段离开的时候去统计它的贡献。如果当前离开的时候第$i$组是两条，并且有$n$覆盖的话，那么答案就加上$2^{cnt_2 -1}$
如果是$1$条，就加上$2^{cnt_2}$
因为我们贪心的想，每个线段一定是尽可能覆盖，直到不能再覆盖了才去统计答案。这样能保证不重不漏
然后扫描线扫一下就好啦(
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
struct Node{
int x,y,Type;
};
int temp(Node a,Node b){
if (a.x == b.x && a.Type == b.Type){
return a.y < b.y;
}
if (a.x == b.x){
return a.Type < b.Type;
}
return a.x<b.x;
}
int Pow(int x,int y){
int ans = 1;
for (;y;y>>=1){
if (y & 1) ans = 1ll * ans * x%MOD;
x = 1ll * x * x%MOD;
}
return ans;
}
int cnt[500005];
vector<Node> nw;
signed main(){
int N;
cin >> N;
for (int i = 1 ; i <= N ; i ++){
int l,r;
cin >> l >> r;
nw.push_back({l,i,1});
nw.push_back({r+1,i,-1});
cin >> l >> r;
nw.push_back({l,i,1});
nw.push_back({r+1,i,-1});
}
sort(nw.begin(),nw.end() ,temp);
int cnt1 = 0,ans = 0 ,ans1 = 0,cnt2 = 0;
for (auto v : nw){
int pos = v.x,bh = v.y,tp = v.Type;
if (tp == 1){
if (cnt[bh] == 0) {
cnt1 ++;
cnt[bh] ++;
}else
if (cnt[bh] == 1){
cnt[bh] ++;
cnt2 ++;
}
}else{
if (cnt[bh] == 1){
if (cnt1 == N) ans = (ans + Pow(2,cnt2))%MOD;
cnt[bh]--;
cnt1--;
} else {
cnt[bh]--;
if (cnt1 == N) (ans += Pow(2,cnt2-1))%=MOD;
cnt2--;
}
}
}
cout << ans%MOD << endl;
return 0;
}
G线代水平不行，没想出来
B数论水平不行，推慢了。
令人感慨(
标签：cnt,5005,int,2023,bh,多校,牛客,ans,nw From： https://www.cnblogs.com/si--nian/p/17629698.html