PM2.5Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1346Accepted Submission(s): 571
问题描述
目前，我们用PM2.5的含量来描述空气质量的好坏。一个城市的PM2.5含量越低，它的空气质量就越好。所以我们经常按照PM2.5的含量从小到大对城市排序。一些时候某个城市的排名可能上升，但是他的PM2.5的含量也上升了。这就意味着他的空气质量并没有改善。所以这样的排序方式是不合理的。为了使得排序合理，我们提出了一个新的排序方法。我们按照两个PM2.5含量测量的差值（第一次-第二次）来对他们按降序排序，如果有重复，按照第二次的测量值升序排序，如果还有重复，按照输入的顺序排序。
输入描述
多组测试数据(大概的信息。请处理到文件末尾。[参数说明]所有整数都在的范围内。
输出描述
对于每一个数据，输出排好序之后的城市ID。
输入样例
2100 11 23100 503 41 2
输出样例
0 10 2 1
直接sort排序，在cmp里面处理一下。
#include <iostream>#include <cstring>#include <cstdio>using namespace std;int n;struct data{int x,y,d,id;}a[10005];bool cmp(data a,data b){if (a.d==b.d){if (a.y==b.y) return a.id<b.id;return a.y<b.y;}return a.d>b.d;}int main(){while (scanf("%d",&n)!=EOF){for (int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y),a[i].d=a[i].x-a[i].y,a[i].id=i;sort(a+1,a+1+n,cmp);for (int i=1;i<n;i++)cout<<a[i].id-1<<" ";cout<<a[n].id-1<<endl;}return 0;}
B:Negative and Positive (NP)Time Limit: 3000/1500 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1161Accepted Submission(s): 59
问题描述
给定一个数组 刚好为。
输入描述
多组测试数据。在文件的第一行给出一个组数据。在接下来的行里，将会给出每一组数据。每一组数据占两行，第一行包含。第二行包含以一个空格分开。[参数说明]所有输入均为整数。
输出描述
对于每一个数据，输出占一行，输出格式是Case #id: ans,这儿id是数据编号，从1开始，ans是根据是否找到满足的二元组而定为“Yes.” 或 “No.” (不包含引号)看样例可以获得更多的信息。
输入样例
21 112 1-1 0
输出样例
Case #1: Yes.Case #2: No.
Hint
如果数据比较多，建议使用快速读入。
求出"前缀和"，一加一减的。
我们考虑奇数位为正，偶数位为负的情况（反之考虑方法一样）：
对于sum[i]（i%2=0）如果i+1作第一位，能使得结果为k的话，一定存在sum[i]+k这个数，如何快速判断是否存在sum[i]+k呢？
我比赛用了map，结果mle+tle。。
其实set和hash+链表都可以过，代码是hash+链表。
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <map>#define LL long long#define mod 1000007using namespace std;LL x[1000005];struct edge{LL v;int ne;}e[1100000];int a[1000005],h[1100000],tot=0,n,T,k;void read(int &tmp){tmp=0;char ch=getchar();int fu=1;for (;ch<'0'||ch>'9';ch=getchar())if (ch=='-') fu=-1;for (;ch>='0'&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';tmp*=fu;}void Insert(LL x){int ha=x%mod;if (ha<0) ha=-ha;for (int i=h[ha];i;i=e[i].ne)if (e[i].v==x) return;e[++tot].ne=h[ha];h[ha]=tot;e[tot].v=x;}bool Find(LL x){int ha=x%mod;if (ha<0) ha=-ha;for (int i=h[ha];i;i=e[i].ne)if (e[i].v==x) return 1;return 0;}void Clear(){for (int i=1;i<=n;i++){int ha=x[i]%mod;if (ha<0) ha=-ha;h[ha]=0;}tot=0;}int main(){read(T);for (int i=1;i<=T;i++){read(n),read(k);x[0]=0;int f=0;for (int i=1;i<=n;i++){read(a[i]);if (i&1)x[i]=x[i-1]+a[i];else x[i]=x[i-1]-a[i];}for (int i=n;i;i–){if (x[i]==k){f=1;break;}if ((i&1)==0){if (Find(x[i]+k)) {f=1;break;}}else if (Find(x[i]-k)) {f=1;break;}Insert(x[i]);}printf("Case #%d: ",i);if (f) printf("Yes.\n");else printf("No.\n");Clear();}return 0;}只能昏昏沉沉地沿着青草和泥土的气息前进。
