wweiyiのblog

【解题报告】 占卜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>...

【解题报告】 POJ1050 To the Max 题目：最大的和（已翻译） 题意简述： 就是一个矩阵中找一个和最大的子矩阵 解题思路： 贪心，我们可以首先在输入的时候贪一遍心，然后我们可以一行一行地贪心，最终得到最后的正确结果 AC代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int maxn=105;int n;int a[maxn][maxn],s[maxn][maxn];int ans=-0x3f,nans;bool check=false;int max(int a,int b){ return a>b? a:b;}int main(){ cin>>n; for(int ...

【解题报告】 POJ2054 给树染色 题目：Color a tree(已翻译) 解题思路： 贪心 我们很容易想到从第一层开始，每次染权值最大的一个节点，但是我们可以构造出一个数，让一个权值很小的点下面有权值很大的节点，所以我们考虑的贪心思路是树中除了根节点外的权值最大的节点，它的父节点染色之后一定会被马上染色，所以我们可以将权值最大的点和它的父节点进行合并，合并得到的新点的权值是这两个点之和的平均值，这样就一直合并，直至合并到一个点的时候，我们就按照这个点合并的顺序染色就是正确的答案了。 AC代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include <iostream>#include <cstdio>using namespace std;long long r,n;long long i,j,now,ans,a,b,father;struct node{ ...

【解题报告】 [NOIP2012]国王游戏 题目：国王游戏 解题思路： 贪心 我们只需要将所有大臣左右手上的数的乘积从小到大进行排序，我们就得到了最优答案，但是这个代码要写高精度就是一个麻烦的东西，要好好写，话说近几年不出高精度的题目了，就怕今年要出。 AC代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>using namespace std;const int maxn=10005;int n;struct mini{ int a; int b;}m[maxn];bool cmp...

【解题报告】 POJ1328 雷达设备 题目：雷达设备（已翻译） 解题思路： 贪心。 这道题只需要将x轴上方的一些建筑物，利用勾股定理算出x轴上一段能管辖它的区间，所以问题就变成了给定n个区间，在x轴上放置最少的点，使每个区间至少包含一个点，但是，特别地，如果建筑物的纵坐标超出了每个雷达管辖的半径，就直接不会继续下去了，因为不管怎么样，那个建筑物都无法被管辖，所以我们只需要每个建筑物算出来的区间的右端点进行排序，然后设置一个数组vis，来记录每个建筑物是否被管辖到，然后就ok了 AC代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <iostream>#include <algorithm>#include <cmath>using namespace std;const int maxn=1005;int n,d;int ans;bool vis[maxn];struct sec
...

【解题报告】 POJ3614 防晒 题目：防晒（已翻译） 解题思路： 模拟+贪心； 我们这道题是一道好的贪心的例题，我们只要对于每一头奶牛按照它们的minspf进行递减排序，然后在对于每一种防晒霜进行一次扫描，找出符合条件的spf值最大的防晒霜 但是会想到一点，我们需要将每一头奶牛的minspf和maxspf进行一一对应，所以我们可以使用结构体，然后自己在写一个比较函数，就可以让这两个数值一一对应，这样就方便多了 AC代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <iostream>#include <algorithm>using namespace std;const int maxn=2505;int c,l,ans;struct cow{ int minspf; int maxspf;}a[maxn];struct sc{ int spf; int cove...

【解题报告】 天才ACM 题目：天才ACM 解题思路： 倍增算法 设p=1，r=l 求出r—r+p这一区间的校验值，如果校验值小于等于t，则r+=p，p*=2； 否则p/=2; 一直重复，直到p等于0的时候，r就是最终答案 AC代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int maxn=500005;long long t,tot;long long n,m,k;long long p[maxn];long long f[maxn];int l,r...

【解题报告】POJ2299 超快速排序 题目：超快速排序（已翻译） 解题思路： 归并排序求逆序对 归并排序使我们众所周知的，我们只要在归并排序中计算每一个子序列中的逆序对数，我们就可以计算出总的逆序对数了，也就是 cnt+=mid−i+1cnt+=mid-i+1 cnt+=mid−i+1 然后就完成了这道题 AC代码 12345678910111213141516171819202122232425262728293031323334353637383940414243#include <iostream>#include <cstring>using namespace std;int n;long long cnt;const int maxn=500005;long long a[maxn];long long b[maxn];void merge_sort(int l,int r){ if(r>l) { int mid=(l+r)/2; int i=l; int p=...