有点可惜，暴力打满就并列 Rank1 了。
Rank
A. Kanon
签。
考虑到每两个球之间的距离是恒不变的，因此我们可以通过找到每个球控制的边界得到答案，每个区间正好可以得出左边球的右边界和右边球的左边界。
记录每个区间的标号和长度，按长度升序 sort 一遍，然后记录总体位移的状态，记录向右的最远距离和向左的最远距离，二者之和大于等于区间长度时，该区间对应的两个球分别的右左边界就确定了。
每个区间只会遍历到一次，总体的复杂度集中在 sort 上，大概是 \(\mathcal{O(n\log 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=3e5+5;
int n,q;
ll tot,lmin,rmax,a[N],L[N],R[N];
bool yzl[N],yzr[N];
struct rmm
{// qujian
int id;ll dis;
}d[N];
bool cmp(rmm a,rmm b){return a.dis<b.dis;}
namespace Wisadel
{
short main()
{
// freopen("Kanon1.in","r",stdin),freopen(".out","w",stdout);
n=qr,q=qr;
fo(i,1,n)
{
a[i]=qr;
if(i>1) d[i-1].dis=a[i]-a[i-1],d[i-1].id=i-1;
}
sort(d+1,d+n,cmp);
int now=1;
fo(i,1,q)
{
ll w=qr;tot+=w;
if(tot>0) rmax=max(rmax,tot);
else lmin=min(lmin,tot);
while(now<=n-1&&rmax-lmin>=d[now].dis)
{
int xi=d[now].id,xj=xi+1;
if(tot>0) L[xj]=a[xj]+lmin,R[xi]=L[xj];
else R[xi]=a[xi]+rmax,L[xj]=R[xi];
yzl[xj]=1,yzr[xi]=1;now++;
}
}
fo(i,1,n)
{
if(!yzl[i]) L[i]=a[i]+lmin;
if(!yzr[i]) R[i]=a[i]+rmax;
printf("%lld\n",R[i]-L[i]);
}
return Ratio;
}
}
int main(){return Wisadel::main();}
B. Summer Pockets
第一次拿首 A。
感觉有点偏思维，不过推出几个重要性质后还是蛮简单的。
首先记 Y 的总数 \(tot\)，若为奇数一定无解。
已知两个 Y 分一组，那么一共有 \(\frac{tot}{2}\) 组。我们将该矩阵分成若干个矩形，比较显然的是，知道了行被分成了几组，就能知道列被分成了几组。
我们可以枚举它，不过我枚举的是行被分成若干组后，每一组含 Y 的个数 \(hk\)，而我们知道两个 Y 一组，所以就能知道列被分成了 \(\frac{hk}{2}\) 部分，根据矩形面积公式，我们就能得到行应当被分成 \(\frac{tot\times 2}{hk}\) 部分；这里具体枚举那个都是无关紧要的，因为已知其中一个的值就能推导出剩下的值。
注意上面描述的时候用了应当，这是因为以上情况只是我们假设出来的理想情况，若与之不符则应当舍弃；此外，还有一个判断无解的标准，就是我们在按以上情况分出各部分后，需要判断每部分是否正好含两个 Y，具体实现我们可以借助二维前缀和维护。
之后方案若仍合法，则开始计数，此时我们划分部分就较为宽松了，在上面判断的时候，我们划分的标准是该行 / 列有 Y 出现且能将行 / 列分成每部分含对应数量的一组，而计数时只要不影响划分的状态都可以计入，最终利用乘法原理计算出该方案的所有方案数计入答案即可。
由于基础方案数比较少，所以原本 \(\mathcal{O(S)}\) 的时间复杂度降到了很低。
点击查看代码
#include<bits/stdc++.h>
const int Ratio=0;
const int N=2005;
const int mod=998244353;
int n,m,tot;
int sum[N][N],hsum[N],lsum[N],hang[N],lie[N];
int hzc[N],lzc[N],cnth[N],cntl[N];
int ans;
namespace Wisadel
{
void Wsol(int hk)
{
int lk=tot*2/hk,ch=0,cl=0,res=1;
for(int i=1;i<=n;i++) if(hang[i]&&hsum[i]%hk==0) hzc[++ch]=i;
for(int i=1;i<=m;i++) if(lie[i]&&lsum[i]%lk==0) lzc[++cl]=i;
if(2*ch!=lk||2*cl!=hk) return;
for(int i=1;i<=ch;i++) for(int j=1;j<=cl;j++)
{
int ck=sum[hzc[i]][lzc[j]]-sum[hzc[i-1]][lzc[j]]-sum[hzc[i]][lzc[j-1]]+sum[hzc[i-1]][lzc[j-1]];
if(ck!=2) return;
}
std::fill(cnth+1,cnth+1+ch,0),std::fill(cntl,cntl+1+cl,0);
for(int i=1;i<=n;i++) if(hsum[i]%hk==0) cnth[hsum[i]/hk]++;
for(int i=1;i<=m;i++) if(lsum[i]%lk==0) cntl[lsum[i]/lk]++;
for(int i=1;i<ch;i++) res=1ll*res*cnth[i]%mod;
for(int i=1;i<cl;i++) res=1ll*res*cntl[i]%mod;
ans=(ans+res)%mod;
}
short main()
{
scanf("%d%d",&n,&m);getchar();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char ch=getchar();
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
if(ch=='Y') hang[i]++,lie[j]++,hsum[i]++,lsum[j]++,sum[i][j]++;
}
getchar();
hsum[i]+=hsum[i-1];
}
for(int i=1;i<=m;i++) lsum[i]+=lsum[i-1];
tot=hsum[n];
if(tot&1){printf("0\n");return Ratio;}
for(int i=2;i<=n*m;i+=2)
{
if(tot%i==0) Wsol(i);
if(i>tot) break;
}
printf("%d\n",ans%mod);
return Ratio;
}
}
int main(){return Wisadel::main();}
C. 空之境界
饭堂的一题，最简单的区间 dp 暴力想不到。
纯搜 + 打表样例拿到 10pts。其实赛时想到 dp 了，但真想不起来区间 dp，看来该补补了。
60pts 代码
#define fuck printf("################33\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=4005;
const int mod=998244353;
int n,f[N][N],w[N][N];
namespace Wisadel
{
int Wdfs(int x,int y)
{
if(f[x][y]||x>=y) return f[x][y];
int ans=mod;
for(int i=x+1;i<=y;i+=2)
ans=min(ans,max({w[x][i],Wdfs(x+1,i-1),Wdfs(i+1,y)}));
return f[x][y]=ans;
}
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
n=qr;
fo(i,1,n) for(int j=i+1;j<=n;j+=2) w[i][j]=qr;
printf("%d\n",Wdfs(1,n));
return Ratio;
}
}
int main(){return Wisadel::main();}
D. 穗
原[Ynoi2016] 镜中的昆虫 我何德何能现在就做上 ynoi 的题了
猜猜我为什么现在才发记录。
扫了一眼，啊！\(\huge{带修莫队！}\)made 这不是我写博客时直接忽视的东西吗wwwww （再也不骑士某个算法了
只拿到了 20pts 的\(\mathcal{O(nm)}\) 暴力分，另外 20pts 不带修的一眼放普通莫队过的，结果又饭堂，离散化后没有直接赋值到原数组上，每次都 lower_bound 一遍导致复杂度直接乘上一个 \(\log n\) 导致爆炸。
然后重温了一下午的带修莫队，被数颜色卡了 5 个 h，最后也是发现一个堂食错误然后过了啊。
80pts 代码
200 行，比正解都长
#define fuck printf("################33\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=1e6+5;
const int mod=998244353;
int n,m,tot;
int a[N],b[N];
struct rmm
{
int op,l,r,x,id;
}q[N];
namespace Wistask1
{
map<int,int>mp;
int ans=0;
short main()
{
while(m--)
{
int op=qr,l=qr,r=qr,x;
if(op==1)
{
x=qr;
fo(i,l,r) a[i]=x;
}
else
{
mp.clear();ans=0;
fo(i,l,r)
{
if(!mp[a[i]]) ans++,mp[a[i]]++;
mp[a[i]]++;
}
printf("%d\n",ans);
}
}
return Ratio;
}
}
namespace Wistask2
{
int b[N],ed[N],bl[N],ans[N],anss,num[N];
bool cmp(rmm a,rmm b)
{
if(bl[a.l]==bl[b.l])
{
if(bl[a.l]&1) return a.r<b.r;
return a.r>b.r;
}
return a.l<b.l;
}
void Wadd(int x)
{
if(!num[a[x]]) anss++;
num[a[x]]++;
}
void Wdel(int x)
{
num[a[x]]--;
if(!num[a[x]]) anss--;
}
short main()
{
fo(i,1,n) b[i]=a[i];
sort(b+1,b+1+n);
int tot=unique(b+1,b+1+n)-b-1;
fo(i,1,n) a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
int sq=sqrt(n);
fo(i,1,sq) ed[i]=n/sq*i;
ed[sq]=n;
fo(i,1,sq) fo(j,ed[i-1]+1,ed[i]) bl[j]=i;
sort(q+1,q+1+m,cmp);
int l=1,r=0;
fo(i,1,m)
{
while(l>q[i].l) Wadd(--l);
while(l<q[i].l) Wdel(l++);
while(r<q[i].r) Wadd(++r);
while(r>q[i].r) Wdel(r--);
ans[q[i].id]=anss;
}
fo(i,1,m) printf("%d\n",ans[i]);
return Ratio;
}
}
namespace Wistask3
{
int qcnt=0,rcnt=0,ed[N],bl[N],ans[N],anss=0,mp[N];
struct qry
{
int id,t,l,r;
bool operator<(const qry &b)const
{
if(bl[l]==bl[b.l])
if(bl[r]==bl[b.r]) return t<b.t;
else return r<b.r;
return l<b.l;
//if(bl[l]!=bl[b.l]) return bl[l]<bl[b.l];
//else if(bl[r]!=bl[b.r]) return bl[r]<bl[b.r];
//else return t<b.t;
}
}qq[N];
struct ope
{
int p,x;
}rr[N];
inline void Wadd(int x)
{
if(!mp[x]) anss++;
mp[x]++;
}
inline void Wdel(int x)
{
mp[x]--;
if(!mp[x]) anss--;
}
short main()
{
// fo(i,1,n) b[i]=a[i];
sort(b+1,b+1+tot);
tot=unique(b+1,b+1+tot)-b-1;
fo(i,1,n) a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
int sq=pow(n,0.666);
// fo(i,1,sq) ed[i]=n/sq*i;
// ed[sq]=n;
// fo(i,1,sq) fo(j,ed[i-1]+1,ed[i]) bl[j]=i;
fo(i,1,n) bl[i]=i/sq+(i%sq!=0);
fo(i,1,m)
{
if(q[i].op==2) qq[++qcnt]={qcnt,rcnt,q[i].l,q[i].r};
else rr[++rcnt].p=q[i].l,rr[rcnt].x=lower_bound(b+1,b+1+tot,q[i].x)-b;
}
sort(qq+1,qq+1+qcnt);
int l=1,r=0,las=0;
fo(i,1,qcnt)
{
while(r<qq[i].r) Wadd(a[++r]);
while(r>qq[i].r) Wdel(a[r--]);
while(l>qq[i].l) Wadd(a[--l]);
while(l<qq[i].l) Wdel(a[l++]);
while(las<qq[i].t)
{
las++;
if(rr[las].p>=l&&rr[las].p<=r) Wadd(rr[las].x),Wdel(a[rr[las].p]);
swap(a[rr[las].p],rr[las].x);
}
while(las>qq[i].t)
{
if(rr[las].p>=l&&rr[las].p<=r) Wadd(rr[las].x),Wdel(a[rr[las].p]);
swap(a[rr[las].p],rr[las].x);
las--;
}
ans[qq[i].id]=anss;
}
fo(i,1,qcnt) printf("%d\n",ans[i]);
return Ratio;
}
}
namespace Wisadel
{
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
n=qr,m=qr;bool task2=1,task3=1;
fo(i,1,n) b[i]=a[i]=qr;
tot=n;
// fuck
if(n<=5000) return Wistask1::main();
fo(i,1,m)
{
q[i].op=qr,q[i].l=qr,q[i].r=qr;
q[i].id=i;
// char ch;cin>>ch;
// if(ch=='Q') q[i].op=2,q[i].l=qr,q[i].r=qr;
// else q[i].op=1,q[i].l=q[i].r=qr,b[++tot]=q[i].x=qr;
if(q[i].op==1)
{
b[++tot]=q[i].x=qr,task2=0;
if(q[i].l!=q[i].r) task3=0;
}
}
if(task2) return Wistask2::main();
if(task3) return Wistask3::main();
return Ratio;
}
}
int main(){return Wisadel::main();}
末
还是挺爽的，毕竟 A 了两道。
不过要是打满的话就 Rank1 了不是吗。
但是确实很难打满，1h 做 T1，做完 T2 已经十点了。
关于 T4 改题
- 怎么一直 RE？
“不是它咋不给我出调试语句啊”
“哦不对我编译错文件了” - 为啥输入一个字符导致 RE了？
“诶我Windows跑没问题啊”
“我重启下试试。。哦好了。。诶不对WA了。。诶不对编译错文件了。。。” - 这优化都一样怎么就 T 了？
“诶分块这步怎么会差这么多时间”
“我输出看看。。（输出了两种的分块结果）这咋两千多个块？哦这应该是块长。。”
穗限时返厂
豪堪捏
完结撒花~
你说得对
但我玩蓝图+益达的
