当前位置：首页 > news >正文

2025牛客暑期多校训练营1(G,E,L,K,I)

news 2025/8/3 16:53:27

补题链接：牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

G.Geometry Friend

思路

就是问S字符串截掉前a个字符后，和T字符串有多少个相等的区间，如果有连续的x个字符相同那么他形成的区间数量便是x*(x+1)/2

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n,q;cin>>n>>q;string s;cin>>s;s=" "+s;while(q--){string T;cin>>T;int m=T.size();T=" "+T;int a;cin>>a;int r=1;int ans=0;while(r<=m){int cnt=0;int tr=r;while(tr<=m&&s[tr+a-1]==T[tr]){cnt++;tr++;}ans+=(cnt+1)*cnt/2;r=tr;r++;}cout<<ans<<"\n";}
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;// cin>>_;while(_--) solve();return 0;
}

E.Endless Ladders

思路

发现所有的两个不同数的平方差可以被表示成

$(k+1)^2-k^2=2*k+1(k>0)$

$(k+1)^2-(k-1)^2=4*k (k\geqslant 1)$

其实打表的话也能发现规律，那么答案不就是x=a*a-b*b, $ans=\left \lfloor \frac{x}{2} \right \rfloor+max(\frac{x}{4}-1,0)$

代码

void solve(){int a,b;cin>>a>>b;if(a<b) swap(a,b);int x=(a*a-b*b);int ans=(x-1)/2+max(x/4-1,0ll);cout<<ans<<"\n";
}

L.Numb Numbers

思路

找到排名为 $\left \lceil \frac{n-1}{2} \right \rceil$ 的值为x，答案就是<=x的个数

方法一:用平衡树，但貌似把手写的平衡树全卡常了，能用c++库自带的平衡树做，具体看代码

方法二:用map，set维护，我们用set维护比x大的数，不断模拟即可

方法三:用树状数组或线段树离线维护，离散化之后二分查找

代码

方法一：

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type,std::less<std::pair<int, int>>, __gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>trr;void solve(){int n,q;cin>>n>>q;vector<int> a(n+10);for(int i=1;i<=n;i++){cin>>a[i];trr.insert({a[i],i});}while(q--){int p,v;cin>>p>>v;trr.erase({a[p],p});a[p]+=v;trr.insert({a[p],p});auto x=*trr.find_by_order((n+1)/2);auto y=*trr.find_by_order((n+1)/2+1);x.second=0;y.second=0;int xx=x.first;int yy=y.first;if(xx==yy){auto y=*trr.lower_bound(x);int rk=trr.order_of_key(y);cout<<rk<<"\n";}else{auto y=*trr.upper_bound(x);int rk=trr.order_of_key(y);cout<<rk<<"\n";}}trr.clear();
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

方法二：

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n,q;cin>>n>>q;vector<int> a(n+1);vector<int> b;map<int,int> mp;for(int i=1;i<=n;i++){cin>>a[i];if(!mp[a[i]]) b.push_back(a[i]);mp[a[i]]++;}sort(b.begin(),b.end());set<int> s; //维护较大的数int num=0;for(int i=b.size()-1;i>=0,num<n/2;i--){s.insert(b[i]);num+=mp[b[i]];}int mn=*s.begin();while(q--){int p,v;cin>>p>>v;int x=a[p];int y=a[p]+v;a[p]+=v;mp[x]--;mp[y]++;if(x>=mn) num--;if(y>=mn){num++;s.insert(y);while(num-mp[mn]>=n/2){num-=mp[mn];s.erase(s.begin());mn=*s.begin();}}cout<<n-num<<"\n";}}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

方法三：

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;struct BIT{vector<int> d1,d2;int n;BIT() {}BIT(int n_){init(n_);}void init(int n_){n = n_;d1.assign(n_ + 2, 0);d2.assign(n_ + 2, 0);}int lowbit(int x){return x & (-x);}// 直接修改树状数组的函数,在位置x上加kvoid add_diff(int x, int k){for (int i = x; i <= n; i += lowbit(i)){d1[i] += k;d2[i] += x * k;}}// 在l,r上加kvoid add(int l, int r, int k){if (l > r) swap(l, r);add_diff(l, k);add_diff(r + 1, -k);}// 在x上加kvoid add(int x, int k){add(x, x, k);}// 求原数组的前缀和int pre(int p){int res = 0;for (int i = p; i > 0; i -= lowbit(i))res += (p + 1) * d1[i] - d2[i];return res;}// 查询l,r之间和int ask(int l, int r){if (l > r) swap(l, r);return pre(r) - pre(l - 1);}// 查询位置xint ask(int x){return ask(x, x);}
};void solve(){int n,q;cin>>n>>q;vi a(n+1);vi ta(n+1);vi b;for(int i=1;i<=n;i++){cin>>a[i];ta[i]=a[i];b.push_back(a[i]);}vi p(q+1),v(q+1);for(int i=1;i<=q;i++){cin>>p[i]>>v[i];ta[p[i]]+=v[i];b.push_back(ta[p[i]]);}sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end());int cnt=b.size();map<int,int> pos;for(int i=0;i<cnt;i++) pos[b[i]]=i+1;BIT bit(cnt);for(int i=1;i<=n;i++) bit.add(pos[a[i]],1);auto check=[&](int x)->bool{return bit.ask(x,cnt)>=(n/2);};for(int i=1;i<=q;i++){bit.add(pos[a[p[i]]],-1);a[p[i]]+=v[i];bit.add(pos[a[p[i]]],1);int l=1,r=cnt;int ans=0;while(l<=r){int mid=l+r>>1;if(check(mid)){ans=mid;l=mid+1;}else{r=mid-1;}}if(ans==1){cout<<"0\n";}elsecout<<bit.ask(1,ans-1)<<"\n";}
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

K.Museum Acceptance

思路

发现路线其实是连通的，即我们从某个出发点进入此路线后此路线上的所有出发点所经过的不同走廊的数量是一样的，可以看成是由多个环组成的。

所以我们来一遍记忆化搜索即可

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n;cin>>n;vector<int> d(n+1);vector<vi> e(n+1);for(int i=1;i<=n;i++){cin>>d[i];for(int j=1;j<=d[i];j++){int x;cin>>x;e[i].emplace_back(x);}}vector<vector<int>> dp(n+1,vector<int>(4,-1));map<pll,bool> mp;vector<vb> vis(n+1,vb(3,false));int cnt=0;auto dfs=[&](auto self,int x,int dir)->void{if(dp[x][dir]!=-1){cnt+=dp[x][dir];return;}if(vis[x][dir]){return ;}vis[x][dir]=true;int nx=e[x][dir];int nxdir=0;int k=e[nx].size();for(int i=0;i<k;i++){if(x==e[nx][i]){nxdir=(i+1)%k;break;}}if(!mp[{min(x,nx),max(x,nx)}]){mp[{min(x,nx),max(x,nx)}]=true;cnt++;self(self,nx,nxdir);}else{self(self,nx,nxdir);}dp[x][dir]=cnt;};for(int i=1;i<=n;i++){cnt=0;if(dp[i][0]==-1){mp.clear();dfs(dfs,i,0);cout<<dp[i][0]<<"\n";}else{cout<<dp[i][0]<<"\n";}}}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;// cin>>_;while(_--) solve();return 0;
}

