A. Verify Password
挨个判断即可，秒了。
#include<cstdio>
#include<cstring>
using namespace std;
const int N=25;
int T,n;
char str[N];
bool is_digit(char ch){return ch>='0'&&ch<='9';}
bool is_lowercase(char ch){return ch>='a'&&ch<='z';}
bool check()
{
for(int i=1;i<n;i++)
{
if(is_lowercase(str[i])&&is_digit(str[i+1])) return false;
if(is_lowercase(str[i])&&is_lowercase(str[i+1]) && str[i]>str[i+1]) return false;
if(is_digit(str[i])&&is_digit(str[i+1]) && str[i]>str[i+1]) return false;
}
return true;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%s",&n,str+1);
printf("%s\n",check()?"YES":"NO");
}
}
B. Increase/Decrease/Copy
因为 \(b\) 的长度只比 \(a\) 的长度大一，所以一定只会复制一次，分以下两种情况讨论:
- 在将 \(a_i\) 化为 \(b_i\) 的过程中经过了 \(b_{n+1}\)，此时只需要额外消耗复制的一次操作次数即可。
- 没有经过，这时需要找离 \(b_{n+1}\) 最近的来化成它，而这个值只可能是其中一个 \(a_i\) 或 \(b_i\)
对于第二种情况，刚开始做的时候我只记录了全局最大最小值，没有考虑到 \([1,2],[4,5]\) 要变成 \(3\) 这类情况并不是用全局最大最小值来计算，而是以单组最大最小值来计算，所幸很快就改对了。
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e6+5;
int T,n,a[N],b[N];
signed main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n+1;i++) scanf("%lld",&b[i]);
long long ans=0;
bool in_range=false;
for(int i=1;i<=n;i++)
{
int x=a[i],y=b[i];
if(x>y) swap(x,y); //make x<=y
ans+=y-x;
if(x<=b[n+1]&&b[n+1]<=y)
in_range=true;
}
ans++;
if(!in_range)
{
int add=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
int x=a[i],y=b[i];
if(x>y) swap(x,y); //make x<=y
if(b[n+1]<x) add=min(add,x-b[n+1]);
if(b[n+1]>y) add=min(add,b[n+1]-y);
}
ans+=add;
}
printf("%lld\n",ans);
}
return 0;
}
C. Job Interview
这道题做的还算顺，就是没开 long long 坑了我好一会，下次要开 long long 的地方一定要第一时间开上，不要想着后面在一个一个改。
在洛谷上发了一篇题解：点击这里。
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int T,n,m;
int prog[N],test[N];
long long sum_prog[N],sum_test[N],sum_ok[N];
int cnt_prog[N],cnt_test[N];
//以上变量含义见题解内容
//prog(rammer)程序员；test(er)测试员
long long getsum(long long sum[],int l,int r)
{
return sum[r]-sum[l-1];
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n+m+1;i++)
{
scanf("%d",&prog[i]);
sum_prog[i]=sum_prog[i-1]+prog[i];
}
for(int i=1;i<=n+m+1;i++)
{
scanf("%d",&test[i]);
sum_test[i]=sum_test[i-1]+test[i];
}
for(int i=1;i<=n+m+1;i++)
{
cnt_prog[i]=cnt_prog[i-1];
cnt_test[i]=cnt_test[i-1];
if(prog[i]>test[i]) //这个候选人是预备程序员
{
cnt_prog[i]++;
sum_ok[i]=sum_ok[i-1]+prog[i];
}
if(prog[i]<test[i]) //这个候选人是预备测试员
{
cnt_test[i]++;
sum_ok[i]=sum_ok[i-1]+test[i];
}
}
for(int pos=1;pos<=n+m+1;pos++)
{
int l=0,r=n+m+1+1;
while(l+1<r) //[1,l] ok; [r,n+m+1] exceeded
{
int mid=l+r>>1,prog_now=cnt_prog[mid]; //当前位置以前的预备程序员人数
if(prog[pos]>test[pos] && pos<=mid) prog_now--; //排除当前候选人
if(prog_now<=n) l=mid;
else r=mid;
}
int pos_prog=l;
l=0,r=n+m+1+1;
while(l+1<r) //[1,l] ok; [r,n+m+1] exceeded
{
int mid=l+r>>1,test_now=cnt_test[mid]; //当前位置以前的预备测试员人数
if(prog[pos]<test[pos] && pos<=mid) test_now--; //排除当前候选人
if(test_now<=m) l=mid;
else r=mid;
}
int pos_test=l;
long long ans=0;
if(pos_prog<pos_test) //程序员先满员，以后所有人只能当测试员
{
ans=getsum(sum_ok,1,pos_prog)+getsum(sum_test,pos_prog+1,n+m+1);
if(pos<=pos_prog) ans-=max(prog[pos],test[pos]); //排除当前候选人
else ans-=test[pos];
}
else if(pos_prog>pos_test) //测试员先满员，以后所有人只能当程序员
{
ans=getsum(sum_ok,1,pos_test)+getsum(sum_prog,pos_test+1,n+m+1);
if(pos<=pos_test) ans-=max(prog[pos],test[pos]); //排除当前候选人
else ans-=prog[pos];
}
else
{
if(pos_prog==n+m+1) //程序员和测试员数量刚好够
{
ans=getsum(sum_ok,1,n+m+1);
ans-=max(prog[pos],test[pos]);
}
else return -1; //为了防止出现意想不到的情况
//上面的 if/else 语句可以删去，只保留中间的处理部分
}
printf("%lld ",ans);
}
putchar('\n');
}
return 0;
}
D. Invertible Bracket Sequences
赛事没做起，赛后补的。
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+5,LogN=20;
int T,n;
char str[N];
int sum[N];
vector<int> pos[N];
long long ans=0;
namespace ST_Table{
int f[N][LogN];
int lg2[N];
void Init(int arr[])
{
for(int i=2;i<=n;i++)
lg2[i]=lg2[i>>1]+1;
for(int i=1;i<=n;i++)
f[i][0]=arr[i];
for(int k=1;k<=lg2[n];k++)
for(int i=1;i+(1<<k-1)-1<=n;i++)
f[i][k]=max(f[i][k-1],f[i+(1<<k-1)][k-1]); //[i,i+2^(k-1)-1]|[i+2^(k-1)][i+2^k-1]
return;
}
int query(int l,int r)
{
int p=lg2[r-l+1];
return max(f[l][p],f[r-(1<<p)+1][p]); //[l,l+2^p-1]|[r-2^p+1,r]
}
} //namespace ST_Table
void ClearData()
{
for(int i=1;i<=n;i++)
pos[i].clear();
ans=0;
return;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%s",str+1);
n=strlen(str+1);
for(int i=1;i<=n;i++)
{
if(str[i]=='(') sum[i]=sum[i-1]+1;
if(str[i]==')') sum[i]=sum[i-1]-1;
pos[sum[i]].push_back(i);
}
ST_Table::Init(sum);
for(int left=1;left<=n;left++)
{
int l=left-1,r=n+1;
while(l+1<r)
{
int mid=l+r>>1;
if(ST_Table::query(left,mid)<=sum[left-1]<<1) l=mid;
else r=mid;
}
int right=l;
vector<int> &vp=pos[sum[left-1]];
ans+=
(upper_bound(vp.begin(),vp.end(),right)-1) //last <=
-(lower_bound(vp.begin(),vp.end(),left)) //first >=
+1;
}
printf("%lld\n",ans);
ClearData();
}
return 0;
}