总结：
比赛链接，题面请到这里看，我就不搬了。
第一次打\(3h\)的\(CF\)，要打到\(1:30\)这是我从未体验过的。
做前面题的时候状态还不错，就是做\(B\)时没有注意到要开\(2\)倍空间吃了\(2\)个罚时
做\(F\)题的时候，完全没有往并查集的方向去想，一直纠结于线性基上，最终无功而返，\(1:10\)的时候就睡大觉了。
题解：
A. Bovine Dilemma
显然影响答案的只有选择的\(2\)个点的坐标之差，\(n\le 50\)，直接暴力枚举即可。
#include<bits/stdc++.h>
using namespace std;
const int N=100;
int t,n,x[N],dis[N];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
memset(dis,0,sizeof(dis));
for(int i=1;i<=n;++i){
scanf("%d",&x[i]);
for(int j=1;j<i;++j)
dis[x[i]-x[j]]=1;
}
int ans=0;
for(int i=1;i<=50;++i) if(dis[i])++ans;
cout<<ans<<endl;
}
return 0;
}
B. Last minute enhancements
从小到大扫一遍，假设当前查找的是\(x\)，如果前面没有出现过\(x\)那么就不变，否则让\(x+1\)
注意开记录数字是否出现过的数组要开\(2e5\)的空间
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int t,n,a[N],cnt[N],b[N];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;++i){
if(!cnt[a[i]]) cnt[a[i]]++;
else cnt[a[i]+1]++;
}
int ans=0;
for(int i=1;i<=2*n+1;++i)
if(cnt[i]) ++ans;
printf("%d\n",ans);
}
return 0;
}
C. Canine poetry
注意到如果不存在任何长度为\(2\)或\(3\)的回文串，那么一定不会有长度\(>3\)的回文串，所以我们只需要关心长度为\(2\)或\(3\)的回文串。
所以从左到右扫一遍，如果发现有以当前位置为结尾的长度\(=2\)或\(3\)的回文串，那么直接修改这个字符，注意到只要修改后让它与相邻的\(4\)个字符不一样，那么就不会出现回文串，所以我们有\(22\)种选择，可以认为它变成了一个与任何字符都不相同的独特字符。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int t,ch[N];
char s[N];
int main(){
scanf("%d",&t);
while(t--){
scanf("%s",s+1);
int n=strlen(s+1),ans=0;
ch[1]=0;
for(int i=2;i<=n;++i){
ch[i]=0;
if(s[i]==s[i-1]&&(!ch[i-1])) ++ans,ch[i]=1;
else if(i>2&&s[i]==s[i-2]&&(!ch[i-2])) ++ans,ch[i]=1;
}
printf("%d\n",ans);
}
return 0;
}
D. 13th Labour of Heracles
手玩一下样例我们会发现：
当只有一种颜色时，答案就是所有点权值和，当有\(2\)种颜色时，我们的收益就是将某一个度数\(>1\)的点所连接的任意\(2\)条边连上不同的颜色，就能额外增加这个点的贡献，以此类推。
于是直接开一个大根堆维护所有度数\(>1\)的点的权值，每增加一种颜色就取出堆顶，增加堆顶的权值并减少一个它的度数，如果它的度数依然\(>1\)再\(push\)进去即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int t,n,w[N],de[N];
ll ans;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
priority_queue<pair<int,int> >q;
ans=0;
for(int i=1;i<=n;++i) scanf("%d",&w[i]),ans+=w[i],de[i]=0;
for(int i=1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
de[u]++;de[v]++;
}
for(int i=1;i<=n;++i)
if(de[i]>1)
q.push(make_pair(w[i],i));
printf("%lld ",ans);
for(int i=2;i<n;++i){
ans+=q.top().first;int u=q.top().second;
q.pop();
--de[u];if(de[u]>1) q.push(make_pair(w[u],u));
printf("%lld ",ans);
}
puts("");
}
return 0;
}
E. Apollo versus Pan
题目要求：
交换和式发现：
注意到\(\sum_i(x_i\&x_j)\)与\(\sum_k(x_j|x_k)\)互不影响，假设前者是\(f(j)\)，后者是\(g(j)\)
那么我们\(ans=\sum_jf(j)g(j)\)
考虑如何求\(f(j)\)与\(g(j)\)，依次考虑\(x_j\)二进制下每一位的贡献，假设当前是从低至高第\(k\)位，若第\(k\)位是\(0\)，那么对\(f(j)\)的贡献一定是\(0\)，对于\(g(j)\)，每一个当前位上为\(1\)的数与\(x_j\)产生贡献，因此贡献就是\(2^k*w_k\)\((w_k\)为二进制下第\(k\)为\(1\)的数的个数\()\)。
同理，若第\(k\)位是\(1\)，那么，对\(f(j)\)的贡献是\(2^j*w_k\)，对\(g(j)\)的贡献是\(2^j*n\)
于是我们就能在$ \mathcal O(n\log \max(x_i))$的复杂度下解决此题了。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
const int mod=1e9+7;
typedef long long ll;
ll t,n;
ll x[N],w[62],s[N][62],ret[N],gx[62],re[N];
ll ans;
inline ll add(ll x,ll y){return (x+y>=mod)?x+y-mod:x+y;}
int main(){
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
ans=0;
for(int i=0;i<=60;++i) w[i]=0,gx[i]=(1ll<<i)%mod;
for(int i=1;i<=n;++i) scanf("%lld",&x[i]),ret[i]=0,re[i]=0;
for(int i=1;i<=n;++i){
for(int j=0;j<=60;++j){
s[i][j]=(x[i]>>j)&1;
w[j]+=s[i][j];
}
}
for(int i=1;i<=n;++i){
for(int j=0;j<=60;++j){
if(s[i][j]){
re[i]=add(re[i],1ll*gx[j]*w[j]%mod);
ret[i]=add(ret[i],1ll*gx[j]*n%mod);
}
else ret[i]=add(ret[i],1ll*gx[j]*w[j]%mod);
}
}
for(int j=1;j<=n;++j)
ans=add(ans,1ll*re[j]*ret[j]%mod);
printf("%lld\n",ans);
}
return 0;
}
F. Euclid's nightmare
首先我们可以将所有向量增加一维，认为只有\(1\)维是\(1\)的向量，在第\(m+1\)维也是\(1\)，这显然不会影响答案，于是我们就将所有向量转化为了有\(2\)维是\(1\)的向量。
同时，还有一个显然的性质：\(\left| T\right|=2^{\left|S'\right|}\)，这里的\(T\)和\(S'\)就是题目中要求的东西。
于是我们只需要知道哪些向量能由其他向量表示出来就行了，直观的想法是线性基，但复杂度太高。
如果把每个向量看作是连接那\(2\)维\((\)指是\(1\)的那两维\()\)的一条边，那么我们会发现如果另一个有\(2\)维是\(1\)的向量能由一些向量表示出来，那它所连接的\(2\)维之间一定有其他路径相连。
于是我们最后欠缺的就是一个并查集板子了，如果当前向量连接的两维不在同一集合内，就说明当前向量能被其他向量表示出来。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
const int mod=1e9+7;
int n,m,fa[N];
vector<int> ans;
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline bool merge(int x,int y){
x=find(x);y=find(y);
if(x!=y){fa[x]=y;return true;}
return false;
}
inline int ksm(int a,int b){
int ret=1;
for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ret=1ll*ret*a%mod;
return ret;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m+1;++i) fa[i]=i;
for(int i=1;i<=n;++i){
int k,x,y;scanf("%d%d",&k,&x);
if(k==1) y=m+1;
else scanf("%d",&y);
if(merge(x,y)) ans.push_back(i);
}
printf("%d %d\n",ksm(2,ans.size()),ans.size());
for(int i=0;i<ans.size();++i) printf("%d ",ans[i]);
return 0;
}
G、H、I
太神了，不会