宜兴市网站建设怎么创办一个网站

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

宜兴市网站建设,怎么创办一个网站,建设双语的网站,阿里云购买域名后怎么建网站文章目录第一题 AcWing 4864. 多边形一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第二题 AcWing 4865. 有效类型一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第三题 AcWing 4866. 最大数量一、题目1、原… 文章目录第一题 AcWing 4864. 多边形一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第二题 AcWing 4865. 有效类型一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第三题 AcWing 4866. 最大数量一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第一题 AcWing 4864. 多边形 一、题目 1、原题链接 4864. 多边形 2、题目描述 如果一个正多边形的边数 n 能被 4 整除那么就称该正多边形是美丽的。 现在给定一个正多边形的边数 n请你判断它是否是美丽的。 输入格式 第一行包含整数 T表示共有 T 组测试数据。 每组数据占一行包含一个整数 n。 输出格式 每组数据输出一行结果如果给定正多边形是美丽的则输出 YES否则输出 NO。 数据范围 前 3 个测试点满足 1≤T≤10。 所有测试点满足 1≤T≤1043≤n≤109。 输入样例 4 3 4 12 1000000000输出样例 NO YES YES YES二、解题报告 1、思路分析 1按照题意模拟即可输出答案即为所求。 2注意YES与NO的大小写问题。 2、时间复杂度 时间复杂度为O(n) 3、代码详解 #include iostream using namespace std; int t; int main(){cint;while(t–){int n;cinn;if(n%40) coutYESendl;else coutNOendl; }return 0; }第二题 AcWing 4865. 有效类型 一、题目 1、原题链接 4865. 有效类型 2、题目描述 在本题中关于有效类型字符串具体定义如下 int 是有效类型字符串。如果字符串 X 和字符串 Y 都是有效类型字符串则 pairX,Y 是有效类型字符串。 现有一行若干个单词每个单词要么是 pair要么是 int并且其中 int 的数量恰好为 n 个。 你可以在不改变单词顺序的前提下在这一行中任意添加 、、, 符号。 你的任务是 构造出一个有效类型字符串。 输出这个有效类型字符串。 注意 有效类型字符串中不含空格或其它多余字符。 可以证明如果存在满足条件的有效类型字符串那么它一定是唯一的。 如果不存在满足条件的有效类型字符串输出 Error occurred即可。 输入格式 第一行包含整数 n表示给定单词中 int 的数量。 第二行包含若干个单词每个单词要么是 pair要么是 int。 输出格式 输出满足条件的有效类型字符串如果不存在则输出 Error occurred。 注意有效类型字符串中不含空格或其它多余字符。 数据范围 前 6 个测试点满足1≤n≤5。 所有测试点满足1≤n≤105输入的总单词数量不超过 105输入的 int 数量恰好为 n。 输入样例1 3 pair pair int int int输出样例1 pairpairint,int,int输入样例2 1 pair int输出样例2 Error occurred二、解题报告 1、思路分析 思路来源y总讲解视频 y总yyds 数据范围为105时间复杂度控制在O(nlogn) 1可以发现每一个满足条件的有效类型字符串都满足一个以pair为根结点int为左右儿子的二叉树。而且每出现一个pair必须有左右儿子每出现一个int必须没有左右儿子即输入多组int是不合法的。所以只有满足每个根结点pair都有孩子每个int都没有孩子而且构造成的二叉树正好将所有的输入都用到即不能多单词也不能少单词就是满足条件类型的字符串。否则就不是有效类型字符串。而输入和输出便是二叉树的前序遍历。 2我们可以通过上述规则来判断给定的输入能否构造出上述的二叉树如果可以我们对二叉树的前序遍历进行输出同时每输出一个根结点pair之后输出一个在遍历完左子树后输出一个,遍历完右子树后输出一个。 3模拟上述过程输出即为所求。 2、时间复杂度 时间复杂度为O(n) 3、代码详解 #include iostream #include string using namespace std; string s,ans; bool dfs(){if(cins){ //每次调用dfs建树时必须有输入如果调用了但是没有输入直接返回falseif(spair){ //如果输入pair需要递归建立左右子树anss;if(!dfs()) return false; //递归构建左子树ans,;if(!dfs()) return false; //递归构建右子树ans;}else anss; //如果输入int直接加到答案中即可}else return false;return true; } int main(){int n;cinn;bool flagdfs();string tmp;if(!flag||cintmp) coutError occurred; //如果无法构成树缺少输入或者输入出现多余则不合法else coutans; //正好用到所有输入的单词而且可以按照规则构造成二叉树按题目要求输出答案return 0; }第三题 AcWing 4866. 最大数量 一、题目 1、原题链接 4866. 最大数量 2、题目描述 一个无向图有 n 个点编号 1∼n。 这些点之间没有任何边。 给定 d 个需求编号 1∼d。 其中第 i 个需求是让点 xi 和点 yi 连通。 需求可能存在重复。 在本题中你需要依次解决 d 个问题编号 1∼d。 其中第 i 个问题是请你在图中添加恰好 i 条无向边不能添加重边和自环使得 前 i 个需求都得到满足。所有点的度的最大值尽可能大。 对于每个问题你不需要输出具体方案你只需要 输出度的最大可能值。 注意 如果点 a 和点 b 之间存在路径则称点 a 和点 b 连通。 图中与点 a 关联的边数称为点 a 的度。 d 个问题之间是相互独立的每个问题的答案都必须独立计算。 输入格式 第一行包含两个整数 n,d。 接下来 d 行其中第 i 行包含两个整数 xi,yi表示第 i 个需求是让点 xi 和点 yi 连通。 输出格式 共 d 行其中第 i 行输出第 i 个问题中度的最大可能值。 数据范围 前三个测试点满足2≤n≤10。 所有测试点满足2≤n≤10001≤d≤n−11≤xi,yi≤nxi≠yi。 输入样例1 7 6 1 2 3 4 2 4 7 6 6 5 1 7输出样例1 1 1 3 3 3 6输入样例2 10 8 1 2 2 3 3 4 1 4 6 7 8 9 8 10 1 4输出样例2 1 2 3 4 5 5 6 8二、解题报告 1、思路分析 思路来源4866. 最大数量 y总yyds 数据范围为1000时间复杂度控制在O(n2)或O(n2logn) 1针对每个需求i让点xi和yi连通即使xi和yi在一个集合中也就是用到了并查集的合并操作。 2前i个操作总共可以使用i条边使每个点相连而我们满足前i个需求即让xi和yi连通可能不会用完i条边。假设我们已经满足前i个需求后还剩余cnt条边而前i个需求已经将所有元素合并成了某些集合k1k2k3…kd而这些集合中点度数最大为集合中元素数-1即其中的某个点与其他所有点都相连。我们将剩余的边数连到某个集合中不会改变该集合的最大度数。如果用边将两个集合相连则合并后集合的度比合并前任意一个集合的度都要大合并后集合的度也就是合并后集合的总元素数-1。而总共可以合并cnt1个集合所以我们需要将元素数量最多的前cnt1个集合合并这样可以保证使用cnt条边后合并完的集合度是比其他任何情况都要大。 3按照上述过程模拟计算出前cnt1个集合的总点数sum则最大度为sum-1输出答案即为所求。 2、时间复杂度 时间复杂度为O(n2logn) 3、代码详解 #include iostream #include algorithm using namespace std; const int N1010; int p[N],num[N],nums[N]; //p[]存储每个结点的祖宗结点num[]存储集合大小nums[]存储集合合并后每个合并后集合的点数 //并查集查找祖宗结点 int find(int x){if(p[x]!x) p[x]find(p[x]);return p[x]; } //按降序排列cmp函数 bool cmp(int A,int B){return AB; } int main(){int n,d;cinnd;//初始化并查集数组for(int i1;in;i){p[i]i;num[i]1;}int cnt0; //cnt记录满足前i个需求后还剩余多少条边while(d–){int x,y;cinxy;if(find(x)!find(y)){ //如果x、y不在一个集合中则合并num[find(y)]num[find(x)];p[find(x)]find(y);}else cnt; //如果xy已经在一个集合中则无需操作可以省下一条边可以使用int t0;//将每个集合中点的数量记录在nums数组中for(int i1;in;i){if(p[i]i){nums[t]num[i];}}sort(nums,numst,cmp); //降序排列nums数组int sum0; //取前cnt1个点数最多的集合将它们的点数记录在sum中for(int i0;iticnt1;i){sumnums[i];}coutsum-1endl; //sum-1即为所求}return 0; }