A

不会

B

不会

C

因为 n = 8 所以我直接选择了暴力
先排个序然后观察对于 i 来说往前往后最多能有几个会被传染记录一下最大最小值就行了

#include <bits/stdc++.h>
#define pb emplace_back
#define xx first
#define yy second
#define in(x) scanf("%d",&x)
#define lin(x) scanf("%lld",&x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e6+10;
const int M = N*2;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
const double PI = acos(-1);
ll qpow(ll a,ll b){ll res = 1;while(b){if(b&1)  res = res*a%MOD;a = a*a%MOD;b >>= 1;}return res;}
int n,m,k;
int A[N],B[N];
char str[N];
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    int T = 1;  in(T);
    while(T--){
        in(n);
        for(int i = 1;i <= n;i++)
            in(A[i]);
        sort(A+1,A+n+1);
        int mn = n,mx = 0;
        for(int i = 1;i <= n;i++){
            int cnt = 0,base = A[i];
            for(int j = i-1;j >= 1;j--){
                if(base - A[j] <= 2)    cnt++,base = A[j];
                else    break;
            }
            base = A[i];
            for(int j = i+1;j <= n;j++){
                if(A[j] - base <= 2)    cnt++,base = A[j];
                else    break;
            }
            cnt++;
            mn = min(mn,cnt),mx = max(mx,cnt);
        }
        cout << mn << ' ' << mx << endl;
    }
    return 0;
}

D

挺简单的一道题
首先如果斜着走比直着走两次要优那么肯定是斜着走反之就直接直着走
第一种情况下斜着走完了。肯定会剩下一段大直道现在考虑是斜向上再斜向下走还是直接向右走两步好所以比较下 x 和 y 就行但要注意如果要斜着走必须满足 min(n,m) > 1

#include <bits/stdc++.h>
#define pb emplace_back
#define xx first
#define yy second
#define in(x) scanf("%d",&x)
#define lin(x) scanf("%lld",&x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e6+10;
const int M = N*2;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
const double PI = acos(-1);
ll qpow(ll a,ll b){ll res = 1;while(b){if(b&1)  res = res*a%MOD;a = a*a%MOD;b >>= 1;}return res;}
int n,m,k;
int A[N];
char str[N];
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    int T = 1;  in(T);
    ll x,y;
    while(T--){
        scanf("%d %d %lld %lld",&n,&m,&x,&y);
        if(n > m)   swap(n,m);
        ll ans = 0;
        if(2*x >= y){   // 斜着走更好
            if(n == 1){
                ans += x * (m-1);
            }else{    // 斜向上 再 斜向下
                ans += y * (n-1);
                m -= n;
                if(x >= y){    // 斜着走更好
                    ans += y * (m/2*2);
                    if(m&1) ans += x;    // 最后一步直着走
                } else  ans += x * m;
            }
        }else{
            ans = x * (n + m - 2);
        }
        cout << ans << endl;
    }
    return 0;
}

E

答案很快就能想到是

for i in range(1, t - 3):
    boys = t - i
    girls = i
    ans += C(n, boys) * C(m, girls)

但由于数据过大所以需要用~~高精度~~python

N = 35
fact = []


def init():
    fact.append(1)
    fact.append(1)
    for i in range(2, N):
        fact.append(fact[i - 1] * i)


def C(a, b):
    if b > a:
        return 0
    return fact[a] // (fact[b] * fact[a - b])


if __name__ == '__main__':
    init()
    str = input()
    n = int(str.split()[0])
    m = int(str.split()[1])
    t = int(str.split()[2])

    ans = 0
    if n < 4 or m < 1:
        print(0)
    else:
        for i in range(1, t - 3):
            b = t - i
            ans += C(n, b) * C(m, i)
        print(ans)

F

阅读理解
只要除第一个字母外出现了小写字母就不反转

