2019 杭电多校（第六场）

本文主要是介绍2019 杭电多校（第六场），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1005 Snowy Smile （线段树）

http://acm.hdu.edu.cn/showproblem.php?pid=6638

题意

给你n个点 让你画个矩形 使矩形内所含点的权值和最大（必须有点）

思路

离散化 枚举矩形的左右区间 线段树维护y坐标的最大字段和 （复杂度 O(n*n*lgn))

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 2e3+100;
int hax[maxn],hay[maxn];
struct point
{int x,y;ll w;
}po[maxn];
struct node
{ll sum,lmax,rmax,MAX;
}tree[maxn*4];
int n;
bool cmp(point a,point b)
{if(a.x == b.x) return a.y < b.y;else return a.x < b.x;
}
void build(int x,int l,int r)
{tree[x].sum = tree[x].lmax = tree[x].rmax = tree[x].MAX = 0;if(l == r){return ;}int mid = (l + r) / 2;build(x*2,l,mid);build(x*2+1,mid+1,r);
}
void updata(int x,int l,int r,int id,ll w)
{if(l==r){tree[x].sum += w;tree[x].lmax += w;tree[x].rmax += w;tree[x].MAX += w;return ;}int mid = (l + r) / 2;if(id <= mid) updata(x*2,l,mid,id,w);else updata(x*2+1,mid+1,r,id,w);tree[x].sum = tree[x*2].sum + tree[x*2+1].sum;tree[x].lmax = max(tree[x*2].lmax,tree[x*2].sum + tree[x*2+1].lmax);tree[x].rmax = max(tree[x*2+1].rmax, tree[x*2+1].sum + tree[x*2].rmax);tree[x].MAX = max(max(tree[x*2].MAX,tree[x*2+1].MAX),tree[x*2].rmax + tree[x*2+1].lmax);
}
ll query()
{return tree[1].MAX;
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i = 1;i <= n;i++){scanf("%d%d%lld",&po[i].x,&po[i].y,&po[i].w);hax[i] = po[i].x,hay[i] = po[i].y;}sort(hay+1,hay+1+n);int mm = unique(hay+1,hay+1+n) - (hay+1);sort(po+1,po+1+n,cmp);ll ans = 0;po[n+1].x = 13452353;for(int i = 1;i <= n;){build(1,1,mm);for(int j = i;j <= n;j++){int id = lower_bound(hay+1,hay+1+mm,po[j].y) - hay;updata(1,1,mm,id,po[j].w);if(po[j].x != po[j+1].x){ll sum = query();ans = max(ans,sum);}}i++;while(po[i].x == po[i-1].x){i++;}}printf("%lld\n",ans);}return 0;
}

10006 Faraway

http://acm.hdu.edu.cn/showproblem.php?pid=6639

题意 

求解方程

思路

对于每个式子 去绝对值后分为四个区间（加一横一竖）n个式子 就是n*n个区间

对着n*n个区间求解 将数分成 lcm(2,3,4,5) = 60种 即如果(x,y)满足这n个式子 那么(x+60,y+60)也一定满足这个式子

对每个区间60*60验证所有类型的数的组合 然后验证n个式子是否满足 满足的话计算着个区间里有多少种答案

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 20;
struct node
{ll x,y,k,t;
}a[maxn];
ll hax[maxn],hay[maxn];
ll n;
int check(int x,int y)
{for(int i = 1;i <= n;i++){if((abs(x-a[i].x) + abs(y-a[i].y)) % a[i].k != a[i].t) return 0;}return 1;
}
ll ok(ll l,ll r)
{ll len = r - l - 1;if(len < 0) return 0;return len / 60 + 1;
}
int main()
{int T;scanf("%d",&T);while(T--){ll m;scanf("%lld%lld",&n,&m);hax[1] = hay[1] = m+1;for(ll i = 1;i <= n;i++){scanf("%lld%lld%lld%lld",&a[i].x,&a[i].y,&a[i].k,&a[i].t);hax[i+1] = a[i].x,hay[i+1] = a[i].y;}sort(hax+1,hax+1+n+1);sort(hay+1,hay+1+n+1);ll ans = 0;for(int i = 0;i < n+1;i++){if(hax[i] == hax[i+1]) continue;for(int j = 0;j < n+1;j++){if(hay[j] == hay[j+1]) continue;
//                cout<<hax[i]<<" "<<hay[j]<<endl;for(int x = 0;x < 60;x++){for(int y = 0;y < 60;y++){if(check(hax[i]+x,hay[j]+y)){ans += ok(hax[i]+x,hax[i+1]) * ok(hay[j]+y,hay[j+1]);
//                            cout<<ans<<endl;}}}}}printf("%lld\n",ans);}return 0;
}

1008 TDL

http://acm.hdu.edu.cn/showproblem.php?pid=6641

题意

f(n,m) 表示大于n的第m小的与n互斥的数   (f(n,m)−n)^n=k 给你k m 求最小n

思路

m小于100  那么f(n,m)最大不会超过n+1000

设f(n,m) 为n + sum

(n + sum - n) ^ n == k  ==>  sum = k^n   ==>  n = sum^k

枚举sum从1到1000 求出n排序 挨个验证

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 1e5+100;
ll a[2200];
int ok(ll n,ll m,ll k)
{ll x = 1;for(ll i = n + 1;;i++){if((__gcd(n,i)) == 1){if(x == m){ll aa = (i-n)^n;if(aa == k){return 1;}else return 0;}x++;}}
}int main()
{int T;scanf("%d",&T);while(T--){ll m,k,n;scanf("%lld%lld",&k,&m);int f = 0;for(ll i = 1;i <= 2000;i++){a[i] = k ^ i;}sort(a+1,a+1+2000);for(ll i = 1;i <= 2000;i++){n = a[i];if(n == 0) continue;if(ok(n,m,k)){printf("%lld\n",n);f = 1;break;}}if(f == 0) printf("-1\n");}return 0;
}

1012 Stay Real

题意

。。。。。。

思路

签到题

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 1e5+100;
int a[maxn];
int main()
{int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);ll num = 0;for(int i = 1;i <= n;i++){scanf("%lld",&a[i]);num += a[i];}ll sum = 0;sort(a+1,a+1+n);for(int i = n;i >= 1;i-=2){sum += a[i];}printf("%lld %lld\n",sum,num-sum);}return 0;
}

 

这篇关于2019 杭电多校（第六场）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---