2020-2021 ACM-ICPC, Asia Nanjing Regional Contest KLMEFA

magicat / 2023-08-25 / 原文

2020-2021 ACM-ICPC, Asia Nanjing Regional Contest (XXI Open Cup, Grand Prix of Nanjing)

image

给队友贡献了 5 发罚时

目录
  • 2020-2021 ACM-ICPC, Asia Nanjing Regional Contest (XXI Open Cup, Grand Prix of Nanjing)
    • K - K Co-prime Permutation
    • L - Let's Play Curling
    • M - Monster Hunter
    • E - Evil Coordinate
    • F - Fireworks
    • A - Ah, It's Yesterday Once More

K - K Co-prime Permutation

将数字shift k 个即可，注意特判

#include<bits/stdc++.h>

using namespace std;


int n, k;
int res[1000010];
void solve()
{
	cin>>n>>k;
	if(k == 0)
	{
		cout<<-1;
		return;
	}
	res[1] = k;
	for(int i = 2; i <= k; i++)
		res[i] = i - 1;
	for(int i = k + 1; i <= n; i++)
		res[i] = i;
	for(int i = 1; i <= n; i++)
	{
		cout<<res[i];
		if(i != n)
			cout<<" ";
	}
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

	solve();

}

L - Let's Play Curling

问蓝球中间的红球最多能有多少个

双指针弄一下

演了队友3发罚时，晕

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 10;

int n, m;
int a[N], b[N], d[N];
bool vis[N];
vector<int> vx;
void solve()
{
	cin>>n>>m;
	
	vx.clear();
	for(int i = 0; i <= n + m; i++)
		a[i] = b[i] = d[i] = 0, vis[i] = false;

	for(int i = 1; i <= n; i++)
	{
		cin>>a[i];
		vx.push_back(a[i]);
	}
	for(int i = 1; i <= m; i++)
	{
		cin>>b[i];
		vx.push_back(b[i]);
	}
	// sort(a + 1, a + 1 + n);
	sort(vx.begin(), vx.end());
	vx.erase(unique(vx.begin(), vx.end()), vx.end());
	for(int i = 1; i <= n; i++)
	{
		int p = lower_bound(vx.begin(), vx.end(), a[i]) 
		- vx.begin();
		d[p]++;
	}
	for(int i = 1; i <= m; i++)
	{
		int p = lower_bound(vx.begin(), vx.end(), b[i]) 
		- vx.begin();
		vis[p] = true;
	}	
	int k = vx.size();
	int res = 0;
	for(int i = 0; i < k; i++)
	{
		int ans = 0;
		if(vis[i] == false && d[i] >= 1)
		{
			int j = i;
			ans = d[j];
			while(j + 1 < k && vis[j + 1] == false && d[j + 1] >= 1)
			{
				j++;
				ans = ans + d[j];
			}
			res = max(ans, res);
			i = j;
		}
	}
	if(res != 0)
	{
		cout<<res<<'\n';
	}
	else
		cout<<"Impossible\n";
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int tc;	cin>>tc;
	for(int i = 1; i <= tc; i++)
		solve();

}

M - Monster Hunter

树上背包典题

定义状态\(f_{u,i,0/1}\) 定义状态为以 \(u\) 为根的子树，已经删掉了 \(i\) 个结点,\(0/1\) 分别代表没删自己和删了自己

因为可以子节点也可以被删掉，转移的时候要减去子节点的权值，具体看代码吧

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e3 + 10;
const ll inf = 1ll << 60;
int n;
ll f[N][N][2], sz[N], w[N], h[N], tmp[N][2];
vector<int> e[N];

