赛后发现C被fst了/kk
本来能上分六十多，结果就上了十几
https://codeforces.com/problemset/problem/1362/A
比赛的时候写麻烦了，其实还有更简单的实现方法
inline int get(int x){
int ret=0;
ret+=x/3;x%=3;
ret+=x/2;x%=2;
ret+=x;
return ret;
}
int main(){
// std::printf("%d %d %d %d\n",get(1),get(8),get(7),get(12));
int T=read();while(T--){
LL a=read(),b=read();
int cnta=0,cntb=0,f=1;
while(a^b){
if(a>b){
if(a&1){
f=0;break;
}
a>>=1,cnta++;
}
else{
if(b&1){
f=0;break;
}
b>>=1,cntb++;
}
}
if(!f) std::puts("-1");
else std::printf("%d\n",get(cnta)+get(cntb));
}
return 0;
}
https://codeforces.com/problemset/problem/1362/B
给出一个集合，选出一个最小的正整数，使得用它异或集合内的每一个数，所得所有数组成的集合与原集合相同
\(|S|\le 1024,S_i\le 1024\)
对于任意 \(S_i\)，\(S_i\oplus k\) 如果也在 \(S\) 中，那么 \(k\) 符合要求
因为集合中的数互不相同，而两个不相同的数，异或后的结果必然不同
所以从 \(1\) 开始枚举 \(k\)，直到成立
那么如何知道它在什么情况下一定不成立？只要比 \(\max S_i\) 的二进制位多一位就可以
多出来的那一位 \(1\)，无法被异或掉（其它的数在这一位都是 \(0\)），也不可能等于任何原集合中的数
为了方便直接枚举到了最大数乘二
int t[10005],n;
int main(){int T=read();while(T--){
n=read();
int max=0;
for(reg int a,i=1;i<=n;i++){
a=read();
t[a]=1;max=std::max(max,a);
}
int maxx=max*2;
for(reg int f,i=1;i<=maxx;i++){
f=1;
for(reg int j=0;j<=max;j++)if(t[j]&&!t[j^i]){
f=0;break;
}
if(f){
std::printf("%d\n",i);
goto YES;
}
}
std::puts("-1");
YES:;
std::memset(t,0,sizeof t);
}
return 0;
}
https://codeforces.com/problemset/problem/1362/C
问从 \(0\) 到 \(n\)，每两个相邻的数的二进制表示中不同位数的个数和，是多少
\(n\le 10^{18}\)
一开始强行找了一波规律，发现并不明显
然后打了个表，放到oeis上，发现还真有
按照第一个公式写的，就是对于 \(n=2m+1\)，答案是：
其中，\(q=\lfloor\log_2 m\rfloor\)，而第 \(2m\) 项是第 \(2m+1\) 项减一
这玩意可以 \(O(\log n)\) 来算，所以写了一发交上去pretest过了，结果第二天以看fst了/kk，并不知道为什么
当然这个我也不会证明
然后才发现还有一个更简单的公式，答案是
也是 \(O(\log n)\)，赛后按这个写过了
这个还是可以稍微说明一下的，把它理解为对于每个二进制位一位一位地看
对于第 \(k\) 个（从 \(0\) 开始编号）二进制位（位权 \(2^k\)），那么其对答案的贡献是 \(\lfloor\dfrac{n}{2^k}\rfloor\)
也就是说，每 \(2^k\) 个数，\(k\) 位的数字会更改一次，对答案产生 \(1\) 的贡献
比如 \(k=2\)
001
010
011
100 <----改变了一次
101
110
111
(1)000<------改变了一次
为什么会这样应该挺好理解的，就是从 \(0\) 到 \(k\) 为上的所有数字累加一遍，就会改变一次
代码
signed main(){int T=read();while(T--){
LL n=read(),f=0;
if(n==1){
std::puts("1");continue;
}
LL ans=0;
for(reg LL now,k=1;;k*=2){
now=n/k;
if(!now) break;
ans+=now;
}
std::printf("%lld\n",ans);
}
return 0;
}
https://codeforces.com/problemset/problem/1361/A
一个无相图，每个点有点权，点权小于等于点数
对于一个选择点的顺序，为每个点确定一个实际的点权为：在与他相邻的点中，没有出现过的，最小的正整数
确定任意一种顺序，使得实际点权与给定点权相等
\(n,m\le 5\cdot 10^5\)
考虑什么时候一个点可以被选择，满足以下条件
点权小的点，要么影响不到点权大的点，要么可以使得点权大的点在考虑上述条件时成立
而点权大的点，无论如何影响不到点权小的点
所以按点权从小到大考虑这些点，判断它们是否满足要求
稍微说一下复杂度的事，用 exis[i] 表示点权为 \(i\) 的与当前点相邻，已经被选择的点（因为如果成立的话权值比他小的点都已经被选了，所以只要判权值大小就好了），是否存在
代码中的这一句话：
for(reg int k=1;k<t[u];k++)if(!exis[k]){f=0;break;}
因为最多有与 \(u\) 相邻的点数个数个数组元素被标为 \(1\)，所以最多枚举 \(\min(t_u,\text{与 }u\text{ 相邻的点的个数})\) 次，所以复杂度是正确的
#define N 500005
#define M 1000005
struct graph{
int fir[N],nex[M],to[M],tot;
inline void add(int u,int v){
to[++tot]=v;
nex[tot]=fir[u];fir[u]=tot;
}
}G;
int n,m;
int ans[N];
int t[N],exis[N],que[N];
std::vector<int>ver[N];
int main(){
n=read();m=read();
for(reg int a,b,i=1;i<=m;i++){
a=read();b=read();
G.add(a,b);G.add(b,a);
}
for(reg int i=1,a;i<=n;i++){
a=read();
ver[a].push_back(i);t[i]=a;
}
for(reg int size,i=1;i<=n;i++){
size=ver[i].size();
for(reg int u,j=0;j<size;j++){
u=ver[i][j];
que[0]=0;
for(reg int v,k=G.fir[u];k;k=G.nex[k]){
v=G.to[k];
if(t[v]<t[u]) exis[t[v]]=1,que[++que[0]]=t[v];
else if(t[v]==t[u]) return std::puts("-1"),0;
}
int f=1;
for(reg int k=1;k<t[u];k++)if(!exis[k]){f=0;break;}
for(reg int k=1;k<=que[0];k++) exis[que[k]]=0;
if(f) ans[++ans[0]]=u;
else return std::puts("-1"),0;
}
}
for(reg int i=1;i<=n;i++) std::printf("%d ",ans[i]);
return 0;
}
Codeforces Round #647 (Div. 2)(CF1362ABC,CF1361AB)
原文：https://www.cnblogs.com/suxxsfe/p/13052358.html