wweiyiのblog

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

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

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

【解题报告】 BZOJ3032 七夕祭 题目：七夕祭（翻译过的） ps：话说今天是七夕节，我就正好做到七夕祭 解题思路： 看到这道题的题目，可以想到《均分纸牌》和我之前做的《货仓选址》两题，这样经过思考，演算和推理，我们可以得出，需要的最少步数是 ∑i=1M∣S[i]−s[k]∣\sum\limits_{i=1}^M\left|S[i]-s[k]\right| i=1∑M​∣S[i]−s[k]∣ 其中S是A的前缀和，即 S[i]=∑j=1iA[j]S[i]=\sum\limits_{j=1}^iA[j] S[i]=j=1∑i​A[j] 所以经过简单地编码，答案就出来了 AC代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>using namespace std;c...