Codeforces Round 1040 (Div. 2)（A~D,E1赛后写出）-拓冰建站

状态不佳，rating--，blog质量--，有点抱歉

A. Submission is All You Need

思路：mex操作优于max操作只限定于{0}，{0，1}，其他都是sum更优秀.所以直接判断0，1数量即可

吐槽：没判多余的0，wa了发

#include<iostream>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#include<functional>
#define ll                            long long
#define ull unsigned long long
#define lowbit(x) (x & -x)
#define endl "\n"//                           交互题记得删除
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
const ll maxn = 2e5 + 5;
ll ksm(ll x, ll y)
{ll ans = 1;while (y){if (y & 1){ans = ans * x % mod;}x = x * x % mod;y >>= 1;}return ans % mod;
}
void fio()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}
int main() {fio();ll t=1;cin>>t;while(t--){ll n;cin>>n;vector<ll>a(n+2);ll c0=0;ll c1=0;ll sum=0;for(ll i=1;i<=n;i++){cin>>a[i];c0+=(a[i]==0);c1+=(a[i]==1);if(a[i]>=2)sum+=a[i];}sum+=min(c0,c1)*2;ll u=min(c0,c1);c0-=u;c1-=u;sum+=c1+c0;cout<<sum<<endl;}return 0;
}

B. Pathless

思路：设sum为数组总和，如果s<sum随便顺序输出，如果s=sum则-1，如果s>sum，且s-sum的差不等于x * 2+y * 3(x>=0&&y>=0)，那么直接0021构造即可，否则怎么构造都无解

