用户工具

站点工具


2020-2021:teams:die_java:front_page_summertrain14

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

2020-2021:teams:die_java:front_page_summertrain14 [2020/08/28 17:07]
fyhssgss 创建
2020-2021:teams:die_java:front_page_summertrain14 [2020/08/28 21:21] (当前版本)
mychael
行 12: 行 12:
  
 ===== A - Xiongnu’s Land ===== ===== A - Xiongnu’s Land =====
 +
 +将一个矩形区域用一条竖直的线一分为二,使得左边绿洲区域大于等于右边且二者差别尽量小,在此基础上使左边区域尽量大
  
 === 题解 === === 题解 ===
  
-<hidden 代码><​code cpp>+枚举分界点即可
  
 +<hidden 代码><​code cpp>
 +#​include<​algorithm>​
 +#​include<​iostream>​
 +#​include<​cstdlib>​
 +#​include<​cstring>​
 +#​include<​cstdio>​
 +#​include<​vector>​
 +#​include<​queue>​
 +#​include<​cmath>​
 +#​include<​map>​
 +#​include<​set>​
 +#define LL long long int
 +#define REP(i,n) for (int i = 1; i <= (n); i++)
 +#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
 +#define cls(s,v) memset(s,​v,​sizeof(s))
 +#define mp(a,b) make_pair<​int,​int>​(a,​b)
 +#define cp pair<​int,​int>​
 +using namespace std;
 +const int maxn = 1000005,​maxm = 100005;
 +const LL INF = 1000000000000000000ll;​
 +inline int read(){
 + int out = 0,flag = 1; char c = getchar();
 + while (c < 48 || c > 57){if (c == '​-'​) flag = 0; c = getchar();}
 + while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
 + return flag ? out : -out;
 +}
 +int N,n;
 +LL D[maxn],S;
 +int main(){
 + int T = read();
 + while (T--){
 + N = read();
 + n = read();
 + S = 0;
 + int x,y,w,h;
 + for (int i = 0; i <= N; i++) D[i] = 0;
 + REP(i,n){
 + x = read(); y = read(); w = read(); h = read();
 + h = min(h,y);
 + w = min(w,N - x);
 + D[x + w] -= h;
 + D[x] += h;
 + S += 1ll * w * h;
 + }
 + REP(i,N) D[i] += D[i - 1];
 + REP(i,N) {
 + D[i] += D[i - 1];
 + //if (i <= 10) printf("​%d ",​D[i]);​
 + }
 + //​puts(""​);​
 + LL mn = INF;
 + int l = 0;
 + for (int i = 0; i < N; i++)
 + if (D[i] >= S - D[i]){
 + if (abs(D[i] - (S - D[i])) <= mn){
 + mn = abs(D[i] - (S - D[i]));
 + l = i;
 + }
 + }
 + printf("​%d\n",​l + 1);
 + }
 + return 0;
 +}
 </​code></​hidden>​ </​code></​hidden>​
 ===== C - Today Is a Rainy Day ===== ===== C - Today Is a Rainy Day =====
2020-2021/teams/die_java/front_page_summertrain14.1598605677.txt.gz · 最后更改: 2020/08/28 17:07 由 fyhssgss