Java教程
模拟83 考试总结
本文主要是介绍模拟83 考试总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
千万恨 争不得 朝夕
考试经过
从秦皇岛回来就状态特别不好，晚上躺下就睡，白天身上基本没劲，想一会就容易犯困
开题发现T1一个\(log\)是显然的，但应该卡不过，然而没咋多想，直接上了，预计60pts，感觉脑子不好使就没想正解
T2应该可做，想了会发现不太好维护，然后就开始犯困，好不容易想出来\(n^2\)的换根，十分明显的意识到离正解只差数据结构，然而这时偶然看见旁边JYF在打主席树，感觉要完，感觉自己不能维护，于是直接上的暴力，对着部分分一通乱写
T3的dp已经没有能力思考了，直接状压走人，T4没多看骗10分跑路了
所以估分60+65+25+10=160，结果60+45+25+0=130
T2T4写挂不说，四个题都有人切，所以就又垫底了
T1.树上的数
正解看上去像暴力
对于每个修改直接dfs，标记途经的点，遇到标记的点就返回，所以是线性的
#include <bits/stdc++.h>
using namespace std;
const int N=5000050;
struct node{
int from,to,next;
}a[2*N];
int head[N],mm=1;
inline void add(int x,int y)
{
a[mm].from=x;a[mm].to=y;
a[mm].next=head[x];head[x]=mm++;
}
int aa,bb,fa[N],q[N],xx,yy,ans,an;
bool v[N];int n,m;
void dfs(int x)
{
v[x]=1;ans--;
for(int i=head[x];i;i=a[i].next)
{
int y=a[i].to;
if(v[y])continue;
dfs(y);
}
}
signed main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
cin>>n>>m>>aa>>bb;
fa[2]=1;add(1,2);ans=n;
for(int i=3;i<=n;i++)
{
fa[i]=((1ll*fa[i-1]*aa+bb)^19760817)%(i-1)+1;
add(fa[i],i);
}
cin>>q[1]>>xx>>yy;
for(int i=2;i<=m;i++)q[i]=(((1ll*q[i-1]*xx+yy)^19760817)^(i<<1))%(n-1)+2;
for(int i=1;i<=m;i++)
{
int x=q[i];
if(!v[x])dfs(x);
an^=ans;
}
cout<<an<<endl;
return 0;
}
T2.时代的眼泪
我考场上竟然忘了还有线段树合并这个东西，更别提神仙的树状数组了
先求出以1为根的答案，每个点贡献就是到根节点路径上大于\(w_x\)的个数
用树状数组维护，在dfs结束时删除，保证了数据结构中只有一条链就能查询了
剩下的就是换根dp，如果把根从\(x\)换到它原本的儿子\(y\)，那么贡献相比原来多算了\(y\)子树内小于\(w_x\)的个数，少算了\(y\)子树外小于\(w_y\)的个数，对应加减
考虑怎么快速维护，线段树合并常数较大不容易卡过，积累一个树状数组的技巧
统计\(x\)子树中的答案时，先在进子树前统计一遍，再把子树全插进去，再查一遍二者相减就是答案
对于子树外的答案，可以用全局的查询减去子树内的答案
#include <bits/stdc++.h>
using namespace std;
const int N=1000050;
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
struct node{
int from,to,next;
}a[2*N];
int head[N],mm=1;
inline void add(int x,int y)
{
a[mm].from=x;a[mm].to=y;
a[mm].next=head[x];head[x]=mm++;
}
int w[N],lsh[N],n,m,cnt;
int p[N],f[N],g[N];long long an[N];
struct bit{
int b[N];
inline int lowbit(int x){return x&(-x);}
inline void add(int p,int v)
{
for(int i=p;i<=n;i+=lowbit(i))
b[i]+=v;
}
inline int getsum(int p)
{
int s=0;
for(int i=p;i;i-=lowbit(i))
s+=b[i];
return s;
}
inline int get(int l,int r)
{
return getsum(r)-getsum(l-1);
}
}tr;
void dfs1(int x,int fa)
{
p[x]=tr.get(w[x]+1,cnt);
tr.add(w[x],1);
for(int i=head[x];i;i=a[i].next)
{
int y=a[i].to;
if(y==fa)continue;
dfs1(y,x);
}
tr.add(w[x],-1);
}
void dfs2(int x,int fa)
{
tr.add(w[x],1);
for(int i=head[x];i;i=a[i].next)
{
int y=a[i].to;
if(y==fa)continue;
int s1=tr.get(1,w[x]-1),s2=tr.get(1,w[y]-1);
dfs2(y,x);
f[y]=tr.get(1,w[x]-1)-s1;
g[y]=tr.get(1,w[y]-1)-s2;
}
}
void dfs3(int x,int fa)
{
for(int i=head[x];i;i=a[i].next)
{
int y=a[i].to;
if(y==fa)continue;
an[y]=an[x]+g[y]-f[y];
dfs3(y,x);
}
}
signed main()
{
freopen("tears.in","r",stdin);
freopen("tears.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;i++)w[i]=read();
for(int i=1;i<=n;i++)lsh[i]=w[i];
sort(lsh+1,lsh+n+1);
cnt=unique(lsh+1,lsh+1+n)-lsh-1;
for(int i=1;i<=n;i++)w[i]=lower_bound(lsh+1,lsh+cnt+1,w[i])-lsh;
for(int i=1;i<n;i++)
{
int x=read(),y=read();
add(x,y);add(y,x);
}
dfs1(1,0);
for(int i=1;i<=n;i++)an[1]+=p[i];
dfs2(1,0);
for(int i=1;i<=n;i++)g[i]=tr.get(1,w[i]-1)-g[i];
dfs3(1,0);
for(int i=1;i<=m;i++)
{
int x=read();
printf("%lld\n",an[x]);
}
return 0;
}
思维一定不能僵化，不要特地贴标签
T3.传统艺能
其实光dp的话是原题，可以类比43场的那个，多亏我还写了那么长题解
一共只有\(f_1,f_2,f_3\)，那么每次转移可以写成矩阵形式
这样不是像原来一样应对极大的\(m\)轮数，而是为了便于支持修改，将动态问题静态化
那么对于修改就可以线段树每个节点维护一个矩阵，pushup的时候就是两个矩阵相乘
所以就可以直接线段树套过来，与之类似的似乎还有之前的那个斐波，不过比这个难
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pp tr[id].p
#define pl tr[id*2].p
#define pr tr[id*2+1].p
const int N=100050;
const int mod=998244353;
char c[N],s[3];int n,m,an[5],ss[5];
struct tree{
int l,r;
int p[5][5];
}tr[4*N],ans;
inline void qi(int id)
{
memset(pp,0,sizeof(pp));
for(int i=1;i<=4;i++)
for(int k=1;k<=4;k++)
for(int j=1;j<=4;j++)
pp[i][j]=(pp[i][j]+pl[i][k]*pr[k][j]%mod)%mod;
}
void build(int id,int l,int r)
{
tr[id].l=l;tr[id].r=r;
if(l==r)
{
memset(pp,0,sizeof(pp));
pp[1][1]=pp[2][2]=pp[3][3]=pp[4][4]=1;
if(c[l]=='A')pp[2][1]=pp[3][1]=pp[4][1]=1;
if(c[l]=='B')pp[1][2]=pp[3][2]=pp[4][2]=1;
if(c[l]=='C')pp[1][3]=pp[2][3]=pp[4][3]=1;
return;
}
int mid=(l+r)>>1;
build(id*2,l,mid);build(id*2+1,mid+1,r);
qi(id);
}
void change(int id,int p,int v)
{
if(tr[id].l==tr[id].r)
{
memset(pp,0,sizeof(pp));
pp[1][1]=pp[2][2]=pp[3][3]=pp[4][4]=1;
if(v==1)pp[2][1]=pp[3][1]=pp[4][1]=1;
if(v==2)pp[1][2]=pp[3][2]=pp[4][2]=1;
if(v==3)pp[1][3]=pp[2][3]=pp[4][3]=1;
return;
}
int mid=(tr[id].l+tr[id].r)>>1;
if(p<=mid)change(id*2,p,v);
else change(id*2+1,p,v);
qi(id);
}
tree get(int id,int l,int r)
{
if(l<=tr[id].l&&r>=tr[id].r)return tr[id];
int mid=(tr[id].l+tr[id].r)>>1;
if(r<=mid)return get(id*2,l,r);
if(l>mid)return get(id*2+1,l,r);
tree ans,an1=get(id*2,l,mid),an2=get(id*2+1,mid+1,r);
memset(ans.p,0,sizeof(ans.p));
for(int i=1;i<=4;i++)
for(int k=1;k<=4;k++)
for(int j=1;j<=4;j++)
ans.p[i][j]=(ans.p[i][j]+an1.p[i][k]*an2.p[k][j]%mod)%mod;
return ans;
}
signed main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
cin>>n>>m;scanf("%s",c+1);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int op;scanf("%lld",&op);
if(op==1)
{
int p;scanf("%lld%s",&p,s+1);
change(1,p,s[1]-'A'+1);
}
else
{
int l,r;scanf("%lld%lld",&l,&r);
ans=get(1,l,r);
memset(ss,0,sizeof(ss));
an[1]=an[2]=an[3]=0,an[4]=1;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
ss[i]=(ss[i]+an[j]*ans.p[j][i]%mod)%mod;
printf("%lld\n",(ss[1]+ss[2]+ss[3])%mod);
}
}
return 0;
}
T4.铺设道路
看着不太可做，但其实还是水题
把序列差分一下，那么每次相当于选择两个位置前面减一后面加一，尽快让所有数变成0
要使得操作数最小，那么选正的减负的加是最优的，所以可以贪心模拟
维护一个双端队列，每次遇见正数把他加进去，负数就考虑找正数和他配对然后删掉
代价最大就是找最左边的，否则是最右边，直接模拟即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=300050;
const int mod=1e9+7;
int a[N],b[N],n,ans;
deque <pair<int,int> > q;
signed main()
{
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n+1;i++)b[i]=a[i]-a[i-1];
for(int i=1;i<=n+1;i++)ans+=max(b[i],(int)0);
int sum1=0,sum2=0;
for(int i=1;i<=n+1;i++)
{
if(!b[i])continue;
if(b[i]>0)q.push_back(make_pair(i,b[i]));
else
{
int x=b[i];
while(q.size()&&q.front().second+x<=0)
{
sum1=(sum1+(i-q.front().first)*(i-q.front().first)%mod*q.front().second%mod)%mod;
x+=q.front().second;q.pop_front();
}
if(x<0)
{
sum1=(sum1+(i-q.front().first)*(i-q.front().first)%mod*abs(x)%mod)%mod;
int p=q.front().second+x,id=q.front().first;q.pop_front();
q.push_front(make_pair(id,p));
}
}
}
assert(q.empty());
for(int i=1;i<=n+1;i++)
{
if(!b[i])continue;
if(b[i]>0)q.push_back(make_pair(i,b[i]));
else
{
int x=b[i];
while(q.size()&&q.back().second+x<=0)
{
sum2=(sum2+(i-q.back().first)*(i-q.back().first)%mod*q.back().second%mod)%mod;
x+=q.back().second;q.pop_back();
}
if(x<0)
{
sum2=(sum2+(i-q.back().first)*(i-q.back().first)%mod*abs(x)%mod)%mod;
int p=q.back().second+x,id=q.back().first;q.pop_back();
q.push_back(make_pair(id,p));
}
}
}
cout<<ans<<endl<<sum2<<endl<<sum1<<endl;
return 0;
}
考试总结
感觉之前犯的毛病还是在犯，考场犯困这个着实很痛苦，要尽量调整好状态
dp这方面差的太多了，接下来的dp不能再咕了，应该好好练一练
策略这块还是太草率，很多能拿的分没有拿到比较可惜，下次应该要好一点
这篇关于模拟83 考试总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
初学者必备：订单系统资料详解与实操教程12-25
-
内网穿透资料入门教程12-24
-
微服务资料入门指南12-24
-
微信支付系统资料入门教程12-24
-
微信支付资料详解：新手入门指南12-24
-
Hbase资料：新手入门教程12-24
-
Java部署资料12-24
-
Java订单系统资料：新手入门教程12-24
-
Java分布式资料入门教程12-24
-
Java监控系统资料详解与入门教程12-24
-
Java就业项目资料：新手入门必备教程12-24
-
Java全端资料入门教程12-24
-
Java日志系统资料详解：新手入门指南12-24
-
Java微服务系统资料：入门与初级应用指南12-24
-
Java小程序资料：入门教程与实战技巧12-24
栏目导航
