A
简单题
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
int n;
string s;
int main(){
n=input();
cin>>s;
cout<<n+1;
}
B
最长连续子串板子题，写个最长连续子串就OK了。但是要注意特判最长连续子串是否是整个串。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=1e5+7;
int n;
ll a[N];
int main(){
int T=input();
while(T--){
n=input();
ll sum=0;
for(int i=1;i<=n;i++){
a[i]=input();
sum+=a[i];
}
ll res=0,dp=0,len=0,rlen=0;
for(int i=1;i<=n;i++){
if(dp+a[i]<=0) dp=0,len=0;
else dp+=a[i],len++;
if(res<dp||(res==dp&&len<rlen))
res=dp,rlen=len;
}
// cout<<sum<<" "<<res<<" "<<rlen<<endl;
if(sum>res){
printf("YES
");
}else if(rlen==n&&a[n]!=0&&a[1]!=0) printf("YES
");
else printf("NO
");
}
}
C
不难想到用(sqrt{n})的时间来枚举因子，用(log n)的时间来判定因子是否互质。总复杂度(O(sqrt{n}log n))。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
ll x;
ll a,b;
int main(){
x=input();
for(ll i=1;i*i<=x;i++){
if(x%i==0){
if(__gcd(i,x/i)==1){
a=i,b=x/i;
}
}
}
printf("%lld %lld
",a,b);
}
D
对所有的数的二进制建立一棵0/1tire树，然后贪心dfs就好了。对于答案来说，如果所有的数的某一位如果全为1就填1，对于全为0就填0，如果即存在1的情况又存在0的情况就这一位填0还是1两种情况都找一下，最后取最小答案就好。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=1e5+7;
int t[N*30][2],cnt,Ans=1<<30;
void dfs(int rt,int dep,int val){
if(dep<0){
Ans=min(Ans,val);
return;
}
if(t[rt][0]&&t[rt][1])
dfs(t[rt][0],dep-1,val|(1<<dep)),
dfs(t[rt][1],dep-1,val|(1<<dep));
else if(t[rt][1]) dfs(t[rt][1],dep-1,val);
else dfs(t[rt][0],dep-1,val);
}
int main(){
int n=input();
for(int i=1;i<=n;i++){
int x=input();
int rt=0;
for(int j=30;~j;j--){
bool tmp= x>>j&1;
if(!t[rt][tmp])
t[rt][tmp]=++cnt;
rt=t[rt][tmp];
}
}
dfs(0,30,0);
printf("%d
",Ans);
}
E
首先避免离散化后求答案可能会导致冲突，把所有的(l)和(r)都乘(2)，然后把(l-1,l,l+1,r-1,r,r+1)都加入离散化数组中，离散化后，维护一个前缀和数组。我们知道如果删掉某一段可能会对答案产生贡献，唯一可能就是前缀和数组中为1的段，因此我们给这些全为1的段做一个标记，最后求答案时只要统计区间内有多少个标记就可以了，因此我们也可以通过前缀和维护标记的数量，但是要注意段的两端可能会出现减少答案的情况。最后还要考虑，所有段都不相交的情况。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
vector <ll> v;
int getid(ll x){
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
const int N=2e5+7;
#define PII pair<ll,ll>
#define fr first
#define sc second
#define mp make_pair
int T;
int n;
PII a[N];
int b[N*8],add[N*8],sum[N*8];
int main(){
T=input();
while(T--){
n=input();
for(int i=1;i<=n;i++){
a[i].fr=input()*2;
a[i].sc=input()*2;
v.push_back(a[i].fr-1);
v.push_back(a[i].fr+1);
v.push_back(a[i].fr);
v.push_back(a[i].sc+1);
v.push_back(a[i].sc);
v.push_back(a[i].sc-1);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
int cnt=v.size();
for(int i=0;i<=cnt;i++){
b[i]=add[i]=sum[i]=0;
}
for(int i=1;i<=n;i++){
a[i].fr=getid(a[i].fr),a[i].sc=getid(a[i].sc);
add[a[i].fr]++;
add[a[i].sc+1]--;
}
int tmp=0;
for(int i=1;i<=cnt;i++){
tmp+=add[i];
b[i]=tmp;
}
for(int i=1;i<=cnt;i++){
if(b[i]==1&&b[i-1]!=1) sum[i]=sum[i-1]+1;
else sum[i]=sum[i-1];
// cout<<sum[i]<<endl;
}
int bas=0;
for(int i=1;i<=cnt;i++){
if(b[i]==0&&b[i-1]!=0) bas++;
}
// cout<<":"<<bas<<endl;
int Ans=bas-1;
for(int i=1;i<=n;i++){
tmp=sum[a[i].sc]-sum[a[i].fr-1];
if(b[a[i].fr-1]==0&&b[a[i].fr]==1) tmp--;
if(b[a[i].sc+1]==0&&b[a[i].sc]==1) tmp--;
// cout<<tmp<<endl;
Ans=max(Ans,tmp+bas);
}
printf("%d
",Ans);
v.clear();
}
}