1001 开场白

来自世界各地的年青人在 https://2050.org.cn 握手团聚， 他们是航空航天的新生代，编程大赛的优胜者，35岁以下的创新者，科技公司的创始人，展望未来的科学家，天马行空的艺术家… TA们期待在这里与所有人分享交流，给彼此灵感，给未来答案。

我们想要用10个题目，大声喊出年青人的声音。我们希望和大家一起用技术创造一个更好的2050。

第一道题目，我们来玩一个数字游戏。
给出一个数字 n，我们想知道 n 是不是若干个 2050 依次拼接起来的。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i>0;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
char stt[1010]="2050";
bool work() {char s[101010];cin>>s;int n=strlen(s);if(n%4==0) {Rep(i,n) if(s[i]!=stt[i%4]) return 0;return 1;}	return 0;
}
int main()
{
//	freopen("D.in","r",stdin);
//	freopen(".out","w",stdout);int T=read();while(T--){cout<<(work()?"Yes":"No")<<endl;}return 0;
}

1002 时间间隔

2019年1月1日，在云栖出现了可能是全世界最长的以秒为单位的倒计时装置：九亿多秒倒计时，直到2050年。

给出一个时间S，我们想知道S距离2050年1月1日0点0时0分多少秒。

因为答案可能很大，请输出答案模100的值。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i>0;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b)
#define gmin(a,b) a=min(a,b)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int is_l(int y)
{if (y%4==0&&y%100!=0) return 366;if (y%400==0) return 366;return 365;
}
typedef long long ll;
ll work(ll y1,ll m1,ll d1) {ll y2=2050,m2=1,d2=1;if (y1>y2||(y1==y2&&m1>m2)||(y1==y2&&m1==m2&&d1>d2)) swap(y1,y2),swap(m1,m2),swap(d1,d2);int tot=0;Fork(i,y1+1,y2-1) tot+=is_l(i);if (y1^y2){if (m1<2) tot+=is_l(y1)==366?29:28;if (m2>2) tot+=is_l(y2)==366?29:28;Fork(i,m1+1,12) if (i!=2) tot+=a[i];Fork(i,1,m2-1) if (i!=2) tot+=a[i];tot+=d2;tot+=a[m1]-d1+1;if (m1==2&&is_l(y1)==366) tot++;if (tot) tot--;}else{if (m1^m2){if (is_l(y1)==366) a[2]=29;Fork(i,m1+1,m2-1) tot+=a[i];tot+=d2;tot+=a[m1]-d1+1;tot--;}else tot=d2-d1;}return tot;}
int main()
{
//	freopen("B.in","r",stdin);
//	freopen(".out","w",stdout);int T;cin>>T;while(T--) {int y1,m1,d1,h,m,s;scanf("%d-%d-%d %d:%d:%d",&y1,&m1,&d1,&h,&m,&s);ll p=24*60*60-h*60*60-m*60-s;cout<<p%100<<endl;} return 0;
}

1003 分宿舍

2050的线下活动吸引了很多心怀梦想的年轻人。

小伙们打算组团去参加。他们一共有 n+m+2k 个人，包括 n+k 个男生，m+k 个女生，其中 k 对男女生为异性情侣，现在他们要找房间住。房间有三种类型，双人间 a 元一间，三人间 b 元一间，这两种只能同性一起住。情侣间能住一对异性情侣，一间 c 元。除了情侣间以外，其他房间都可以不住满。

求最少花多少钱，能让小伙伴们都有地方住。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i>0;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b)
#define gmin(a,b) a=min(a,b)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
ll f[2010];
bool work() {ll n,m,k,a,b,c;cin>>n>>m>>k>>a>>b>>c;ll ans=1e18;MEM(f)f[0]=0;For(i,max(n+k,m+k)){f[i]=1e18;if(i>=2) gmin(f[i],f[i-2]+a),gmin(f[i],f[i-2]+b);if(i>=3) gmin(f[i],f[i-3]+b);if(i>=1) gmin(f[i],f[i-1]+min(a,b));}Rep(i,k+1){ll ln=n+k-i,lv=m+k-i;ll p=c*i+f[ln]+f[lv];gmin(ans,p);}cout<<ans<<endl;
}
int main()
{
//	freopen("D.in","r",stdin);
//	freopen(".out","w",stdout);int T=read();while(T--){work();}return 0;
}

