目录
NOIP2023
T1 词典(dict)
考察:贪心
首先任意多次操作本质就是随意排序,所以如果要使 \(w_i\) 最小,我们一定会使 \(w_i\) 从 \(a\) 到 \(z\) 排,其它都 \(z\) 到 \(a\) 排。然后考虑比较字典序的实质:
-
如果 \(w_i\) 中第一个(即最小的)字符都比 \(w_j\) 中第一个(即最大的)字符大,那么显然不可能满足性质。
-
如果相同,那么若存在,我们考虑第一个不同的位置,发现一定有 \(w_i>w_j\),而若不存在,则等价于两串相同,也不符合
因此我们只需要记录每个串的最大最小字符即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int n,m,minn[3005],maxn[3005],fl;
char s[3005];
signed main() {
cin>>n>>m;
for(int i=1;i<=n;i++) {
minn[i]=27;
scanf("%s",s+1);
for(int j=1;j<=m;j++)
minn[i]=min(minn[i],s[j]-'a'+1ll),maxn[i]=max(maxn[i],s[j]-'a'+1ll);
}
for(int i=1;i<=n;i++) {
fl=1;
for(int j=1;j<=n;j++)
fl&=(i==j||minn[i]<maxn[j]);
printf("%lld",fl);
}
return 0;
}
时间复杂度 \(O(nm+n^2)\),理论可以优化到 \(O(nm+n)\),但完全没必要。
T2 三值逻辑(tribool)
考察:模拟、图论(?)
我们拿个数组分别记录每个值在此刻与谁相等或与谁相反,特殊的,对于定值,多用 \(3\) 个变量记录,这是好模拟的。
然后操作结束后会得到若干初始值之间的相等与相反关系,考虑用无向有权图来刻画,那么由于每个点最多只贡献一条边,最终得到的是一个树与基环树的森林。
考虑对于每个联通块统计答案,容易发现,一个联通块要么全是 \(U\) 要么全不是 \(U\),所以:如果其中有 \(U\),那么只能算上贡献,否则除非迫不得已,我们一定不会赋 \(U\)。什么叫迫不得已?只有一种情况,就是基环树的环为奇环(奇环树(雾)),然后答案就是好统计的了。
但是细节很多,比如你基环树会找环吗?
我的代码相当丑。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int c,t,n,m,a[100005],fl[100005];
char op[5];int x,y;
int h[100005],cnt;
struct QWQ{int v,w,nxt;} e[100005*2];
void add(int u,int v,int w) {e[++cnt]={v,w,h[u]},h[u]=cnt;}
int vis[100005],num,ff,ans;
stack<int> st,wt;
void dfs(int u,int p,int ww) {
vis[u]=1;num++;
st.push(u);wt.push(ww);
for(int i=h[u];i;i=e[i].nxt) {
int v=e[i].v,w=e[i].w;
if(v==p) continue;
if(vis[v]&&ff==-1) {
ff=w;
while(st.size()&&st.top()!=v) {
ff^=wt.top();
st.pop();wt.pop();
}
}
if(!vis[v]) dfs(v,u,w);
}
if(ff==-1) st.pop(),wt.pop();
}
signed main() {
cin>>c>>t;
while(t--) {
n=read(),m=read();
for(int i=1;i<=n+3;i++) a[i]=i,fl[i]=0;
memset(h,0,sizeof(h));cnt=0;
memset(vis,0,sizeof(vis));
ans=0,num=0;
for(int i=1;i<=m;i++) {
scanf("%s%lld",op+1,&x);
switch(op[1]) {
case '+':y=read();a[x]=a[y],fl[x]=fl[y];break;
case '-':y=read();a[x]=a[y],fl[x]=fl[y]^1;break;
case 'T':a[x]=n+1,fl[x]=0;break;
case 'F':a[x]=n+2,fl[x]=0;break;
case 'U':a[x]=n+3,fl[x]=0;break;
}
}
for(int i=1;i<=n;i++)
add(i,a[i],fl[i]),add(a[i],i,fl[i]);
while(st.size()) st.pop(),wt.pop();ff=-1;
dfs(n+3,0,0);
ans+=num-1;
while(st.size()) st.pop(),wt.pop();ff=-1;
if(!vis[n+1]) dfs(n+1,0,0);
while(st.size()) st.pop(),wt.pop();ff=-1;
if(!vis[n+2]) dfs(n+2,0,0);
for(int i=1;i<=n;i++) {
if(!vis[i]) {
while(st.size()) st.pop(),wt.pop();ff=-1;
int las=num;
dfs(i,0,0);
if(ff==1) ans+=num-las;
}
}
printf("%lld\n",ans);
}
return 0;
}
时间复杂度 \(O(\sum n+m)\)。
T3 双序列拓展(expand)
考察:\(dp\)、人类智慧(
部分分启示正解。
- \(35pts\) 的 \(O(qnm)\)
将原题目转化为这样:两个指针分别指着两个序列,每次将任意至少一个指针向后移一个位置,并使每时每刻都满足两个指针所指的位置有单调的偏序关系。
所谓单调的偏序关系可以用第一个位置来判断,在下文我们只考虑 \(a<b\) 的情况。
我们考虑 \(dp\):记 \(f_{i,j}\) 表示 \(a_{1-i}\) 能否和 \(b_{1-j}\) 匹配,那么有转移 \(f_{i,j}=(a_i<b_j)\&(f_{i-1,j}|f_{i,j-1}|f_{i-1,j-1})\)。此时即可 \(O(qnm)\) 完成本题。
- \(70pts\) 的特殊性质
我们考虑构造 01 矩阵 \(c\),其中 \(c_{i,j}=[a_i<b_j]\),那么等价于我们要判断是否存在只走 \(1\),只能向下、向右、向右下的路径从 \((1,1)\) 到 \((n,m)\)。
其实我们不会向右下走,因为可以证明不存在
1 0
0 1
这样的矩阵,但对正解没啥作用,所以我就没管了。
由于性质保证,我们发现最后一列与最后一行都是 \(1\)。接下来我们考虑 \(a\) 除 \(a_n\) 最小值 \(a_{min}\) 与 \(b\) 除 \(b_m\) 的最小值 \(b_{min}\),如果 \(a_{min}<b_{min}\),那么 \(a_{min}\) 所在的列也全是 \(1\),于是我们可以递归下去;否则,一定有 \(b_{min}\) 所在的行全是 \(0\)。
对于 \(a_{max}\) 和 \(b_{max}\) 我们同样考虑,如果 \(b_{max}>a_{max}\) 那么就继续递归,否则一定有 \(a_{max}\) 所在的列全是 \(0\),然后你发现,\(b_{min}\) 所在的行与 \(a_{max}\) 所在的列把 \((1,1)\) 围起来了!于是就直接返回 \(false\)。
实现的话预处理前缀 \(min\)、\(max\) 即可。
- \(100pts\)
其实 \(70pts\) 就是 \(100pts\) 的一半,物理意义的一半,我们寻找全局 \(a_{min}\) 和全局 \(b_{max}\),只要有一列或一行全是 \(0\),那么就相当于分割了 \((1,1)\) 和 \((n,m)\),否则做两次特殊性质即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int cc,n,m,q,c[500005],d[500005],a[500005],b[500005],pax[500005],pan[500005],sax[500005],san[500005],pbx[500005],pbn[500005],sbx[500005],sbn[500005];
bool calc1(int x,int y) {
if(x==1||y==1) return 1;
int ax=pax[x-1],an=pan[x-1],bx=pbx[y-1],bn=pbn[y-1];
if(a[an]<b[bn]) return calc1(an,y);
if(b[bx]>a[ax]) return calc1(x,bx);
return 0;
}
bool calc2(int x,int y) {
if(x==n||y==m) return 1;
int ax=sax[x+1],an=san[x+1],bx=sbx[y+1],bn=sbn[y+1];
if(a[an]<b[bn]) return calc2(an,y);
if(b[bx]>a[ax]) return calc2(x,bx);
return 0;
}
bool check() {
if(a[1]>b[1]) {
for(int i=1;i<=n;i++) a[i]*=-1;
for(int i=1;i<=m;i++) b[i]*=-1;
}
pax[1]=1,pan[1]=1;
for(int i=2;i<=n;i++)
pax[i]=(a[pax[i-1]]>a[i]?pax[i-1]:i),
pan[i]=(a[pan[i-1]]<a[i]?pan[i-1]:i);
pbx[1]=1,pbn[1]=1;
for(int i=2;i<=m;i++)
pbx[i]=(b[pbx[i-1]]>b[i]?pbx[i-1]:i),
pbn[i]=(b[pbn[i-1]]<b[i]?pbn[i-1]:i);
sax[n]=n,san[n]=n;
for(int i=n-1;i>=1;i--)
sax[i]=(a[sax[i+1]]>a[i]?sax[i+1]:i),
san[i]=(a[san[i+1]]<a[i]?san[i+1]:i);
sbx[m]=m,sbn[m]=m;
for(int i=m-1;i>=1;i--)
sbx[i]=(b[sbx[i+1]]>b[i]?sbx[i+1]:i),
sbn[i]=(b[sbn[i+1]]<b[i]?sbn[i+1]:i);
int ax=pax[n],an=pan[n],bx=pbx[m],bn=pbn[m];
if(a[an]>=b[bn]) return 0;
if(b[bx]<=a[ax]) return 0;
return calc1(an,bx)&calc2(an,bx);
}
signed main() {
cin>>cc>>n>>m>>q;
for(int i=1;i<=n;i++)
a[i]=c[i]=rd();
for(int i=1;i<=m;i++)
b[i]=d[i]=rd();
cout<<check();
while(q--) {
for(int i=1;i<=n;i++) a[i]=c[i];
for(int i=1;i<=m;i++) b[i]=d[i];
int k1=rd(),k2=rd();
for(int i=1;i<=k1;i++) {
int p=rd(),v=rd();
a[p]=v;
}
for(int i=1;i<=k2;i++) {
int p=rd(),v=rd();
b[p]=v;
}
cout<<check();
}
return 0;
}
时间复杂度 \(O(q(n+m))\)。
T4 天天爱打卡(run)
考察:\(dp\)、线段树
先考虑 \(n=10^5\) 的部分分。动态规划是显然的:记 \(f_{i,0/1}\) 表示前 \(i\) 位,最后一位选/不选的最大能量。转移: \(f_{i,0}=max(f_{i-1,0},f_{i-1,1})\),\(f_{i,1}=max_{i-j+1\le k}(f_{j-1,0}+val(j,i))\)。也是显然的线段树优化,把 \(val\) 拆成加减两部分,减的部分是简单的,而加的部分对挑战按结束时间排序,然后指针扫描即可。
接下来考虑满分做法,基于一个贪心理念:跑步的目的是为了完成挑战,所以显然就是对所有挑战的起始与终止点进行离散化,但是转移就有点不同了。
记 \(f_{i,0/1}\) 表示前 \(i\) 个关键点,最后一个选/不选的最大能量。
\(f_{i,0}=max(f_{i-1,0},f_{i-1,1})\) 是同理的,但 \(f_{i,1}\) 稍微有点不同,首先,我们枚举最后一段跑步之后,在上文中我们只能从 \(f_{j-1,0}\) 转移,这是为了使跑步不再连续,但在这儿,我们是可能可以从 \(f_{j-1,1}\) 转移的,因为两个关键点之间也许有空隙,我们只要在空隙中不跑步那么依然是不连续的,所以要特判关键点是否连续。然后转移的范围可以使用另一个指针来扫描,\(val\) 中加的部分与上文相同(因为所有起始终止点都是作为关键点参与离散化的),可减的部分就有点不同了:我们把其拆为 \(-d(p_i-p_{i-1})-d(p_{i-1}-p_{i-2})-\dots-d(p_{j+1}-p_j)-d\),然后考虑贡献,但是千万注意最后的那个 \(-d\)!被坑了好久,,,
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
#define inf ((int)1e12)
int c,t,n,m,k,d,b[200005],cnt,f[200005][2];
struct QWQ {int l,r,v;} a[100005];
bool cmp(QWQ a1,QWQ a2) {return a1.r<a2.r;}
struct Node {int l,r,d,laz;};
struct Segment_Tree {
Node t[4*200005];
int ls(int p) {return p<<1;}
int rs(int p) {return p<<1|1;}
void pushup(int p) {t[p].d=max(t[ls(p)].d,t[rs(p)].d);}
void pushdown(int p) {
t[ls(p)].d+=t[p].laz,t[rs(p)].d+=t[p].laz;
t[ls(p)].laz+=t[p].laz,t[rs(p)].laz+=t[p].laz;t[p].laz=0;
}
void clear(int p,int l,int r) {
t[p].l=l,t[p].r=r,t[p].d=-inf,t[p].laz=0;
if(l==r) return;int m=(l+r)>>1;
clear(ls(p),l,m);clear(rs(p),m+1,r);
}
void update(int p,int l,int r,int v) {
if(l>r) return;
if(l<=t[p].l&&t[p].r<=r) {t[p].d+=v,t[p].laz+=v;return;}
pushdown(p);int m=(t[p].l+t[p].r)>>1;
if(l<=m) update(ls(p),l,r,v);
if(r>m) update(rs(p),l,r,v);pushup(p);
}
int query(int p,int l,int r) {
if(l<=t[p].l&&t[p].r<=r) return t[p].d;
pushdown(p);int s=-inf,m=(t[p].l+t[p].r)>>1;
if(l<=m) s=max(s,query(ls(p),l,r));
if(r>m) s=max(s,query(rs(p),l,r));return s;
}
} tt;
signed main() {
cin>>c>>t;
while(t--) {
cin>>n>>m>>k>>d;
b[cnt=1]=n;
for(int i=1;i<=m;i++) {
int x=read(),y=read();
b[++cnt]=a[i].l=x-y+1,b[++cnt]=a[i].r=x,a[i].v=read();
}
sort(b+1,b+cnt+1);int q=unique(b+1,b+cnt+1)-b-1;
tt.clear(1,1,200002);
memset(f,-0x3f,sizeof(f));f[0][0]=0;tt.update(1,1,1,inf);
for(int i=1;i<=m;i++)
a[i].l=lower_bound(b+1,b+q+1,a[i].l)-b,a[i].r=lower_bound(b+1,b+q+1,a[i].r)-b;
sort(a+1,a+m+1,cmp);
for(int i=1,j=1,r=1;i<=q;i++) {
tt.update(1,1,i-1,-d*(b[i]-b[i-1]));
while(b[i]-b[j]+1>k) j++;
while(r<=m&&a[r].r==i)
tt.update(1,1,a[r].l,a[r].v),r++;
f[i][0]=max(max(f[i-1][0],f[i-1][1]),0ll);
f[i][1]=tt.query(1,j,i)-d;
if(b[i+1]-b[i]==1) tt.update(1,i+1,i+1,inf+f[i][0]);
else tt.update(1,i+1,i+1,inf+max(f[i][0],f[i][1]));
}
printf("%lld\n",max(f[q][0],f[q][1]));
}
return 0;
}
时间复杂度 \(O(m\log m)\)。
标签:ch,return,int,题解,while,max,NOIP2023,getchar From: https://www.cnblogs.com/operator-/p/17974763