2022/1/5
2022/1/5
[ Paimon Sorting ]( D (codeforces.com) )
思路
设前i-1个数的最大值是 Max
- 当a[i]
- 当a[i]==Max时，不产生贡献
- 当a[i]>Max时，产生的贡献为 2+cnt. cnt为第二次出现Max的位置到i的数个数。
参考代码
#include
#define ll long long
#define pii pair
#define se second
#define pb push_back
#define pf push_front
#define si size()
#define db double
#define ls (p<<1)
#define rs (p<<1|1)
#define fi first
#define se second
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const int qs=2e5+7;
const ll mod=998244353;
ll T,n,k,u[qs],c[qs],a[qs];
ll lb(ll x){
return x&(-x);
}
void add(ll x,ll val){
for(;x<=n;x+=lb(x)) c[x]+=val;
}
ll ask(ll x){
ll ret=0;
for(;x>0;x-=lb(x)) ret+=c[x];
return ret;
}
int main(){
T=read();
while(T--){
n=read();
for(int i=1;i<=n;++i) a[i]=read(),u[i]=0,c[i]=0;
ll Max=-1,ans=0,flag=0,cnt=0;
for(int i=1;i<=n;++i) {
if(!u[a[i]]) add(a[i],1),u[a[i]]=1;
if(i==1){
Max=a[i];
cout<<"0";
continue;
}
if(a[i]==Max||flag) cnt++;
if(a[i]>Max){
flag=0;
ans=ans+2+(cnt ? cnt-1 : 0);
Max=a[i];
cnt=0;
}
else if(a[i]==Max) {
//cout<<"i="< [ J. Xingqiu's Joke ]( Problem - J - Codeforces )
思路
设 a
根据同余定理有: \(a \equiv b(modg)\)
那么对于\((a,b,c)\),我们需要将其转换为$ (\lfloor { \frac ag } \rfloor ,\lfloor { \frac bg } \rfloor,\frac cg)$ 或者我们需要将其转换为$ (\lceil { \frac ag } \rceil ,\lceil { \frac bg } \rceil,\frac cg)$ 。
在两者中取步数小的。
注意用unordered_map,map会超时。
unordered_map 对 pair 存储
struct hash_pair {
template
size_t operator()(const pair& p) const
{
auto hash1 = hash{}(p.first);
auto hash2 = hash{}(p.second);
return hash1 ^ hash2;
}
};
unordered_map< pii ,ll,hash_pair> mp;
参考代码
#include
#define ll long long
#define pii pair
#define se second
#define pb push_back
#define pf push_front
#define si size()
#define db double
#define ls (p<<1)
#define rs (p<<1|1)
#define fi first
#define se second
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const int qs=2e5+7;
const ll mod=998244353;
struct hash_pair {
template
size_t operator()(const pair& p) const
{
auto hash1 = hash{}(p.first);
auto hash2 = hash{}(p.second);
return hash1 ^ hash2;
}
};
ll T;
vector v;
unordered_map< pii ,ll,hash_pair> mp;
ll dfs(ll a,ll c){
if(a==1) return 0;
if(c==1) return a-1;
if(mp[{a,c}]) return mp[{a,c}];
ll Min=a-1;
for(int i=0;i1) v.pb(c);
cout<