博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
Atcoder Grand Contest 004 题解
阅读量：5105 次
发布时间：2019-06-13

本文共 13472 字，大约阅读时间需要 44 分钟。

A - Divide a Cuboid

如果一边是偶数，肯定一刀切一半最优，否则看一下切出来的差就是另外两边的乘积。

//waz#include 
     
       using namespace std; #define mp make_pair#define pb push_back#define fi first#define se second#define ALL(x) (x).begin(), (x).end()#define SZ(x) ((int)((x).size())) typedef pair
      
        PII;typedef vector
       
         VI;typedef long long int64;typedef unsigned int uint;typedef unsigned long long uint64; #define gi(x) ((x) = F())#define gii(x, y) (gi(x), gi(y))#define giii(x, y, z) (gii(x, y), gi(z)) int F(){	char ch;	int x, a;	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');	if (ch == '-') ch = getchar(), a = -1;	else a = 1;	x = ch - '0';	while (ch = getchar(), ch >= '0' && ch <= '9')		x = (x << 1) + (x << 3) + ch - '0';	return a * x;} int A, B, C;  int main(){	giii(A, B, C);	if (A % 2 == 0 || B % 2 == 0 || C % 2 == 0) puts("0");	else printf("%lld\n", min(1LL * A * B, min(1LL * B * C, 1LL * A * C)));	return 0;}

　　

B - Colorful Slimes

枚举转了y次，那么一个点被造出来的花费就是min(a[i-y]...a[i])，最后加上x*y对所有情况取min就好了。

//waz#include 
     
       using namespace std; #define mp make_pair#define pb push_back#define fi first#define se second#define ALL(x) (x).begin(), (x).end()#define SZ(x) ((int)((x).size())) typedef pair
      
        PII;typedef vector
       
         VI;typedef long long int64;typedef unsigned int uint;typedef unsigned long long uint64; #define gi(x) ((x) = F())#define gii(x, y) (gi(x), gi(y))#define giii(x, y, z) (gii(x, y), gi(z)) int F(){	char ch;	int x, a;	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');	if (ch == '-') ch = getchar(), a = -1;	else a = 1;	x = ch - '0';	while (ch = getchar(), ch >= '0' && ch <= '9')		x = (x << 1) + (x << 3) + ch - '0';	return a * x;} int n, a[2010], x, mn[2010][2010]; long long ans; int main(){	gii(n, x);	for (int i = 1; i <= n; ++i) gi(a[i]), ans += a[i];	for (int i = 1; i <= n; ++i)	{		mn[i][i] = a[i];		for (int j = i + 1; j <= n; ++j)			mn[i][j] = min(mn[i][j - 1], a[j]);	}	for (int i = 0; i <= n; ++i)	{		long long ret = 1LL * x * i;		for (int j = 1; j <= n; ++j)		{			int k = j - i;			if (k < 1) k += n, ret += min(mn[k][n], mn[1][j]);			else ret += mn[k][j];		}		ans = min(ans, ret);	}	printf("%lld\n", ans);	return 0;}

　　

C - AND Grid

两边摆成类似正反E字交错放，重复地方两个都放就好了。

//waz#include 
     
       using namespace std; #define mp make_pair#define pb push_back#define fi first#define se second#define ALL(x) (x).begin(), (x).end()#define SZ(x) ((int)((x).size())) typedef pair
      
        PII;typedef vector
       
         VI;typedef long long int64;typedef unsigned int uint;typedef unsigned long long uint64; #define gi(x) ((x) = F())#define gii(x, y) (gi(x), gi(y))#define giii(x, y, z) (gii(x, y), gi(z)) int F(){	char ch;	int x, a;	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');	if (ch == '-') ch = getchar(), a = -1;	else a = 1;	x = ch - '0';	while (ch = getchar(), ch >= '0' && ch <= '9')		x = (x << 1) + (x << 3) + ch - '0';	return a * x;} int n, m; char str[510][510]; int main(){	gii(n, m);	for (int i = 1; i <= n; ++i) scanf("%s", str[i] + 1);	for (int i = 1; i <= n; ++i)	{		for (int j = 1; j <= m; ++j)		{			if (((j == 1 || (i & 1)) && j != m) || str[i][j] == '#')				putchar('#');			else				putchar('.');		}		putchar('\n');	}	for (int i = 1; i <= n; ++i)	{		for (int j = 1; j <= m; ++j)		{			if (((j == m || !(i & 1)) && j != 1) || str[i][j] == '#')				putchar('#');			else				putchar('.');		}		putchar('\n');	}}

　　

