2019银川区域赛

2019年银川区域赛.

昨日重现.

题目链接

https://www.jisuanke.com/contest/5527/challenges

N Fibonacci Sequence

直接输出斐波那契数列的前五项,

超级超级超级签到的大水题.

因为难度太低甚至计蒜客都没有收录这个题.

B So Easy

ac代码

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

const int maxv=1e3+10;
int a[maxv][maxv];
int tx,ty;
int n;

int main(){
	while(~scanf("%d",&n)){
		inc(i,1,n) inc(j,1,n) {
			scanf("%d",&a[i][j]);
			if(a[i][j]==-1) tx=i,ty=j,a[i][j]=0;
		}

		inc(i,1,n){
			int Min=0x3f3f3f3f;
			inc(j,1,n){
				if(i==tx && j==ty) continue;
			   	Min=min(Min,a[i][j]);
			}


			inc(j,1,n) a[i][j]-=Min;
		}

		inc(j,1,n){
			int Min=0x3f3f3f3f;
			inc(i,1,n) {
				if(i==tx && j==ty) continue;
				Min=min(Min,a[i][j]);
			}

			inc(i,1,n) a[i][j]-=Min;
		}


		int ans=-a[tx][ty];
		printf("%d\n",ans);
	}
	return 0;
}

I Base62

进制转化, 如果是c++的话需要使用大整数模板,当时现场赛抄写模板还抄错了细节,查了很长时间.

当时python用的并不是很熟练 现在其实也是:-|

下面放出python版的代码,有时间可以写写java版的代码.

有一个小的坑点,我以注释的形式在代码中标注了:-)


def char_to_num(ch):
    if(ch>='0'and ch<='9'):
        return ord(ch)-ord('0')
    elif(ch>='A' and ch<='Z'):
        return ord(ch)-ord('A')+10
    elif(ch>='a' and ch<='z'):
        return ord(ch)-ord('a')+36
    return 0

def num_to_char(num):

    if(num>=0 and num<=9):
        return chr(num+ord('0'))
    elif(num>=10 and num<=35):
        return chr(num-10+ord('A'))
    elif(num>=36 and num<=61):
        return chr(num-36+ord('a'))
    return 0

o=input().split()
x=int(o[0])
y=int(o[1])
z=o[2]

a=0

for ch in z:
    val=char_to_num(ch)
    a=a*x+val

ans=''

while(a!=0):
    t=a//y
    val=a-t*y
    a=t
    ch=num_to_char(val)
    ans+=ch

'''
如果a=0 那么上面while的过程是不会走的
'''
if(len(ans)==0):
    ans+='0'

res=''
for ch in ans:
    res=ch+res

print(res)

G Pot!!!

看懂题意之后,就会明白这是一个 需要区间加和区间求最大的线段树 的数据结构题.

数据结构的细节可能会比较繁琐,耐心一点哦:-)

ac代码

// ac
//
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}




const int maxv=1e5+10;
struct Tree{
	int l,r;
	int mx;
	int add;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define mx(x) tree[x].mx
#define add(x) tree[x].add	

}tree[maxv<<2][5];

#define ls o<<1
#define rs o<<1|1

void pushup(int o,int p){
	tree[o][p].mx=max(tree[ls][p].mx,tree[rs][p].mx);
}



void build(int l,int r,int o,int p){
	tree[o][p].l=l;
	tree[o][p].r=r;
	tree[o][p].mx=0,tree[o][p].add=0;
	if(l==r) return;
	int m=(l+r)>>1;
	build(l,m,ls,p);
	build(m+1,r,rs,p);
	pushup(o,p);
}

void pushdown(int o,int p){
	if(tree[o][p].add!=0){
		int l=tree[o][p].l;
		int r=tree[o][p].r;
		int m=(l+r)>>1;
		tree[ls][p].mx+=tree[o][p].add;
		tree[rs][p].mx+=tree[o][p].add;
		tree[ls][p].add+=tree[o][p].add;
		tree[rs][p].add+=tree[o][p].add;
		tree[o][p].add=0;
	}

}

