A. CME

题意：

你有 N 根火柴 , 多少根火柴就可以组成多大的数（如 三根火柴可以表示 3）, 现在要求你用火柴组成任意三个数 A , B , C 使得 A + B = C 关系成立

如果无论怎么组都无法使等式成立 , 则你可以额外购入 X 根火柴来重新组数使得关系成立 , 求 X 的最小值

分析：

签到题。

特判 N = 2 , X = 2

当 N > 2 时不难发现当 N 为偶数时是肯定可以找到对应的 A , B , C 使得 A + B = C 的 , N 为奇数时肯定是找不到对应的 A , B , C 的 , 所以当 N 为奇数时我们只需要额外购入一根火柴使总共的火柴数为偶数即可

#include
#define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define numm ch - 48
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pi 3.14159265358979323
#define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=numm;isdigit(ch=getchar());res=(res<<)+(res<<)+numm);flag&&(res=-res);} templatevoid Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}
ll fact_pow(ll n,ll p){ll res=;while(n){n/=p;res+=n;}return res;}

const int N = 3e5 + ;

int main()
{
int t ;
cin >> t;
while(t--)
{
long long n ;
cin >> n;
if(n == )
{
cout << << endl;
}
else
{
if(n & )
cout << << endl;
else cout << << endl;
}
}
return ;
}

B. Strings Equalization

题意：

给定两个字符串 S 和 T  , 你可以使 S 串任意相邻的两个位置的字符都变为其中的一个字符 , T 串也可以进行 S 串的操作 , 问将 S 串 T 串任意改变最后能否使得 S = T

分析：

签到题。

只要 S 和 T 串有一个相同的字符 , 那么我们就可以把 S 和 T 都变为只有这个字符的字符串 ,  若一个相同字符都不存在则不可能使 S = T

#include
#define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define numm ch - 48
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pi 3.14159265358979323
#define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=numm;isdigit(ch=getchar());res=(res<<)+(res<<)+numm);flag&&(res=-res);} templatevoid Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}
ll fact_pow(ll n,ll p){ll res=;while(n){n/=p;res+=n;}return res;}

const int N = 3e5 + ;

int main()
{
ios;
int haha;
cin >> haha;
string s ,t;
while(haha--)
{
cin >> s >> t;
int flag = ;
int len = s.size();
for(int i = ; i < len ; i++)
{
for(int j = ; j < len ; j++)
{
if(s[i] == t[j])
{
flag = ;
break;
}
}
if(flag) break;
}
if(flag) cout << "YES" << endl;
else cout << "NO" <<endl;
}
return ;
}

C. Save the Nature

题意：

你有 N 张票和一个预期收入 K , 每张票的价格为 Pi ,你可以从 N 张票中选出任意张票任意摆放

对于选出来的数摆放完后你的收入money  =  a倍数的位置的票的价格 *  x + b倍数的位置的票的价格 * y + lcm(a,b)倍数的位置的票的价格 * (x + y)

// 若某个位置既是 a 或 b 的倍数 又是 lcm(a,b)的倍数 , 则它只属于lcm(x,y)的倍数 ; 若某个位置不是 a 不是 b 也不是 lcm(a,b) 的倍数 , 则它能带来的收入为0

问最少可以选出几张票任意摆放后使得 money > K , 若不论怎么选都无法使得money > K , 则输出 -1

分析：

贪心 + 二分答案

从大到小排序后 , 假设挑选出 M 张票（从前往后挑选）

那么票价高的票肯定是要尽可能的放在 lcm(a,b)的位置上 , 若lcm(a,b)的位置不存在则尽可能放在 max(x,y) 对应的 a（b） 位置上 , 若max(x,y)对应的a（b）位置也不存在 , 则放在min(x,y)对应的a（b）上

若这些位置都不存在 或者 最后得到的 money < K , 则说明挑选M 张票还不够; 若最后得到的 money >= K , 则挑选 M 张票可能过多了

所以对答案进行二分查找即可

这里用到前缀和使计算起来方便些(っ•̀ω•́)っ

#include
#define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define numm ch - 48
#define INF 0x3f3f3f3f
#define pi 3.14159265358979323
#define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=numm;isdigit(ch=getchar());res=(res<<)+(res<<)+numm);flag&&(res=-res);} templatevoid Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}
ll fact_pow(ll n,ll p){ll res=;while(n){n/=p;res+=n;}return res;}

const int N = 2e5 + ;
ll sum[N] , aa[N];
ll n , k , x , y , a, b;
int num1 , num2 , num3;
bool check(int num)
{
num1 = num / lcm(a,b);
num2 = num / a - num1;
num3 = num / b - num1;
ll res = ;
res += (x + y) * sum[num1] + x * (sum[num1 + num2] - sum[num1]) + y * (sum[num1 + num2 + num3] - sum[num1 + num2]);
return res >= k;
}
bool cmp(ll a, ll b)
{
return a > b;
}
int main()
{
ios;
int t;
cin >> t;
while(t--)
{
mm(aa , ) , mm(sum , );
cin >> n;
rep(i , ,n)
{
cin >> aa[i];
aa[i] /= ;
}
sort(aa + , aa + + n , cmp);
partial_sum(aa + , aa + + n , sum + );
cin >> x >> a >> y >> b >> k;
if(x < y){x^=y,y^=x,x^=y,a^=b,b^=a,a^=b;}; int l = , r = n; int ans = n + ; while(l <= r) { int mid = l + r >> ;
if(check(mid))
{
ans = min(ans , mid);
r = mid - ;
}
else l = mid + ;
}
if(ans <= n) cout << ans << endl;
else cout << - << endl;

}  
return ;  

}

D. Sequence Sorting

题意：

给你一个长度为 N 的序列 , 你每次操作可以把序列中的相同数字移到序列的最前端或者最末端 , 问最少可以进行多少次操作使得序列为连续上升序列

分析：

求出最多的不需要移动的数字的个数, 那么答案就是总的数字个数 - 最多的不需要移动的数字的个数

对于每个数我们可以用 lef 记录它出现的最左端 , rig 记录它出现的最右端 , 然后用last记录比它小的前一个数字的最右端 , 判断 last 和 lef[ now ]的关系 , 详见代码

#include
#define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define numm ch - 48
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pi 3.14159265358979323
#define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=numm;isdigit(ch=getchar());res=(res<<)+(res<<)+numm);flag&&(res=-res);} templatevoid Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}
ll fact_pow(ll n,ll p){ll res=;while(n){n/=p;res+=n;}return res;}

const int N = 3e5 + ;
int lef[N] , rig[N] , a[N];
int t , n;
int main()
{
ios;
cin >> t;
while(t--)
{
cin >> n;
maphaha;
rep(i , ,n)
lef[i] = rig[i] = ;
rep(i , ,n)
{
cin >> a[i];
if(!haha[a[i]])
{
lef[a[i]] = i;
}
rig[a[i]] = i;
haha[a[i]] = ;
}
int last = , ans = , cnt = , tot = ;
rep(i , ,n)
{
if(lef[i])
{
if(last < lef[i])
cnt ++;
else
cnt = ;
last = rig[i];
ans = max(ans , cnt);
tot ++;
}
}
cout << tot - ans << endl;
}
return ;
}