牛客多校2019 第三场
按难度补题， 深感自己越来越菜。
题目顺序 分别是 B H J F D G 其他待补
Crazy Binary String
题意
就是给你一个01字符串，让你求01个数相等的子串和子序列长度。
首先是子序列就很简单，即.
接下来是求子串的的长度，比赛的时候傻缺了，写前缀和的时候wa了几发。
主要就是求当前位置之前0的个数，以及1的个数，然后做差。看差值相同的两个位置最大是多少。
这个也很好理解吧，就是满足两位置间的01个数相等，即 数组表示
的个数，
数组表示
的个数，化简即可得
但是在维护差值的时候，比赛时用的sort对差值进行排序。。还是犯了蠢，有 的解法，就在边算差值，边在前面找相同差值的位置，可以用map存。
#include <bits/stdc++.h>
using namespace std;
struct node{
int id;
int ans;
}num[100005];
int cmp(node a,node b){
if(a.ans==b.ans) return a.id<b.id;
return a.ans<b.ans;
}
int main()
{
int a=0,b=0;
string s;
int n;
cin>>n;
cin>>s;
for(int i=0;i<s.length();i++){
num[i].id=i;
num[i].ans=a-b;
if(s[i]=='0') a++;
else b++;
}
num[n].id=n;
num[n].ans=a-b;
int t=2*min(a,b);
sort(num,num+s.length()+1,cmp);
int maxn=0;
int sw=0;
for(int i=1;i<=n;i++){
if(num[i].ans==num[sw].ans) maxn=max(maxn,num[i].id-num[sw].id);
else sw=i;
}
cout<<maxn<<' '<<t<<endl;
return 0;
}Magic Line
题意
给你n个二维平面点，你需要划一条线，满足线两边的点的个数相等，以及直线不能经过这n个点
思路也很简单
对点进行排序即可，我是对点进行按x从小到大排序，如果x相同则对y进行从小到大排序
然后对于每个点必定满足过该点的竖线平分点的个数（x不存在相同）
这样我们只需要找到最中间的那个点，然后过这个点的竖线，稍微倾斜以及向上平移一点，即满足题目要求
中间点有两个，我们找靠左边的那个点即可
#include <bits/stdc++.h>
using namespace std;
struct node{
int x,y;
}point[100005];
int cmp(node a,node b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int main()
{
int n,m;
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<n;i++) cin>>point[i].x>>point[i].y;
sort(point,point+n,cmp);
node s=point[n/2-1];
cout<<s.x-1<<' '<<s.y+999000000+1<<' '<<s.x+1<<' '<<s.y-999000000<<endl;
}
return 0;
}LRU management
题意
J题怎么说呢，像签到但是卡常？ 也可能是我的写法的问题
题目大意就是说 给你一个容器，满足插入和查询两个需求，并且容器大小为
首先是数据，数据有两个值一个是名字，一个是值
插入数据，首先是去容器里找有没有这个名字，如果有则把这个数据移到末尾，并不改变值 ，如果没有，则在末尾加上这个数据，输出
值即可。，如果容器满了，就删掉第一个数据。
查询，就是找当前数据的左右或者当前值是否存在，存在输出数据的值即可
就是一道模拟题，用map+list存即可，但是就是t了，可能是我写法有问题
然后改成了unordered_map 存 list的迭代器
具体实现看代码吧。
#include <bits/stdc++.h>
using namespace std;
struct node
{
int v;
string s;
node() {}
node (string s,int v): s(s),v(v) {}
};
list<node> ls;
unordered_map<string,list<node>::iterator> mp;
//读入优化
inline int read(){
char ch, c;
int res;
while (ch = getchar(), ch < '0' || ch > '9') c = ch;
res = ch - 48;
while (ch = getchar(), ch >= '0' && ch <= '9')
res = (res << 3) + (res << 1) + ch - 48;
if (c == '-') res = -res;
return res;
}
int main()
{
int n,m;
ios::sync_with_stdio(false);
int t;
t=read();
while(t--)
{
ls.clear();
mp.clear();
n=read();
m=read();
int opt,v;
char s[20];
for(int i=0; i<n; i++)
{
opt=read();
scanf("%s",s);
v=read();
if(opt==0)
{
if(mp.find(s)!=mp.end())
{
auto sw=mp[s];
v=sw->v;
ls.erase(sw);
}
printf("%d\n",v);
node a(s,v);
ls.push_back(a);
mp[s]=prev(ls.end());
if(ls.size()>m)
{
auto sw=ls.begin();
mp.erase(sw->s);
ls.pop_front();
}
}
else
{
if(mp.find(s)==mp.end()) printf("Invalid\n");
else
{
auto sw=mp[s];
if((v==1&&next(sw)==ls.end())||(v==-1&&sw==ls.begin())) printf("Invalid\n");
else
{
if(v==1) sw=next(sw);
else if(v==-1) sw=prev(sw);
printf("%d\n",sw->v);
}
}
}
}
}
return 0;
}Planting Trees
题意
一个二维平面内的每个点都有个树，树有高度。
然后让你找一个最大区域，满足区域內任意两树的高度差
思路就是枚举上下边界，然后再枚举一个左边界，然后二分啥的搞右边界，，会T的。
更好一点的思路就是再枚举了左边界之后，用两个单调队列去维护区间内的最大值和最小值
然后就算区间最大和最小的差值就行
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=505;
const int inf = 0x3f3f3f;
int main()
{
int n,m;
int minn[maxn],maxx[maxn];
int a[maxn][maxn];
int q[maxn],p[maxn];
int t;
ios::sync_with_stdio(false);
cin>>t;
while(t--){
int ans=0;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++) maxx[j]=-inf,minn[j]=inf;
for(int j=i;j<=n;j++){
int l1=1,l2=1;
int r1=0,r2=0;
int pos=1;
for(int k=1;k<=n;k++){
minn[k]=min(minn[k],a[j][k]);
maxx[k]=max(maxx[k],a[j][k]);
while(r1>=l1&&minn[q[r1]]>minn[k]) r1--;
q[++r1]=k;
while(r2>=l2&&maxx[p[r2]]<maxx[k]) r2--;
p[++r2]=k;
while(pos<=k&&l1<=r1&&l2<=r2&&(maxx[p[l2]]-minn[q[l1]]>m)){
pos++;
if(l2<=r2&&p[l2]<pos) l2++;
if(l1<=r1&&q[l1]<pos) l1++;
}
ans=max(ans,(j-i+1)*(k-pos+1));
}
}
}
cout<<ans<<endl;
}
return 0;
}Big Integer
题意
具体实现看 博客
我主要是通过看咖啡鸡的代码理解的。
主要是用欧拉定理算出最小循环节，然后通过最小循环节的因子去找个数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int inf = 0x3f3f3f;
ll a[maxn],b[maxn],vis;
int cnt;
ll n,m,p;
void calc(ll x){
cnt=0;
int j=2;
while(j*j<=x){
if(x%j==0){
cnt++;
a[cnt]=j;
b[cnt]=0;
while(x%j==0) b[cnt]++,x/=j;
}
j++;
}
if(x>1){
cnt++;
a[cnt]=x;
b[cnt]=1;
}
}
ll pow_mul(ll a,ll b,ll c){
ll ans=0;
while(b){
if(b&1) ans=(ans+a)%c;
b>>=1;
a=(a+a)%c;
}
return ans;
}
ll pow_mod(ll a,ll b,ll c){
a%=c;
ll ans=1;
while(b){
if(b&1) ans=pow_mul(ans,a,c);
b>>=1;
a=pow_mul(a,a,c);
}
return ans;
}
ll solve(ll d){
calc(d);
ll maxx=1;
ll ans=0;
for(int i=1;i<=cnt;i++) maxx=max(maxx,b[i]);
for(int i=1;i<=min(maxx,m);i++){
ll sum=1;
for(int j=1;j<=cnt;j++){
int s=(b[j]+i-1)/i;
for(int k=0;k<s;k++) sum=sum*a[j];
}
ans+=n/sum;
}
if(m>maxx){
ll sum=1;
for(int i=1;i<=cnt;i++) sum=sum*a[i];
ans+=(m-maxx)*(n/sum);
}
return ans;
}
int main()
{
int t;
cin>>t;
while(t--){
cin>>p>>n>>m;
if(p==2||p==5){
cout<<0<<endl;
continue;
}
else if(p==3){
cout<<n/3*m<<endl;
continue;
}
else{
calc(p-1);
//for(int i=1;i<=cnt;i++) cout<<a[i]<<' '<<b[i]<<endl;
ll d=p-1;
for(int i=1;i<=cnt;i++){
for(int j=1;j<=b[i];j++)
if(pow_mod(10,d/a[i],p)==1) d/=a[i];
}
//cout<<d<<endl;
cout<<solve(d)<<endl;
}
}
}
Removing Stones
题意
有n堆石子
问多少个石子区间，可以满足“石子总和若为偶数，那么可以两两取来自不同堆的石子，直到取完； 如果为奇数，那么排除其中一个，然后可以两两取来自不同堆的石子，直到取完” 如果区间的最大值大于其他数的和，就肯定不能清空了
题意转化一下就是 区间最大值小于等于区间和的区间个数
思路主要是看了咖啡鸡的代码，真的是又短又简练，咖啡鸡tql。
就是我们对于每个数都看把这个数当成最大值得左边界和右边界的和，然后求是否这个区间成立。
但是这里不好统计有多少成立的区间，于是便反向取，即求有多少不满足的区间。
具体实现看代码。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=300005;
ll a[maxn],l[maxn],r[maxn];
int main()
{
int t;
int n,m;
cin>>t;
while(t--){
cin>>n;
ll ans=1LL*n*(n+1)/2;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
int x=0,y=0;
while(i-x-1>=1&&a[i-x-1]+l[x]<a[i]){
l[x+1]=l[x]+a[i-x-1];
x++;
}
while(i+y+1<=n&&a[i+y+1]+r[y]<a[i]){
r[y+1]=r[y]+a[i+y+1];
y++;
}
for(int j=0;j<=x;j++){
while(l[j]+r[y]>=a[i]) y--;
ans-=y+1;
}
}
cout<<ans<<endl;
}
return 0;
}
爱玛科技公司福利 8人发布
