A:
/* 画图研究可得大部分情况都是走一个矩形 但是要考虑特殊情况 1 只有下方有点 1.1 点在s一侧：找距离s最近的，且能包含所有点的特殊点 1.2 点在s两侧：找距离最小的能把所有的点包起来的两个特殊点 2 两侧都有点(只有上方有点和这个情况一样) 2.1 点在s一侧：找最小的能把距离s远的那一侧全包围且能把距离s近的这一侧的上面包围的矩形 2.2 点在s两侧：找一个最小的四个点是特殊点的矩形 */ #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define maxn 110 using namespace std; int n,r,m,k,s,mxa,mxb,mia,mib,p[maxn],ans,A,B; int main(){ scanf("%d%d%d%d%d",&n,&r,&m,&k,&s); int x,y;mia=mib=1e7; for(int i=1;i<=r;i++){ scanf("%d%d",&x,&y); if(x<s)A=1;if(x>s)B=1; if(y)mxb=max(mxb,x),mib=min(mib,x); else mxa=max(mxa,x),mia=min(mia,x); } for(int i=1;i<=m;i++)scanf("%d",&p[i]); p[++m]=1;p[++m]=n;sort(p+1,p+1+m); if(A+B==0){ printf("0 ");return 0; } if(A+B!=2){ if(mxb==0){ if(A){ for(int i=m;i>=1;i--) if(p[i]<=mia){ ans=(s-p[i])*2;break; } printf("%d ",ans); } else { for(int i=1;i<=m;i++) if(p[i]>=mxa){ ans=(p[i]-s)*2;break; } printf("%d ",ans); } } else { if(A){ for(int i=1;i<=m;i++) if(p[i]>=mxb){ if(s>p[i])ans+=(s-p[i])*2; ans-=(n-p[i])*2;break; } for(int i=m;i>=1;i--) if(p[i]<=mia&&p[i]<=mib){ ans-=(p[i]-1)*2;break; } ans+=k*2+(n-1)*2;printf("%d ",ans); } else{ for(int i=1;i<=m;i++) if(p[i]>=mxa&&p[i]>=mxb){ ans-=(n-p[i])*2;break; } for(int i=m;i>=1;i--) if(p[i]<=mib){ if(s<p[i])ans+=(p[i]-s)*2; ans-=(p[i]-1)*2;break; } ans+=k*2+(n-1)*2;printf("%d ",ans); } } return 0; } for(int i=1;i<=m;i++) if(p[i]>=mxa&&p[i]>=mxb){ ans-=(n-p[i])*2;break; } for(int i=m;i>=1;i--) if(p[i]<=mia&&p[i]<=mib){ ans-=(p[i]-1)*2;break; } if(mxb)ans+=k*2;ans+=(n-1)*2; printf("%d ",ans);return 0; }
B:
/* 这题一开始思路被带到了bfs上 状态是f[x][y][t][c]第t秒到了(x,y)有了c个糖果 然后走 考虑复杂度c为1018,t最多1018*10 10*10*1018*10*1018 有点凉 考虑到很多走法是很傻逼的 需要有决策 那就把状态直接拿到dp上 去掉第四维,f[x][y][t]为最多的糖果数 t决定更新的先后 然后可以滚一下数组 至于div1 1e18的做法 好像是有循环节来着 */ #include<cstdio> #include<cstring> #include<iostream> #define maxn 11 using namespace std; int n,m,C,sx,sy,ex,ey,a[maxn][maxn][2],T[maxn][maxn]; int main(){ scanf("%d%d%d",&n,&m,&C); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&T[i][j]); scanf("%d%d%d%d",&sx,&sy,&ex,&ey); memset(a,-127/3,sizeof(a)); a[sx][sy][0]=0; for(int k=1;;k++){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(k%T[i][j]==0){ a[i][j][k%2]=a[i][j][(k+1)%2]+1; if(i-1>=1)a[i][j][k%2]=max(a[i][j][k%2],a[i-1][j][(k+1)%2]+1); if(j-1>=1)a[i][j][k%2]=max(a[i][j][k%2],a[i][j-1][(k+1)%2]+1); if(i+1<=n)a[i][j][k%2]=max(a[i][j][k%2],a[i+1][j][(k+1)%2]+1); if(j+1<=m)a[i][j][k%2]=max(a[i][j][k%2],a[i][j+1][(k+1)%2]+1); } else { a[i][j][k%2]=a[i][j][(k+1)%2]; if(i-1>=1)a[i][j][k%2]=max(a[i][j][k%2],a[i-1][j][(k+1)%2]); if(j-1>=1)a[i][j][k%2]=max(a[i][j][k%2],a[i][j-1][(k+1)%2]); if(i+1<=n)a[i][j][k%2]=max(a[i][j][k%2],a[i+1][j][(k+1)%2]); if(j+1<=m)a[i][j][k%2]=max(a[i][j][k%2],a[i][j+1][(k+1)%2]); } } if(a[ex][ey][k%2]>=C){ printf("%d ",k);break; } } return 0; }
E：
/* f[i][0/1]表示i为根的子树 且i选没选的max */ #include<cstdio> #include<cstring> #include<iostream> #define maxn 1010 using namespace std; int n,f[maxn],d[maxn],num,head[maxn],dp[maxn][2],fa[maxn]; struct node{ int v,pre; }e[maxn*2]; void Add(int from,int to){ num++;e[num].v=to; e[num].pre=head[from]; head[from]=num; } int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); } void Dfs(int now,int from){ dp[now][0]=0;dp[now][1]=f[now]; for(int i=head[now];i;i=e[i].pre){ int v=e[i].v;if(v==from)continue; Dfs(v,now);dp[now][0]+=max(dp[v][0],dp[v][1]); dp[now][1]+=max(dp[v][0],dp[v][1]-d[min(now,v)]); } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&f[i]); for(int i=1;i<=n;i++)scanf("%d",&d[i]); for(int i=1;i<=n;i++)fa[i]=i; for(int i=2;i<=n;i++){ if(i%2==1){ if(i*3+1>n)continue; Add(i,i*3+1);Add(i*3+1,i); fa[find(i)]=find(i*3+1); } else { Add(i,i/2);Add(i/2,i); fa[find(i)]=find(i/2); } } for(int i=1;i<=n;i++) if(find(i)==i)Add(0,i); Dfs(0,-1);printf("%d ",max(dp[0][0],dp[0][1])); return 0; }
F:
/* 回家好颓啊,不行啊赶紧发发博客监督自己 day1 F 关键 上升体力-- 下降体力++ 这样子的话,如果初始体力为x 则任何海拔不超过x的山都能到 如果整张图没有海拔>x的山 因为下降山需要的花费是l*l 那么显然不降最优 即裸地最短路 现在考虑不好的山v 从u->v的新的花费就是dis[u][v]+(h[v]-x)^2 由于上面的证明,就是-x不是-h[u] 另外出题人说没卡spfa是因为他那个年代不卡 也就是说现在写比较危险 而我比较喜欢写spfa 所以以后还是写dij吧 还有别忘了longlong.... */ #include<cstdio> #include<cstring> #include<iostream> #include<queue> #define maxn 200010 #define ll long long using namespace std; ll n,m,K,num,head[maxn],h[maxn],dis[maxn],f[maxn]; struct node{ ll v,t,pre; }e[maxn*2];queue<ll>q; void Add(ll from,ll to,ll dis){ num++;e[num].t=dis; e[num].v=to; e[num].pre=head[from]; head[from]=num; } void SPFA(){ memset(dis,127/3,sizeof(dis)); dis[1]=0;ll lim=h[1]+K; q.push(1);f[1]=1;while(!q.empty()){ ll k=q.front();q.pop();f[k]=0; for(ll i=head[k];i;i=e[i].pre){ ll v=e[i].v,r=0; if(h[v]>lim)r=(h[v]-lim)*(h[v]-lim); if(dis[v]>dis[k]+e[i].t+r){ dis[v]=dis[k]+e[i].t+r; if(f[v]==0){ f[v]=1;q.push(v); } } } } } int main(){ scanf("%lld%lld%lld",&n,&m,&K); for(ll i=1;i<=n;i++) scanf("%lld",&h[i]); ll u,v,t; for(ll i=1;i<=m;i++){ scanf("%lld%lld%lld",&u,&v,&t); Add(u,v,t);Add(v,u,t); } SPFA();printf("%lld ",dis[n]); return 0; }
G：
/* 首先答案矩阵包含的范围要么很大要么很小 很大的情况特判一下： 1.能包含所有：一个小矩形的所有数gcd>1 2.横着贯穿：枚举上下界 3.竖着贯穿：枚举左右界 小的情况就是在2*2的四个矩阵里找 枚举上下边界 转化成一维的问题 rmq预处理 区间gcd 然后尺取 n*n*n*logn */ #include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<ctime> #define maxn 210 #define ll long long using namespace std; int n,m,g[maxn][maxn],mx,a[maxn],f[maxn][20],p[maxn]; int A[maxn][maxn][20],B[maxn][maxn][20];ll ans,x,y; int gcd(int x,int y){ if(y==0)return x; return x==0?y:gcd(y,x%y); } int pre(){ for(int i=0;i<=10;i++) if((1<<i)<=200)p[1<<i]=i; for(int i=1;i<=200;i++) if(!p[i])p[i]=p[i-1]; for(int i=1;i<=n*2;i++){ for(int j=1;j<=m*2;j++)A[i][j][0]=g[i][j]; for(int k=1;k<=10;k++) for(int j=1;j+(1<<k-1)<=m*2;j++) A[i][j][k]=gcd(A[i][j][k-1],A[i][j+(1<<k-1)][k-1]); } for(int j=1;j<=m*2;j++){ for(int i=1;i<=n*2;i++)B[i][j][0]=g[i][j]; for(int k=1;k<=10;k++) for(int i=1;i+(1<<k-1)<=n*2;i++) B[i][j][k]=gcd(B[i][j][k-1],B[i+(1<<k-1)][j][k-1]); } } int Query(int l,int r){ if(l>r)return 0;int k=p[r-l+1]; return gcd(f[l][k],f[r-(1<<k)+1][k]); } int Query1(int l,int r,int t){ if(l>r)return 0;int k=p[r-l+1]; return gcd(B[l][t][k],B[r-(1<<k)+1][t][k]); } int Query2(int l,int r,int t){ if(l>r)return 0;int k=p[r-l+1]; return gcd(A[t][l][k],A[t][r-(1<<k)+1][k]); } ll Solve(int up,int down){ int N=m*2; for(int j=1;j<=N;j++) a[j]=Query1(up,down,j); for(int i=1;i<=N;i++)f[i][0]=a[i]; for(int j=1;j<=10;j++) for(int i=1;i+(1<<j-1)<=N;i++) f[i][j]=gcd(f[i][j-1],f[i+(1<<j-1)][j-1]); int l=1,r=1,now=a[1],ans=0; for(;l<=N&&r<=N;l++){ if(l>r)r=l; while(now=gcd(now,a[r])>1&&r<=N)r++; ans=max(ans,r-l); now=Query(l+1,r); } return ans*(down-up+1); } int Solve1(int up,int down){ int N=m*2; for(int j=1;j<=N;j++) a[j]=Query1(up,down,j); for(int i=1;i<=N;i++)f[i][0]=a[i]; for(int j=1;j<=10;j++) for(int i=1;i+(1<<j-1)<=N;i++) f[i][j]=gcd(f[i][j-1],f[i+(1<<j-1)][j-1]); int l=1,r=1,now=a[1],ans=0; for(;l<=N&&r<=N;l++){ if(l>r)r=l; while(now=gcd(now,a[r])>1&&r<=N)r++; ans=max(ans,r-l); now=Query(l+1,r); } return ans; } int Solve2(int lef,int rig){ int N=n*2; for(int i=1;i<=N;i++) a[i]=Query2(lef,rig,i); for(int i=1;i<=N;i++)f[i][0]=a[i]; for(int j=1;j<=10;j++) for(int i=1;i+(1<<j-1)<=N;i++) f[i][j]=gcd(f[i][j-1],f[i+(1<<j-1)][j-1]); int l=1,r=1,now=a[1],ans=0; for(;l<=N&&r<=N;l++){ if(l>r)r=l; while(now=gcd(now,a[r])>1&&r<=N)r++; ans=max(ans,r-l); now=Query(l+1,r); } return ans; } int main(){ //srand(time(0)); scanf("%d%d%lld%lld",&n,&m,&x,&y); //n=100;m=100;x=1000;y=1000; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) //g[i][j]=rand()%100000; scanf("%d",&g[i][j]); int now=0,mx; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) now=gcd(now,g[i][j]); if(now>1){ printf("%lld ",n*m*x*y);return 0; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) g[i+n][j]=g[i][j+m]=g[i+n][j+m]=g[i][j]; pre(); mx=0;for(int i=1;i<=n*2;i++) for(int j=i;j<=n*2;j++) if(j-i+1>mx&&Solve1(i,j)==m*2) mx=max(mx,j-i+1); ans=max(ans,mx*m*y); //printf("%d ",clock()); mx=0;for(int i=1;i<=m*2;i++) for(int j=i;j<=m*2;j++) if(j-i+1>mx&&Solve2(i,j)==n*2) mx=max(mx,j-i+1); ans=max(ans,mx*n*x); //printf("%d ",clock()); for(int i=1;i<=n*2;i++) for(int j=i;j<=n*2;j++) ans=max(Solve(i,j),ans); //printf("%d ",clock()); printf("%lld ",ans); return 0; }
I：
/* 简单的dp f[i][j][k]表示以第i个为结尾 上一个选的是p[j] k==0表示i为子序列的偶数位 1为奇数位 转移就是 枚举上次在哪里选的 然后前缀后缀和优化一下 */ #include<cstdio> #include<cstring> #include<iostream> #define maxn 2010 #define mod 1000000007 #define ll long long using namespace std; ll n,p[maxn],f[maxn][maxn][2],s[maxn][maxn][2],t[maxn][maxn][2],ans; int main(){ scanf("%lld",&n); for(ll i=1;i<=n;i++)scanf("%lld",&p[i]); for(ll i=1;i<=n;i++) for(ll j=1;j<i;j++) if(p[j]>p[i])f[i][p[j]][0]++; for(ll i=1;i<=n;i++){ for(ll j=1;j<=n;j++) s[i][j][0]=s[i][j-1][0]+f[i][j][0]; for(ll j=n;j>=1;j--) t[i][j][0]=t[i][j+1][0]+f[i][j][0]; } for(ll i=1;i<=n;i++){ for(ll j=1;j<i;j++){ if(p[i]>p[j]){ f[i][p[j]][1]+=t[j][p[i]+1][0];f[i][p[j]][1]%=mod; } if(p[j]>p[i]){ f[i][p[j]][0]+=s[j][p[j]-1][1];f[i][p[j]][0]%=mod; } } for(ll j=1;j<=n;j++){ s[i][j][0]=s[i][j-1][0]+f[i][j][0];s[i][j][0]%=mod; s[i][j][1]=s[i][j-1][1]+f[i][j][1];s[i][j][1]%=mod; } for(ll j=n;j>=1;j--){ t[i][j][0]=t[i][j+1][0]+f[i][j][0];t[i][j][0]%=mod; t[i][j][1]=t[i][j+1][1]+f[i][j][1];t[i][j][1]%=mod; } } for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++){ ans+=f[i][j][1];ans%=mod; } printf("%lld ",ans);return 0; }