1004 PASS

有 n 个选手参加了 2050 编程竞赛，他们属于 m 个学校，学校的编号为 1 到 m，2050 编程竞赛的 PASS 奖励资格如下：对于一个学校，如果它有 x 个学生参赛，它的参赛学生里成绩最好的 ⌊xk⌋ 人里，每有一个人总排名在前 50% 内（包括50%），就奖励一个 PASS。

现在给出每个选手所属的学校和它的排名（假设没有平手），请你帮主办方算一下一共发出了几个 PASS。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i>0;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
int a[11234],c[11234],p[11234];
int main()
{
//	freopen("D.in","r",stdin);
//	freopen(".out","w",stdout);int T=read();while(T--){int n=read(),m=read(),k=read();memset(c,0,sizeof(int)*(m+1));For(i,n) a[i]=read(),c[a[i]]++;For(i,m) c[i]/=k;int tot=0;For(i,n/2) if(c[a[i]]>0) c[a[i]]--,++tot;cout<<tot<<endl;}return 0;
}

1005 球赛

https://2050.org.cn/games-at2019 是2050非常重要的组成部分之一，包括逐日晨跑、足球风暴、室内骑行挑战、棒球全民打、篮球嘉年华、户外电影等活动。

身体是革命的本钱，这道题是关于运动的。
Alice和Bob在进行乒乓球比赛，比赛一共打了 n 个球，对于每一球，如果Alice赢了，那么裁判员会在计分板上记下’A’，如果Bob赢了则会记下’B’。
时间转眼间到了2050年，计分板上某些信息因为时间流逝丢失了，但我们想要复现当年的激烈局面。
丢失的位置用’?'表示，我们想知道，计分板上对应的乒乓球球赛，最多进行了多少局（最后一局可以没打完，但是如果没打完的话就不计入答案）？
在一局比赛中，先得11分的一方为胜方，10平后，先多得2分的一方为胜方。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i>0;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
int f[10101][13][13]={};
int main()
{
//	freopen("E.in","r",stdin);
//	freopen(".out","w",stdout);int T=read();while(T--){char s[10101];cin>>(s+1);MEM(f)int n=strlen(s+1);f[0][0][0]=100000;Rep(i,n) {Rep(j,13) Rep(k,13) if(f[i][j][k]){if(s[i+1]=='A'||s[i+1]=='?') {int nj=j+1,nk=k;if(nj>=11 && nk<=9 || nj==12&&nk==10) {gmax(f[i+1][0][0],f[i][j][k]+1 );}else if(nj<11&&nk<11){gmax(f[i+1][nj][nk],f[i][j][k]);}else if (nj-1>=10&&nk-1>=0) {gmax(f[i+1][nj-1][nk-1],f[i][j][k]);}else {gmax(f[i+1][nj][nk],f[i][j][k]);}}if(s[i+1]=='B'||s[i+1]=='?') {int nj=j,nk=k+1;if(nk>=11 && nj<=9 || nk==12&&nj==10) {gmax(f[i+1][0][0],f[i][j][k]+1 );}else if(nj<11&&nk<11){gmax(f[i+1][nj][nk],f[i][j][k]);}else if (nj-1>=10&&nk-1>=0) {gmax(f[i+1][nj-1][nk-1],f[i][j][k]);}else {gmax(f[i+1][nj][nk],f[i][j][k]);}}}}int tot=0;Rep(j,13) Rep(k,13) gmax(tot,f[n][j][k])cout<<tot-100000<<endl;}return 0;
}

