A.Equalize Prices Again
过水已略。
B.Social Network
题意
题解
用一个队列维护显示的消息，再开个 map 记录是否在队列中即可。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
map <int,int> mp;
int n,k,s,l,r,q[400005];
signed main()
{
n=read(); k=read();
l=1; r=0;
for (int i=1;i<=n;i++)
{
s=read();
if (mp[s]) continue;
if (r>=k) mp[q[l++]]=0;
q[++r]=s;
mp[s]=1;
}
printf("%d\n",r-l+1);
for (int i=r;i>=l;i--) printf("%d ",q[i]);
return 0;
}C.Pipes
题意
题解
从 $1$ 开始递推，用 $j$ 记录当前在上/下面。如果是弯的管道，那么需要改变状态，如果改变状态后是直的就无解。最后再判断下是不是在下面即可。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
int t,n;
char s[2][200005];
signed main()
{
t=read();
while (t--)
{
n=read();
scanf("%s",s[0]+1);
scanf("%s",s[1]+1);
int j=0; bool flag=0;
for (int i=1;i<=n;i++)
{
if (s[j][i]>'2')
{
j^=1;
if (s[j][i]<='2') { flag=1; break; }
}
}
if (flag || !j) puts("NO");
else puts("YES");
}
return 0;
}D.Distinct Characters Queries
题意
题解
树状数组裸题，开 $26$ 个直接怼。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const int N=100005;
char s[N],d[5];
int n,m,a,b,c,t[26][N];
inline void add(int x,int y,int z) { for (;x<=n;x+=x&-x) t[z][x]+=y; }
inline int query(int x,int z)
{
int ans=0;
for (;x;x-=x&-x) ans+=t[z][x];
return ans;
}
signed main()
{
scanf("%s",s+1);
n=strlen(s+1);
for (int i=1;i<=n;i++) add(i,1,s[i]-'a');
m=read();
while (m--)
{
a=read(); b=read();
if (a==1)
{
scanf("%s",d);
add(b,-1,s[b]-'a');
s[b]=d[0];
add(b,1,s[b]-'a');
}
else
{
c=read();
int ans=0;
for (int i=0;i<26;i++) ans+=(bool)(query(c,i)-query(b-1,i));
printf("%d\n",ans);
}
}
return 0;
}E.Special Permutations
题意
题解
考虑每一个数对 $x_k,x_{k+1}$ 对 $i$ 的贡献，令数对中较小值为 $l$ ，较大值为 $r$ ：
- $i < l$ ，移动不对数对产生影响，贡献还是 $r-l$
- $i = l$ ，$l\rightarrow 1$ ，$r > l$ 所以不变，贡献为 $r-1$
- $i\in (l,r)$ ，中间会被移走一个数，所以贡献为 $r-l-1$
- $i = r$ ，$r\rightarrow 1$ ，$l < r$ 所以向后移动一位，贡献为 $l+1-1=l$
- $i > r$ ，不产生影响，贡献为 $r-l$
可以用差分维护贡献。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar(); ll f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const ll N=200005;
ll n,m,x[N],s[N];
inline void add(ll l,ll r,ll w)
{
s[l]+=w;
s[r+1]-=w;
}
signed main()
{
n=read(); m=read();
for (ll i=1;i<=m;i++) x[i]=read();
for (ll i=1;i<m;i++)
{
ll l=x[i],r=x[i+1];
if (l==r) continue;
if (l>r) swap(l,r);
add(1,l-1,r-l);
add(l,l,r-1);
if (r-l>1) add(l+1,r-1,r-l-1);
add(r,r,l);
add(r+1,n,r-l);
}
for (ll i=1;i<=n;i++) printf("%lld ",s[i]+=s[i-1]);
return 0;
}F.Yet Another Substring Reverse
题意
仔细分析可以发现所谓的翻转子串，就是任意合并两个子串。坑死了
然后可以发现字符数 $\le 20$ ，考虑状压。用 $f(S)$ 表示字符状态为 $S$ 时子串的最长长度，最后枚举两个互斥的状态相加取最大值即是答案。
合法的子串最长为 $20$ ，所以可以扫一遍找到所有合法状态的长度，然后更新所有状态的最大值。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const int N=1<<20;
int n,ans,f[N];
char s[1000005];
signed main()
{
scanf("%s",s+1);
n=strlen(s+1);
for (int i=1;i<=n;i++) s[i]-='a';
for (int i=1;i<=n;i++)
{
int maxj=min(n,i+19),cur=0;
for (int j=i;j<=maxj;j++)
{
if (cur>>s[j]&1) break;
cur|=1<<s[j];
f[cur]=j-i+1; //状态为 cur 的长度
}
}
for (int i=0;i<N;i++) for (int j=0;j<20;j++)
{
if (i>>j&1) continue;
f[i|(1<<j)]=max(f[i|(1<<j)],f[i]); //更新所有状态
}
for (int i=0;i<N;i++)
{
int j=(N-1)^i; //选互斥的集合
ans=max(ans,f[i]+f[j]);
}
return !printf("%d",ans);
}