文章目录

C. Tree Diameter

题意： 有一个n个点的树，但我们不知道树的形态，需要求树的直径，你可以进行不大于10次询问，每次询问包含两个集合 x,y ,(x 与y交集为空), 之后会给出x集合中的点到y集合中的点最远的距离
分析: 本题的关键就是划分集合，你需要进行的10次询问必须将任意两个点的距离都清楚，这时候有趣的事情发生了，我们知道不同的树，二进制表达肯定不相同，所以我们可以将节点x按照二进制上的每一位是否为1划分两个集合，巧妙地利用二进制的特点

int main(void)
{
	int t;cin>>t;
	int n;
	while(t--){
		cin>>n;
		int M = 0;
		int a = 0;
		for(int i = 0;i < 10; ++i){
			// cout<<i<<" "<<endl;
			a = 0;
			for(int j = 0;j < n; ++j)
				if((j>>i)&1)
					a++;
			if(a == 0 ||a == n) break;
			cout<<a<<" "<<n-a<<" ";
			for(int j = 0;j < n; ++j)
				if((j>>i)&1)
					cout<<j+1<<" ";
			for(int j = 0;j < n; ++j)
				if(!((j>>i)&1))
					cout<<j+1<<" ";
			cout<<endl;
			int MM;cin>>MM;
			M = max(M,MM);
		}
		cout<<-1<<" "<<M<<endl;
	}
   return 0;
}

D - Frog Jumping

题意: 这个题绞尽脑汁想不通啊，看了题解写的是个垃圾啊，关键是那个出题人还以为自己说清楚了，然后看了别人的代码懂了
我的分析如下：
首先下结论：
如果 x &gt; a + b x &gt; a+b x>a+b,如果 g c d ( a , b ) ∣ x gcd(a,b) |x gcd(a,b)∣x ，那么肯定可以在 f(x) 是x就可达了，那么x的贡献就是(m-x+1)
如果 x &lt; a + b x &lt; a+b x<a+b,我们可以暴力算出 f ( x ) f(x) f(x) ，因为 a , b a,b a,b 的范围很小

我们不考虑f(x） 中不能超过x的限制，每一个d的倍数的贡献是多少呢
(n-id+1)
所有的d的倍数的贡献就是
∑ i = 1 i = m / d ∗ ( m − i d + 1 ) \sum_{i = 1}^{i = m/d}*(m-id+1) ∑i=1i=m/d​∗(m−id+1)
这是个等差数列
注释:
定理1：x能被表示，x-a 一定要能被表示
定理2 : 根据 欧几里得扩展定理， gcd(a,b) |x 这个条件肯定需要被满足

其它的深层次需要看代码

const int maxn = 3e5+10;
bool vis[maxn];
int ans = 0;
LL m,a,b;
void bfs(int x){
	if(vis[x]) return ;
	queue<int> q;
	q.push(x);
	vis[x] = 1,ans++;
	while(!q.empty()){
		int p = q.front();q.pop();
		if(p+a < x && !vis[p+a])
			q.push(p+a),vis[p+a] = 1,ans++;
		if(p-b > 0 && !vis[p-b])
			q.push(p-b),vis[p-b] = 1,ans++;
	}
}
LL Get(LL n){
	LL d = gcd(a,b);
	return n/d*(m+1)-(n/d)*(n/d+1)/2*d;
}
int main(void)
{
	cin>>m>>a>>b;
	LL cnt = 0;
	vis[0] = 1;
	ans = 1;
	for(int i = 0;i <= min(a+b,m); ++i){
		if(i-a>= 0&&vis[i-a])
			bfs(i);
		// cout<<i<<" "<<vis[2]<<endl;
		// cout<<i<<" "<<ans<<endl;
		cnt += ans;
	}
	LL Ans = cnt;
	// cout<<cnt<<endl;
	if(m > a+b){
		Ans += Get(m);
		Ans += (m-(a+b))*ans;
		Ans -= Get(a+b);
		// cnt -= Get(a+b);
	}
	cout<<Ans<<endl;
    

   return 0;
}