目录

cf1713 A. Traveling Salesman Problem

cf1713 B. Optimal Reduction

cf1713 C. Build Permutation

cf1716 A. 2-3 Moves

cf1716 B. Permutation Chain

cf1714 A. Everyone Loves to Sleep

cf1714 B. Remove Prefix

cf1714 C. Minimum Varied Number

---

cf1713 A. Traveling Salesman Problem

题意

你生活在一个无限平面上，上面有笛卡尔坐标系。在一个移动中，您可以到达四个相邻点（左、右、上、下）中的任何一个。

更正式地说，如果你站在点 (x,y)，你可以：

向左走，然后移动到 (x−1,y)，或者
向右走，然后移动到 (x+1,y)，或者
向上，移动到 (x,y+1)，或者
向下，移动到 (x,y−1)。
这架飞机上有 n 个箱子。第 i 个框的坐标为 (xi,yi)。保证这些框位于 x 轴或 y 轴上。即，xi=0 或yi=0。

如果你和盒子在同一点，你可以收集一个盒子。如果您必须在点 (0,0) 开始和结束，请找出您必须执行的最小移动次数以收集所有这些框。

输入
第一行包含一个整数 t (1≤t≤100)——测试用例的数量。

每个测试用例的第一行包含一个整数 n (1≤n≤100)——盒子的数量。

以下 n 行的第 i 行包含两个整数 xi 和 yi (−100≤xi,yi≤100) — 第 i 个框的坐标。保证 xi=0 或 yi=0。

请注意，所有测试用例的 n 的总和是无界的。

输出
对于每个测试用例输出一个整数——所需的最小移动次数。

思路

最短路线可以拼接成一个矩形，所以找出横纵坐标最远的点把路线加起来即可

代码

#include 
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int nx=0,ny=0,px=0,py=0;
        while(n--)
        {
            int x,y;
            cin>>x>>y;
            if(x<0) nx=max(nx,-x);
            if (x>=0) px=max(px,x);
 
            if(y<0)ny=max(ny,-y);
            if(y>=0)py=max(py,y);
        }
        cout<<(2*nx+2*ny+2*px+2*py)<
 
    }
    return 0;
}

cf1713 B. Optimal Reduction

题意

考虑一个由 n 个正整数组成的数组 a。

您可以执行以下操作：

选择两个索引 l 和 r (1≤l≤r≤n)，则
将所有元素 al,al+1,…,ar 减 1。
让我们将 f(a) 称为将数组 a 更改为 n 个零的数组所需的最小操作数。

确定对于 a 的所有排列† b，f(a)≤f(b) 是否为真。

† 如果 b 由 a 的元素以任意顺序组成，则数组 b 是数组 a 的排列。例如，[4,2,3,4] 是 [3,2,4,4] 的排列，而 [1,2,2] 不是 [1,2,3] 的排列。

输入
第一行包含一个整数 t (1≤t≤104)——测试用例的数量。

每个测试用例的第一行包含一个整数 n (1≤n≤105) — 数组 a 的长度。

第二行包含 n 个整数 a1,a2,…,an (1≤ai≤109) — 数组 a 的描述。

保证所有测试用例的 n 总和不超过 105。

输出
对于每个测试用例，如果对于 a 的所有排列 b，f(a)≤f(b) 为真，则打印“YES”（不带引号），否则打印“NO”（不带引号）。

您可以在任何情况下输出“YES”和“NO”（例如，字符串“yEs”、“yes”和“Yes”将被识别为肯定响应）。

思路

找出输出NO的情况，即在数组中是否存在ai，ai的前面并且后面都有大于ai的数，所以判断数组中元素前面和后面的最大值就是输出NO的情况

代码（错误样例）

