A - Three Strings

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 +7;
const ll MAXN = 1e6 + 5;

void solve(){
	string a,b,c;
	cin>>a>>b>>c;
	int len=a.size();
	bool flag=true;
	for(int i=0;i<len;i++){
		if(a[i]==c[i] || b[i]==c[i]){
			continue;
		}else{
			flag=false;
		}
	}
	if(flag) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

B. Motarack’s Birthday
题意：
有T组样例
每组第一行输入一个n
第二行有n个数
其中-1的地方可以用k来替换
要求输出相邻两个数的差的最大值和k并使得相邻之差最小。
思路：
贪心
记录-1的两侧非-1的数的最大值，两个数的和除以2就是满足条件的k，然后填上所求k并遍历求两个数的差的最大值。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;

ll a[maxn];

void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ll ans=0,L=1e18,R=0;
    a[0]=a[n+1]=-1;
    for(int i=1;i<=n;i++){
        if(a[i]==-1){
            if(a[i-1]!=-1){
                L=min(L,a[i-1]);
                R=max(R,a[i-1]);
            }
            if(a[i+1]!=-1){
                L=min(L,a[i+1]);
                R=max(R,a[i+1]);
            }
        }
    }
    ll p=(L+R)/2;
    for(int i=1;i<=n;i++){
        if(a[i]==-1) a[i]=p;
    }
    ll res=0;
    for(int i=1;i<n;i++){
        res=max(res,abs(a[i+1]-a[i]));
    }
    if(p>1e9) p=10;
    cout<<res<<" "<<p<<endl;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

C - Ayoub’s function
题意：
T组样例
每组输入两个数n,m。
由n长的01串中的1的个数是m，求含有1的子串有多少种。L和R不相同即视为不同种。
思路：
正难则反+数学+贪心
求只含有0的子串最少有多少个。
显然n长最多能分为(m+1）段。每个区间至少有u个，有v个区间有u+1个，总的减去最少所含0的子串的数量即为答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 +7;
const ll MAXN = 1e6 + 5;

void solve(){
	ll n,m;
	cin>>n>>m;
	ll x=m+1;//分成(m+1)个区间
	ll y=n-m;//0的数量
	ll u=y/x;//每个区间有至少u个 
    ll v=y%x;//v个区间有u+1个 
    ll res=n*(n+1)/2-u*(u+1)*(x-v)/2-(u+1)*(u+2)*v/2;
    cout<<res<<endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T; cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

D - Time to Run
题意：
给你一个n*m的矩阵，每个方格都连通且为双向边，求房间内走k步能否走，如果能走该怎么走。
思路：
构造+特判+贪心
利用贪心思想构造一个能全部走完的方案并记录，如果k比全部走完还打就输出no，否则输出方案。
需要利用到vector<pair<int,string> >V,ans不得不说stl是真的强！vector里放pair也太酷了，虽然写个struct也可以利用数组应该也是可以实现的。
pair<first,second>

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 +7;
const ll MAXN = 1e6 + 5;

ll n,m,k;
vector<pair<int,string> >V,ans;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>k;
	for(int i=0;i<n-1;i++){
		if(m!=1){
			V.push_back({m-1,"R"});
			V.push_back({m-1,"L"});
		}
		V.push_back({1,"D"});
	}
	if(m!=1){
		V.push_back({m-1,"R"});
	}
	for(int i=0;i<m-1;i++){
		if(n!=1){
			V.push_back({n-1,"U"});
			V.push_back({n-1,"D"});
		}
		V.push_back({1,"L"});
	}
	if(n!=1){
		V.push_back({n-1,"U"});
	}
	for(int i=0;i<V.size();i++){
		if(k>=V[i].first){
			k-=V[i].first;
			ans.push_back(V[i]);
		}else if(k!=0 && V[i].first>k){
			ans.push_back({k,V[i].second});
			k=0;
		}
	}
	if(k>0){
		cout<<"NO\n";
	}else{
		cout<<"YES\n";
		cout<<ans.size()<<endl;
		for(int i=0;i<ans.size();i++){
			cout<<ans[i].first<<" "<<ans[i].second<<endl;
		}
	}
	return 0;
}