Problem B:
题意:给出[1..n]排列,找到一对(i,j) 要求i<j以及a[i]<a[j],并且j-i尽量大.n<=1e5.
记录每个数位置以后 按数值排序,则比a[i]大的a[j]都在a[i]之后 和a[i]最大距离为mx-pos,找到此时后缀i位置的最大值mx即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+20;
struct node{
int id,x;
}a[N];
bool cmp(node a,node b)
{return a.x<b.x;}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i].x),a[i].id=i;
sort(a+1,a+1+n,cmp);
int mx=0,ans=-1;
for(int i=n;i>=1;i--)
{
ans=max(ans,mx-a[i].id);
mx=max(a[i].id,mx);
}
if(ans<=0)
ans=-1;
printf("%d\n",ans);
return 0;
}
Problem C:
题意:n个白点落在x轴上,现在选k个点染成黑色,定义花费为某个白点到其距离最近的黑点.
n<=1e5,0<=x[i]<=1e9,现在要求最小化最大花费.
最小化最大啥的 二分最大花费,显然可以记录最左边的点p,当dis(x[i+1]-x[p])>mid 则对i染色
二分最值,判定染色点数是否超过k即可
注意更新左端点(超出a[pos]+mid的第一个点)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+20;
int a[N],n,k;
bool check(ll y)
{
int cnt=0,i=1;
while(i<=n)
{
int L=a[i];
while(i+1<=n&&a[i+1]-L<=y)
i++;
L=a[i]+y;
while(i<=n&&a[i]<=L)
i++;
// a[i] new leftpoint
cnt++;
}
return cnt<=k;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
ll l=0,r=2e9;
while(l<=r)
{
ll m=(l+r)>>1;
if(check(m))
r=m-1;
else
l=m+1;
}
cout<<r+1<<endl;
return 0;
}Problem D:
题意:若一个数,其相邻digit差值小于等于1 则定义该数为合法的.
给出n,k,问n以后第k个合法的数是多少? n,k<=1e18 .答案也在1e18内.
n以后第k个合法的数? 好像做过这种套路..设f[n]为小于n的合法数的个数.然后二分找到第一个x满足f(x)-f(n)=k的即可.
现在求f(n) 标准的数位"DP", dp[i][j] 还要i位数,当前位为j时的合法个数
注意点:
下一位为j-1,j,j+1注意不超过n.当前为前导0和非前导0的转移状态不同.
dp[pos][sta] sta为0时 注意要只在非前导0下保存dp值.
然后这个上限要开大一点。。注意中间不要被爆LL.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxx (LL) 9000000000000000000
#define LL long long
const int N=3e2+20;
ll k,n,a[N];
ll dp[N][N];
ll dfs(ll pos,ll sta,bool flag,bool limit)
{
if(pos==0)
return 1ll;
if(!limit&&dp[pos][sta]!=-1&&(!flag))
return dp[pos][sta];
ll res=0;
if(flag)
{
for(ll i=0ll;i<=9ll;i++)
res+=dfs(pos-1ll,i,i==0,false);
}
else
{
for(ll i=max(0ll,sta-1ll);i<=min(sta+1ll,9ll);i++)
{
if(limit&&i>a[pos])
break;
res+=dfs(pos-1,i,false,limit&&i==a[pos]);
}
}
if(!limit&& !flag)
dp[pos][sta]=res;
return res;
}
ll calc(ll x)
{
memset(dp,-1,sizeof(dp));
ll res=0,pos=0;
while(true)
{
a[++pos]=x%10,x/=10;
if(x==0)
break;
}
for(int i=0;i<=a[pos];i++)
res+=dfs(pos-1,i,i==0,i==a[pos]);
return res;
}
int main()
{
ios::sync_with_stdio(false);
LL i,j,n,m,x,st,en,mid,c;
cin>>m>>n;
x=calc(n);m+=x;
st=0; en=c=maxx;
while(st<=en)
{
//cout<<mid<<' ';
mid=((en-st)>>1)+st;
x=calc(mid);
if(x>=m)c=min(c,mid),en=mid-1;
else st=mid+1;
}
cout<<c<<endl;
return 0;
}
Problem E:
题意:给出n个字符串,问有多少对(i,j)满足s[j]连在s[i]后面使得新的串为回文.
n<=1e5,总的字符串长度<=1e5.
s=a+b为回文 则a[1]=b[m],a[2]=b[m-1],...a[n]=b[1] b'为b的反转 则a=b'.
计算每个字符串及其反转串的hash值 枚举i判断有多少个反转串的hash值和s相同.
a,b' 因为长度,hash值不同连接后可能也为回文,[ bac,ccab.] [bac,ab] [aaaaaa,a]
当a为长度较长 则a[1]=b'[1],a[2]=b'[2]....a[i-1]=b'[m] 于是后缀i必须为回文.(a长度短类似)
枚举后缀时 怎么判断后缀i是不是回文.
b:a[n],a[n-1]...a[2],a[1].
a:a[1],a[2]....a[n-1],a[n];
知道前缀s[1..i]的哈希值 则可以知道(s[l..r]的哈希值= hash[r]-hash[l]*base^(r-l+1).
则hash(i,l[i])=rhash(1,l[i]-i+1).然后加上上crh[hash[a前缀i-1]]即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const int N=2e5+20;
const ll mod=(ll)(1e9+7),base=26ll;
ll pw[N];
string a[N],b[N];
int n,l[N];
map<ll,ll> mp;
ii h[N],rh[N];//with length
ll Hash[N],rhash[N];
map<ii,int> ch,crh;
ll get_hash(string s)
{
ll res=0;
for(int i=1;s[i];i++)
res=(res*base+s[i]-'a')%mod;
return res;
}
ll get(int i,int j,ll Hash[])
{
return (Hash[j]-Hash[i-1]*pw[j-i+1]+mod*mod)%mod;
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);
pw[0]=1;
for(int i=1;i<N;i++)
pw[i]=(pw[i-1]*base)%mod;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>b[i];
a[i]=b[i];
l[i]=a[i].size();
reverse(b[i].begin(),b[i].end());
a[i]=" "+a[i];//1-index
b[i]=" "+b[i];
}
ll ans=0;
for(int i=1;i<=n;i++)
{
h[i].first=get_hash(a[i]);
rh[i].first=get_hash(b[i]);
h[i].second=rh[i].second=l[i];
ch[h[i]]++;
crh[rh[i]]++;
}
//length=1
for(int i=1;i<=n;i++)
if(l[i]==1)
ans+=ch[h[i]]-1;
//equ length
for(int i=1;i<=n;i++)
{
if(l[i]!=1)
{
if(h[i]==rh[i])
ans+=ch[h[i]]-1;
else
ans+=ch[rh[i]];
}
}
//dif length
for(int i=1;i<=n;i++)
{
if(l[i]==1) continue;
for(int j=1;j<=l[i];j++)
{
Hash[j]=(Hash[j-1]*base+a[i][j]-'a')%mod;
rhash[j]=(rhash[j-1]*base+b[i][j]-'a')%mod;
}
for(int j=1;j<l[i];j++)// a has larger length
if(get(j+1,l[i],Hash)==get(1,l[i]-(j+1)+1,rhash))//suf[i] is palindromic
ans+=crh[ii(get(1,j,Hash),j)];
for(int j=l[i]; j>1; --j)
if(get(1, j-1, Hash)==get(l[i]-(j-1)+1, l[i], rhash))
ans+=(ch[ii(get(1, l[i]-j+1, rhash), l[i]-j+1)]);
}
cout<<ans<<endl;
return 0;
}