A
分类讨论 \(b+c\) 和 \(a\) 的大小即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
void solve(){
int a,b,c;
read(a),read(b),read(c);
if(b+c<a){
write_endl((b+c)*2+1);
}
else{
write_endl(a*2-1);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
B
可以发现因为每次选的是血最多的，所以影响实际死亡顺序的是最后一击前的血量。以血量模 \(k\) 的余数为第一关键字（如果血量模 \(k\) 的余数为 \(0\) 则看作余数为 \(k\)），以编号为第二关键字排序即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3e5+10;
int n,k;
struct node{
int id,val;
}a[N];
bool cmp(node x,node y){
return x.val==y.val?x.id<y.id:x.val>y.val;
}
void solve(){
read(n),read(k);
for(int i=1;i<=n;i++){
read(a[i].val);
a[i].val=(a[i].val-1)%k+1;
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
write_space(a[i].id);
}
putchar('\n');
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
C
每次排序时的前缀 \(0\) 和后缀 \(1\) 都是没有意义的，该在最前面的还在最前面，该在最后面的还在最后面。所以维护两个数组 \(nxt_i\) 表示 \([i,n]\) 中第一个 \(1\) 的位置，\(pre_i\) 表示 \([1,i]\) 中最后一个 \(0\) 的位置，每次排序会修改的部分只有 \([nxt_l,pre_r]\) 这个部分。注意的是当 \(nxt_l>pre_r\) 时，整个序列没有修改，将修改操作变为 \([0,0]\) 即可。答案为不同的操作数量，用 map 计数一下就行。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
int nxt[N],pre[N],n,m;
char s[N];
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
s[i]=getchar();
while(s[i]!='0'&&s[i]!='1'){
s[i]=getchar();
}
}
for(int i=1;i<=n;i++){
if(s[i]=='0'){
pre[i]=i;
}
else{
pre[i]=pre[i-1];
}
}
nxt[n+1]=n+1;
for(int i=n;i;i--){
if(s[i]=='1'){
nxt[i]=i;
}
else{
nxt[i]=nxt[i+1];
}
}
map<pii,int>vis;
for(int i=1;i<=m;i++){
int l,r;
read(l),read(r);
if(nxt[l]>pre[r]){
vis[mp(0,0)]=1;
}
else{
vis[mp(nxt[l],pre[r])]=1;
}
}
write_endl(vis.size());
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
D
对于一个非零段，如果从左端开始，则可以将该非零段的右边第一个 \(0\) 的位置染色，从右端开始则可以将左边第一个 \(0\) 的位置染色。如果有 \(2\)，可以从 \(2\) 的位置开始，将左右的第一个 \(0\) 都染色。所以我们先将有 \(2\) 的非零段和其左右的第一个 \(0\) 染色。剩下的 \(0\) 直接贪心染色。对于从左往右的每个非零段，如果左侧的第一个 \(0\) 未染色，则将其染色，否则将右侧的第一个 \(0\) 染色，最后剩下的 \(0\) 单独染一次色即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
int n,a[N],b[N];
void solve(){
int ans=0;
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1,j;i<=n;i=j+1){
int flag=0;
for(j=i;j<=n;j++){
if(!a[j]){
break;
}
flag=max(flag,a[j]);
}
if(flag==2){
ans++;
for(int k=i-1;k<=j;k++){
b[k]=1;
}
}
}
for(int i=1,j;i<=n;i=j+1){
int flag=0;
for(j=i;j<=n;j++){
if(!a[j]){
break;
}
flag=max(flag,a[j]);
}
if(flag==1){
ans++;
if(i>1&&!b[i-1]){
for(int k=i-1;k<j;k++){
b[k]=1;
}
}
else{
for(int k=i;k<=j;k++){
b[k]=1;
}
}
}
}
for(int i=1;i<=n;i++){
if(!b[i]){
ans++;
}
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
E
在确定右端点 \(j\) 的情况下，可能合法的区间有 \(j\) 个，令 \(f_i\) 表示左端点为 \(i\) 时区间的合法性。如果此时我们在后面加上一个 \(a_{j+1}\)，可能影响区间的情况只有 \(a_{j+1}\) 为新区间的最大值和区间最小值。\(a_{j+1}\) 是区间最大值会使区间变得合法，是区间最小值会使区间变得不合法。
可以预处理出 \([1,j]\) 中最后一个大于 \(a_{j+1}\) 的数的位置 \(mx_{j+1}\) 和最后一个小于 \(a_{j+1}\) 的数的位置 \(mn_{j+1}\)，如果不存在大于或不存在小于的数则为 \(0\)。如果 \(a_j\) 大于 \(a_{j+1}\) 则 \(a_{j+1}\) 会在左端点在一段区间中时最小值，将 \(f_{[mn_{j+1}+1,j]}\) 赋值为 \(0\)，反之则为最大值，将 \(f_{mx_{j+1}+1,j}\) 赋值为 \(1\)。用线段树维护 \(f\) 数组的权值，只需要实现区间赋 \(0/1\)，求所有权值和的操作。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e6+10;
int n,a[N],pre_mn[N],pre_mx[N],stk[N],top;
namespace Seg_Tree{
int ans[N<<2],tag[N<<2];
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
void f(int p,int l,int r,int val){
tag[p]=val+1;
ans[p]=(r-l+1)*val;
}
void push_down(int p,int l,int r){
if(tag[p]){
int mid=(l+r)>>1;
f(ls(p),l,mid,tag[p]-1);
f(rs(p),mid+1,r,tag[p]-1);
}
}
void push_up(int p){
ans[p]=ans[ls(p)]+ans[rs(p)];
}
void update(int p,int l,int r,int q_l,int q_r,int val){
if(q_l<=l&&r<=q_r){
f(p,l,r,val);
return;
}
int mid=(l+r)>>1;
push_down(p,l,r);
if(q_l<=mid){
update(ls(p),l,mid,q_l,q_r,val);
}
if(q_r>mid){
update(rs(p),mid+1,r,q_l,q_r,val);
}
push_up(p);
}
}
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1;i<=n;i++){
while(top&&a[stk[top]]>a[i]){
top--;
}
pre_mn[i]=stk[top];
stk[++top]=i;
}
top=0;
for(int i=1;i<=n;i++){
while(top&&a[stk[top]]<a[i]){
top--;
}
pre_mx[i]=stk[top];
stk[++top]=i;
}
int ans=0;
for(int i=2;i<=n;i++){
if(a[i-1]<a[i]){
Seg_Tree::update(1,1,n,pre_mx[i]+1,i-1,1);
}
else{
Seg_Tree::update(1,1,n,pre_mn[i]+1,i-1,0);
}
ans+=Seg_Tree::ans[1];
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
F
对于这种划分到两个集合的题要能够惯性想到二分图上去，想到二分图上后就好做了。
这里有两种做法解决本题。
第一种做法，二分答案，只连接异或和小于二分的权值 \(x\) 的边，判断是否为二分图即可，如果为二分图，则说明所有异或和小于 \(x\) 的数对都不同时在一个集合中，答案肯定大于等于 \(x\)。但这里有个问题，在 \(x\) 较大时，连的边是接近 \(n^2\) 的此时我们一次染色判断二分图复杂度太大，需要考虑优化建图。
有一个结论是，对于一个排好序的数组 \(val\)，如果存在一个 \(i\) 使得 \(x>val_i\oplus val_{i+4}\)，此时一定是无解。
证明：令 \(y=val_i\oplus val_{i+4}\)，\(y\) 的最高位为 \(a\)，必然的是 \(val_i\) 第 \(a\) 位为 \(0\)，\(val_{i+4}\) 的第 \(a\) 位为 \(1\)。根据鸽巢原理，\(val_i,val_{i+1},val_{i+2},val_{i+3},val_{i+4}\) 这 \(5\) 个数在第 \(a\) 位上至少有三个数相同，也就意味着至少会有三个数两两异或和小于 \(x\)，必然不是二分图，同理 \(x>val_i\oplus val_{i+5}\)，\(x>val_i\oplus val_{i+6}\) 等也是一样的。
这个结论让我们的边数从原来的 \(n^2\) 级别变成了与 \(n\) 同阶。如果无解，那么加上更多边一定无解；如果有解，那么问题就变成了是否会存在 \(x>val_i\oplus val_{i+4}\) 且不加该边时原图为二分图的情况，答案为不能。回到开始的分类讨论，假定 \(val_i,val_{i+1},val_{i+2}\) 第 \(a\) 位均为 \(0\)，那么在 \(i\) 连边时会连出奇环，假定 \(val_{i+2},val_{i+3},val_{i+4}\) 第 \(a\) 位为 \(1\)，那么在 \(i+2\) 连边时会连出奇环，所以上述问题所说的情况一定不存在。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
int n,a[N],col[N],val[N],pos[N],flag=0;
vector<pii>id;
vector<int>e[N];
void dfs(int u,int color){
col[u]=color;
for(auto v:e[u]){
if(!col[v]){
dfs(v,3-color);
}
if(col[v]!=3-color){
flag=0;
return;
}
}
}
bool check(int x){
for(int i=1;i<=n;i++){
e[i].clear();
col[i]=0;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=min(i+3,n);j++){
if((val[i]^val[j])<x){
e[i].pb(j);
e[j].pb(i);
}
}
}
flag=1;
for(int i=1;i<=n;i++){
if(!col[i]){
dfs(i,1);
}
}
return flag;
}
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
id.pb(mp(a[i],i));
}
sort(id.begin(),id.end());
for(int i=1;i<=n;i++){
pos[id[i-1].second]=i;
val[i]=id[i-1].first;
}
if(n==2){
puts("10");
return;
}
int l=1,r=(1<<30)-1,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
ans=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
check(ans);
for(int i=1;i<=n;i++){
write(col[pos[i]]-1);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
第二种做法，每次选出最小的边，要答案最大，这条边的两个端点显然应该属于不同集合。我们一直加边，直到加边后图不再是二分图。但其实没必要是图，一棵树就已经能够把哪个点属于哪个集合定下来了，根据这个思路，我们只需求出完全图的最小异或生成树，对其进行黑白染色，就是最后的划分结果。求完全图图的最小异或生成树类似于CF888G，感兴趣的可以直接看01trie，这里就不给出代码了。