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;
int n,s1,s2;
void solve(){
read(n);
s1=0,s2=0;
for(int i=1;i<=n;i++){
int x;
read(x);
if(x==1){
s1++;
}
else{
s2++;
}
}
if(s2%2==0){
if(s1-s2>0){
write_endl(0);
}
else{
int delta=-(s1-s2-1)/2;
write_endl((delta+1)/2*2);
}
}
else{
if(s1-s2>0){
write_endl(1);
}
else{
int delta=-(s1-s2-1)/2;
if(delta%2){
write_endl(delta);
}
else{
write_endl(delta+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
容易发现，将两个数位数补齐，找到第一个不同的位置，这一位取到极差，剩下为的差的绝对值都可以取到 \(9\)。令这一位 \(L'\) 取到 \(a\)，\(R'\) 取到 \(b(b>a)\)。那么对于后面的位数 \(L'\) 取 \(9\)，\(R'\) 取 \(0\)，显然 \(L'<R'\) 且 \(L',R'\in[L,R]\)。
点击查看代码
#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(){
string s,t,S="",T="";
cin>>s>>t;
for(int i=0;i<s.size();i++){
S=S+s[s.size()-i-1];
}
for(int i=0;i<t.size();i++){
T=T+t[t.size()-i-1];
}
int len=max(s.size(),t.size());
for(int i=s.size()+1;i<=len;i++){
S=S+'0';
}
for(int i=t.size()+1;i<=len;i++){
T=T+'0';
}
int ans=0;
for(int i=len-1;i>=0;i--){
if(S[i]!=T[i]){
int x=S[i]-'0',y=T[i]-'0';
ans+=abs(x-y);
ans+=i*9;
break;
}
}
write_endl(ans);
}
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
因为 Bob 只能在两个串中选择一个串操作，不能不操作，所以无论他两次操作的分别是哪两个串，两次操作后对应位还是对应，所以分类讨论 Bob 操作奇数次和偶数次，并可以得到对应时刻是 Bob 操作后结束还是 Alice 操作后结束。取较小值即可。
点击查看代码
#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;
int n;
string s,t;
void solve(){
read(n);
cin>>s>>t;
s=' '+s;
t=' '+t;
int tot1=0,tot2=0;
for(int i=1;i<=n;i++){
if(s[i]!=t[i]){
tot1++;
}
}
for(int i=1,j=n;i<=n;i++,j--){
if(s[i]!=t[j]){
tot2++;
}
}
int ans=1e9;
if(tot1%2){
ans=min(ans,tot1*2-1);
}
else{
if(tot1==0){
ans=min(ans,0);
}
else{
ans=min(ans,tot1*2);
}
}
if(tot2%2){
ans=min(ans,tot2*2);
}
else{
if(tot2==0){
ans=min(ans,2);
}
else{
ans=min(ans,tot2*2-1);
}
}
write_endl(ans);
}
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
如果给到最后造成极差的两个区间，考虑分类，两个区间是包含关系，相交关系，相离关系。
- 对于包含的情况，答案只有可能大区间的长度减去小区间的长度。
- 对于相离的情况，答案只有可能是大区间的长度。
- 对于相交的情况，答案为大区间的长度减去相交的长度，但这个不是很好处理，考虑转化为左边未相交的部分的长度和右边未相交部分的长度中的较大值，即 \(\max(l_i-l_j,r_i-r_j)\)。
于是我们有了一个简单的思路。将所有区间以右端点为关键字从小到大排序。通过二分可以找到相离的区间有哪些，这是一段前缀，我们可以动态维护前缀区间长度最大值。剩下的一段前缀的后缀里面有相交和包含关系的区间。根据前面的分析，我们可以用树状数组维护到 \(i-1\) 时，一段后缀中左端点的最小值，右端点的最小值，区间长度的最小值。
这里有一个问题，为什么我们不需要考虑将信息分相离和相交来维护。考虑如果一个被包含的区间 \(j\) 去用相交的答案计算方式去算会不会使答案变大，答案是不会。\(l_i-l_j\le 0\) 而 \(r_i-r_j\le r_i-r_j+l_j-l_i\)，故而答案不会更大。相交的线段用包含的方式去计算的答案也不会更大，所以直接用树状数组维护到 \(i-1\) 时，每个后缀的信息即可。
点击查看代码
#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,m;
struct seg{
int l,r;
}s[N];
bool cmp(seg x,seg y){
return x.r==y.r?x.l<y.l:x.r<y.r;
}
int c1[N],c2[N],c3[N],c4[N];
int lowbit(int x){
return x&(-x);
}
void update1(int pos,int val){
while(pos<=n){
c1[pos]=max(val,c1[pos]);
pos+=lowbit(pos);
}
}
int query1(int pos){
int ans=0;
while(pos){
ans=max(ans,c1[pos]);
pos-=lowbit(pos);
}
return ans;
}
void update2(int pos,int val){
pos=n-pos+1;
while(pos<=n){
c2[pos]=min(c2[pos],val);
pos+=lowbit(pos);
}
}
int query2(int pos){
pos=n-pos+1;
int ans=1e9;
while(pos){
ans=min(ans,c2[pos]);
pos-=lowbit(pos);
}
return ans;
}
void update3(int pos,int val){
pos=n-pos+1;
while(pos<=n){
c3[pos]=min(c3[pos],val);
pos+=lowbit(pos);
}
}
int query3(int pos){
pos=n-pos+1;
int ans=1e9;
while(pos){
ans=min(ans,c3[pos]);
pos-=lowbit(pos);
}
return ans;
}
void update4(int pos,int val){
pos=n-pos+1;
while(pos<=n){
c4[pos]=min(c4[pos],val);
pos+=lowbit(pos);
}
}
int query4(int pos){
int ans=1e9;
pos=n-pos+1;
while(pos){
ans=min(ans,c4[pos]);
pos-=lowbit(pos);
}
return ans;
}
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
c1[i]=0;
c4[i]=c2[i]=c3[i]=1e9;
read(s[i].l),read(s[i].r);
}
sort(s+1,s+n+1,cmp);
int ans=0;
for(int i=1;i<=n;i++){
int l=1,r=i-1,pos=0;
while(l<=r){
int mid=(l+r)>>1;
if(s[mid].r<s[i].l){
pos=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
ans=max(ans,max(query1(pos),(s[i].r-s[i].l+1)*(pos>0)));
ans=max(ans,max(s[i].l-query2(pos+1),s[i].r-query3(pos+1)));
ans=max(ans,s[i].r-s[i].l+1-query4(pos+1));
update1(i,s[i].r-s[i].l+1);
update2(i,s[i].l);
update3(i,s[i].r);
update4(i,s[i].r-s[i].l+1);
}
write_endl(ans*2);
}
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;
}
E
已知第 \(300001\) 个质数为 \(4256233\)，所以大于等于该数的 \(\operatorname{lcm}_{[l,r]}\) 值均为无效。给定 \(x\) 和 \(y\)，\(\operatorname{lcm}(x,y)\) 和 \(x\) 相比，要么不变，要么至少翻倍。所以给定一个 \(r\)，\(\operatorname{[l,r]}\) 不重且有效的 \(l\) 最多只有 \(\log\) 个。枚举 \(r\)，用 set 维护小于 \(4256233\) 的 \(\operatorname{[l,r-1]}\)，总复杂度为 \(O(n\log^2 V)\)，其中 \(V\) 表示值域。
点击查看代码
#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=3e5+10,MX=4256233;
int n,a[N];
set<int>now,lst,ans;
int lcm(int x,int y){
return x/__gcd(x,y)*y;
}
void solve(){
read(n);
set<int>().swap(ans);
set<int>().swap(lst);
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1;i<=n;i++){
set<int>().swap(now);
now.insert(a[i]);
for(auto x:lst){
int s=lcm(x,a[i]);
if(s<=MX){
now.insert(s);
}
}
set<int>().swap(lst);
for(auto x:now){
lst.insert(x);
ans.insert(x);
}
}
int mex=1;
while(ans.count(mex)){
mex++;
}
write_endl(mex);
}
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;
}