后来补题发现这场做的可真他妈傻逼
A.签到傻逼题，自己分情况
1 #include2 #include 3 #include 4 5 using std::vector; 6 using std::sort; 7 8 typedef long long ll; 9 10 int n, m;11 12 ll a[2100], b[2100];13 14 ll sa, sb, dis, tmp, qaq;15 16 int t1 = -1, t2 = -1;17 18 int a1, a2, a3, a4;19 20 struct node {21 ll x, y, z;22 bool operator < (const node &a) const {23 return x < a.x;24 }25 };26 27 vector e;28 29 ll abs(ll x) {30 return x < 0 ? -x : x;31 }32 33 node find1(ll x) {34 node ret = { 0, -1, -1};35 int l = 0, r = e.size() - 1, mid;36 while(l <= r) {37 int mid = (l + r) >> 1;38 if(e[mid].x * 2 <= x) ret = e[mid], l = mid + 1;39 else r = mid - 1;40 }41 return ret;42 }43 44 node find2(ll x) {45 node ret = { 0, -1, -1};46 int l = 0, r = e.size() - 1, mid;47 while(l <= r) {48 int mid = (l + r) >> 1;49 if(e[mid].x * 2 > x) ret = e[mid], r = mid - 1;50 else l = mid + 1;51 }52 return ret;53 }54 55 int main() {56 scanf("%d", &n);57 for(int i = 1;i <= n;i ++)58 scanf("%lld", &a[i]), sa += a[i];59 scanf("%d", &m);60 for(int i = 1;i <= m;i ++)61 scanf("%lld", &b[i]), sb += b[i];62 if(abs(sa - sb) <= 1) {63 printf("%lld\n0\n", abs(sa - sb));64 return 0;65 }66 qaq = tmp = dis = sa - sb;67 for(int i = 1;i <= n;i ++) 68 for(int j = 1;j <= m;j ++)69 if(abs(qaq - (a[i] - b[j]) * 2) < abs(dis))70 dis = qaq - (a[i] - b[j]) * 2, t1 = i, t2 = j;71 for(int i = 1;i <= n;i ++)72 for(int j = i + 1;j <= n;j ++)73 e.push_back((node){a[i] + a[j], i, j});74 sort(e.begin(), e.end());75 for(int i = 1;i <= m;i ++)76 for(int j = i + 1;j <= m;j ++) {77 ll k = b[i] + b[j];78 node tt = find1(qaq + k * 2);79 if(tt.y != -1 && abs(qaq + k * 2 - tt.x * 2) < abs(tmp)) tmp = qaq + k * 2 - tt.x * 2, a1 = tt.y, a2 = i, a3 = tt.z, a4 = j;80 tt = find2(qaq + k * 2);81 if(tt.y != -1 && abs(qaq + k * 2 - tt.x * 2) < abs(tmp)) tmp = qaq + k * 2 - tt.x * 2, a1 = tt.y, a2 = i, a3 = tt.z, a4 = j;82 }83 if(abs(qaq) <= abs(dis) && abs(qaq) <= abs(tmp)) printf("%lld\n0\n", abs(qaq));84 else if(abs(dis) <= abs(tmp)) printf("%lld\n1\n%d %d", abs(dis), t1, t2);85 else printf("%lld\n2\n%d %d\n%d %d", abs(tmp), a1, a2, a3, a4);86 return 0;87 }
想写if-else结果写完if忘记else了
B.我是暴力的O(n^2logn)
首先如果只交换一个数，那O(n^2)都会算吧
那交换两个数呢，我把n个数两两结合并求和，再对他们排序
再枚举另一数组的数对，二分一下尝试更新答案
1 #include2 #include 3 #include 4 5 using std::vector; 6 using std::sort; 7 8 typedef long long ll; 9 10 int n, m;11 12 ll a[2100], b[2100];13 14 ll sa, sb, dis, tmp, qaq;15 16 int t1 = -1, t2 = -1;17 18 int a1, a2, a3, a4;19 20 struct node {21 ll x, y, z;22 bool operator < (const node &a) const {23 return x < a.x;24 }25 };26 27 vector e;28 29 ll abs(ll x) {30 return x < 0 ? -x : x;31 }32 33 node find1(ll x) {34 node ret = { 0, -1, -1};35 int l = 0, r = e.size() - 1, mid;36 while(l <= r) {37 int mid = (l + r) >> 1;38 if(e[mid].x * 2 <= x) ret = e[mid], l = mid + 1;39 else r = mid - 1;40 }41 return ret;42 }43 44 node find2(ll x) {45 node ret = { 0, -1, -1};46 int l = 0, r = e.size() - 1, mid;47 while(l <= r) {48 int mid = (l + r) >> 1;49 if(e[mid].x * 2 > x) ret = e[mid], r = mid - 1;50 else l = mid + 1;51 }52 return ret;53 }54 55 int main() {56 scanf("%d", &n);57 for(int i = 1;i <= n;i ++)58 scanf("%lld", &a[i]), sa += a[i];59 scanf("%d", &m);60 for(int i = 1;i <= m;i ++)61 scanf("%lld", &b[i]), sb += b[i];62 if(abs(sa - sb) <= 1) {63 printf("%lld\n0\n", abs(sa - sb));64 return 0;65 }66 qaq = tmp = dis = sa - sb;67 for(int i = 1;i <= n;i ++) 68 for(int j = 1;j <= m;j ++)69 if(abs(qaq - (a[i] - b[j]) * 2) < abs(dis))70 dis = qaq - (a[i] - b[j]) * 2, t1 = i, t2 = j;71 for(int i = 1;i <= n;i ++)72 for(int j = i + 1;j <= n;j ++)73 e.push_back((node){a[i] + a[j], i, j});74 sort(e.begin(), e.end());75 for(int i = 1;i <= m;i ++)76 for(int j = i + 1;j <= m;j ++) {77 ll k = b[i] + b[j];78 node tt = find1(qaq + k * 2);79 if(tt.y != -1 && abs(qaq + k * 2 - tt.x * 2) < abs(tmp)) tmp = qaq + k * 2 - tt.x * 2, a1 = tt.y, a2 = i, a3 = tt.z, a4 = j;80 tt = find2(qaq + k * 2);81 if(tt.y != -1 && abs(qaq + k * 2 - tt.x * 2) < abs(tmp)) tmp = qaq + k * 2 - tt.x * 2, a1 = tt.y, a2 = i, a3 = tt.z, a4 = j;82 }83 if(abs(qaq) <= abs(dis) && abs(qaq) <= abs(tmp)) printf("%lld\n0\n", abs(qaq));84 else if(abs(dis) <= abs(tmp)) printf("%lld\n1\n%d %d", abs(dis), t1, t2);85 else printf("%lld\n2\n%d %d\n%d %d", abs(tmp), a1, a2, a3, a4);86 return 0;87 }
补题的时候，就把比赛代码三个地方的 int 改成了long long就过了
C.别人补题写的DP一眼看不懂...反正数据范围也不大，我们来xjb乱搞吧
数据范围20，时间5s，没有直接爆搜的思路
答案在0-1之间，满足单调性...试试二分？那judge呢？暴力dfs枚举?
效率玄学？并没有关系！...就当试试咯...过了...比DP还快...
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 const double eps = 1e-14; 8 9 int n, L[21], R[21];10 11 double a[21];12 13 bool dfs(int i, int x) {14 if(i > n)15 return 1;16 int y = L[i] / x;17 if(L[i] % x) y ++;18 for(y *= x;y <= R[i];y += x)19 if(dfs(i + 1, y))20 return 1;21 return 0;22 }23 24 bool judge(double k) {25 for(int i = 1;i <= n;i ++)26 L[i] = ceil(a[i] - a[i] * k), R[i] = floor(a[i] + a[i] * k);27 for(int i = L[1];i <= R[1];i ++)28 if(dfs(2, i))29 return 1;30 return 0;31 }32 33 int main() {34 scanf("%d", &n);35 for(int i = 1;i <= n;i ++)36 scanf("%lf", &a[i]);37 double l = 0, r = 1.0, mid, ans;38 for(int t = 66;t --;) {39 mid = (l + r) / 2;40 if(judge(mid)) ans = mid, r = mid - eps;41 else l = mid + eps;42 }43 printf("%.12f", ans);44 return 0;45 }
看了别人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)回答
1 #include2 3 typedef long long ll; 4 5 const int maxn = 1000010; 6 7 ll a[maxn], b[maxn]; 8 9 ll c(ll x) {10 return x * (x - 1) * (x - 2) / 6;11 }12 13 int main() {14 for(int i = 3;i <= 1000000;i ++) a[i] = (i + 1) / 2 - 1;15 for(int i = 4, j = 0;i <= 1000000;i ++) {16 if(!(i & 1)) j ++;17 b[i] = b[i - 1] + j;18 } 19 for(int i = 3;i <= 1000000;i ++) a[i] += a[i - 1], b[i] += b[i - 1];20 int n;21 while(scanf("%d", &n), n >= 3) printf("%lld\n", c(n) - a[n] - b[n]);22 return 0;23 }
E.