#include<iostream>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#include<functional>
#define ll                            long long
#define ull unsigned long long
#define lowbit(x) (x & -x)
#define endl "\n"//                           交互题记得删除
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
const ll maxn = 2e5 + 5;
ll ksm(ll x, ll y)
{ll ans = 1;while (y){if (y & 1){ans = ans * x % mod;}x = x * x % mod;y >>= 1;}return ans % mod;
}
void fio()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}
int main() {fio();ll t=1;cin>>t;while(t--){ll n,s;cin>>n>>s;vector<ll>a(n+2);ll sum=0;for(ll i=1;i<=n;i++)cin>>a[i],sum+=a[i];if(sum==s)cout<<-1<<endl;else if(s<sum){for(ll i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;}else {ll dd=s-sum;ll c0=0,c2=0;for(ll i=1;i<=n;i++){c0+=(a[i]==0);c2+=(a[i]==2);// c3+=(a[i]==3);}bool flag=0;for(ll j=0;j<=1000;j++){if(j*2<=dd){if((dd-j*2)%3==0){flag=1;break;}}}if(flag)cout<<-1<<endl;else {for(ll i=1;i<=n;i++){if(c0>0){c0--;cout<<0<<" ";}  else if(c2>0){c2--;cout<<2<<" ";}else {cout<<1<<" ";}}cout<<endl;}}}return 0;
}

C. Double Perspective

思路：显然如果构成了环，那么其的并集将会重复一次，所以考虑直接连边，然后直接dfs得出答案即可，可能是多个连通分量，每个点都去dfs一下即可（使用vis标记），不走已被vis标记过的点（防止成环）

吐槽：这个n * n<=9e6看得真难受

#include<iostream>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#include<functional>
#define ll                            long long
#define ull unsigned long long
#define lowbit(x) (x & -x)
#define endl "\n"//                           交互题记得删除
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
const ll maxn = 2e5 + 5;
ll ksm(ll x, ll y)
{ll ans = 1;while (y){if (y & 1){ans = ans * x % mod;}x = x * x % mod;y >>= 1;}return ans % mod;
}
void fio()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}
int main() {fio();ll t=1;cin>>t;while(t--){ll n;cin>>n;vector<vector<pair<ll,ll>>>g(n*2+4);for(ll i=1;i<=n;i++){ll l,r;cin>>l>>r;g[l].push_back({r,i<<1});g[r].push_back({l,i<<1|1});// b[i]={l,r};}vector<bool>vi(n*2+2,0);vector<ll>d;function<void(ll)>dfs=[&](ll x){vi[x]=1;for(auto [to,j]:g[x]){if(vi[to])continue;else {d.push_back(j/2);dfs(to);}}};for(ll i=1;i<=2*n;i++){if(vi[i]==0){dfs(i);}}cout<<d.size()<<endl;sort(d.begin(),d.end());for(auto j:d)cout<<j<<" ";cout<<endl;}return 0;
}

D. Stay or Mirror

思路：这道题分类讨论下，讨论x和2 * n-x产生的必定贡献，谁更小选谁，相等选x(不知道选n * 2-x是否一样)。这个思路没有严谨证明，赛时想了下试了下就过了。

#include<iostream>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#include<functional>
#define ll                            long long
#define ull unsigned long long
#define lowbit(x) (x & -x)
#define endl "\n"//                           交互题记得删除
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
const ll maxn = 2e5 + 5;
ll ksm(ll x, ll y)
{ll ans = 1;while (y){if (y & 1){ans = ans * x % mod;}x = x * x % mod;y >>= 1;}return ans % mod;
}
void fio()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}
int main() {fio();ll t = 1;cin >> t;while (t--) {ll n;cin >> n;vector<ll>a(n + 2);for (ll i = 1; i <= n; i++)cin >> a[i];vector<ll>vis(n * 2 + 5, 0);for (ll i = 1; i <= n; i++) {ll l = min(a[i], 2 * n - a[i]);ll r = max(a[i], 2 * n - a[i]);ll c1 = 0, c2 = 0;vector<ll>now(n * 2 + 5, 0);for (ll j = r - 1; j >= 1; j--) {if (vis[j] == 0 && now[j] == 0 && 2 * n - j <= r - 1) {now[j] = now[2 * n - j] = 1;c1++;}}ll c3 = 0;for (ll j = r + 1; j <= 2*n; j++) {if (vis[j] == 1)c3++;}for (ll j = l + 1; j <= 2 * n; j++) {if (vis[j] == 1)c2++;}if (c2 <= c3 + c1) {a[i] = l;vis[r] = -1, vis[l] = 1;}else a[i] = r, vis[l] = -1, vis[r] = 1;}ll ans = 0;vector<bool>vi(n * 2 + 2, 0);for (ll i = 1; i <= n; i++) {for (ll j = a[i] + 1; j <= 2 * n; j++)ans += (vi[j] == 1);vi[a[i]] = 1;}cout << ans << endl;}return 0;
}

E1. Interactive RBS (Easy Version)

思路：二分出'('和')'的位置（设位置分别为x,y），然后两个两个扫，按照x i-1 i y的格式询问，因为如果(())答案为2,()()答案为3，至此答案得出。如果多了个位置，特判下即可

注意：由于还在重测中，这里给出的代码不一定对，但是大致思路一定可以过E1,E2要换形式了

#include<iostream>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#include<functional>
#define ll                            long long
#define ull unsigned long long
#define lowbit(x) (x & -x)
//#define endl "\n"//                           交互题记得删除
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
const ll maxn = 2e5 + 5;
ll ksm(ll x, ll y)
{ll ans = 1;while (y){if (y & 1){ans = ans * x % mod;}x = x * x % mod;y >>= 1;}return ans % mod;
}
void fio()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}
int main() {fio();ll t = 1;cin >> t;while (t--) {ll n;cin >> n;vector<char>a(n + 5);ll l = 2, r = n;while (l < r) {ll mid = l + r >> 1;cout << "? " << mid;for (ll i = 1; i <= mid; i++)cout << " " << i;cout << endl;cout.flush();ll x;cin >> x;if (x > 0)r = mid;else l = mid + 1;}ll a1 = r;cout << "? " << r;for (ll i = 1; i <= r; i++)cout << " " << i;cout << endl;cout.flush();ll x;cin >> x;if (x == 0)a1 = 1;l = 1, r = n-1;while (l <= r) {ll mid = l + r >> 1;cout << "? " << n-mid;for (ll i = mid+1; i<=n; i++)cout << " " << i;cout << endl;cout.flush();ll x;cin >> x;if (x > 0)l = mid + 1;else r = mid - 1;}ll a2=r;cout << "? " << n - r;for (ll i = r + 1; i <= n; i++)cout << " " << i;cout << endl;cout.flush();cin >> x;if (x == 0)a2 = n;for (ll i = 2; i <= n; i += 2) {cout << "? " << 4 << " " << a2 << " " << i - 1 << " " << i <<" "<< a1 << endl;cout.flush();   ll x;cin >> x;if (x == 3)a[i - 1] = ')', a[i] = '(';else a[i - 1] = '(', a[i] = ')';}if (n & 1) {cout << "? " << 2 << " " << n << " " << a1 << endl;cout.flush();ll x;cin >> x;if (x)a[n] = '(';else a[n] = ')';}cout << "! ";for (ll i = 1; i <= n; i++)cout << a[i];cout << endl;}return 0;
}