2024 睿抗机器人开发者大赛CAIP-编程技能赛-本科组（省赛）

Kent_J_Truman

555人浏览 · 2025-03-29 11:28:40

Kent_J_Truman · 2025-03-29 11:28:40 发布

T1

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

const int N = 100;

int w[N];

int main()
{
	int n, cur;
	scanf("%d%d", &n, &cur);
	for(int i = 1; i <= n; i++)
		scanf("%d", &w[i]);
		
	int ans1 = 0, ans2 = 0;
	for(int i = 1; i <= n; i++, cur++)
	{
		if(cur > 7) cur = 1;
		
		if(w[i] >= 35 && cur != 4) ans1++;
		if(w[i] >= 35 && cur == 4) ans2++;
	}
	
	printf("%d %d", ans1, ans2);
}

T2

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

const int N = 100;

int w[N] = {0, 12, 9, 7, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1};
int ans[22];

int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
		for(int i = 1; i <= 20; i++)
		{
			int p, k;
			scanf("%d%d", &p, &k);
			ans[i] += w[p] + k;
		}
	}
	
	for(int i = 1; i <= 20; i++)
		printf("%d %d\n", i, ans[i]);
}

T3

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

const int N = 1010;

int g[N][N], w[N][N];
int n, m;

void f(int a, int b, int x)
{
	bool nom = true;
	for(int i = a-1; i <= a+1; i++)
		for(int j = b-1; j <= b+1; j++)
		{
			if(i < 1 || j < 1 || i > n || j > m) continue;
			if(g[i][j] == 'm') nom = false;
			if(w[i][j] == 3 || w[i][j] == 2) continue;
			if(x == 1 && w[i][j] == 4) continue;
			w[i][j] = x;
		}
		
	if(nom && x == 1)
	{
		for(int i = a-1; i <= a+1; i++)
			for(int j = b-1; j <= b+1; j++)
			{
				if(i < 1 || j < 1 || i > n || j > m) continue;
				if(w[i][j] == 1) w[i][j] = 4;
			}
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			scanf(" %c", &g[i][j]);
			if(g[i][j] != '.') w[i][j] = 3; //0空，1可能，2不可能，3被占, 4疑似
		}
		
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
			{
				if(g[i][j] == 'w') f(i, j, 1);
				else if(g[i][j] == 'c') f(i, j, 2);
			}
	
	bool has = false;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(w[i][j] == 4)
				printf("%d %d\n", i, j), has = true;
				
	if(!has) puts("Too cold!");
}

T4

错解

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

const int N = 1e5 + 10;
const int M = 2e5 + 10;

int h[N], e[M], ne[M], idx;
int p[N], cnt[N];
int st, ed;
int dist[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
int bfs()
{
    memset(dist, 0, sizeof dist);
    dist[st] = 1;
    queue<int> q;
    q.push(st);

    while (q.size())
    {
        int u = q.front();
        q.pop();

        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if (u == st && j == ed)
                continue;
             if (dist[j])
                 continue;
            dist[j] = dist[u] + 1;
            if (j == ed)
                return dist[j];
            q.push(j);
        }
    }

    return -1;
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        idx = 0;
        memset(h, -1, sizeof h);
        memset(cnt, 0, sizeof cnt);

        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            p[i] = i;

        for (int i = 1; i <= m; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b);
            add(b, a);
            int pa = find(a), pb = find(b);
            if (pa != pb)
            {
                cnt[pa] += cnt[pb]; // 归拢环数目到新的根节点
                p[pb] = pa;
            }
            else
            {
                cnt[pa]++;      // 检测到环
                st = a, ed = b; // 记录成环的端点
            }
        }

        int s = 0; // 子图个数(注意这个不是环的个数，而是只有一个环的连通块的个数)
        for (int i = 1; i <= n; i++)
            if (p[i] == i && cnt[i] == 1) // 并查集中一个根节点代表一个连通块
                s++;

        if (s != 1)
            printf("No %d\n", s);
        else
            printf("Yes %d\n", bfs());
    }
}

这个借鉴别人的，有误。这个想通过保留环上间距为1的点对来直接求环的长度，这有问题，因为即便只有一个章鱼子环，但是整个图可能有多个环出现（其它的连通块有多个环，不影响最后的答案），这样保留的st ed甚至可能不在目标环上！！所以还是老实的用topsort把非环点逐个剥离掉，间接算环的大小吧~

正确答案1

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

const int N = 1e5+10;
const int M = 2 * N;

