T1. 坏掉的键盘 (keyboard)
传送门 http://218.5.5.242:9019/contest/13/problem/1
Description
\(n\times m\)网格, 从左上走到右下, 只能往下或往右
有一些障碍物, 数量 \(\leq 10^5\)
询问能否到达,\(n,m\leq 10^9\)
Solution?
直接暴力维护每行可以到达的区间即可
- Code?
- //70pts 离散后暴力算方案数
- #include<bits/stdc++.h>
- #define ll long long
- #define db double
- #define reg register
- #define dbg1(x) cerr<<#x<<"="<<(x)<<" "
- #define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"
- #define dbg3(x) cerr<<#x<<"\n"
- #define int ll
- using namespace std;
- inline int read()
- {
- int x=0,f=1;char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
- return x*f;
- }
- const int MN=4e5+5,P=19260817;
- int Mul(int x,int y){return (1ll*x*y)%P;}
- int Add(int x,int y){return (x+y)%P;}
- int nn,mm,n,m,k,x[MN],y[MN];
- int num[MN],tot,fac[MN],inv[MN];
- bool mp[6005][6005];int f[6000][6005];
- int lb(int _){return lower_bound(num+1,num+tot+1,_)-num;}
- bool chk()
- {
- if(k==0) return true;
- tot=0;reg int i,j;
- for(i=1;i<=k;++i)
- {
- num[++tot]=x[i];
- if(x[i]>1) num[++tot]=x[i]-1;
- if(x[i]<n) num[++tot]=x[i]+1;
- }
- num[++tot]=1;num[++tot]=n;
- std::sort(num+1,num+tot+1);
- tot=unique(num+1,num+tot+1)-num-1;
- for(i=1;i<=k;++i) x[i]=lb(x[i]);n=lb(n);
- tot=0;
- for(i=1;i<=k;++i)
- {
- num[++tot]=y[i];
- if(y[i]>1) num[++tot]=y[i]-1;
- if(y[i]<m) num[++tot]=y[i]+1;
- }
- num[++tot]=1;num[++tot]=m;
- std::sort(num+1,num+tot+1);
- tot=unique(num+1,num+tot+1)-num-1;
- for(i=1;i<=k;++i) y[i]=lb(y[i]);m=lb(m);
- memset(mp,0,sizeof mp);
- for(i=1;i<=k;++i) mp[x[i]][y[i]]=true;
- f[1][1]=1;
- for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(i!=1||j!=1)
- {
- if(!mp[i][j])f[i][j]=Add(f[i-1][j],f[i][j-1]);
- else f[i][j]=0;
- }
- return f[n][m]>0;
- }
- signed main()
- {
- #ifndef LOCAL
- freopen("keyboard.in","r",stdin);
- freopen("keyboard.out","w",stdout);
- #endif
- int T=read();
- while(T--)
- {
- nn=n=read(),m=mm=read(),k=read();
- reg int i;
- for(i=1;i<=k;++i) x[i]=read(),y[i]=read();
- printf("%lld\n",chk()?(ll)nn+(ll)mm-2ll:-1ll);
- }
- return 0;
- }
- //100 pts
- #include<bits/stdc++.h>
- #define ll long long
- #define dbg1(x) cerr<<#x<<"="<<(x)<<" "
- #define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"
- #define dbg3(x) cerr<<#x<<"\n"
- using namespace std;
- #define reg register
- inline int read()
- {
- int x=0,f=1;char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
- return x*f;
- }
- const int MN=1e5+5;
- struct node{int x,y;bool operator<(const node&o)const{return x<o.x||(x==o.x&&y<o.y);}};
- struct sec{int x,l,r;};
- sec P[MN<<2];node p[MN];int K,k;
- void mk(int x,int l,int r){if(x==1&&l!=1)return;P[++K]=(sec){x,l,r};}
- int n,m;
- int main()
- {
- #ifndef LOCAL
- freopen("keyboard.in","r",stdin);
- freopen("keyboard.out","w",stdout);
- #endif
- int T=read();
- while(T--)
- {
- n=read(),m=read(),k=read();K=0;
- reg int i,j;p[0]=(node){1,0};p[k+1]=(node){n,m+1};
- for(i=1;i<=k;++i) p[i].x=read(),p[i].y=read();
- std::sort(p+1,p+k+1);
- for(j=1,i=1;i<=k+1;++i)
- {
- if(p[i].x==p[i-1].x)
- {
- if(p[i].y>1+p[i-1].y)
- mk(j,p[i-1].y+1,p[i].y-1);
- }
- else
- {
- if(p[i-1].y<m) mk(j,p[i-1].y+1,m);
- if(p[i-1].x+1<p[i].x) mk(++j,1,m);
- ++j;if(p[i].y>1) mk(j,1,p[i].y-1);
- }
- }
- int N=j;
- for(i=1,j=2;j<=K;++j)
- {
- if(P[j].l>P[j].r){P[j].l=m+1;continue;}
- while(P[i].x<P[j].x-1&&i<=K){++i;while(P[i].l>P[i].r&&i<=K)++i;}
- while(P[i].x<P[j].x&&P[i].r<P[j].l&&i<=K){++i;while(P[i].l>P[i].r&&i<=K)++i;}
- if(i<j&&P[i].x==P[j].x-1&&P[i].r>=P[j].l) P[j].l=max(P[j].l,P[i].l);
- else P[j].l=m+1;if(P[j].l>P[j].r) P[j].l=m+1;
- }
- //for(i=1;i<=K;++i)dbg1(P[i].x),dbg1(P[i].l),dbg2(P[i].r);
- printf("%lld\n",(P[K].x==N&&P[K].l<=m&&P[K].r==m)?((ll)n+(ll)m-2ll):-1ll);
- }
- return 0;
- }
- T2. LibreOJ (libreoj)
传送门 http://218.5.5.242:9019/contest/13/problem/2
Description
给定 \(b\), 多组询问
每个询问给出 \(n\), 求出 \(\sum_{i=1}^n if(i)\)
其中 \(f(x)=atoi(sort(itoa(x,b)),b)\)
\(itoa(x,b)\)表示把 \(x\)转为 \(b\)进制的字符串
\(sort(s)\)表示将字符串 \(s\)按照字典序升序排序后的字符串
\(atoi(s,b)\)表示将字符串 \(s\)以 \(b\)今之形式转换得到的正整数
对 \(998244353\)取模
Solution?
\(11223446\) 产生了 \(11111111\)(大于等于 \(1\) 的)加 \(111111\) (大于等于 \(2\)的)加 \(1111\)(大于等于 \(3\)的)加 \(111\) (大于等于 \(4\) 的)加 \(1\)(大于等于 \(5\) 的)加 \(1\)(大于等于 \(6\) 的)加 \(0\)(大于等于 \(7,8,9\)的)的贡献.
然后发现仍然是可以数位 dp 的, 就是枚举 \(1-9\), 算有 \(i\)个数位大于等于它的数的一次和 (我还算了零次和, 便于转移) 是多少, 把之前的 \(b=2\)的暴力改改就行了...
- Code?
- //50 pts dp(b=2)+ 暴力
- #include<bits/stdc++.h>
- #define ll long long
- #define db double
- #define reg register
- #define dbg1(x) cerr<<#x<<"="<<(x)<<" "
- #define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"
- #define dbg3(x) cerr<<#x<<"\n"
- using namespace std;
- inline int read()
- {
- int x=0,f=1;char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
- return x*f;
- }
- const int P=998244353;
- int Mul(int x,int y){return 1ll*x*y%P;}
- int Add(int x,int y){return (x+y)%P;}
- int T,b,len[25];
- char n[25][1005];
- namespace solve1
- {
- int f[100005];
- int to_int(char *s,int L)
- {
- int r=0;
- for(int i=0;i<L;++i) r=r*b+(s[i]-'0');
- return r;
- }
- int cal(int i)
- {
- char tmp[40];int L=-1;
- while(i) tmp[++L]='0'+(i%b),i/=b;++L;
- std::sort(tmp,tmp+L);
- return to_int(tmp,L);
- }
- void Main()
- {
- for(int i=1;i<=100000;++i) f[i]=Add(f[i-1],Mul(i,cal(i)));
- for(int i=1;i<=T;++i) printf("%d\n",f[to_int(n[i],len[i])]);
- }
- }
- namespace solve2
- {
- char s[1005];
- int L,g[1005][1005],f[1005][1005],g2[1005][1005],f2[1005][1005];
- void Main()
- {
- for(int o=1;o<=T;++o)
- {
- reg int i,j;
- scanf("%s",s);L=strlen(s);
- memset(g,0,sizeof g);
- memset(f,0,sizeof f);
- memset(g2,0,sizeof g2);
- memset(f2,0,sizeof f2);
- f[L-1][0]=f[L-1][1]=g[L-1][0]=1;
- f2[L-1][1]=1;
- if(s[L-1]=='1') g[L-1][1]=1,g2[L-1][1]=1;
- int _=1;
- for(i=L-2;~i;--i)
- {
- _=Mul(_,2);
- f[i][0]=f[i+1][0];
- for(j=1;j<=L-i;++j) f[i][j]=Add(f[i+1][j-1],f[i+1][j]);
- for(j=1;j<=L-i;++j) f2[i][j]=Add(Add(f2[i+1][j-1],Mul(_,f[i+1][j-1])),f2[i+1][j]);
- g[i][0]=g[i+1][0];
- for(j=1;j<=L-i;++j)
- {
- if(s[i]=='1') g[i][j]=Add(g[i+1][j-1],f[i+1][j]),
- g2[i][j]=Add(Add(g2[i+1][j-1],Mul(_,g[i+1][j-1])),f2[i+1][j]);
- else g[i][j]=g[i+1][j],g2[i][j]=g2[i+1][j];
- }
- }
- int nm=1,ans=0;
- for(i=1;i<=L;++i,nm=Add(1,Mul(nm,2))) ans=Add(ans,Mul(nm,g2[0][i]));
- printf("%d\n",ans);
- }
- }
- }
- int main()
- {
- #ifndef LOCAL
- freopen("libreoj.in","r",stdin);
- freopen("libreoj.out","w",stdout);
- #endif
- T=read(),b=read();int ml=0,i;
- if(b==2) {solve2::Main();return 0;}
- for(i=1;i<=T;++i) scanf("%s",n[i]),ml=max(ml,len[i]=strlen(n[i]));
- if(len[i]<=40) solve1::Main();
- return 0;
- }
- #include<bits/stdc++.h>
- #define ll long long
- #define db double
- #define reg register
- #define dbg1(x) cerr<<#x<<"="<<(x)<<" "
- #define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"
- #define dbg3(x) cerr<<#x<<"\n"
- using namespace std;
- inline int read()
- {
- int x=0,f=1;char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
- return x*f;
- }
- const int P=998244353;
- int Mul(int x,int y){return 1ll*x*y%P;}
- int Add(int x,int y){return (x+y)%P;}
- int T,b;
- namespace solve3
- {
- char s[1005];
- int L,g[1005][1005],f[1005][1005],g2[1005][1005],f2[1005][1005];
- int nm[1005],ans;
- int cal(int l,int r){return (l+r)*(r-l+1)/2;}
- void Main()
- {
- reg int i,j,_;
- for(_=1,j=1;j<=1000;++j,_=Add(1,Mul(_,b)))nm[j]=_;
- for(int o=1;o<=T;++o)
- {
- ans=0;
- scanf("%s",s);L=strlen(s);
- for(int d=1;d<b;++d)
- {
- memset(g,0,sizeof g);memset(f,0,sizeof f);memset(g2,0,sizeof g2);memset(f2,0,sizeof f2);
- f[L-1][0]=d;f2[L-1][0]=cal(0,d-1);g[L-1][0]=min(s[L-1]-'0',d-1)+1;g2[L-1][0]=cal(0,min(s[L-1]-'0',d-1));
- f[L-1][1]=b-d;f2[L-1][1]=cal(d,b-1);if(s[L-1]-'0'>=d) g[L-1][1]=s[L-1]-'0'+1-d,g2[L-1][1]=cal(d,s[L-1]-'0');
- for(_=1,i=L-2;~i;--i)
- {
- _=Mul(_,b);f[i][0]=Mul(f[i+1][0],d);f2[i][0]=Add(Mul(d,f2[i+1][0]),Mul(cal(0,d-1),Mul(_,f[i+1][0])));
- for(j=1;j<=L-i;++j) f[i][j]=Add(Mul(b-d,f[i+1][j-1]),Mul(d,f[i+1][j]));
- for(j=1;j<=L-i;++j) f2[i][j]=Add(Add(Mul(b-d,f2[i+1][j-1]),Mul(cal(d,b-1),Mul(_,f[i+1][j-1]))),
- Add(Mul(d,f2[i+1][j]),Mul(cal(0,d-1),Mul(_,f[i+1][j]))));
- if(s[i]-'0'>=d)
- {
- g[i][0]=Mul(d,f[i+1][0]);
- g2[i][0]=Add(Mul(d,f2[i+1][0]),Mul(cal(0,d-1),Mul(_,f[i+1][0])));
- }
- else
- {
- g[i][0]=g[i+1][0],g2[i][0]=Add(g2[i+1][0],Mul(s[i]-'0',Mul(_,g[i+1][0])));
- if(s[i]>'0') g[i][0]=Add(g[i][0],Mul(f[i+1][0],s[i]-'1'+1)),
- g2[i][0]=Add(g2[i][0],Add(Mul(s[i]-'0',f2[i+1][0]),Mul(cal(0,s[i]-'1'),Mul(_,f[i+1][0]))));
- }
- for(j=1;j<=L-i;++j)
- {
- if(s[i]-'0'>=d)
- {
- g[i][j]=Add(g[i+1][j-1],Mul(d,f[i+1][j]));
- g2[i][j]=Add(Add(g2[i+1][j-1],Mul(s[i]-'0',Mul(_,g[i+1][j-1]))),
- Add(Mul(d,f2[i+1][j]),Mul(cal(0,d-1),Mul(_,f[i+1][j]))));
- if(s[i]-'1'>=d) g[i][j]=Add(g[i][j],Mul(s[i]-'1'+1-d,f[i+1][j-1])),
- g2[i][j]=Add(g2[i][j],Add(Mul(s[i]-'0'-d,f2[i+1][j-1]),Mul(cal(d,s[i]-'1'),Mul(_,f[i+1][j-1]))));
- }
- else
- {
- g[i][j]=g[i+1][j],g2[i][j]=Add(g2[i+1][j],Mul(s[i]-'0',Mul(_,g[i+1][j])));
- if(s[i]>'0') g[i][j]=Add(g[i][j],Mul(f[i+1][j],s[i]-'1'+1)),
- g2[i][j]=Add(g2[i][j],Add(Mul(f2[i+1][j],s[i]-'0'),Mul(cal(0,s[i]-'1'),Mul(_,f[i+1][j]))));
- }
- }
- }
- for(i=1;i<=L;++i)ans=Add(ans,Mul(g2[0][i],nm[i]));
- }
- printf("%d\n",ans);
- }
- }
- }
- int main()
- {
- #ifndef LOCAL
- freopen("libreoj.in","r",stdin);
- freopen("libreoj.out","w",stdout);
- #endif
- T=read(),b=read();int ml=0,i;
- solve3::Main();
- return 0;
- }
T3. 一键挖矿 (veinminer)
传送门 http://218.5.5.242:9019/contest/13/problem/3
Description
求一个矩阵 (其中的数是个排列) 中有多少的子矩阵 \(S\)满足 \(max_S-min_S=siz_S\)
也就是矩阵中的数恰好是连续的一段数
Solution?
这里有坑
- Code?
- // 大暴力 30pts
- #include<bits/stdc++.h>
- #define ll long long
- #define db double
- #define reg register
- #define dbg1(x) cerr<<#x<<"="<<" "
- #define dbg2(x) cerr<<#x<<"="<<"\n"
- #define dbg3(x) cerr<<#x<<"\n"
- using namespace std;
- inline int read()
- {
- int x=0,f=1;char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
- return x*f;
- }
- int n,m;
- ll ans;
- namespace solve1
- {
- int a[2005];
- void Main()
- {
- reg int i,j,mi,ma;
- for(i=1;i<=m;++i) a[i]=read();
- for(i=1;i<=m;++i)
- for(mi=ma=a[i],j=i;j<=m;++j)
- {
- mi=min(mi,a[j]);
- ma=max(ma,a[j]);
- if(ma-mi+1==j-i+1) ++ans;
- }
- }
- }
- namespace solve2
- {
- int a[105][105],Mi[105][105][105],Ma[105][105][105];
- void Main()
- {
- reg int i,j,k,l,mi,ma;
- for(i=1;i<=n;++i)for(j=1;j<=m;++j)a[i][j]=read();
- for(l=1;l<=n;++l)
- {
- for(i=1;i<=m;++i)
- for(mi=ma=a[l][i],j=i;j<=m;++j)
- {
- mi=min(mi,a[l][j]);
- ma=max(ma,a[l][j]);
- Mi[l][i][j]=mi;
- Ma[l][i][j]=ma;
- }
- }
- for(l=1;l<=n;++l)for(k=1;k<=m;++k)
- for(j=k;j<=m;++j)for(ma=0,mi=10001,i=l;i<=n;++i)
- {
- mi=min(mi,Mi[i][k][j]);
- ma=max(ma,Ma[i][k][j]);
- if(ma-mi+1==(i-l+1)*(j-k+1)) ++ans;
- }
- }
- }
- int main()
- {
- #ifndef LOCAL
- freopen("veinminer.in","r",stdin);
- freopen("veinminer.out","w",stdout);
- #endif
- n=read(),m=read();
- if(n==1&&m<=2000) solve1::Main();
- else if(n<=100&&m<=100) solve2::Main();
- else
- {
- for(int i=1;i<=n*m;++i) read();
- ll lin=1ll*n*1ll*m*1ll*(m+1)/2;
- ll row=1ll*n*1ll*(n-1)/2;
- ans=lin+row;
- }
- return 0*printf("%lld\n",ans);
- }
- gugugu
- gugugugugugu
- gugugugugugugugugu
- gugugugugugugugugugugugu
- ......
Blog 来自 PaperCloud, 未经允许, 请勿转载, TKS!
来源: http://www.bubuko.com/infodetail-3156029.html