网易有道资格赛1-最大和子序列

我个NC。。这道题代码量实际上很小而且也不是很triky。。比赛的时候我居然悲剧囧死了。。。。
就是原来的算法,首先由于每个都是非空的那么特判一下正数小于等于2个情况(此时显然取最大的两个)。。然后先算没有跨越环的,设L[x]表示1-x的最大子序列长度,R[x]表示x-n的最大子序列长度,答案很显然就是Max(L[x]+R[x+1])。。。然后如果跨越环了,那么它的对偶问题就是不选的那些肯定不跨越环,一样的DP可以算出来(为了方便把所有值取负就OK了。。)。。两个中的最大值就是答案了。。。。
Code:
#include<cstdio>#include<algorithm>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=50000+10,inf=~0U>>1;int t,n,A[maxn],L[maxn],R[maxn];int Cal(){ L[0]=0; for(int i=1;i<=n;i++) L[i]=max(L[i-1],0)+A[i]; R[n+1]=0; for(int i=n;i>=1;i–) R[i]=max(R[i+1],0)+A[i]; for(int i=1;i<=n;i++)L[i]=max(L[i],L[i-1]); for(int i=n;i>=1;i–)R[i]=max(R[i],R[i+1]); int ans=-inf; for(int i=1;i<=n;i++)ans=max(ans,L[i]+R[i+1]); return ans;}void Solve(){ scanf("%d",&n);int z=0,s=0,a=-inf,b=-inf; rep(i,n)scanf("%d",A+i+1),z+=A[i+1]>0,s+=A[i+1]; if(z<=2) { rep(i,n) { if(A[i+1]>b)b=A[i+1]; if(a<b)swap(a,b); } printf("%dn",a+b); return; } int ans=Cal(); rep(i,n)A[i+1]=-A[i+1]; ans=max(ans,s+Cal()); printf("%dn",ans);}int main(){ //freopen("in","r",stdin); int t;scanf("%d",&t); rep(i,t)Solve();}

网易有道资格赛-1

第一题直接暴力算就OK了。。
第二题先把所有字符串排序,然后查找就OK了。。。
第三题真是太狗血了。算法我一下就想到了但因为脑子出问题一直WA(F..K啊!!!)
实际上如果不跨越环的话,一个O(N)的DP就可以解决问题,如果跨越环的话,那么考虑这个问题的对偶就是取两段最小的(那么出这些之外的也是两段且是最大的)就不会跨越环了。。
但见鬼的是由于两段都要非空,所以第一个要求至少取两个,第二个要求剩下的至少有2个。。就很难处理了。。我是个NC。。所以一直WA。。痛苦死了。。
太失败了。。总结一下。。首先是脑子很乱的时候如果再急一下就大悲剧了。。
对于难题算法的思考还是不够细致和冷静而导致悲剧。。现在我明白为什么我的代码会错了。。
犯了一个超低级的错误。。晕死。。还有就是错误点不一定是你一直以为的,
比如我一直以为是非空的处理错了,实际上之后几次已经改对了,但DP的时候犯了个小错误导致悲剧。。。脑子一片空白就不要写了。。休息一下什么的,否则也不会把DP写错了囧。。
还有就是C是有朴素算法,为什么不先写个对拍呢?真是NC啊囧。。。
弄测试数据的时候不要总想着极端的,极端只能测试一些点有没有处理正确,不能测试算法是否整体正确啊。。
哎。。总而言之言而总之我是个大大的NC、SB、弱菜。。
但神奇的是难道是我信春哥春哥保佑我么?前400晋级最后我正好398名。。。无语了。。

[SCOI2009]windy数

[SCOI2009]windy数

Time Limit:1000MS  Memory Limit:165536K
Total Submit:118 Accepted:54

Description

windy定义了一种windy数。
不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。
windy想知道,在A和B之间,包括A和B,总共有多少个windy数?

Input

包含两个整数,A B。

Output

一个整数。

Sample Input

【输入样例一】
1 10

【输入样例二】
25 50

Sample Output

【输出样例一】
9

【输出样例二】
20

【数据规模和约定】
20%的数据,满足 1 <= A <= B <= 1000000 。
100%的数据,满足 1 <= A <= B <= 2000000000 。

Source

Day1
哎。。还是数位统计问题,幸好对付这种题目可以写个暴力程序来对拍,不然肯定要悲剧啊囧。。。有经验了。。总结一下:
首先要注意第一位就是0的情况,着并不代表这位是0,而是忽略这位,所以按照公式写个特殊的统计的就OK了。。
还有就是可以前面的数位已经不能是windy数了,就不要推下去了。。
同时一定要写个暴力对拍。。
对拍要多考虑这样的数据:
1: 1-1000000这样的.。。
2:1-99999这样的。。
3: xxx-xxxxx这样的,至少差2位。。
4:如果还不放心随机个N组来搞搞。。
5:最好用long long免得溢出。。
6:没有了。。

