B - Build Tree
题意:一个满二叉树，给定k个数，选sum（结点）个数。求每个点到根节点的距离之和，要求尽可能的使得“和”较小。
求这个较小的和。
思路：先排序，对每个点dp一遍到树根的距离，求一个和就完事。
排序的依据是，因为是满n叉树，同一层的点都是满的，那么之前的每条边都会对和有贡献，那么只能从选择数时选较小的数来实现贪心，使得每一步对和的贡献较小。
#include <iostream>
#include <cstring>
#include <algorithm>
const int N=2e5+10;
typedef long long LL;
LL a[N];
LL b[N];
LL k,m,n,p;
using namespace std;
int main()
{
while(cin>>k>>m>>n>>p)
{
memset(b,0,sizeof b);
for(int i=1;i<=k;i++) scanf("%lld",&a[i]);
sort(a+1,a+1+k);
LL cnt=1;
LL sum=0;
m--;
if(m)//如果m=0此时代表没有结点，距离为0
for(int i=1;i<=n;i++) b[i]=a[i]%p;
while (m -- )//递推出一共有多少结点，不需要快速幂
{
cnt*=n;
sum+=cnt;
}
for(int i=n+1;i<=sum;i++)//简单的dp一下
{
b[i]=(b[(i-1)/n]%p+a[i]%p)%p;
}
LL res=0;
for(int i=1;i<=sum;i++)//求个和
{
res=(res%p+b[i]%p)%p;
}
cout<<res<<endl;
}
}
E - Hello XTCPC H
题意：给定字符串，求其中“xtCpc”的个数，选择不可重复。
思路：贪心枚举出合法方案。a[x]指的是按题意要求的顺序，到x这个字符的最多合法方案。最后a[4]就是所有的以c结尾的按题意要求顺序的合法方案。
K - SSY and JLBD
思路：无脑模拟
#include <iostream>
#include <cstring>
#include <algorithm>
const int N=2e5+10;
int a[10];
using namespace std;
int main()
{ int n;
while(cin>>n)
{
memset(a,0,sizeof a);
string st;
cin>>st;
for(int i=0;i<st.size();i++)
{
if(st[i]=='x') a[0]++;
else if(st[i]=='t'&&a[0]) a[0]--,a[1]++;
else if(st[i]=='C'&&a[1]) a[1]--,a[2]++;
else if(st[i]=='p'&&a[2]) a[2]--,a[3]++;
else if(st[i]=='c'&&a[3]) a[3]--,a[4]++;
}
cout<<a[4]<<endl;
}
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include<map>
typedef long long LL;
const int N = 2e6+10;
int a[N];
char b[N];
using namespace std;
int main()
{
for(int i=1;i<=14;i++)
{
string st;
cin>>st;
if(st[1]=='w'||st[1]=='s'||st[1]=='p')
{
a[i]=st[0]-'0';
b[i]=st[1];
}
else
{
if(st[0]!='b')
{
a[i]=0;
b[i]=st[0];
}
else//e-bei||a-bai
{
a[i]=0;
b[i]=st[1];
}
}
}
int flag=1;
for(int i=2;i<=14;i++)
{
if(b[i]!=b[i-1]) flag=0;
}
if(flag)
{
int cnt1=0,cnt2=0,cnt3=0,cnt4=0,cnt5=0,cnt6=0,cnt7=0,cnt8=0,cnt9=0;
for(int i=1;i<=14;i++)
{
if(a[i]==1) cnt1++;
else if(a[i]==2) cnt2++;
else if(a[i]==3) cnt3++;
else if(a[i]==4) cnt4++;
else if(a[i]==5) cnt5++;
else if(a[i]==6) cnt6++;
else if(a[i]==7) cnt7++;
else if(a[i]==8) cnt8++;
else if(a[i]==9) cnt9++;
}
int ct=0;//大于等于2的数量
if(cnt2>=2) ct++;
if(cnt3>=2) ct++;
if(cnt4>=2) ct++;
if(cnt5>=2) ct++;
if(cnt6>=2) ct++;
if(cnt7>=2) ct++;
if(cnt8>=2) ct++;
if(cnt1<3||cnt9<3) {cout<<"I dont know!"<<endl;return 0;}
if(ct>1) {cout<<"I dont know!"<<endl;return 0;}
if(cnt1==4&&cnt9==3&&ct==0) {cout<<"jiulianbaodeng!"<<endl;return 0;}
else if(cnt1==3&&cnt9==4&&ct==0) {cout<<"jiulianbaodeng!"<<endl;return 0;}
else if(cnt1==3&&cnt9==3&&ct==1) {cout<<"jiulianbaodeng!"<<endl;return 0;}
else {cout<<"I dont know!"<<endl;return 0;}
}
else
{
int ct1=0,ct2=0,ct3=0;int ct4=0,ct5=0,ct6=0;
for(int i=1;i<=14;i++)
{
if(a[i]==1&&b[i]=='w') ct1++;
else if(a[i]==1&&b[i]=='s') ct2++;
else if(a[i]==1&&b[i]=='p') ct3++;
else if(a[i]==9&&b[i]=='w') ct4++;
else if(a[i]==9&&b[i]=='s') ct5++;
else if(a[i]==9&&b[i]=='p') ct6++;
}
int num_1=ct1+ct2+ct3;int num_9=ct4+ct5+ct6;
if(ct1&&ct2&&ct3&&ct4&&ct5&&ct6)
{
int t1=0,t2=0,t3=0,t4=0,t5=0,t6=0,t7=0;
for(int i=1;i<=14;i++)
{
if(a[i]==0&&b[i]=='d') t1++;
if(a[i]==0&&b[i]=='n') t2++;
if(a[i]==0&&b[i]=='x') t3++;
if(a[i]==0&&b[i]=='e') t4++;
if(a[i]==0&&b[i]=='z') t5++;
if(a[i]==0&&b[i]=='f') t6++;
if(a[i]==0&&b[i]=='a') t7++;
}
if(num_1==3&&num_9==3&&t1&&t2&&t3&&t4&&t5&&t6&&t7)
{
if(t1+t2+t3+t4+t5+t6+t7==8) {cout<<"shisanyao!"<<endl;return 0;}
else {cout<<"I dont know!"<<endl;return 0;}
}
else if(num_1==4&&num_9==3&&t1&&t2&&t3&&t4&&t5&&t6&&t7)
{
cout<<"shisanyao!"<<endl;return 0;
}
else if(num_1==3&&num_9==4&&t1&&t2&&t3&&t4&&t5&&t6&&t7)
{
cout<<"shisanyao!"<<endl;return 0;
}
else {cout<<"I dont know!"<<endl;return 0;}
}
else {cout<<"I dont know!"<<endl;return 0;}
}
}
L - Can you raed it croretcly?
签到题直接模拟。
#include <iostream>
#include <cstring>
#include <algorithm>
#include<map>
typedef long long LL;
const int N = 50;
using namespace std;
int main()
{
string st1,st2;
while(cin>>st1>>st2)
{
map<char ,int> mp1;
map<char ,int> mp2;
int flag=1;
if(st1==st2) cout<<"Equal"<<endl;
else if(st1[0]==st2[0]&&st1[st1.size()-1]==st2[st2.size()-1])
{
for(int i=0;i<st1.size();i++)
{
mp1[st1[i]]++;
}
for(int i=0;i<st2.size();i++)
{
mp2[st2[i]]++;
}
for(int i=0;i<26;i++)
{
if(mp1['a'+i]!=mp2['a'+i]) flag=0;
}
if(flag==1) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
else cout<<"No"<<endl;
}
}