牛客周赛round64

下面依据(1–10)星级评判本次周赛:

小红的对错判断

题目描述
小红在判题的时候,经常发现选手把”Yes”输出成”YES”或者”yes”,她希望写一个spj(special judge)来判断选手是否输出了”Yes”.你能帮帮她吗?
输入描述:
一个长度不超过3的,仅由小写字母或者大写字母组成.
输出描述:
若字符串可以通过大小写转换变成”Yes”,则输出”accept”.否则输出”wrong answer”.

评价: 1星,无脑签到题,考查字符串,toupper,tolower函数的用法.如果硬用if,6种情况.

---

#include <bits/stdc++.h>
using namespace std;

void func()
{
char crr[3] = {0};
scanf("%s",crr);
for (int i = 0; crr[i]; i++)
{
    crr[i]=toupper(crr[i]);
}
if (crr[0] == 'Y' && crr[1] == 'E' && crr[2] == 'S')
{
    printf("accept");
}
else
{
    printf("wrong answer");
}
}
int main()
{
func();
return 0;
}

---

小红的幂表达

题目描述
小红拿到了一个正整数,请你帮小红将其表示为幂(a^b)的形式.
输入描述:

一个正整数x (2≤x≤10^5)
输出描述:
第一行输出x.
接下来每一行输出一个幂的表达式。
请按指数从小到大的顺序输出。

评价: 2星,高一数学对数函数换底公式.当时没有这么想,直接优化暴力就过了.

---

//实战AC:重点在func1暴力找对数和指数
#include <bits/stdc++.h>
using namespace std;

void func1(int x)
{ 
for (int i = sqrt(x); i > 1; i--)
{
    int j = 1;
    int m = i;
    while (m < x)
    {
        m = m * i;
        j++;
    }
    if (m == x)
    {
        printf("=%d^%d\n", i, j);
    }
}

}
void func()
{
int x;
cin >> x;
cout << x<<endl;
cout <<"="<< x << "^" << "1" << endl;
func1(x);
}

int main()
{
func();
return 0;
}

正规解法(也是暴力遍历,复杂度跟我差不多):
void func1(int x)
{ 
for (int i = sqrt(x); i > 0; i--)
{
    int m = log2(x) / log2(i);
    if (x == pow(i , m))//pow明显增加时间复杂度.
    {
        printf("=%d^%d\n", i, m);
    }
}
}

---

小红的前缀询问

链接:https://ac.nowcoder.com/acm/contest/92662/C

题目大意:

小红拿到了一个数组,她有若干次询问,每次询问一个前缀内有多少对相同的数.你能帮帮她吗?

评价: 4星,从此题起开始上难度,当时map不了解,以后单独开一个系列总结.本题考查map(红黑树),字符串,前缀和.
思路:
只需要记录在每个前缀前相同的数字出现次数,出现多少次ans就需要加多少ans需在上一个前缀的基础上累加数据大小比较大,开数组记录不可行,需要用到map.

---

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int n;
void solve()
{
 cin>>n;
 map<int,int>mp;// 声明一个键和值都是整数的map有点像动态哈希.
 
 ll ans=0;
 
 for(int i=1;i<=n;i++)
 {
 	int x;
 	cin>>x;
 	ans+=mp[x];//记录各个值上的相同对数.
 	cout<<mp[x]<<" ";
 	mp[x]++;
 	cout<<ans<<" ";//依次输出
 } 
 }
int main()
{
solve();

return 0;
}

---

小红和小紫的博弈游戏

链接:https://ac.nowcoder.com/acm/contest/92662/D

题目大意: 2*2矩阵,两人轮流操作,每次操作时选择两个相邻的正整数,使它们同时减1.谁先无法操作谁就输了.
两人都使用最优策略的情况下,谁将获得最终胜利?

评价: 3星,重点考查算法的构建,数学,博弈论,对语法的要求并不高.

思路: 由于是2*2矩阵,根据题意(相邻)反过来找不相邻,假设二维矩阵a[2][2],不相邻为a[0][0],a[1][1]与a[1][0],a[0][1].
将其作为一组,设为(a1,a4),(a2,a3),每一次对一组内的一个数操作,另一组全部减1,所以可分别对二组求和,取其min.
然后min在判断奇偶性.为奇数前者胜,偶数后者.

---

#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

void func()
{
int t;
cin >> t;
int a[2][2] = { 0 };
for (int i = 0; i < t; i++)
{
    for (int j = 0; j < 2; j++)
    {
        for (int k = 0; k < 2; k++)
        {
            cin >> a[j][k];
        }
    }
    int sum1 = a[0][0] + a[1][1];
    int sum2 = a[1][0] + a[0][1];
    int summin = min(sum1, sum2);
    if (summin % 2 == 0)
    {
        printf("yukari\n");
    }
    else
    {
        printf("kou\n");
    }
}
}


int main()
{ 
func();

return 0;
}

---