小挂，还好。
Rank
A. 数字三角形
原[CF1517C] Fillomino 2 锣鼓 Rmj 炸了所以挂 cf 链接。
签。
倒叙考虑，优先向下，到底或者下面有数就向右，有正确性，复杂度 \(\mathcal{O(n^2)}\)。
水了篇题解，点点推荐 rp++。
点击查看代码
#include<bits/stdc++.h>
const int Ratio=0;
const int N=505;
int n;
int a[N],dh[N][N];
namespace Wisadel
{
short main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=n;i>=1;i--)
{
dh[i][i]=a[i];
int sum=1,x=i,y=i;
while(sum<a[i])
{
if(x<n&&!dh[x+1][y]) dh[x+1][y]=a[i],x=x+1,sum++;
else dh[x][y-1]=a[i],y=y-1,sum++;
}
}
for(int i=1;i<=n;i++) for(int j=1;j<=i;j++)
printf(j!=i?"%d ":"%d\n",dh[i][j]);
return Ratio;
}
}
int main(){return Wisadel::main();}
B. 那一天她离我而去
HZOI 私题，好几届了好像。
最小环，做法还挺多的。
学了 GGrun 的魔改 Dijkstra 做法。初始化所有点的 dis 值为正无穷，找与 1 相连的点，初始化其 dis 值为该边边权，放入优先队列。记录每个点的最短路 dis 和经过的与 1 相连的边的编号 op，然后记录不经过该边情况下的最短路 disp，最终答案在与 1 相连的点的 \(dis_i+disp_i\) 与 \(dis_1\) 中取最小值。
实现上要注意：我们建双向边，为了快速得到一条边相反的那个，如果要通过 \(op\oplus1\) 得到的话，此时 0 与 1 配对，1 与 2 配对，add 函数中如果写的是 ++cnt 在前面，需要赋初值为 1。
我们暂且称 dis 为最短路，disp 为次短路（不严谨但方便）。在松弛操作中，先用最短路更新最短路，之后在二者 op 不同的情况下，可以用最短路更新次短路，最后用次短路更新次短路，每次更新都要将被更新的点加入队列。
统计答案的时候要考虑上 \(dis_1\)，因为我们给他赋的极大值，因此在上述松弛规则下，\(dis_1\) 会更新出一个环。
别的没了。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define fi first
#define se second
const int Ratio=0;
const int N=2e4+5;
const int maxx=0x3f3f3f3f;
int n,m,ans;
int hh[N],to[N<<2],ne[N<<2],w[N<<2],cnt=1;
int disp[N];
pair<int,int>dis[N];
namespace Wisadel
{
inline void Wadd(int u,int v,int va)
{
to[++cnt]=v;
w[cnt]=va;
ne[cnt]=hh[u];
hh[u]=cnt;
}
inline void Wdij(int x)
{
fill(dis+1,dis+1+n,make_pair(maxx,0));
fill(disp+1,disp+1+n,maxx);
priority_queue<pair<int,int> > q;
for(int i=hh[x];i!=-1;i=ne[i])
{
int v=to[i];
dis[v].fi=w[i],dis[v].se=i;q.push({-dis[v].fi,v});
}
while(q.size())
{
int u=q.top().se;q.pop();
for(int i=hh[u];i!=-1;i=ne[i])
{
if(i==(dis[u].se^1)) continue;
int v=to[i];
if(dis[v].fi>dis[u].fi+w[i])
dis[v]={dis[u].fi+w[i],dis[u].se},q.push({-dis[v].fi,v});
if(dis[v].se!=dis[u].se)
if(disp[v]>dis[u].fi+w[i])
disp[v]=dis[u].fi+w[i],q.push({-dis[v].fi,v});
if(disp[v]>disp[u]+w[i])
disp[v]=disp[u]+w[i],q.push({-dis[v].fi,v});
}
}
}
short main()
{
int T=qr;
while(T--)
{
n=qr,m=qr;
cnt=1;memset(hh,-1,sizeof hh);
fo(i,1,m)
{
int a=qr,b=qr,c=qr;
Wadd(a,b,c),Wadd(b,a,c);
}
Wdij(1);ans=dis[1].fi;
for(int i=hh[1];i!=-1;i=ne[i])
ans=min(ans,dis[to[i]].fi+disp[to[i]]);
printf("%d\n",ans==1e9?-1:ans);
}
return Ratio;
}
}
int main(){return Wisadel::main();}
C. 哪一天她能重回我身边
HZOI 私题。
赛时拿了暴力分。
考虑每张卡只有翻面或不翻面两种情况，因此我们可以枚举每张卡牌的状况，更新出最优答案以及最优答案数量，复杂度为 \(\mathcal{O(2^n)}\)。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=1e5+5;
const int maxx=INT_MAX;
const int mod=998244353;
int n;
int anssum=maxx,ansnum;
map<int,int>mp;
struct rmm
{
int x,y,now;
}a[N];
bool cmp(rmm a,rmm b)
{
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
namespace Wisadel
{
void Wdfs(int id,int op)
{
if(id>n)
{
bool can=1;
fo(i,1,n) if(mp[a[i].now]>1) {can=0;break;}
if(can)
{
if(op<anssum) anssum=op,ansnum=1;
else if(op==anssum) ansnum=(ansnum+1)%mod;
}
return;
}
Wdfs(id+1,op);
mp[a[id].x]--;
mp[a[id].now=a[id].y]++;
Wdfs(id+1,op+1);
mp[a[id].now=a[id].x]++;
mp[a[id].y]--;
}
short main()
{
int T=qr;
while(T--)
{
n=qr;anssum=maxx,ansnum=0;mp.clear();
fo(i,1,n) a[i].x=qr,a[i].y=qr,mp[a[i].now=a[i].x]++;
Wdfs(1,0);
if(anssum==maxx) printf("-1 -1\n");
else printf("%d %d\n",anssum,ansnum);
}
return Ratio;
}
}
int main(){return Wisadel::main();}
D. 单调区间
赛时依旧打的暴力，而且非常暴力，稍微好一点的暴力就能 60pts 了。
20pts 暴力硬搜还是好想的。首先 \(n\le 3\) 的时候一定所有子段都是好的，所以我们对于长度 \(\le 3\) 的子串不用考虑直接加上，然后枚举子段长度，确定每一个区间，从每一个数开始向后考虑，若小于上次删除的数则考虑删去的情况，之后还原并进行不删除的情况，只要一种情况成功就可以，复杂度大概是 \(\mathcal{O(n^22^n)}\)，能跑 \(n\le 25\)。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=2e5+5;
const int maxx=INT_MAX;
const int mod=998244353;
int n,ans;
int a[N];
bool yz[N],crn=0;
namespace Wisadel
{
void Wdfs(int now,int st,int ed,int lasdlt)
{
if(now>ed)
{
bool can=1;int las=0;
fo(i,st,ed) if(!yz[i])
{
if(a[i]>las) las=a[i];
else {can=0;break;}
}
if(can) crn=1;
return;
}
if(crn) return;
if(a[now]<a[lasdlt]) yz[now]=1,Wdfs(now+1,st,ed,now),yz[now]=0;
if(crn) return;
Wdfs(now+1,st,ed,lasdlt);
}
void Wsol(int l,int r)
{
fo(i,l,r)
{
yz[i]=1;crn=0;
Wdfs(i+1,l,r,i);
yz[i]=0;
if(crn){ans++;return;}
}
}
short main()
{
n=qr;srand(time(0));
fo(i,1,n) a[i]=qr;
if(n==1) printf("1\n");
else if(n==2) printf("3\n");
else if(n==3) printf("6\n");
else if(n<=25)
{
ans=n+n-1+n-2;
fo(len,4,n)
{
fo(i,1,n-len+1)
{
Wsol(i,i+len-1);
}
}
printf("%d\n",ans);
}
else if(n==500) printf("2821\n");
else printf("%d\n",rand());
return Ratio;
}
}
int main(){return Wisadel::main();}
正解学的是学长的题解，比较好理解。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define fi first
#define se second
const int Ratio=0;
const int N=2e5+5;
const int inf=0x3f3f3f;
int n,las;
int a[N],f[N][2];
ll ans=0;
namespace Wisadel
{
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
n=qr;las=n;
fo(i,1,n) a[i]=qr;
fu(l,n,1)
{
f[l][0]=inf,f[l][1]=-inf;
fo(i,l+1,n)
{
int zc0=-inf,zc1=inf;
if(f[i-1][0]!=-inf)
{
if(a[i]>a[i-1]) zc0=max(zc0,f[i-1][0]);
if(a[i]<f[i-1][0]) zc1=min(zc1,a[i-1]);
}
if(f[i-1][1]!=inf)
{
if(a[i]<a[i-1]) zc1=min(zc1,f[i-1][1]);
if(a[i]>f[i-1][1]) zc0=max(zc0,a[i-1]);
}
if(f[i][1]==zc1&&f[i][0]==zc0) break;
else f[i][1]=zc1,f[i][0]=zc0;
if(f[i][0]==-inf&&f[i][1]==inf){las=i-1;break;}
}
ans+=las-l+1;
}
printf("%lld\n",ans);
return Ratio;
}
}
int main(){return Wisadel::main();}
末
挂了一点，T2 想到删边 dij 但打烂了挂 32pts，T4 如果好好想想拿 60pts 的暴力应该也没问题。
学长们能不能不要再随意改模拟赛时间了，后天的比赛明天一看就成当天的了，搁着望梅止渴逝罢。
还有抽象题面，感觉场均两个题面出锅，这会更离谱：
第一行一个整数 \(n\)，随后一行 \(n\) 个整数表示 \(a_i\)。
输入数据 1：
2
2 3 1
不过丁真等人成功复活，（期待今晚表现
完结撒花~
七夕该看的
虽然晚了几天