D - Teleporter

首先，1号必须连自己，因为如果1有在一个环上，环上每个点走k次结果都不一样，其它也只能改为1号最优。

那么，省下就是一棵树了，bfs一遍即可。

//waz#include 
     
       using namespace std; #define mp make_pair#define pb push_back#define fi first#define se second#define ALL(x) (x).begin(), (x).end()#define SZ(x) ((int)((x).size())) typedef pair
      
        PII;typedef vector
       
         VI;typedef long long int64;typedef unsigned int uint;typedef unsigned long long uint64; #define gi(x) ((x) = F())#define gii(x, y) (gi(x), gi(y))#define giii(x, y, z) (gii(x, y), gi(z)) int F(){	char ch;	int x, a;	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');	if (ch == '-') ch = getchar(), a = -1;	else a = 1;	x = ch - '0';	while (ch = getchar(), ch >= '0' && ch <= '9')		x = (x << 1) + (x << 3) + ch - '0';	return a * x;} const int N = 1e5 + 10; int n, k, a[N];  int ans = 0; int deg[N], dep[N]; int main(){	gii(n, k); --k;	for (int i = 1; i <= n; ++i) gi(a[i]);	if (a[1] != 1) ++ans, a[1] = 1;	for (int i = 1; i <= n; ++i)		++deg[a[i]];	static int q[N]; int l = 0, r = 0;	for (int i = 1; i <= n; ++i)	{		if (!deg[i]) q[r++] = i;	}	while (l < r)	{		int u = q[l++];		--deg[a[u]];		if (!deg[a[u]]) q[r++] = a[u];		if (dep[u] == k && a[u] != 1) a[u] = 1, ++ans;		else dep[a[u]] = max(dep[a[u]], dep[u] + 1);	}	printf("%d\n", ans);	return 0;}

　　

E - Salvage Robots

能走的区域是一个矩形，但是能取到的就长得奇形怪状了，所以我们就写一个四位dp，算算边界就好了。

