大前端

前端学习之家-大前端

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

比赛链接

A.无敌的强太郎

不会,后面看看能不能补

B.阿强的路

不会,后面看看能不能补

C.传染病统计(模拟+签到)

思路

考虑到数据范围很小,所以怎么搞都能过,直接枚举每一个人当作病毒源,然后找到最大最小输出即可

CODE

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

int n;

const int N = 10;

int a[N];
int chafen[N];

int check(int loc) {
	int ans = 1;
	for(int i = loc;i < n; ++i) {
		if(a[i + 1] - a[i] > 2) break;
		ans++;
	}
	for(int i = loc; i > 1; --i) {
		if(a[i] - a[i - 1] > 2) break;
		ans++;
	}
	return ans;
}

int main()
{
	int t;
	cin>>t;
	while(t--) {
		cin>>n;
		for(int i = 1;i <= n; ++i) {
			cin>>a[i];
		}
		sort(a+1,a+n+1);
		int ans_min = 10000;
		int ans_max = 0;
		for(int i =1;i <= n; ++i) {
			int k = check(i);
			ans_min = min(ans_min,k);
			ans_max = max(ans_max,k);
		}
		cout<<ans_min<<" "<<ans_max<<endl;
	}
	
	
	
	return 0;
}

D.阿强与网格(思维+签到)

思路

因为考虑到阿强是从左上角移动到左下角的,那么向上和向左的移动是无效的,又因为我们能斜着移动,所以只有向右、向下、向左下、向右下的移动是有效移动,为什么说向左下移动是有效的呢,当Y的花费比2X小的时候我们会发现,我们斜着移动是最优的,也就是我们总共有三种到达终点的方法:

  • 第一种直接先下,然后右移
  • 第二种先斜着移动一个小正方形的边界,然后再平移过去
  • 第三种就是一直斜着移动,但是要注意判断奇偶

注意一点就是,如果当这个矩阵的大小是 1 × n 1\times n 1×n or n × 1 n \times 1 n×1的话直接输出就好

CODE

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

#define ll long long
ll t,n,m,x,y;

int main()
{
	scanf("%lld",&t);
	while(t--) {
		scanf("%lld%lld%lld%lld",&n,&m,&x,&y);
		ll ans = x * (n + m - 2LL);//横竖直接走
		ll kk = 0;
		if(n > m) {
			if(m == 1) {
                printf("%lld\n",(n-1) * x);
                continue;
            }
			kk = (m - 1LL) * min(2LL * x, y) + x * (n - m);
		}
		else {
			if(n == 1) {
                printf("%lld\n",(m-1) * x);
                continue;
            }
			kk = (n - 1LL) * min(2LL * x, y) + x * (m - n);
		}
		ll k3 = max(n-1LL,m-1LL) * y;
		ll k2 = max(n-1LL,m-1LL) - min(n-1LL,m-1LL);
		if(k2 & 1) {
			k3 += x - y;
		}
		ans = min(k3,ans);
		printf("%lld\n",min(kk,ans));
	}
	
	return 0;
}

E.生活大爆炸(组合数学)

思路

