电子商务网站建设技术规范,合肥中科大网站开发,外贸网站 球衣,公众号编辑器365T1:标题统计 题目大意
输入一个字符串#xff0c;求字符串除了空格的字符个数 解题思路
这种考你会不会编程的题不会#xff1f; code
#includecstdio
#includestring
#includeiostream
using namespace std;
int ans;
string c;
int main()
{get…T1:标题统计 题目大意
输入一个字符串求字符串除了空格的字符个数 解题思路
这种考你会不会编程的题不会 code
#includecstdio
#includestring
#includeiostream
using namespace std;
int ans;
string c;
int main()
{getline(cin,c);int lc.size();for(int i0;il;i)ans(c[i]! c[i]!\n);printf(%d,ans);
}T2:龙虎斗 题目大意
一个长度为n序列被中间点m分成两半m左边和m右边。 左边战斗力为 ∑i1m−1(m−i)∗ai\sum_{i1}^{m-1}(m-i)*a_ii1∑m−1(m−i)∗ai ∑im1n(i−m)∗ai\sum_{im1}^{n}(i-m)*a_iim1∑n(i−m)∗ai 找到一个数值加s2s2s2使两边的战斗力之差最小 解题思路
先处理好两边战斗力 暴力枚举位置。注意要用longlong code
#includecstdio
#includealgorithm
#define N 100010
#define lls long long
using namespace std;
lls n,c[N],m,p1,s1,s2,ans1,ans2,mins,mark;
int main()
{scanf(%lld,n);for(lls i1;in;i)scanf(%lld,c[i]);scanf(%lld%lld%lld%lld,m,p1,s1,s2);c[p1]s1;for(lls i1;im;i)ans1c[i]*(m-i);for(lls im1;in;i)ans2c[i]*(i-m);mark0;mins1e19;for(lls i1;im;i){if(abs(ans1s2*(m-i)-ans2)mins){marki;minsabs(ans1s2*(m-i)-ans2);}}for(lls im1;in;i){if(abs(ans1-ans2-s2*(i-m))mins){marki;minsabs(ans1-ans2-s2*(i-m));}}if((minsabs(ans1-ans2)markm)||minsabs(ans1-ans2)) printf(%lld,mark);else printf(%lld,m);
}T3:摆渡车 题目大意
n个人有不同的到达时间。一辆车来回一次要mminm\ \ minm min。安排一个来回时间使所有人等待时间之和最小。 解题思路
我们可以发现m很小可是t却很大。所有我们不一定要从t入手。因为一个人会影响到他的只有之前的m−1minm-1\ \ minm−1 min。 用fi,jf_{i,j}fi,j表示第i个人等了j的等待时间总数。然后我们枚举i和枚举上一班车的最后一个人j。之后枚举那个人等了多久k。我们就可以计算出这个人上车最少等待时间 tjkm−tit_jkm-t_itjkm−ti 然后我们可以更新fi,wf_{i,w}fi,w fi,wmin{fi,w,fj,ksj1,i(i−j)∗w}f_{i,w}min\{f_{i,w},f_{j,k}s_{j1,i}(i-j)*w\}fi,wmin{fi,w,fj,ksj1,i(i−j)∗w} 其中用si,js_{i,j}si,j表示i到j的人都等第j个人上车需要的时间 code
#includecstdio
#includecstring
#includealgorithm
#define N 510
#define M 210
using namespace std;
int n,m,t[N],s[N][N],f[N][M],ans;
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,t[i]);sort(t1,t1n);for(int i1;in;i)//预处理sfor(int ji1;jn;j)for(int ki;kj;k)s[i][j]t[j]-t[k];memset(f,0x3f3f3f3f,sizeof(f));t[0]-2e9;for(int i0;im;i)//初始化{f[0][i]0;f[1][i]i;}for(int i2;in;i)//dpfor(int j0;ji;j)for(int k0;km;k){int wt[j]km-t[i];if(w0)f[i][w]min(f[i][w],f[j][k]s[j1][i](i-j)*w);else//特判防越界f[i][0]min(f[i][0],f[j][k]s[j1][i]);}ans2e9;for(int i0;im;i)ansmin(ans,f[n][i]);printf(%d\n,ans);
}T4:对称二叉树 题目大意
一棵n个点的二叉树每个点有不同的权值。一棵树对称就是整棵树的左右子节点互换之和长的和之前一样。求这棵树上最大的一颗对称二叉树。 解题思路
对于每个点我们给他两个特征值 z1ilsoni∗2rsoniwi∗4z1_ilson_i*2rson_iw_i*4z1ilsoni∗2rsoniwi∗4 z2ilsonirsoni∗2wi∗4z2_ilson_irson_i*2w_i*4z2ilsonirsoni∗2wi∗4 lson:这个点有没有左子节点 rson:这个点有没有右子节点 然后先左后右的跑一边记录跑到的点的z1和这颗子树包含的范围。 再先右后左的跑一边记录跑到的点的z2和这颗子树包含的范围。 之后对于每个节点用字符串hash判断一下z1对于范围是否和z2对应范围相等如果相等那么这棵子树就是一颗对称二叉树。
时间负责度:O(n)O(n)O(n) code
#includecstdio
#includealgorithm
#define N 1000010
#define p 10007
#define ull unsigned long long
using namespace std;
int sz[N],a1[N],b1[N],e1[N],a2[N],b2[N],e2[N],z[N],f[N];
int maxs,n,tot,ls[N],rs[N],w[N];
ull hash1[N],hash2[N],pows[N];
void read(int x)
{char c;bool flagfalse;while(cgetchar())if((c0c9)||c-) break;if(c!-)xc-48;else flagtrue;while(cgetchar())if(c0c9) xx*10c-48;else break;if(flag) x-x;
}
void dfs1(int x)
{sz[x]1;a1[tot]z[x];b1[x]tot;if(ls[x]!-1)dfs1(ls[x]);if(rs[x]!-1)dfs1(rs[x]);sz[x]sz[ls[x]]sz[rs[x]];e1[x]tot;
}
void dfs2(int x)
{if(x-1) return;a2[tot]f[x];b2[x]tot;if(rs[x]!-1)dfs2(rs[x]);if(ls[x]!-1)dfs2(ls[x]);e2[x]tot;
}
ull hash1z(int l,int r)
{return hash1[r]-hash1[l-1]*pows[r-l1];}
ull hash2z(int l,int r)
{return hash2[r]-hash2[l-1]*pows[r-l1];}
bool check(int x)
{if(sz[ls[x]]!sz[rs[x]]) return false;int l1b1[x],r1e1[x],l2b2[x],r2e2[x];if(hash1z(l1,r1)hash2z(l2,r2)) return true;return false;
}
int main()
{read(n);for(int i1;in;i)read(w[i]);for(int i1;in;i){read(ls[i]);read(rs[i]);//fa[ls[i]]fa[rs[i]]i;z[i]((ls[i]!-1)1)(rs[i]!-1)w[i]*4;f[i]((rs[i]!-1)1)(ls[i]!-1)w[i]*4;//计算特征值}dfs1(1);//正搜tot0;dfs2(1);//反搜pows[0]1;for(int i1;in;i){pows[i]pows[i-1]*p;hash1[i]hash1[i-1]*pa1[i];hash2[i]hash2[i-1]*pa2[i];}//字符串哈希for(int i1;in;i)//枚举节点if(check(i))//判断相等maxsmax(maxs,sz[i]);printf(%d,maxs);
}
