A. Three Strings
题意：每次可以把c[i]拿去和a[i]或b[i]交换。 问你能否把ab变成相等。
思路：在ab不相等的时候看看c能不能与一方相等来中和。不能的话就不行。
view code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#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 pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };
int main()
{
int kase;
cin>>kase;
while(kase--)
{
string a, b , c;
cin>>a>>b>>c;
int flag = 1;
for(int i=0; i<a.size(); i++)
{
if(c[i]==a[i]||c[i]==b[i]) continue;
flag = 0; break;
}
puts(flag?"YES":"NO");
}
return 0;
}
B. Motarack's Birthday
题意：给一个序列，除了若干-1外全是正数，问把所有-1替换成k后，这个序列的max(abs(a[i+1] - a[i]))的最小值为多少。
思路：其实-1改变后能产生影响的也就是它相邻的非-1的数。我们只需要统计一下和-1相邻的值的最大值和最小值找出来。k为（最大值+最小值）/2是最优的。
view code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#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 pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 4e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };
ll a[maxn];
int main()
{
int kase;
cin>>kase;
while(kase--)
{
ll n = read();
rep(i,1,n) a[i] = read();
ll ma = -1, mi = inf;
a[0] = a[n+1] = -1;
int flag = 0;
rep(i,1,n)
{
if(a[i]!=-1) flag=1;
if(a[i]==-1)
{
if(a[i-1]!=-1)
ma = max(ma, a[i-1]), mi = min(mi, a[i-1]);
if(a[i+1]!=-1)
ma = max(ma, a[i+1]), mi = min(mi, a[i+1]);
}
}
if(!flag) cout<<0<<' '<<0<<'
';
else
{
ll m = max(ma-(ma+mi)/2, (ma+mi)/2 - mi);
rep(i,1,n) if(a[i]==-1) a[i] = (ma+mi)/2;
rep(i,1,n-1)
{
m = max(m, abs(a[i+1] - a[i]));
}
cout<<m<<' '<<(ma+mi)/2<<'
';
}
}
return 0;
}
C. Ayoub's function
题意：定义f(s)为s串在长度1<=l,r<=|s|的满足有一个1的区间个数总和。
思路：容斥定理。 想到要直接通过1统计f(x)会很麻烦。我们可以考虑从0的角度入手。
f(x)区间里面有1就行，那就相当于是全排列 - 全为0的方案数。
考虑有一块长度为l的0串，f(x) = n(n+1)/2 - l(l+1)/2 。我们想要后者越小越好，所以想到把0的块分散开来。
而我们有m个1，可以分开m+1个0，每块有(n-m)/(m+1)个0 。 然后用余下来的0尽量均摊，多出来的贡献是((n-m)/(m+1)+1)*(n-m)/(m+1)。最后用总数减去即可。
view code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#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 pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };
int main()
{
int kase;
cin>>kase;
while(kase--)
{
ll n = read(), m = read();
ll zeros = n - m;
ll len = zeros/(m+1);
ll Left = zeros%(m+1);
ll ans_zeros = ( (len+1)*len/2 ) * (m+1) + Left*(len+1);
ll ans_all = (n+1)*n/2;
cout<<ans_all - ans_zeros<<'
';
}
return 0;
}