T1 JOI 2022 Final T3「選挙で勝とう / Let's Win the Election」
赛时对着一个假贪心不知道为什么是错的。
贪心就是枚举选几个协作州，然后贪心把小的都拿了，剩下的支持州挑小的。
可能会出现某个协作州的 \(b\) 小，但是 \(a\) 更小，导致将他与某个支持州交换反而更优。
于是需要dp，考虑我们要选出 \(p\) 个支持州，设 \(f_{i,j}\) 表示在前 \(i\) 个州里，选出 \(j\) 个协作州的最小时间，我们发现前 \(i\) 个州是不可能不选的，要么是协作州，要么是支持州。因为如果有一个州没选，那么我把其后选的一个协作州换成它显然更优。于是还是枚举协作州的数量，然后做一次dp，统计答案时枚举最后一个协作州是谁，然后从它之后的州里贪心的选 \(a\) 小的即可。
点击查看代码
#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i)
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;
const int maxn=5e2+10,INF=1e9;
const double eps=1e-4;
int n,K,mx;
struct Ver{double a,b;}E[maxn];
bool cmp1(const Ver &x,const Ver &y){return x.b<y.b;}
bool cmp2(const Ver &x,const Ver &y){return x.a<y.a;}
double pre[maxn];
double f[maxn][maxn];
double ans=INF;
multiset<double>S,rec;
void Get(int Te){
Rep(i,0,n)Rep(j,0,n)f[i][j]=INF;
f[0][0]=0;
Rep(i,1,K){
Rep(j,0,min(Te,i)){
f[i][j]=min(f[i][j],f[i-1][j]+E[i].a/(Te+1));
if(j>=1 && abs(E[i].b-INF)>eps)f[i][j]=min(f[i][j],f[i-1][j-1]+E[i].b/j);
}
}
S=rec;
Dwn(i,K,0){
double te=0;
//Rep(j,i+1,K)te+=E[j].a;
auto it = S.begin();
Rep(j,i+1,K)te+=(*it),++it;
ans=min(ans,f[i][Te]+te/(Te+1));
S.insert(E[i].a);
}
}
void solve(){
cin>>n>>K;
Rep(i,1,n){ cin>>E[i].a>>E[i].b; if(E[i].b==-1)E[i].b=INF;else ++mx; }
sort(E+1,E+n+1,cmp1);
Rep(i,K+1,n)rec.insert(E[i].a);
Rep(i,0,min(K-1,mx))Get(i);
cout<<fixed<<setprecision(10)<<ans<<"\n";
}
int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }
T2 JOISC 2017 Day1 T2「港湾設備 / Port Facility」
其实并查集做是很容易想的，即时删点保证连边复杂度也是很容易想的，零分也是很容易拿的
因为即时删点的并查集做法是没有办法把边连全的，所以根本判不了无解，如果题目保证有解的话就比较美妙了。
正解就是不删点，而是维护联通块，然后维护nxt指针指向下一个联通块，连边后就把他们合并起来，然后在图上贪心做染色就能判无解
T3 JOISC 2017 Day3 T2「細長い屋敷 / Long Mansion」
考虑暴力扩展的做法，把当前拥有的钥匙用某种东西维护起来显然是劣的，考虑优化我们判断能不能开一个门的方法。
假设我从 \(x\) 点开始扩展，当前已经扩展到的区间为 \([l,r]\)，如果我们想要扩展到 \(r+1\)，那么 \([l,r]\) 内至少有一个屋子里有 \(c_{r+1}\)，因为我从左向右走，只要离 \(r+1\) 最近的出现了 \(c_{r+1}\) 的位置已经被扩展到即可，于是我们只需要维护一个 \(L_i\) 表示 \(c_i\) 在之前的最近一次出现的位置。向 \(l-1\) 扩展同理。
暴力扩展每一个点是 \(n^2\) 的，考虑优化它。假设我们现在已经扩展完了一个点，正在扩展的另一个点此时扩展到了它，那么这个点所有能到的位置正在扩展的点一定都能到，于是我们可以直接对两者的答案取并集给当前扩展的点。这样进行类似记忆化搜索，每次我要扩展一侧边界时，就从那个边界开始做一次扩展，然后取并集即可，如果已经扩展过了就直接返回跑路。
复杂度 \(O(n)\)，实测比随机化快一点
点击查看代码
#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i)
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;
const int maxn=5e5+10;
int n,q;
int c[maxn];
vector<int>vec[maxn];
int last[maxn];
int L[maxn],R[maxn],p[maxn];
bool vis[maxn];
pii rg[maxn];
void Sol(int x){
bool flag=false;
if(vis[x])return void();
if(rg[x].fir>0)return;
vis[x]=true;
int &l =rg[x].fir,&r=rg[x].sec;
l=x,r=x;flag=true;
while(flag){
flag=false;
if(l>1 && R[l-1]>=l && R[l-1]<=r)
{ Sol(l-1);flag=true; l=min(l,rg[l-1].fir),r=max(r,rg[l-1].sec); }
if(r<n && L[r]<=r && L[r]>=l)
{ Sol(r+1);flag=true; l=min(l,rg[r+1].fir),r=max(r,rg[r+1].sec); }
}
}
void solve(){
cin>>n;int x,y;
for(int i=1;i<n;++i)cin>>c[i];
Rep(i,1,n){
cin>>y; Rep(j,1,y){ cin>>x;vec[i].push_back(x);last[x]=i; }
if(i!=n)L[i]=last[c[i]];
}
Rep(i,1,n)last[i]=n+1;
Dwn(i,n,1){ for(auto it : vec[i])last[it]=i; R[i-1]=last[c[i-1]]; }
Rep(i,1,n)Sol(i);
cin>>q;
while(q--){
cin>>x>>y;
if(rg[x].fir<=y && rg[x].sec>=y)cout<<"YES\n";
else cout<<"NO\n";
}
}
int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }
T4 JOISC 2017 Day3 T1「長距離バス / Long Distance Coach」
发现几个性质
- 每次下车的都是一段后缀
- 如果某个人会下车，那么一定尽早下
- 水的价格是相同的，于是可以每次到服务站时水箱都是空的
- 如果一个人作为被删的后缀的末尾，那么它某次喝水的时间一定与下一个服务站到达的时间相邻(中间没有其他人要喝水)
于是我们可以按照一个 \(T\) 内喝水的时间对乘客排序，逐个考虑其是否下车。设 \(f_i\) 表示前 \(i\) 个人的最小费用
如果不下车
\[f_i=f_{i-1}+W \times (\lfloor \frac{X}{T} \rfloor+ D_i \leq X \bmod T) \]如果下车
\[f_i=\min_{1\leq j < i} f_j+pre_i-pre_j+W \times mt_i \times (i-j) \]\(pre_i\) 为前 \(i\) 个人退费的和，\(mt_i\) 为第 \(i\) 个人最少在喝几次水后下车。\(mt\) 可以把所有服务站出现的时间对周期取模后排序，单指针扫一遍处理。
由于司机一定不能下车，每个点只能从比靠前的转移，转移不会成环。下车的转移是套路的斜率优化。
点击查看代码
#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i)
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
#define int ll
using namespace std;
const int maxn=2e5+10,INF=1e18;
int X,n,m,W,T;
int s[maxn];
struct Per{
int D,C,mini;
bool operator<(const Per &rhs)const{ return D<rhs.D; }
}E[maxn];
int f[maxn];
int pre[maxn];
pii t[maxn];
int q[maxn],top;
#define S(x) (f[x]-pre[x])
int Query(int x){
int l=1,r=top+1;
while(r-l>1){
int mid=(l+r)>>1;
if(x*(q[mid]-q[mid-1])>(S(q[mid])-S(q[mid-1])))l=mid;
else r=mid;
}
return q[l];
}
void solve(){
cin>>X>>n>>m>>W>>T;
Rep(i,1,n)cin>>s[i],t[i]=mair(s[i]%T,s[i]);
t[++n]=mair(X%T,X);
Rep(i,1,m)cin>>E[i].D>>E[i].C,E[i].mini=INF;
sort(E+1,E+m+1);sort(t+1,t+n+1);
E[m+1].D=T;
int p=1;
Rep(i,1,m){
while(p<=n && t[p].fir<E[i].D)++p;
while(p<=n && t[p].fir<E[i+1].D)E[i].mini=min(E[i].mini,t[p++].sec/T);
pre[i]=pre[i-1]+E[i].C;
}
++top;
Rep(i,1,m){
f[i]=f[i-1]+W*((X/T)+(X%T>=E[i].D ? 1 : 0));
if(E[i].mini<INF){ int j=Query(W*E[i].mini); f[i]=min(f[i],f[j]+pre[i]-pre[j]+W*E[i].mini*(i-j)); }
while(top>1 && (S(x)-S(q[top]))*(q[top]-q[top-1])<=(S(q[top])-S(q[top-1]))*(x-q[top]))--top;
q[++top]=x;
}
cout<<f[m]+(X/T+1)*W<<"\n";
}
#undef int
int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }