2021-02-09-2月9日题解
题解¶
用线段树来维护某一区间的最小值，然后对 (0,n-1) 每一个数进行查询，定位到该数所在的最小区间（注意特判一个最小值对应多个区间这种情况），然后对该区间的最小值的 最小值 进行查询，如果这个区间的最小值都比该值大，则输出-1。
代码¶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
ll l,r,pos,min1,add;
};
ll n,q;
node tree[400500]={0};
struct node1
{
ll l,r;
};
vector<node1>v[100500];
ll num[100500]={0};
void build(ll t,ll l,ll r)
{
tree[t].pos=l;
tree[t].l=l;
tree[t].r=r;
tree[t].min1=-1;
tree[t].add=-1;
if(l==r)
return ;
ll mid=(l+r)/2;
build(2*t,l,mid);
build(2*t+1,mid+1,r);
return ;
}
void push_up(ll p)
{
if(tree[p*2].min1<tree[p*2+1].min1){
tree[p].min1=tree[p*2].min1;
tree[p].pos=tree[p*2].pos;
}else {
tree[p].min1=tree[p*2+1].min1;
tree[p].pos=tree[p*2+1].pos;
}
return ;
}
void push_down(ll t)
{
if(tree[t].add==-1)
return ;
tree[2*t].add=max(tree[t].add,tree[2*t].add); ///最小值中取最大
tree[2*t+1].add=max(tree[t].add,tree[2*t+1].add);
tree[2*t].min1=max(tree[t].min1,tree[2*t].min1);
tree[2*t+1].min1=max(tree[t].min1,tree[2*t+1].min1);
tree[t].add=-1;
return ;
}
void update(ll t,ll l,ll r,ll x)
{
if(l==tree[t].l&&r==tree[t].r)
{
tree[t].add=max(tree[t].add,x);
tree[t].min1=max(tree[t].min1,x);
return ;
}
push_down(t);
ll mid=(tree[t].l+tree[t].r)/2;
if(r<=mid)
update(2*t,l,r,x);
else if(l>mid)
update(2*t+1,l,r,x);
else
{
update(2*t,l,mid,x);
update(2*t+1,mid+1,r,x);
}
push_up(t);
return ;
}
void update(ll t,ll pos)
{
if(tree[t].l==tree[t].r)
{
tree[t].min1=1e9;
return ;
}
push_down(t);
ll mid=(tree[t].l+tree[t].r)/2;
if(pos<=mid)
update(2*t,pos);
if(pos>mid)
update(2*t+1,pos);
push_up(t);
return ;
}
node query(ll t,ll l,ll r)
{
if(tree[t].l==l&&tree[t].r==r)
{
return tree[t];
}
push_down(t);
ll mid=(tree[t].l+tree[t].r)/2;
if(r<=mid)
return query(2*t,l,r);
else if(mid<l)
return query(2*t+1,l,r);
else
{
node tree1=query(2*t,l,mid);
node tree2=query(2*t+1,mid+1,r);
if(tree1.min1<tree2.min1)
return tree1;
else
return tree2;
}
}
int main()
{
scanf("%lld%lld",&n,&q);
build(1,1,n);
for(ll i=1;i<=q;i++)
{
ll l,r,x;
scanf("%lld%lld%lld",&l,&r,&x);
l++,r++,x++;
update(1,l,r,x);
v[x].push_back({l,r});
}
ll flag=1;
for(ll x=1;x<=n&&flag;x++)
{
ll l=1,r=n;
for(int i=0;i<v[x].size();i++)
{
l=max(l,v[x][i].l);
r=min(r,v[x][i].r);
}
if(l>r) ///一个最小值对应多个区间的情况
{
flag=0;
break;
}
node ans=query(1,l,r);
if(ans.min1>x)
{
flag=0;
break;
}
ll pos=ans.pos;
num[pos]=x-1;
update(1,pos);
}
if(!flag)
{
for(ll i=1;i<=n;i++)
{
printf("-1 ");
}
printf("\n");
}
else
{
for(ll i=1;i<=n;i++)
{
printf("%d ",num[i]);
}
printf("\n");
}
return 0;
}
题解¶
路径可以拼凑成一个长方形，只需要暴力找到这个长方形即可，注意如果两个点在同一条直线上则需要将两个点错开。
代码¶
#include <stdio.h>
#include <math.h>
#include <bits/stdc++.h>
using namespace std;
int x1,x2,y1,y2;
int px,py,dis=0;
int judge1(int x,int y)
{
int dis1=abs(x1-x)+abs(y1-y);
if(dis1>dis)
px=x,py=y,dis=dis1;
}
int main()
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1==x2)
x1++;
if(y1==y2)
y1++;
judge1(x2+1,y2+1);
judge1(x2+1,y2);
judge1(x2+1,y2-1);
judge1(x2,y2+1);
judge1(x2,y2-1);
judge1(x2-1,y2+1);
judge1(x2-1,y2);
judge1(x2-1,y2-1);
printf("%d\n",dis*2);
}
题解¶
根据题意直接标记模拟即可。
代码¶
#include <stdio.h>
#include <math.h>
#include <bits/stdc++.h>
using namespace std;
char a[2000]={0};
map<char,int>s;
map<int,int>k;
char b[2000][2000]={0};
map<char,int>mp1;
map<char,int>mp;
int main()
{
int n;
scanf("%d",&n);
scanf("%s",a+1);
for(int i=1;i<=n;i++)
{
if(a[i]=='*')
k[i]=1;
else
s[a[i]]=1;
}
int m;
scanf("%d",&m);
int sum=0;
for(int i=1;i<=m;i++)
{
scanf("%s",b[++sum]+1);
int flag=1;
for(int j=1;j<=n&&flag;j++)
{
if(k[j]&&s[b[sum][j]])
flag=0;
else if(!k[j]&&b[sum][j]!=a[j])
flag=0;
}
if(!flag)
sum--;
}
for(int i=1;i<=sum;i++)
{
mp.clear();
for(int j=1;j<=n;j++)
{
if(k[j])
{
if(!mp[b[i][j]])
{
mp[b[i][j]]=1;
mp1[b[i][j]]++;
}
}
}
}
int ans=0;
for(char i='a';i<='z';i++)
{
if(mp1[i]==sum)
ans++;
}
cout<<ans<<endl;
}
题解¶
将u替换为oo，kh替换为h，然后找相同的字符串即可。
代码¶
#include <stdio.h>
#include <math.h>
#include <bits/stdc++.h>
using namespace std;
char a[500][500]={0};
int ans[500]={0};
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",a[i]+1);
}
for(int i=1;i<=n;i++)
{
stack<char>s;
for(int j=1;a[i][j];j++)
{
if(a[i][j]=='u')
{
s.push('o');
s.push('o');
}
else if(a[i][j]=='h')
{
while(!s.empty()&&s.top()=='k')
s.pop();
s.push('h');
}
else
{
s.push(a[i][j]);
}
}
int sum=0;
while(!s.empty())
{
a[i][++sum]=s.top();
s.pop();
}
a[i][++sum]='\0';
}
int ans1=0;
for(int i=1;i<=n;i++)
{
if(ans[i])
continue;
for(int j=i+1;j<=n;j++)
{
if(strcmp(a[i]+1,a[j]+1)==0)
{
ans[j]=1;
ans1++;
}
}
}
cout<<n-ans1<<endl;
}
题解¶
找最大相同长度的回文字符串，可以发现构造 abcba 这种字符串（两边为能够匹配的字母，中间为不能匹配的）能够最小程度的减少块数，提高长度，用堆栈来模拟这个过程即可。
代码¶
#include <stdio.h>
#include <math.h>
#include <bits/stdc++.h>
using namespace std;
char a[400500]={0};
map<char,int>mp;
stack<char>s1,s2;
queue<char>que2;
int main()
{
int n;
scanf("%d",&n);
scanf("%s",a+1);
for(int i=1;i<=n;i++)
mp[a[i]]++;
for(char i='a';i<='z';i++)
{
if(mp[i]%2==1)
que2.push(i);
for(int j=1;j<=mp[i]/2;j++)
{
s1.push(i);
s2.push(i);
}
}
for(char i='0';i<='9';i++)
{
if(mp[i]%2==1)
que2.push(i);
for(int j=1;j<=mp[i]/2;j++)
{
s1.push(i);
s2.push(i);
}
}
for(char i='A';i<='Z';i++)
{
if(mp[i]%2==1)
que2.push(i);
for(int j=1;j<=mp[i]/2;j++)
{
s1.push(i);
s2.push(i);
}
}
if(que2.size()==0)
{
printf("%d\n",1);
stack<char>s;
while(!s1.empty())
s.push(s1.top()),s1.pop();
while(!s.empty())
printf("%c",s.top()),s.pop();
while(!s2.empty())
printf("%c",s2.top()),s2.pop();
}
else
{
while(s1.size()%que2.size()!=0)
{
que2.push(s1.top());
s1.pop();
que2.push(s2.top());
s2.pop();
}
printf("%d\n",que2.size());
int size1=s1.size()/que2.size();
while(!que2.empty())
{
stack<char>s;
for(int i=0;i<size1;i++)
s.push(s1.top()),s1.pop();
while(!s.empty())
printf("%c",s.top()),s.pop();
printf("%c",que2.front()),que2.pop();
for(int i=0;i<size1;i++)
printf("%c",s2.top()),s2.pop();
printf(" ");
}
}
}
题解¶
二分最大差值，然后用dp来进行check()
代码¶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[300500]={0};
int dp[300500]={0};
int n,m;
int check(ll k)
{
for(int i=1;i<=n;i++)
dp[i]=0;
dp[0]=1;
int last=1;
for(int i=1;i<=n;i++)
{
while(a[i]-a[last]>k)
last++;
for(int j=last;j+m<=i+1;j++)
{
if(dp[j-1])
{
dp[i]=1;
break;
}
else
{
last++;
}
}
}
return dp[n];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
ll l=0,r=2e9;
while(l<r)
{
ll mid=(l+r)/2;
if(check(mid))
r=mid;
else
l=mid+1;
}
cout<<l<<endl;
}