质量不错，难度不高的良心场。
CF360A Levko and Array Recovery
注意到 (n,m) 很小，可以先求出每刻每个点的加值。
然后通过区间最值可以得到原最值。
于是构成了一个满足 (le) 最值的原序列，带回去验证是否存在最值即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define bg begin()
#define ed end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define R(i,n) for(int i(0);i<(n);++i)
#define L(i,n) for(int i((n)-1);i>=0;--i)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
//Data
const int N=5e3;
int n,m,a[N],c[N],b[N][4],d[N];
//Main
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
R(i,n) a[i]=int(1e9);
R(i,m){
R(t,4) cin>>b[i][t];
--b[i][0],--b[i][1];
}
R(i,m){
if(b[i][0]) for(int j=b[i][1];j<b[i][2];++j) a[j]=min(a[j],b[i][3]-d[j]);
else for(int j=b[i][1];j<b[i][2];++j) d[j]+=b[i][3];
}
R(i,n) c[i]=a[i];
R(i,m){
if(b[i][0]){
int mx=-iinf;
for(int j=b[i][1];j<b[i][2];++j) mx=max(mx,c[j]);
if(mx!=b[i][3]) return !(cout<<"NO
");
} else for(int j=b[i][1];j<b[i][2];++j) c[j]+=b[i][3];
}
cout<<"YES
";
R(i,n) cout<<a[i]<<' ';
cout<<'
';
return 0;
}
CF360B Levko and Array
相当于要留下 (n-m) 个，先二分答案 (x)，然后 dp：
-
设 (f(i)) 表示以选 (a_i) 结尾最多选几个。
-
[f(i)=max_{j<i,x(i-j)ge |a_i-a_j|}{f(j)+1} ]
然后看看存不存在 (f(i)ge n-m) 即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define bg begin()
#define ed end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define R(i,n) for(int i(0);i<(n);++i)
#define L(i,n) for(int i((n)-1);i>=0;--i)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
//Data
const int N=2000;
int n,m,a[N],f[N];
//Function
bool check(ll mid){
// cout<<"mid="<<mid<<'
';
R(i,n) f[i]=1;
R(i,n)R(j,i)if(mid*(i-j)>=abs(a[i]-a[j]))
f[i]=max(f[i],f[j]+1);
// R(i,n) cout<<f[i]<<' '; cout<<'
';
R(i,n)if(f[i]>=m) return true;
// cout<<"false
";
return false;
}
//Main
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m,m=n-m;
R(i,n) cin>>a[i];
ll l=-1,r=2e9+1;
while(r-l>1){
ll mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid;
}
cout<<r<<'
';
return 0;
}
CF360C Levko and Strings
挺巧妙 (+) 玄学的计数题。
在每个 (t) 的子串中第一个 (>s) 的地方统计它的贡献。
设 (f(i,x)) 表示到第 (i) 个字母， 有 (x) 个子串的方案数。
- 如果 (t_i>s_i)，枚举 (j<i)，表示 ([j+1,i)) 这段 (t_i=s_i)：
-
[f(i,x)leftarrow (25-s_i)f(j,x-(n-i+1)(i-j-1)) ]
- 这段可以暴力枚举，最终复杂度 (Theta(n^2log n))。
-
- 如果 (t_i<s_i)，同样枚举 (j<i)：
-
[f(i,x)leftarrow s_icdot f(j,x) ]
- 这段可以前缀和。
-
然后答案就是 (sum_{i=0}^n f(i,k))。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define bg begin()
#define ed end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define R(i,n) for(int i(0);i<(n);++i)
#define L(i,n) for(int i((n)-1);i>=0;--i)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
//Data
const int N=2e3+1,mod=1e9+7;
int n,m,f[N][N],sm[N|1][N];
string s;
//Math
int& mod_s(int &x){return x<mod?x:x-=mod;}
int& mod_p(int &x){return x<0?x+=mod:x;}
//Main
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m>>s,**f=1;
R(j,m+1) mod_s(sm[1][j]=sm[0][j]+f[0][j]);
R(i,n){
L(t,i+1)R(j,m+1-(i+1-t)*(n-i)){
f[i+1][j+(i+1-t)*(n-i)]=(1ll*(25-
(s[i]-'a'))*f[t][j]+f[i+1][j+(i+1-t)*(n-i)])%mod;
}
R(j,m+1) f[i+1][j]=(1ll*sm[i+1][j]*(s[i]-'a')+f[i+1][j])%mod;
R(j,m+1) mod_s(sm[i+2][j]=sm[i+1][j]+f[i+1][j]);
}
// R(i,n+1)R(j,m+1) cout<<f[i][j]<<"
"[j==m];
int ns=0;
R(i,n+1) mod_s(ns+=f[i][m]);
cout<<ns<<'
';
return 0;
}
CF360D Levko and Sets
CF360E Levko and Game
可以先把所有边 (i) 权设为 (r_i)，发现把 (r_i) 改为 (l_i)，总是因为 (s_1) 到 (a_i) 比 (s_2) 到 (a_i) 更近，目的是使最短路必经 (a_i)。
所以可以跑最多 (k) 次 dijkstra：每次找到还没被降权且 (s_1) 到 (a_i) 比 (s_2) 到 (a_i) 更近的边降权，如果 (s_1) 到 (t) 比 (s_2) 到 (t) 更近或者一轮中没有降权过，就 break。
最后直接比较 (s_1) 到 (t) 和 (s_2) 到 (t) 的距离即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define bg begin()
#define ed end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define R(i,n) for(int i(0);i<(n);++i)
#define L(i,n) for(int i((n)-1);i>=0;--i)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
//Data
const int N=1e4,me_N=100;
int n,ce_n,me_n,a,b,t,me[me_N][5];
bool low[me_N];
//Graph
vector<int> adj[N],to,we;
int adde(int u,int v,int w){
int e_i=sz(to);
adj[u].pb(e_i),to.pb(v),we.pb(w);
return e_i;
}
ll a_dis[N],b_dis[N]; bool vis[N];
priority_queue<pair<ll,int>> q;
void dijkstra(int s,ll* dis){
R(u,n) dis[u]=linf,vis[u]=false;
q.push(mp(-(dis[s]=0),s));
while(sz(q)){
int u=q.top().y; q.pop();
if(vis[u]) continue; vis[u]=true;
for(int i:adj[u])if(dis[to[i]]>dis[u]+we[i])
q.push(mp(-(dis[to[i]]=dis[u]+we[i]),to[i]));
}
}
//Main
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>ce_n>>me_n>>a>>b>>t,--a,--b,--t;
R(i,ce_n){
int u,v,w;
cin>>u>>v>>w,--u,--v;
adde(u,v,w);
}
R(i,me_n){
R(t,4) cin>>me[i][t];
R(t,2) --me[i][t];
me[i][4]=adde(me[i][0],me[i][1],me[i][3]);
}
while(true){
dijkstra(a,a_dis),dijkstra(b,b_dis);
if(a_dis[t]<b_dis[t]) break;
int move=0;
R(i,me_n)if(!low[i]&&a_dis[me[i][0]]<b_dis[me[i][0]])
++move,low[i]=true,we[me[i][4]]=me[i][2];
if(!move) break;
}
if(a_dis[t]<=b_dis[t]){
cout<<(a_dis[t]==b_dis[t]?"DRAW
":"WIN
");
R(i,me_n) cout<<(low[i]?me[i][2]:me[i][3])<<' ';
cout<<'
';
} else cout<<"LOSE
";
return 0;
}