CF1340A Nastya and Strange Generator
如题目所定义地，我们设(r_j)表示(geq j)的位置中，第一个没有被占用的位置。特别地，我们认为位置(n+1)永远不被占用。即：如果([j,n])都已经被占用了，那么(r_j=n+1)。
题目还定义了，( ext{count}_t)表示有多少个(j)的(r_j=t)。要求我们从小到大，每次填的位置必须是( ext{count})值最大的位置。
如果(r_j>j)，我们就从(j)向(r_j)连一条边，则该图成为一个森林。( ext{count}_t)，就是森林里以(t)为根的这棵树的大小。当我们在(p)位置填入一个数后，原本(r_j=p)的，就会变为(r_jleftarrow r_{p+1})。这就相当于把森林里的一整棵树，挂到另一棵树的某个节点下。
可以用并查集维护这个森林。用一个( exttt{multiset})维护森林里所有树的大小。从小到大考虑所有数字，设当前数字要被放在位置(p)，我们直接看以(p)为根的树，大小是否是( exttt{multiset})里的最大值即可。
时间复杂度(O(nlog n))。
参考代码：
//problem:A
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int MAXN=1e5;
int n,a[MAXN+5],pos[MAXN+5],fa[MAXN+5],sz[MAXN+5];
int get_fa(int x){
return (x==fa[x])?x:(fa[x]=get_fa(fa[x]));
}
multiset<int>s;
void union_s(int x,int y){
x=get_fa(x);
y=get_fa(y);
if(x!=y){
fa[x]=y;
s.erase(s.find(sz[x]));
if(y!=n+1)s.erase(s.find(sz[y]));
sz[y]+=sz[x];
if(y!=n+1)s.insert(sz[y]);
}
}
int main() {
int T;cin>>T;while(T--){
cin>>n;
s.clear();
for(int i=1;i<=n;++i)cin>>a[i],pos[a[i]]=i;
for(int i=1;i<=n+1;++i){
fa[i]=i;
if(i<=n)sz[i]=1,s.insert(1);
}
bool fail=false;
for(int i=1;i<=n;++i){
int u=pos[i];
assert(get_fa(u)==u);
if(sz[u]!=*s.rbegin()){
fail=true;
break;
}
union_s(pos[i],pos[i]+1);
}
if(fail)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
CF1340B Nastya and Scoreboard
可以预处理一个数组，( ext{dis}[i][j])，其中(0leq i<2^7)，(0leq jleq9)，表示数字屏的一个数位，从(i)这种状态，变成(j)这个数字，需要点亮多少灯管。特别地，如果对于某个灯管，在(i)中是(1)而在(j)所在的状态中是(0)，即：从(i)变成(j)需要熄灭某个灯管，则(i)永远不可能变成(j)，此时令( ext{dis}[i][j]=inf)。
我们先判断可行性。做一个DP：设(dp[i][j])为一个( exttt{bool})型变量，表示考虑了数字屏的后(i)位数字（为什么要从后往前DP，下面会讲），已经点亮了(j)根灯管，是否存在这样的方案。转移是比较简单的，枚举把第(i)位改成数字(k) ((0leq kleq9))，则(dp[i][j+ ext{dis}[a_i][k]] exttt{|=}dp[i+1][j])。容易发现，问题有解当且仅当(dp[1][K]= exttt{true})。
确定有解后，我们从前向后，依次构造出每一位。维护一个变量( ext{used})，表示已经使用了多少灯管。我们贪心地从(9)到(0)考虑当前位变成几。当前位，能变成数字(k) ((0leq kleq 9))，当且仅当(dp[i+1][K-( ext{used}+ ext{dis}[a_i][k])]= exttt{true})。确定了当前位能变成哪个数字后，令( ext{used} exttt{+=}k)即可。
现在，大家就很容易明白我们为什么要从后往前DP。因为在构造答案时，是贪心地从左向右构造。所以会需要判断后若干位，还剩若干次操作时的可行性。
时间复杂度(O(n^2cdot 10+ncdot 10))。
参考代码：
//problem:B
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int MAXN=2000,INF=1e9;
const string s[10]={"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
int n,K,dis[1<<7][10],b[MAXN+5],ans[MAXN+5];
bool dp[MAXN+5][MAXN+5];
string a[MAXN+5];
int main() {
for(int i=0;i<(1<<7);++i){
for(int j=0;j<10;++j){
bool fail=false;
for(int k=0;k<7;++k)if(((i>>k)&1)&&s[j][k]=='0'){fail=true;break;}
if(fail){
dis[i][j]=INF;
continue;
}
for(int k=0;k<7;++k)if(!((i>>k)&1)&&s[j][k]=='1')dis[i][j]++;
}
}
cin>>n>>K;
for(int i=1;i<=n;++i){
cin>>a[i];
for(int j=0;j<7;++j)if(a[i][j]=='1')b[i]|=(1<<j);
}
dp[n+1][0]=1;
for(int i=n;i>=1;--i){
for(int j=0;j<=K;++j)if(dp[i+1][j]){
for(int k=0;k<10;++k){
if(dis[b[i]][k]==INF)continue;
if(j+dis[b[i]][k]<=K)dp[i][j+dis[b[i]][k]]=1;
}
}
}
if(!dp[1][K]){
cout<<-1<<endl;return 0;
}
int used=0;
for(int i=1;i<=n;++i){
int dig=-1;
for(int j=9;j>=0;--j){
if(dis[b[i]][j]==INF)continue;
if(used+dis[b[i]][j]>K)continue;
//cout<<j<<endl;
if(!dp[i+1][K-(used+dis[b[i]][j])])continue;
dig=j;
break;
}
assert(dig!=-1);
ans[i]=dig;
used+=dis[b[i]][dig];
}
for(int i=1;i<=n;++i)cout<<ans[i];cout<<endl;
return 0;
}
CF1340C Nastya and Unexpected Guest
把一个安全岛，拆成(g)个点。((i,left))表示在到达安全岛(i)时，绿灯时间还剩(left)秒。问题转化为，在这(mcdot gleq 10^7)个点之间，求从(0)到(n)的最短路。
如果(n)不是安全岛没有关系。我们每到达一个状态，就尝试能不能用剩下的时间，从当前安全岛走到(n)。若可以走到，就更新答案。
从每个状态，只需要向相邻的两个安全岛走。因为走到更远的安全岛必然会经过相邻的。
在这张图上做bfs。求出答案。
emmm...我写着写着就写成了spfa。考场上AC了，但复杂度我也不会证明（如果有会证明的神仙请教教我！）。不过卡掉spfa的一般是网格图。spfa在这种近似一维的线段上应该还是相当优秀的。
update：看了官方题解。我们把每((g+r))秒视为一个时间单位，则两个节点之间转移的边权要么是(0)，要么是(1)。所以做01 bfs即可。时间复杂度严格的(O(n+m))。
所谓01 bfs，就是这种边权只有(0), (1)的图上求最短路的方法。具体做法是维护一个双端队列，如果边权为(0)，就把新节点( exttt{push_front})，否则就( exttt{push_back})。这样，相当于在线性的时间里，实现了dijkstra的效果。
参考代码（spfa写法）：
//problem:
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int MAXN=1e6,MAXM=1e4,MAXG=1000;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,d[MAXM+5],G,R,dis[MAXM+5][MAXG+5];
bool inq[MAXM+5][MAXG+5];
int main() {
cin>>n>>m;
for(int i=1;i<=m;++i)cin>>d[i];
cin>>G>>R;
sort(d+1,d+m+1);
memset(dis,0x3f,sizeof(dis));
queue<pii>q;
if(d[1]!=0){
if(d[1]>G){
cout<<-1<<endl;return 0;
}
if(G-d[1]==0){
dis[1][G]=G+R;
q.push(mk(1,G));
}
else{
dis[1][G-d[1]]=d[1];
q.push(mk(1,G-d[1]));
}
}
else{
dis[1][G]=0;
q.push(mk(1,G));
}
ll ans=INF;
while(!q.empty()){
int u=q.front().fi;
int le=q.front().se;
q.pop();
//cout<<u<<" "<<le<<endl;
inq[u][le]=0;
ll D=dis[u][le];
if(n-d[u]<=le){
ans=min(ans,D+n-d[u]);
//return 0;
}
if(u!=1 && d[u]-d[u-1]<=le){
if(d[u]-d[u-1]==le){
ll nd=D+le+R;
if(nd<dis[u-1][G]){
dis[u-1][G]=nd;
if(!inq[u-1][G]){
inq[u-1][G]=1;
q.push(mk(u-1,G));
}
}
}
else{
ll nd=D+d[u]-d[u-1];
if(nd<dis[u-1][le-(d[u]-d[u-1])]){
dis[u-1][le-(d[u]-d[u-1])]=nd;
if(!inq[u-1][le-(d[u]-d[u-1])]){
inq[u-1][le-(d[u]-d[u-1])]=1;
q.push(mk(u-1,le-(d[u]-d[u-1])));
}
}
}
}
if(u!=m && d[u+1]-d[u]<=le){
if(d[u+1]-d[u]==le){
ll nd=D+le+R;
if(nd<dis[u+1][G]){
dis[u+1][G]=nd;
if(!inq[u+1][G]){
inq[u+1][G]=1;
q.push(mk(u+1,G));
}
}
}
else{
ll nd=D+d[u+1]-d[u];
if(nd<dis[u+1][le-(d[u+1]-d[u])]){
dis[u+1][le-(d[u+1]-d[u])]=nd;
if(!inq[u+1][le-(d[u+1]-d[u])]){
inq[u+1][le-(d[u+1]-d[u])]=1;
q.push(mk(u+1,le-(d[u+1]-d[u])));
}
}
}
}
}
if(ans==INF)cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}