void update(int ql,int qr,int add,int o,int p){

	int l=tree[o][p].l,r=tree[o][p].r;

	if(ql<=l&&r<=qr){
		tree[o][p].add+=add;
		tree[o][p].mx+=add;
		return ;
	}
	pushdown(o,p);

	int m=l+r>>1;

	if(ql<=m) update(ql,qr,add,ls,p);
	if(qr>m) update(ql,qr,add,rs,p);
	pushup(o,p);
}


int query(int ql,int qr,int o,int p){
	int l=tree[o][p].l,r=tree[o][p].r;

	if(ql<=l&& r<=qr) return tree[o][p].mx;

	pushdown(o,p);

	int m=l+r>>1;
	int res=-0x3f3f3f3f;
	if(ql<=m) res=max(res,query(ql,qr,ls,p));
	if(m<qr) res=max(res,query(ql,qr,rs,p));
	return  res;
}

int change(int x){
	if(x==2) return 1;
	if(x==3) return 2;
	if(x==5) return 3;
	if(x==7) return 4;
	return 0;
}

int n,q;

char s[20];
bool show=true;

int main(){

	show=false;

	scanf("%d%d",&n,&q);
		inc(i,1,4) build(1,n,1,i);
		while(q--){
			scanf("%s",s);
			if(show)			printf("%s\n",s);
	

			if(s[1]=='U'){
				int a,b,c;scanf("%d%d%d",&a,&b,&c);
				if(show) cout<<a<<" "<<b<<" "<<c<<endl;

				if(c==2) {
					update(a,b,1,1,1);
				}

				else if(c==3) update(a,b,1,1,2);
				else if(c==4) update(a,b,2,1,1);
				else if(c==5) update(a,b,1,1,3);
				else if(c==6){
					update(a,b,1,1,1);
					update(a,b,1,1,2);
				}else if(c==7){
					update(a,b,1,1,4);
				}else if(c==8){
					update(a,b,3,1,1);
				}else if(c==9){
					update(a,b,2,1,2);
				}else if(c==10){
					update(a,b,1,1,1);
					update(a,b,1,1,3);
				}
			}else {
				int a,b;scanf("%d%d",&a,&b);
	if(show)				cout<<a<<" "<<b<<endl;
				int res=0;
				for(int i=1;i<=4;i++){
					int t=query(a,b,1,i);
					res=max(res,t);
				}
				printf("ANSWER %d\n",res);
			}
		}
		
	return 0;
}

F function!

前缀和的前缀和,是一个数学题,感觉还挺技巧的,

如果范围大的话可以直接利用公式推导,如果范围小的话直接分块了.

还是这种类型的题目做的不够多啊.

为了处理mod 过程中可能出现的各种问题,我写了一个支持+,-,*时候同时进行mod运算的类,可以加入模板组.

相关资料

具体的数学推导可以看下面这个博客

https://blog.csdn.net/weixin_43464149/article/details/103326814

一个很好看的分数类的代码,利用的是friend函数,不过这个代码可能不适合在acm场上写,太繁琐了

https://www.cnblogs.com/gongkai/p/10806080.html

ac代码


#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

const ll mod = 998244353; 

struct mint{
	ll val;

	mint(ll o=0){
		val=o;
	}

	ll go(){ return val;}


	mint operator+(const mint & rhs) const{
		ll u=val%mod;
		ll v=rhs.val%mod;
		mint res;res.val=(u+v)%mod;
		return res;
	}
	mint operator-(const mint & rhs) const{
		ll u=val%mod;
		ll v=rhs.val%mod;
		mint res;res.val=(u-v+mod)%mod;
		return res;
	}

	mint operator*(const mint & rhs) const{
		ll u=val%mod;
		ll v=rhs.val%mod;
		mint res;res.val=(u*v)%mod;
		return res;
	}
};

ostream & operator << (ostream &out,const mint &rhs){
	out<<rhs.val;
	return out;
}

ll ksm(ll a,ll n){
	ll res=1;while(n){
		if(n&1) res=res*a%mod;
		a=a*a%mod;
		n>>=1;
	}return res;
}

