好吧这是我第一次把一场比赛的5题全部做出= =
写一份题解纪念~
A题：
给你2个点，构造另外2个点，使得这4个点组成一个平行于坐标轴的正方形
无解输出-1
好吧div2的A显然是水题= =
判断一下是否在同一直线上然后构造
判断是否是对角线然后构造
不行就-1
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <set>
using namespace std;
inline int maxx(const int &a,const int &b){if (a>b)return a;return b;}
inline int minn(const int &a,const int &b){if (a<b)return a;return b;}
int abs(int x){if (x<0)return -x;return x;}
int a,x1,x2,y1,y2;
int main(){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if (x1==x2){a=abs(y1-y2);printf("%d %d %d %d",x1-a,y1,x2-a,y2);return 0;}
if (y1==y2){a=abs(x1-x2);printf("%d %d %d %d",x1,y1-a,x2,y2-a);return 0;}
if (abs(x1-x2)==abs(y1-y2)){printf("%d %d %d %d",x1,y2,x2,y1);return 0;}
printf("-1");
return 0;
}
B题：
给你n个数，求最大数与最小数的差以及最大数的个数-最小数的个数
好吧还是水题= =
最大最小不说了，计数也不说了，注意下如果所有数都相同的情况
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <set>
using namespace std;
inline int maxx(const int &a,const int &b){if (a>b)return a;return b;}
inline int minn(const int &a,const int &b){if (a<b)return a;return b;}
int a[1000005],b,c,d,e,f,g,h,i,j,k,l,m,n;
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+1+n);
printf("%d ",a[n]-a[1]);
if (a[n]==a[1])printf("%I64d",1ll*n*(n-1)/2);
else{
i=1;
j=n;
while (a[i]==a[1]){h++;i++;}
while (a[j]==a[n]){g++;j--;}
printf("%I64d",1ll*h*g);
}
return 0;
}
C题：
n个人，k辆车，d天
每人每天选一辆车，使得没有2个人d天的坐车序列完全相同
无解-1
有解输出每天每人坐那辆车
求长度为d的k进制的n项
可以根据前一个人得到后一个人的解
中间做到没法做了就-1
#include <cstdio>
#include <algorithm>
using namespace std;
int a[1005][1005],b,c,d,e,f,g,h,i,j,k,l,m,n;
int main(){
scanf("%d%d%d",&n,&k,&d);
for(j=1;j<=d;j++)a[1][j]=1;
for(i=2;i<=n;i++){
for(j=d;a[i-1][j]==k;j--)a[i][j]=1;
if (!j){printf("-1");return 0;}
a[i][j]=a[i-1][j]+1;j--;
for(;j;j--)a[i][j]=a[i-1][j];
}
for(i=1;i<=d;i++)
{for(j=1;j<=n;j++)printf("%d ",a[j][i]);printf("\n");}
return 0;
}
D题：
定义f(1,i,a[i])为1~i中a[i]出现的次数
定义g(j,n,a[j])为1~j中a[j]出现的次数
求(i,j)(i<j)使得f(1,i,a[i])>g(j,n,a[j])的（i,j）的对数
把a离散O(nlogn)
O(n)预处理f(1,i,a[i])和g(j,n,a[j])
树状数组计算答案O(nlogn)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <set>
#define maxn 1000005
using namespace std;
int a[maxn],b[maxn],c,d,e,f[maxn],g[maxn],i,j,k,l,m,n,S[maxn],tree[maxn],N;
long long h;
inline int sum(int x){int s=0;for(;x;x-=x&(-x))s+=tree[x];return s;}
inline void add(int x){for(;x<=n;x+=x&(-x))tree[x]++;}
inline int ef(int x){int l=1,r=N,mid=(l+r+1)>>1;for(;l<r;mid=(l+r+1)>>1)if (b[mid]>x)r=mid-1;else l=mid;return l;}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)b[i]=a[i];
sort(b+1,b+1+n);
for(i=1;i<=n;i++)if (b[i]!=b[i+1])b[++N]=b[i];
for(i=1;i<=n;i++)a[i]=ef(a[i]);
for(i=1;i<=n;i++)f[i]=++S[a[i]];
memset(S,0,sizeof(S));
for(i=n;i;i--)g[i]=++S[a[i]];
for(i=n;i;i--){
h+=sum(f[i]-1);
add(g[i]);
}
printf("%I64d",h);
return 0;
}
E题:
给一张有向图，求一条包含最多点的路径满足路径上的每条边比前一条边长
先把边排序，f[i]表示一i点结尾的路径最多包含多少点
假设有一条u->v的边，f[v]=max(f[v],f[u]+1);
长度相同的边同时计算然后更新答案
好了就这样了……
#include <cstdio>
#include <algorithm>
using namespace std;
struct node{int from,to,cost;}way[1000005];
inline bool cmp(const node &a,const node &b){return a.cost<b.cost;}
int a,b,c,d,e,f[1000005],g[1000005],h,i,j,k,l,m,n,dl[1000005];
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
way[i]=(node){a,b,c};
}
sort(way+1,way+1+m,cmp);
l=0;
for(i=1;i<=m;i++){
dl[++l]=way[i].to;
g[l]=f[way[i].from]+1;
if (way[i].cost!=way[i+1].cost){
for(;l;l--)
f[dl[l]]=max(f[dl[l]],g[l]);
}
}
for(i=1;i<=n;i++)h=max(h,f[i]);
printf("%d",h);
return 0;
}
好了A~E的题解都写完了
当时这场比赛的时候正在补作业TAT，本来rating肯定可以加的……
略可惜……
评论 (0)
