Codeforces Round 865 (Div. 2)

news/2024/7/15 17:28:13 标签: 算法, c++, 图论

文章目录

  • 一、A - Ian Visits Mary
  • 二、B - Grid Reconstruction
  • 三、C - Ian and Array Sorting
  • 四、D - Sum Graph

一、A - Ian Visits Mary

  • 思路:
    思维题,仔细观察发现.要想他们中间没有数字,那我们就第一步先走到(1,b - 1),然后再从(1,b - 1)走到(a,b)

  • 代码:

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
const int N = 1e6 + 10,M = 1000007,INF = 1e18 + 1,mod = 1000000007;

void solve()
{
	int a,b; cin >> a >> b;
	
	if(__gcd(a,b) == 1)
	{
		cout << "1" << endl;
		cout << a << ' ' << b <<endl;
	}
	else
	{
		cout << "2" << endl;
		cout << 1 << ' ' << b - 1 << endl;
		cout << a << ' ' << b << endl;                                
	
	}
	
}

signed main()
{
  ios::sync_with_stdio(false);  cin.tie(0); cout.tie(0);
  int T; T = 1;cin >> T;
  while(T--) solve();
}

二、B - Grid Reconstruction

  • 思路:

    1: 你把图画出来会发现,加减是绝对的,也就是某个位置如果是 + ,不管从哪条路径到这个点来都是 + ,如果是 - ,不管哪条路径过来的都是 -

    2: 这时候就贪心来想,把[n + 1 ,2 * n]之内的数字赋值给 + ,[1,n]之内的数字赋值给 -

    3: 就是对于 + 就是第一行进行降序,也就是n * 2,n* 2 - 2,n * 2 - 4,对第二行进行升序,n + 1,n + 3,n + 5,这种,对于 – ,就上下两行交错的赋值,也就是第一列为1,第二列2,第三列为3,…

  • 代码:

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
const int N = 1e6 + 10,M = 1000007,INF = 1e18 + 1,mod = 1000000007;
int a[N][2];
void solve()
{
	int n; cin >> n;
	int p = n * 2;
	int q = n + 1;
	for(int i = 1;i <= n;i ++ )
	{
		if(i & 1)
		{
			a[i][1] = i;
			a[i][0] = p;
			p -= 2;
		}
		else
		{
			a[i][0] = i;
			a[i][1] = q;
			q += 2;
		}
	}

	

		for(int i = 1;i <= n;i ++ ) cout << a[i][0] << ' ';	cout << endl;
		for(int i = 1;i <= n;i ++ )	cout << a[i][1] << ' '; cout << endl;

	
	
}

signed main()
{
  ios::sync_with_stdio(false);  cin.tie(0); cout.tie(0);
  int T; T = 1;cin >> T;
  while(T--) solve();
}

三、C - Ian and Array Sorting

  • 思路:
    1: 先遍历一遍对于a[i - 1] > a[i]的这种,就改变a[i]和a[i + 1],也就是操作a[i + 1] += a[i - 1] - a[i] ,a[i] = a[i - 1];

    2: 遍历完一遍以后,这个数组要么就变成非递减的,要么除了最后一个其他都是非递减的,

    3: 我们再从后往前遍历对于a[i] > a[i + 1],就改变a[i]和a[i - 1],也就是再操作一遍,最后再遍历一下看看是否有非递减的数字,有就是 NO

  • 代码:

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
const int N = 1e6 + 10,M = 1000007,INF = 1e18 + 1,mod = 1000000007;
int a[N];
void solve()
{
	int n; cin >> n;
	for(int i = 1;i <= n;i ++ ) cin >> a[i];
	for(int i = 2;i <= n;i ++ )
	{
		if(a[i] < a[i - 1])
		{
			int t = a[i - 1] - a[i];
			if(i + 1 <= n)
			{
			a[i] = a[i - 1];
			a[i + 1] = t + a[i + 1];
			}
			
		}
	}
	if(a[n] >= a[n - 1] || (n - 1) % 2 == 0) 
	{
		cout << "YES" << endl;
		return;
	}
	
	for(int i = n - 1;i >= 1;i -- )
	{
		if(a[i] > a[i + 1] && i - 1 >= 1)
		{
			int t = a[i] - a[i + 1];
			a[i] = a[i + 1];
			a[i - 1] -= t; 
		}
	}
	for(int i = 2;i <= n;i ++ )
	{
		if(a[i] < a[i - 1])
		{
			cout << "NO" << endl;	
			return;
		}
	}
	
	cout << "YES" << endl;
	 
	
	
}

signed main()
{
  ios::sync_with_stdio(false);  cin.tie(0); cout.tie(0);
  int T; T = 1;cin >> T;
  while(T--) solve();
}

四、D - Sum Graph

  • 思路:
    这个也是看别人的代码,我们首先可以进行操作1两次,就是add(n),add(n + 1),这样你的连接的每个点最终会变成一条链,然后你再随便找一个点 ,进行n次查找操作,找出距离该点最长的那个点,那么这个点就一定是这条链的其中一个端点,然后再从该端点出发,进行n次查找就可以知道这个排列(因为题目说排列两个所以,2 *n次操作就可以了)
  • 代码:
#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
const int N = 1e6 + 10,M = 1000007,INF = 1e18 + 1,mod = 1000000007;
int a1[N],a2[N],b[N],c[N];
int p[N];

