前言

290卡成145，十分开心。

---

正题

---

T1：密码

大意

N个数乘起来

考试时

看起来十分简单的高精乘单精

解题思路

1024 1024 其实是 1024 10 24 高精乘高精了解一下，30分QAQ

代码(高精乘高精我就不解释了吧)

#include<cstdio> #include<cstring> #define M 2500 using namespace std; long long a[M+1],n,k[M],b[M+1],l,lo; void read() { memset(k,0,sizeof(k)); char c[51]; scanf("%s",c); l=strlen(c); for (int i=1;i<=l;i++) k[i]=c[l-i]-48; } void add() { for (int i=1;i<=lo;i++) { for (int j=1;j<=l;j++) { b[i+j-1]+=a[i]*k[j]; b[i+j]+=b[i+j-1]/10; b[i+j-1]%=10; } } lo=-1; for (int i=M;i>=1;i--) { if (b[i]!=0&&lo==-1) lo=i; a[i]=b[i];b[i]=0; } } void write() { int w=M; while (w>1&&!a[w]) w--; int flag=w; for (;w;w--) printf("%d",a[w]); } int main() { scanf("%d",&n); a[1]=1;lo=1; for (int i=1;i<=n;i++) { read(); add(); } write(); }

---

T2：宝石

大意

有一个 m∗m m ∗ m 的矩阵，然后 n n 个宝石价值不同在矩阵里，然后一个为k∗kk∗k的东西要求碰到大宝石价值最大。

考试时

敲了一个矩阵前缀和然后 O(n2) O ( n 2 ) 暴力枚举拿了60分

解题思路

定义一个长度m，高度为k的扫描线，然后在线内的用线段树维护最大长度为k的字段和。

代码

#include<cstdio> #include<algorithm> using namespace std; struct treenode{ int l,r,w,lazy; }a[300001]; struct node{ int x,y,w; }d[50001]; int m,n,k,maxs; void build(int k,int l,int r) { a[k].l=l;a[k].r=r; if (l==r) return; int mid=(l+r)/2; build(k*2,l,mid); build(k*2+1,mid+1,r); } void ddata(int k) { a[k*2].w+=a[k].lazy; a[k*2+1].w+=a[k].lazy; a[k*2].lazy+=a[k].lazy; a[k*2+1].lazy+=a[k].lazy; a[k].lazy=0; } void updata(int l,int r,int k,int num) { if (a[k].l==l&&a[k].r==r) { a[k].w+=num; a[k].lazy+=num; return; } ddata(k); if (a[k*2].r>=r) updata(l,r,k*2,num); else if (a[k*2+1].l<=l) updata(l,r,k*2+1,num); else updata(l,a[k*2].r,k*2,num),updata(a[k*2+1].l,r,k*2+1,num); a[k].w=max(a[k*2].w,a[k*2+1].w); } //以上为线段树 bool cmp(node x,node y) { return x.y<y.y; } int main() { scanf("%d%d%d",&m,&n,&k); for (int i=1;i<=n;i++) { scanf("%d%d%d",&d[i].x,&d[i].y,&d[i].w); } sort(d+1,d+1+n,cmp);//排序 build(1,1,m);//建树 int w=1;//扫描上限 for (int i=1;i<=n;i++)//枚举下限 { while (d[i].y-d[w].y>k)//更新上限 { updata(d[w].x,min(d[w].x+k,m),1,-d[w].w);//去掉 w++; } updata(d[i].x,min(d[i].x+k,m),1,d[i].w);//维护字段和 maxs=max(maxs,a[1].w);//查询最大字段和 } printf("%d",maxs); }

---

T3：页

大意

一个序列，每次取中间的放到头或尾，求至少多少次可以变为单调递增。

考试

刚开始打了个贪心，然后发现数据不是很大，然后打了一个广搜，为了防止超时打了一个卡时间的结果就炸了30。把卡时间的去掉后100

解题思路

广搜然后map库(或哈希表)去重

代码

#include<cstdio> #include<map> #include<string> #include<iostream> #include<queue> #include<ctime> using namespace std; map<string,int> f; string s,mb,state[362881]; int a[10],n,head,tail; void bfs() { if (s==mb) { printf("0"); return; } state[1]=s;f[s]=1; head=0;tail=1; do { s=state[++head]; int k=f[state[head]]; for (int i=1;i<=n/2;i++) swap(s[i],s[n/2+1]);//放在头 if (!f[s]) { state[++tail]=s; f[s]=k+1; if (s==mb)//已经完成 { printf("%d",k); return; } } s=state[head]; for (int i=n;i>n/2+1;i--) swap(s[i],s[n/2+1]);//放在尾 if (!f[s]) { state[++tail]=s; f[s]=k+1; if (s==mb)//已经完成 { printf("%d",k); return; } } } while (head<tail); printf("No Answer"); } int main() { scanf("%d",&n); s+="*";mb+="*"; for (int i=1;i<=n;i++) { scanf("%d",&a[i]); s+=i+48; mb+=i+48; } for (int i=1;i<n;i++) for (int j=i+1;j<=n;j++) { if (a[i]>a[j]) { swap(a[i],a[j]); swap(mb[i],mb[j]);//确定目标状态 } } bfs(); return 0; }

---

T4：景点中心

大意

有n个景点构成一颗树，然后每个景点有不同数量的学生，边有不同的长度，定一个景点为中心要求所有学生到达这个点的路径长度和最小。

考试

敲出了正解，结果没注意范围30QAQ。

解题思路

一棵树然后就想到了树形dp，然后想起来有个东西叫二次扫描换根法，之后就推出了正解：

首先我们先以1为根进行一遍求出 f[i] f [ i ] 和 zn[i] z n [ i ] ， f[i] f [ i ] 是表示点i子树的学生走到点i的路径长度和，然后 zn[i] z n [ i ] 表示点i的子树的学生人数总和。

然后我们就求出了以i为根节点的情况下的路径和，我们尝试推到第二层的节点。 这是一颗以1为根节点的树，然后我们变为以2为根节点 然后我们会发现 图中绿色部分（原第二个节点的子树部分）都少走了一条路w，而图中红色部分（其余部分）都多走了一条路w，所以我们可以自己计算：

c[x]=c[father]+(zn[1]−zn[x])∗w−zn[x]∗w c [ x ] = c [ f a t h e r ] + ( z n [ 1 ] − z n [ x ] ) ∗ w − z n [ x ] ∗ w 从而 O(1) O ( 1 ) 的时间复杂度内计算出下一个点为根时的距离和。

代码

#include<cstdio> #include<algorithm> #include<cstring> #define N 1000001 using namespace std; struct node{ int next,to,w; }a[N]; int ls[N],tot,n,x,y,w,v[N]; long long c[N],f[N],zn[N],maxs,num[N]; void addl(int x,int y,int w) { a[++tot].to=y;a[tot].w=w; a[tot].next=ls[x];ls[x]=tot; } void dp(int x,int dep)//第一次扫描 { v[x]=true; zn[x]=num[x];//记录人数 f[x]=num[x]*dep;//统计 for (int i=ls[x];i;i=a[i].next) { int y=a[i].to; if (!v[y]) { dp(y,dep+a[i].w); f[x]+=f[y]; zn[x]+=zn[y];//累计 } } } void zdp(int x,int dep,int fa,int from)//第二次扫描 { v[x]=true; if (x!=1) c[x]=c[fa]+(zn[1]-zn[x])*a[from].w-zn[x]*a[from].w;//计算 if (c[x]<c[maxs]) maxs=x; for (int i=ls[x];i;i=a[i].next) { y=a[i].to; if (!v[y]) zdp(y,dep+a[i].w,x,i);//计算子节点 } } int main() { freopen("data.txt","r",stdin); scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%lld",&num[i]); } for (int i=1;i<n;i++) { scanf("%d%d%d",&x,&y,&w); addl(x,y,w); addl(y,x,w); } c[0]=1e18; maxs=0; dp(1,0); memset(v,0,sizeof(v)); c[1]=f[1]; zdp(1,0,0,0); printf("%lld\n%lld",maxs,c[maxs]); }

---

后续

zyc大佬太强了

m e | \ / V / / ====== / / orz orz orz orz orz orz orz orz orz / / ====== / / orz orz orz orz orz orz orz orz orz + =========== + orz orz orz orz orz orz orz orz orz | [zyc dalao] | orz orz orz orz orz orz orz orz orz + =========== + orz orz orz orz orz orz orz orz orz \ \ ====== \ \ orz orz orz orz orz orz orz orz orz \ \ ====== \ \ orz orz orz orz orz orz orz orz orz