#include <bits/stdc++.h>
#define pb emplace_back
#define xx first
#define yy second
#define in(x) scanf("%d",&x)
#define lin(x) scanf("%lld",&x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e6+10;
const int M = N*2;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
const double PI = acos(-1);
ll qpow(ll a,ll b){ll res = 1;while(b){if(b&1)  res = res*a%MOD;a = a*a%MOD;b >>= 1;}return res;}
int n,m,k;
int A[N];
char str[N];
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    int T = 1;
    while(T--){
        scanf("%s",str);
        n = strlen(str);
        bool flag = 1;
        for(int i = 1;i < n;i++){
            if(str[i] >= 'a')   flag = 0;
        }
        if(flag){
            for(int i = 0;i < n;i++){
                if(str[i] >= 'a')   printf("%c",str[i]-('a'-'A'));
                else    printf("%c",str[i]+('a'-'A'));
            }
        }else{
            for(int i = 0;i < n;i++)    printf("%c",str[i]);
        }

    }
    return 0;
}

G

方法一：判断字符串长度
方法二：python

n = eval(input())

if n<= 127:
    print("byte")
elif n<=32767:
    print("short")
elif n <= 2147483647:
    print("int")
elif n<=9223372036854775807:
    print("long")
else:
    print("BigInteger")

H

不会

I

挺简单的一道线段树队友写的

#define xx first
#define yy second
#include <bits/stdc++.h>
#define in(x) scanf("%d", &x)
#define lin(x) scanf("%lld", &(x))
#define rep(i, x, y) for(auto i = (x); i <= (y); i ++ )
#define dep(i, x, y) for(auto i = (x); i >= (y); i -- )
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 300010;
const int INF = 0x3f3f3f3f;
const int mo = 1e9 + 7;
struct Node{
    int l, r;
    int w;
}node[N<<2];
int a[N];
int b;
void pushUp(int rt) {
    node[rt].w = node[rt<<1].w + node[rt<<1|1].w;
}
void build(int rt, int l, int r) {
    node[rt] = {l, r};
    if(l == r) {
        return;
    }
    int mid = l + r >> 1;
    build(rt<<1, l, mid);
    build(rt<<1|1, mid + 1, r);
}

void add(int rt, int id, int num) {
    if(node[rt].l == node[rt].r) {
        node[rt].w = num;
        return;
    }
    int mid = node[rt].l + node[rt].r >> 1;
    if(id <= mid) {
        add(rt << 1, id, num);
    } else {
        add((rt << 1)|1, id, num);
    }
    pushUp(rt);
}
int query(int rt, int ql, int qr) {
    int l = node[rt].l, r = node[rt].r;
    if(ql <= l && qr >= r) return node[rt].w;
    int mid = l + r >> 1, sum = 0;
    if(ql <= mid) sum = query(rt << 1, ql, qr);
    if(qr > mid) sum += query((rt << 1)|1, ql, qr);
    return sum;
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("data/1.in", "r", stdin);
    #endif
    int m, q; in(m), in(q);
    
    build(1, 1, m);
    int idx = 0, last = 0;
    rep(i, 1, m) {
        in(a[i]);
    }

    a[0] = 0, a[m + 1] = INF;
    rep(i, 1, m) {
        if(a[i] <= a[i + 1] && a[i] >= a[i - 1]) {
            add(1, ++idx, 0);
        } else {
            add(1, ++ idx, 1);
        }
    }

    rep(i, 1, q) {
        int opt, x, y;
        in(opt), in(x), in(y);
        if(opt == 1) {
            a[x] = y;
            rep(j, x - 1, x + 1) {
                if(j < 1 || j > m) continue;
                if(a[j] <= a[j + 1] && a[j] >= a[j - 1]) {
                    add(1, j, 0);
                } else {
                    add(1, j, 1);
                }
            }
            
        } else {
            if(x == y) puts("Yes");
            else if(x + 1 == y) {
                if(a[x] <= a[y]) {
                    puts("Yes");
                } else {
                    puts("No");
                }
            } else if(query(1, x + 1, y - 1) == 0) {
                puts("Yes");
            } else {
                puts("No");
            }
            
        }
        
    }
    return 0;
}

J

