2019ICPC-银川站补题
发布时间
阅读量：
阅读量
下下周就要打icpc银川站了，今天和队友一起做了一套2019年的银川站的原题，感觉收获很多，也发现了很多问题。趁有时间补下题吧，也算是给自己积点幸运值。希望接下来的icpc银川站可以取得自己满意的成绩。菜鸡只希望拿个铜牌就行了。QAQ。
N. Fibonacci Sequence
签到题，直接输出非波纳西数列的前5项就行了，拼手速的话直接用python就行了。
print('1 1 2 3 5')
python
B. So Easy
给一个n行n列的矩阵，初始时全部都是0,可以对某一行整行或者某一列的整列进行同时加上某一个正数的操作。最后将某一个位置的数变为-1,问最后给出一个数列，是否可以找到这个-1上本来应该的值是多少。
我们直接对每行找出该行的最小值，然后同一行的所有数都减去这个最小值，对列执行同样的操作，但是要注意的是-1位置的行或者列的不可以进行处理。最后，求-1位置的该行的数与该列的数相加的结果的值就是我们要求的了，但是要注意-1的位置可能在边界的情况。
#include<iostream>
#include<cstring>
using namespace std;
int a[1010][1010];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
int mi=1e9;
for(int j=1;j<=n;j++){
mi=min(mi,a[i][j]);
}
if(mi==-1) continue;
for(int j=1;j<=n;j++){
a[i][j]-=mi;
}
}
for(int i=1;i<=n;i++){
int mi=1e9;
for(int j=1;j<=n;j++){
mi=min(mi,a[j][i]);
}
if(mi==-1) continue;
for(int j=1;j<=n;j++){
a[j][i]-=mi;
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// cout<<a[i][j]<<" ";
// }
// cout<<endl;
// }
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]==-1){
int ans=0;
if(i+1<=n){
ans+=a[i+1][j];
}else if(i-1>0){
ans+=a[i-1][j];
}
if(j+1<=n){
ans+=a[i][j+1];
}else if(j-1>0){
ans+=a[i][j-1];
}
cout<<ans<<endl;
return 0;
}
}
}
return 0;
}
cpp
I. Base62
进制转换，大模拟题，用到的就是高精度加法，乘法和除法这三种。用C++的话相对比较麻烦，比赛的时候想用py的，但是发现不会将某一个字符的下标进行ASCII加减法，所以直接硬刚C++，最后三次罚时通过。赛后补题用Python直接一次通过，人生苦短，我用python。python用的是ord这个函数将字符转化为相应的ASCII码，相反，利用chr可以将ASCII转划为字符。但是，不管是C++还是python，都记得z为0的情况。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> sum,k[220],tmp;
vector<int> add(vector<int> &A,vector<int> &B){
vector<int> C;
int t=0;
for(int i=0;i<A.size()||i<B.size();i++){
if(i<A.size()) t+=A[i];
if(i<B.size()) t+=B[i];
C.push_back(t%10);
t/=10;
}
if(t) C.push_back(t);
return C;
}
vector<int> mul(vector<int> &A,int b){
vector<int> C;
int t=0;
for(int i=0;i<A.size()||t;i++){
if(i<A.size()) t+=A[i]*b;//模拟
C.push_back(t%10);
t/=10;
}
while(C.size()>1&&C.back()==0) C.pop_back();//排除前导0,b为0时会出现多余前导0
return C;
}
vector<int> div(vector<int> &A,int b,int &r){
vector<int> C;
for(int i=A.size()-1;i>=0;i--){
r=r*10+A[i];
C.push_back(r/b);
r%=b;
}
reverse(C.begin(),C.end());//翻转是为了方便去除前导0
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}
void print(vector<int> a){
for(int i=a.size()-1;i>=0;i--){
cout<<a[i];
}
cout<<endl;
}
bool judge(vector<int> a){
int Sum=0;
for(int i=0;i<a.size();i++){
Sum+=(a[i]);
}
if(Sum) return true;
return false;
}
int main(){
int x,y;
cin>>x>>y;
string s;
cin>>s;
if(s=="0"){
cout<<"0"<<endl;
return 0;
}
if(x==y){
cout<<s<<endl;
return 0;
}
vector<int> v;
for(int i=s.size()-1;i>=0;i--){
v.push_back(s[i]-'0');
}
k[0].push_back(1);
int len=s.size();
for(int i=1;i<len+2;i++){
k[i]=mul(k[i-1],x);
}
sum.push_back(0);
for(int i=len-1;i>=0;i--){
tmp.clear();
tmp.push_back(0);
int d=0;
if(s[i]>='A'&&s[i]<='Z') d=s[i]-'A'+10;
if(s[i]>='a'&&s[i]<='z') d=s[i]-'a'+36;
if(s[i]<='9') d=s[i]-'0';
int index=len-1-i;
tmp=mul(k[index],d);
sum=add(sum,tmp);
}
string res="";
while(judge(sum)){
int r=0;
sum=div(sum,y,r);
// print(sum);
// cout<<"r:"<<r<<endl;
if(r<10) res+=(r+'0');
else if(r<36) res+=(r-10+'A');
else res+=(r-36+'a');
}
reverse(res.begin(),res.end());
cout<<res<<endl;
return 0;
}
cpp
python代码：
x,y,s=input().split()
x=int(x)
y=int(y)
l=len(s)
if(s=="0"):
print("0")
exit(0)
sum=0
tmp=1
for i in range(0,l):
k=0
if s[l-i-1]<='Z' and s[l-i-1]>='A':
k=ord(s[l-i-1])-ord('A')+10
if s[l-i-1]<='z' and s[l-i-1]>='a':
k=ord(s[l-i-1])-ord('a')+36
if s[l-i-1]<='9':
k=ord(s[l-i-1])-ord('0')
sum+=tmp*k
tmp=tmp*x
ans=[]
while sum>0:
k=sum%y
sum//=y
if k<10:
ans.append(chr(k+ord('0')))
elif k<36:
ans.append(chr(k-10+ord('A')))
else:
ans.append(chr(k-36+ord('a')))
ans.reverse()
l=len(ans)
for i in range(0,l):
print(ans[i],end="")
python
Largest Common Submatrix
这个题目乍一看是一个模板题，但是看一下数据发现直接对矩阵进行哈希的话时间复杂度很高，仔细看题，发现这个矩阵的每个位置的数字都是不一样的。所以可以利用单调栈来进行求解。对于每个位置，我们用一个数组f表示矩阵a位置(i,j)上面与矩阵相同位置的最长的一样的数字的长度。然后，我们对每一行的所有列执行单调栈的写法，记得判断中间可能断开的情况。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
#define fi first
#define se second
#define pb push_back
int n,m;
int a[1111][1111],b[1111][1111];
struct node{
int x,y;
}pA[N];
int f[N];
pair<int,int> q[1003];
int h,t;
int L[1003],ans=1;
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)scanf("%d",&a[i][j]),pA[a[i][j]]={i,j};}
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&b[i][j]);
//对矩阵求改位置向上的最长的相同数字的长度
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[b[i][j]]=1;
int le = b[i-1][j],dx=pA[b[i][j]].x,dy=pA[b[i][j]].y;
if(a[dx-1][dy]==le)f[b[i][j]]=f[le]+1;
ans=max(ans,f[b[i][j]]);
}
}
for(int i=1;i<=n;i++){
//对每行求单调栈
h=1;t=0;int can=1;
for(int j=1;j<=m;j++){
if(j==1)q[++t]={f[b[i][j]],1};
else{
int le = b[i][j-1];
int dx=pA[b[i][j]].x,dy=pA[b[i][j]].y;
if(a[dx][dy-1]!=le){
while(h<=t){
ans=max(ans,(j-q[h].se)*q[h].fi);
h++;
}
h=1;t=0;
q[++t]={f[b[i][j]],j};
continue;
}
int pos=j;
while(h<=t&&q[t].fi>=f[b[i][j]]){
ans=max(ans,(j-q[t].se)*q[t].fi);
t--;
pos=q[t+1].se;
}
q[++t]={f[b[i][j]],pos};
}
}
while(h<=t){
ans=max(ans,(m-q[h].se+1)*q[h].fi);
h++;
}
}
printf("%d\n",ans);
return 0;
}
cpp
G Pot!!
这个题目题意就是线段树的常规操作，区间1-n初始全部都是1,给两个操作：
1、在[l,r]都乘上一个数字x(1<=x<=10)
2、询问区间[l,r]上的每个质因数出现的次数最大值。
由于x在1-10直接，所以很显然，质因数也就只有2,3，5,7,所以我们可以对四个质因数分别构建线段树，初始化都是0,然后每进行一次操作，我们就将x进行质因数分解，然后更新相应的线段树即可。查询的时候我们对四棵线段树查找出出现最多的那个素数的次数就行了，需要使用懒标记。
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct node{
int l,r;
int mx;
int tag;
}Node[10][N<<2];
int a[4]={2,3,5,7};
void pushup(int id,int p){
Node[id][p].mx=max(Node[id][p<<1].mx,Node[id][p<<1|1].mx);
}
void build(int p,int l,int r,int id){
Node[id][p].l=l,Node[id][p].r=r;
if(l==r){
Node[id][p].mx=0;
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid,id);
build(p<<1|1,mid+1,r,id);
pushup(id,p);
}
void pushdown(int id,int p){
if(Node[id][p].tag){
Node[id][p<<1].tag+=Node[id][p].tag;
Node[id][p<<1|1].tag+=Node[id][p].tag;
Node[id][p<<1].mx+=Node[id][p].tag;
Node[id][p<<1|1].mx+=Node[id][p].tag;
Node[id][p].tag=0;
}
}
void update(int p,int l,int r,int id){
if(Node[id][p].l>=l&&Node[id][p].r<=r){
Node[id][p].tag++;
Node[id][p].mx++;
return;
}
pushdown(id,p);
int mid=(Node[id][p].r+Node[id][p].l)>>1;
if(l<=mid) update(p<<1,l,r,id);
if(r>mid) update(p<<1|1,l,r,id);
pushup(id,p);
}
int query(int p,int l,int r,int id){
if(Node[id][p].l>=l&&Node[id][p].r<=r){
return Node[id][p].mx;
}
pushdown(id,p);
int mid=(Node[id][p].r+Node[id][p].l)>>1;
int sum=0;
if(l<=mid) sum=max(sum,query(p<<1,l,r,id));
if(r>mid) sum=max(sum,query(p<<1|1,l,r,id));
return sum;
}
int main(){
int n,q;
scanf("%d %d",&n,&q);
char op[20];
for(int i=0;i<4;i++){
build(1,1,n,a[i]);
}
while(q--){
scanf("%s",op);
if(*(op+1)=='U'){
// 将区间内的每个数字都乘x
int l,r,x;
scanf("%d %d %d",&l,&r,&x);
for(int i=0;i<4;i++){
while(x%a[i]==0){
update(1,l,r,a[i]);
x/=a[i];
}
}
}else{
// 查询区间的最大值
int l,r;
scanf("%d %d",&l,&r);
int ans=0;
for(int i=0;i<4;i++){
ans=max(ans,query(1,l,r,a[i]));
}
printf("ANSWER %d\n",ans);
}
}
return 0;
}
cpp
全部评论 (0)
还没有任何评论哟~