CodeForces 1491F Magnets 题解
标签:main math using push log amp map begin tor
好不容易自己做出来个 \(2700\) ...
首先我们对题目中的 \(n_1n_2 + s_1s_2 - n_1s_2 - n_2s_1\) 因式分解,得到 \(F = (n_1 - s_1)(n_2 - s_2)\)
也就是说,\(F \neq 0\) 当且仅当 \(n_1 \neq s_1\) , \(n_2 \neq s_2\) 。
然后,题目中说“至少有 \(2\) 个 \(N / S\) 的磁铁”,先考虑只有 \(2\) 个 \(N / S\) 的情况(一个子问题),我们必须得在 \(n\) 次操作内找出它们。
我们根据 \(F \neq 0\) 的条件思考,要构造出“一个磁铁在 \(L\) 集合中,另一个磁铁在 \(R\) 集合中”的情况。在排除各种千奇百怪的方法后,主要有以下 3 种:
1.对于每个 \(i\) ,询问:\(L[1,2,...,i-1], R[i+1,i+2,...,n]\)
2.对于每个 \(i\) ,询问:\(L[i], R[1,2,...,i-1,i+1,...,n]\)
3.对于每个 \(i\) ,询问:\(L[1,2,...,i-1], R[i]\)
然后推广到一般情况,1 可以扔掉,主要剩下后两种。
其实我一开始想的是 2,想了很长时间。中间还挺顺的,看似可以轻松出解,结果 \(|num_S - num_N| = 1\) 的情况实在做不了... (读者可以自己推一下试试)
然后灵光一现,想到了 3。
我们从左到右询问,第一次发现 \(F \neq 0\) ,说明当前位置肯定是第二个 \(N / S\) 的位置。然后继续向后问,可以轻松地把后面的问出来。
咦,怎么才 \(n - 1\) 次操作,题目中的限制不是 \(n + \lfloor \log n \rfloor\) 吗?是不是我错了?但我感觉很对啊!(当时想到这里,我还真的看了一下评测记录,看看大家是不是都带 \(\log\))
结果写程序的时候才发现,第一个 \(N / S\) 的位置还没求呢!当然,解决这个问题也很简单,二分一下就好了。这样询问次数就对上了。
这样就 A 了。
code(有点丑):
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define mit map<int,int>::iterator #define sit set<int>::iterator #define itrm(g,x) for(mit g=x.begin();g!=x.end();g++) #define itrs(g,x) for(sit g=x.begin();g!=x.end();g++) #define ltype int #define rep(i,j,k) for(ltype(i)=(j);(i)<=(k);(i)++) #define rap(i,j,k) for(ltype(i)=(j);(i)<(k);(i)++) #define per(i,j,k) for(ltype(i)=(j);(i)>=(k);(i)--) #define pii pair<int,int> #define fi first #define se second #define mpr make_pair #define pb push_back #define fastio ios::sync_with_stdio(false) const int inf=0x3f3f3f3f,mod=1000000007; const double pi=3.1415926535897932,eps=1e-6; int T,n; vector<int> ok; bool bad[2005]; int ask(int x,int l,int r){ printf("? %d %d\n",1,r-l+1); printf("%d\n",x); rep(i,l,r) printf("%d ",i); puts(""); fflush(stdout); int a;scanf("%d",&a);return a; } void solve() { rep(i,1,n) bad[i] = 0; ok.clear(); scanf("%d",&n); int lim = 0; rep(i,2,n) { lim = i; int x = ask(i,1,i-1); if(x) break; } ok.pb(lim); int l = 1, r = lim - 1; while(l < r) { int mid = (l + r) >> 1; if(ask(lim, 1, mid)) r = mid; else l = mid + 1; } ok.pb(l); rep(i,lim+1,n) if(ask(lim,i,i)) ok.pb(i); rap(i,0,ok.size()) bad[ok[i]] = 1; printf("! %d ",n - ok.size()); rep(i,1,n) if(!bad[i]) printf("%d ",i); puts("");fflush(stdout); } int main() { scanf("%d",&T); while(T--) solve(); return 0; }
标签:main math using push log amp map begin tor
原文地址:https://www.cnblogs.com/yz-beacon-cwk/p/14466410.html