很明显可以看出第n+1列上的棋子个数跟第1列的棋子个数是一样的所以我们可以得到两个式子: $\sum_{i = 0}^{n-1}a_{i} = k$ 和 $ans = \prod_{i=0}^{m-1}C_{n}^{a_{i\%n}}$

#include <bits/stdc++.h>
#define pb emplace_back
#define xx first
#define yy second
#define int ll
#define in(x) scanf("%lld",&x)
#define lin(x) scanf("%lld",&x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 100+10;
const int M = N*2;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
const double PI = acos(-1);
ll qpow(ll a,ll b){ll res = 1;while(b){if(b&1)  res = res*a%MOD;a = a*a%MOD;b >>= 1;}return res;}
int inv(int x){
    return qpow(x,MOD-2);
}
int n,m,k;
int A[N],C[N],times[N],ans[N][2];
int dp[N][N*N];
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    int T = 1;
    while(T--){
        in(n),in(m),in(k);
        C[0] = 1;   // C(n,0)
        for(int i = 1;i <= n;i++){
            C[i] = C[i-1] * (n + 1 - i) % MOD * inv(i) % MOD;
        }

        for(int i = 0;i <= n;i++){  // ai的出现次数
            if(m % n >= i)  times[i] = m/n+1;
            else    times[i] = m/n;
        }
        dp[0][0] = 1;
        for(int i = 0;i <= n;i++){  // 贡献
            ans[i][1] = qpow(C[i],m/n+1);
            ans[i][0] = qpow(C[i],m/n);
        }

        for(int i = 1;i <= n;i++){
            for(int j = 0;j <= k;j++){
                for(int t = 0;t <= min(j,n);t++){
                    dp[i][j] = (dp[i][j] + dp[i-1][j-t] * ans[t][times[i] == (m/n+1)] % MOD) % MOD;
                }
            }
        }
        cout << dp[n][k] << endl;
    }
    return 0;
}

K

不会

L

签到题
输出 min(x,18)就行

M

挺裸的一道拓扑排序题

#include <bits/stdc++.h>
#define pb emplace_back
#define xx first
#define yy second
#define in(x) scanf("%d",&x)
#define lin(x) scanf("%lld",&x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 500+10;
const int M = N<<1;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
const double PI = acos(-1);
ll qpow(ll a,ll b){ll res = 1;while(b){if(b&1)  res = res*a%MOD;a = a*a%MOD;b >>= 1;}return res;}
int n,m,k;
bool st[N];
int ind[N],out[N];
int h[N],ne[M],e[M],idx;
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
    ind[b]++,out[a]++;
}
int q[M];
int hh = 0,tt = 0;
void topsort(){
    for(int i = '0';i <= 'z';i++)
        if(st[i] && !ind[i])  q[tt++] = i;

    while(hh != tt){
        int t = q[hh++];
        char ch = t;
        for(int i = h[t]; ~i;i = ne[i]){
            int j = e[i];
            ch = j;
            ind[j]--;
            if(!ind[j])  q[tt++] = j;
        }
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    int T = 1;
    while(T--){
        memset(h,-1,sizeof h);
        in(n);
        char str[5];
        int a,b,c;
        for(int i = 1;i <= n;i++){
            scanf("%s",str);
            b = str[0],a = str[2],c = str[3];
            add(a,b),add(b,c);
            st[a] = st[b] = st[c] = 1;
        }
        int cnt = 0;
        for(int i = '0';i <= 'z';i++){
            if(st[i])   cnt++;
        }
        topsort();
        if(tt == cnt){
            for(int i = 0;i < tt;i++){
                char tp = q[i];
                printf("%c",tp);
            }
        } else  puts("No Answer");
    }
    return 0;
}

2021辽宁省大学生程序设计竞赛题解

2021辽宁省大学生程序设计竞赛题解

A

B

C

D

E

F

G

H

I

J

K

L

M

推荐阅读更多精彩内容

2021辽宁省大学生程序设计竞赛 题解

A

B

C

D

E

F

G

H

I

J

K

L

M

推荐阅读更多精彩内容

2021辽宁省大学生程序设计竞赛题解