LCCUP'21春季编程大赛-团队赛(4.10)
1. 蓄水
2. 二叉树染色
3. 电动车游城市
4. 最多牌组数
5. 最小矩形面积
6. 守卫城堡
答案
1. 蓄水
第一名答案
class Solution {
public:
int storeWater(vector<int>& bucket, vector<int>& vat) {
int ans=1e9;
if(*max_element(vat.begin(),vat.end())==0)return 0;
for(int i=1;i<=10000;++i){
int n=vat.size(),sum=i;
for(int j=0;j<n;++j){
sum+=max(0,(vat[j]+i-1)/i-bucket[j]);
}
ans=min(ans,sum);
}
return ans;
}
};第二名答案
class Solution {
public:
int storeWater(vector<int>& b, vector<int>& v) {
int n = b.size();
if (count(v.begin(), v.end(), 0) == n){
return 0;
}
int ans = 100000000;
for (int i = 1; i <= 10000; ++i){
int s = i;
for (int j = 0; j < n; ++j)
s += max(0, (v[j] + i - 1) / i - b[j]);
ans = min(ans, s);
}
return ans;
}
};第三名答案
2. 二叉树染色
第一名答案
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> dfs(TreeNode* root, int k){
if (root==NULL){
vector<int> res;
res.push_back(0);
return res;
}
vector<int> vl=dfs(root->left ,k);
vector<int> vr=dfs(root->right ,k);
vector<int> res;
res.resize(k+1);
for (int i=0;i<vl.size();i++)
for (int j=0;j<vr.size();j++){
res[0]=max(res[0],vl[i]+vr[j]);
if (i+j+1<=k)
res[i+j+1]=max(res[i+j+1],vl[i]+vr[j]+root->val);
}
return res;
}
int maxValue(TreeNode* root, int k) {
vector<int> result=dfs(root,k);
int ans=0;
for (int i=0;i<=result.size();i++)
if (i<=k) ans=max(ans,result[i]);
return ans;
}
};第二名答案
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> dfs(TreeNode* now, int k) {
if (now->left == nullptr && now->right == nullptr) {
vector<int> ans(k + 1, 0);
ans[0] = 0;
ans[1] = now->val;
return ans;
}
if (now->left == nullptr) {
vector<int> ret = dfs(now->right, k);
vector<int> ans(k + 1, 0);
for (int i = 0; i < k; i++) {
ans[i + 1] = ret[i] + now->val;
ans[0] = max(ans[0], ret[i]);
}
ans[0] = max(ans[0], ret[k]);
return ans;
}
if (now->right == nullptr) {
vector<int> ret = dfs(now->left, k);
vector<int> ans(k + 1, 0);
for (int i = 0; i < k; i++) {
ans[i + 1] = ret[i] + now->val;
ans[0] = max(ans[0], ret[i]);
}
ans[0] = max(ans[0], ret[k]);
return ans;
}
vector<int> r1 = dfs(now->left, k);
vector<int> r2 = dfs(now->right, k);
vector<int> ans(k + 1, 0);
int p = 0, q = 0;
for (int i = 0; i <= k; i++) {
p = max(p, r1[i]);
q = max(q, r2[i]);
}
ans[0] = p + q;
for (int i = 0; i <= k; i++) {
for (int j = 0; j + i < k; j++) {
ans[i + j + 1] = max(ans[i + j + 1], r1[i] + r2[j] + now->val);
}
}
// cout << " ?? " << now->val << endl;
// for (auto &x : r1) cout << x << ' '; cout << endl;
// for (auto &x : r2) cout << x << ' '; cout << endl;
// for (auto &x : ans) cout << x << ' '; cout << endl;
return ans;
}
int maxValue(TreeNode* root, int k) {
if (root == nullptr) return 0;
vector<int> res = dfs(root, k);
int ans = 0;
for (auto &x : res) ans = max(ans, x);
return ans;
}
};第三名答案
class Solution {
public:
int K;
struct Data{
int a[2][20];
Data(){
memset(a,0,sizeof(a));
}
};
Data dfs(TreeNode* root){
if(!root){
return Data();
}
Data ret;
Data lres=dfs(root->left);
Data rres=dfs(root->right);
for(int s=0;s<2;++s){
for(int i=0;i<=K;++i)ret.a[s][i]=-5e8;
if(s==0){
int mx1=0,mx2=0;
for(int i=0;i<=K;++i)mx1=max(mx1,lres.a[0][i]),mx1=max(mx1,lres.a[1][i]);
for(int i=0;i<=K;++i)mx2=max(mx2,rres.a[0][i]),mx2=max(mx2,rres.a[1][i]);
ret.a[0][0]=mx1+mx2;
} else {
for(int i=0;i<=K;++i)
for(int j=0;i+j<=K;++j){
int L=lres.a[1][i],R=rres.a[1][j];
L=max(L,lres.a[0][i]),R=max(R,rres.a[0][j]);
// printf("[%d,%d(%d,%d)]",L,R,root->val,i+j);
ret.a[1][i+j+1]=max(ret.a[1][i+j+1],L+R+root->val);
}
}
}
return ret;
}
int maxValue(TreeNode* root, int k) {
K=k;
Data ans=dfs(root);
int mx=0;
for(int i=0;i<2;++i)for(int j=0;j<=K;++j)
mx=max(mx,ans.a[i][j]);
return mx;
}
};3. 电动车游城市
第一名答案
class Solution {
public:
int f[110][110],dis[110][110];
set<pair<int,int> > s;
struct node{int to,next;}e[2010];
void upd(int x,int y,int d)
{
if (dis[x][y]<=d&&d<1000000000) return;
s.erase(make_pair(dis[x][y],x*1000+y));
dis[x][y]=d;
s.insert(make_pair(dis[x][y],x*1000+y));
}
int electricCarPlan(vector<vector<int>>& paths, int cnt, int start, int end, vector<int>& charge) {
int n=charge.size(),m=paths.size(),c=0;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) f[i][j]=cnt*n*10;
for (int i=0; i<m; i++) f[paths[i][0]][paths[i][1]]=min(f[paths[i][0]][paths[i][1]],paths[i][2]);
for (int i=0; i<n; i++)
{
f[i][i]=0;
for (int j=0; j<n; j++) f[i][j]=min(f[i][j],f[j][i]);
}
for (int k=0; k<n; k++)
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
s.clear();
for (int i=0; i<n; i++)
for (int j=0; j<=cnt; j++) upd(i,j,1000000000);
upd(start,0,0);
while (1)
{
int x=(*s.begin()).second/1000,y=(*s.begin()).second%1000;
if (x==end) return dis[x][y];
s.erase(s.begin());
if (y<cnt) upd(x,y+1,dis[x][y]+charge[x]);
for (int i=0; i<n; i++) if (f[x][i]<=y) upd(i,y-f[x][i],dis[x][y]+f[x][i]);
}
}
};第二名答案
const int MAXN = 222;
struct pt {
int u, crg; //, tm;
};
// bool operator < (const pt & a, const pt & b) {
// return a.tm > b.tm;
// }
typedef pair<int,int> PII;
int f[MAXN][MAXN], vis[MAXN][MAXN];
vector<PII> E[MAXN];
int dis[MAXN][MAXN];
const int INF = 1e9 + 7;
class Solution {
public:
int electricCarPlan(vector<vector<int>>& path, int cnt, int start, int end, vector<int>& charge) {
int n = charge.size();
for (int i = 0; i < n; i++) {
E[i].clear();
for (int j = 0; j <= cnt; j++) f[i][j] = INF, vis[i][j] = 0;
// for (int j = 0; j < n; j++) dis[i][j] = INF;
}
for (auto &e : path) {
E[e[0]].emplace_back(e[1], e[2]);
E[e[1]].emplace_back(e[0], e[2]);
// dis[e[0]][e[1]] = dis[e[1]][e[0]] = min(dis[e[1]][e[0]], e[2]);
}
// for (int k = 0; k < n; k++) {
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
// }
// }
// }
f[start][0] = 0;
vis[start][0] = 1;
queue<pt> Q;
Q.push((pt){start, 0});
while (!Q.empty()) {
auto nico = Q.front();
int u = nico.u;
int crg = nico.crg;
Q.pop();
vis[u][crg] = 0;
for (int i = crg + 1; i <= cnt; i++) {
if (f[u][i] > f[u][crg] + charge[u] * (i - crg)) {
f[u][i] = f[u][crg] + charge[u] * (i - crg);
if (!vis[u][i]) {
vis[u][i] = 1;
Q.push((pt){u, i});
}
}
}
for (auto &x : E[u]) {
int y = x.first;
int rm = crg - x.second;
if (rm >= 0 && f[y][rm] > f[u][crg] + x.second) {
f[y][rm] = f[u][crg] + x.second;
if (!vis[y][rm]) {
vis[y][rm] = 1;
Q.push((pt){y, rm});
}
}
}
}
int ans = INF;
for (int j = 0; j <= cnt; j++) {
ans = min(ans, f[end][j]);
}
return ans;
}
};第三名答案
class Solution {
public:
int electricCarPlan(vector<vector<int>>& paths, int cnt, int start, int end, vector<int>& charge) {
int n = charge.size();
int m = paths.size();
vector<vector<pair<int, int> > > G(n, vector<pair<int, int> > (0));
for (int i = 0; i < m; i++) {
G[paths[i][0]].push_back(make_pair(paths[i][2], paths[i][1]));
G[paths[i][1]].push_back(make_pair(paths[i][2], paths[i][0]));
}
vector<vector<int> > dis(n, vector<int> (cnt + 1, 0x3f3f3f3f));
dis[start][0] = 0;
priority_queue<pair<int, pair<int, int> > > q;
q.push(make_pair(0, make_pair(start, 0)));
while (!q.empty()) {
auto x = q.top();
int d = -x.first;
int u = x.second.first, v = x.second.second;
q.pop();
if (d != dis[u][v]) continue;
if (v != cnt) {
if (dis[u][v + 1] > dis[u][v] + charge[u]) {
dis[u][v + 1] = dis[u][v] + charge[u];
q.push(make_pair(-dis[u][v + 1], make_pair(u, v + 1)));
}
}
for (auto y : G[u]) {
if (v >= y.first) {
if (dis[y.second][v - y.first] > dis[u][v] + y.first) {
dis[y.second][v - y.first] = dis[u][v] + y.first;
q.push(make_pair(-dis[y.second][v - y.first], make_pair(y.second, v - y.first)));
}
}
}
}
return dis[end][0];
}
};4. 最多牌组数
第一名答案
class Solution {
public:
int dp[2][3][3];
int maxGroupNumber(vector<int>& tiles) {
int last=-1;
bool d=0;
map<int,int> cnt;
for(auto x:tiles)++cnt[x];
for(auto pr:cnt){
int x=pr.first,c=pr.second;
if(x-last>1){
for(int i=0;i<3;++i)
for(int j=0;j<3;++j)
if(i+j)
dp[d][i][j]=-1e9;
}
last=x;
x=c;
d^=1;
for(int i=0;i<3;++i)
for(int j=0;j<3;++j)
dp[d][i][j]=-1e9;
for(int c3=0;c3<=min(2,x);++c3)
for(int c2=0;c2<=min(2,x-c3);++c2)
for(int c1=0;c1<=min(2,x-c2-c3);++c1)
{
dp[d][c1][c2]=max(dp[d][c1][c2],dp[d^1][c2][c3]+c3+(x-c1-c2-c3)/3);
}
}
return dp[d][0][0];
}
};第二名答案
int dp[2][5][5];
class Solution {
public:
int maxGroupNumber(vector<int>& t) {
map<int, int> lst;
for (auto x: t)
++lst[x];
memset(dp, -1, sizeof(dp));
dp[0][0][0] = 0;
int ri = 0;
int pre[2] = {-2, -1};
for (auto pr: lst){
int x = pr.first, c = pr.second;
auto (&f) = dp[ri & 1];
auto (&g) = dp[ri + 1 & 1];
ri += 1;
memset(g, -1, sizeof(g));
for (int i = 0; i <= 2; ++i){
if (c < i) continue;
if (i > 0 && !(pre[0] + 1 == pre[1] && pre[1] + 1 == x)) continue;
for (int j = i; j <= 4; ++j)
for (int k = i; k <= 4; ++k){
if (f[j][k] == -1) continue;
int tc = c - i;
for (int l = 0; l <= 4 && tc >= l; ++l)
g[k - i][l] = max(g[k - i][l], f[j][k] + i + (tc - l) / 3);
//printf("%d %d %d %d, %d %d\n", i, j, k, g[0][0], tc, f[j][k]);
}
}
for (int j = 4; j >= 0; --j)
for (int k = 4; k >= 0; --k){
if (j > 0) g[j - 1][k] = max(g[j - 1][k], g[j][k]);
if (k > 0) g[j][k - 1] = max(g[j][k - 1], g[j][k]);
}
pre[0] = pre[1];
pre[1] = x;
}
return dp[ri & 1][0][0];
}
};第三名答案
class Solution {
public:
int maxGroupNumber(vector<int>& tiles) {
int n = tiles.size();
map<int, int> c;
int f[3][3], g[3][3];
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) f[i][j] = g[i][j] = 0;
for (int i = 0; i < n; i++) {
c[tiles[i]]++;
}
int las = -4, cur;
for (auto x : c) {
cur = x.first;
if (cur == las + 1) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (i + j + k > (c.count(cur)?c[cur]:0)) continue;
if (j + k > (c.count(cur+1)?c[cur+1]:0)) continue;
if (k > (c.count(cur+2)?c[cur+2]:0)) continue;
g[j][k] = max(g[j][k], f[i][j] + k + ((int) (c.count(cur)?c[cur]:0) - i - j - k) / 3);
}
}
}
} else {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (k > (c.count(cur)?c[cur]:0)) continue;
if (k > (c.count(cur+1)?c[cur+1]:0)) continue;
if (k > (c.count(cur+2)?c[cur+2]:0)) continue;
g[0][k] = max(g[0][k], f[i][j] + k + ((int) (c.count(cur)?c[cur]:0) - k) / 3);
}
}
}
}
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
f[i][j] = g[i][j];
g[i][j] = 0;
}
las = cur;
}
int ans = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
ans = max(ans, f[i][j]);
}
}
return ans;
}
};5. 最小矩形面积
第一名答案
bool cmp1(const vector<int> &a,const vector<int> &b){
return a[0]==b[0]?a[1]>b[1]:a[0]<b[0];
}
bool cmp2(const vector<int> &a,const vector<int> &b){
return a[0]==b[0]?a[1]>b[1]:a[0]>b[0];
}
class Solution {
public:
double solve1(vector<vector<int> >& lines){
double p=1e18;
sort(lines.begin(),lines.end(),cmp1);
for (int i=1;i<lines.size();i++)
if (lines[i][0]!=lines[i-1][0]){
double px=-(lines[i][1]-lines[i-1][1])*1.0/(lines[i][0]-lines[i-1][0]);
p=min(p,px);
}
return p;
}
double solve2(vector<vector<int> >& lines){
double p=-1e18;
sort(lines.begin(),lines.end(),cmp2);
for (int i=1;i<lines.size();i++)
if (lines[i][0]!=lines[i-1][0]){
double px=-(lines[i][1]-lines[i-1][1])*1.0/(lines[i][0]-lines[i-1][0]);
p=max(p,px);
}
return p;
}
double solve3(vector<vector<int> >& lines){
double p=1e18;
sort(lines.begin(),lines.end(),cmp1);
for (int i=1;i<lines.size();i++)
if (lines[i][0]!=lines[i-1][0]){
double px=-(lines[i][1]-lines[i-1][1])*1.0/(lines[i][0]-lines[i-1][0]);
double py=px*lines[i][0]+lines[i][1];
p=min(p,py);
}
return p;
}
double solve4(vector<vector<int> >& lines){
double p=-1e18;
sort(lines.begin(),lines.end(),cmp2);
for (int i=1;i<lines.size();i++)
if (lines[i][0]!=lines[i-1][0]){
double px=-(lines[i][1]-lines[i-1][1])*1.0/(lines[i][0]-lines[i-1][0]);
double py=px*lines[i][0]+lines[i][1];
p=max(p,py);
}
return p;
}
double minRecSize(vector<vector<int> >& lines) {
bool flag=0;
for (auto i:lines)
if (i[0]!=lines.back()[0])
flag=1;
if (!flag)
return 0;
double v1=solve1(lines);
double v2=solve2(lines);
double v3=solve3(lines);
double v4=solve4(lines);
return (v2-v1)*(v4-v3);
}
};第二名答案
typedef long long ll;
class Solution {
public:
double minRecSize(vector<vector<int>>& f) {
int n = f.size();
vector<ll> k(n, 0), b(n, 0);
sort(f.begin(), f.end());
double ans = 0;
for (int i = 0; i < n; i++) {
k[i] = f[i][0];
b[i] = f[i][1];
}
int p = 0, q = 0;
while (q < n && k[q] == k[p]) q++;
if (q >= n) return 0.;
double x_min = 1e100, x_max = -1e100;
double y_min = 1e100, y_max = -1e100;
for (; q < n;) {
int r = q;
while (r + 1 < n && k[r + 1] == k[q]) r++;
// [p, q - 1], [q, r]
double cx1 = 1.0 * (b[r] - b[p]) / (k[r] - k[p]);
double cx2 = 1.0 * (b[q] - b[q - 1]) / (k[q] - k[q - 1]);
x_min = min(x_min, min(cx1, cx2));
x_max = max(x_max, max(cx1, cx2));
double cy1 = 1.0 * (b[r] * k[p] - b[p] * k[r]) / (k[r] - k[p]);
double cy2 = 1.0 * (b[q] * k[q - 1] - b[q - 1] * k[q]) / (k[q] - k[q - 1]);
y_min = min(y_min, min(cy1, cy2));
y_max = max(y_max, max(cy1, cy2));
p = q;
while (q < n && k[q] == k[p]) q++;
}
return (x_max - x_min) * (y_max - y_min);
}
};第三名答案
#include<bits/stdc++.h>
#define min min111
#define max max111
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;
#define xx first
#define yy second
template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;}
template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}}
template<typename T> inline T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define I __attribute__((always_inline))inline
#define mset(a,b) memset(a,b,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))
#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define fd0(i,n) for(int i=(n)-1;~i;i--)
#define fd1(i,n) for(int i=n;i;i--)
#define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define foe(i,x)for(__typeof((x).end())i=(x).begin();i!=(x).end();++i)
#define fre(i,x)for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i)
#ifdef LOCAL
struct Cg{I char operator()(){return getchar();}};
struct Cp{I void operator()(char x){putchar(x);}};
#define OP operator
#define RT return *this;
#define UC unsigned char
#define RX x=0;UC t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\
if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x
#define RU x=0;UC t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x;
I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int&x)
{RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char&x)
{for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char*x){char t=P();for(;IS(t);t=P());if(~t){for(;!IS
(t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf&x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf&x){RX;RL;RT}I OP llf()
{llf x;TR}I Fr&OP,(uint&x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull&x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in;
#define WI(S) if(x){if(x<0)P('-'),x=-x;UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\
x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5);
#define WU(S) if(x){UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT}
I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(38);RT}I Fw&OP,(ull x){WU(20);RT}I Fw&OP()
(ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char*x){while(*x)P(*x++);RT}
I Fw&OP()(const char*x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out;
#endif
using std::string;
using std::vector;
const int N=100007;
int n,cp[N];
lf k[N],b[N];
std::pair<lf,int>c[N],d[N];
void upd(lf&xmin,lf&xmax,lf k1,lf b1,lf k2,lf b2)
{
if(abs(k1-k2)/k1<1e-6)return;
lf u=(b1-b2)/(k2-k1);
//printf("upd: %.5f %.5f %.5f %.5f %.5f\n",k1,b1,k2,b2,u);
repl(xmin,u),repr(xmax,u);
}
void tsolve(lf l,lf r,lf&xmin,lf&xmax)
{
//printf("tsolve:%.5f %.5f %.5f %.5f\n",l,r,xmin,xmax);
fo0(i,n)c[i]=mp(l*k[i]+b[i],i),d[i]=mp(r*k[i]+b[i],i);
std::sort(c,c+n);
std::sort(d,d+n);
fo0(i,n)cp[c[i].yy]=i;
std::set<int>tmp;
fo0(i,n)
{
int u=cp[d[i].yy];
std::set<int>::iterator t=tmp.lower_bound(u);
while(t!=tmp.end())
{
upd(xmin,xmax,k[d[i].yy],b[d[i].yy],k[c[*t].yy],b[c[*t].yy]);
++t;
}
tmp.insert(u);
}
}
void solve(lf&xmin,lf&xmax)
{
//out,"solve\n";
// first sample n points
std::mt19937 ran(114514);
fo0(i,n)
{
int x=ran()%n,y=ran()%(n-1);
if(y>=x)y++;
upd(xmin,xmax,k[x],b[x],k[y],b[y]);
}
//tsolve(-1e15,1e10,xmin,xmax);
tsolve(-1e20,xmin,xmin,xmax);
tsolve(xmax,1e20,xmin,xmax);
}
void flip()
{
fo0(i,n)
{
//kx+b=0
lf nb=-b[i]/k[i];
lf nk=1/k[i];
k[i]=nk,b[i]=nb;
}
}
class Solution {
public:
double minRecSize(vector<vector<int>>& lines) {
n=lines.size();
fo0(i,n)k[i]=lines[i][0],b[i]=lines[i][1];
std::set<int>ks;
fo0(i,n)ks.insert(lines[i][0]);
if(ks.size()==1)return 0;
lf xmax=-1e20,xmin=1e20,ymax=-1e20,ymin=1e20;
solve(xmin,xmax);
flip();
solve(ymin,ymax);
//int i=28,j=20;upd(ymin,ymax,k[i],b[i],k[j],b[j]);
//printf("%.5f %.5f %.5f %.5f\n",xmin,xmax,ymin,ymax);
return (xmax-xmin)*(ymax-ymin);
}
};
#ifdef LOCAL
class Solution2 {
public:
double minRecSize(vector<vector<int>>& lines) {
n=lines.size();
fo0(i,n)k[i]=lines[i][0],b[i]=lines[i][1];
lf xmax=-1e20,xmin=1e20,ymax=-1e20,ymin=1e20;
//fo0(i,n)fo0(j,n)upd(xmin,xmax,k[i],b[i],k[j],b[j]);
//flip();
//fo0(i,n)fo0(j,n)upd(ymin,ymax,k[i],b[i],k[j],b[j]);
fo0(i,n)fo0(j,i)
{
lf k1=k[i],b1=b[i],k2=k[j],b2=b[j];
if(abs(k1-k2)<1e-6)continue;
lf u1=1/k1,v1=-b1/k1,u2=1/k2,v2=-b2/k2;
lf x=(b1-b2)/(k2-k1);
lf y=x*k1+b1;
//if(y<-2e6||y>2e6)printf("%d %d %.5f %.5f %.5f\n",i,j,x,y,(v1-v2)/(u2-u1));
repl(xmin,x),repr(xmax,x),repl(ymin,y),repr(ymax,y);
}
printf("%.5f %.5f %.5f %.5f\n",xmin,xmax,ymin,ymax);
return (xmax-xmin)*(ymax-ymin);
}
};
int main()
{
/*vector<int> t1({2,3});
vector<int> t2({3,0});
vector<int> t3({4,1});
vector<vector<int>>t({t1,t2,t3});*/
vector<vector<int>>t;
fo0(T,1)
{
t.clear();
fo0(i,1000)
{
t.pb(vector<int>({rand()%10000+1,rand()%20001-10000}));
}
lf a=Solution().minRecSize(t);
lf b=Solution2().minRecSize(t);
printf("%.5f %.5f\n",a,b);
if(abs(a-b)>1e-4)printf("%.5f %.5f\n",a,b);
}
//out,Solution().purchasePlans(t,10),'\n';
//out,Solution().orchestraLayout(3,0,2),'\n';
//int n=9;fo0(i,n){fo0(j,n)out,Solution().orchestraLayout(n,i,j),' ';out,'\n';}
}
#endif6. 守卫城堡
第一名答案
class Solution {
public:
struct node{int to,next,c;}e[1000010];
int n,dis[50010],q[50010],l,r,hd[50010],cnt,cur[50010];
void add(int x,int y,int c)
{
e[++cnt]=(node){y,hd[x],c},hd[x]=cnt;
e[++cnt]=(node){x,hd[y],0},hd[y]=cnt;
}
bool bfs()
{
for (int i=2 ;i<=n; i++) dis[i]=-1;
dis[1]=0,q[l=r=1]=1;
while (l<=r)
{
int x=q[l++];
for (int i=hd[x]; i; i=e[i].next)
if (dis[e[i].to]==-1&&e[i].c) q[++r]=e[i].to,dis[e[i].to]=dis[x]+1;
}
return dis[n]!=-1;
}
int dfs(int x,int f)
{
if (x==n) return f;
for (int &i=cur[x]; i; i=e[i].next)
if (dis[e[i].to]==dis[x]+1&&e[i].c)
{
int nw=dfs(e[i].to,min(f,e[i].c));
if (nw) return e[i].c-=nw,e[i^1].c+=nw,nw;
}
return 0;
}
long long solve()
{
long long ans=0,nw;
while (bfs())
{
for (int i=1; i<=n; i++) cur[i]=hd[i];
while (nw=dfs(1,1000000000)) ans+=nw;
}
return ans;
}
int guardCastle(vector<string>& grid) {
memset(hd,0,sizeof(hd)),cnt=1;
int m=grid[0].length();
n=4*m+3;
for (int i=0; i<2; i++)
for (int j=0; j<m; j++)
if (grid[i][j]=='C') add(j*2+i+2,j*2+i+2+2*m,1000000000),add(j*2+i+2+2*m,4*m+3,1000000000); else
if (grid[i][j]=='P') add(j*2+i+2,j*2+i+2+2*m,1000000000),add(j*2+i+2+2*m,4*m+2,1000000000),add(4*m+2,j*2+i+2,1000000000); else
if (grid[i][j]=='.') add(j*2+i+2,j*2+i+2+2*m,1); else
if (grid[i][j]=='S') add(1,j*2+i+2,1000000000),add(j*2+i+2,j*2+i+2+2*m,1000000000);
for (int j=0; j<m; j++)
{
add(j*2+1+2+2*m,j*2+2,1000000000);
add(j*2+2+2*m,j*2+1+2,1000000000);
}
for (int j=1; j<m; j++)
{
add(j*2+1+2+2*m,(j-1)*2+1+2,1000000000);
add((j-1)*2+1+2+2*m,j*2+1+2,1000000000);
add(j*2+2+2*m,(j-1)*2+2,1000000000);
add((j-1)*2+2+2*m,j*2+2,1000000000);
}
long long ans=solve();
if (ans>=1000000000) return -1; else return ans;
}
};第二名答案
class Solution {
public:
int n;
// i, monster, port, castle, monster--port, castle--port
int f[20010][4][4][4][2][2];
void upd(int &x, int y) {
x = min(x, y);
}
int guardCastle(vector<string>& grid) {
int n = grid[0].size();
const int INF = 1e8;
for (int i=0;i<=n;i++) {
for (int m=0;m<4;m++) {
for (int p=0;p<4;p++) {
for (int c=0;c<4;c++) {
for (int mp=0;mp<2;mp++) {
for (int cp=0;cp<2;cp++) {
f[i][m][p][c][mp][cp] = INF;
}
}
}
}
}
}
// i, monster, port, castle, monster--port, castle--port
f[0][0][0][0][0][0] = 0;
for (int i=0;i<n;i++) {
for (int m=0;m<4;m++) {
for (int p=0;p<4;p++) {
for (int c=0;c<4;c++) {
for (int mp=0;mp<2;mp++) {
for (int cp=0;cp<2;cp++) {
int now = f[i][m][p][c][mp][cp];
if (now == INF) continue;
int mup = (m & 1);
int mdown = (m >> 1);
int pup = (p & 1);
int pdown = (p >> 1);
int cup = (c & 1);
int cdown = (c >> 1);
/*
bool ok = true;
if (mup && grid[0][i+1] == 'C') ok = false;
if (mdown && grid[1][i+1] == 'C') ok = false;
if (cup && grid[0][i+1] == 'S') ok = false;
if (cdown && grid[1][i+1] == 'S') ok = false;
if (!ok) continue;
*/
int delta = 0;
// how to put stone
bool print = (i==3&&m==0&&p==1&&c==1&&mp==0&&cp==1);
for (int nn=0;nn<4;nn++) {
int up_stone = (nn & 1);
int down_stone = (nn >> 1);
int cost = __builtin_popcount(nn);
if (up_stone && grid[0][i] != '.') continue;
if (down_stone && grid[1][i] != '.') continue;
up_stone |= (grid[0][i] == '#');
down_stone |= (grid[1][i] == '#');
int new_mup = 0, new_mdown = 0, new_pup = 0, new_pdown = 0, new_cup = 0, new_cdown = 0;
int new_mp = mp, new_cp = cp;
if (!up_stone) {
new_mup = (grid[0][i] == 'S' || mup);
new_pup = (grid[0][i] == 'P' || pup);
new_cup = (grid[0][i] == 'C' || cup);
}
if (!down_stone) {
new_mdown = (grid[1][i] == 'S' || mdown);
new_pdown = (grid[1][i] == 'P' || pdown);
new_cdown = (grid[1][i] == 'C' || cdown);
}
if (!up_stone) {
new_mup |= new_mdown;
new_pup |= new_pdown;
new_cup |= new_cdown;
}
if (!down_stone) {
new_mdown |= new_mup;
new_pdown |= new_pup;
new_cdown |= new_cup;
}
new_mp |= (new_mup && new_pup);
new_mp |= (new_mdown && new_pdown);
new_cp |= (new_cup && new_pup);
new_cp |= (new_cdown && new_pdown);
int new_m = new_mup + new_mdown * 2;
int new_p = new_pup + new_pdown * 2;
int new_c = new_cup + new_cdown * 2;
//if (print) printf("%d: go %d %d %d %d %d\n",nn,new_m,new_p,new_c,new_mp,new_cp);
if (new_mup && new_cup) continue;
if (new_mdown && new_cdown) continue;
upd(f[i + 1][new_m][new_p][new_c][new_mp][new_cp], now + cost);
}
}
}
}
}
}
}
// i, monster, port, castle, monster--port, castle--port
//printf("? %d\n",f[3][0][1][1][0][1]);
//printf("? %d\n",f[4][2][0][0][0][1]);
int ans = INF;
for (int m=0;m<4;m++) {
for (int p=0;p<4;p++) {
for (int c=0;c<4;c++) {
for (int mp=0;mp<2;mp++) {
for (int cp=0;cp<2;cp++) {
if (mp && cp) continue;
upd(ans, f[n][m][p][c][mp][cp]);
}
}
}
}
}
if (ans == INF) ans = -1;
return ans;
}
};第三名答案
#ifdef yfzLOCAL
#include<bits/stdc++.h>
using namespace std;
#endif
namespace WXHAK{
struct edge{
int r,nxt,w;
}e[1010000];
int head[1001000],q[1001000],l,r,S,T,esz,cur[1010000],dep[1001000];
void adde(int u,int v,int w){
// printf("[%d,%d,%d]\n",u,v,w);
e[++esz].r=v;e[esz].nxt=head[u];head[u]=esz;e[esz].w=w;
e[++esz].r=u;e[esz].nxt=head[v];head[v]=esz;e[esz].w=0;
}
bool bfs(){
for(int i=S;i<=T;++i)dep[i]=0,cur[i]=head[i];
l=r=0,q[r++]=S,dep[S]=1;
while(l<r){
int u=q[l++];
for(int t=head[u];t;t=e[t].nxt)if(e[t].w&&!dep[e[t].r])
dep[e[t].r]=dep[u]+1,q[r++]=e[t].r;
}
return dep[T]!=0;
}
int find(int u,int flow){
if(u==T)return flow;
int used=0,a=0;
for(int& t=cur[u];t;t=e[t].nxt)if(e[t].w&&dep[e[t].r]==dep[u]+1){
a=find(e[t].r,min(flow-used,e[t].w)),e[t].w-=a,e[t^1].w+=a,used+=a;
if(used==flow)return used;
}
return used;
}
void clr(int nS,int nT){
for(int i=S;i<=T;++i)head[i]=0;
S=nS,T=nT,esz=1;
}
int dinic(){
int ans=0;
while(bfs())ans+=find(S,1<<30);
return ans;
}
}
class Solution {
public:
int in(int x,int y,int n){
return (x*n+y)*2+1;
}
int out(int x,int y,int n){
return (x*n+y)*2+2;
}
int guardCastle(vector<string>& grid) {
int n=grid[0].size();
WXHAK::clr(0,n*4+10);
int S=0,T=n*4+10;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int inf=1e9;
int Pin=n*4+9,Pout=n*4+8;
for(int i=0;i<2;++i){
for(int j=0;j<n;++j){
if(grid[i][j]=='.'&&grid[i][j]!='#'){
WXHAK::adde(in(i,j,n),out(i,j,n),1);
for(int k=0;k<4;++k){
int ni=i+dx[k],nj=j+dy[k];
if(ni>=0&&ni<2&&nj>=0&&nj<n&&grid[ni][nj]!='#'){
// printf("<%d,%d>--<%d,%d>\n",i,j,ni,nj);
WXHAK::adde(out(i,j,n),in(ni,nj,n),inf);
}
}
} else if(grid[i][j]=='S'){
WXHAK::adde(S,out(i,j,n),inf);
for(int k=0;k<4;++k){
int ni=i+dx[k],nj=j+dy[k];
if(ni>=0&&ni<2&&nj>=0&&nj<n&&grid[ni][nj]!='#'){
WXHAK::adde(out(i,j,n),in(ni,nj,n),inf);
}
}
} else if(grid[i][j]=='C'){
WXHAK::adde(in(i,j,n),T,inf);
} else if(grid[i][j]=='P'){
WXHAK::adde(in(i,j,n),Pin,inf);
for(int k=0;k<4;++k){
int ni=i+dx[k],nj=j+dy[k];
if(ni>=0&&ni<2&&nj>=0&&nj<n&&grid[ni][nj]!='#'){
WXHAK::adde(Pin,in(ni,nj,n),inf);
}
}
}
}
}
int ans=WXHAK::dinic();
if(ans>10*n)return -1;
else return ans;
}
};
#ifdef yfzLOCAL
int main(){
vector<string> A;
// string s;
// cin>>s;
// A.push_back(s);
// cin>>s;
// A.push_back(s);
int n=1e4;
srand(time(0));
for(int i=0;i<2;++i){
string s;
for(int j=0;j<n;++j){
int r=rand()%7;
if(r<5){
s+=rand()%10?".":"#";
} else if(r==5){
s+="S";
} else s+=".";
}
A.push_back(s);
}
A[rand()%2][rand()%n]='C';
Solution sol;
printf("%d",sol.guardCastle(A));
}
#endif
基恩士成长空间 443人发布
