day 6
A. Thoughtful Dreams
难度：红
输出 \(1\sim n\) 即可。
#include<bits/stdc++.h>
#define ll long long
#define mxn 200010
using namespace std;
ll n;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cout<<i<<' ';
return 0;
}
B. Azurite Ascent
难度：红
我真唐，真的。
判断相邻两个数之间是否互质即可。
#include<bits/stdc++.h>
#define mxn 200010
#define ll long long
using namespace std;
ll n,a[mxn];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
a[0]=a[n];
for(int i=1;i<=n;i++){
if(__gcd(a[i],a[i-1])!=1){
cout<<"No";
exit(0);
}
}
cout<<"Yes";
return 0;
}
C. Ancient Engine
难度：蓝
恶心图论大模拟。
若有环且有路径长度不为 \(0\)，则时间和路径数都为 \(inf\)。
若无环则为DAG，跑一遍拓扑排序找出最长路，然后对于每一段路径取最大值，数量就在拓扑排序时算出。
#include<bits/stdc++.h>
#define ll long long
#define mxn 200010
#define mxm 2000010
#define mod 998244353
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int n,m,pd=1,ans,du1[mxn],du2[mxn];
int judge[mxn],vis[mxn];
int cnt[mxn],road[mxn];
int layer[mxn],lcnt,tmp[mxn],tcnt;
vector<pii> t1[mxn],t2[mxn];
queue<int> q1,q2;
void dfs(int u){
if(vis[u]==2){cout<<"inf\ninf";exit(0);}
if(vis[u])return;
vis[u]=2;
for(int i=0;i<t1[u].size();i++){
int v=t1[u][i].fi;
dfs(v);
}
vis[u]=1;
return;
}
void add(int &x,int y){
if(x<0||y<0){x=-1;return;}
else{x=(x+y)%mod;return;}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
t1[v].pb(mp(u,w));
t2[u].pb(mp(v,w));
du1[u]++,du2[v]++;
pd&=(!w);
judge[u]|=w;
}
for(int i=1;i<=n;i++)if(judge[i])dfs(i);
for(int i=1;i<=n;i++)if(du1[i]==0)q1.push(i);
for(int i=1;i<=n;i++)if(du2[i]==0)q2.push(i);
while(q1.size()){
int u=q1.front();
q1.pop();
add(cnt[u],1);
for(int i=0;i<t1[u].size();i++){
int v=t1[u][i].fi;
if(vis[v])continue;
cnt[v]=(cnt[u]+cnt[v])%mod;
du1[v]--;
if(du1[v]==0)q1.push(v);
}
}
for(int i=1;i<=n;i++)
if(!cnt[i]&&!vis[i])
cnt[i]=-1;
if(pd){
ans=0;
for(int i=1;i<=n;i++)
add(ans,cnt[i]);
cout<<"0\n";
if(ans<0)cout<<"inf";
else cout<<ans;
return 0;
}
for(int i=1;i<=n;i++)road[i]=1;
while(q2.size()){
int u=q2.front();
q2.pop();
if(vis[u]==0)continue;
for(int i=0;i<t2[u].size();i++){
int v=t2[u][i].fi;
road[v]=max(road[v],road[u]+(vis[u]|vis[v]));
du2[v]--;
if(du2[v]==0)q2.push(v);
}
}
for(int i=1;i<=n;i++){
judge[i]=0;
ans=max(ans,road[i]);
}
for(int i=1;i<=n;i++)
if(road[i]==ans)
layer[++lcnt]=i;
while(road[layer[1]]!=1){
for(int i=1;i<=lcnt;i++)tmp[i]=layer[i];
tcnt=lcnt;
ans=0,lcnt=0;
for(int i=1;i<=tcnt;i++){
int u=tmp[i];
for(int j=0;j<t1[u].size();j++){
int v=t1[u][j].fi;
if(road[v]!=road[u]-1)continue;
ans=max(ans,t1[u][j].se);
}
}
cout<<ans;
for(int i=1;i<=tcnt;i++){
int u=tmp[i];
for(int j=0;j<t1[u].size();j++){
int v=t1[u][j].fi;
if(road[v]!=road[u]-1)continue;
if(t1[u][j].se==ans){
add(cnt[v],cnt[u]);
if(judge[v]==0)
layer[++lcnt]=v;
judge[v]=1;
}
}
}
}
cout<<'\n';
ans=0;
for(int i=1;i<=lcnt;i++)
ans=(ans+cnt[layer[i]])%mod;
if(ans<0)cout<<"inf";
else cout<<ans;
return 0;
}
D. Above Celeste's Peak
难度：蓝-紫
恶心的矩阵优化dp。
求本质不同子序列？这里的dp我在之前的模拟赛中写过。
这里转化成矩阵乘法，时间复杂度 \(O((n+q)m^3)\)，会TLE。
笔者止步于此，\(O((n+q)m)\) 的做法尚未搞懂（以后也可能没时间再想了），先把官方std留下吧。
#include<bits/stdc++.h>
#define mxn 210000
#define ll long long
#define P 998244353
using namespace std;
int a[mxn][210],b[mxn][210],c[mxn][210];
int d[210],n,m,t,x[mxn],h,f,g,ans,l,r;
vector<int>p[210],q[210];
int add(int x,int y){
return x+y<P?x+y:x+y-P;
}
int mus(int x,int y){
return x-y<0?x-y+P:x-y;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m>>t;
m++;
for(int i=1;i<=n;i++)cin>>x[i];
for(int i=1;i<=m;i++){
a[i][i]=b[i][i]=d[i]=1;
p[i].push_back(i);
q[i].push_back(i);
}
for(int i=1;i<=n;i++){
int k=p[x[i]].back(),l=i+m;
for(int j=1;j<=m;j++){
a[l][j]=d[j];
d[j]=mus(add(d[j],d[j]),a[k][j]);
}
p[x[i]].push_back(l);
}
for(int i=n;i;i--){
int k=q[x[i]].back(),l=n+m+1-i;
for(int j=1;j<=m;j++){
b[l][j]=mus(0,c[i+1][j]);
c[i][j]=add(add(c[i+1][j],c[i+1][j]),b[k][j]);
}
q[x[i]].push_back(l);
}
while(t--){
cin>>h>>f>>g;
ans=0;
l=*(--upper_bound(q[f].begin(),q[f].end(),n+m-h));
r=*(--upper_bound(p[g].begin(),p[g].end(),h+m-1));
for(int j=1;j<=m;j++)
ans=(ans+(b[l][j]+2ll*c[h+1][j]+(j==m))*a[r][j])%P;
cout<<ans<<'\n';
}
return 0;
}