欢乐赛#34不正经题解!(全站第一首发)

Erika

2024-11-20 00:02:17

发布于：湖南

61阅读

0回复

0点赞

T1.简单
T2.小小模拟
T3.二分……额不管了反正想不起来（
T4.埃氏筛...
T5.P党大喜
T6.升华(感人)

开做

T1:
预计得分：
$200pts$
实际得分：
$200pts$
用时5min
集合的特性(去重)来计算列表中不同元素的数量(这个都知道):

def sanb(a):
    return len(set(a))
a=int(input())
a=list(map(int,input().split()))
b=sanb(a)
print(b)

T2:
预计得分：
$200pts$
实际得分：
$200pts$
用时15min
小模拟(注意输出格式要不然会全WA)：

#include <iostream> 
#include <string>  
int main() { 
    int n; 
    std::string i; 
    std::cin>>n>>i; 
    int x = 0, y = 0; 
    for (char a : i) { 
        switch (a) { 
            case 'D': 
                y--; 
                break; 
            case 'U': 
                y++; 
                break; 
            case 'R': 
                x++; 
                break; 
            case 'L': 
                x--; 
                break; 
        } 
    }  
    std::cout << "(" << x << "," << y << ")" << std::endl; 
     
    return 0; 
}

T3:
预计得分：
$500pts$
实际得分：
$450pts$ (极限)
😭😭😭已老实😭😭😭
二分我恨你

#include <iostream>
#include <algorithm>
using namespace std; 
bool f(long long n, long long m) {
    long long a = m;
    long long b = 2 * m;
    long long c = n - 1 - b;
    if (c > m) return true;
    return false;
} 
int main() {
    long long n;
    cin >> n;
    long long l = 0, r = n / 3;
    long long res = 0;
    while (l <= r) {
        long long m = (l + r) / 2;
        if (f(n, m)) {
            res = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    cout << res - 1 << endl;
    return 0;
}

T4:
预计得分：
$200pts$
实际得分：
$200pts$
不难发现，如果 $n<=2$ ，直接返回0就行，因为小于等于2的质数个数为0
先弄一个长度为 $n+1$ 的布尔数组 $s$ ，初始值全为True，表示所有数都假设为质数
然后将 $s[0]$ 和 $s[1]$ 设为False，因为0和1不是质数
然后埃氏筛
从2开始遍历到 $sqrt(n)$ 就行，要不然会TLE
如果 $s[i]$ 为True，则 $i$ 是质数，就将 $i$ 的倍数(从 $i^2$ 开始)标记为False
代码如下:

def s(n):
    if n <= 2:
        return 0
    s=[True]*(n+1)
    s[0]=s[1]=False
    for i in range(2, int(n**0.5)+1):
        if s[i]:
            s[i*i:n+1:i]=[False]*len(s[i*i:n+1:i])
    return sum(s) 
n=int(input())
print(s(n))

T5:
预计得分：
$300pts$
实际得分：
$300pts$
(~~P党最可以装的一集~~)不难想到，可以用collections.Counter库来统计字符串中每个字符的出现次数，然后比较两个Counter对象是否相等
如果两个字符串的字符计数相同，返回True；否则返回False
(对于每个测试用例，读取两个字符串str1和str2，并判断它们是否字符数量平衡)
最后遍历list并输出
tips:这里故意降低code可读性所以头加了as C(~~懒的打Counter了~~)(bushi

from collections import Counter as C  
def f(s1, s2):
    return C(s1) == C(s2)
def main():
    import sys 
    i=sys.stdin.read  
    d=i().split()
    x=0 
    t=int(d[x])
    x+=1 
    r=[]
    for _ in range(t):
        x+=1 
        s1=d[x]
        x+=1 
        s2=d[x]
        x+=1 
        r.append('YES'  if f(s1, s2) else 'NO')
    for o in r:
        print(o) 
if __name__ == "__main__":
    main()