Educational Codeforces Round 143 (Rated for Div. 2)（A，C,D)
好久没有写题了，这次\(vp\)竟然连\(vs\)都不会用了，O(∩_∩)O
A
这个也是差一点了，还有一个情况我的解法是没有输出的，果然手生了，题目还蛮好理解的
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
int t,n,m;
string s,ss;
map<char,int>is;
void solve()
{
cin>>n>>m;
cin>>s>>ss;
reverse(ss.begin(),ss.end());
s=s+ss;
int len=s.size();
for (int i=1;i<len;i++)
{
if (s[i]!=s[i-1]) continue;
for (int j=i+1;j<len;j++)
{
if (s[j]==s[j-1])
{
cout<<"NO\n";
return ;
}
}
cout<<"YES\n";
return ;
}
cout<<"YES\n";//这个一开始没有写，大意了
return ;
}
int main ()
{
cin>>t;
is['R']=1;
is['B']=0;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
C
由于第一道题花了太多的时间，让本来不聪明的我雪上加霜，不过大致的框架什么的已经出来了
这个题大意就是有\(n\)杯茶，还有\(n\)个人，每个人最多可以喝\(b^i\)毫升茶，杯子里有\(a^i\)毫升茶，然后每一个在喝了\(i\)杯茶后，又会再去和\(i-1\)杯茶，每个人喝的时间是一样的，大致就是在第一轮是，每一个\(i\)都在喝第\(i\)杯茶，在第二轮是，每一个\(i\)都在喝第\(i-1\)杯茶，问我们每个人可以喝到多少毫升茶
考虑到\(n\)比较大，所以我们不可以一个一个暴力
然后我就想到了对于每一杯茶，如果不考虑那个人喝不喝得到，对于第\(i\)杯茶，\(i,i+1,i+3.......n\)这些人都可以喝到这个杯子里面的茶
然后我们就可以考虑到从\(i\)到\(len\)这一个部分的人都是可以喝到自己的最大量\(b^j\)，然后后面还可能会有一个人喝不满，那么我们就让那个人喝下最后剩下的
但是呢，每一个人的\(b\)都不一样，一个一个加是不现实的，所以我们只需要统计每个人喝足量的数量，然后我们还需要开一个数组，是那个人没有喝到足量的茶的时候的喝的量
对于每一杯茶，喝足量的人每次都是连续的，所以我们可以用到差分前缀的思想
当然我们还需要利用二分来寻找\(len\)的位置
还要注意使用\(vector\)的\(upper bound\)时\(vector\)里面的每一个都要有一个具体的数，并且是有序的，比如这个我把\(vecor\)开到了\(n+10\)的空间，但是里面最后只有\(n\)个数，所以就用不了，所以这一点要注意
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
const int maxn=2e5+10;
int t,n,k;
vector<int>a,b,ans,x;
//int sum[maxn];
vector<int>sum;
void solve()
{
cin>>n;
x=ans=a=b=vector<int>(n+10,0);
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
sum=vector<int>(n+1);
sum[0]=0;
for (int i=1;i<=n;i++)
{
cin>>b[i];
sum[i]=sum[i-1]+b[i];
}
for (int i=1;i<=n;i++)
{
int now=a[i]+sum[i-1];
int len=upper_bound(sum.begin(),sum.end(),now)-sum.begin();
// cout<<now<<" ";
// cout<<len<<" "<<sum[len]<<" \n";
if (sum[len]>=now&&len>=i)
{
if (len==i)
{
x[i]+=a[i];
}
else
{
ans[i]++;
ans[len]--;
x[len]+=min(b[len],now-sum[len-1]);
}
}
else
{
ans[i]++;
ans[n+1]--;
}
}
for (int i=1;i<=n;i++)
{
ans[i]=ans[i-1]+ans[i];
}
for (int i=1;i<=n;i++)
{
ans[i]*=b[i];
ans[i]+=x[i];
cout<<ans[i]<<" ";
}
cout<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
D
这个题大意就是有\(n\)个点，每三个点可以构成一个三角形，然后我们需要把这个三角形染色，总共有两种颜色，但是有一个要求就是这三个点必须染色必须有两个相同的，一个不同的，并且，最后两种颜色染色的点的数量都一样。
然后对于两个不同色的点之间的权值我们会加到\(W\)里面，（\(W\)是所以可得的权值之和的最大的那一个条件），问得到这个\(w\)可以有多少种方案
对于这些条件，我们知道每一个三角形都一定会有两个边是可以选择的，所以在不考虑颜色的情况下，三点之间的选择也有不同的数量
如果三个点都是一样的，那么会有\(3\)种选择，这个情况有\(cnt1\)个
如果最大点只有一个，次大点有两个，除了最大的那个点是确定的，次大点有两个选择，即会有\(2\)种选择，有\(cnt2\)个
那个这个分配方案个数为\(3^cnt1 * 2^cnt1\)
然后我们考虑颜色的分配，例如，对于一个三角形的颜色是\(a,a,b\),那么另外一个三角形一定是\(b,b,a\)，所以总共有\(n/6\)个选择，总共有\(n/3\)个三角形，所以这就是一个组合数\(\begin{pmatrix}n/6 \\ n/3\\ \end{pmatrix}\)
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
#define int long long
int mod=998244353;
int t,n,w[maxn];
int f[maxn],invf[maxn];
int ksm(int x,int p)
{
int res=1;
while (p)
{
if (p&1)
{
res=(res*x)%mod;
}
x=(x*x)%mod;
p>>=1;
}
return res%mod;
}
void init(int mx)
{
f[0]=f[1]=1;
for (int i=2;i<=mx;i++)
{
f[i]=f[i-1]*i%mod;
}
invf[mx]=ksm(f[mx],mod-2);
for (int i=mx-1;i>=0;i--)
{
invf[i]=1ll*invf[i+1]*(i+1ll)%mod;
}
return ;
}
int C(int n,int m)
{
if (n==m&&m==-1) return 1;
if (n<0||m<0) return 0;
return f[n]*invf[n-m]%mod*invf[m]%mod;
}
void solve()
{
cin>>n;
init(n/3+6);
int cnt1=0,cnt2=0;
for (int i=1;i<=n/3;i++)
{
for (int j=1;j<=3;j++)
{
cin>>w[j];
}
if (w[1]==w[2]&&w[2]==w[3])
{
cnt1++;
}
else
{
sort(w+1,w+4);
if (w[2]==w[1]) cnt2++;
}
}
//cout<<cnt1<<" "<<cnt2<<" ";
int ans=ksm(3,cnt1)*ksm(2,cnt2)%mod;
//cout<<ans<<" ";
//cout<<C(n/3,n/6)<<" ";
ans=(ans*C(n/3,n/6))%mod;
cout<<ans<<'\n';
return ;
}
signed main ()
{
t=1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}