中国石油大学（北京）第三届“骏码杯”程序设计竞赛（同步赛）(D,E,F)
D
这个题大意就是给你\(n\)个数，我们对于每一段数组，有一个公式需要计算
其中\(f(x)\)是\(x\)的质因数的数量
然后对于这某一段的数，我们只需要知道这些数的所有出现过的质因数的种类即可
但是对于\(i\)和\(j\)是任意的，我们使用暴力求解显然是不现实的
然后我就想到了一种方法
就是对于从\(1\)到\(i-1\)，我们已经知道了\(i-1\)个数作为最后一个数的和，然后对于添加一个\(a_i\),它里面有多少个质因数是有效的呢，贡献是多少呢
对于\(a_i\)的质数\(x\)来说，只有对于从\(j\)到\(i\)这一段里面都没有出现过\(x\)作为质因数才可以说是有效
那么这个因数的贡献值为\(j-i\),对于\(j\),我们可以使用一个\(unordered__mpa\)来实现
对于求质因数
我之前是一个一个数的求质因数
但是我好像知道了一个新的求值因数的求法，是直接求的方式
void init()
{
for (int i=2;i<=mx;i++)//p[i]里面存的就是i的质因数
{
if(p[i].size()) continue;
for (int j=i;j<=mx;j+=i)
{
p[j].push_back(i);
}
}
return ;
}
然后具体的就看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
int t,n;
int mx=1e6;
int a[maxn];
vector<int>p[1000000+10];
void init()
{
for (int i=2;i<=mx;i++)
{
if(p[i].size()) continue;
for (int j=i;j<=mx;j+=i)
{
p[j].push_back(i);
}
}
return ;
}
void solve()
{
cin>>n;
unordered_map<int,int>last;
int ans=0;
int pre=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
int now=0;
for (auto x:p[a[i]])
{
// cout<<x<<" ";
now+=(i-last[x]);
last[x]=i;
}
now+=pre;
ans+=now;
pre=now;
// cout<<"\n";
}
cout<<ans<<"\n";
return ;
}
signed main ()
{
cin>>t;
init();
while (t--)
{
solve();
}
return 0;
}
E
这个题大意就是有一个网格，每一个空格要么是空格，要么是建筑，要么是悬崖等无用的土地
我们需要找到一个\(r\times c\)大小的空地并且离这个空地不大于的\(d\)的距离至少有一个建筑
问有多少块空地的选择
我在赛时觉得对于\(r\times c\)大小的空地比较好找，就是直接使用二维前缀和
就是找到至少一个建筑离这块空地的距离小于等于\(d\)不好找
然后发现这个其实也可以用二维前缀和
我们先把所有建筑作为起始点，然后把这些建筑可到达（距离小于等于\(d\))的点的值赋为\(1\)，那么对于这一块只要前缀和不为\(0\)即可满足条件
然后我这里为了不适用全局变量，使用了匿名函数，之前一直不知道这个叫什么
auto check=[&](int x,int y,int tx,int ty)->bool
{
int now=sum[tx][ty]-sum[tx][y-1]-sum[x-1][ty]+sum[x-1][y-1];
if(now) return false;
now=can[tx][ty]-can[tx][y-1]-can[x-1][ty]+can[x-1][y-1];
if(now) return true;
return false;
};
#include <bits/stdc++.h>
using namespace std;
int t,n,m,r,c,d;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
void solve()
{
cin>>n>>m>>r>>c>>d;
vector<string>a(n+1);
vector<vector<int>>sum(n+1,vector<int>(m+1,0));
vector<vector<int>>can(n+1,vector<int>(m+1,0));
queue<array<int,3>>q;
for (int i=1;i<=n;i++)
{
cin>>a[i];
a[i]=" "+a[i];
for (int j=1;j<=m;j++)
{
if(a[i][j]=='x')
{
q.push({i,j,0});
}
if(a[i][j]!='.')
{
sum[i][j]=1;
}
}
}
while (!q.empty())
{
auto [x,y,dis]=q.front();
q.pop();
if(dis>d) break;
if(can[x][y]) continue;
can[x][y]=1;
for (int d=0;d<4;d++)
{
int tx=x+dx[d];
int ty=y+dy[d];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m)
{
q.push({tx,ty,dis+1});
}
}
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];
can[i][j]=can[i-1][j]+can[i][j-1]-can[i-1][j-1]+can[i][j];
}
}
auto check=[&](int x,int y,int tx,int ty)->bool
{
int now=sum[tx][ty]-sum[tx][y-1]-sum[x-1][ty]+sum[x-1][y-1];
if(now) return false;
now=can[tx][ty]-can[tx][y-1]-can[x-1][ty]+can[x-1][y-1];
if(now) return true;
return false;
};
int ans=0;
for (int i=1;i<=n;i++)
{
int ii=i+r-1;
if(ii>n) break;
for (int j=1;j<=m;j++)
{
int jj=j+c-1;
if(jj>m) break;
if(check(i,j,ii,jj))
{
ans++;
}
}
}
cout<<ans<<"\n";
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
return 0;
}
F
题目大意就是有一个集合，有三种操作
一种是添加，往集合了添加一个\(x\)
一种是删除，从集合了删除一个\(x\)
最后一个是查询，查询这个集合的任意两个数的最小异或值
我们可以知道，对于这些有序数\(a,b,c,d\)，最小异或值一定是出现在相邻的两个数异或值里
然后我们可以开一个\(multiset\)用来存这个集合里面的数
一个\(multiset\)用来存所有相邻的两个数的异或值
对于每一次增加一个数，我们不仅要增加这个数和左右两边的异或值，还需要删除原来左右两边的异或值（原来这两个是相邻的，这个是一定要删除的，我们要保证后面的位置不会受到影响）
然后删除操作和增加操作是相反的
查询就是记录异或值的那个集合的最小的那一个异或值
具体的看代码
#include <bits/stdc++.h>
using namespace std;
int n;
multiset<int>st,ans;
void add(int x)
{
auto it=st.lower_bound(x);
if(it!=st.end())
{
ans.insert(*it^x);
}
if(it!=st.begin())
{
ans.insert(*prev(it)^x);
}
if(it!=st.end()&&it!=st.begin())
{
ans.erase(ans.lower_bound(*it^*prev(it)));
}
st.insert(x);
return ;
}
void del(int x)
{
auto it=st.lower_bound(x);
st.erase(it);
it=st.lower_bound(x);
if(it!=st.end())
{
ans.erase(ans.lower_bound(*it^x));
}
if(it!=st.begin())
{
ans.erase(ans.lower_bound(*prev(it)^x));
}
if(it!=st.end()&&it!=st.begin())
{
ans.insert(*it^*prev(it));
}
return ;
}
void query()
{
cout<<*ans.begin()<<"\n";
return ;
}
int main ()
{
cin>>n;
while (n--)
{
string s;
cin>>s;
if(s=="ADD")
{
int x;
cin>>x;
add(x);
}
else if(s=="DEL")
{
int x;
cin>>x;
del(x);
}
else
{
query();
}
}
return 0;
}