void add(int x)
{
	cout << "+ " << x << endl;	
	int k; cin >> k;
} 
int ask(int x,int y)
{
	cout << "? " << x << ' ' << y << endl;
	int k; cin >> k;
	return k;
}

void print(int n)
{
	cout << "! ";
	for(int i = 1;i <= 2 * n;i ++ ) cout << p[i] << ' ';
	cout << endl; 
	int w; cin >> w;
}

void solve()
{
	int n; cin >> n;
	add(n);
	add(n + 1);
	int k = 1,t = 0;
	int cnt = 0;
	for(int i = 1;i <= n / 2;i ++)
	{
		b[++cnt] = n - i + 1;
		b[++cnt] = i; // 把这条链放到数组中
	}
	
	if(n & 1) b[++cnt] = n / 2 + 1;// 如果是奇数,特判一下
	
	for(int i = 1;i <= n;i ++ )
	{
		c[b[i]] = b[n - i + 1]; // c数组这个没啥用,
		a1[i - 1] = b[i]; // 距离左端点距离为i - 1的点的值
		a2[i - 1] = b[n - i + 1]; //距离右端点距离为i - 1的点的值
	}
	
	int id = -1,mx = -1;
	for(int i = 2;i <= n;i ++ ) // 找出端点在id位置
	{
		int dis = ask(1,i);
		if(dis > mx)
		{
			mx = dis;
			id = i;
		}
	}
	p[id] = n; // 这个位置要么是n
	p[n + id] = c[n]; // n + i就是另一个端点
	for(int i = 1;i <= n;i ++ )
	{
		if(i == id) continue;
		int dis = ask(id,i); // id = 2
		int val = a1[dis];
		p[i] = val;
		p[i + n] = a2[dis];
	}
	
	print(n);
}

signed main()
{
  ios::sync_with_stdio(false);  cin.tie(0); cout.tie(0);
  int T; T = 1;cin >> T;
  while(T--) solve();
}

http://www.niftyadmin.cn/n/206398.html

相关文章

关于 GPT 的 10 个认知

关于 GPT 的 10 个认知

自从 GPT-4 发布以来&#xff0c;短短十来天&#xff0c;人类像来到了一个完全不同的世界。如果未来书写历史&#xff0c;AI 时代的奇点&#xff0c;应是 GPT-4 正式对外发布的这一天&#xff1a;2023 年 3 月 15 日。 关于 GPT 的新闻报道&#xff0c;堪称汗牛充栋&#xff0…
阅读更多...
为什么数字工厂管理系统是电子企业的必备品

为什么数字工厂管理系统是电子企业的必备品

与许多电子制造企业观望心态有所不同的是&#xff0c;电子产品分销商正在积极投身于实施数字工厂系统&#xff0c;部分分销商对已完成实施的系统赞不绝口。 数字工厂在元器件分销业的应用逐渐普遍 在一些大型分销商的影响下&#xff0c;数字工厂在分销行业的应用加快。相比而…
阅读更多...
《Java8实战》第5章 使用流

《Java8实战》第5章 使用流

上一章已经体验到流让你从外部迭代转向内部迭代。 5.1 筛选 看如何选择流中的元素&#xff1a;用谓词筛选&#xff0c;筛选出各不相同的元素。 5.1.1 用谓词筛选 filter 方法&#xff0c;该操作会接受一个谓词&#xff08;一个返回boolean 的函数&#xff09;作为参数&am…
阅读更多...
python pyc文件

python pyc文件

py 文件在执行的时候会先被编译成 PyCodeObject 对象&#xff0c;并且该对象还会被保存到 pyc 文件中 实际上&#xff0c;在运行过程中&#xff0c;如果碰到 import abc 这样的语句&#xff0c;那么 Python 会在设定好的 path 中寻找 abc.pyc 或者 abc.pyd 文件。如果没有这些文…
阅读更多...
足够惊艳，使用Alpaca-Lora基于LLaMA(7B)二十分钟完成微调，效果比肩斯坦福羊驼

足够惊艳，使用Alpaca-Lora基于LLaMA(7B)二十分钟完成微调，效果比肩斯坦福羊驼

之前尝试了从0到1复现斯坦福羊驼&#xff08;Stanford Alpaca 7B&#xff09;&#xff0c;Stanford Alpaca 是在 LLaMA 整个模型上微调&#xff0c;即对预训练模型中的所有参数都进行微调&#xff08;full fine-tuning&#xff09;。但该方法对于硬件成本要求仍然偏高且训练低效…
阅读更多...
使用Cheat Engine与DnSpy破解Unity游戏

使用Cheat Engine与DnSpy破解Unity游戏

题目连接&#xff1a; https://play.picoctf.org/practice/challenge/361?originalEvent72&page3我们是windows系统&#xff0c;所以点击windows game下载游戏 双击运行pico.exe 屏幕上方的一串英文是叫我们找flag&#xff0c;我在这个小地图里走来走去也没flag&#xff…
阅读更多...
HTML+CSS+JS 学习笔记（一）———HTML(上)

HTML+CSS+JS 学习笔记（一）———HTML(上)

&#x1f331;博客主页&#xff1a;大寄一场. &#x1f331;系列专栏&#xff1a;前端 &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注 目录 代码开发工具 概念 HTML模板 body元素的常用属性 HTML 控制标记&#xff08;标签&#xff09;的类型 HTML语法…
阅读更多...
0406作业

0406作业

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);//获取界面尺寸QSize s this->size();qDebug()<<"w:"<<s.width()<<" h:…
阅读更多...
最新文章

Copyright @ 2022~2023