bupt summer training for 16 #3 —

后来补题发现这场做的可真他妈傻逼

A.签到傻逼题，自己分情况

 #include <cstdio>

 #include <vector>

 #include <algorithm>

 using std::vector;

 using std::sort;

 typedef long long ll;

 int n, m;

 ll a[], b[];

 ll sa, sb, dis, tmp, qaq;

 int t1 = -, t2 = -;

 int a1, a2, a3, a4;

 struct node {

     ll x, y, z;

     bool operator < (const node &a) const {

         return x < a.x;

     }

 };

 vector <node> e;

 ll abs(ll x) {

     return x <  ? -x : x;

 }

 node find1(ll x) {

     node ret = {, -, -};

     int l = , r = e.size() - , mid;

     while(l <= r) {

         int mid = (l + r) >> ;

         if(e[mid].x *  <= x) ret = e[mid], l = mid + ;

         else r = mid - ;

     }

     return ret;

 }

 node find2(ll x) {

     node ret = {, -, -};

     int l = , r = e.size() - , mid;

     while(l <= r) {

         int mid = (l + r) >> ;

         if(e[mid].x *  > x) ret = e[mid], r = mid - ;

         else l = mid + ;

     }

     return ret;

 }

 int main() {

     scanf("%d", &n);

     for(int i = ;i <= n;i ++)

         scanf("%lld", &a[i]), sa += a[i];

     scanf("%d", &m);

     for(int i = ;i <= m;i ++)

         scanf("%lld", &b[i]), sb += b[i];

     if(abs(sa - sb) <= ) {

         printf("%lld\n0\n", abs(sa - sb));

         return ;

     }

     qaq = tmp = dis = sa - sb;

     for(int i = ;i <= n;i ++)

         for(int j = ;j <= m;j ++)

             if(abs(qaq - (a[i] - b[j]) * ) < abs(dis))

                 dis = qaq - (a[i] - b[j]) * , t1 = i, t2 = j;

     for(int i = ;i <= n;i ++)

         for(int j = i + ;j <= n;j ++)

             e.push_back((node){a[i] + a[j], i, j});

     sort(e.begin(), e.end());

     for(int i = ;i <= m;i ++)

         for(int j = i + ;j <= m;j ++) {

             ll k = b[i] + b[j];

             node tt = find1(qaq + k * );

             if(tt.y != - && abs(qaq + k *  - tt.x * ) < abs(tmp)) tmp = qaq + k *  - tt.x * , a1 = tt.y, a2 = i, a3 = tt.z, a4 = j;

             tt = find2(qaq + k * );

             if(tt.y != - && abs(qaq + k *   - tt.x * ) < abs(tmp)) tmp = qaq + k *  - tt.x * , a1 = tt.y, a2 = i, a3 = tt.z, a4 = j;

         }

     if(abs(qaq) <= abs(dis) && abs(qaq) <= abs(tmp)) printf("%lld\n0\n", abs(qaq));

     else if(abs(dis) <= abs(tmp)) printf("%lld\n1\n%d %d", abs(dis), t1, t2);

     else printf("%lld\n2\n%d %d\n%d %d", abs(tmp), a1, a2, a3, a4);

     return ;

  }

想写if-else结果写完if忘记else了

B.我是暴力的O(n^2logn)

首先如果只交换一个数，那O(n^2)都会算吧

那交换两个数呢，我把n个数两两结合并求和，再对他们排序

