Codeforces Round 906 (Div. 2)(D推公式 E1分类讨论区间 E2 dp+线段树)

2023-12-01 04:44

本文主要是介绍Codeforces Round 906 (Div. 2)(D推公式 E1分类讨论区间 E2 dp+线段树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A - Doremy's Paint 3

推公式得

b1=b3=b5=b7....

b2=b4=b6=b8...

所以如果只有一个数或者两个数且数量差小于等于1即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=1000003;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
const long long inf=1e17;
int n,m,k;
vector<int> g[N];
int a[N];
void solve()
{cin>>n;map<int,int> mp;for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;sort(a+1,a+1+n);if(mp.size()<=2){if(mp.size()==1){cout<<"Yes\n";return ;}else{auto x=mp[a[1]];auto y=mp[a[n]];if(abs(x-y)<=1){cout<<"Yes\n";}else cout<<"No\n";}}else cout<<"No\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

B - Qingshan Loves Strings

老规矩操作题先思考操作的性质

如果T串本身不合法那么就NO了,且我们插入肯定是在相同的时候插入

比如 相邻的0 或相邻的1,这时候要求T串首尾要不同且能接的上

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=1000003;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
const long long inf=1e17;
int n,m,k;
vector<int> g[N];
int a[N];
bool check(string s){for(int i=1;i<s.size();i++){if(s[i]==s[i-1]) return false;}return true;
}
void solve()
{cin>>n>>m;string s,t;cin>>s>>t;if(check(s)){cout<<"YES\n";return ;    }else{if(!check(t)||t[0]!=t.back()){cout<<"NO\n";return ;}}for(int i=1;i<n;i++){if(s[i]==s[i-1]){if(s[i]==t[0]){cout<<"NO\n";return ;}}}cout<<"YES\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

C:C - Qingshan Loves Strings 2

看范围100 所以可以n^2去暴力

考虑插入哪个位置

如果 0XXXX0,因为只能插入 01 那么这个只能插入到翻转位置后的那个位置,否则就是无效插入

如果是1XXXX1,因为只能插入01 只能插入到第一个字母的前面

所以可得 如果当前是0 那么插入当前位置的翻转后的位置,如果当前是1,那么插入到当前位置的前面的位置

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=1000003;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
const long long inf=1e17;
int n,m,k;
vector<int> g[N];
int a[N];
int check(string s){int n=s.size()-1;for(int i=1;i<=(n+1)/2;i++){if(s[i]==s[n-i+1]){return i;}}return 0;
}
void solve()
{cin>>n;string s;cin>>s;vector<int> res;s="?"+s;for(int j=1;j<=300;j++){int x=check(s);if(!x){cout<<res.size()<<"\n";for(auto x:res) cout<<x<<" ";cout<<"\n";return ;}n=s.size()-1;//   cout<<s<<"\n";if(s[x]=='0'){res.push_back(n-x+1);string t;for(int i=0;i<=n-x+1;i++){t.push_back(s[i]);}t+="01";for(int i=n-x+1+1;i<=n;i++) t.push_back(s[i]);swap(s,t);}else{res.push_back(x-1);string t;for(int i=0;i<=x-1;i++){t.push_back(s[i]);}t+="01";for(int i=x;i<=n;i++) t.push_back(s[i]);swap(s,t);}}//  cout<<check(s)<<"\n";if(check(s)) cout<<-1<<"\n";else{cout<<res.size()<<"\n";for(auto x:res) cout<<x<<" ";cout<<"\n";return ;}
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

D - Doremy's Connecting Plan

这是个推公式题,肯定是用已经联通的块连向其他点

设只有两个数

ai+ aj >=i*j*c

然后发现好像不太能合并,然后可以想到1如果i=1,那么就单纯的变成

0>=j*c-aj,然后后面一直用1点去联通即可

证明

ai + aj>=i*j*c

a1+ai<i*c

a1+aj<j*c

假设只能连 i j的点,不能先连 1点,

用反证法得

a1+a1<(i+j-i*j)*c

因为i和j不能为1

所以这个(i+j-i*j)肯定是负数,不满足等式,所以证明如果能连i和j点,必然可以先连1点

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=1000003;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
const long long inf=1e17;
int n,m,k;
vector<int> g[N];
int a[N];
void solve()
{int c;cin>>n>>c;priority_queue<PII,vector<PII>,greater<PII>> q;for(int i=1;i<=n;i++){cin>>a[i];if(i!=1) q.emplace(i*c-a[i],i);}auto now=a[1];while(q.size()){auto t=q.top();if(now>=t.first){now+=a[t.second];q.pop();}else break;}if(q.size()) cout<<"No\n";else cout<<"Yes\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

E1 - Doremy's Drying Plan (Easy Version)

因为k=2,所以思考选哪两个区间

1.这两个区间相交

2.这两个区间不相交

因为只能去掉两个区间,所以如果有些点被大于两个区间得点覆盖直接去掉就行了,

对于第二个条件两个区间不相交,说明如果去掉某个区间,那么这个点只能被一个区间覆盖

所以我们预处理

s1:只被一个区间覆盖的点的前缀和

s2:只被两个区间覆盖的点的前缀和

然后第二个条件直接枚举每个区间的贡献的最大值和次大值相加即可

然后可能有人问万一最大值和次大值区间相交呢,这说明这个相交的点要被覆盖两次,

我们求这个用的是s1数组,所以不会重复计算贡献

即任意取两个区间

如果相交的部分至少被覆盖两次他们不会在s1的数组

不相交的部分相加即为第二个条件的答案

对于第一个条件

我们直接暴力枚举每个点,以当前端点为相交的部分即可

然后用个堆枚举即可

贡献就是 两个区间相交部分的s2区间和maxr到minl的s1部分

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=1000003;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
const long long inf=1e17;
int n,m,k;
vector<int> g[N];
int a[N];
void solve()
{cin>>n>>m>>k;vector<int> s1(n+10),s2(n+10),d(n+10);vector<array<int,2>> a;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;a.push_back({x,y});d[x]++,d[y+1]--;}int res=0;for(int i=1;i<=n;i++){d[i]+=d[i-1];if(d[i]==0) res++;if(d[i]==1) s1[i]++;if(d[i]==2) s2[i]++;s1[i]+=s1[i-1];s2[i]+=s2[i-1];}int cnt1=0,cnt2=0;for(int i=0;i<m;i++){int x=a[i][0],y=a[i][1];int cnt=s1[y]-s1[x-1];if(cnt>cnt1){cnt2=cnt1,cnt1=cnt;}else if(cnt>cnt2) cnt2=cnt;}int mx=cnt1+cnt2;priority_queue<PII> q;int idx=0;sort(a.begin(),a.end());for(int i=1;i<=n;i++){while(idx<m&&a[idx][0]<=i){q.emplace(a[idx][1],a[idx][0]);idx++;}while(q.size()&&q.top().first<i) q.pop();if(q.empty()) continue;auto t=q.top();q.pop();while(q.size()&&q.top().first<i) q.pop();q.push(t);if(q.size()>=2){auto t1=q.top();q.pop();auto t2=q.top();vector<int> c={t1.first,t1.second,t2.first,t2.second};sort(c.begin(),c.end());int cnt=s1[c[3]]-s1[c[0]-1]+(s2[c[2]]-s2[c[1]-1]);mx=max(mx,cnt);q.push(t1);}}cout<<res+mx<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

E2 - Doremy's Drying Plan (Hard Version)

考虑dp

状态:第i个点没被区间覆盖,且已经使用了j次机会的最大值

!!!!重点使得当前i点没被区间覆盖

举例说明

当前点5,使用了5次机会可以由

第4个点使用了5次机会获得(为啥机会没-1呢

因为f[4]代表着没被区间覆盖,说明f[4]已经把前面能覆盖到4的点的区间已经删除了)

第3个点使用4次机会获得

这里要把4到5的区间删去

以此类推

所以我们要找这个区间的最大值了

因为可能我后面再加个6的点,但我不增加区间,他可以由f[4][5]和f[5][5]最大值获得

所以涉及区间查询最大值,但是k很小,直接暴力每个k开个线段树即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=1000003;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
const long long inf=1e17;
int n,m,k;
vector<int> g[N];
int a[N];
struct node{int l,r,mx;
}tr[11][N*4];
void pushup(int p,int u){tr[p][u].mx=max(tr[p][u<<1].mx,tr[p][u<<1|1].mx);
}
void build(int p,int u,int l,int r)
{tr[p][u]={l,r,0};if(l==r) return ;int mid=l+r>>1;build(p,u<<1,l,mid);build(p,u<<1|1,mid+1,r);
}void modify(int p,int u,int x,int v){if(tr[p][u].l==tr[p][u].r&&tr[p][u].l==x){tr[p][u].mx=max(tr[p][u].mx,v);return ;}else{int mid = tr[p][u].l + tr[p][u].r >> 1;if(x <= mid) modify(p, u << 1, x,v);else modify(p, u << 1 | 1, x,v);pushup(p, u);}
}
int query(int p, int u, int l, int r) {if(!l && !r) return 0;if(l <= tr[p][u].l && r >= tr[p][u].r) return tr[p][u].mx;int mid = tr[p][u].l + tr[p][u].r >> 1;int res = 0;if(l <= mid) res = max(res, query(p, u << 1, l ,r));if(r > mid) res = max(res, query(p, u << 1 | 1, l, r));return res;
}void solve()
{cin>>n>>m>>k;vector<array<int,2>> seg;for(int i=0;i<=k;i++) build(i,1,1,n);vector<vector<int>> f(n+10,vector<int>(k+10));for(int i=0;i<m;i++){int x,y;cin>>x>>y;seg.push_back({x,y});}sort(seg.begin(),seg.end());multiset<PII> st;int res=0;for(int i=1,idx=0;i<=n;i++){while(idx<m&&seg[idx][0]<=i){st.insert({seg[idx][1],seg[idx][0]});idx++;}if(st.size()<=k){vector<int> S{0};S.push_back(i);for(auto [r, l] : st) S.push_back(l);sort(S.begin(), S.end());for(int j = st.size(); j <= k; j ++ ) {for(int z = S.size() - 2, w = 0; w <= j && z >= 0; w ++, z -- ) {int l = S[z], r = S[z + 1] - 1;if(l > r) continue;f[i][j] = max(f[i][j], query(j - w, 1, l ,r) + 1);modify(j, 1, i, f[i][j]);}}res = max(res, f[i][k]);}PII tmp;while(st.size() && (tmp = *(st.begin())).first == i)st.extract(tmp);}cout<<res<<"\n";}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

这篇关于Codeforces Round 906 (Div. 2)(D推公式 E1分类讨论区间 E2 dp+线段树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/439849

相关文章

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务,目标是自动识别图像中的对象类别。通过卷积神经网络(CNN)等深度学习技术,我们可以构建高效的图像分类系统,广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统,包括环境

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :