2019 ICPC 银川站
2019-12-11 16:00:43来源:博客园 阅读 ()
2019 ICPC 银川站
I. Base62(高精度进制转换)
比赛当时雷菊苣和队长俩人拿着大数板子摸了一百多行(然后在缺少大数板子的情况下雷菊苣一发过了orz) 今天补题随便摸了个高精度进制转换的板子交上去就过了还贼短,, 我好菜,佬们好厉害const int maxn = 1000; int t[maxn], A[maxn]; char str1[maxn], str2[maxn]; int n, m; void solve() { int i, len, k; len = strlen(str1); for(i=len; i>=0; --i) t[len-1-i] = str1[i] -(str1[i]<58 ? 48: str1[i]<97 ? 55: 61); for(k=0; len;) { for(i=len; i>=1; --i) { t[i-1] +=t[i]%m*n; t[i] /= m; } A[k++] = t[0] % m; t[0] /=m; while(len>0&&!t[len-1]) len--; } str2[k] =NULL; for(i=0; i<k; i++) str2[k-1-i] = A[i]+(A[i]<10 ? 48: A[i]<36 ? 55:61); } int main() { scanf("%d%d%s",&n, &m, str1); solve(); printf("%s\n",str2); return 0; }??
Largest Common Submatrix(单调栈)
求两个矩阵的最大相同子矩阵,两个矩阵位置可以不同 重点在两个矩阵都是全排列,那么我们可以做到O(1)找到某数字在另外一个矩阵的位置, 存下b数组中每个数字出现的位置,然后就普通最大01子矩阵写,,,然后挂掉了QAQ,首先是超时,加了快读果然很快就WA了(WA12,一开始写错一组判断条件还跑过10个样例。。神了) 菊苣说是因为没有判断合法性,但是我还是没想通QAQ 只好又去拿单调栈写QAQ 入栈的是该点为右边界时矩阵的高度和矩阵所能到达的左边界,最后留在栈内没弹出来的就以m为右边界,否则以j-1为右边界 再复习一下单调栈,以单调递增栈为例,入栈时,弹出的最后一个结点就是当前结点的左边界(代表着最后一个大于当前点的值) 对于该结点弹出的那些结点,当前结点的左边第一个位置就是他们的右边界(因为遍历到 j - 1 的时候他们还没有被弹出来,到 j 就要被弹出来了(你说气不气误))
int n,m; pii pos[MAXN]; pii q[MAXN];//单调递增栈 int high[1111][1111]; int a[1111][1111],b[1111][1111]; int main() { rd(n),rd(m); rpp(i,n) rpp(j,m) rd(a[i][j]); rpp(i,n) rpp(j,m) rd(b[i][j]),pos[b[i][j]]=make_pair(i,j); // int ans=0; rpp(i,n) rpp(j,m) { int x=pos[a[i][j]].first,y=pos[a[i][j]].second; if(a[i-1][j]==b[x-1][y]) high[i][j]=high[i-1][j]+1; else high[i][j]=1; ans=max(ans,high[i][j]); } rpp(i,n) { int t=0; rpp(j,m) { if(j==1) q[++t]=make_pair(high[i][j],1);//队列中first存该位置的高度,se位置存该位置向左最远能延伸到哪 else { int x=pos[a[i][j]].first,y=pos[a[i][j]].second; if(a[i][j-1]!=b[x][y-1])//这时候队列里面的元素已经结束了!再往后就断了,所以全部弹出 { while(t>0) ans=max(ans,(j-q[t].second)*q[t].first),--t; q[++t]=make_pair(high[i][j],j); } else { int p=j; while(t>0&&q[t].first>high[i][j]) ans=max(ans,(j-q[t].second)*q[t].first),p=q[t].second,--t; q[++t]=make_pair(high[i][j],p); } } } while(t>0) ans=max(ans,(m-q[t].second+1)*q[t].first),--t; } cout<<ans<<endl; //stop; return 0; }??
B. So Easy
哇这个题,,现场写了好久还WA了好多发,现在写就感觉,,,嗯???当时我是脑残吗,1A,就想清楚计算行列的贡献值就行了。int mn[MAXN];//每一行的最小值 int v[1111][1111]; int main() { int n,x,y;cin>>n; rep(i,n) mn[i]=1<<30; rep(i,n) rep(j,n) { cin>>v[i][j],mn[i]=min(mn[i],v[i][j]); if(v[i][j]==-1) x=i,y=j; } int ans=v[(x+1)%n][y]-mn[(x+1)%n];//列的贡献 ans+=v[x][(y+1)%n]-v[(x+1)%n][(y+1)%n]+mn[(x+1)%n];//行对他下一列的贡献就等同于对他的贡献 cout<<ans<<endl; //stop; return 0; }??
G. Pot!!(线段树)
又是一道在现场疯狂WA的题。。。现在想想感觉好气。。。明明很好写,我是脑残QAQ
一个教训就是线段树数组开大点 [MAXN<<2]这样子QAQ,还有就是不关流居然第五个样例就扑街了,,,提交前记得关流
还有一个教训就是看清数据范围啊啊啊啊,现场想了好久队友突然一句x大于2小于10点醒梦中人
#define lc root<<1 #define rc root<<1|1 #define ls root<<1,l,mid #define rs root<<1|1,mid+1,r struct IN { int t[MAXN<<2],lazy[MAXN<<2]; void build(int root,int l,int r) { if(l==r) {t[root]=0;return;} lazy[root]=0; int mid=(l+r)>>1; build(ls);build(rs); t[root]=0; } void push_down(int root) { t[lc]+=lazy[root],t[rc]+=lazy[root]; lazy[lc]+=lazy[root],lazy[rc]+=lazy[root]; lazy[root]=0; } void update(int root,int l,int r,int ql,int qr,int v) { if(ql<=l&&qr>=r) { t[root]+=v,lazy[root]+=v; return ; } int mid=(l+r)>>1; if(lazy[root]) push_down(root); if(ql<=mid) update(ls,ql,qr,v); if(qr>mid) update(rs,ql,qr,v); t[root]=max(t[lc],t[rc]); } int query(int root,int l,int r,int ql,int qr) { if(ql<=l&&qr>=r) return t[root]; int mid=(l+r)>>1; if(lazy[root]) push_down(root); int ans=0; if(ql<=mid) ans=max(ans,query(ls,ql,qr)); if(qr>mid) ans=max(ans,query(rs,ql,qr)); return ans; } }t2,t3,t5,t7; int main() { fast; int n,q;cin>>n>>q; t2.build(1,1,n);t3.build(1,1,n);t5.build(1,1,n);t7.build(1,1,n); while(q--) { string s;int l,r; cin>>s>>l>>r; if(s[1]=='U') { int v;cin>>v; if(v==2) t2.update(1,1,n,l,r,1); else if(v==3) t3.update(1,1,n,l,r,1); else if(v==4) t2.update(1,1,n,l,r,2); else if(v==5) t5.update(1,1,n,l,r,1); else if(v==6) t2.update(1,1,n,l,r,1),t3.update(1,1,n,l,r,1); else if(v==7) t7.update(1,1,n,l,r,1); else if(v==8) t2.update(1,1,n,l,r,3); else if(v==9) t3.update(1,1,n,l,r,2); else if(v==10) t2.update(1,1,n,l,r,1),t5.update(1,1,n,l,r,1); } else { int ans=0; ans=max(ans,t2.query(1,1,n,l,r)); ans=max(ans,t3.query(1,1,n,l,r)); ans=max(ans,t5.query(1,1,n,l,r)); ans=max(ans,t7.query(1,1,n,l,r)); cout<<"ANSWER "<<ans<<endl; } } //stop; return 0; }??
还有一道没输输入的真·签到题就不补了,over
(我感觉我也over了QAQ菜的真实)
原文链接:https://www.cnblogs.com/Herlo/p/12020565.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Visual Studio 2019提示不能将const char*类型的值分配到con 2020-06-07
- windows7 + Qt(MSVC2017) + VS2019安装配置 2020-04-25
- 2020年3月21日Benelux Algorithm Programming Contest 2019 2020-03-25
- 2019.3.14解题报告&补题报告 2020-03-22
- Qt5 error LNK2019 无法解析的外部符号的解决办法 2020-02-14
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash