noip模拟测试50
2024-09-04 05:43:17
考试过程：开题顺序1,2，3,做T1的时候我想到了要求的东西，就是分成尽量少的段使得每段之和>=k，但是我不会求,就打了个暴力走了，然后看T2，这题我觉得和之前做过的一道题比较像，因为我觉得\(a_i\)比较大，所以我就把每个数取了个log,结果错了，根据log函数图象可知，或者根据公式\(log(a\times b)=log(a)+log(b)\),所以用 log 只适合有乘法运算的时候。然后T3，暴力没时间打了，其实是考场上\(n^2\)可以水过的一道题。总结一下：1.有一个想法之后可以联系之前学过的知识思考如何实现。2.要合理分配时间，没道题必须都要有分，模拟真实考试环境。
T1 第零题
思路：容易发现，如果只考虑朝上走,就是求出每个点可以走到的点,接下来就是一个简单的倍增，（好吧，我在考场上就是想不到），接下来考虑往下走的一段。这里有一个神秘的观察,对于一条链,如果体力都是满的从两边开始走,那么复活的次数是一样的，证明的话可以使用调整法，将满足条件的一段进行左移即可。最后感谢varuxn教我关于倍增的基础知识，要从大到小进行枚举....代码如下：
AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define head heeeaddd
#define next net
#define f() cout<<"YES"<<endl
using namespace std;
const int N=2e5+10;
const int INF=1e9+10;
int n,k,tot,q,timi;
int to[N<<1],next[N<<1],head[N],val[N<<1];
int size[N],top[N],son[N],deep[N],dfn[N],id[N],dis[N],fa[N];
int die[N][35];
vector<int> v;
ii read()
{
int x=0;
char ch=getchar();
bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
iv add(int x,int y,int z)
{
to[++tot]=y;
next[tot]=head[x];
head[x]=tot;
val[tot]=z;
}
iv dfs(int st,int f)
{
deep[st]=deep[f]+1;
size[st]=1;
for(re i=head[st];i;i=next[i])
{
int p=to[i];
if(p==f) continue;
dis[p]=dis[st]+val[i];
dfs(p,st);
size[st]+=size[p];
fa[p]=st;
son[st]=(size[son[st]]>size[p])?son[st]:p;
}
}
iv dfs2(int st,int t)
{
dfn[st]=++timi;
id[timi]=st;
top[st]=t;
if(!son[st]) return;
dfs2(son[st],t);
for(re i=head[st];i;i=next[i])
{
int p=to[i];
if(p==fa[st] or p==son[st]) continue;
dfs2(p,p);
}
}
ii get(int x,int y)
{
if(x==y) return x;
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(deep[fx]<deep[fy]) swap(x,y),swap(fx,fy);
x=fa[fx],fx=top[x];
}
return deep[x]<deep[y]?x:y;
}
iv DFS(int st,int f)
{
int l=0,r,pos=INF;
if(!v.empty())
{
r=v.size()-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(dis[st]-dis[v[mid]]>=k)
{
pos=v[mid];
l=mid+1;
}
else r=mid-1;
}
if(pos!=INF)
{
die[st][0]=pos;
for(re i=1;(1<<i)<=n;i++) die[st][i]=die[die[st][i-1]][i-1];
}
}
v.push_back(st);
for(re i=head[st];i;i=next[i])
{
int p=to[i];
if(p==f) continue;
DFS(p,st);
}
v.pop_back();
}
signed main()
{
n=read(),k=read();
int u,v,c,x,y;
for(re i=1;i<n;i++)
{
u=read(),v=read(),c=read();
add(u,v,c);
add(v,u,c);
}
dfs(1,0),dfs2(1,1),DFS(1,0);
q=read();
while(q--)
{
x=read(),y=read();
int lca=get(x,y),now,cnt=0,ans=0,las1,las2;
cnt=22;
while(1)
{
if(deep[die[x][0]]<deep[lca] or (!die[x][0])) break;
while( (!die[x][cnt] and cnt>=0) or (deep[die[x][cnt]]<deep[lca])) --cnt;
ans+=(1<<cnt);
x=die[x][cnt];
}
cnt=22;
while(1)
{
if(deep[die[y][0]]<deep[lca] or (!die[y][0])) break;
while( (!die[y][cnt] and cnt>=0) or (deep[die[y][cnt]]<deep[lca])) --cnt;
ans+=(1<<cnt);
y=die[y][cnt];
}
if(dis[x]+dis[y]-2*dis[lca]>=k) ++ans;
printf("%lld\n",ans);
}
return 0;
}
T2 第负一题
思路：这道题\(o(n^2)\)的朴素DP是很好想的，主要是说说如何进行优化，考虑分治,求通过中间的答案.
对于每个点,可以分别求出取不不取对应的中间的点的最优答案,记为\(l_{i,0/1}\),\(r_{i,0/1}\),那么考虑合并，对于 i,j,那么合并答案为\(max(l_{i,0}+r_{j,0},l_{i,1}+r_{j,0},l_{i,0}+r_{j,1})\).
令\(ld_i=max(l_{i,1}-l_[i,0],0)\),\(rd_i=max(r_{j,1}-r_{j,0},0)\),那么答案即为\(l_{i,0}+r_{j,0}+max(ld_i,rd_j)\),这东西可以进行排序，然后我们枚举左区间，二分查找右区间即可。实现细节较多，代码如下：
AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
using namespace std;
const int N=2e5+10;
const int mo=998244353;
const int INF=1e18;
int n,ans;
int a[N],l[N][3][3],r[N][3][3],sumd[N],sumr[N];
struct node {int val,pos;friend bool operator < (node a,node b) {return a.val<b.val;}}ld[N],rd[N];
ii read()
{
int x=0;
char ch=getchar();
bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
void solve(int L,int R)
{
if(L==R) return ans=(ans+a[L])%mo,void();
int mid=(L+R)>>1;
solve(L,mid),solve(mid+1,R);
l[mid][1][1]=l[mid][2][1]=a[mid],l[mid][1][0]=l[mid][0][1]=-INF,l[mid][0][0]=0,ld[mid]=(node){a[mid],mid};
r[mid+1][1][1]=r[mid+1][2][1]=a[mid+1],r[mid+1][1][0]=r[mid+1][0][1]=-INF,r[mid+1][0][0]=0,rd[mid+1]=(node){a[mid+1],mid+1};
for(re i=mid-1;i>=L;i--)
{
l[i][1][0]=l[i+1][0][0]+a[i],l[i][1][1]=l[i+1][0][1]+a[i];//l[i][0][0] 左边的，自己不选，分界点(mid)不选
l[i][0][0]=max(l[i+1][1][0],l[i+1][0][0]),l[i][0][1]=max(l[i+1][1][1],l[i+1][0][1]);
l[i][2][0]=max(l[i][1][0],l[i][0][0]),l[i][2][1]=max(l[i][1][1],l[i][0][1]);//l[i][2][0/1] 表示在 i 处选不选右边界的最大值，起统计答案作用
ld[i]=(node){max(0ll,l[i][2][1]-l[i][2][0]),i};
}
for(re i=mid+2;i<=R;i++)
{
r[i][1][0]=r[i-1][0][0]+a[i],r[i][1][1]=r[i-1][0][1]+a[i];//r[i][0][0] 右边的，自己不选，分界点(mid+1)不选
r[i][0][0]=max(r[i-1][1][0],r[i-1][0][0]),r[i][0][1]=max(r[i-1][1][1],r[i-1][0][1]);
r[i][2][0]=max(r[i][1][0],r[i][0][0]),r[i][2][1]=max(r[i][1][1],r[i][0][1]);
rd[i]=(node){max(0ll,r[i][2][1]-r[i][2][0]),i};
}
sort(ld+L,ld+mid+1),sort(rd+mid+1,rd+R+1);
sumr[mid]=sumd[mid]=0,sumr[mid+1]=r[rd[mid+1].pos][2][0],sumd[mid+1]=rd[mid+1].val;
for(re i=mid+2;i<=R;i++) sumr[i]=(sumr[i-1]+r[rd[i].pos][2][0])%mo,sumd[i]=(sumd[i-1]+rd[i].val)%mo;
for(re i=L;i<=mid;i++)
{
int p=upper_bound(rd+mid+1,rd+R+1,ld[i])-rd-1;
ans=(ans+(p-mid)*((l[ld[i].pos][2][0]+ld[i].val)%mo)%mo+sumr[p]%mo)%mo;
ans=(ans+(R-p)*(l[ld[i].pos][2][0])%mo+(sumr[R]-sumr[p]+mo)%mo+(sumd[R]-sumd[p]+mo)%mo)%mo;
}
}
signed main()
{
n=read();
for(re i=1;i<=n;i++) a[i]=read();
solve(1,n);
printf("%lld\n",ans);
return 0;
}
T3 第负二题
思路：因为这题数据太水了，\(o(n^2)\)的算法就能过，这也提示我们对于暴力算法可以进行优化，让他能够计算较大的数据，可能会多得分。
代码如下：
AC_code
#include<bits/stdc++.h>
#define re register int
#define int long long
#define ii inline int
#define iv inline void
#define head heeeaddd
#define next net
#define f() cout<<"YES"<<endl
using namespace std;
typedef unsigned long long u64;
const int mo=998244353;
const int N=5e6+10;
int n,L,X,Y,A,B,cnt,timi,ans;
int l[N],r[N],f[N],jc[N];
bool hav[N];
int q1[N],q2[N];
struct node
{
int l,r;
}cun[N];
ii read()
{
int x=0;
char ch=getchar();
bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
u64 xorshift128p(u64 &A, u64 &B) {
u64 T = A, S = B;
A = S;
T ^= T << 23;
T ^= T >> 17;
T ^= S ^ (S >> 26);
B = T;
return T + S;
}
void gen(int n, int L, int X, int Y, u64 A, u64 B, int l[], int r[])
{
for (int i = 1; i <= n; i ++) {
l[i] = xorshift128p(A, B) % L + X;
r[i] = xorshift128p(A, B) % L + Y;
if (l[i] > r[i]) swap(l[i], r[i]);
}
}
signed main()
{
n=read(),L=read(),X=read(),Y=read();
scanf("%llu%llu",&A,&B);
gen(n,L,X,Y,A,B,l,r);
for(re i=1;i<=n;i++)
if(!l[i] and !r[i]) ++cnt,f[i]=0;
else hav[i]=1,q1[++q1[0]]=i;
jc[0]=1;
for(re i=1;i<=n;i++) jc[i]=(jc[i-1]%mo)*3%mo;
while(1)
{
if(cnt==n) break;
++timi;
q2[0]=0;
for(re i=1;i<=q1[0];i++)
{
if(i==1 or i==q1[0] or l[q1[i]]==r[q1[i]] or l[q1[i]]+1==r[q1[i]] or (!hav[q1[i]-1]) or (!hav[q1[i]+1])) {f[q1[i]]=timi;continue;}
cun[q1[i]].l=max(l[q1[i]]+1,max(l[q1[i-1]],l[q1[i+1]]));
cun[q1[i]].r=min(r[q1[i]]-1,min(r[q1[i-1]],r[q1[i+1]]));
if(cun[q1[i]].l>cun[q1[i]].r) f[q1[i]]=timi;
else q2[++q2[0]]=q1[i];
}
for(re i=1;i<=q1[0];i++) hav[q1[i]]=0,l[q1[i]]=cun[q1[i]].l,r[q1[i]]=cun[q1[i]].r;
for(re i=1;i<=q2[0];i++) hav[q2[i]]=1,q1[i]=q2[i];
cnt+=q1[0]-q2[0];
q1[0]=q2[0];
}
for(re i=1;i<=n;i++) ans=(ans%mo+f[i]*jc[i-1]%mo)%mo;
printf("%lld\n",ans);
return 0;
}
最新文章
- NSOperation操作依赖和监听
- linux vi编辑器操作手册
- Ansible简介及常用模块
- C语言各种标准的
- Debian 7 安装 Python3.4
- 单机c/s软件如何让老板在异地看销售营业报表
- Android开发5大布局方式详解
- BZOJ_1202_狡猾的商人_(并查集)
- C# Datatable导出Excel方法
- CSS 3 属性学习 —— 1. Gradient 渐变
- 人工智能 tensorflow框架-->简介及安装01
- myEclipse配置SVN
- vue 树形下拉框 亲测 好用
- RestTemplate之GET和POST调用和异步回调
- python学习记录（一）
- jdk8系列二、jdk8方法引用、重复注解、更好的类型推断、新增注解
- Jenkins-Publish HTML reports
- linux下面redis安装
- [Visual Studio] 记一次排错：打不开 Nuget 包管理器里的安装package页面，无法 安装 / 恢复 包
- 设计模式_享元设计模式(flyweight)