这套题真的有点传奇了，考了两次。虽然银川赛区名声不行，但这套题质量还是过硬的，所以来补一下，还是收获颇丰。
A. Maximum Element In A Stack
题意
实现一个支持查询当前栈中元素的最大值的栈。
题解
最大栈的模板题，相当于在原始栈的基础上再开一个栈存前缀最大值，pop操作与原栈同步就好。
代码
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
int n,p,q,m;
unsigned int SA,SB,SC;
unsigned int rng61(){
SA^=SA<<16;
SA^=SA>>5;
SA^=SA<<1;
unsigned int t=SA;SA=SB;
SB=SC;
SC^=t^SA;
return SC;
}
stack
void push(int x){
if(!ms.empty()) ms.push(max(x,ms.top()));
else ms.push(x);
sta.push(x);
}
void pop(){
if(!ms.empty()) ms.pop(),sta.pop();
}
void solve(int Case){
while(!ms.empty()) sta.pop(),ms.pop();
scanf("%d%d%d%d%u%u%u",&n,&p,&q,&m,&SA,&SB,&SC);
LL ans=0;
for(int i=1;i<=n;i++){
if(rng61()%(p+q) else pop(); if(!ms.empty()) ans^=1ll*ms.top()*i; } printf("Case #%d: %lld\n",Case,ans); } int main(){ int T;scanf("%d",&T); for(int i=1;i<=T;i++) solve(i); return 0; } B. Rolling The Polygon 题意 给你一个多边形，沿逆时针滚一圈，要求多边形中某一点的运动路程。 题解 其实可以发现多边形沿一个角滚一下，这个点的轨迹是一个以该点到滚动角的距离为半径，滚动角的补角为角度的扇形，可以直接把这个距离算出来。 代码 #include #include #include #include #include using namespace std; int n; double x[55],y[55],ag[55],dis[55]; double calc(int i,int j){ double res=(x[i]-x[j])*(x[i]-x[j]); res+=(y[i]-y[j])*(y[i]-y[j]); return sqrt(res); } double calcangle(int i,int j,int k){ double res=x[i]*y[j]+x[j]*y[k]+x[k]*y[i]-y[j]*x[k]-y[i]*x[j]-y[k]*x[i]; double a=calc(i,j),b=calc(k,j),c=calc(i,k); res/=a*b; res=asin(res); if(c*c>b*b+a*a) return res; else return 3.1415926525-res; } void solve(int Case){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]); scanf("%lf%lf",&x[0],&y[0]); double ans=0; for(int i=1,a=i-1,b=i,c=i+1;i<=n;i++,a--,b--,c--){ if(a<1) a+=n;if(b<1) b+=n;if(c<1) c+=n; ag[i]=calcangle(a,b,c); dis[i]=calc(0,b); //printf("(%.0lf,%.0lf),(%.0lf,%.0lf),(%.0lf,%.0lf) angle=%lf dis=%lf\n",x[a],y[a],x[b],y[b],x[c],y[c],ag[i],dis[i]); ans+=ag[i]*dis[i]; } printf("Case #%d: %.3lf\n",Case,ans); } int main(){ int T;scanf("%d",&T); for(int i=1;i<=T;i++) solve(i); return 0; } C. Caesar Cipher 本场白给题 #include #include #include #include using namespace std; int n,m; char s1[55],s2[55],t[55]; void solve(int Case){ scanf("%d%d",&n,&m); scanf("%s%s%s",s1+1,s2+1,t+1); int sub=s1[1]-s2[1]; for(int i=1;i<=m;i++) t[i]=(t[i]-'A'+sub+26)%26+'A'; printf("Case #%d: %s\n",Case,t+1); } int main(){ int T;scanf("%d",&T); for(int i=1;i<=T;i++) solve(i); return 0; } D. Take Your Seat 题意 杜华是个疯子，有一天他去坐飞机，轮到他上机时，他会从没有人的位置中随机选择一个位置坐下。如果其他乘客发现自己位置被人占之后，他也会疯掉，从没有人的位置中随机选择一个坐下。那么问题来了： 1.共有 \(n\) 个乘客，编号 \(1,2,...,n\)，对应座位号 \(1,2,...,n\)，依次登机，杜华是 \(1\) 号乘客，问第 \(n\) 位乘客能做 \(n\) 号位置的概率。 2.共有 \(m\) 个乘客，编号 \(1,2,...,m\)，对应座位号 \(1,2,...,m\)，随机顺序登机，问最后一个登机的乘客能坐到自己对应位置上的概率。 题解 概率杀我。 先看第一个问题： 如果杜华坐了 \(1\) 号，那么此时概率 \(=1\) 。 如果杜华坐了 \(i(1 如果杜华坐了 \(n\) 号，当然概率直接为 \(0\)。 那么如果设该问题的概率为 \(f[n]\)，可知 \(f[n]=\frac{1+f[n-1]+f[n-2]+...+f[2]}{n}\) ，那这时就可以计算了，其实手算一下，可以发现 \(f[n]=\frac{1}{2}\)。 再来看第二个问题，可以发现： 如果杜华是第 \(i\) 个登机的人，那么这个问题就相当于规模为 \(m-i+1\) 的一问题。 那么设二问题概率为 \(g[m]\)，可得 \(g[m]=\frac{f[m]+f[m-1]+...+f[1]}{m}\)。 代码 #include #include #include #include using namespace std; double f[55],g[55]; void solve(int Case){ int n,m; scanf("%d%d",&n,&m); printf("Case #%d: %.6lf %.6lf\n",Case,f[n],g[m]); } int main(){ f[1]=g[1]=1; double sum=0; for(int i=2;i<=50;i++){ sum+=f[i-1]; f[i]=sum/i; g[i]=(sum+f[i])/i; } int T;scanf("%d",&T); for(int i=1;i<=T;i++) solve(i); return 0; } E. 2-3-4 Tree 题意 给出234树的形态和插入方法，然后依次插入一个 \(n\) 的全排列，要求输出最后234树的前序遍历。 如果总共加入234树的值不超过 \(3\) 个，那么这棵树显然只有根节点一个点。否则从根节点开始按一下规律插入值： 1.如果当前节点是一个 '4节点'： 将这个节点中间的值拿出来，左右两边的值和四个儿子构成两个 '2节点'。 如果原 '4节点' 是根节点，那么把中间值重新构成一个根节点，让新生成的两个 '2节点' 成为它的儿子。 否则把中间值插入原 '4节点' 的父节点，新生成的两个 '2节点' 成为原 '4节点' 父节点的儿子。 2.如果当前节点是叶节点了，那么直接将值加入当前节点中，插入完成。 3.否则： 寻找值属于当前节点的哪个子节点。 进入子节点继续从第 \(1\) 步开始判断。 题解 有点变态的数据结构模拟题啊……读懂题都要下一番功夫。 其实构造这个234树的难点就在于对 '4节点' 的调整。我们来考虑一下： 1.如果当前节点为 '4节点' 并且当前节点是根节点： 新建一个节点，将右值存入，它的1儿子为原4节点的3儿子，2儿子为原4节点的4儿子。 再新建一个节点，将中值存入，它的1儿子为原4节点，2儿子为刚刚新建的节点。指定它为新的根节点。 设定这 \(3\) 个点的大小信息，分配儿子时也不要忘记重新定向儿子的父亲。 2.如果当前节点为 '4节点' 并且当前节点不是根节点： 新建一个节点，将右值存入，它的1儿子为原4节点的3儿子，2儿子为原4节点的4儿子。 将中值加入原4节点的父节点。让新建的节点成为原4节点的父节点的又一个儿子。 调整节点信息，并对父节点中的值排序，对父节点的所有儿子进行排序。 3.经过调整之后，从父节点开始，寻找应该插入哪颗子树。注意这时如果父节点是 '4节点'，也不调整了。 如果是不需要调整的节点，那就很好找了。 要注意的点：往一个节点中插入值之后，一定要排序。向一个节点加入了儿子，也要对它所有儿子排序；加入儿子同时也要将儿子的父亲指针指向父节点。 代码 #include #include #include #include #include using namespace std; const int N=5010; int n; bool cmp(int x,int y); struct _234Tree{ int data[N][3],siz[N],tr[N][4],fa[N],rt,tot; void init(){ memset(data,0,sizeof(data)); memset(tr,0,sizeof(tr)); memset(fa,0,sizeof(fa)); memset(siz,0,sizeof(siz)); rt=tot=0; } void insert(int id,int val){ if(siz[id]==3){ if(id==rt){ rt=++tot;int rs=++tot; data[rt][0]=data[id][1],siz[rt]=1,tr[rt][0]=id,tr[rt][1]=rs; data[rs][0]=data[id][2],siz[rs]=1,tr[rs][0]=tr[id][2],tr[rs][1]=tr[id][3];fa[rs]=rt; fa[tr[id][2]]=rs;fa[tr[id][3]]=rs; siz[id]=1;fa[id]=rt; } else{ int par=fa[id],rs=++tot; data[par][siz[par]++]=data[id][1],tr[par][siz[par]]=rs; data[rs][0]=data[id][2],siz[rs]=1,tr[rs][0]=tr[id][2],tr[rs][1]=tr[id][3];fa[rs]=par; fa[tr[id][2]]=rs;fa[tr[id][3]]=rs; siz[id]=1; sort(data[par],data[par]+siz[par]); sort(tr[par],tr[par]+siz[par]+1,cmp); } int par=fa[id]; if(val else if(siz[par]==1||val else if(siz[par]==2||val else insert(tr[par][3],val); return; } if(!tr[id][0]){ data[id][siz[id]++]=val; sort(data[id],data[id]+siz[id]); return; } if(val else if(siz[id]==1||val else if(siz[id]==2||val } void dfs(int id){ if(!id) return; for(int i=0;i for(int i=0;i<=siz[id];i++) dfs(tr[id][i]); } }_234; bool cmp(int x,int y){ return _234.data[x][0]<_234.data[y][0]; } void solve(int Case){ printf("Case #%d:\n",Case); _234.init(); scanf("%d",&n); int x; scanf("%d",&x); _234.rt=_234.tot=1; _234.data[1][0]=x; _234.siz[1]=1; for(int i=2;i<=n;i++){ scanf("%d",&x); _234.insert(_234.rt,x); } _234.dfs(_234.rt); } int main(){ int T;scanf("%d",&T); for(int i=1;i<=T;i++) solve(i); return 0; } F. Moving On 题意 有一个点权边权图，多组询问，问从 \(u\) 到 \(v\) 经过的点点权不超过 \(w\) 的路径的最小值。 题解 如果熟悉floyd最短路的话，这道题还是很简单的。 首先从 \(n\) 的范来说，可以肯定用floyd。 然后可以将询问离线，按 \(w\) 排序，把所有点也按点权排序。 双指针，如果当前询问的 \(w\) 大于已经处理的点的点权，尝试继续处理之后的点。 代码 #include #include #include #include #include #define ff first #define ss second using namespace std; typedef long long LL; typedef pair const int N=2e5+10; int n,m,ans[N]; int g[210][210]; PII p[210]; struct Qure{ int u,v,w,id; }q[N]; bool cmp(Qure a,Qure b){return a.w void solve(int Case){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&p[i].ff),p[i].ss=i; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&g[i][j]); for(int i=1;i<=m;i++) scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w),q[i].id=i; sort(p+1,p+n+1); sort(q+1,q+m+1,cmp); for(int i=1,j=0;i<=m;i++){ while(j int k=p[++j].ss; for(int u=1;u<=n;u++) for(int v=1;v<=n;v++) g[u][v]=min(g[u][v],g[u][k]+g[k][v]); } ans[q[i].id]=g[q[i].u][q[i].v]; } printf("Case #%d:\n",Case); for(int i=1;i<=m;i++) printf("%d\n",ans[i]); } int main(){ int T;scanf("%d",&T); for(int i=1;i<=T;i++) solve(i); return 0; } G. Factories 题意 给一颗树，要求你从选 \(k\) 个叶节点，使得这 \(k\) 个叶节点各自之间的距离之和最短。 题解 这是个树形背包的板子题。 如果从以 \(v\) 为根节点的子树中选定了 \(i\) 个节点，那么在所有 \(\frac{k\times(k-1)}{2}\) 条路径中，边 \(v-fa_v\) 被经过了 \(i\times (k-i)\) 次，所以可以推出方程： \[f[u][i]=min\big(f[u][i],f[u][i-j]+f[v][j]+w_{uv}\times j\times (k-j)\big) \] 当然要注意，要用额外的数组来存 \(f[u][i]\)，统计玩一颗子树之后再付给 \(f[u][i]\)，这不是为了加快速度，而是为了避免重复统计同一颗子树中的信息。 这里我想起了 CCF 某次的第 5 题，我好像就是没用开另外的数组，导致只有 70 分。 代码 #include #include #include #include #include #define ff first #define ss second using namespace std; typedef long long LL; typedef pair const int N=1e5+10; const int inf=0x3f3f3f3f; const LL INF=0x3f3f3f3f3f3f3f3f; int n,k,cnt[N],d[N]; LL f[N][110],tmp[110]; int head[N],to[N*2],val[N*2],nxt[N*2],tot; int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();} return x*f; } void add(int u,int v,int w){ to[++tot]=v;val[tot]=w;nxt[tot]=head[u];head[u]=tot; } void dfs(int u,int fa){ cnt[u]=0;f[u][0]=0; if(d[u]==1) f[u][1]=0,cnt[u]=1; if(d[u]==1) return; for(int i=1;i<=k;i++) f[u][i]=INF; for(int i=head[u];i;i=nxt[i]){ if(to[i]==fa) continue; dfs(to[i],u); cnt[u]+=cnt[to[i]]; if(cnt[u]>k) cnt[u]=k; int v=to[i];LL w=val[i]; for(int j=0;j<=cnt[u];j++) tmp[j]=INF; for(int j=0;j<=cnt[u];j++) for(int p=0;p<=cnt[v]&&p<=j;p++) tmp[j]=min(tmp[j],f[u][j-p]+f[v][p]+w*p*(k-p)); for(int j=0;j<=cnt[u];j++) f[u][j]=tmp[j]; } } void solve(int Case){ printf("Case #%d: ",Case); n=read(),k=read(); for(int i=1;i<=n;i++) head[i]=0,d[i]=0; tot=0; int u,v,w; for(int i=1;i u=read(),v=read(),w=read(); add(u,v,w);add(v,u,w); d[u]++;d[v]++; } if(n==2){ if(k==2) printf("%d\n",w); else printf("0\n"); return; } int root=1; while(d[root]<2) root++; dfs(root,0); printf("%lld\n",f[root][k]); } int main(){ int T;scanf("%d",&T); for(int i=1;i<=T;i++) solve(i); return 0; } H. Fight Against Monsters 题意 有 \(n\) 个怪兽，每个怪兽有血量和攻击力，你每回合会收到所有没有死掉的怪兽的依次攻击，问你杀死所有怪兽最少损失多少血量。 题解 微扰法贪心。 首先可以算出每只怪兽的血量可以顶我几回合的攻击，记为 \(k_i\)，每只怪兽的攻击力记为 \(a_i\)，那么假如我按顺序杀怪兽损失血量最少，那么我损失血量为： \[a_1\times k_1+a_2\times (k_1+k_2)+...+a_n\times \sum_{i=1}^{n}k_i \] 假如我先杀第 \(2\) 只，再杀第 \(1\) 只怪兽，损失血量为： \[a_2\times k_2+a_1\times (k_1+k_2)+...+a_n\times \sum_{i=1}^{n}k_i \] 此时我受到的伤害肯定不会减少，那么： \[\begin{aligned}a_1\times k_1+a_2\times (k_1+k_2)+...+a_n\times \sum_{i=1}^{n}k_i&\le a_2\times k_2+a_1\times (k_1+k_2)+...+a_n\times \sum_{i=1}^{n}k_i\\a_1\times k_1+a_2\times k_1+a_2\times k2&\le a_2\times k_2+a_1\times k_1+a_1\times k_2\\a_2\times k_1&\le a_1\times k_2\end{aligned} \] 那么只需要按 \(a_2\times k_1\le a_1\times k_2\) 这个顺序对怪兽排序，依次杀掉就可以了。 代码 #include #include #include #include #include #include #define ff first #define ss second using namespace std; typedef long long LL; typedef pair const int N=1e5+10; int n; PII p[N]; bool cmp(PII a,PII b){return a.ss*b.ff void solve(int Case){ printf("Case #%d: ",Case); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&p[i].ss,&p[i].ff); LL num=0,sum=0; while(sum p[i].ss=num; } sort(p+1,p+n+1,cmp); LL ans=0,sum=0; for(int i=1;i<=n;i++){ sum+=p[i].ss; ans+=sum*p[i].ff; } printf("%lld\n",ans); } int main(){ int T;scanf("%d",&T); for(int i=1;i<=T;i++) solve(i); return 0; } K. Vertex Covers 题意 定义完全覆盖点集 \(S\)：\(G\) 中任意一条边总有至少 \(1\) 个顶点在 \(S\) 中。 \(S\) 的积：\(S\) 中所有点的点权之积；空集的积为 \(1\)。 求 \(G\) 的所有 \(S\) 的积之和。 题解 从 \(n\) 的范围来说，肯定是双向搜索。可以将前 \(\frac{n}{2}\) 个点和其余 \(n-\frac{n}{2}\) 个点分为两堆，分别枚举每堆的状态，算出每种状态的积。 这两堆种，如果有边在一堆之内，那么这个边的两端至少有一个点要被选。如果是有边在两堆之间，如果一堆的状态确定，可以发现另一堆最差的状态也确定了，然后另一堆中没被选的点其实是可选可不选，这就是这个集合的超集，这个超集之和就是这一堆所有方案之和。 计算超集之和就是高维前缀和： for(int u=0;u for(int sta=0;sta<1< if(!(sta&1< 当然高维前缀和也可以计算子集之和： for(int u=0;u for(int sta=0;sta<1< if(sta&1< 代码 #include #include #include #include #include using namespace std; typedef long long LL; typedef pair const int M=1e6+10; LL a[40],ans,fl[M],fr[M]; int n,m,mod; vector void solve(int Case){ ans=0; scanf("%d%d%d",&n,&m,&mod); for(int i=0;i for(int i=0;i for(int i=0,u,v;i scanf("%d%d",&u,&v); u--;v--; g[u].push_back(v); g[v].push_back(u); } int nl=n/2,nr=n-nl; for(int sta=0;sta<(1< bool flag=true;fl[sta]=1; for(int u=0;u for(int v:g[u]){ if(v>=nl) continue; if(!(sta&1ll< } if(!flag) {fl[sta]=0;break;} if(sta&1ll< } } //高维前缀和 for(int u=0;u for(int sta=0;sta<1< if(!(sta&1< for(int sta=0;sta<(1< bool flag=true;fr[sta]=1; int link=0; for(int i=0;i int u=nl+i; for(int v:g[u]) if(v if(!(sta&1< } else{ int j=v-nl; if(!(sta&1< } if(!flag) {fr[sta]=0;break;} if(sta&1< } ans=(ans+fr[sta]*fl[link])%mod; } printf("Case #%d: %lld\n",Case,ans); } int main(){ int T;scanf("%d",&T); for(int i=1;i<=T;i++) solve(i); return 0; } L. Continuous Intervals 题意 给数列 \(a_1,a_2,...,a_n\)，问有多少个连续子序列 \(a_1,a_2,...,a_m\) 满足排序后 \(a_i-a_{i-1}\le 1\)。 题解 其实这个题和蓝桥杯2013的最后一题基本一致，只是蓝桥杯是全排列，而这个是任意数。相似问题： 蓝桥杯2013省赛10题 CodeForces 193D 这类问题当然是用线段树解决的，但是用法有两种，我这里选择在原数列上来，这样形象一点，还有一种是在自然数列上进行，在这道题上就没那么好想、好写了。 设 f[i,r] 为 \(a_i,a_{i+1},...,a_r\) 排序后是几段，那么线段树可以维护 \(f[1,r],f[2,r],...,f[r,r]\)。 此时我加入 \(a_{r+1}\)，观察 \(f[1,r+1],f[2,r+1],...,f[r+1,r+1]\) 相对 \(f[1,r],f[2,r],...,f[r,r]\) 会发生什么变化。 可以发现，如果数 \(a_{r+1}\) 上一次出现的位置在 \(pos\) 的话，\(f[1,r+1],f[2,r+1],...,f[pos,r+1]\) 相对之前是不会有变化的，因为本来这些区间里就有 \(a_{r+1}\)，你再加一个 \(a_{r+1}\) 当然不会有任何影响。 如果 \(a_{r+1}-1\) 和 \(a_{r+1}+1\) 中有一个数出现在 \(pos1(pos1>l)\) 位置，那么 \(f[i,r+1]=f[i,r](l 如果 \(a_{r+1}-1\) 和 \(a_{r+1}+1\) 这两个数分别出现在 \(pos1,pos2(l 当然还有这两个数都没有出现的情况，直接所有区间都+1就行了，因为 \(a_{r+1}\) 在这些区间里很孤单。 代码 #include #include #include #include #include using namespace std; typedef long long LL; const int N=1e5+10; int n,a[N]; map struct SegTree{ #define mid (l+r>>1) int minv[N*4],tag[N*4],num[N*4]; void build(int id,int l,int r){ minv[id]=tag[id]=0,num[id]=r-l+1; if(l==r) return; build(id<<1,l,mid); build(id<<1|1,mid+1,r); } void pushdown(int id){ minv[id<<1]+=tag[id];tag[id<<1]+=tag[id]; minv[id<<1|1]+=tag[id];tag[id<<1|1]+=tag[id]; tag[id]=0; } void pushup(int id){ minv[id]=min(minv[id<<1],minv[id<<1|1]); num[id]=0; if(minv[id]==minv[id<<1]) num[id]+=num[id<<1]; if(minv[id]==minv[id<<1|1]) num[id]+=num[id<<1|1]; } void upd(int id,int l,int r,int L,int R,int x){ if(L<=l&&r<=R) {minv[id]+=x;tag[id]+=x;return;} if(tag[id]) pushdown(id); if(L<=mid) upd(id<<1,l,mid,L,R,x); if(R>mid) upd(id<<1|1,mid+1,r,L,R,x); pushup(id); } int ask(int id,int l,int r,int L,int R){ if(L<=l&&r<=R) return minv[id]==1?num[id]:0; if(tag[id]) pushdown(id); int res=0; if(L<=mid) res+=ask(id<<1,l,mid,L,R); if(R>mid) res+=ask(id<<1|1,mid+1,r,L,R); return res; } #undef mid }tr; void solve(int Case){ lastpos.clear(); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); tr.build(1,1,n); LL ans=0; for(int i=1;i<=n;i++){ int l=lastpos[a[i]]+1,pos1=lastpos[a[i]-1],pos2=lastpos[a[i]+1]; if(pos1>pos2) swap(pos1,pos2); if(pos1>=l) tr.upd(1,1,n,l,pos1,-1),tr.upd(1,1,n,pos2+1,i,1); else if(pos2>=l) tr.upd(1,1,n,pos2+1,i,1); else tr.upd(1,1,n,l,i,1); ans+=tr.ask(1,1,n,1,i); lastpos[a[i]]=i; } printf("Case #%d: %lld\n",Case,ans); } int main(){ int T;scanf("%d",&T); for(int i=1;i<=T;i++) solve(i); return 0; }