24.11.10
星期一：
补 23ICPC 合肥 G cf传送门
思路：由使第 k个最大这种条件易联想到二分，但是如何check是个问题
check使用dp，先想到个比较朴素的状态设定，dp【i】【j】表示考虑到第 i个，已有 j个连续1段长度>=mid，考虑转移，是从dp【i-mid】【j-1】转移还是从dp【i-mid-1】【j-1】进行转移呢？两种转移都有问题，不知道第 i-mid个是否是第 j-1段的末尾1，就有可能出现第 j-1段和第 j段连一起的情况
于是定义状态为dp【i】【j】【0/1】表示考虑到第 i个，共有 j段，第 i个 不是/是 第 j段的末尾1 ，即可进行正常转移
代码如下：
const int N=2e5+10,M=1e4+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
ll m,k;
string s;
int sum[N];
int dp[N][6][2];
bool check(int x){
for(int i=0;i<=n;i++)
for(int j=0;j<=5;j++) j?dp[i][j][0]=dp[i][j][1]=1e9:dp[i][j][1]=1e9;
dp[0][0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
if(j && i-x>=0) dp[i][j][1]=dp[i-x][j-1][0]+sum[i]-sum[i-x];
if(s[i]=='1') dp[i][j][0]=dp[i-1][j][0];
else dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1]);
}
}
return min(dp[n][k][0],dp[n][k][1])<=m;
}
void solve(){
cin >> n >> m >> k;
cin >> s; s=" "+s;
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(s[i]=='0');
int l=1,r=(n+k-1)/k,res=-1;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) res=mid,l=mid+1;
else r=mid-1;
}
cout << res << "\n";
}学而时习之，20届东南校赛 J cf传送门
上半年被这题拿下了，现在重做倒没什么难度了
思路：朴素定义 dp【i】【j】表示考虑到第 i个，分了 j段的最小值
复杂度很明显可以接受 n^2 *k，枚举 i，j，再枚举转移的状态，此转移需要知道任何区间中的布尔值总和，简单区间dp处理出sum【l】【r】
代码如下：
const int N=2e5+10,M=1e4+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
ll a[3030],sum[3030][3030];
ll dp[3030][22];
void solve(){
ll k,x; cin >> n >> k >> x;
for(int i=1;i<=n;i++){
cin >> a[i];
a[i]+=a[i-1];
}
//for(int i=1;i<=n;i++)
//for(int j=i;j<=n;j++) sum[i][j]=sum[i+1][j]+sum[i][j-1]-sum[i+1][j-1]+(a[j]-a[i-1]==x);
for(int len=1;len<=n;len++){ //第一层枚举长度
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
sum[l][r]=sum[l+1][r]+sum[l][r-1]-sum[l+1][r-1]+(a[r]-a[l-1]==x);
}
}
for(int i=0;i<=n;i++) for(int j=0;j<=k;j++) dp[i][j]=1e18;
dp[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
for(int y=j-1;y<i;y++)
dp[i][j]=min(dp[y][j-1]+sum[y+1][i],dp[i][j]);
cout << dp[n][k] << "\n";
//cout << sum[1][3];
}星期二：
补 24 辽宁省赛 G cf传送门
思路：考虑把每个数当作魔力数组的第一个最大值来统计，不重不漏
需要知道左边第一个大于等于ai的值下标，以及右边第一个大于ai值的下标，和以i为第一次，ai值第k次出现的下标，这些信息比较好统计，之后可以直接算出答案
代码如下：
const int N=1e6+10,M=5e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
int a[N];
int b[N];
int lm[N],rm[N],lst[N],nxt[N];
void solve(){
ll k; cin >> n >> k;
for(int i=1;i<=n;i++){
cin >> a[i];
b[i]=0;
}
for(int i=1;i<=n;i++){
if(!b[a[i]]) lst[i]=1;
else lst[i]=b[a[i]]+1;
b[a[i]]=i;
}
map<int,queue<int>>qu;
for(int i=n;i;i--){
qu[a[i]].push(i);
if((int)qu[a[i]].size()>k) qu[a[i]].pop();
if((int)qu[a[i]].size()<k) nxt[i]=n+1;
else nxt[i]=qu[a[i]].front();
}
stack<int>sk;
for(int i=1;i<=n;i++){
while(!sk.empty() && a[sk.top()]<=a[i]) sk.pop();
if(sk.empty()) lm[i]=1;
else lm[i]=sk.top()+1;
sk.push(i);
}
while(!sk.empty()) sk.pop();
for(int i=n;i;i--){
while(!sk.empty() && a[sk.top()]<=a[i]) sk.pop();
if(sk.empty()) rm[i]=n;
else rm[i]=sk.top()-1;
sk.push(i);
}
ll ans=0;
for(int i=1;i<=n;i++){
int l=i-max(lm[i],lst[i])+1,r=rm[i]-nxt[i]+1;
if(l>0 && r>0) ans+=1ll*l*r;
}
cout << ans << "\n";
//for(int i=1;i<=n;i++) cout << nxt[i] << " ";
}补 D cf传送门
思路：和东南校赛那题有点类似，f【i】【j】表示 i点与 i - j点中组成的最长线段长度
此题不需要处理出 i - j 区间所有线段的信息，n^2枚举足够把所有状态枚举到
代码如下：
const int N=2e5+10,M=1e4+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
double dis(ll x1,ll y1,ll x2,ll y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
ll x[5050],y[5050];
double dp[5050],f[5050][5050];
void solve(){
cin >> n;
for(int i=1;i<=n;i++) cin >> x[i] >> y[i];
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
f[i][j]=max(dis(x[i],y[i],x[j],y[j]),f[i][j]);
for(int i=1;i<=n;i++)
for(int j=i-1;~j;j--)
dp[i]=max(dp[j]+f[j+1][i],dp[i]);
cout << fixed << setprecision(8) << dp[n] << "\n";
}星期四：
补 湖南省赛 E cf传送门
思路：看数据范围想到状压
f【mask】表示的并不是 mask的长度（也不需要因为长度就是__builtin_popcount(mask)，而是mask的所有合法子集中最长的那个
这是如何处理出来的呢？先遍历 n，每个 i往后枚举找最长子串，最多枚举18位，此时f【mask】若有值则代表存在此合法子串
然后遍历mask，对于每个mask枚举其 1位，1变为0即nmask，即mask的一个子集，f【mask】再与f【nmask】取max，因为nmask此时已表示其所有合法子集，所以mask只需枚举去掉单个1，就能完成和所有子集取max
然后再枚举mask，对 f【mask】+ f【mask^tot】取max
代码如下：
const int N=1e6+10,M=1e4+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
int a[N];
int f[N];
void solve(){
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i],a[i]--;
for(int i=1;i<=n;i++){
int mask=0;
for(int j=0;j<18 && i+j<=n;j++){
if(mask&1<<a[i+j]) break;
mask|=1<<a[i+j];
f[mask]=j+1;
}
}
int tot=(1<<18)-1;
for(int mask=0;mask<=tot;mask++){
for(int j=0;j<18;j++) if(mask&1<<j){
int nmask=mask^(1<<j);
f[mask]=max(f[nmask],f[mask]); //mask的最大合法子集
}
}
int ans=0;
for(int mask=0;mask<=tot;mask++) ans=max(f[mask]+f[mask^tot],ans);
cout << ans;
}补 K cf传送门
思路：超级源点+分层图
对于超级源点到第一层的每个点建立边权为 ai的边，即可把点权转化为边权处理，然后对于法宝只需建第二层图，建图后跑常规dij即可
取ans时需注意，第二层的点 dis【i+n】只有可能是从非 i点到达i点渡劫的权值，所以缺少了一种可能即在 i点直接渡劫，所以也要考虑第一层点的答案
代码如下：
const int N=2e6+10,M=1e4+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
vector<PII>ve[N];
ll dis[N];
bool vi[N];
void dij(){
for(int i=1;i<=n*2;i++) dis[i]=1e18;
priority_queue<PII,vector<PII>,greater<>>pq;
pq.push({0,0});
while(!pq.empty()){
auto [d,u]=pq.top(); pq.pop();
if(vi[u]) continue;
vi[u]=1;
for(auto [w,v]:ve[u]) if(dis[v]>d+w){
dis[v]=d+w;
pq.push({dis[v],v});
}
}
}
void solve(){
ll m; cin >> n >> m;
for(int i=1;i<=m;i++){
int u,v,w; cin >> u >> v >> w;
ve[u].push_back({w,v});
ve[v].push_back({w,u});
ve[u+n].push_back({w,v+n});
ve[v+n].push_back({w,u+n});
ve[u].push_back({0,v+n});
ve[v].push_back({0,u+n});
}
for(int i=1;i<=n;i++){
ll a; cin >> a;
ve[0].push_back({a,i});
}
dij();
ll ans=0;
for(int i=n+1;i<=n*2;i++) ans=max(min(dis[i],dis[i-n]),ans);dis取min
cout << ans;
}星期五:
补 cf round983 div2 E 构造 cf传送门
绞尽脑汁差分不如直接上线段树
思路：有意思的构造，通过1 2 1的操作逐步构成其他操作，若对 x+2，x+4...x-1执行1 2 1操作，即等价与对 x和x+1进行 -1操作。若对 x+1，x+3...x-2进行-1 -1操作，即等价于对x进行 +1操作
思路很清新，实现很勾史，最开始想差分试试，结果半天没差分出来，好不容易过了样例 wa6，没办法只能上线段树，虽然线段树的实现也很麻烦但起码很稳定地一发过了
代码如下:
const int N=2e5+10,M=7e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
struct seg_Tree{
#define lc p<<1
#define rc p<<1|1
struct nod{
int l,r;
ll mi1,mi2,op1,op2;
ll tagm1,tagm2,tago1,tago2;
}t[N<<2];
ll ql,qr,q1,qv,qop;
nod merge(nod a,nod b){
nod res;
res.l=a.l,res.r=b.r;
//
res.tagm1=res.tagm2=res.tago1=res.tago2=0;
return res;
}
void pushup(int p){t[p]=merge(t[lc],t[rc]);}
void bd(int p,int l,int r){
t[p]={l,r,0,0,0,0,0,0,0,0};
if(l==r) return ;
int mid=l+r>>1;
bd(lc,l,mid);
bd(rc,mid+1,r);
}
void pushdn(int p){
if(t[p].tagm1){
t[lc].mi1+=t[p].tagm1;
t[rc].mi1+=t[p].tagm1;
t[lc].tagm1+=t[p].tagm1;
t[rc].tagm1+=t[p].tagm1;
t[p].tagm1=0;
}
if(t[p].tagm2){
t[lc].mi2+=t[p].tagm2;
t[rc].mi2+=t[p].tagm2;
t[lc].tagm2+=t[p].tagm2;
t[rc].tagm2+=t[p].tagm2;
t[p].tagm2=0;
}
if(t[p].tago1){
t[lc].op1+=t[p].tago1;
t[rc].op1+=t[p].tago1;
t[lc].tago1+=t[p].tago1;
t[rc].tago1+=t[p].tago1;
t[p].tago1=0;
}
if(t[p].tago2){
t[lc].op2+=t[p].tago2;
t[rc].op2+=t[p].tago2;
t[lc].tago2+=t[p].tago2;
t[rc].tago2+=t[p].tago2;
t[p].tago2=0;
}
}
void update(int p){
if(ql<=t[p].l && qr>=t[p].r){
if(qop==1){
if(q1) t[p].mi1+=qv,t[p].tagm1+=qv;
else t[p].mi2+=qv,t[p].tagm2+=qv;
}else{
if(q1) t[p].op1+=qv,t[p].tago1+=qv;
else t[p].op2+=qv,t[p].tago2+=qv;
}
return ;
}
int mid=t[p].l+t[p].r>>1;
pushdn(p);
if(ql<=mid) update(lc);
if(qr>mid) update(rc);
pushup(p);
}
void updt(int l,int r,int op,int if1,ll v){
ql=l,qr=r;
qop=op,q1=if1;
qv=v;
update(1);
}
nod query(int p){
if(ql<=t[p].l && qr>=t[p].r) return t[p];
int mid=t[p].l+t[p].r>>1;
pushdn(p);
if(ql<=mid) return query(lc);
if(qr>mid) return query(rc);
}
ll ask(int x,int op){
ql=qr=x;
qop=op;
nod res=query(1);
if(op==1) return x&1?res.mi1:res.mi2;
else return x&1?res.op1:res.op2;
}
}tr;
ll a[N];
void solve(){
cin >> n;
tr.bd(1,1,n);
ll ma=0;
for(int i=1;i<=n;i++){
cin >> a[i];
ma=max(a[i],ma);
}
for(int i=1;i<=n;i++) if(a[i]!=ma){
if(i<n) tr.updt(i+1,n,1,!(i&1),ma-a[i]);
if(i>1) tr.updt(1,i-1,1,i&1,ma-a[i]);
}
for(int i=1;i<=n;i++){
ll mi=tr.ask(i,1);
//cout << mi << " \n"[i==n];
if(i<n) tr.updt(i+1,n,2,i&1,mi);
if(i>1) tr.updt(1,i-1,2,!(i&1),mi);
}
for(int i=1;i<=n;i++) cout << tr.ask(i,2) << " \n"[i==n];
//cout << tr.t[8].mi1 << " ";
}星期六：
vp了21年沈阳ICPC，B题常数卡了很久，也算一个经验
晚上cf round985，预测的掉分场，但因为C的dp出的够快，又给+了2分
周日：
补 cf round985 D 构造 cf传送门
又是一道有意思的构造
思路：每次操作对于边的数量有4种结果，+3,-3,+1,-1。考虑先把图拆成森林，让每个连通块的点数小于等于2，最多m次操作，若无边则直接结束，若有边考虑再构造成一颗树，事实上对于此操作和森林的情况下，构造成树很轻松，对于边 u，v，若要合并单点 w，直接进行操作u v w，操作边变为 u w，若合并边 p q，进行操作 v p q，p q即成为了v的子节点，此步骤操作次数也小于n
代码如下：
const int N=2e6+10,M=1e4+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
vector<int>ve[N];
struct nod{
ll a,b,c;
};
vector<nod>ans;
void solve(){
ans.clear();
ll m; cin >> n >> m;
for(int i=1;i<=n;i++) ve[i].clear();
for(int i=1;i<=m;i++){
int u,v; cin >> u >> v;
ve[u].push_back(v);
ve[v].push_back(u);
}
for(int i=1;i<=n;i++) sort(ve[i].begin(),ve[i].end());
for(int i=1;i<=n;i++) if(ve[i].size()>1){
sort(ve[i].begin(),ve[i].end());//
while(ve[i].size()>1){
int u=ve[i].back(); ve[i].pop_back();
int v=ve[i].back(); ve[i].pop_back();
ans.push_back({i,u,v});
sort(ve[u].begin(),ve[u].end());
sort(ve[v].begin(),ve[v].end());
ve[u].erase(find(ve[u].begin(),ve[u].end(),i));
ve[v].erase(find(ve[v].begin(),ve[v].end(),i));
if(find(ve[u].begin(),ve[u].end(),v)==ve[u].end()){
ve[u].push_back(v);
ve[v].push_back(u);
}else{
ve[u].erase(find(ve[u].begin(),ve[u].end(),v));
ve[v].erase(find(ve[v].begin(),ve[v].end(),u));
}
}
}
int u=0,v=0;
for(int i=1;i<=n;i++) if(!ve[i].empty()){
u=i,v=ve[i].back();
break;
}
map<int,bool>vi;
//cout << u << " " << v << "\n";
vi[v]=vi[u]=1;
if(u){
for(int i=1;i<=n;i++) if(!vi.count(i)){
//cout << i << "\n";
if(ve[i].empty()){
ans.push_back({i,u,v});
v=i;
}else{
int b=ve[i].back(); ve[i].pop_back();
ve[b].pop_back();
ans.push_back({v,i,b});
vi[b]=1;
}
}
}
cout << ans.size() << "\n";
for(auto i:ans) cout << i.a << " " << i.b << " " << i.c << "\n";
}原文地址：https://blog.csdn.net/breath_of_yuan/article/details/143484604
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！