void dfs(int u)
{
	h[u] = w[u];
	sz[u] = 0;
	for(auto v : e[u])
	{
		dfs(v);
		h[u] += w[v];
	}


	for(int i = 0; i <= N - 10; i++)
		f[u][i][0] = f[u][i][1] = inf;
	f[u][1][0] = h[u];
	f[u][0][1] = 0;
	sz[u] = 1;
	for(auto v : e[u])
	{
		for(int i = 0; i <= sz[u] + sz[v]; i++)
			tmp[i][0] = inf, tmp[i][1] = inf;
		for(int i = 0; i <= sz[u]; i++)
			for(int j = 0; j <= sz[v]; j++)
			{
				tmp[i + j][0] = min(tmp[i + j][0], f[u][i][0] + f[v][j][1] - w[v]);
				tmp[i + j][0] = min(tmp[i + j][0], f[u][i][0] + f[v][j][0]);

				tmp[i + j][1] = min(tmp[i + j][1], f[u][i][1] + f[v][j][1]);
				tmp[i + j][1] = min(tmp[i + j][1], f[u][i][1] + f[v][j][0]);

			}
		sz[u] += sz[v];
		for(int i = sz[u]; i >= 0; i--)
			f[u][i][0] = tmp[i][0], f[u][i][1] = tmp[i][1];
	}
}

void solve()
{
	cin>>n;
	for(int i = 1; i <= n; i++)
	{
		e[i].clear();
		w[i] = h[i] = 0;
	}

	for(int i = 2; i <= n; i++)
	{
		int p;	cin>>p;
		e[p].push_back(i); 
	}
	for(int i = 1; i <= n; i++)
		cin>>w[i];
	dfs(1);
	// for(int i = 1; i <= n; i++)
	// {
	// 	cout<<"i: "<<i<<"   " ;
	// 	for(int j = 0; j <= n; j++)
	// 	{
	// 		cout<<f[i][j]<<" ";
	// 	}
	// 	cout<<'\n';
	// }
	for(int i = n; i >= 0; i--)
	{
		cout<<min(f[1][i][0], f[1][i][1]);
		if(i != 0)
			cout<<" ";
	}
	cout<<'\n';

}

int main()
{
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int tc;	cin>>tc;
	for(int i = 1; i <= tc; i++)
		solve();
}

E - Evil Coordinate

check 一下16种RLUD的排列是否有一种符合即可

我懒得预处理出全排列，写了一个更暴力求排列的了

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 10;

ll mx,my;
string s;
void solve()
{

	cin>>mx>>my;
	cin>>s;
	
	int cnt[5];	memset(cnt, 0, sizeof cnt);
	for(auto it : s)
	{
		if(it=='R')		cnt[1]++;
		if(it=='L')		cnt[2]--;
		if(it=='U')		cnt[3]++;
		if(it=='D')		cnt[4]--;
	}
	// for(int i = 1; i <= 4; i++)
	// 	cout<<cnt[i]<<"  ";
	// cout<<'\n';
	for(int i = 1; i <= 4; i++)
	{
		for(int j = 1; j <= 4; j++)
		{
			for(int k = 1; k <= 4; k++)
			{
				for(int l = 1; l <= 4; l++)
				{
					if(i != j && i != k && i != l
						&& j != k && j != l
						&& k != l)
					{
						int x = 0, y = 0;
						int tx = 0, ty = 0;

						bool ok = true;

						if(i == 1 || i == 2)
						{
							x = x + cnt[i];
							if(y == my && ((tx <= mx && mx <= x) || (tx >= mx && mx >= x)))
								ok = false;
							tx = x;
						}
						else 
						{
							y = y + cnt[i];
							if(x == mx && ((ty <= my && my <= y) || (ty >= my && my >= y)))
								ok = false;
							ty = y;
						}

						if(j == 1 || j == 2)
						{
							x = x + cnt[j];
							if(y == my && ((tx <= mx && mx <= x) || (tx >= mx && mx >= x)))
								ok = false;
							tx = x;
						}
						else
						{
							y = y + cnt[j];
							if(x == mx && ((ty <= my && my <= y) || (ty >= my && my >= y)))
								ok = false;
							ty = y;							
						}
						
						if(k == 1 || k == 2)
						{
							x = x + cnt[k];
							if(y == my && ((tx <= mx && mx <= x) || (tx >= mx && mx >= x)))
								ok = false;
							tx = x;
						}
						else
						{
							y = y + cnt[k];
							if(x == mx && ((ty <= my && my <= y) || (ty >= my && my >= y)))
								ok = false;
							ty = y;							
						}

						if(l == 1 || l == 2)
						{
							x = x + cnt[l];
							if(y == my && ((tx <= mx && mx <= x) || (tx >= mx && mx >= x)))
								ok = false;
							tx = x;
						}
						else
						{
							y = y + cnt[l];
							if(x == mx && ((ty <= my && my <= y) || (ty >= my && my >= y)))
								ok = false;
							ty = y;							
						}

						if(ok)
						{
							// cout<<i<<"  "<<j<<"  "<<k<<"  "<<l<<'\n';
							// cout<<cnt[i]<<"  "<<cnt[j]<<"  "<<cnt[k]<<"  "<<cnt[l]<<'\n';
							cnt[2] = abs(cnt[2]);
							cnt[4] = abs(cnt[4]);
							while(cnt[i] >= 1)
							{
								cnt[i]--;
								if(i == 1)	cout<<'R';
								else if(i == 2) cout<<'L';
								else if(i == 3)	cout<<"U";
								else if(i == 4)	cout<<"D";
							}
							while(cnt[j] >= 1)
							{
								cnt[j]--;
								if(j == 1)	cout<<'R';
								else if(j == 2) cout<<'L';
								else if(j == 3)	cout<<"U";
								else if(j == 4)	cout<<"D";
							}
							while(cnt[k] >= 1)
							{
								cnt[k]--;
								if(k == 1)	cout<<'R';
								else if(k == 2) cout<<'L';
								else if(k == 3)	cout<<"U";
								else if(k == 4)	cout<<"D";
							}							
							while(cnt[l] >= 1)
							{
								cnt[l]--;
								if(l == 1)	cout<<'R';
								else if(l == 2) cout<<'L';
								else if(l == 3)	cout<<"U";
								else if(l == 4)	cout<<"D";
							}
							cout<<'\n';
							return;
						}

					}
				}
			}
		}
	}
	cout<<"Impossible\n";
	// if(my == 0 && (0 <= mx && mx <= x) || )

}