I.Iron Bars Cutting

思路

区间dp，我们用 $dp[l][r][i]$ 表示棍子从l到r时切割i点的最小价值，显然状态转移方程为

$dp[l][r][i]=dp[l][i][j]+dp[i+1][r][k]+cost(l,r,i)$

对于不平衡度b来说我们要保证其不递增，那么可以将转移方程看成一个树状结构，只要 $b(l,r,i)>=b(l,i,j)$ 并且 $b(l,r,i)>=b(i+1,r,k)$ ，我们总能找到一个顺序满足其对不平衡度的要求

就这样的思路未优化前其复杂度为 $O(n^4)$ 会超时

如此代码所示这里用递归实现的：代码查看

那么我们就想办法优化，我们可以将切割(l,r)的区间内不平衡度给统计在一个数组f[l][r]里面，我们在更新 $dp[l][r][i]$ 时我们要找到不大于 $b(l,r,i)$ 的 $b(l,i,j)$ 以及 $b(i+1,r,k)$ 之中的cost最小来更新dp[l][r][i]，我们可以用二分来找到不大于b(l,r,i)，然后用前缀最小值来表示最小的cost，这样便将复杂度降为了 $O(n^3logn)$ ，这个时候时间复杂度就能够通过了

但是要注意空间复杂度：代码查看，我们还需要对此代码进行空间的优化，最终代码如下

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;int a[425];
int sum[425];int getb(int l,int r,int i){return abs((sum[i]-sum[l-1])-(sum[r]-sum[i]));
}
int getcost(int l,int r,int i){return min(sum[i]-sum[l-1],sum[r]-sum[i])*ceil(log2(sum[r]-sum[l-1]));
}void solve(){int n;cin>>n;sum[0]=0;for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];vector<vector<vector<pll>>> f(n+1,vector<vector<pll>>(n+1));    //{b,cost}vector<vector<vector<int>>> premn(n+1,vector<vector<int>>(n+1));vi ans(n+1,inf);for(int len=2;len<=n;len++){for(int l=1,r=len;r<=n;l++,r++){vector<pll> tmp;for(int i=l;i<r;i++){int b=getb(l,r,i);int cost=getcost(l,r,i);int lc=0,rc=0;bool valid=true;if(l!=i){if(f[l][i].empty()){valid=false;}else{auto it=upper_bound(f[l][i].begin(),f[l][i].end(),make_pair(b,inf));if(it==f[l][i].begin()){valid=false;}else{int idx=it-f[l][i].begin();lc=premn[l][i][idx-1];}}}if(valid && i+1!=r){if(f[i+1][r].empty()){valid=false;}else{auto it=upper_bound(f[i+1][r].begin(),f[i+1][r].end(),make_pair(b,inf));if(it==f[i+1][r].begin()){valid=false;}else{int idy=it-f[i+1][r].begin();rc=premn[i+1][r][idy-1];}}}if(!valid) continue;int total=lc+rc+cost;tmp.push_back({b,total});if(l==1&&r==n){ans[i]=min(ans[i],total);}}if(tmp.empty()) continue;sort(tmp.begin(),tmp.end());f[l][r]=tmp;vi pre(tmp.size());pre[0]=tmp[0].second;for(int k=1;k<tmp.size();k++){pre[k]=min(pre[k-1],tmp[k].second);}premn[l][r]=pre;}}for(int i=1;i<n;i++){if(ans[i]>=inf){cout<<"-1 ";}else{cout<<ans[i]<<" ";}}cout<<"\n";}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

查看全文

http://www.lryc.cn/news/608490.html