再枚举另一数组的数对，二分一下尝试更新答案

 #include <cstdio>

 #include <vector>

 #include <algorithm>

 using std::vector;

 using std::sort;

 typedef long long ll;

 int n, m;

 ll a[], b[];

 ll sa, sb, dis, tmp, qaq;

 int t1 = -, t2 = -;

 int a1, a2, a3, a4;

 struct node {

     ll x, y, z;

     bool operator < (const node &a) const {

         return x < a.x;

     }

 };

 vector <node> e;

 ll abs(ll x) {

     return x <  ? -x : x;

 }

 node find1(ll x) {

     node ret = {, -, -};

     int l = , r = e.size() - , mid;

     while(l <= r) {

         int mid = (l + r) >> ;

         if(e[mid].x *  <= x) ret = e[mid], l = mid + ;

         else r = mid - ;

     }

     return ret;

 }

 node find2(ll x) {

     node ret = {, -, -};

     int l = , r = e.size() - , mid;

     while(l <= r) {

         int mid = (l + r) >> ;

         if(e[mid].x *  > x) ret = e[mid], r = mid - ;

         else l = mid + ;

     }

     return ret;

 }

 int main() {

     scanf("%d", &n);

     for(int i = ;i <= n;i ++)

         scanf("%lld", &a[i]), sa += a[i];

     scanf("%d", &m);

     for(int i = ;i <= m;i ++)

         scanf("%lld", &b[i]), sb += b[i];

     if(abs(sa - sb) <= ) {

         printf("%lld\n0\n", abs(sa - sb));

         return ;

     }

     qaq = tmp = dis = sa - sb;

     for(int i = ;i <= n;i ++)

         for(int j = ;j <= m;j ++)

             if(abs(qaq - (a[i] - b[j]) * ) < abs(dis))

                 dis = qaq - (a[i] - b[j]) * , t1 = i, t2 = j;

     for(int i = ;i <= n;i ++)

         for(int j = i + ;j <= n;j ++)

             e.push_back((node){a[i] + a[j], i, j});

     sort(e.begin(), e.end());

     for(int i = ;i <= m;i ++)

         for(int j = i + ;j <= m;j ++) {

             ll k = b[i] + b[j];

             node tt = find1(qaq + k * );

             if(tt.y != - && abs(qaq + k *  - tt.x * ) < abs(tmp)) tmp = qaq + k *  - tt.x * , a1 = tt.y, a2 = i, a3 = tt.z, a4 = j;

             tt = find2(qaq + k * );

             if(tt.y != - && abs(qaq + k *   - tt.x * ) < abs(tmp)) tmp = qaq + k *  - tt.x * , a1 = tt.y, a2 = i, a3 = tt.z, a4 = j;

         }

     if(abs(qaq) <= abs(dis) && abs(qaq) <= abs(tmp)) printf("%lld\n0\n", abs(qaq));

     else if(abs(dis) <= abs(tmp)) printf("%lld\n1\n%d %d", abs(dis), t1, t2);

     else printf("%lld\n2\n%d %d\n%d %d", abs(tmp), a1, a2, a3, a4);

     return ;

  }

补题的时候，就把比赛代码三个地方的 int 改成了long long就过了

C.别人补题写的DP一眼看不懂...反正数据范围也不大，我们来xjb乱搞吧

数据范围20，时间5s，没有直接爆搜的思路

答案在0-1之间，满足单调性...试试二分？那judge呢？暴力dfs枚举?

效率玄学？并没有关系！...就当试试咯...过了...比DP还快...

 #include <cmath>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const double eps = 1e-;

 int n, L[], R[];

 double a[];

 bool dfs(int i, int x) {

     if(i > n)

         return ;

     int y = L[i] / x;

     if(L[i] % x) y ++;

     for(y *= x;y <= R[i];y += x)

         if(dfs(i + , y))

             return ;

     return ;

 }

 bool judge(double k) {

     for(int i = ;i <= n;i ++)

         L[i] = ceil(a[i] - a[i] * k), R[i] = floor(a[i] + a[i] * k);

     for(int i = L[];i <= R[];i ++)

         if(dfs(, i))

             return ;

     return ;

 }

 int main() {

     scanf("%d", &n);

     for(int i = ;i <= n;i ++)

         scanf("%lf", &a[i]);

     double l = , r = 1.0, mid, ans;

     for(int t = ;t --;) {

         mid = (l + r) / ;

         if(judge(mid)) ans = mid, r = mid - eps;

         else l = mid + eps;

     }

     printf("%.12f", ans);

     return ;

 }

看了别人DP代码...看懂了...

f[i][j]代表把第 i 种货币变成 j 的最小答案

我们有一种无赖解是把所有货币都变0

所以对于第 i 种货币，从 0 枚举到 a[i] * 2 就可以啦

复杂度O(nklogk)， k = max(a[i]) = 20W

这么来说粗略计算我的做法复杂度就是O(nklogk * log(1/eps))...实际优太多

D.ans = C(n，3) - 不合法的三角形

对于非法三角形枚举最大边 z

再求 x + y <= z 的 (x，y) 有多少对即可

预处理，O(1)回答

 #include <cstdio>

 typedef long long ll;

 const int maxn = ;

 ll a[maxn], b[maxn];

 ll c(ll x) {

     return x * (x - ) * (x - ) / ;

 }

 int main() {

     for(int i = ;i <= ;i ++) a[i] = (i + ) /  - ;

     for(int i = , j = ;i <= ;i ++) {

         if(!(i & )) j ++;

         b[i] = b[i - ] + j;

     }

     for(int i = ;i <= ;i ++) a[i] += a[i - ], b[i] += b[i - ];

     int n;

     while(scanf("%d", &n), n >= ) printf("%lld\n", c(n) - a[n] - b[n]);

     return ;

 }

巴特西

bupt summer training for 16 #3 ——构造

最新文章

热门文章