对拍器:

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <sstream>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1;
using namespace std;
typedef ostringstream OSS;
int C[10];
bool Check(int a)
{
OSS t;t<<a;string s=t.str();
rep(i,s.size()-1)if(abs(s[i]-s[i+1])<2)return false;
return true;
}
int main()
{
int a,b,c=0;cin>>a>>b;
for(int i=a;i<=b;i++)c+=Check(i);
cout<<c<<endl;
}

代码:

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1,maxd=12;
using namespace std;
typedef long long ll;
ll Count[maxd][10]={},C;
int N[maxd],n;
void PreDo()
{
rep(j,10)Count[1][j]=1;
for(int i=2;i<maxd;i++)
{
rep(j,10)
{
Count[i][j]=0;
rep(k,10)if(abs(k-j)>=2)Count[i][j]+=Count[i-1][k];
}
}
}
void Dfs(int p,int l)
{
int t=N[p];
if(p==0)
{
rep(j,t+1)if(abs(j-l)>=2)C++;
return;
}
rep(i,t)
{
if(abs(i-l)>=2)
{
if(p==n-1&&i==0)
{
rep(j,p)rep(k,9)C+=Count[j+1][k+1];
}
else
{
C+=Count[p+1][i];
}
}
}
if(abs(t-l)>=2)Dfs(p-1,t);
}
ll Cal(ll A)
{
if(!A)return 0;
for(n=0;A;A/=10,n++)N[n]=A%10;
C=0;Dfs(n-1,20);
return C;
}
int main()
{
//freopen("in","r",stdin);
PreDo();
ll a,b;cin>>a>>b;
cout<<Cal(b)-Cal(a-1)<<endl;
}

[Scoi2010]传送带

[Scoi2010]传送带

Time Limit:1000MS  Memory Limit:65536K
Total Submit:48 Accepted:30

Description

在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P,在CD上的 移动速度为Q,在平面上的移动速度R。现在lxhgww想从A点走到D点,他想知道最少需要走多长时间

Input

输入数据第一行是4个整数,表示A和B的坐标,分别为Ax,Ay,Bx,By
第二行是4个整数,表示C和D的坐标,分别为Cx,Cy,Dx,Dy
第三行是3个整数,分别是P,Q,R

Output

输出数据为一行,表示lxhgww从A点走到D点的最短时间,保留到小数点后2位

Sample Input

0 0 0 100
100 0 100 100
2 2 1

Sample Output

136.60

Hint

对于100%的数据,1<= Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000
1<=P,Q,R<=10

Source

Day2
很显然正解是双重二分之类的,不过我用模拟退火A掉了囧。。随机化无敌!!!
Code:

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
double P,Q,R;
struct Point
{
double x,y;
Point(){}
Point(double _x,double _y):x(_x),y(_y){}
Point operator*(double d)
{
return Point(x*d,y*d);
}
Point operator+(const Point&o)const
{
return Point(x+o.x,y+o.y);
}
};
struct Line
{
Point A,B;
Line(){}
Point get(double d)
{
return A*d+B*(1-d);
}
}A,B;
istream& operator>>(istream&in,Point&p)
{
in>>p.x>>p.y;
return in;
}
istream& operator>>(istream&in,Line&l)
{
in>>l.A>>l.B;
return in;
}
struct State
{
double Up,Down;
State(){}
State(double _Up,double _Down):Up(_Up),Down(_Down){}
void Just(double a,double b)
{
Up+=a;Down+=b;
}
};
double Dist(const Point&a,const Point&b)
{
static double A,B;
A=a.x-b.x,B=a.y-b.y;
return sqrt(A*A+B*B);
}
double Cal(State s)
{
Point a=A.get(s.Up),b=B.get(s.Down);
return Dist(a,A.A)/P+Dist(a,b)/R+Dist(b,B.B)/Q;
}
double rand_double()
{
return (double(2*rand())/RAND_MAX)-1;
}
double check_Legal(State s)
{
return s.Up>=0&&s.Up<=1&&s.Down>=0&&s.Down<=1;
}
int main()
{
//freopen("in","r",stdin);
cin>>A>>B>>P>>Q>>R;
State now(0,0),tmp;double min=Cal(now);
for(double e=1;e>1e-10;e/=2)
{
int time=1000;
while(time–)
{
tmp=now;tmp.Just(rand_double()*e,rand_double()*e);
if(!check_Legal(tmp))continue;
double new_min=Cal(tmp);
if(new_min<min)
{
min=new_min;now=tmp;
}
}
}
printf("%0.2lfn",min);
}