mint inv2=mint(ksm(2,mod-2));
mint inv6=mint(ksm(6,mod-2));


ll n;
int main(){
	while(~scanf("%lld",&n)){
		ll res=0;

		if(n>=1000001){
			mint m=mint(1e6+1);
			mint tn=mint(n);
			mint one=mint(1);
			mint two=mint(2);
			mint fi=(tn+one)*(tn-m+one)*(m+tn)*inv2;
			mint se=tn*(tn+one)*(tn*two+one)*inv6;
			mint th=(m-one)*m*(m*two-one)*inv6;
			mint t=fi-se+th;
			ll val=t.go();
			res=(res+val)%mod;

		}

		ll rhs=0;
		for(ll a=2;a<=min(1000000LL,n);a++){
			ll sum=0,cnt=1;
			ll l=a,r=a*a-1;
			while(1){
				if(r>=n){
					r=min(r,n);
					ll len=r-l+1;
					sum=(sum+len%mod*cnt%mod)%mod;
					break;
				}else {
					ll len=r-l+1;
					sum=(sum+len%mod*cnt%mod)%mod;
				}
				l=r+1;
				r=l*a-1;
				cnt++;
			}
			sum=(sum*a)%mod;
			rhs=(rhs+sum)%mod;
		}
		res=(res+rhs)%mod;
		printf("%lld\n",res);
	}
	return 0;
}

K Largest Common Submatrix

看到这种最大子矩阵的题目,就应该第一时间想到悬线法和单调栈啊!!!

悬线法和单调栈的这类题目,我想我会单独再写一篇博客进行总结 现在也没有学完

单独利用悬线法的ac代码

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

const int maxv=1e3+10;
int a[maxv][maxv],b[maxv][maxv];
int n,m;
int ax[maxv*maxv],ay[maxv*maxv];

bool shu(int p,int q){
	int delta=ax[p]-ax[q];
	if(delta==-1 && ay[p]==ay[q]) return true;
	return false;
}

bool hen(int p,int q){
	int delta=ay[p]-ay[q];
	if(delta==-1 && ax[p]==ax[q]) return true;
	return false;
}

int l[maxv][maxv],r[maxv][maxv],h[maxv][maxv];

int main(){
	while(~scanf("%d%d",&n,&m)){
		inc(i,1,n) inc(j,1,m) {
			scanf("%d",&a[i][j]);
			ax[a[i][j]]=i,ay[a[i][j]]=j;
			l[i][j]=r[i][j]=j;
			h[i][j]=1;
		}
		inc(i,1,n) inc(j,1,m) scanf("%d",&b[i][j]);
		/*

		cout<<"A\n";
		inc(i,1,n) {
			inc(j,1,m) printf("%4d",a[i][j]);
			putchar('\n');
		}
		cout<<"B\n";
		inc(i,1,n){
			inc(j,1,m) printf("%4d",b[i][j]);
			putchar('\n');
		}


		*/

		int ans=0;
		inc(i,1,n) inc(j,2,m) 
			if(hen(b[i][j-1],b[i][j])) l[i][j]=l[i][j-1];
		inc(i,1,n) dec(j,m-1,1)
			if(hen(b[i][j],b[i][j+1])) r[i][j]=r[i][j+1];


		inc(i,1,n) inc(j,1,m) {
			if(i>1 && shu(b[i-1][j],b[i][j])){
				l[i][j]=std::max(l[i][j],l[i-1][j]);
				r[i][j]=std::min(r[i][j],r[i-1][j]);
				h[i][j]=h[i-1][j]+1;
			}

			int o1=r[i][j]-l[i][j]+1;
			int o2=h[i][j];

			ans=std::max(ans,o1*o2);
		}

		/*
		cout<<" L -------------\n";
		inc(i,1,n){	
			inc(j,1,m) printf("%4d",l[i][j]);
			putchar('\n');
		}
		cout<<" R --------------\n";
		inc(i,1,n){
			inc(j,1,m) printf("%4d",r[i][j]);
			putchar('\n');
		}

		*/




		printf("%d\n",ans);
	}
	return 0;
}