我们枚举每个女生选中的情况,队友A的(

CODE

#include <bits/stdc++.h>
using namespace std;
int a[100][100];
void prehandle() {
	for(int i = 0; i < 80; i++) {
		a[i][0] = 1;
	}
	for(int i = 1; i < 33; i++) {
		for(int j = 0; j <= i; j++) {
			if(!j) a[i][j] = 1;
			else if(i == j) a[i][j] = 1;
			a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
		}
	}
}
int main() {
   long long n, m ,t;
   cin >> n >> m >> t;
   prehandle();
   long long ans = 0;
   if(n >= m) {
		long long g = 1;
		while(t - g >= 4 && g <= m) {
		//	cout << t << " " << g << endl;
			if(t - g > n) {g++;continue;}
			
		//	cout << t << " " << g << endl;
			ans += (a[m][g] * a[n][t - g]);
			g++;
		}
   } else {
   		long long b = 4;
   		while(t - b >= 1 && b <= n) {
			   cout << t << " " << b << endl;
   			if(t - b > m) {b++;continue;}
			   
   			ans += (a[m][b] * a[n][t - b]);
   			b++;
  		 }
   }
  // cout << a[n][4] * a[m][1] * a[n + m - 5][t - 5] << endl;
     cout << ans << endl;
    return 0;
}

F.Capslock(暴力+签到)

思路

直接暴力判断就好了

CODE

#include<bits/stdc++.h>
using namespace std;
int main()
{
		string ch;
		cin>>ch;
		bool fg1 = true;
		for(int i = 1;i < ch.size(); ++i) {
			if(ch[i] >= 'A' && ch[i] <= 'Z') continue;
			fg1 = false;
			break;
		}
		if(ch[0] >= 'A' && ch[0] <= 'Z') {
			if(fg1) {
				for(int i = 0;i < ch.size(); ++i) {
					ch[i] += 32;
				}
			}
		}
		else {
			if(fg1) {
				for(int i = 1;i < ch.size(); ++i) {
					ch[i] += 32;
				}
				ch[0] -= 32;
			}
		}
		cout<<ch<<endl;
	
	return 0;
}

G.字节类型(签到+模板)

思路

如果是C/C++选手的话直接写高精度模板判断就行,JAVA选手可以使用Biginteger,当然我选py

CODE`

y = input("")
x = int(y)
if (x >= -128 and x <= 127):
    print("byte")
elif(x >= -32768 and x <= 32767):
    print("short")
elif (x >= -2147483648 and x <= 2147483647):
    print("int")
elif (x >= -9223372036854775808 and x <= 9223372036854775807):
    print("long")
else:
    print("BigInteger")

H.制造游戏币

不会,后面看看能不能补

I.完美主义(线段树+差分)

思路

我们可以先对苹果做一个差分,然后我们维护一个区间最小值的线段树,如果查询的区间的最小值小于0,那么这个区间不是完美的,反之则是完美的,更新也就比较方便了

CODE

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

const int INF = 0x3f3f3f3f;
const int N = 2000005;
int n,m;
int a[N],tree[N << 2],b[N];

void push_up(int k) {
	tree[k] = min(tree[k<<1],tree[k<<1|1]);
}
void build(int k, int l,int r) {
	if(l == r) {
		tree[k] = a[l];
	}
	else {
		int mid = l + ((r-l)>>1);
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
		push_up(k);
	}
}

void updata(int p,int v,int l,int r,int k) {
	if(l == r) {
		a[p] += v, tree[k] += v;
	}
	else {
		int mid = l + ((r-l)>>1);
		if(p <= mid) {
			updata(p,v,l,mid,k<<1);
		}
		else {
			updata(p,v,mid+1,r,k<<1|1);
		}
		push_up(k);
	}
}

int query(int L, int R,int l,int r,int k) {
	if(L <= l && R >= r) {
		return tree[k];
	}
	else {
		int ans = INF;
		int mid = l+r >>1;
		if(L <= mid) {
			ans = min(ans,query(L,R,l,mid,k<<1));
		}
		if(R > mid) {
			ans = min(ans,query(L,R,mid+1,r,k<<1|1));
		}
		return ans;
	}
}
int main()
{
	while(~scanf("%d%d",&n,&m)) {
		for(int i = 1;i <= n; ++i) {
			scanf("%d",&b[i]);
			a[i] = b[i] - b[i - 1];
		}
		build(1,1,n);
		int op;
		int l,r;
		while(m--) {
			scanf("%d",&op);
			if(op == 2) {
				scanf("%d%d",&l,&r);
				int k = query(l + 1,r,1,n,1);
				if(k < 0) puts("No");
				else puts("Yes");
			}
			else {
				scanf("%d%d",&l,&r);
				updata(l,r-b[l],1,n,1);
				updata(l+1,b[l] -r,1,n,1);
				b[l] = r;
			}
		}
	}
	return 0;
}

J.放棋子

不会,后面看看能不能补

K.赌博

不会,后面看看能不能补

L.神奇的回答(签到)

思路

直接判断就行

CODE

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	while(n--) {
		int x;
		cin>>x;
		if(x > 18) cout<<18<<endl;
		else cout<<x<<endl;
	}
	return 0;
}

M.比赛!(拓扑排序)

思路

队友A的,听说是拓扑排序比较麻烦的一题

CODE

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define N 509
#define mt(x) memset(x, 0, sizeof x)
int n, m;
int num, head[N], in[N];
char s[N], ans[N];
bool vis[N];
struct ii
{
    int to, next;
} mp[N];
void add(int x, int y)
{
    mp[++num].to = y;
    mp[num].next = head[x];
    head[x] = num;
    in[y]++;
}
void tpsort()
{
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 1; i <= n; ++i)
        if (!in[ans[i]])
            q.push(ans[i]);
    int pd = 0;
    while (q.size())
    {
        int p = q.top();
        pd = 1;
        printf("%c", p);
        q.pop();
        for (int i = head[p]; i; i = mp[i].next)
        {
            in[mp[i].to]--;
            if (!in[mp[i].to])
                q.push(mp[i].to);
        }
    }
    puts("");
}
bool bfs(int x, int y)
{
    queue<int> q;
    q.push(x);
    //因为添加的是x->y,要找环的话就找是否有边存在y->x
    int vis[N] = {};
    while (q.size())
    {
        int p = q.front();
        q.pop();
        vis[p] = 1;
        for (int i = head[p]; i; i = mp[i].next)
        {
            int z = mp[i].to;
            if (y == z)
                return true;
            if (!vis[z])
                q.push(z);
        }
    }
    return false;
}
int main()
{
    scanf("%lld", &m);
    mt(head);
    mt(in);
    num = 0;
    bool pd = true;
    for (int i = 0; i < m; ++i)
    {
        scanf("%s", s);
        int x = s[0], y = s[2], z = s[3];
        //printf("%d %d %d\n", x, y, z);
        if (!vis[x])
        {
            vis[x] = 1;
            ans[++n] = s[0];
        }
        if (!vis[y])
        {
            vis[y] = 1;
            ans[++n] = s[2];
        }
        if (!vis[z])
        {
            vis[z] = 1;
            ans[++n] = s[3];
        }
        add(y, x);
        if (pd && bfs(x, y))
            pd = false;
        add(x, z);
        if (pd && bfs(z, x))
            pd = false;
    }
    if (pd)
        tpsort();
    else
        printf("No Answer");
    return 0;
}

总结

在这里插入图片描述

这场比赛是我们正式赛结束后当天VP的一场(原因是rhr说辽宁离济南近点,可能风格和济南站差不多),效果还不错,rank27,开局速A4个签到题,然后D题卡了很久,然后和队友讨论E题去了,yy WA了几发后最后找到了bug,然后速A,我们转头开D,因为这个时候D已经很多人开出来了,我们当时还没想到折线走,半小时后我们想到了折线走可能会最优,但是忘记处理只有一行或者一列的情况不能折现走,所以WA了4发,这是很可惜的,当时A出来的时候六题就已经二十多名了,所以我们继续开题,rhr看到M题,他说他做过,然后过了一会就A了,然后我看到了I,感觉也能做,然后1A,这个时候已经做了3个小时21分钟了,我们继续开J,想了好几种方法,但是都不对,所以3小时30min的时候就下机了,最终的终榜也就再rank27,感觉最近的训练还是有效果,怎么说呢,感觉未来可期吧。

发表评论:

Copyright Your WebSite.Some Rights Reserved.