dell网站的网站设计特色,自建网站服务器,wordpress刷权重插件,手机app的开发与维护费用E.不知道叫什么名字
题意#xff1a;找一段连续的区间#xff0c;使得区间和为0且区间长度最大#xff0c;输出区间长度。 思路#xff1a;考虑前缀和#xff0c;然后使用map去记录每个前缀和第一次出现的位置#xff0c;然后对数组进行扫描即可。原理#xff1a;若 s …E.不知道叫什么名字
题意找一段连续的区间使得区间和为0且区间长度最大输出区间长度。 思路考虑前缀和然后使用map去记录每个前缀和第一次出现的位置然后对数组进行扫描即可。原理若 s [ i ] x s[i]x s[i]x,则 m a p [ x ] i map[x]i map[x]i,当后续出现 s [ j ] x s[j]x s[j]x时 s [ j ] − s [ i ] 0 s[j]-s[i]0 s[j]−s[i]0,则合法的区间长度为 j − i j-i j−i。 将此题一般化为找一段连续的区间使得区间和为 k 且长度最大输出区间长度我们同样使用这个方法去记录前缀和然后对数组进行扫码即可对于前缀和 s [ j ] s[j] s[j]而言因为 s [ j ] − ( s [ j ] − k ) k s[j]-(s[j]-k)k s[j]−(s[j]−k)k,所以需要定位到 s [ j ] − k s[j]-k s[j]−k第一次出现的位置即可。
#include bits/stdc.husing namespace std;
const int N 2e5 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 p3;
int mod 1e97;
// const int maxv 4e6 5;
// #define endl \nvoid solve()
{int n;cinn;vectorint a(n5),s(n5);for(int i1;in;i) cina[i];for(int i1;in;i){s[i]s[i-1]((a[i]1)?1:-1);}mapint,int mp;mp[0]0;for(int i1;in;i){if(!mp.count(s[i])) mp[s[i]]i;}int ans0;for(int i1;in;i){int xs[i];ansmax(ans,i-mp[x]);}coutansendl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t1;
// cint;while(t--){solve();}system(pause);return 0;
}
G.闪闪发光心动不已
题意找到包含kira…doki的最长子序列。 思路运用前后缀的思想对字符串正向扫描一遍然后逆向扫描一遍对于位置i而言其最大长度为其前面的kira子序列其后面doki的子序列。
#include bits/stdc.husing namespace std;
const int N 2e5 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 ar;
int mod 1e97;
// const int maxv 4e6 5;
#define endl \nvoid solve()
{int n;cinn;string s;cins;s s;vectorint pre(n5),suf(n5);int tot0;for(int i1;in;i){pre[i]pre[i-1];if(tot0s[i]k) tot;else if(tot1s[i]i) tot;else if(tot2s[i]r) tot;else if(tot3s[i]a) tot;if(tot4) pre[i]4,tot0;}
// for(int i1;in;i) coutpre[i] ;tot0;for(int in;i1;i--){suf[i]suf[i1];if(tot0s[i]i) tot;else if(tot1s[i]k) tot;else if(tot2s[i]o) tot;else if(tot3s[i]d) tot;if(tot4) suf[i]4,tot0;}int ans0;for(int i1;in;i){if(pre[i]suf[i1]) ansmax(ans,pre[i]suf[i1]);}coutansendl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t1;
// cint;while(t--){solve();}system(pause);return 0;
}I.uu爱玩飞行棋
题意距离终点m米然后给定n个操作每次可以走x步若不能直接到达终点则需返回多余的步数问走到终点的最小操作。 思路考虑背包设计状态 d p [ i ] [ j ] dp[i][j] dp[i][j]表示对于前 i i i个操作还剩 j j j步的最小操作数量。
#include bits/stdc.husing namespace std;
const int N 2e5 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 p3;
int mod 1e97;
// const int maxv 4e6 5;
// #define endl \nint dp[2010][2010];void solve()
{int n,m;cinnm;vectorint a(m5);for(int i1;im;i){cina[i];}memset(dp,0x3f,sizeof dp);dp[0][n]0;for(int i1;im;i){for(int j0;jn5;j){dp[i][j]min(dp[i-1][j],dp[i-1][ja[i]]1);//当前状态由ja[i]转移而来if(ja[i])dp[i][j]min(dp[i-1][j],dp[i-1][a[i]-j]1);//表示反弹的状态}}if(dp[m][0]1e9/2) cout-1endl;else coutdp[m][0]endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t1;
// cint;while(t--){solve();}system(pause);return 0;
}
J.火柴人小游戏 思路很容易想到二分需要思考如何进行check我们同样容易发现我们可以贪心去选择战斗力较小的且能到达的点所以我们无论我们初始的战斗力如何我们的战斗顺序都是固定的显然普通的队列并不能满足我们的贪心需求我们使用优先队列去生成我们的路径即可然后每次就可以在线性时间复杂度内check完成。
#include bits/stdc.husing namespace std;
const int N 2e5 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 ar;
int mod 1e97;
// const int maxv 4e6 5;
// #define endl \nint n,m,x,y;
ll a[1005][1005];vectorll p;
int dx[]{0,0,-1,1};
int dy[]{-1,1,0,0};
int st[1005][1005];
void bfs()
{priority_queuear,vectorar,greaterar q;int ega[x][y];q.push({eg,x,y});st[x][y]1;//p.push_back(a[x][y]);while(!q.empty()){auto [z,nx,ny]q.top();//coutz nx nyendl;p.push_back(z);q.pop();for(int i0;i4;i){int zxdx[i]nx,zydy[i]ny;if(zx1||zxn||zy1||zym) continue;if(st[zx][zy]) continue;//p.push_back(z);st[zx][zy]1;q.push({a[zx][zy],zx,zy});}}
}bool check(ll x)
{ll nowx;
// if(xp[0]) return false;for(int i1;ip.size();i){if(p[i]now) return false;nowp[i];}return true;
}void solve()
{cinnmxy;for(int i1;in;i){for(int j1;jm;j){cina[i][j];}}bfs();ll la[x][y],r1e18,ans-1;while(lr){ll mid(lr)/2;if(check(mid)){rmid-1;ansmid;}else{lmid1;}}
// for(auto x: p) coutx ;if(ansa[x][y]) coutNo cheating need.endl;else coutansendl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t1;
// cint;while(t--){solve();}system(pause);return 0;
}
