2023 NOI 春季测试 题解
do_while_true
·
·
个人记录
挂个博客链接球球访问量。
2023.3.11 upd：原先那个 D 做法在被官方数据卡了一个点，常数太大了。又实现得精细了一点。
瞎做一通战绩：100+0+0+60，中间两个题忘加 #include<cmath> CE 了，6
啥时候考场能用 NOI Linux 啊。
A 涂色游戏
对于每行每列都记录一下最后一次操作的编号是什么。对于点 (x,y) 其被涂上的颜色就是 x 行和 y 列更靠后的那次涂色的颜色。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<cstring>
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;
typedef vector<int>vi;
typedef vector<pii>vpii;
typedef vector<ll>vll;
typedef vector<pll>vpll;
template<typename T>void cmax(T &x,T y){x=x>y?x:y;}
template<typename T>void cmin(T &x,T y){x=x<y?x:y;}
template<typename T>
T &read(T &r){
r=0;bool w=0;
char ch=getchar();
while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
while(ch>='0'&&ch<='9')r=r*10+ch-'0',ch=getchar();
return r=w?-r:r;
}
const int N=100010;
int n,m,q;
int r[N],c[N];
int col[N];
void solve(){
read(n);read(m);read(q);
for(int i=1;i<=n;i++)r[i]=0;
for(int i=1;i<=m;i++)c[i]=0;
for(int i=1;i<=q;i++){
int op,x;read(op);read(x);read(col[i]);
if(op==0)r[x]=i;
else c[x]=i;
}
for(int i=1;i<=n;i++,puts(""))
for(int j=1;j<=m;j++){
if(j<m)
cout << col[max(r[i],c[j])] << ' ';
else
cout << col[max(r[i],c[j])];
}
}
signed main(){
freopen("paint.in","r",stdin);
freopen("paint.out","w",stdout);
int T;read(T);while(T--)solve();
return 0;
}
B 幂次
$2\leq k\leq 3$：容斥。（不知道咋说明白，鸽了）
$k\geq 4$：直接暴力统计。
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cstring>
#include<cmath>
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define dbg(x) cerr<<"In the line " << __LINE__ << " the " << #x << " = " << x << '\n'
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;
typedef vector<int>vi;
typedef vector<pii>vpii;
typedef vector<ll>vll;
typedef vector<pll>vpll;
template<typename T>void cmax(T &x,T y){x=x>y?x:y;}
template<typename T>void cmin(T &x,T y){x=x<y?x:y;}
template<typename T>
T &read(T &r){
r=0;bool w=0;
char ch=getchar();
while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
while(ch>='0'&&ch<='9')r=r*10+ch-'0',ch=getchar();
return r=w?-r:r;
}
const int N=100010;
int n,k;
int vis[110];
signed main(){
// freopen("power.in","r",stdin);
// freopen("power.out","w",stdout);
read(n);read(k);
if(k==1){
cout << n << '\n';
return 0;
}
if(k>=60){
puts("1");
return 0;
}
auto sol=[](int x,int y){
if(!x)return 1;
int s=1;
for(int i=1;i<=y;i++)
if(n/x>=s)
s=s*x;
else return 0;
return 1;
};
auto calc=[&](int x){
int y=pow(n,1.0/x);
int t=0;
for(int i=max(y-5,0ll);i<=y+5;i++){
if(sol(i,x))
t=i;
}
return t;
};
if(k<=3){
vi vec;vec.pb(0);
for(int i=k;i<=59;i++){
if(!vis[i]){
vec.pb(i);
for(int j=2*i;j<=59;j+=i)
vis[j]=1;
}
}
int m=(int)vec.size()-1,ans=0;
for(int i=1;i<(1<<m);i++){
int x=1;
for(int j=0;j<m;j++)
if((1<<j)&i){
if(x<=59)
x=x*vec[j+1];
}
int s=0;
if(x<=59)
s=calc(x);
else
s=1;
if(__builtin_popcount(i)&1)ans+=s;
else ans-=s;
}
cout << ans << '\n';
return 0;
}
map<int,int>ok;
int ans=0;
for(int i=k;i<=59;i++){
int x=calc(i);
for(int j=1;j<=x;j++){
int s=1;
for(int k=1;k<=i;k++)
s=s*j;
if(!ok[s]){
ok[s]=1;
++ans;
}
}
}
cout << ans << '\n';
return 0;
}
```
# C 圣诞树
结论是连线一定不会出现交叉的情况。那么就区间 dp $f_{i,j,0/1}$ 表示已经连好了 $[i,j]$，最终落在 $i$ 还是落在 $j$．注意要在后面多复制一份，因为这个是个环。
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cstring>
#include<cmath>
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define dbg(x) cerr<<"In the line " << __LINE__ << " the " << #x << " = " << x << '\n'
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;
typedef vector<int>vi;
typedef vector<pii>vpii;
typedef vector<ll>vll;
typedef vector<pll>vpll;
template<typename T>void cmax(T &x,T y){x=x>y?x:y;}
template<typename T>void cmin(T &x,T y){x=x<y?x:y;}
template<typename T>
T &read(T &r){
r=0;bool w=0;
char ch=getchar();
while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
while(ch>='0'&&ch<='9')r=r*10+ch-'0',ch=getchar();
return r=w?-r:r;
}
const int N=2010;
int n,k;
ld x[N],y[N];
ld dis(int i,int j){
return sqrtl((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
ld f[N][N][2];
int pre[N][N][2];
signed main(){
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);
read(n);k=1;
for(int i=1;i<=n;i++){
scanf("%lf%lf",&x[i],&y[i]);
x[i+n]=x[i];
y[i+n]=y[i];
if(y[i]>y[k])
k=i;
}
for(int i=1;i<=2*n;i++)
if(i!=k&&i!=k+n)
f[i][i][0]=f[i][i][1]=1e15;
for(int len=1;len<n;len++){
for(int i=1;i+len<=2*n;i++){
int j=i+len;
if((i<=k&&k<=j)||(i<=k+n&&k+n<=j)){
int j=i+len;
f[i][j][0]=min(f[i+1][j][0]+dis(i,i+1),f[i+1][j][1]+dis(i,j));
pre[i][j][0]=f[i][j][0]==f[i+1][j][0]+dis(i,i+1)?0:1;
f[i][j][1]=min(f[i][j-1][0]+dis(i,j),f[i][j-1][1]+dis(j-1,j));
pre[i][j][1]=f[i][j][1]==f[i][j-1][0]+dis(i,j)?0:1;
}
else
f[i][j][0]=f[i][j][1]=1e15;
}
}
int l=1,r=n,o=0;
for(int i=1;i<=n;i++){
if(f[i][i+n-1][0]<f[l][r][o])
l=i,r=i+n-1,o=0;
if(f[i][i+n-1][1]<f[l][r][o])
l=i,r=i+n-1,o=1;
}
vi vec;
while(l!=r){
if(!o)vec.pb(l);
else vec.pb(r);
int nl,nr,no;
if(!o)
nl=l+1,nr=r,no=pre[l][r][o];
else
nl=l,nr=r-1,no=pre[l][r][o];
l=nl;r=nr;o=no;
}
vec.pb(k);
reverse(vec.begin(),vec.end());
for(auto i:vec){
if(i>n)cout << i-n << ' ';
else cout << i << ' ';
}
return 0;
}
```
# D 密码锁
$k\leq 2$ 平凡。$k=3$：二分答案。钦定 $\min$ 出现在第一行，枚举 $\max$ 出现在了哪一行。对于每个拨圈，枚举其哪一个是打头的，如果符合 $\min,\max$ 那一行的限制，那么就记录一下剩余的那一行是可以放那个值的。那么问题就变成了能否挑出值域上一个区间 $[i-mid,i]$ 满足 $1\sim n$ 在里面都出现过。
$k=4$：仍然是先二分答案之后钦定 $\min$ 位置枚举 $\max$ 位置。
剩下两行是一个二维的问题，转成矩形加颜色，查询是否有个点被所有颜色覆盖，这样一个问题。（注意这里同一颜色即同一拨圈所要加的矩形数很少）。
我没想到的，好像也是比较通用且好写的做法是，矩形并暴力容斥成矩形交，然后扫描线就是区间加 查最大值。
我写的做法是把矩矩形的横纵坐标都离散下来，暴力拆矩形，最后也是扫描线区间加 查最大值。
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cstring>
#include<cmath>
#include<ctime>
#include<random>
#include<assert.h>
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define dbg(x) cerr<<"In the line " << __LINE__ << " the " << #x << " = " << x << '\n'
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;
typedef vector<int>vi;
typedef vector<pii>vpii;
typedef vector<ll>vll;
typedef vector<pll>vpll;
template<typename T>void cmax(T &x,T y){x=x>y?x:y;}
template<typename T>void cmin(T &x,T y){x=x<y?x:y;}
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template<typename T>
T &read(T &r){
r=0;bool w=0;
char ch=getchar();
while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
while(ch>='0'&&ch<='9')r=r*10+ch-'0',ch=getchar();
return r=w?-r:r;
}
//mt19937 rnd(time(NULL)^(ull)(new char));
mt19937 rnd(0);
const int N=50010;
const int inf=0x7fffffff;
int n,k;
int a[N][5];
int b[N*4],m;
#define ls (x<<1)
#define rs ((x<<1)|1)
struct Node{
int mx,tag;
}tree[N*4*4];
inline void pushup(int x){tree[x].mx=max(tree[ls].mx,tree[rs].mx);}
inline void pushdown(int x){
if(tree[x].tag){
int p=tree[x].tag;tree[x].tag=0;
tree[ls].tag+=p;tree[rs].tag+=p;
tree[ls].mx+=p;tree[rs].mx+=p;
}
}
void build(int x,int l,int r){
tree[x].mx=tree[x].tag=0;
if(l==r)return ;
int mid=(l+r)>>1;
build(ls,l,mid);build(rs,mid+1,r);
}
void modify(int x,int tl,int tr,int l,int r,int v){
if(tl>=l&&tr<=r){
tree[x].mx+=v;tree[x].tag+=v;
return ;
}
int mid=(tl+tr)>>1;
pushdown(x);
if(mid>=l)modify(ls,tl,mid,l,r,v);
if(mid<r)modify(rs,mid+1,tr,l,r,v);
pushup(x);
}
#undef ls
#undef rs
void solve(){
read(n);
for(int i=1;i<=k;i++)
for(int j=1;j<=n;j++)
read(a[j][i]);
if(n==1){
puts("0");
return ;
}
if(k==1){
int mn=inf,mx=0;
for(int i=1;i<=n;i++)cmin(mn,a[i][1]),cmax(mx,a[i][1]);
cout << mx-mn << '\n';
return ;
}
if(k==2){
int mn=inf,mx=0,s=0;
for(int i=1;i<=n;i++)cmin(mn,min(a[i][1],a[i][2])),cmax(mx,min(a[i][1],a[i][2]));
s=mx-mn;
mn=inf,mx=0;
for(int i=1;i<=n;i++)cmin(mn,max(a[i][1],a[i][2])),cmax(mx,max(a[i][1],a[i][2]));
cmax(s,mx-mn);
cout << s << '\n';
return ;
}
if(k>=3){
m=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
b[++m]=a[i][j];
sort(b+1,b+m+1);
m=unique(b+1,b+m+1)-b-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
a[i][j]=lower_bound(b+1,b+m+1,a[i][j])-b;
auto po=[&](int x,int y){
return a[x][(y-1+k)%k+1];
};
if(k==3){
static vi ok[N*4];
static int vis[N];
auto check=[&](int mid){
for(int o=2;o<=3;o++){
for(int i=1;i<=m;i++)vi().swap(ok[i]);
for(int i=1;i<=n;i++)vis[i]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++)
if(b[po(i,j)]<=b[1]+mid&&b[po(i,j+o-1)]>=b[m]-mid)
ok[po(i,j+(o==2?3:2)-1)].pb(i);
}
int l=1,r=1,ct=0;
for(auto i:ok[1])ct+=++vis[i]==1;
for(l=1;l<=m;l++){
while(r<m&&b[r+1]-b[l]<=mid){
++r;
for(auto i:ok[r])ct+=++vis[i]==1;
}
if(ct==n)
return 1;
for(auto i:ok[l])ct-=--vis[i]==0;
}
}
return 0;
};
int l=0,r=30000,mid,ans=30000;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout << ans << '\n';
return ;
}
else{
static vpii addvec[N*4],delvec[N*4];
static int fr[N*4];
auto check=[&](int mid){
for(int i=1,j=1;i<=m;i++){
while(b[i]-b[j]>mid)++j;
fr[i]=j;
}
for(int o=2;o<=4;o++){
for(int i=1;i<=m;i++){
vpii().swap(addvec[i]);
vpii().swap(delvec[i]);
}
for(int i=1;i<=n;i++){
static int posx[15],totx;
static int posy[16],toty;
static int c[21][21];
totx=0;toty=0;
vpii vec;
for(int j=1;j<=4;j++)
if(b[po(i,j)]<=b[1]+mid&&b[po(i,j+o-1)]>=b[m]-mid){
int x=0,y=0;
for(int l=1;l<=3;l++)
if(l!=o-1){
if(!x)
x=po(i,j+l);
else{
y=po(i,j+l);
}
}
vec.pb(mp(x,y));
posx[++totx]=fr[x];
posx[++totx]=x+1;
posy[++toty]=fr[y];
if(y<m)posy[++toty]=y+1;
}
sort(posx+1,posx+totx+1);
totx=unique(posx+1,posx+totx+1)-posx-1;
sort(posy+1,posy+toty+1);
toty=unique(posy+1,posy+toty+1)-posy-1;
posy[toty+1]=m+1;
for(int i=0;i<=totx;i++)
for(int j=0;j<=toty;j++)
c[i][j]=0;
for(auto j:vec){
int x=j.fi,y=j.se;
int lx=lower_bound(posx+1,posx+totx+1,fr[x])-posx;
int rx=lower_bound(posx+1,posx+totx+1,x+1)-posx-1;
int down=lower_bound(posy+1,posy+toty+1,fr[y])-posy;
int up=lower_bound(posy+1,posy+toty+1,y+1)-posy-1;
for(int l=lx;l<=rx;l++)
c[l][down]++,c[l][up+1]--;
}
vpii lstvec;
for(int p=1;p<=totx;p++){
for(auto i:lstvec)
delvec[posx[p]].pb(mp(i.fi,i.se));
vpii().swap(lstvec);
int lst=0,op=0;
for(int q=1;q<=toty;q++){
c[p][q]+=c[p][q-1];
int now=c[p][q]>0;
if(!lst)lst=q,op=now;
else{
if(op!=now){
if(op==1){
int ydown=posy[lst],yup=posy[q]-1;
addvec[posx[p]].pb(mp(ydown,yup));
lstvec.pb(mp(ydown,yup));
}
lst=q;op=now;
}
}
}
int ydown=posy[lst],yup=m;
if(op==1)addvec[posx[p]].pb(mp(ydown,yup)),lstvec.pb(mp(ydown,yup));
}
}
build(1,1,m);
for(int i=1;i<=m;i++){
map<pii,int>vis;
for(auto j:addvec[i])
vis[j]++;
for(auto j:delvec[i])
vis[j]--;
for(auto j:vis)
if(j.se)
modify(1,1,m,j.fi.fi,j.fi.se,j.se);
if(tree[1].mx>=n)
return 1;
}
}
return 0;
};
int l=0,r=30000,mid,ans=30000;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout << ans << '\n';
return ;
}
}
}
signed main(){
freopen("lock.in","r",stdin);
freopen("lock.out","w",stdout);
int T;read(T);read(k);
while(T--)solve();
return 0;
}
```