2024牛客寒假算法基础集训营3
A.智乃与瞩目狸猫、幸运水母、月宫龙虾
思路:就是一个简单的字符串
#include <bits/stdc++.h>
using namespace std;
void solve(){
string a,b;
cin>>a>>b;
if(a[0]==b[0]||a[0]-'A'+'a'==b[0]||b[0]-'A'+'a'==a[0]){
cout<<"Yes\n";
return;
}
cout<<"No\n";
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
}
B. 智乃的数字手串
思路：我是直接猜的结论
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
vector<int> a(n);
int num1=0,num2=0;
for(int i=0;i<n;i++){
cin>>a[i];
if(a[i]%2==0) a[i]=0,num1++;
else a[i]=1,num2++;//奇数为1，偶数为0
}
if(abs(num1-num2)%2==1){
cout<<"qcjj\n";
}
else{
cout<<"zn\n";
}
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
}
D. chino's bubble sort and maximum subarray sum(easy version)
思路:就是字串之和的最大化，我想了超级久，然后发现写不出来,摆，然后写了B之后直接回来一看范围得出结论:我是sb、、、直接暴力的题想那么多，甚至WA了一发，只想怎么写了，忘了计算k
#include <bits/stdc++.h>
using namespace std;
const int MAX=1e3+10;
#define int long long
int a[MAX];
signed main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i];
}
int m=0,ma=a[0];
for(int i=0;i<n;i++){
m+=a[i];
ma=max(ma,m);
if(m<0){
m=0;
}
}
for(int j=1;j<n;j++){
m=0;
if(j>1) swap(a[j-2],a[j-1]);
swap(a[j-1],a[j]);
/*for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
*/
for(int i=0;i<n;i++){
m+=a[i];
ma=max(ma,m);
if(m<0){
m=0;
}
}
}
cout<<ma<<endl;
}
G.智乃的比较函数(easy version)
思路:题上有一个很明显的东西:不矛盾就是YES,为什么WA：0是带=，忘记了a[x]=a[y]的情况
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
if(n==1){
int x,y,z;
cin>>x>>y>>z;
if(x==y&&z==1){
cout<<"No\n";
return;
}
}else{
int a,b,c,x,y,z;
cin>>a>>b>>c;
cin>>x>>y>>z;
if(c==0&&z==0){
cout<<"Yes\n";
return;
}
//自身矛盾
if(x==y&&z==1){
cout<<"No\n";
return;
}if(a==b&&c==1){
cout<<"No\n";
return;
}
if(x==y||a==b){
cout<<"Yes\n";
return;
}
//完全一样
if(x==a&&y==b&&z!=c){
cout<<"No\n";
return;
}
//相反
if(x!=y&&x==b&&y==a&&z==c){
cout<<"No\n";
return;
}
}
cout<<"Yes\n";
}
signed main()
{
int t;
cin>>t;
while(t--){
solve();
}
}
H.智乃的比较函数(normal version)
思路：还是一样只要不矛盾就是yes，而且这个x只有123，那么我们可以诶个给xyz赋值，最多就27种情况，只要其中有不矛盾的我们就可以直接输出yes
#include <bits/stdc++.h>
using namespace std;
int v[53][3];
int n;
int a[5];
bool check(){
for(int i=0;i<n;i++){
if(v[i][2]==1){
if(a[v[i][0]]<a[v[i][1]]) continue;
else return false;
}else{
if(a[v[i][1]]<=a[v[i][0]]) continue;
else return false;
}
}
return true;
}
void solve()
{
cin>>n;
for(int i=0;i<n;i++){
cin>>v[i][0]>>v[i][1]>>v[i][2];
}
bool res=false;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
for(int k=1;k<=3;k++){
a[1]=i; a[2]=j; a[3]=k;
res=check();
if(res){
cout<<"Yes\n";
return;
}
}
}
}
cout<<"No\n";
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
}
L.智乃的36倍数(easy version)
思路:简单版甚至是1-10，n=1000，n方就行
#include <bits/stdc++.h>
using namespace std;
const int MAX=1100;
char a[MAX];
int main(){
int n;
cin>>n;
if(n==1){
cout<<"0\n";
return 0;
}
int sum=0;
for(int i=0;i<n;i++){
cin>>a[i];
for(int j=0;j<i;j++){
long long int x=(a[j]-'0')*10+(a[i]-'0');
if(x%36==0){
sum++;
}
}
}for(int i=n-1;i>=0;i--){
for(int j=n-1;j>i;j--){
long long int x=(a[j]-'0')*10+(a[i]-'0');
if(x%36==0){
sum++;
}
}
}
cout<<sum<<endl;
}
M. 智乃的36倍数(normal version)
$$
(a+b):mod:n=a:mod:n+b:mod:n
$$
思路：要么就是用上述公式或者找36的性质，在这里我找的是36的性质：36=4*9，如何整除9？所有位数之和是9的倍数；如何整除4？ 后两位是4的倍数
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX=1e5+10;
int a[MAX],p[MAX];//a纯数字，p能否被9除
int cnt[10][11];//前者记录总数mod9的余数，后数记录最后个位数(当b是个位数的时候，只有当这两位数是4的倍数的时候才可以被4整除)
int mod9(int x){
int res=0;
while(x){
res+=x%10;
x/=10;
}
res%=9;
return res;
}
signed main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
p[i]=mod9(a[i]);
cnt[p[i]][a[i]%10]++;
}
int ans=0;
for(int i=1;i<=n;i++){
cnt[p[i]][a[i]%10]--;
if(a[i]/10>0){
if(a[i]%100%4==0){
for(int j=0;j<=9;j++){
ans+=cnt[(9-p[i])%9][j];
}
}//可被100除，就不用考虑各位
}
else{
for(int j=0;j<=9;j++){
if((j*10+a[i])%4==0){//保证能被4整除
ans+=cnt[(9-p[i])%9][j];
}
}
}
cnt[p[i]][a[i]%10]++;
}
cout<<ans<<endl;
}