A
这个题目其实乍一看还比较麻烦，其实很简单。其实像这种题目我们只需要构造出来一个最基本的需要操作的情况，然后可以往这种操作最多可以进行多少次这个方向来思考问题。
很显然这个遇到那种需要操作的序列最多操作一次。
// Problem: A. Two Towers
// Contest: Codeforces - Educational Codeforces Round 143 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1795/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
void solve()
{
int n,m;
cin>>n>>m;
string a,b;
cin>>a>>b;
int flag=0;
if(a[a.size()-1]==b[b.size()-1])
{
flag=1;
}
/*for(int i=0;i<n;i++)
{
}*/
int cnt1=0;
int cnt2=0;
for(int i=0;i<n-1;i++)
{
if(a[i]==a[i+1])
{
cnt1++;
}
}
for(int i=0;i<m-1;i++)
{
if(b[i]==b[i+1])
{
cnt2++;
}
}
/* if((n==1&&cnt2>=1)||(m==1&&cnt1>=1))
{
cout<<"NO"<<endl;
return;
}*/
if(cnt1+cnt2>1||((cnt1+cnt2==1)&&flag))
{
cout<<"NO"<<endl;
return;
}
cout<<"YES"<<endl;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
B
核心思路·
这个因为需要我们唯一确定一个点，但是我们每次删去的必须得是线段。所以那个点一定是个端点，然后在推导出来一个性质就好了。也就是我们最后如果只留下两条线段，那么这又会有一个什么样的性质。
我们发现线段必须得一个左端点是x，另外一个右端点是x。左边的都是或者右边的都是x的话也是不满足性质的。
// Problem: B. Ideal Point
// Contest: Codeforces - Educational Codeforces Round 143 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1795/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 n,x;
cin>>n>>x;
int fl=0,fr=0;
while(n--)
{
int l,r;
cin>>l>>r;
if(l==x)
fl=1;
if(r==x)
fr=1;
}
if(fr&&fl)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
C
核心思路
这个题目我觉得是要比D难的。因为需要考虑的边界很麻烦，又是差分又是前缀和的。
首先直接模拟下这个操作就是：我们可以往顶部往下面看，因为最顶部的茶可以被从顶部到底部的人品尝，当然前提是量比较足。
所以我们可以看当前的茶可以最多可以被多少人喝，因此首先可以预处理出来这个前缀和。然后我们发现如果是可以被\(1\sim 3个喝，那么对于他们来说都是要累加下b[i]的。因此预处理出来差分数组就是第二个优化。\)然后可以被多少人喝我们可以采用二分出来那个小于\(a[i]\)的边界点。
但是一定要注意的有可能1 7 5这种情况，所以我们还得加一个特判，也就是没有这么多茶够喝的情况。
于是大题思路就是二分加前缀和再加差分。
// Problem: A. Yet Another Promotion
// Contest: Codeforces - Codeforces Round #852 (Div. 2)
// URL: https://codeforces.com/contest/1793/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 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;
vector<int> a(n+1),b(n+1),s(n+1),d(n+1);
vector<long long> ans(n+1);
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
cin>>b[i];
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]+b[i];
}
auto erfen=[&](int x,int start){
int l=1,r=n;
while(l<r)
{
int mid=l+r+1>>1;
if((s[mid]-s[start-1])<=x)
{
l=mid;
}
else
{
r=mid-1;
}
}
return r;
};
for(int i=1;i<=n;i++)
{
int j=erfen(a[i],i);
//int j=std::lower_bound(a.begin(),a.end(),a[i]+s[i])-a.begin();
//cout<<j<<endl;
if(s[j]-s[i-1]<=a[i])
{
if(j<n)
{
d[j+1]--;
d[i]++;
ans[j+1]+=a[i]-(s[j]-s[i-1]);
}
else if(j==n)
{
d[i]++;
}
}
else
{
ans[j]+=a[i];
}
}
for(int i=1;i<=n;i++)
{
d[i]+=d[i-1];
}
for(int i=1;i<=n;i++)
{
ans[i]+=d[i]*b[i];
}
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
cout<<endl;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
D
核心思路
老样子，构造下最基本的样例找规律。所以对于一个普通的三元环，最好的上色的方法就是红红蓝或者蓝蓝红。然后对于一个三元环怎么去上色就和那个边权有关。
再就是题目还有一个约束条件：需要红和蓝各上色一半。也就是一个红红蓝必须得搭配一个蓝蓝红。但是我们要注意的是在上面我们已经对每一个三元环上好色了。所以接下来的问题就是怎么去选而已。这个就是排列组合把:\(C_{n/3}^{n/6}\).
// Problem: D. Triangle Coloring
// Contest: Codeforces - Educational Codeforces Round 143 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1795/problem/D
// Memory Limit: 512 MB
// Time Limit: 3000 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=3e5+10;
const int mod=998244353;
int fac[N],infac[N];
int qmi(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
void Init()
{
fac[0]=1;
infac[0]=1;
for(int i=1;i<N;i++)
{
fac[i]=fac[i-1]*i%mod;
infac[i]=infac[i-1]*qmi(i,mod-2)%mod;
}
}
int C(int a,int b)
{
return fac[a]*infac[b]%mod*infac[a-b]%mod;
}
void solve()
{
int n;
cin>>n;
int ans=1;
for(int i=1;i<=n;i+=3)
{
int w1,w2,w3;
cin>>w1>>w2>>w3;
vector<int> e={w1,w2,w3};
int mx=0;
for(int i=0;i<3;i++)
{
for(int j=i+1;j<3;j++)
{
mx=max(mx,e[i]+e[j]);
}
}
int cnt=0;
for(int i=0;i<3;i++)
{
for(int j=i+1;j<3;j++)
{
cnt+=(mx==(e[i]+e[j]));
}
}
ans=(ans*cnt)%mod;
}
cout<<(ans*C(n/3,n/6)%mod)<<endl;
}
signed main()
{
Init();
int T;
T=1;
while(T--)
{
solve();
}
}