[ZJOI2010]count 数字计数

[ZJOI2010]count 数字计数

Time Limit:3000MS  Memory Limit:65536K
Total Submit:128 Accepted:63
Case Time Limit:1000MS

Description

给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次。

Input

输入文件中仅包含一行两个整数a、b,含义如上所述。

Output

输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次。

Sample Input

1 99

Sample Output

9 20 20 20 20 20 20 20 20 20

Hint

30%的数据中,a<=b<=10^6;
100%的数据中,a<=b<=10^12。

Source

Day1
我的娘啊,这题搞死我了。。
数位统计真是恶心囧。。。
算法差不多吧,就是一位位统计过去,最关键的一点是处理好第一位为0的情况。。我的办法是首先看成0000-9999之类的,然后减掉多余的0囧。。

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1,maxn=10,maxd=15;
using namespace std;
typedef long long ll;
ll A[maxn],C[maxn],Pow[maxd],Pre[maxn];
int N[maxd],n;
void Dfs(int p)
{
int t=N[p];
if(p<0)
{
rep(j,10)C[j]+=Pre[j];
return;
}
rep(i,t)
{
ll num=Pow[p];
if(p==n-1&&i==0)
{
rep(j,10)C[j]+=num/10*p;
rep(j,p+1)
{
C[0]-=(Pow[p-j]-Pow[p-j]/10)*j;
}
}
else
{
Pre[i]++;
rep(j,10)C[j]+=Pre[j]*num;
Pre[i]–;num/=10;
rep(j,10)C[j]+=p*num;
}
}
Pre[t]++;Dfs(p-1);
}
void Cal(ll x)
{
for(n=0;x;x/=10,n++)N[n]=x%10;
memset(C,0,sizeof(C));
memset(Pre,0,sizeof(Pre));
Dfs(n-1);
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
ll a,b;cin>>a>>b;Pow[0]=1;rep(i,maxd-1)Pow[i+1]=Pow[i]*10;
Cal(b);rep(i,10)A[i]=C[i];
Cal(a-1);rep(i,10)A[i]-=C[i];
rep(i,10)cout<<A[i]<<" ";
}

[BeiJing2006]狼抓兔子

[BeiJing2006]狼抓兔子

Time Limit:15000MS  Memory Limit:165536K
Total Submit:762 Accepted:164
Case Time Limit:4000MS

Description

现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对 下面这样一个网格的地形:


左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路
1:(x,y)<==>(x+1,y)
2:(x,y)<==>(x,y+1)
3:(x,y)<==>(x+1,y+1)
道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的.
左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角(1,1)的窝里,现在它们要跑到右下解(N,M)的窝中去,狼王开始伏击这些兔 子.当然为了保险起见,如果一条道路上最多通过的兔子数为K,狼王需要安排同样数量的K只狼,才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使 得在将兔子一网打尽的前提下,参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.

Input

第一行为N,M.表示网格的大小,N,M均小于等于1000.接下来分三部分
第一部分共N行,每行M-1个数,表示横向道路的权值.
第二部分共N-1行,每行M个数,表示纵向道路的权值.
第三部分共N-1行,每行M-1个数,表示斜向道路的权值.
输入文件保证不超过10M

Output

输出一个整数,表示参与伏击的狼的最小数量.

Sample Input

3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6

Sample Output

14

Source
这题一看就是最小割问题,但范围怎么这么大囧。。。后来看了周冬神牛的论文(2008年的那个)才知道原来平面图的最小割等于对偶图的最短路囧。。构图很麻烦,搞得我累死囧。。

