房地产网站大全,做网站简约学校网站,郑州做手机网站建设,网站建设一站式服务公司Wallet Exchange#xff08;Problem - A - Codeforces#xff09;
题目大意#xff1a;A#xff0c;B做游戏#xff0c;它们的钱包里各有a,b个硬币#xff0c;轮到它们操作时#xff0c;它们可以扔掉自己或者对手钱包里的硬币#xff0c;谁不能操作谁输#xff0c;问…Wallet ExchangeProblem - A - Codeforces
题目大意AB做游戏它们的钱包里各有a,b个硬币轮到它们操作时它们可以扔掉自己或者对手钱包里的硬币谁不能操作谁输问最后的胜者是谁。
思路很显然取决于总数的奇偶性奇数则A胜偶数则B胜。
#includebits/stdc.h
using namespace std;
int main()
{int t;scanf(%d,t);while(t--){int a,b;scanf(%d%d,a,b);a b;if(a%2) printf(Alice\n);else printf(Bob\n);}
}
Plus-Minus SplitProblem - B - Codeforces
题目大意代表1-代表-1给定一个字串要求进行划分划分中原来的相对顺序不能改变每个划分的值是划分内的和的绝对值*划分的长度结果是各个划分值的和问最小的结果是多少。
思路很显然只要划分的和为0那么这段划分的值就最小我们只用看有多少不能抵消如果不能抵消那么就一个一个划开使长度最小。
#includebits/stdc.h
using namespace std;
int main()
{int t;scanf(%d,t);while(t--){int n;scanf(%d,n);string s;cins;int c0;for(int i0;in;i){if(s[i]) c;else c--;}printf(%d\n,abs(c));}
}
Grouping IncreasesProblem - C - Codeforces
题目大意现有一个a[]需要把它拆成两个数组a[]中的元素只能属于两个数组之一而且相对顺序不能改变然后我们去计算两个数组中b[i]b[i1]的数对的对数和要求输出最小和。
思路这道题实际上是贪心的题目因为只需要考虑相邻元素之间的关系我们只用记录新数组最后位置的元素即可假设已经插入了i-1个元素了现在要插入第i个元素而此时新数组的两个元素分别为b,c,且bcbc那么两个数组完全等价没有讨论的必要随便插入一个即可,那么现在的问题就转化成将a[i]插入哪个数组。a[i]与b,c有三种关系
1.a[i]bc:此时无论插入哪个数组都不会产生影响但是我们注意到a[i]的插入会减小末尾元素所以如果插c后面a[i1]如果小于c,但是大于b,就不得不产生影响所以为了后面能让更大的数插入不产生影响我们将它插到b后面。
2.bca[i]显然插在哪个后面都会造成影响插入的过程实际上也是增加末尾元素的机会显然增加b比增加c效益更大因为增加b后b,c后面都可以接更大的元素了。
3.ba[i]c:此时插在c后面不会造成影响另外对于a[i]a[i1]c,a[i]插在b后面a[i1]插在c后面与a[i]插在c后面a[i1]插在b后面实际影响是等价的(ba[i1]a[i]讨论类似也是产生1个影响)再者若a[i1]c,将a[i]插在c后面还能减少一次影响。
至此贪心部分就讨论完毕。边界可以再细推一下
#includebits/stdc.h
using namespace std;
int main()
{int t;scanf(%d,t);while(t--){int n;scanf(%d,n);int b0x3f3f3f3f,c0x3f3f3f3f;//为了保证bc始终成立记得更新后交换int ans0;for(int i1;in;i){int x;scanf(%d,x);if(xb) bx;else if(xc) {bx;swap(b,c);ans;}else cx;}printf(%d\n,ans);}
}
这个题的贪心解法和活动 - AcWing第二问有些相似我们在此处一并讨论一下。
每个系统只能拦截非上升子序列第二问要求找出最少需要配备多少个系统才能拦截所有的导弹我们再抽象一点这题考的就是用多少个非上升的序列可以覆盖整个区间。也是从贪心的角度来进行分析
假设现在已经有若干个系统了然后要拦截高度为h的导弹我们有两种选择一种是用已经有的系统去拦截另一种是新开一个系统根据每个系统的性质我们可以知道系统末尾元素肯定是最小的而且比它大的元素不能接在它后面所以如果所有系统的末尾都小于h那么只能新开如果有一部分系统的末尾不小于h那么为了使结果尽可能的少肯定是接在它们中某一个的后面更划算那么就要考虑接在谁的后面更好把h接上后会减少序列末尾的值为了使它们能够拦截后面更高的导弹肯定是将h接在这些序列中小的那个后面才是最优的解法。进而我们考虑如果维护显然这些结尾是满足单调递增的关系的这样就可以二分查找答案。进而该题的贪心部分分析完毕。
这两题都有一个很明显是贪心的点就是需要对于每一个点进行决策那么对每一个决策讨论的过程就是贪心的过程。所以下次涉及需要对一个区间进行操作而且每步操作需要考虑策略的时候就要想一想贪心是否可以。
01 TreeProblem - D - Codeforces
题目大意给出一个序列我们需要判断这个序列是否与某个特定二叉树dfs遍历的叶子节点序相同这里的特定二叉树是指除了叶子节点外的节点都有两个子节点同时两条边的边权一个为1一个为0.
思路这里的叶子节点可能有兄弟节点也可能没有兄弟节点。来看叶子节点与父节点的关系父节点与其中一个子节点的值相同比另一个子节点的值小1那么如果一个点的左右相邻位置有比它小1的值那么就说明它可能有兄弟节点我们如果删除较大的子节点那么因为另一个子节点的值与父节点的值相同所以实际上相当于删除了两个子节点将父节点变成一个叶子节点。我们可以确定值最大的那个点一定有兄弟节点我们从最大的那个入手不断往前删最后如果只有一个点没被删而且值为0那么就说明有这样的二叉存在。
#includebits/stdc.h
using namespace std;
const int N200010;
int a[N],l[N],r[N],st[N];
int n;
int ok(int k)
{if(k1||kn) return 0;if(a[k]-a[l[k]]1||a[k]-a[r[k]]1) return 1;return 0;
}
int main()
{int t;scanf(%d,t);while(t--){scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);l[i]i-1;r[i]i1;st[i]0;}a[0]a[n1]-10;//指针会指到它们初始化一下防止误判priority_queuepairint,intp;for(int i1;in;i){if(ok(i)){st[i]1;p.push({a[i],i});}}while(p.size()){auto itp.top();p.pop();int vit.first,iit.second;//这里更新一定要特别注意很容易出错。l[r[i]]l[i];r[l[i]]r[i];if(!st[l[i]]ok(l[i])){st[l[i]]1;p.push({a[l[i]],l[i]});}if(!st[r[i]]ok(r[i])){st[r[i]]1;p.push({a[r[i]],r[i]});}}int f0,v3e5;for(int i1;in;i){if(!st[i])f;vmin(v,a[i]);}if(f1v0) printf(YES\n);else printf(NO\n);}
}
有时候做不出来的意义只是告诉你该学什么东西了别附加太多别的意义。