1006 冰水挑战

Polar Bear Pitching helps you crystallize your message.
The stage could not be any cooler, and we mean literally:
a hole cut through the ice in the frozen Baltic Sea.

2050有一项很有挑战的活动 —— Polar Bear Pitching 。
体验人跳入冰水中讲述自己的恐惧，改变以及梦想。这是没有时间限制的演讲，就看你能在冰水中呆多久！

现在，我们要依次面对 n 个冰水挑战，每个挑战你都可以选择接受或不接受。接受第 i 个挑战会让你丧失 ai点体力，因为每个挑战所处的环境不同，如果你要挑战它，在挑战它之前你的体力 x 会变成 min(x,bi)，当你完成这个挑战的时候，你的体力会变成 x−ai，体力任何时候不允许小于等于 0，无论你是否接受第 i 个挑战，在这个挑战结束以后你的体力都会增加 ci。

现在我们想知道最多可以完成多少个挑战。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i>0;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b)
#define gmin(a,b) a=min(a,b)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
ll a[2010],b[2010],c[2010];
ll f[2010];
bool work() {int n=read();ll cc=read();For(i,n) f[i]=-1e18; f[0]=cc;ll ans=0;For(i,n) {cin>>a[i]>>b[i]>>c[i];RepD(j,i-1) if(f[j]>0){if(min(f[j],b[i])-a[i]>0) {gmax(f[j+1],min(f[j],b[i])-a[i]);}}Rep(j,i+1)f[j]+=c[i]; }For(i,n) if(f[i]>0) ans=i;cout<<ans<<endl;
}
int main()
{
//    freopen("F.in","r",stdin);
//    freopen(".out","w",stdout);int T=read();while(T--){work();}return 0;
}

1007 大厦

我们看到了一栋高楼大厦，大厦的墙面可以看做一个 W×H 的矩形，我们把它的左下角当成(0,0)，右上角当成(W,H)。上面分布着一些LED灯，这些LED灯与地面呈45度倾斜，并且从矩形的边界延伸到另一边界，把大厦分成了若干个区域。我们想数一下这个图里面存在多少个与地面成45度角的矩形，其中四条边都是LED灯的一部分。
Input
第一行一个正整数 T (T≤10) 表示数据组数。
对于每组数据，第一行 W,H,n,m (1≤W,H≤109,0≤n,m≤103) 表示矩形的长和宽，以及两种方向的LED灯的个数。
接下来一行 n 个整数c (1≤c≤W+H−1)，表示这个LED灯可以表示成 x+y=c 的形式，保证 c 两两不同。
接下来一行 m 个整数 c (1−H≤c≤W−1)，表示这个LED灯可以表示成 x−y=c 的形式，保证 c 两两不同。

Output
对于每组数据，输出一个整数表示答案，由于答案可能很大，对 109+7 取模。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i>0;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b)
#define gmin(a,b) a=min(a,b)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} ll w,h,n,m;
ll a[1010],b[1010];
ll getl(ll x){if(x<=h) return -x;return -(2*h-x);
}
ll getr(ll x){if(x<=w) return x;return (2*w-x);
}bool work() {cin>>w>>h>>n>>m;For(i,n) a[i]=read();For(i,m) b[i]=read();sort(a+1,a+1+n);ll ans=0;sort(b+1,b+1+m);For(i,n) Fork(j,i+1,n) {ll l=max(getl(a[i]),getl(a[j]));ll r=min(getr(a[i]),getr(a[j]));ll p1=lower_bound(b+1,b+1+m,l)-b;ll p2=upper_bound(b+1,b+1+m,r)-b-1;if(p1<=p2) {ans+=(ll)(p2-p1+1) * (p2-p1)/2%F;ans%=F;}}cout<<ans<<endl;
}
int main()
{
//	freopen("g.in","r",stdin);
//	freopen(".out","w",stdout);int T=read();while(T--){work();}return 0;
}