int h[N], e[M], ne[M], idx;
int p[N], cnt[N], sz[N], d[N];
int n, m;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void merge(int a, int b)
{
    int pa = find(a);
    int pb = find(b);
    
    if(pa != pb)
    {
        p[pa] = pb;
        cnt[pb] += cnt[pa];
        sz[pb] += sz[pa];
    }
    else cnt[pb]++;
}
int toposort()
{
    int ret = 0;
    
    queue<int> q;
    int rt;
    for(int i = 1; i <= n; i++)
        if(p[i] == i && cnt[i] == 1)
            rt = i;
    for(int i = 1; i <= n; i++)
    {
        if(find(i) == rt && d[i] == 1) q.push(i);//必须保证进行topsort的点都来自章鱼图（通过根节点的ez,sz属性来判断）
    }
    
    while(q.size())
    {
        int u = q.front(); q.pop(); ret++;
        
        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(--d[j] == 1) q.push(j);
        }
    }
    
    return  sz[rt] - ret; //这里当然所有点不是n拉，我们是在章鱼图（块）上进行拆环，所有点是sz[rt]
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset(h, -1, sizeof h);
        idx = 0;
        
        cin >> n >> m;
        for(int i = 1; i <= n; i++) p[i] = i, cnt[i] = 0, d[i] = 0, sz[i] = 1;
        for(int i = 1; i <= m; i++)
        {
            int a, b;
            cin >> a >> b;
            merge(a, b);
            add(a, b);
            add(b, a);
            d[a]++;
            d[b]++;
        }
        
        int s = 0;
        for(int i = 1; i <= n; i++)
        {
            if(p[i] == i && cnt[i] == 1)
                s++;
        }

        if(s == 1) printf("Yes %d\n", toposort());
        else printf("No %d\n", s);
    }
}

正确答案2

下面的用sz ez来判断连通块中环的数量

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

const int N = 1e5+10;
const int M = 2 * N;

int h[N], e[M], ne[M], idx;
int p[N], cnt[N], sz[N], d[N];
int n, m;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void merge(int a, int b)
{
    int pa = find(a);
    int pb = find(b);
    
    if(pa != pb)
    {
        p[pa] = pb;
        cnt[pb] += cnt[pa];
        sz[pb] += sz[pa];
    }
    else cnt[pb]++;
}
int toposort()
{
    int ret = 0;
    
    queue<int> q;
    int rt;
    for(int i = 1; i <= n; i++)
        if(p[i] == i && cnt[i] == 1)
            rt = i;
    for(int i = 1; i <= n; i++)
    {
        if(find(i) == rt && d[i] == 1) q.push(i);//必须保证进行topsort的点都来自章鱼图（通过根节点的ez,sz属性来判断）
    }
    
    while(q.size())
    {
        int u = q.front(); q.pop(); ret++;
        
        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(--d[j] == 1) q.push(j);
        }
    }
    
    return  sz[rt] - ret; //这里当然所有点不是n拉，我们是在章鱼图（块）上进行拆环，所有点是sz[rt]
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset(h, -1, sizeof h);
        idx = 0;
        
        cin >> n >> m;
        for(int i = 1; i <= n; i++) p[i] = i, cnt[i] = 0, d[i] = 0, sz[i] = 1;
        for(int i = 1; i <= m; i++)
        {
            int a, b;
            cin >> a >> b;
            merge(a, b);
            add(a, b);
            add(b, a);
            d[a]++;
            d[b]++;
        }
        
        int s = 0;
        for(int i = 1; i <= n; i++)
        {
            if(p[i] == i && cnt[i] == 1)
                s++;
        }

        if(s == 1) printf("Yes %d\n", toposort());
        else printf("No %d\n", s);
    }
}

T5

#include <bits/stdc++.h>
using namespace std;
 
const int N = 5010;
 
int f[N];
struct node
{
    int t, d, p;
    bool operator<(const node &u) const
    {
        if (d != u.d)
            return d < u.d;
        return t > u.t;
    }
} a[N];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        memset(f, 0, sizeof f);
        int tm = 0;
 
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d%d%d", &a[i].t, &a[i].d, &a[i].p), tm = max(tm, a[i].d);
 
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; i++)
            for (int j = a[i].d; j >= a[i].t; j--)
                f[j] = max(f[j], f[j-a[i].t]+a[i].p);
                
        int ans = 0;
        for(int i = 1; i <= tm; i++)
            ans = max(ans, f[i]);
        printf("%d\n", ans);
    }
}

一般背包问题只有下限，这里还有上限。更新区间在下限~上限。

因此最优状态并不一定在Vm。

所以需要遍历所有状态。