A
核心思路
水题，想清楚代价就好了。
// Problem: A. GamingForces
// Contest: Codeforces - Educational Codeforces Round 142 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1792/problem/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
int a[1000];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
int cnt=0;
for(int i=1;i<=n;i++)
{
if(a[i]==a[i+1]&&a[i]==1)
{
cnt++;
i++;
}
else
{
cnt++;
}
}
cout<<cnt<<endl;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
B
核心思路
这个题目当时陷入了一个误区，以为需要分几种情况轮着使用。但是这样就会比较麻烦。
其实这么想比较好，首先把我们的a全部都用完，然后把我们b和c较小的那个先使用完。这里需要乘2。因为另外一个还需要补这么多回来。这样就只剩下了b-c和d还没有使用完。这里就要讨论a是否可以支撑这样的消耗，所以两者去最小值就好了。
// Problem: B. Stand-up Comedian
// Contest: Codeforces - Educational Codeforces Round 142 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1792/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
void solve()
{
int a,b,c,d;
cin>>a>>b>>c>>d;
int b1=a,c1=a;
if(!a)
{
cout<<1<<endl;
}
else
{
cout<<a+min(b,c)*2+min(a+1,abs(b-c)+d)<<endl;//后面这个是次数刚好用完。
}
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
C
核心思路
这个题目没有这么好想，我们就先从一般的样例入手：2 3 1 5 4。我们可以发现这种情况就只需要交换5 1.所以我们对于\(1\sim n\)里面的数本质使用操作交换\(i和n-i+1\)。如果\([i,n-i+1]\)这个区间里面的数都是有序的肯定是不需要交换的。所以我们可以枚举这个这个区间里面的数。
(可以类比冒泡排序)那怎么判断他是否有序呢，我们可以使用pos数组记录每个数的下标。再看其是否构成逆序对。这个判断是否某个区间有序的方法可以学一下。然后有个小细节就是我们的i尽量从\(\frac{n+1}{2}\)开始枚举，因为我们需要从大的数开始枚举，为什么需要这样呢。因为如果从小的开始枚举,我们那些大的肯定有需要重新排下序。
// Problem: C. Min Max Sort
// Contest: Codeforces - Educational Codeforces Round 142 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1792/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
void solve()
{
int n;
cin>>n;
int t=1;
vector<int> pos(n+1);
for(int i=0;i<n;i++)
{
int x;
cin>>x;
pos[x]=i;
}
int l=(n+1)/2;
int r=(n+2)/2;
while(l>0&&(l==r||(pos[l]<pos[l+1]&&pos[r-1]<pos[r])))
{
l--;
r++;
}
/*一定要注意这里的r-l-1才是区间长度。
vector<int> pos(n+1);vector<int> pos(n+1);因为当我们的长度是奇数，r肯定会越界。+
cout<<l<<" "<<r<<endl;*/
cout<<(n-r+l+1)/2<<endl;;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
D
题意
题意：
给定 n(n≤5×104) 个排列 a1,a2,a3,a4.....an ，每个排列的长度都为 m(1≤m≤10) 。
定义一个排列 p 的漂亮值为 k ：
找到最大的一个数字 k ，满足 p[1]=1,p[2]=2,p[3]=3,.....p[k]=k
定义两个排列的乘法 p⋅q 的结果为一个新的排列 r ，其中 r[i]=q[p[i]]
核心思路
p: 2 3 4 1
q: 2 3 1 4
当i=1时p[1]=2,q[p[1]]=3,r[1]=3;
当i=2时p[2]=3,q[p[2]]=1,r[2]=1;
......
r=[3,1,4,2]
接下来就是去想怎么去构造一个最大的漂亮之呢。很显然这个序列的最大值时最大的：1 2 3 4.
如果我们的\(p=[3,1,4,2]\)
i=1,我们希望 q[3]=1;
i=2,我们希望 q[1]=2;
i=3,我们希望 q[4]=3;
i=4,我们希望 q[2]=4；
其实就是q[p[i]]=i.这个样子肯定就是最优解。所以我们可以把我们构造出来的最优解先搞出来。然后在和我们的实际情况去匹配。
这里的p.q是换了一个位置的，
例如： p=[4,3,5,1,2],q=[5,4,2,1,3],pos[q]=[4,3,5,2,1].
pos是我们构造出来的最优解， p是我们实际的取值。(我们这里是希望p[q[i]]=i的，因为这样才能取到最优解)
所以我们进行前缀匹配就好了，这里的最长前缀是3，所以漂亮值也是3.
至于这个数据结构很显然可以使用字典树来维护。
// Problem: D. Fixed Prefix Permutations
// Contest: Codeforces - Educational Codeforces Round 142 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1792/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
const int N=5e4+10;
int tot,n,m;
int tr[N*11][11];
int a[N][11];
void solve()
{
tot=0;
cin>>n>>m;
//build tree
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
int pos[11]={0};
for(int j=1;j<=m;j++)
pos[a[i][j]]=j;
int u=0;
for(int j=1;j<=m;j++)
{
if(!tr[u][pos[j]])
{
tr[u][pos[j]]=++tot;
}
u=tr[u][pos[j]];
}
}
for(int i=1;i<=n;i++)
{
int len=0;
int u=0;
for(int j=1;j<=m;j++)
{
if(tr[u][a[i][j]])
{
u=tr[u][a[i][j]];
len++;
}
else
break;
}
cout<<len<<" ";
}
cout<<endl;
for(int i=0;i<=tot;i++)//一定要注意这里是小于tot，因为我们总共开了这么多节点，
{
memset(tr[i],0,sizeof tr[i]);
}
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}