A. Likes
分析
首先数据保证了一定合法，那只需要统计有几个负数。最大的策略是先把所有正数用完，然后把所有负数用完，可知答案一定是1 2 3 4 5 4 3这种形式；最小策略是加一个就直接把这个减去，最后再把只能加的加上，答案一定为1 0 1 0 1 0 1 2 3 4这种形式
代码实现
#include<bits/stdc++.h>
#define ll long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define no cout<<"No\n"
#define yes cout<<"Yes\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sol void solve
using namespace std;
int n,b[2000];
sol(){
int tem=0;
cin>>n;
rep(i,1,n){
cin>>b[i];
if(b[i]<0) tem++;
}
rep(i,1,n-tem){
cout<<i<<" ";
}
int ans=n-tem-1;
rep(i,n-tem+1,n){
cout<<ans<<" ";
ans--;
}
cout<<"\n";
rep(i,1,tem){
cout<<"1 0 ";
}
rep(i,1,n-tem*2){
cout<<i<<" ";
}
cout<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
B. Settlement of Guinea Pigs
分析
如何处理动物：
当有了3个未知动物时，经过确认，一定可以把其中两个合并到一个笼子里，那么现在剩下了一个存放单个动物的笼子。3个以上同理。所以遇到2时，只需要一直-2到不足3个动物。
处理笼子：
笼子最多的时间一定是某次输入1的时刻，刚开始想的时候想到每输入一次1就笼子数量++。但，每当输入2进行合并操作时，会空出一些笼子，所以在下次输入1时，先把之前空出的笼子用完，再笼子数量++。
代码实现
#include<bits/stdc++.h>
#define ll long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define no cout<<"No\n"
#define yes cout<<"Yes\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sol void solve
using namespace std;
int n,x;
sol(){
cin>>n;
int tem=0;
int ans=0;
int trans=0;
int fre=0;
rep(i,1,n){
cin>>x;
if(x==1){
tem++;
if(fre>0) fre--;
else trans++;
continue;
}
else{
while(tem>=3){
tem-=2; ans++; fre++;
}
}
}
trans=max(trans, tem+ans);
cout<<trans<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
C. The Very Beautiful Blanket
分析
每个元素的二进制分为左、右两部分。y坐标确定左部分，x坐标确定右部分。
如何划分y和x所属的不同部分？
如果有5列，那么列从左到右为000 001 010 011 100 -> x负责右边的三位二进制
行从上到下应该为00 01 10 11。。。对于某个元素，其二进制形式为 str（行二进制+列二进制）。
以上面的东西进行举例，A11为00 000，A12为00 001->1，A13为00 010->2，A21为01 000->8，A44为11 011->27。。。
为什么这样可行？对于某四个元素异或，两个数某部分二进制完全相同，那么这部分二进制经过异或就能变成0，所以经过这样构造，每个4*4子矩阵的异或都为0。
代码实现
#include<bits/stdc++.h>
#define ll long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define no cout<<"No\n"
#define yes cout<<"Yes\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sol void solve
using namespace std;
int n,m;
sol(){
cin>>n>>m;
int tem=m, cnt=0, inter=1;
while(tem){
tem>>=1;
inter<<=1;
}
tem=0;
cout<<n*m<<"\n";
rep(i,1,n){
int ttt=tem;
rep(j,1,m){
cout<<ttt<<" ";
ttt++;
}
tem+=inter;
cout<<"\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
D. Buying gifts
分析
题目让你把数据分为两个集合A、B，max(A)和max(B)的差距尽可能的小。
结构体存数据，然后按a降序排序。形成一个如下结构：
4 3 2 2 1
5 7 4 6 2
开始遍历a，以每次遍历到的a[i]作为A的最大值，那此时B的最大值应该是什么呢？
首先，遍历到a[i]，那么[1]～[i-1]一定属于集合B，那么可以用变量maxx维护max(b[1]～b[i-1])。
对于b[i+1]～b[n]的部分，可以将它们用一个multiset维护，每轮从中找到一个元素x>=a[i]，一个元素y<=a[i]，那么与a[i]“最亲近”的元素必然是maxx、x、y之一。如果maxx较大，就必须选maxx；否则，可以在x、y中挑选一个合适的元素。
代码实现
#include<bits/stdc++.h>
#define ll long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define no cout<<"No\n"
#define yes cout<<"Yes\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sol void solve
using namespace std;
const ll INF = 0x3f3f3f3f;
struct node{
ll a;
ll b;
}m[500005];
int n;
bool cmp(const node &xx, const node &yy){
return xx.a > yy.a;
}
sol(){
ll maxx=-INF;
multiset<ll> st({-INF, INF});
ll ans=1e9+2;
cin>>n;
rep(i,1,n){
cin>>m[i].a>>m[i].b;
st.insert(m[i].b);
}
sort(m+1,m+n+1,cmp);
rep(i,1,n) {
st.erase(st.find(m[i].b));
ans=min(ans, abs(m[i].a - max(maxx, *st.lower_bound(m[i].a)) ));//大于等于a[i]
ans=min(ans, abs(m[i].a - max(maxx, *prev(st.upper_bound(m[i].a))) ));//小于等于a[i]
maxx=max(maxx, m[i].b);
}
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