#include
using namespace std;
const int N=110;
typedef long long LL;
LL a[N];
void solve()
{
    int n;
    cin>>n;
    for(int i=0;i>a[i];
    LL x,y;
    for(int i=1;i-1;i++)
    {
 
        x=*max_element(a,a+i);
        y=*max_element(a+i+1,a+n);
        if(x>a[i]&&a[i]
        {
            cout<<"NO"<
            return ;
        }
 
    }
    cout<<"YES"<
    return ;
}
int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

最大值函数的复杂度是O（n），所以会超时。一般复杂度在1e7~1e8

正确做法用两个数组分别记录一下每个元素前面和后面的最大值然后进行判断

AC代码

#include
using namespace std;
const int N=1e5+10;
typedef long long LL;
LL a[N],b[N],c[N];
void solve()
{
    int n;
    cin>>n;
    for(int i=0;i>a[i];
    b[0]=a[0];
    c[n-1]=a[n-1];
    for(int i=1;imax(b[i-1],a[i]);
    for(int i=n-2;i>=0;i--)c[i]=max(c[i+1],a[i]);
    for(int i=1;i-1;i++)
    {
        if(b[i]>a[i]&&a[i]
        {
            cout<<"NO"<
            return ;
        }
 
    }
    cout<<"YES"<
    return ;
}
int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

cf1713 C. Build Permutation

题意

如果对于所有有效索引 i (0≤i≤n−1)，ai+i 是一个完美的正方形†，则大小为 n 的 0 索引数组 a 称为好数组。

给定一个整数 n。找到一个 [0,1,2,…,n−1] 的排列‡ p 是好的或确定不存在这样的排列。

† 如果存在满足 x=y2 的整数 y，则称整数 x 为完全平方。

‡ 如果 b 由 a 的元素以任意顺序组成，则数组 b 是数组 a 的排列。例如，[4,2,3,4] 是 [3,2,4,4] 的排列，而 [1,2,2] 不是 [1,2,3] 的排列。

输入
第一行包含一个整数 t (1≤t≤104)——测试用例的数量。

每个测试用例的唯一一行包含一个整数 n (1≤n≤105) — 排列 p 的长度。

保证所有测试用例的 n 总和不超过 105。

输出
对于每个测试用例，输出 n 个不同的整数 p0,p1,…,pn−1 (0≤pi≤n−1) — 排列 p — 如果答案存在，否则为 -1。

代码

#include
using namespace std;
void solve()
{
	int n;
	cin>>n;
	vector<int> a(n);
	vector<int> b(n,0);
	int t=0;
	for(int i=0;i
    {
        a[i]=i;
        if(t*t
        b[i]=t*t;
    }
    int j=n-1;
    while(j>0)
    {
        if(2*j-b[j]<0)
        {
            cout<<"-1"<
            return ;
        }
        reverse(a.begin()+(b[j]-j),a.begin()+j+1);
        j=b[j]-j-1;
    }
	for (auto now:a)
		cout<' ';
	cout<
}
int main()
{
	int T;
	cin>>T;
	while(T--)
		solve();
	return 0;
}

cf1716 A. 2-3 Moves​​​​​​​

题意

你站在坐标线上的 0 点。 你的目标是到达点 n。 在一分钟内，您可以向左或向右移动 2 或 3（即，如果您当前的坐标是 x，它可以变为 x−3、x−2、x+2 或 x+3 ）。 请注意，新坐标可能变为负数。

你的任务是找出从点 0 到点 n 所需的最少分钟数。

你必须回答 t 个独立的测试用例。

输入
输入的第一行包含一个整数 t (1≤t≤104) — 测试用例的数量。 然后是描述测试用例的 t 行。

这些行中的第 i 行包含一个整数 n (1≤n≤109)——第 i 个测试用例的目标。

输出
对于每个测试用例，打印一个整数——对应测试用例从点 0 到点 n 所需的最小分钟数。

代码

#include
using namespace std;
int n,t;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        if (n == 1)
            cout<<2<
        else if (n == 2)
            cout<<1<
        else
        {
            int x=n/3;
            int y=n%3;
            if (y==2||y==1)
                cout<1<
            else
                cout<
        }
    }
    return 0;
}

cf1716 B. Permutation Chain

题意

长度为 n 的排列是从 1 到 n 的整数序列，使得每个整数在其中恰好出现一次。

令排列 p 的固定性为其中不动点的数量——使得 pj=j 的位置 j 的数量，其中 pj 是排列​​ p 的第 j 个元素。

你被要求构建一系列排列 a1,a2,...，从恒等排列开始（排列 a1=[1,2,...,n]）。我们称其为排列链。因此，ai 是长度为 n 的第 i 个排列。

对于从 2 开始的每个 i，排列 ai 应该通过交换其中的任意两个元素（不一定是相邻的）从排列 ai-1 中获得。排列 ai 的固定性应严格低于排列 ai-1 的固定性。

考虑 n=3 的一些链：

a1=[1,2,3], a2=[1,3,2] - 这是一个长度为 2 的有效链。从 a1 到 a2，位置 2 和 3 上的元素交换，固定性从 3 减少到1.
a1=[2,1,3], a2=[3,1,2] — 这不是一个有效的链。对于 n=3，第一个排列应始终为 [1,2,3]。
a1=[1,2,3], a2=[1,3,2], a3=[1,2,3] — 这不是一个有效的链。从 a2 到 a3，位置 2 和 3 上的元素被交换，但固定性从 1 增加到 3。
a1=[1,2,3], a2=[3,2,1], a3=[3,1,2] — 这是一个长度为 3 的有效链。从 a1 到 a2，位置 1 和3 交换，固定性从 3 减少到 1。从 a2 到 a3，位置 2 和 3 的元素交换，固定性从 1 减少到 0。
找到最长的排列链。如果有多个最长的答案，打印其中任何一个。

输入
第一行包含一个整数 t (1≤t≤99)——测试用例的数量。

每个测试用例的唯一一行包含一个整数 n (2≤n≤100) — 链中所需的排列长度。

输出
对于每个测试用例，首先，打印排列链 k 的长度。

然后打印 k 个排列 a1,a2,…,ak。 a1 应该是长度为 n ([1,2,…,n]) 的恒等排列。对于从 2 到 k 的每个 i，应该通过交换 ai-1 中的两个元素来获得 ai。它还应该具有比 ai-1 严格更低的固定性。

代码1

#include 
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<int>res;
        cout<
        for(int i=0;i
        {
            res.push_back(i+1);
            cout<1<<" ";
        }
        cout<
        for(int i=1;i
        {
            swap(res[i],res[i-1]);
            for(int v:res) cout<" ";
            
            cout<
        }
        
    }
    return 0;
}

代码2

#include
using namespace std;
const int N=120;
int n,t;
int a[N];
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int j=1;j<=n;j++) a[j]=j;
 
        cout<
        for(int j=1;j<=n;j++) cout<" ";
 
        cout<
 
        for(int j=0;j-1;j++)
        {
            swap(a[n-j],a[n-1-j]);
            for(int k=1;k<=n;k++) cout<" ";
            cout<
        }
    }
    return 0;
}
 
 

cf1714 A. Everyone Loves to Sleep

题意

弗拉德和其他人一样，非常喜欢睡觉。

弗拉德每天必须在特定时间做 n 件事。对于这些事情中的每一个，他都设置了一个闹钟，其中第 i 个在每天的 hi 小时 mi 分钟触发（0≤hi<24,0≤mi<60）。 Vlad 使用 24 小时时间格式，因此在 h=12,m=59 之后是 h=13,m=0，在 h=23,m=59 之后是 h=0,m=0。

这次弗拉德在 H 小时 M 分钟（0≤H<24,0≤M<60）上床睡觉，并要求您回答：直到下一个闹钟响，他才能睡多少觉。

如果在他上床睡觉的时间任何闹钟响起，那么他将睡一段长度为 0 的睡眠。

输入
输入数据的第一行包含一个整数 t (1≤t≤100) — 测试中的测试用例数。

案例的第一行包含三个整数 n、H 和 M (1≤n≤10,0≤H<24,0≤M<60)——警报次数和 Vlad 上床睡觉的时间。

以下 n 行包含两个数字，每个 hi 和 mi (0≤hi<24,0≤mi<60) — 第 i 次警报的时间。两个或多个警报同时触发是可以接受的。

描述时间的数字不包含前导零。

输出
输出 t 行，每行包含对应测试用例的答案。作为答案，输出两个数字——分别是弗拉德要睡觉的小时数和分钟数。如果在他上床睡觉的时间任何闹钟响起，答案将是 0 0。

代码

#include 
using namespace std;
int T, t, H, M, h, m;
int main()
{
    cin>>T;
    while (T--)
    {
        cin>>t>>H>>M;
        int r=1439;
        while(t--)
        {
            cin>>h>>m;
            int a=(h*60+m)-(H*60+M);
            a < 0 ? a += 24 * 60 : a;
            if (a
                r=a;
        }
        cout<60<<' '<60<
    }
    return 0;
}

cf1714 B. Remove Prefix

题意

Polycarp 提供了一些长度为 n (1≤ai≤n) 的整数 a 序列。只有由不同的数字（即不同的数字）组成的序列才能使 Polycarp 快乐。

为了使他的序列像这样，Polycarp 将进行一些（可能为零）的移动。

在一个动作中，他可以：

删除序列的第一个（最左边）元素。
例如，在一次移动中，序列 [3,1,4,3] 将产生由不同数字组成的序列 [1,4,3]。

确定他需要进行的最小移动次数，以便在剩余序列中所有元素都不同。换句话说，找到给定序列 a 的最小前缀的长度，将其删除后，序列中的所有值都是唯一的。

输入
输入的第一行包含一个整数 t (1≤t≤104) — 测试用例的数量。

每个测试用例由两行组成。

第一行包含一个整数 n (1≤n≤2⋅105) — 给定序列 a 的长度。

第二行包含 n 个整数 a1,a2,…,an (1≤ai≤n) — 给定序列 a 的元素。

保证所有测试用例的 n 值之和不超过 2⋅105。

输出
对于每个测试用例，将您的答案打印在单独的行上——必须从序列开头删除的最小元素数，以便所有剩余元素都不同。

代码

#include
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		vector<int> a(n);
		vector<int> b(n + 1);
		int k=0,q=0;
		for (int i=0;i
		{
			cin>>a[i];
			if (b[a[i]]==0) q++;  
			b[a[i]]++;
			k++;
		}
		k-=q;
		if(k==0)
		{
			cout<<0<
			continue;
		}
		for(int i=0;i
		{
			if(b[a[i]]>1)
			{
				b[a[i]]--;
				k--;
				if(k==0)
				{
					cout<1<
					break;
				}
			}
		}
	}
	return 0;
}

cf1714 C. Minimum Varied Number​​​​​​​

题意

找到具有给定数字总和 s 的最小数字，使得其中的所有数字都是不同的（即所有数字都是唯一的）。

例如，如果 s=20，则答案为 389。这是所有数字不同且数字之和为 20（3+8+9=20）的最小数字。

对于给定的 s 打印所需的数字。

输入
第一行包含一个整数 t (1≤t≤45)——测试用例的数量。

每个测试用例由包含唯一整数 s (1≤s≤45) 的行指定。

输出
打印 t 个整数——给定测试用例的答案。

代码

#include
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
    {
		int n;
		cin>>n;
		int l=9;
		vector<int> v;
		while(l>0 || n>0)
		{
			if(n>=l)
			{
				v.push_back(l);
				n-=l;
				l--;
			}
			else
			{
				v.push_back(n);
				break;
			}
		}
		int ans=0;
		int i =v.size()-1;
		while(i>=0)
		{
			ans= ans*10+ v[i];
			i--;
		}
		cout<
	}
	return 0;
}