#include<cstdio>
#include<vector>
#include<queue>
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define tr(e,x) for(eit e=x.begin();e!=x.end();e++)
using namespace std;
const int maxn=1000,maxv=maxn*maxn*2,inf=~0U>>2;
int n,m,vs,vt,v;
int Node[maxn][maxn][2];
int Dist[maxv];
struct Edge
{
int t,c;
Edge(int _t,int _c):t(_t),c(_c){}
};
struct State
{
int p,c;
State(int _p,int _c):p(_p),c(_c){}
bool operator<(const State&o)const
{
return c>o.c;
}
};
vector<Edge> E[maxv];
priority_queue<State> Q;
typedef vector<Edge>::iterator eit;
int Dijstra()
{
rep(i,v)Dist[i]=inf;Q.push(State(vs,0));
while(Q.size())
{
State t=Q.top();Q.pop();if(t.c>Dist[t.p])continue;
if(t.p==vt)return t.c;
tr(e,E[t.p])
{
int ncost=t.c+e->c;
if(ncost<Dist[e->t])
{
Dist[e->t]=ncost;
Q.push(State(e->t,ncost));
}
}
}
}
void AddEdge(int s,int t,int c)
{
E[s].pb(Edge(t,c));
E[t].pb(Edge(s,c));
}
int main()
{
//freopen("in","r",stdin);
scanf("%d%d",&n,&m);v=0;
rep(i,n-1)rep(j,m-1)rep(k,2)Node[i][j][k]=v++;
vs=v++;vt=v++;int c;
rep(j,m-1)scanf("%d",&c),AddEdge(vs,Node[0][j][0],c);
rep(i,n-2)rep(j,m-1)
{
scanf("%d",&c);AddEdge(Node[i][j][1],Node[i+1][j][0],c);
}
rep(j,m-1)scanf("%d",&c),AddEdge(Node[n-2][j][1],vt,c);
rep(i,n-1)
{
scanf("%d",&c);AddEdge(Node[i][0][1],vt,c);
rep(j,m-2)
{
scanf("%d",&c);AddEdge(Node[i][j+1][1],Node[i][j][0],c);
}
scanf("%d",&c);AddEdge(vs,Node[i][m-2][0],c);
}
rep(i,n-1)
rep(j,m-1)
{
scanf("%d",&c);
AddEdge(Node[i][j][0],Node[i][j][1],c);
}
printf("%dn",Dijstra());
}

[HNOI2008]Cards

[HNOI2008]Cards

Time Limit:10000MS  Memory Limit:165536K
Total Submit:114 Accepted:65
Case Time Limit:1000MS

Description

小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答 案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出了正确答案.
最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用 多种洗牌法,而每种方法可以使用多次)洗成另一种.Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以P的余数(P为质数).

第一行输入五个整数:Sr,Sb,Sg,M,P(M<=60,M+1

<100).
N=Sr+Sb+Sg.接下来M行,每行描述一种洗牌法,每行有N个用空格隔开的整数X1X2…Xn.
恰为1到N的一个排列,表示使用这种洗牌法,第I位变成原来的Xi位的牌.
输入数据保证任意多次洗牌都可以用M种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到
原状态.
20%的数据保证Sr+Sb+Sg<=20
100%的数据保证Max(Sr,Sb,Sg)<=20

Input

第一行输入五个整数:Sr,Sb,Sg,M,P(M<=60,M+1

<100).N=Sr+Sb+Sg.
接下来M行,每行描述一种洗牌法,每行有N个用空格隔开的整数X1X2…Xn.
恰为1到N的一个排列,表示使用这种洗牌法,第I位变成原来的Xi位的牌.
输入数据保证任意多次洗牌都可以用M种洗牌法中的一种代替,且对每种洗牌法
都存在一种洗牌法使得能回到原状态.
20%的数据保证Sr+Sb+Sg<=20
100%的数据保证Max(Sr,Sb,Sg)<=20

Output

不同染法除以P的余数

Sample Input

1 1 1 2 7
2 3 1
3 1 2

Sample Output

2

Hint

有2 种本质上不同的染色法RGB 和RBG,使用洗牌法231 一次可得GBR 和BGR,使用洗牌法312 一次
可得BRG 和GRB。

Source
昨天很累啊,做了这题差不多就睡了。。今天才写这个,这题就是Polya计数法的扩展应用了。
本质上上是对每个置换的不动点数量求出平均值,不动点数量由于需要满足颜色的要求只能用Dp来搞,同时求出平均值需要除法,幸好P是素数,所以直接乘以拟元就可以了。。

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1,maxn=60;
typedef long long ll;
using namespace std;
int a,b,c,m,p,n;ll ret;
int M[maxn];
void Plus(int&a,int b)
{
a+=b;if(a>=p)a-=p;
}
int Cal(int A[maxn])
{
static int B[maxn],s;
static bool V[maxn];
static int Dp[2][maxn][maxn];
s=0;memset(V,0,sizeof(V));
rep(i,n)if(!V[i])
{
int t=0,x=i;
while(!V[x])V[x]=true,x=A[x],t++;
B[s++]=t;
}
int now=0,next=1;
memset(Dp,0,sizeof(Dp));Dp[next][0][0]=1;
rep(o,s)
{
swap(now,next);memset(Dp[next],0,sizeof(Dp[next]));
int t=B[o],tmp;
rep(i,a+1)rep(j,b+1)if(tmp=Dp[now][i][j])
{
Plus(Dp[next][i+t][j],tmp);
Plus(Dp[next][i][j+t],tmp);
Plus(Dp[next][i][j],tmp);
}
}
return Dp[next][a][b];
}
int pow_mod(int a,int b)
{
if(b==1)return a;
ll tmp=pow_mod(a,b/2);tmp*=tmp;tmp%=p;
if(b&1)tmp*=a,tmp%=p;
return tmp;
}
int main()
{
//freopen("in","r",stdin);
cin>>a>>b>>c>>m>>p;n=a+b+c;
rep(i,m)
{
rep(j,n)scanf("%d",M+j),M[j]–;
ret+=Cal(M);
}
rep(i,n)M[i]=i;ret+=Cal(M);
ret=ret*pow_mod(m+1,p-2);ret%=p;
cout<<ret<<endl;
}