int main()
{
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int tc;	cin>>tc;
	for(int i = 1; i <= tc; i++)
		solve();
}

F - Fireworks

发现是一个可以三分函数

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 10;


int n, m, v;
double p, q;
double qmi(double a, int b)
{
	double res = 1.0;
	while(b)
	{
		if(b & 1)	res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}

double calc(int x)
{
	return (1.0 * n * x + m) / (1.0 - qmi(q, x)); 
}

void solve()
{
	cin>>n>>m>>v;
	p = 1.0 * v / 10000;
	q = 1.0 - p;
	int l = 1, r = 1e9;
	while(r - l > 2)
	{
		int lmid = l + (r - l) / 3;
		int rmid = r - (r - l) / 3;
		if(calc(lmid) <= calc(rmid))
			r = rmid;
		else l = lmid;
	} 
	double res = 1e18;
	for(int i = l; i <= r; i++)
		res = min(res, calc(i));
	//double res = min(calc(l), calc(r));
	printf("%.7lf\n", res);
}

int main()
{
	
	// ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	
	int tc;	cin>>tc;
	for(int i = 1; i <= tc; i++)
		solve();
}

A - Ah, It's Yesterday Once More

尽可能地构造出分叉可以多走的迷宫，使得指令无效，而不是构造步数尽可能多的迷宫

//  AC one more times

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//const int mod = 1e9 + 7;
const int N = 2e5 + 10;


//  AC one more times

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int a[30][30] = {{0 ,1  ,2, 3,  4,  5,  6,  7,  8,  9,  10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
    {1, 0,  1,  1,  1,  0,  0,  0,  1,  1,  1,  0,  0,  0,  1,  1,  1,  0,  1,  1,  1},
    {2, 0,  1,  0,  1,  1,  0,  0,  1,  0,  1,  1,  0,  0,  1,  0,  1,  1,  0,  0,  1},
    {3, 0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1},
    {4, 0,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  1},
    {5, 0,  0,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  0,  0},
    {6, 1,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  0},
    {7, 1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0},
    {8, 1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1},
    {9, 0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1},
{10,    0,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  1},
{11,    0,  0,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  0,  0},
{12,    1,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  0},
{13,    1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0},
{14,    1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1},
{15,    0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1},
{16,    0,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  1},
{17,    0,  0,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  0,  0},
{18,    1,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  1,  1,  0,  0},
{19,    1,  0,  1,  1,  0,  1,  0,  0,  1,  1,  0,  1,  0,  0,  1,  1,  0,  1,  0,  0},
{20,    1,  1,  0,  1,  1,  1,  0,  0,  0,  1,  1,  1,  0,  0,  0,  1,  1,  1,  0,  0}};



void solve()
{       
    cout<<"20 20\n";
    for(int i = 1; i <= 20; i++)
    {
        for(int j = 1; j <=20; j++)
            cout<<a[i][j];
        cout<<'\n';
    }

    return;
}


  
int main()
{
    std::ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    
    int TC = 1;
    
    //cin >> TC;    
    for(int tc = 1; tc <= TC; tc++)
    {
        //cout << "Case #" << tc << ": ";         
        solve();
    }


    return 0;
}

2020-2021 ACM-ICPC, Asia Nanjing Regional Contest KLMEFA更多相关文章

原型模式的C++实现

跨境从国内远程连接国外设备？从国外远程连接国内设备？巧用ToDesk即搞定

如何实现跨境设备操作？ToDesk远程控制加持全球节点轻松搞定

虚拟机扩容ubuntu22.04磁盘空间到逻辑卷中。

L. A Game On Tree

11月1日 2023CSP-S 复赛模测（“日记和×××”系列） - 模拟赛记录

【算法学习】扫描线

05C++数据类型

2024ICPC成都比赛部分题解

Educational Codeforces Round 20 E. Roma and Poker

11.1随笔

asio

C++之OpenCV入门到提高003：矩阵的掩膜（Mask）处理

Docker命令备忘录----Linux运维

项目添加埋点

使用axios下载二进制流文件

HTB-Cicada 靶机笔记

【再探图论】深入理解图论经典算法

C++范型二：右值引用

2023CCPC秦皇岛比赛部分题解

随机推荐

20241101 数据结构与算法期中机试收获

Java，启动！

什么是IT技术

即将到来！

2024/11/1日 日志 关于JavaScript简介&引入方式 以及基础语法的学习

舍得-时间-工作是人的一生最重要的事情-自己要有私房钱-人的一生最重要的事情是书写自己的人生

2.TiUP 部署 DM 集群

原型模式的C++实现

python bytecode解析

09-XSS键盘监听、cookie窃取&文件上传绕过

ubuntu 24.04 部署 mysql 8.4.3 LTS

国标GB28181公网平台LiteGBS国标GB28181视频平台建筑工地无线视频联网监控系统方案

imes完工下线

android 13 更改手机信号调整

BFS(Breath First Search 广度优先搜索)

Visual Studio Code（VSCode）中设置中文界面

影响黄金价格大幅波动的因素主要有哪些？

winform用Dev的TreeList滚动到指定节点的位置

Angular 18 上手开发

SSHD服务

热门话题

Ethernaut Level 11: Elevator Attack and Blockchain Interaction

快速部署开源spug运维平台的Docker安装指南

驱动调试之printk的原理与使用

计算机思维模型及其应用

华为云发布代码大模型PanGu-Coder2，实现高效代码生成

Linux多硬盘数据存储和分区操作

构建高可用架构: 分层冗余与自动故障转移

LoRA：高效调参的大语言模型适应方法

《分布式系统的基本原理及互联网分层架构的本质》

Hadoop写流程解析

Java架构师的系统架构设计方法论中的规范要点

使用observeDOM解决BetterScroll插件在移动端无法滑动的问题

互联网一致性架构设计实践

高并发系统架构与水平扩展

混合应用的崛起：跨平台开发取代原生应用

  穗舟网 （www.seizhou.com）

本站除标明"本站原创"外所有文章版权归创作人所有，本站不承担任何法律责任和连带责任，如有冒犯请直接联系，我们将立即予以纠正并致歉。

Powered by WordPress  ·  v1.0.0-alpha