单独利用单调栈的ac代码

// beta
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

const int maxv=1e3+10;
int a[maxv][maxv],b[maxv][maxv];
int n,m;
int ax[maxv*maxv],ay[maxv*maxv];

bool shu(int p,int q){
	int delta=ax[p]-ax[q];
	if(delta==-1 && ay[p]==ay[q]) return true;
	return false;
}

bool hen(int p,int q){
	int delta=ay[p]-ay[q];
	if(delta==-1 && ax[p]==ax[q]) return true;
	return false;
}

int st[maxv];
int s,t;
int val[maxv];
int l[maxv],r[maxv];


int main(){
	while(~scanf("%d%d",&n,&m)){
		inc(i,1,n) inc(j,1,m) {
			scanf("%d",&a[i][j]);
			ax[a[i][j]]=i,ay[a[i][j]]=j;
		}
		inc(i,1,n) inc(j,1,m) scanf("%d",&b[i][j]);
		int ans=0;
		inc(i,1,n) {
			if(i==1) inc(j,1,m) val[j]=1;
			else {
				inc(j,1,m) if(shu(b[i-1][j],b[i][j])) val[j]++;
				else val[j]=1;
			}
			s=t=0;
			int L=1,R=m;
			inc(j,1,m){
				int now=val[j];
				if(j==1 || hen(b[i][j-1],b[i][j])) ;
				else {
					while(s<t) t--;
					L=j;
				}

				// val 和 st写反了 调试了半天:-|
				while(s<t && val[st[t-1]]>=now) t--;
				if(s==t) l[j]=L;
				else l[j]=st[t-1]+1;

				st[t++]=j;
			}



			s=t=0;
			dec(k,m,1){
				int now=val[k];
				if(k==m || hen(b[i][k],b[i][k+1])) ;
				else {
					while(s<t) t--;
					R=k;
				}
				while(s<t && val[st[t-1]]>=now) t--;
				if(s==t) r[k]=R;
				else r[k]=st[t-1]-1;
				st[t++]=k;
			}
			inc(j,1,m){
				int a=r[j]-l[j]+1;
				int b=val[j];
				ans=max(ans,a*b);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

数据生成代码和对拍程序

令人忧伤的是我利用悬线法写的第一份代码是有重大bug的(上面给出的代码bug已经修改),

但是依然神奇的通过了该题目, 所以带着对于数据的怀疑我又写了数据生成程序进行了对拍.

上述两种不同思路ac的代码对拍结果一致:-)

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


int main(){
	srand(time(0));
	int n=rand()%1000+1;
	int m=rand()%1000+1;
	vector<int> res;
	inc(i,1,(n*m)) res.pb(i);
	cout<<n<<" "<<m<<endl;

	random_shuffle(res.begin(),res.end());

	int cnt=0;
	inc(i,1,n){
		inc(j,1,m){
			printf("%d ",res[cnt]);
			cnt++;
		}
		printf("\n");
	}
    // 整个代码的灵魂
	random_shuffle(res.begin(),res.end());

	cnt=0;
	inc(i,1,n){
		inc(j,1,m){
			printf("%d ",res[cnt]);
			cnt++;
		}
		printf("\n");
	}
}
# 命名为bash.sh

cnt=0

while true; do
	./c > data.in
	./a<data.in> a.out
	./b<data.in> b.out
	diff a.out b.out
	if [ $? -ne 0 ] ;
	then break;
	else 
		echo $cnt
		let cnt=cnt+1
	fi
done

and more

事实上银川的这套题出的质量相当高了,考察了各种各样的能力,

不过可能有点依赖于平时的做题量,要不然有的知识点根本就不会啊(泪目).

网上也基本上可以找到对应题目的题解的: )

D 是莫比乌斯反演,欧拉降幂

E 是长链剖分+ 套路

H 是tarjan+ dijkstra+神奇的建图

J 是圆方树?

L 是大力搜索吧 (好像实现比较难写)

总之这套题目的其他题还是有必要做的啊 :-)

在未来来临之前,把之前未完成的心愿完成吧.


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!