A. Traveling Salesman Problem
找到最短路径的规律,发现找到一个最大矩形即可
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int N = 1e4 + 10,M = 3e5 + 10;
typedef long long LL;
//#define int long long
typedef pair<int,int>PII;
//#define x first
//#define y second
void solve()
{
int n;cin >> n;
int left = 0,right = 0,up = 0,down = 0;
for(int i = 0; i < n; i ++)
{
int x,y;cin >> x >> y;
left = min(left, x);
right = max(right, x);
up = max(up, y);
down = min(down, y);
}
cout << 2 * (up - down + right - left) << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}
题目是给定我们一个数组,我们可以使连续的一段减去1,问我们它是否在所有排列中
是操作次数最少的一个
我们可以发现,要使得操作次数最少,我们的序列得是类似山峰的一段,即不能有"凹陷"
于是我们可以统计一下前缀和后缀最大值,然后看是否有中间的一个数比它左右都小
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int N = 1e5 + 10,M = 3e5 + 10;
typedef long long LL;
//#define int long long
typedef pair<int,int>PII;
//#define x first
//#define y second
int a[N];
int max1[N],max2[N];
void solve()
{
int n;cin >> n;
for(int i = 1; i <= n; i ++)cin >> a[i];
//统计一下前缀最大值和后缀最大值,然后检查一下原数组是否有凹陷,若有则一定存在更优解
for(int i = 1; i <= n; i ++) max1[i] = max(max1[i - 1], a[i]);
max2[n] = a[n];
for(int i = n - 1; i >= 1; i --) max2[i] = max(max2[i + 1], a[i]);
bool ok = true;
for(int i = 2; i < n; i ++)
{
if(max1[i] > a[i] && max2[i] > a[i])
{
ok = false;
break;
}
}
if(ok)cout << "YES" << endl;
else cout << "NO" << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}
题意:给定我们一段数,让我们安排他们的顺序使得ai+i等于某个数的平方(下标从0开始),并输出这段序列
根据我们的观察可以发现对于每个数我们只需要找到在2*(n-1)范围内的最大一个t,然后找到对应的位置
依次往后放即可
例如:n=7,1 0 2 6 5 4 3
对于6,我们发现在2*(n-1)范围内最大的平方数是9,我们就找到6所在的位置(9-6=3,即放到第四个位置)顺次往后填直到结尾
然后再找次小的4,再找到对应的位置顺次填后即可
总结做法:
1、从大到小找到最大的平方数,!(x<=t*t&&t*t<=2*(n-1))
2、找到最大要减去的数u=t*t-x
3、找到能放的长度len=n-u,我们的下标是从1开始的,所以n里面就已经加1了
4、更新n
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int N = 1e5 + 10,M = 3e5 + 10;
typedef long long LL;
//#define int long long
typedef pair<int,int>PII;
//#define x first
//#define y second
int a[N];
void solve()
{
int n;cin >> n;
int now = n,k = n;
while(n > 0)
{
int t = 0;
while(!(n - 1 <= t * t && t * t <= 2 * (n - 1)))t ++;
int u = t * t - (n - 1);//当前要加的数
int len = n - u;
for(int i = 1; i <= len; i ++)
{
a[now] = t * t - now + 1;
now --;
}
n -= len;
}
for(int i = 1; i <= k; i ++)cout << a[i] << " ";
cout << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}