//waz#include 
     
       using namespace std; #define mp make_pair#define pb push_back#define fi first#define se second#define ALL(x) (x).begin(), (x).end()#define SZ(x) ((int)((x).size())) typedef pair
      
        PII;typedef vector
       
         VI;typedef long long int64;typedef unsigned int uint;typedef unsigned long long uint64; #define gi(x) ((x) = F())#define gii(x, y) (gi(x), gi(y))#define giii(x, y, z) (gii(x, y), gi(z)) int F(){	char ch;	int x, a;	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');	if (ch == '-') ch = getchar(), a = -1;	else a = 1;	x = ch - '0';	while (ch = getchar(), ch >= '0' && ch <= '9')		x = (x << 1) + (x << 3) + ch - '0';	return a * x;} int H, W; char str[110][110]; int cnt[110][110]; int sum(int x1, int y1, int x2, int y2){	x1 = max(x1, 1), x1 = min(x1, H);	x2 = max(x2, 1), x2 = min(x2, H);	y1 = max(y1, 1), y1 = min(y1, W);	y2 = max(y2, 1), y2 = min(y2, W);	if (x1 > x2) return 0;	if (y1 > y2) return 0;	//cerr << x1 << ", " << y1 << " and " << x2 << ", " << y2 << endl;	return cnt[x2][y2] + cnt[x1 - 1][y1 - 1] - cnt[x1 - 1][y2] - cnt[x2][y1 - 1];} int f[2][110][110][110]; int main(){	gii(H, W);	for (int i = 1; i <= H; ++i)		scanf("%s", str[i] + 1);	int x = 0, y = 0;	for (int i = 1; i <= H; ++i)		for (int j = 1; j <= W; ++j)			if (cnt[i][j] = (str[i][j] == 'o'), str[i][j] == 'E')				x = i, y = j;	for (int i = 1; i <= H; ++i)		for (int j = 1; j <= W; ++j)			cnt[i][j] += cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1];	int ans = 0;	for (int l = 0; x + l <= H; ++l)		for (int r = 0; x - r > 0; ++r)			for (int u = 0; y + u <= W; ++u)				for (int d = 0; y - d > 0; ++d)				{					int L = l & 1;					f[L][r][u][d] = 0;					int left = x - r, right = x + l;					int up = y - d, down = y + u;					left = max(1 + l, left);					right = min(H - r, right);					up = max(up, 1 + u);					down = min(down, W - d);					if (l && l + r + x <= H) f[L][r][u][d] = max(f[L][r][u][d], f[L ^ 1][r][u][d] + sum(x + l, up, x + l, down));					if (r && l + r <= x - 1) f[L][r][u][d] = max(f[L][r][u][d], f[L][r - 1][u][d] + sum(x - r, up, x - r, down));					if (u && u + d + y <= W) f[L][r][u][d] = max(f[L][r][u][d], f[L][r][u - 1][d] + sum(left, y + u, right, y + u));					if (d && u + d <= y - 1) f[L][r][u][d] = max(f[L][r][u][d], f[L][r][u][d - 1] + sum(left, y - d, right, y - d));					//cerr << l << ", " << r << ", " << u << ", " << d << " : " << f[l][r][u][d] << endl; 					ans = max(ans, f[L][r][u][d]);				}	printf("%d\n", ans);	return 0;}

　　

F - Namori

我们首先可以发现一个性质，黑色只能成对出现而且，这两个点距离为奇数，次数是距离。

那么树就很好写了，只要一个启发式合并，求深度的奇偶性。

环套树我们把它缩成环，然后每个附上权值d[i]，偶环就是一个负载平衡问题，奇环我们可以断开一条边，因为那条边的作用是改变奇偶用的，所以我们扫一遍就能知道会改变多少次。

