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取mincout << 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|1struct 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";
}