wweiyiのblog

2019.8.30做的三道题 Mayan游戏 没啥好说的，看着就恶心，还好有大佬的题解指导要不然我就废废废了 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164#include<iostream>#include<cstdio>#include<...

【解题报告】 Stick 题目：木棍 解题思路： 深度优先搜索 我们可以用深度优先搜索简单地做出来，没错，是很简单 AC代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;int a[100],v[100],n,len,cnt;bool cmp(int a,int b){ return a>b;}bool dfs(int stick,int cab,int last){ if(stick>cnt) return true; if(cab==len) return dfs(stick+1,0,1); int fail=0; ...

【解题报告】 加成序列 题目：加成序列 解题思路： dfs+剪枝+迭代加深 这道题我们可以看出任何序列的长度都在10左右，所以这道题我们可以很好地看出是用迭代加深来解决问题 所以我们为了让序列中的数尽快逼近n，在枚举i和j时，可以从大到小枚举 然后我们还需要一个判重，因为不让两个数加起来等于第三个数多次 AC代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int maxn=110;int n;int path[maxn];bool dfs(int u,int depth){ if(u==depth) return path[u-1]==n; bool st[maxn]={false}; for...

【解题报告】 [NOI1999]生日蛋糕 题目：生日蛋糕 解题思路： dfs枚举 这道题上面的表面积不用管，只用管侧面积和体积，上面的表面积就是最底下的圆的面积 我们只需要枚举半径和高度就OK了 另外需要剪枝，如果枚举到dep-1层时，最小体积大于n的话，我们就可以进行剪枝了 AC代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int maxn=0x3f3f3f;const int N=20007;int ans=maxn;int mins[N],minv[N],n,m;void dfs(int now,int r,int h,int s,int v){ int mh=h; if(now==0) ...

【解题报告】 小猫爬山 题目：小猫爬山 解题思路： 哪家会养这么重又这么多猫，只能说他们两个比较闲的无聊 当然这道题就像猫一样，特别狡猾 开始的时候我看到这个，想到了一个贪心做法，但是不管怎么改，答案就是改不对，经过前思后想，左顾右盼，我知道了真正的算法：搜索+剪枝 恰好就是我不最擅长的算法！ 我就按照思路和书中所给的部分代码打出来了，当我提交上去的时候，一个大大的A字亮在我的眼前，没错 AC代码 123456789101112131415161718192021222324252627282930313233343536373839404142#include <iostream>#include <cstdio>#include <algorithm>using namespace std;int c[20],cab[20],n,w,ans;void dfs(int now,int cnt){ if(cnt>=ans) return ; if(now==n+1) { ans=min(ans,cnt); retu...

【解题报告】 防线 题目：防线 解题思路： 虽然说是解题报告，但是也是有一部分曲折在其中的，因为这道题开始的时候实在想不到思路，知道看到了某大佬的题解之后才豁然开朗，明白了这道题目的做法，和神奇的思想 这道题的思想很简单，就是用前缀和 你要想，奇数加奇数等于偶数，但是题目中只有一个是奇数的，所以这种情况不成立，那么就只有偶数加奇数或偶数加偶数两种情况 因此我们就做一个前缀和加上一个神奇而又简单的二分，就可以得出正确而又完美有缺的答案了（有缺我也不知道那里缺） AC代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int maxn=200005;int n,t;struct ar{ long long s; long long e; long long...

【解题报告】 耍杂技的牛 题目：耍杂技的牛 解题思路： 排序+贪心 这个牛啊实际上就是大臣，约翰那就是国王，你有没有想到一道题目，没错，那就是《国王游戏》，但是没错，那道题需要高精度，这道题目不需要高精度，所以这道题目就简单多了，这道题就是按（w+s）把牛牛们从小到大排序一下，然后计算出它们的风险值，找出最大的就可以了，还是比较简单的 AC代码 12345678910111213141516171819202122232425262728293031#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int maxn=50010;long long n;long long d[maxn];long long res=-0x3f3f3f3f,sum=0;struct cow{ long long w; long long s;}a[maxn];bool cmp(cow a,cow b){ return a....

【解题报告】 占卜DIY 题目：占卜DIY 解题思路： 简简单单的模拟加上dfs（简单的dfs） 但是这个游戏还是挺有意思的，可以看一下 一副去掉大小王的扑克共52张，打乱后均分为13堆，编号1~13，每堆4张，其中第13堆称作“生命牌”，也就是说你有4条命。 这里边，4张K被称作死神。 初始状态下，所有的牌背面朝上扣下。 流程如下： 1.抽取生命牌中的最上面一张(第一张)。 2.把这张牌翻开，正面朝上，放到牌上的数字所对应编号的堆的最上边。(例如抽到2，正面朝上放到第2堆牌最上面，又比如抽到J，放到第11堆牌最上边，注意是正面朝上放) 3.从刚放了牌的那一堆最底下(最后一张)抽取一张牌，重复第2步。（例如你上次抽了2，放到了第二堆顶部，现在抽第二堆最后一张发现是8，又放到第8堆顶部…） 4.在抽牌过程中如果抽到K，则称死了一条命，就扔掉K再从第1步开始。 5.当发现四条命都死了以后，统计现在每堆牌上边正面朝上的牌的数目，只要同一数字的牌出现4张正面朝上的牌(比如4个A)，则称“开了一对”，当然4个K是不算的。 6.统计一共开了多少对，开了0对称作”极凶”，1~2对为“大凶”，...

【解题报告】 士兵 题目：士兵 解题思路： 排序+离散化 我们可以对每个士兵的纵坐标和横坐标进行排序，然后算它们的中位数，就可以得到他们最短的路线，然后就可以对每个士兵和中位数做差，用一个变量记录它们的和，即为答案 AC代码 12345678910111213141516171819202122232425262728#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>using namespace std;const int maxn=10005;int n;long long x[maxn],y[maxn],mx,my,ans;int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>x[i]>>y[i]; sort(x+1,x+1+n); sort(y+1,y+1+n); for(int i=1;i<=n;i++) x[i]-=i; sort(...

【解题报告】 Task 题目：任务 解题思路： 贪心 我们可以贪心每个任务的等级，再贪心每个任务的时间，我们这样排一下序，再循环一下，就可以得到正确的答案了 AC代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const long long maxn=100010;long long n,m;struct task{ long long x; long long y;}; task f[maxn];task e[maxn];long long cnt[105],ans,num;long long cmp(task a,task b){ if(a.x==b.x) return a.y>b.y; return a.x>...