今天摆了???
A.异或帽子
**题。
点击查看代码
#include<bits/stdc++.h>
using ll=long long;
ll n,b[200005],sum;
int main(){
freopen("hat.in","r",stdin);freopen("hat.out","w",stdout);
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin>>n;
for(int i=1;i<=n;++i)std::cin>>b[i],sum=sum^b[i];
for(int i=1;i<=n;++i)std::cout<<(sum^b[i])<<' ';
return 0;
}
B.传话游戏
**题。
点击查看代码
#include<bits/stdc++.h>
using ll=long long;
const int P=1000000007;
ll n,f[100005][3];
std::string s[100005];
int main(){
freopen("string.in","r",stdin);freopen("string.out","w",stdout);
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin>>n;for(int i=1;i<=n;++i)std::cin>>s[i];
f[1][1]=f[1][2]=1;
for(int i=2;i<=n;++i){
f[i][1]=(f[i-1][0]+f[i-1][1])%P;
f[i][2]=(f[i-1][0]+f[i-1][1])%P;
if(s[i]!=s[i-1])f[i][0]=f[i-1][2]%P;
}
std::cout<<(f[n][0]+f[n][1])%P;
return 0;
}
C.全球覆盖
首先可以看出 \(x\) 轴和 \(y\) 轴相互独立，所以可以当成一维处理，分别求出 \(x\) 轴和 \(y\) 轴线段交集的最大值乘起来就是答案。
因为对于一种覆盖方案，交集答案一定是被相邻两点夹在中间的若干状态相同的线段之和，两线段状态相同指两线段被相同的初始线段所夹。
具体操作我们可以采用异或哈希，再统计哈希值相同的状态的长度之和就可以。
点击查看代码
#include<bits/stdc++.h>
using ll=long long;using ull=unsigned long long;
std::mt19937_64 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
int n,X,Y,w[1000005];
ull s[1000005],t[1000005],val[1000005],rd;
struct node{int val,id;bool operator<(const node &rhs)const{return val<rhs.val;}}x[1000005],y[1000005],len[1000005];
std::unordered_map<ull,int> hash;
inline int solve(node *a,int lim){
hash.clear();ull now=0;int ans=0;
std::sort(a+1,a+1+2*n);
for(int i=1;i<=2*n;++i)len[i].val=a[i].val-a[i-1].val,len[i].id=a[i].id;len[2*n+1].val=lim-a[2*n].val;
for(int i=1;i<=2*n+1;++i)hash[now]+=len[i].val,ans=std::max(ans,hash[now]),now^=val[len[i].id];
return ans;
}
int main(){
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin>>n>>X>>Y;
for(int i=1;i<=n;++i)std::cin>>x[i].val>>y[i].val>>x[i+n].val>>y[i+n].val,x[i].id=x[i+n].id=y[i].id=y[i+n].id=i,val[i]=rnd();
std::cout<<1ll*solve(x,X)*solve(y,Y);
return 0;
}
D.幂次序列
咕。暴力 70pts。对于 \(n\le 50\) 直接跑 \(O(n^2\log n)\)。
对于 \(\forall a_i\le 30\) 的点可以直接枚举幂次维护前缀和，是 \(O(n\log n)\) 的。
点击查看代码
#include<bits/stdc++.h>
using ll=long long;
ll n,a[200005],ans;
namespace BF1{
std::priority_queue<ll,std::vector<ll>,std::greater<ll>> pq;
int main(){
for(int i=1;i<=n;++i){
while(!pq.empty())pq.pop();
pq.push(a[i]);ans++;
for(int j=i+1;j<=n;++j){
pq.push(a[j]);
while(pq.size()>1){
int x=pq.top();pq.pop();
if(x!=pq.top()){pq.push(x);break;}
pq.pop();pq.push(x+1);
}
(pq.size()==1)&&(ans++);
}
}
std::cout<<ans;
return 0;
}
}
bool flag=true;
namespace BF2{
ll sum[200005];
std::unordered_set<ll> s;
int main(){
for(int i=1;i<=n;++i)sum[i]=sum[i-1]+(1ll<<a[i]);
s.insert(0);
for(int i=1;i<=n;++i){
for(int j=0;(1ll<<j)<=sum[i];++j)(s.count(sum[i]-(1ll<<j)))&&(ans++);
s.insert(sum[i]);
}
std::cout<<ans;
return 0;
}
}
int main(){
freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin>>n;for(int i=1;i<=n;++i)std::cin>>a[i];
if(n<=5000)return BF1::main();
for(int i=1;i<=n;++i)if(a[i]>30){flag=false;break;}
if(flag)return BF2::main();
return assert(0),0;//qwq
}