Codeforces 922 (Div. 2)
A Brick Wall
用$1\times k$ 的方格填满整个矩阵， $k$ 可以不同，要求水平放置的方格数量减竖直放置的方块数量最大，输出最大值。
可以全放水平的。
#include <iostream>
#include <cstdio>
inline int read();
namespace pro{
inline int read();
int solve(){
int T=read();
while(T--){
int n=read(),m;
m=read();
printf("%d\n",(m/2)*n);
}
return 0;
}
};
int main(){
#ifdef ONLINE_JUDGE
#else
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
return pro::solve();
}
inline int pro::read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/
B Minimize Inversions
给定两个排列，每次选择 $i,j$ ，分别交换两个排列中 $i,j$ 位置元素，最小化两个排列逆序对数量之和。
可以发现一个排列排序后再进行交换答案一定不优。
#include <iostream>
#include <cstdio>
#include <algorithm>
inline int read();
class node{
public:
int x,y;
}no[200005];
int tree[200005];
int lowbit(int x){
return (x)&(-x);
}
int query(int x){
int ans=0;
while(x>0){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
void add(int x,int y){
while(x<=200000){
tree[x]+=y;
x+=lowbit(x);
}
return ;
}
bool operator<(node a,node b){
return a.x<b.x;
}
namespace pro{
inline int read();
int solve();
};
int pro::solve(){
int T=read();
while(T--){
int n=read();
for(int i=1;i<=n;i++){
no[i].x=read();
}
for(int i=1;i<=n;i++){
no[i].y=read();
}
std::sort(no+1,no+n+1);
for(int i=1;i<=n;i++){
printf("%d ",no[i].x);
}
printf("\n");
for(int i=1;i<=n;i++){
printf("%d ",no[i].y);
}
printf("\n");
}
return 0;
}
int main(){
#ifdef ONLINE_JUDGE
#else
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
return pro::solve();
}
inline int pro::read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/
C XOR-distance
给定 $a,b,r$ ，求 $\min\limits_{x=0}^{r}{|({a \oplus x}) - ({b \oplus x})|}$ 。
其中 $\oplus$ 表示按位异或。
我们先只考虑 ${a \oplus x} \leq {b \oplus x}$ ，另一种情况交换 $a,b$ 即可。
按位考虑，如果 $a,b$ 在某一位相同，那么 $x$ 相应这位无论是什么不会影响答案。
从高位向低位遍历，如果存在某一位 $a$ 比 $b$ 大，后面的位就要尽可能让 $b$ 大于 $a$ 才能最小化答案。
所以找到第一位不一样的时候，使用 $x$ 使 $a$ 的这位大于 $b$ 的这位，后面的反之，即可最小化答案，并且保证答案最小。
可以发现即使考虑 $r$ 的限制，每一位的决策仍然互相独立，这是由二进制数的性质保证的。
#include <iostream>
#include <cstdio>
#include <cmath>
#define int long long
inline int read();
namespace pro{
inline int read();
int a[105],b[105],c[105];
int solve();
};
int pro::solve(){
int T=read();
while(T--){
int x=0;
int aa=read();
int bb=read();
int rr=read();
int bka=aa;
int bkb=bb;
int bkr=rr;
for(int i=1;i<=64;i++){
a[i]=aa%2;
b[i]=bb%2;
c[i]=rr%2;
aa/=2;
bb/=2;
rr/=2;
}
rr=bkr;
int ans=std::abs(bka-bkb);
x=0;
for(int i=64;i>=1;i--){
if(a[i]==b[i]){
continue;
}
if(a[i]<b[i]){
x=(x)|(1ll<<(i-1));
}
i--;
while(i>=1){
if(a[i]>b[i]){
if((x|(1ll<<(i-1)))<=rr){
x=x|(1ll<<(i-1));
}
}
i--;
}
break;
}
if(x<=rr&&(bka^x)>(bkb^x)){
ans=std::min(ans,(bka^x)-(bkb^x));
}
rr=bkr;
aa=bkb;
bb=bka;
bka=aa;
bkb=bb;
for(int i=1;i<=64;i++){
a[i]=aa%2;
b[i]=bb%2;
c[i]=rr%2;
aa/=2;
bb/=2;
rr/=2;
}
x=0;
rr=bkr;
for(int i=64;i>=1;i--){
if(a[i]==b[i]){
continue;
}
if(a[i]<b[i]){
x=(x)|(1ll<<(i-1));
}
i--;
while(i>=1){
if(a[i]>b[i]){
if((x|(1ll<<(i-1)))<=rr){
x=x|(1ll<<(i-1));
}
}
i--;
}
break;
}
if(x<=rr&&(bka^x)>(bkb^x)){
ans=std::min(ans,(bka^x)-(bkb^x));
}
printf("%lld\n",ans);
}
return 0;
}
signed main(){
#ifdef ONLINE_JUDGE
#else
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
return pro::solve();
}
inline int pro::read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/
D Blocking Elements
最难崩的一集。
在一个序列中选择若干个点，把序列划分成若干子序列，求出所有子序列的和，取最大值，然后与所有选出的数的和取最大值，最小化这个值。
二分是很明显的，然后考虑如何 check 。
不会 ，结束前 $6 min$ 想到，我们可以以 $dp_i$ 表示最后一个选择的数是 $i$ 的方案所有选出的数的和的最小值，转移时只用保证中间的区间和小于二分到的点即可。
然而我想了一个小时，这种行为可以称为 Genshin 。
并且没有调出来，joker行为。
注意DP转移实际上是后缀最小，单调队列或者高级数据结构均可解决。
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
inline int read();
class node{
public:
int pos,zhi;
node(int x=0,int y=0){
pos=x;
zhi=y;
return ;
}
}aa[100005];
bool operator < (node a,node b){
return a.zhi<b.zhi;
}
namespace pro{
inline int read();
int a[100005];
int n;
bool check(int mid);
int solve();
};
int tree[100005];
int lowbit(int x){
return (x)&(-x);
}
void add(int x,int y){
while(x<=100000){
tree[x]=std::min(tree[x],y);
x+=lowbit(x);
}
return ;
}
int query(int x){
int ans=0x3f3f3f3f3f3f3f3f;
while(x>0){
ans=std::min(ans,tree[x]);
x-=lowbit(x);
}
return ans;
}
int dp[100005];
bool pro::check(int mid){
int ansnow=0;
for(int i=1;i<=n;i++){
tree[i]=0x3f3f3f3f3f3f3f3f;
}
add(n+1,0);
for(int i=1;i<=n;i++){
dp[i]=0;
int to=std::lower_bound(a,a+i,a[i-1]-mid)-a;
dp[i]=query(n-to+1)+a[i]-a[i-1];
add(n-i+1,dp[i]);
}
int sum=0;
for(int i=n;i>=1;i--){
if(std::max(dp[i],sum)<=mid){
return 1;
}
sum+=a[i]-a[i-1];
}
return 0;
}
int pro::solve(){
int T=read();
while(T--){
n=read();
int sum=0;
for(int i=1;i<=n;i++){
a[i]=read();
sum+=a[i];
a[i]+=a[i-1];
aa[i].zhi=a[i];
aa[i].pos=i;
}
std::sort(aa+1,aa+n+1);
int l=0,r=n*1000000000ll+5;
while(r-l>3){
int mid=(l+r)/2;
if(check(mid)){
r=mid+1;
}else{
l=mid-1;
}
}
for(int i=l;i<=r;i++){
if(check(i)){
printf("%lld\n",std::min(i,sum));
break;
}
}
}
return 0;
}
signed main(){
#ifdef ONLINE_JUDGE
#else
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
return pro::solve();
}
inline int pro::read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/
E ace5 and Task Order
交互题，有一个长度为 $n$ 的排列 $a$，交互库内生成一个 $x$ ，保证 $x \in [1,n]$ 。
你可以每次给出询问 $i$ 。
给定 $a_i$ 和 $x$ 的关系。
若 $a_i > x$ ，$x$ 自加 $1$ 。
若 $a_i < x$ ，$x$ 自减 $1$ 。
在 $40n$ 的次数内求出排列并报告。
实际上我们可以发现只要次数足够多，你可以把 $x$ 变成任意一个排列中的数，一直对着这个数操作直到等于即可。
然后我们可以发现，变成某个数之后，如果查询了其他数，再查询原来那个数无论如何都可以再变回去。
实际上这样就可以模拟快排了。
虽然快排是一种玄学，但是随机打乱之后就是 玄上加玄 ，被卡的概率很小。
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
inline int read();
int id[2005];
char ask(int x){
printf("? %d\n",x);
fflush(stdout);
char temp=getchar();
while(temp!='<'&&temp!='>'&&temp!='='){
temp=getchar();
}
return temp;
}
std::queue<int>v1,v2;
void qsort(int l,int r){
if(l>=r){
return ;
}
int mid=id[(l+r)/2];
while(ask(mid)!='=');
for(int i=l;i<=r;i++){
if(id[i]==mid){
continue;
}
if(ask(id[i])=='<'){
v1.push(id[i]);
}else{
v2.push(id[i]);
}
ask(mid);
}
int now=l-1;
while(v1.size()>0){
id[++now]=v1.front();
v1.pop();
}
int tt=now;
id[++now]=mid;
while(v2.size()>0){
id[++now]=v2.front();
v2.pop();
}
qsort(l,tt);
qsort(tt+2,r);
return ;
}
int ans[2005];
int main(){
#ifdef ONLINE_JUDGE
#else
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
int T=read();
while(T--){
int n=read();
for(int i=1;i<=n;i++){
id[i]=i;
}
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::shuffle(id+1,id+n+1,std::default_random_engine(seed));
qsort(1,n);
printf("!");
for(int i=1;i<=n;i++){
ans[id[i]]=i;
}
for(int i=1;i<=n;i++){
printf(" %d",ans[i]);
}
printf("\n");
fflush(stdout);
}
return 0;
}
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/