cf教育场a-e奉上/12.1
前言：好久没打cf了，确实感觉手生了，立个flag：一天来一场cf练习。
A.无脑方式：直接看样例，输出输入数字的长度
x/f((x))的作用就是把后缀零都给删了，对于一个数x，x/f(f(x))，实际上表示的值与x的后缀0有多少个有关，比如100就是100，90就是10...，而后缀0有多少个与位数有关。
code：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
string s;
while(t--)
{
cin >> s;
cout << s.length() << endl;
}
}B.
一开始我的想法对于一个n，只要找到i(i+1)/2，使得这个大于n，然后多的都-1过去。但这是一个错误的想法，原因是这样还不够小。重新想一下发现对于1+2+3+...+i,如果把其中的某一步替换为-1，那么会比原来少了-2,-3,-4,,,也就是说除了-1以外，任何比(i-1+1)(i-1)/2大，比(i+1)*i/2小的数都可以在i来完成。如果是那么-1只能是i步+1。
code：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t; cin >> t;
while(t--)
{
int n, i;
cin >> n;
for(i = 1; i*(i+1)/2 < n; i++);
cout << i + (i*(i+1)/2 == n+1) << endl;
}
}C.
博弈题，alice和bob都首先希望增加自己得分，其次再尽量减少对方的得分。
我们可以先分几种情况来考虑，加入x>=y,bob为了让自己的得分尽量大会让alice先赢上x-1局，最后一局bob可以迎击并且仍然让自己得分尽量大。这是bob来掌控的贪心。
如果x<y,bob最大的取胜次数显而易见为y，为了让自己的分数最大，他会让x先赢x-1局，分析思路仍然与上一个相同，（与其说是博弈倒不如说是贪心？）
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int x, y;
cin >> x >> y;
cout<<x-1 << " " << y << endl;
}
}D.
题意很好理解，通过每一个与x进行置换来让队列有序，问最少操作几次。假设现在有个队列前面都比x小，然后遇到一个比x大的，那么它换还是不换呢？看到总数据量才500就知道暴力check呗，如果现在本来就是有序的当然不换并且break掉，如果当前是不满足的，那么肯定要换，并且是第一次遇到比x大的时候就换。
E.
假设4个点别在最后的正方形的左下，右下，左上，右上，记为p1，p2，p3，p4，那么设x1=min(p1x,p3x),x2=max(p1x,p3x),x3=min(p2x,p4x),x4=max(p2x,p4x)
那么显然目标正方形左边位于x1，x2之间为最优且花费恒为x2-x1，右边位于x3，x4之间为最优且花费恒为x4-x3，那么相加这就是costx，(在写代码的时候发现自己遗漏了如果x4<x1)，通过对x的讨论我们可以得到范围:(x2-x3,x4-x1),同理对于y，但题目要求是个正方形，如果x的范围和y的范围中有交集可以通过适当调整不改变costx+costy,但如果x的范围不包含y的范围且差值为val，那么某一维自然都要补上val。
这种思路参考别人题解链接：https://www.cnblogs.com/qieqiemin/p/14069636.html
还看到一种思路是：
首先这四个点对应在正方形上点的顺序总共只有4！种可能性，可以用next_permutation来枚举这个对应顺序。
接下来是这个正方形的边长，它的边长肯定是这四个点之间的横纵坐标差的绝对值中的一个，共有12种可能性。
假设左下的点为a[1],右下的点为a[2],左上的点为a[3],右下的点为a[4]。
枚举边长d，我们先将四个点做操作，x的1，3固定，y的1，2固定：
a[2].x-=d, a[4].x-=d, a[3].y-=d, a[4].y-=d
经典问题：横纵坐标分开考虑，显然是移动到中位数位置即可。
给定序列求最少总变化量使所有数相等,结论是取中位数（若序列长度为偶数，可以取中部区间中的任意一值。）
code:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
int a[maxn];
int n, x;
bool ck()
{
for(int i=1; i<= n-1; i++){
if(a[i] > a[i+1]) return false;
}
return true;
}
int main()
{
int t;
cin >> t;
while(t--)
{
cin >> n >> x;
for(int i=1; i<=n; i++){
cin >> a[i];
}
int s = 0;
for(int i=1; i<=n; i++){
if(ck()){
break;
}
if(a[i] > x)
{
swap(a[i], x);
s++;
}
}
cout << (ck() ? s : -1) << endl;
}
}
code:)
#include <bits/stdc++.h>
using namespace std;
#define N 5
#define int long long
int p[N], x[N], y[N];
struct Node{
int x, y;
}a[N];
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t;
cin >> t;
for(int i=0; i<4; i++) p[i] = i;
while(t--)
{
vector<int> vlen;
for(int i=0; i<4; i++) {
cin >> a[i].x >> a[i].y;
for(int j=0; j<i; j++){
vlen.emplace_back(abs(a[i].x-a[j].x));
vlen.emplace_back(abs(a[i].y-a[j].y));
}
}
int ans = 1e18;
do{
for(int i=0; i<4; i++){
x[i]=a[p[i]].x, y[i]=a[p[i]].y;
}
for(auto d : vlen){
x[1]-=d; x[3]-=d, y[2]-=d, y[3]-=d;
int cnt = 0;
vector<int> vx;
vector<int> vy;
for(int i=0; i<4; i++){
vx.emplace_back(x[i]);
vy.emplace_back(y[i]);
}
sort(vx.begin(),vx.end());
sort(vy.begin(),vy.end());
for(int i=0; i<4; i++){
cnt += abs(vx[i]-vx[1]);
cnt += abs(vy[i]-vy[1]);
}
ans = min(ans, cnt);
x[1]+=d; x[3]+=d, y[2]+=d, y[3]+=d;
}
}while(next_permutation(p,p+4));
cout << ans << endl;
}
}
投递华为等公司10个岗位