//waz#include 
     
       using namespace std; #define mp make_pair#define pb push_back#define fi first#define se second#define ALL(x) (x).begin(), (x).end()#define SZ(x) ((int)((x).size())) typedef pair
      
        PII;typedef vector
       
         VI;typedef long long int64;typedef unsigned int uint;typedef unsigned long long uint64; #define gi(x) ((x) = F())#define gii(x, y) (gi(x), gi(y))#define giii(x, y, z) (gii(x, y), gi(z)) int F(){	char ch;	int x, a;	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');	if (ch == '-') ch = getchar(), a = -1;	else a = 1;	x = ch - '0';	while (ch = getchar(), ch >= '0' && ch <= '9')		x = (x << 1) + (x << 3) + ch - '0';	return a * x;} const int N = 1e5 + 10; VI edge[N]; int n, m; namespace task1{	set
        
          e[N][2];		int fa[N], dep[N], check_cnt;		void dfs1(int u)	{		dep[u] = dep[fa[u]] + 1;		e[u][dep[u] & 1].insert(u);		if (dep[u] & 1) ++check_cnt;		else --check_cnt;		for (auto v : edge[u])		{			if (v == fa[u]) continue;			fa[v] = u;			dfs1(v);		}	}		long long ans;		void dfs2(int u)	{		for (auto v : edge[u])		{			if (v == fa[u]) continue;			dfs2(v);			if (e[u][1].size() < e[v][1].size())				e[u][1].swap(e[v][1]);			for (auto x : e[v][1])				e[u][1].insert(x);			if (e[u][0].size() < e[v][0].size())				e[u][0].swap(e[v][0]);			for (auto x : e[v][0])				e[u][0].insert(x);		}		if (e[u][1].size() && e[u][0].size())		{			int s = min(e[u][1].size(), e[u][0].size());			set
         
          ::iterator it1 = e[u][1].begin(), it2 = e[u][0].begin();			static PII stk[N]; int tp = 0;			for (int i = 1; i <= s; ++i)			{				int v1 = *it1;				int v2 = *it2;				stk[++tp] = mp(v1, v2);				ans += dep[v1] + dep[v2] - (dep[u] << 1);				//cerr << v1 << ", " << v2 << ", " << u << endl;				++it1, ++it2;			}			for (int i = 1; i <= tp; ++i)				e[u][1].erase(stk[i].fi), e[u][0].erase(stk[i].se);		}	}		void solve()	{		dfs1(1);		if (check_cnt)		{			puts("-1");			return;		}		dfs2(1);		printf("%lld\n", ans);	}} namespace task2{	bool vis[N], cir[N];	int use_fa[N];	vector
          
            circle; bool exit_flag; void dfs1(int u) { vis[u] = 1; for (auto v : edge[u]) { if (exit_flag) return; if (use_fa[u] == v) continue; if (vis[v]) { while (u != v) circle.pb(u), cir[u] = 1, u = use_fa[u]; circle.pb(v), cir[v] = 1; exit_flag = 1; return; } use_fa[v] = u; dfs1(v); } } int dep[N], fa[N]; set
           
             e[N][2]; void dfs2(int u) { dep[u] = dep[fa[u]] + 1; e[u][dep[u] & 1].insert(u); for (auto v : edge[u]) { if (v == fa[u]) continue; if (cir[v]) continue; fa[v] = u; dfs2(v); } } long long ans; void dfs3(int u) { for (auto v : edge[u]) { if (v == fa[u]) continue; if (cir[v]) continue; dfs3(v); if (e[u][1].size() < e[v][1].size()) e[u][1].swap(e[v][1]); for (auto x : e[v][1]) e[u][1].insert(x); if (e[u][0].size() < e[v][0].size()) e[u][0].swap(e[v][0]); for (auto x : e[v][0]) e[u][0].insert(x); } if (e[u][1].size() && e[u][0].size()) { int s = min(e[u][1].size(), e[u][0].size()); set
            
             ::iterator it1 = e[u][1].begin(), it2 = e[u][0].begin(); static PII stk[N]; int tp = 0; for (int i = 1; i <= s; ++i) { int v1 = *it1; int v2 = *it2; stk[++tp] = mp(v1, v2); ans += dep[v1] + dep[v2] - (dep[u] << 1); //cerr << v1 << ", " << v2 << ", " << u << endl; ++it1, ++it2; } for (int i = 1; i <= tp; ++i) e[u][1].erase(stk[i].fi), e[u][0].erase(stk[i].se); } } int d[N]; void solve() { dfs1(1); for (auto root : circle) { //cerr << root << endl; dfs2(root), dfs3(root); if (e[root][1].size()) { for (auto v : e[root][1]) ++d[root], ans += dep[v] - 1; } else if (e[root][0].size()) { for (auto v : e[root][0]) --d[root], ans += dep[v] - 1; } } int vtx = SZ(circle); //cerr << "ok!" << endl; if (vtx % 2 == 0) { int sum = 0; for (int i = 0; i < vtx; ++i) { if (i & 1) d[circle[i]] = -d[circle[i]]; sum += d[circle[i]]; } if (sum) { puts("-1"); return; } static vector
             
               t; t.pb(-d[circle[0]]); for (int i = 1; i < vtx; ++i) { d[circle[i]] += d[circle[i - 1]]; t.pb(-d[circle[i]]); } sort(t.begin(), t.end()); int v = t[SZ(t) >> 1]; for (auto x : t) ans += abs(x - v); printf("%lld\n", ans); } else { int sum = 0; for (int i = 0; i < vtx; ++i) { if (i & 1) d[circle[i]] = -d[circle[i]]; sum += d[circle[i]]; } if (sum % 2 != 0) { puts("-1"); return; } ans += abs(sum / 2); d[circle[0]] -= sum / 2; d[circle[vtx - 1]] += sum / 2; for (int i = 0; i < vtx - 1; ++i) { ans += abs(d[circle[i]]); d[circle[i + 1]] += d[circle[i]]; } printf("%lld\n", ans); } }} int main(){ gii(n, m); for (int i = 1; i <= m; ++i) { int u, v; gii(u, v); edge[u].push_back(v); edge[v].push_back(u); } if (m == n - 1) { task1::solve(); return 0; } task2::solve(); return 0;}

　　

 

  1. //waz
  2. #include<bits/stdc++.h>
  3.  
  4. usingnamespace std;
  5.  
  6. #define mp make_pair
  7. #define pb push_back
  8. #definefi first
  9. #define se second
  10. #define ALL(x)(x).begin(),(x).end()
  11. #define SZ(x)((int)((x).size()))
  12.  
  13. typedef pair<int,int> PII;
  14. typedef vector<int> VI;
  15. typedeflonglong int64;
  16. typedefunsignedintuint;
  17. typedefunsignedlonglong uint64;
  18.  
  19. #define gi(x)((x)= F())
  20. #define gii(x, y)(gi(x), gi(y))
  21. #define giii(x, y, z)(gii(x, y), gi(z))
  22.  
  23. int F()
  24. {
  25. char ch;
  26. int x, a;
  27. while(ch = getchar(),(ch <'0'|| ch >'9')&& ch !='-');
  28. if(ch =='-') ch = getchar(), a =-1;
  29. else a =1;
  30. x = ch -'0';
  31. while(ch = getchar(), ch >='0'&& ch <='9')
  32. x =(x <<1)+(x <<3)+ ch -'0';
  33. return a * x;
  34. }
  35.  
  36. constint N =1e5+10;
  37.  
  38. int n, k, a[N];
  39.  
  40. int ans =0;
  41.  
  42. int deg[N], dep[N];
  43.  
  44. int main()
  45. {
  46. gii(n, k);--k;
  47. for(int i =1; i <= n;++i) gi(a[i]);
  48. if(a[1]!=1)++ans, a[1]=1;
  49. for(int i =1; i <= n;++i)
  50. ++deg[a[i]];
  51. staticint q[N];int l =0, r =0;
  52. for(int i =1; i <= n;++i)
  53. {
  54. if(!deg[i]) q[r++]= i;
  55. }
  56. while(l < r)
  57. {
  58. int u = q[l++];
  59. --deg[a[u]];
  60. if(!deg[a[u]]) q[r++]= a[u];
  61. if(dep[u]== k && a[u]!=1) a[u]=1,++ans;
  62. else dep[a[u]]= max(dep[a[u]], dep[u]+1);
  63. }
  64. printf("%d\n", ans);
  65. return0;
  66. }

转载于:https://www.cnblogs.com/AnzheWang/p/9615564.html

你可能感兴趣的文章
html嵌入zabbix网页,通过Zabbix通过Python发送HTML和纯文本电子邮件
查看>>
路由 asp.net mvc html,asp.net-mvc – 为什么需要为Html.Action定义的路由？
查看>>
goquery 查找html标签,goquery库的使用
查看>>
bzoj 3473 后缀自动机多字符串的子串处理方法
查看>>
现金销售与欠款销售
查看>>
MongoDb系列
查看>>
【C语言】控制台窗口图形界面编程（七）：鼠标事件
查看>>
BZOJ3732 Network
查看>>
DJango中ORM操作
查看>>
Oracle查询优化--单表查询
查看>>
面试常被问到的小程序问题
查看>>
人类的数学抽象思维
查看>>
时序图
查看>>
beyond compare 4.2.9桌面右键集成的问题修复
查看>>
冒泡排序
查看>>
jdk8_默认方法
查看>>
PS 2018安装教程
查看>>
transition 用法
查看>>
淘宝镜像cnpm提示“不是内部命令”解决方法
查看>>
Host '****' is not allowed to connect to this MySQL server(数据库不能远程连接)
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-11-17 17:26:06   当前IP: 18.222.182.29   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我