[Baltic2003]Gem

[Baltic2003]Gem

Time Limit:2000MS Memory Limit:65536K
Total Submit:18 Accepted:11
Case Time Limit:1000MS

Description

给出一棵树,要求你为树上的结点标上权值,权值可以是任意的正整数
唯一的限制条件是相临的两个结点不能标上相同的权值,要求一种方案,使得整棵树的总价值最小。

Input

先给出一个数字N,代表树上有N个点,N<=10000
下面N-1行,代表两个点相连

Output

最小的总权值

Sample Input

Sample Output

Source
这题首先是不能用奇偶层染色的办法来做的,我构造出了至少需要1-3的反例,同时用数学归纳法可以证明对于任意n,都有树不能用1-n达到最优解(提示:使用大量叶子节点逼迫某节点染2。。)。。
但是我的构造法弄出来的反例的大小至少是指数增长的,所以我感觉对于N<=10000,10种颜色足够了。。更精确的测试表明3种就OK了(!!!!!我可以构造出1000个以内的需要4种颜色的反例啊囧。。这个数据好弱啊。。)。。然后就是简单的树形DP。。。比赛的时候很明显直接DP就可以了。。证明不重要(*^__^*) 嘻嘻……

14

10 7 5 1 2 1 7 8 9 4 1 9 7 5 6 10 2 9 3
囧。。由于不会绘图软件。。自己手绘了一个反例。。
可以看出在一些情况中奇偶层的叶子都很多。。如果奇偶染色肯定要悲剧。。
可以用类似的方法构造出需要1-4、1-5、1-6的反例。。

[FJOI2007]轮状病毒

[FJOI2007]轮状病毒

Time Limit:500MS Memory Limit:165536K
Total Submit:141 Accepted:63
Case Time Limit:100MS

Description

给定n(N<=100),编程计算有多少个不同的n轮状病毒。

Input

第一行有1个正整数n。

Output

将编程计算出的不同的n轮状病毒数输出

Sample Input

Sample Output

Source

16

3

16

3做了N久的八中OJ才做第二题晕。。。
这道题首先我的想法是破环为链,再想办法做。。
对于一个链来说,设Dp[i]为长度为i的链和一个“中心”的生成树数量,可以Dp之。。
然后考虑环,枚举1节点所在的环的长度,设为Len,那么这个环的位置有Len种情况,这个环与中心连接也有Len种情况,那么这个节点对答案的贡献就是Len^2*Dp[n-Len]。。
写个高精度+一下久OK了。。。

[Baltic2005]Cards

[Baltic2005]Cards

Time Limit:5000MS Memory Limit:165536K
Total Submit:6 Accepted:6
Case Time Limit:1000MS

Description

Adam在抽屉时发现了一些卡片,他在卡片的正反面随机写了一些数字,然后按其随机排放.
并进行形如下图的计算,问所能得到的最小值为多少.注意Adam可以把卡片翻转过来.

第一行输入数字N,N在[2,100000]且为偶数.
下面N行每行两个数字Ai,Bi,表示Adam写在卡片上的数字.其值在[-2000,2000]

Input

input data1
6
-8 12
0 5
7 -3
10 -7
-2 7

input data2
10
70 70
62 73
81 65
59 77
99 40
35 88
80 57
76 67
85 57
53 96

Output

output data1
-34

output data 2
-155

Sample Input

Sample Output

Hint

Source
水题。很显然如果一个数前面是-号,则要用Max(a,b),否则就是Min(a,b)
神奇的变换来了(*^__^*) 嘻嘻……。。
-2Max(a,b)=-(a+b)-|a-b|,2Min(a,b)=a+b-|a-b|…
所以|a-b|是都有的,故只要按a+b排序就OK了。。。|

Page 1 of 41234