碎碎念
欸嘿，鸽了小半年
去做了一些不喜欢的事情，但兜兜转转，还是acm最香捏
求和
题意
求\(\sum_{i=1}^n\sum_{j=1}^n a_i*a_j (i!=j)\)
题解
感觉是去年的时候笨人唯一做满分的题……
经典前缀和，设\(sum[i]=\sum_{j=i}^na[j]\)，答案即为\(\sum_{i=1}^{n-1}a[i]*sum[i+1]\)
#define int long long
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=n;i>=1;i--)
{
if(i==n) sum[i]=a[i];
else sum[i]=a[i]+sum[i+1];
}
int ans=0;
for(int i=1;i<n;i++)
{
ans+=a[i]*sum[i+1];
}
cout<<ans;
}
选数异或
妙妙题，没有任何算法和数据结构的东东，纯思维
题意
给定n,m,x(x非负)，给出a[1]到a[n]，m次询问a[l]到a[r]内有无一对数字异或为x，若有输出yes，否则输出no
题解
边读边处理，对于每一个数字a[i]，记录其最新出现位置last[a[i]]=i
可以找到其左侧最近的和其异或为x的数字\(a[i]\oplus x\)，位置即为\(last[a[i]\oplus x]\)
设dp[i]为 a[1]~a[i]所有满足异或为x的数对中左边的数的最大位置，则$$dp[i]=max(dp[i-1],last[a[i]\oplus x])$$
则查询[l,r]时只需查看dp[r]是否>=l即可。
注意在更新dp[i]后再更新last[a[i]]，否则针对x=0的cornerCase会死得很惨
void solve()
{
cin>>n>>m>>x;
for(int i=1;i<=2000000;i++) last[i]=-1,dp[i]=-1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
int b = x^a[i];
dp[i]=max(dp[i-1],last[b]);
last[a[i]]=i;
}
for(int i=1;i<=m;i++)
{
int l,r;cin>>l>>r;
if(dp[r]>=l) puts("yes");
else puts("no");
}
}
爬树的甲壳虫
题目和题解都看懂了，比去年的自己多了一点期望dp芝士，可惜不能独立做出来，也很难独立推出来，，
待补
青蛙过河
去年水了一个二分+暴力判断做法，复杂度爆表，不知道过了几组
设跳跃能力距离为y，只要所有长度为y的区间都满足石头高度总和为2*x，则一定有解，否则无解