竞赛讨论区 > 题解-牛客IOI周赛25
头像
213dd
发布于 2021-05-02 10:43
+ 关注

题解-牛客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;
}






全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