晚来了一小时，终榜14名，血亏
https://ac.nowcoder.com/acm/contest/61132
A题不会，我选择oeis
n=int(input()) print(n*(n+1)*(n+2)//6%1000000007)python代码
B题考虑线段树f[x][i][0]表示如果x所统辖的区间里，x第i位为0做计算得到的值，f[x][i][1]表示x所统辖的区间里，第i位为1做计算得到的值
那么叶子节点可以写三个if，合并两个区间时可以使用
f[x][i][0]=f[x*2+1][i][f[x*2][i][0]!=0];
f[x][i][1]=f[x*2+1][i][f[x*2][i][1]!=0];
询问时可以把[l,r]区间的转移矩阵合并，最后对于x的每一位计算答案
合并操作；
for(int i=0;i<=20;i++)
{
t[i][0]=f[x][i][t[i][0]!=0];
t[i][1]=f[x][i][t[i][1]!=0];
}
计算答案：
for(int i=0;i<=20;i++)
{
ans=ans+t[i][ (x&(1<<i))!=0] ;
}
（太C了，写了十五分钟就过了）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
ll x;scanf("%lld",&x);return x;
}
int n;
char s[100010];
int f[400010][25][2],t[25][2],a[100010];
int work(int xx,char c,int yy)
{
if(c=='|')
return xx|yy;
else if(c=='^')
return xx^yy;
else
return xx&yy;
}
void build(int x,int l,int r)
{
if(l==r)
{
for(int i=0;i<=20;i++)
{
f[x][i][0]=work(0,s[l],a[l]&(1<<i));
f[x][i][1]=work(1<<i,s[l],a[l]&(1<<i));
}
return ;
}
int mid=(l+r)/2;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
for(int i=0;i<=20;i++)
{
f[x][i][0]=f[x*2+1][i][f[x*2][i][0]!=0];
f[x][i][1]=f[x*2+1][i][f[x*2][i][1]!=0];
}
}
void add(int x,int l,int r,int d)
{
if(l==r)
{
for(int i=0;i<=20;i++)
{
f[x][i][0]=work(0,s[l],a[l]&(1<<i));
f[x][i][1]=work(1<<i,s[l],a[l]&(1<<i));
}
return ;
}
int mid=(l+r)/2;
if(d<=mid)
add(x*2,l,mid,d);
else
add(x*2+1,mid+1,r,d);
for(int i=0;i<=20;i++)
{
f[x][i][0]=f[x*2+1][i][f[x*2][i][0]!=0];
f[x][i][1]=f[x*2+1][i][f[x*2][i][1]!=0];
}
}
void ask(int x,int l,int r,int tl,int tr )
{
if(tl<=l&&r<=tr)
{
for(int i=0;i<=20;i++)
{
t[i][0]=f[x][i][t[i][0]!=0];
t[i][1]=f[x][i][t[i][1]!=0];
}
return ;
}
int mid=(l+r)/2;
if(tl<=mid)
ask(x*2,l,mid,tl,tr);
if(tr>mid)
ask(x*2+1,mid+1,r,tl,tr);
}
int main()
{
// freopen("1.in","r",stdin);
n=read();
scanf("%s",s+1);
for(int i=1;i<=n;i++)
a[i]=read();
build(1,1,n);
for(int m=read();m;m--)
{
if(read()&1)
{
int pos=read();
a[pos]=read();
add(1,1,n,pos);
}
else
{
int x=read(),l=read(),r=read(),ans=0;
for(int i=0;i<=20;i++)
{
t[i][0]=0;
t[i][1]=(1<<i);
}
ask(1,1,n,l,r);
for(int i=0;i<=20;i++)
{
ans=ans+t[i][ (x&(1<<i))!=0] ;
}
printf("%d\n",ans);
}
}
}
B
C
如果先手一次能赢，输出alice
如果先手第一次怎么动，后手第一次一定能赢，输出Bob
否则输出平局
D
考虑二分答案，问题转变成判断，只经过小于等于val的点，到达ed的最短路是否小于等于h，暴力跑一跑即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
ll x;scanf("%lld",&x);return x;
}
int n,m,st,ed,a[10010],vis[10010],h;
ll d[10010];
queue<int>q;
vector<int>e[10010],v[10010];
int check(int val)//要求路上的松果数量<=val
{
memset(d,0x3f,sizeof(d));
if(a[st]>val)
return 0;
d[st]=0;
q.push(st);
while(q.size())
{
int tx=q.front();
q.pop();
vis[tx]=0;
for(int i=0;i<e[tx].size();i++)
{
if(a[e[tx][i]]<=val&&d[tx]+v[tx][i]<d[e[tx][i]])
{
d[e[tx][i]]=d[tx]+v[tx][i];
if(vis[e[tx][i]]==0)
{
vis[e[tx][i]]=1;
q.push(e[tx][i]);
}
}
}
}
if(d[ed]<=h)
return 1;
return 0;
}
int main()
{
// freopen("1.in","r",stdin);
n=read();m=read();st=read();ed=read();h=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
e[x].push_back(y);
v[x].push_back(z);
e[y].push_back(x);
v[y].push_back(z);
}
int l=1,r=10000000,mid;
while(l+1<r)
{
mid=(l+r)/2;
if(check(mid))
r=mid;
else
l=mid;
}
if(check(l))
cout<<l;
else if(check(r))
cout<<r;
else
cout<<-1;
}
D
E
对于当前前缀和sum，只需判断sum-m是否出现过即可，用前缀和维护一下。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
ll x;scanf("%lld",&x);return x;
}
int n,m,ans;
ll sum;
map<ll,int>o;
int main()
{
n=read();m=read();
o[0]=1;
for(int i=1;i<=n;i++)
{
sum=sum+read();
ans=ans+o[sum-m];
o[sum]++;
}
cout<<ans;
}
E
F
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
ll x;scanf("%lld",&x);return x;
}
int ans;
int n,a[100010],fa[100010];
int get(int x)
{
return fa[x]==x?x:fa[x]=get(fa[x]);
}
void merge(int x,int y)
{
if(get(x)==get(y))
return ;
fa[get(x)]=get(y);
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=n;i++)
{
a[i]=read();
merge(a[i],i);
}
ans=n;
for(int i=1;i<=n;i++)
if(i==get(i))
ans--;
cout<<ans;
}
F
标签：11,12,return,get,int,ll,long,read,萌新 From： https://www.cnblogs.com/qywyt/p/17548290.html