题解-牛客IOI周赛25
A-字符串修改
模拟
注意加减法的取模就行了
#include<bits/stdc++.h>
using namespace std;
int n;
char a[100005];
int main(){
scanf("%d",&n);
scanf("%s",a);
for (int i=1;i<=n;i++){
int x=a[i-1]-'a';
if (i&1)x=x+i;
else x=x-i;
x+=2600000;
printf("%c",x%26+'a');
}
} B-学姐的编码1.0 序列自动机+dp
f[i]表示以i所代表的的字符为结尾的合法编码方案数，每次从最近的合法前置进行答案更新，可以保证不重复统计
复杂度O(16*n)
十六进制只有0~9，A~F共16种情况，最后枚举十六种情况，f[i]累加就是答案
#include<bits/stdc++.h>
using namespace std;
int n;
int g[50];
int f[1000005];
char a[1000005];
int main(){
scanf("%s",a);
n=strlen(a);
memset(f,0,sizeof(f));
for (int i=0;i<16;i++)g[i]=-1;
for (int i=0;i<n;i++){
int x;
if (a[i]<='9')x=a[i]-48;
else x=a[i]-55;
for (int j=0;j<x;j++)
if (g[j]!=-1)f[i]+=f[g[j]];
g[x]=i;f[i]++;
}
int ans=0;
for (int i=0;i<16;i++)
if (g[i]!=-1)ans+=f[g[i]];
printf("%d\n",ans);
return 0;
} C-学姐的编码2.0 序列自动机+dfs
这里涉及到一个关于答案量的计算，16进制，按位递增，满足这两个条件的合法编码最大方案数是2^16-1，所以只要不重复统计，在复杂度上是不会出现问题的
这里先序列自动机有一个复杂度O(16*n)的预处理，然后后面是一个复杂度O(16*方案数)的dfs
搞清楚递归调用的机制，倒序预处理，递归输出后正好就是字典序递增的答案
#include<bits/stdc++.h>
using namespace std;
const char p[16]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
char a[1000005];
int n,nt[1000005][20],g[20];
void dfs(int x,int y,string s){
if (y==n+1)return;
cout<<s+p[x]<<endl;
for (int i=x+1;i<16;i++)dfs(i,nt[y][i],s+p[x]);
}
int main(){
scanf("%s",a);
n=strlen(a);
for (int i=0;i<=9;i++)g[i]=n+1;
for (int i='A';i<='F';i++)g[i-55]=n+1;
for (int i=n;i>=1;i--){
int x;
if (a[i-1]>='0'&&a[i-1]<='9')x=a[i-1]-'0';
else x=a[i-1]-55;
for (int j=0;j<16;j++)nt[i][j]=g[j];
g[x]=i;
}
for (int i=0;i<16;i++)dfs(i,g[i],"");
} D-迷阵 枚举答案+验证
分成两部分操作
验证：如果给定上界Max和下界Min，可以确定极差dt=Max-Min,把[Min,Max]作为限制条件从(1,1)开始遍历，如果(n,n)能被遍历到说明dt=Max-Min是一个合法解，复杂度O(n*n)
枚举答案：双指针l,r枚举上下界，l,r的初始值为矩阵里的最小值和最大值(一个没什么大影响的优化，直接设l=0，r=3000也没有关系)，如果(l,r)是一对合法解r--，缩小答案，如果不合法把整个区间向右平移一位，即l++,r++,复杂度是线性的，即O(区间长度）
#include<bits/stdc++.h>
using namespace std;
const int p[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
bool vis[105][105];
int n,l,r,ans;
int a[105][105];
bool pd(int x,int y){
if (x<1||y<1||x>n||y>n)return 0;
if (vis[x][y])return 0;
return 1;
}
void pa(int x, int y, int xx, int yy){
vis[x][y]=1;
if (vis[n][n])return;
for (int i=0;i<4;i++)
if (pd(x+p[i][0],y+p[i][1]))
if (a[x+p[i][0]][y+p[i][1]] >= xx&&a[x + p[i][0]][y + p[i][1]] <= yy)pa(x + p[i][0], y + p[i][1], xx, yy);
}
int main(){
scanf("%d",&n);
l=3001;r=-1;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
l=min(l,a[i][j]);r=max(r,a[i][j]);
}int p=r;ans=r-l;r--;
while (l<=r){
if (r>p||l>a[1][1]||l>a[n][n])break;
while (l<=r){
if (r<a[1][1]||r<a[n][n])break;
memset(vis,0,sizeof(vis));
pa(1,1,l,r);
if (vis[n][n]) ans=r-l,r--;
else break;
}
l++;r++;
}
printf("%d\n",ans);
return 0;
} 