2022牛客寒假算法基础集训营（六）全部题解
A 回文大师 哈希二分/kmp 【补】
题意：
翻译过来就是
求每一个前缀串 在原串的反串中有多少个相同的子串
题解：
可以构造一个反串
枚举反串开始的位置 再二分去找最长的和原前缀匹配（哈希O1判断）的在原串的位置，这个位置之前的所有前缀 的ans都+1，最后答案用差分维护
using namespace std;
const int N=1e6+5;
const int M=1e9+7;
const int qwq=23333;
int p[N];
int a[N];
int ans[N];
int haa[N],hbb[N];
int get(int a,int b) {
return hbb[b]-hbb[a-1]*p[b-a+1];
}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;
cin>>n;
p[0]=1;
for(int i=1; i<=n; i++) {
p[i]=p[i-1]*qwq;
}
for(int i=1; i<=n; i++) {
cin>>a[i];
haa[i]=haa[i-1]*qwq+a[i];
hbb[n-i+1]=hbb[n-i+1+1]*qwq+a[i];
}
reverse(a+1, a+1+n);
for(int i=1; i<=n; i++) {
hbb[i]=hbb[i-1]*qwq+a[i];
}
for(int i=1;i<=n; i++) {
int l=1,r=n-i+1;
while(l<=r) {
int mid=(l+r)/2;
if(get(i, i+mid-1)==haa[mid]) {
l=mid+1;
}else r=mid-1;
}
ans[1]++;
ans[l]--;//求出来的是l==mid+1
}
for(int i=1; i<=n; i++) {
ans[i]+=ans[i-1];
cout<<ans[i]<<" ";
}
cout<<endl;
return 0;
}
B 价值序列 计数
题意：
题解：
删除一个数，价值必定不增
上升的序列和下降的序列之间的数 是可取可不取的 每一个数对答案的贡献是 2^(sum)
而波峰的那个值和波谷至少保留一个不然答案会减少 对答案的贡献是（2^sum)-1
using namespace std;
const int N=2e7+5;
const int M=998244353;
struct node {
int v, sum;
}b[N];
int p[N],a[N];
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t; cin>>t;
while(t--) {
int n; cin>>n;
for (int i=1; i<=n; i++) {
cin>>a[i];
b[i].sum=0;
}
int cnt=0;
b[++cnt].v=a[1];b[cnt].sum=1;
for(int i=2; i<=n; i++) {
if(a[i]!=a[i-1]) b[++cnt].v=a[i];
b[cnt].sum++;
}
int ans=1;
for (int i=1; i<=cnt; i++) {
if(i==cnt||i==1)ans=(ans%M*(ksm(2, b[cnt].sum)-1+M)%M)%M;
else if (b[i-1].v<b[i].v&&b[i].v<b[i+1].v||b[i-1].v>b[i].v&&b[i].v>b[i+1].v) {
ans=(ans%M*(ksm(2, b[i].sum)+M)%M)%M;
}else {
ans=(ans%M*(ksm(2, b[i].sum)-1+M)%M)%M;
}
}
ans%=M;
cout<<ans<<endl;
}
return 0;
}
C 数组划分 栈/并查集 【补】
题意：
求某个区间的有几个子数组的每个前缀和都大于等于0 且划分的数组尽量少
题解：
从每个位置（记为l），出发去找第一个 $sum[r]-sum[l-1]<0$ 的 r 位置，题目里 r 是不包含的，这个 $[l, r)$ 就是最大的满足所有前缀和都大于等于 $0$ 的划分区间
就是对于每个 $l$ 去找第一个 $sum[r]
using namespace std;
const int N=5e6+5;
const int M=1e9+7;
const int qwq=23333;
const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,1,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
inline int read() {
int x=0,f=1;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
return x*f;
}
void print(int x)
{
if(x>9) print(x/10);
putchar(x%10|'0');
}
int l[N], r[N];
int sum[N];
int ans[N];
int st[N];
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
t=read();
while(t--) {
int n, q;
n=read();
q=read();
for(int i=1; i<=n; i++) {
int x=read();
sum[i]=sum[i-1]+x;
}
for(int i=1; i<=q; i++) {
l[i]=read();
r[i]=read();
}
int m=q;
int cnt=0;
st[++cnt]=n;
for(int i=n; i>=1; i--) {
while(cnt&&sum[st[cnt]]>=sum[i-1]) {
cnt--;
}
st[++cnt]=i-1;
while(m&&l[m]==i) {
int ll=1, rr=cnt;
while(ll<rr){
int mid=ll+rr>>1;
if(st[mid]<r[m])rr=mid;
else ll=mid+1;
}
ans[m]=cnt-(ll)+1;
m--;
}
}
for(int i=1; i<=q; i++) {
print(ans[i]);
putchar('\n');
}
}
return 0;
}
D 删除子序列 计数
题意：
题解：
因为T字符串没重复的字符 那么从后往前循环找 这个字符的后一个字母有没有
using namespace std;
const int N=2e6+5;
const int M=998244353;
int a[N], b[N],sum[N];
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--) {
int n, m;
cin>>n>>m;
string s;
string t;
cin>>s>>t;
for(int i=1; i<=26; i++) sum[i]=0;
map<char, char> mp;
for (int i=0; i<m-1; i++) mp[t[i]]=t[i+1];
for(int i=n-1; i>=0; i--) {
if(s[i]==t[m-1]) {
sum[s[i]-'a'+1]++;
}else {
if(sum[mp[s[i]]-'a'+1]) {
sum[mp[s[i]]-'a'+1]--;
sum[s[i]-'a'+1]++;
}
}
}
cout<<sum[t[0]-'a'+1]<<endl;
}
return 0;
}
E 骑士 贪心
题意：
题解：
找最大值
对于最大的那个人只要能打过第二大的
using namespace std;
const int N=2e6+5;
const int M=998244353;
int a[N], b[N], h[N];
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--) {
int n;
cin>>n;
int maxx=0, p=0, ma2=0, p2=0;
for(int i=1 ;i<=n; i++) {
cin>>a[i]>>b[i]>>h[i];
if(maxx<=a[i]) maxx=max(maxx,a[i]),p=i;
}
for(int i=1 ;i<=n; i++) {
if(ma2<=a[i]&&p!=i) ma2=max(ma2,a[i]);
}
int ans=0;
for(int i=1; i<=n; i++) {
if(i!=p) ans+=max(0ll, maxx-b[i]-h[i]+1);
else ans+=max(0ll, ma2-b[i]-h[i]+1);
}
cout<<ans<<endl;
}
return 0;
}
F +-串 分类讨论
题意：
一串+-的式子，+是+1，-是-1，可以改变符号k次使得算是绝对值最小
题解：
|
G 迷宫2 思维+最短路 【补】
题意：
题解：
随便你改一定有一条从$(1,1)$到$(n,m)$的路，对于每个点修改就要代价就为1 不修改代价就为0
于是问题变为找$(1,1)$到$(n,m)$的最短路径，对于点$(x,y)$，如果 $Cxy==L$，则 $(x,y)$ 到 $(x,y-1)$的花费为 $0$，到其它三个方向的花费为 $1$。
看错范围n，m<=1000，拿map当二维数组然后t死了
using namespace std;
const int N=1005+5;
const int M=1e9+7;
string maze[N];
bool is[N][N];
int n, m;
int t;
int dir[4][2]={{1,0},{-1,0}, {0, 1}, {0,-1}};
bool in(int x, int y) {
return 1<=x&&x<=n&&1<=y&&y<=m;
}
struct node{
int x, y, d;
bool operator <(const node&rhs) const {
return d>rhs.d;
}
};
struct node1{
int x, y;
};
int dis[N][N];
node1 pre[N][N];
priority_queue<node> q;
int dij() {
while(q.size()) q.pop();
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
dis[i][j]=1e18, is[i][j]=0;
}
}
dis[1][1]=0;
q.push({1,1, 0});
while(!q.empty()) {
node now=q.top();
q.pop();
for(int i=0; i<4; i++) {
int x=now.x+dir[i][0];
int y=now.y+dir[i][1];
if(in(x, y)) {
if(maze[now.x][now.y]=='U'&&i==1||maze[now.x][now.y]=='D'&&i==0||maze[now.x][now.y]=='L'&&i==3||maze[now.x][now.y]=='R'&&i==2) {
if(dis[x][y]>now.d) {
dis[x][y]=now.d;
pre[x][y]={now.x, now.y};
q.push({x,y,now.d});
}
}else {
if(dis[x][y]>now.d+1) {
pre[x][y]={now.x, now.y};
dis[x][y]=now.d+1;
q.push({x,y,now.d+1});
}
}
}
}
}
return dis[n][m];
}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>t;
while(t--) {
cin>>n>>m;
for(int i=1; i<=n; i++) {
cin>>maze[i];
maze[i]='.'+maze[i];
}
if(n==m&&n==1) {
cout<<0<<'\n';
continue;
}
cout<<dij()<<endl;
while(1) {
int x=pre[n][m].x;
int y=pre[n][m].y;
if((n-x)==1&&(m-y)==0) {
if(maze[x][y]!='D') cout<<x<<" "<<y<<" "<<"D"<<'\n';
}
else if((n-x)==-1&&(m-y)==0) {
if(maze[x][y]!='U') cout<<x<<" "<<y<<" "<<"U"<<'\n';
}
else if((n-x)==0&&(m-y)==-1) {
if(maze[x][y]!='L') cout<<x<<" "<<y<<" "<<"L"<<'\n';
}
else if((n-x)==0&&(m-y)==1) {
if(maze[x][y]!='R') cout<<x<<" "<<y<<" "<<"R"<<'\n';
}
n=x, m=y;
if(x==1&&y==1) break;
}
}
return 0;
}
H 寒冬信使2 博弈【补】
题意：
题解：
n很小
所以所有状态可以状态压缩存起来
当前状态如果在一次操作后变成了一个必败态，那么当前状态就是先手必胜
假如一个状态经过一次操作怎么都让对手赢那么当前状态就是先手必败
必败态是全黑 必胜态是两个白色或者第一个是白色
所以你每个状态只要找到他之前的状态里有一个必败 那么你这个状态就是必胜
using namespace std;
const int N=8e7+5;
const int M=998244353;
int a[N], b[N], c[N];
int dp[1<<14];
void init() {
dp[0]=0;
for(int i=1; i<(1<<12); i++) {
if((i&1)&&!dp[i^1]) {
dp[i]=1;
continue;
}
for(int j=0; j<=11&&!dp[i]; j++) {
if((1<<j)>i) break;
if((i&(1<<j))==0) continue;
for(int k=0; k<j; k++) {
if(dp[(i^(1<<j))^(1<<k)]==0) {
dp[i]=1;
break;
}
}
}
}
}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
init();
int t;
cin>>t;
while(t--) {
int n;
cin>>n;
string s;
cin>>s;
int p=0;
for(int i=0; i<n; i++) if(s[i]=='w') p+=(1<<i);
//cout<<p<<endl;
if(dp[p]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
I A+B问题 进制模拟
|
J 牛妹的数学难题 数学
题意：
题目骗你的
不过有个题https://codeforces.com/contest/1637/problem/D呜呜呜昨天考今天用
题解：
看到ai的范围
题目式子是每次选 k 个数字
|
