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

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

不会

B

不会

C

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

#include 
#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 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 
#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 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 
#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 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 
#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 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列的棋子个数是一样的 所以我们可以得到两个式子: ∑ i = 0 n − 1 a i = k sum_{i = 0}^{n-1}a_{i} = k ∑i=0n−1​ai​=k 和 a n s = ∏ i = 0 m − 1 C n a i % n ans = prod_{i=0}^{m-1}C_{n}^{a_{i%n}} ans=∏i=0m−1​Cnai%n​​
可以看出 答案其实只跟 a 0 a_{0} a0​到 a n − 1 a_{n-1} an−1​有关
所以 a n s = ∏ i = 0 n − 1 C n a i ∗ t i m e s [ a i ] ans = prod_{i=0}^{n-1}C_{n}^{a_{i}}*times[a_{i}] ans=∏i=0n−1​Cnai​​∗times[ai​]
所以现在只要求 a i a_{i} ai​的各种分布所得到的答案就行 dp

#include 
#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 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 
#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 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;
}