1009 跨洋飞行

已知地图上一共有 n 个机场，张博博士要从 1 号机场飞到 n 号机场，也就是2050的举办地杭州。

从 i 号机场飞行到 j 号机场需要消耗 dist(i,j) 个单位的油量，其中 dist(i,j) 为 i 号机场和 j 号机场之间的欧几里得距离。

张博博士可以选择在任意机场起降和加油。飞机油箱最多可以保存 u 单位的燃油。

考虑到可能遇到的极端天气，某些机场在某些时候不具备降落的条件。所以出于安全的考虑，当他飞到一个机场的时候，必须保证飞机剩下的油足以飞到离他最近的机场。

假设一次起飞和降落分别需要花费 a 秒和 b 秒的时间，加 1 单位的油需要花费 c 秒的时间，飞行 1 单位的距离需要花费 d 秒的时间，请问张博博士最早什么时候可以到达杭州，和我们相见？

飞机初始的油量为0，也就是说，飞机需要先在起点加油再起飞。

Input
第一行一个整数 T (1≤T≤50)，表示数据组数。

对于每组数据：

第一行 6 个整数 n,a,b,c,d,u (2≤n≤103,0≤a,b,c,d,u≤105)。

接下来 n 行，每行两个整数 xi,yi (0≤xi,yi≤105) 表示第 i 个机场的坐标。

Output
对于每组数据输出一行一个数，表示最早的到达时间，只要你的答案和标准答案相对误差或者绝对误差在 10−5 以内就算通过。

数据保证有解。

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair 
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case %d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
const double eps=1e-8;
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
struct Edge{int from,to;double dist;
};
struct HeapNode {double d;int u;bool operator< (const HeapNode& rhs) const {return d > rhs.d;}
}; 
#define MAXN (1100)
struct Dijkstra {int n,m;vector<Edge> edges;vector<int> G[MAXN];bool done[MAXN];double d[MAXN];void addedge(int u,int v,int w){edges.pb((Edge){u,v,w});G[u].pb(m++);}void addedge2(int u,int v,int w) {addedge(u,v,w);addedge(v,u,w);}void init(int _n){n=_n; m = 0;Rep(i,n) G[i].clear();edges.clear(); } void dijkstra(int s) {priority_queue<HeapNode> Q;Rep(i,n) d[i]=INF;d[s]=0;MEM(done)Q.push((HeapNode){0,s});while(!Q.empty()) {HeapNode x=Q.top(); Q.pop();int u=x.u;if (done[u]) continue;done[u]=1;int mm=G[u].size();Rep(i,mm) {Edge e = edges[G[u][i]];if (d[e.to]>eps+d[u]+e.dist) {d[e.to]=d[u]+e.dist;Q.push((HeapNode){d[e.to],e.to});}}}} 
}S1;
double x[1010],y[1010];
double dis[1010];
double dd(int i,int j){return hypot(x[i]-x[j],y[i]-y[j]);
}
void work() {int n,a,b,c,d,u;cin>>n>>a>>b>>c>>d>>u;For(i,n) cin>>x[i]>>y[i];S1.init(n+3);For(i,n) dis[i]=1e18;For(i,n){For(j,n) if(i^j) {gmin(dis[j],dd(i,j));}}Fork(i,2,n) Fork(j,2,n) {if(dd(i,j)+dis[j]<=u) S1.addedge(i,j,a+b+(c+d)*dd(i,j)+c*(dis[j]-dis[i]));}Fork(j,2,n) {if(dd(1,j)+dis[j]<=u) S1.addedge(1,j,a+b+(c+d)*dd(1,j)+c*dis[j]);}S1.dijkstra(1);printf("%.8lf\n",S1.d[n]);}
int main()
{
//    freopen("i.in","r",stdin);
//    freopen(".out","w",stdout);int T=read();while(T--){work();}return 0;
}