投稿
  1. 首页
  2. C

2020团队设计天梯赛（部分）

code • 2022-4-25 • C • 阅读 46

2020团队设计天梯赛（部分）,第1张

文章目录
  • L2-2 分发口罩---大模拟
  • L2-3 完全二叉树的层序遍历 --后序转前序
    • 前序转层序
    • 中序转层序
    • 后序转层序
    • 代码
  • L2-4 网红点打卡攻略---简单模拟
  • L3-1 那就别担心了---dfs+记忆化搜索
    • 与运算&
    • 或运算|
    • 异或运算

以下的题目可能会有多种写法，大家看不懂得话，可以换一个代码看看，这些题目是卡住我的题目。
第一道题是一个大模拟，由于自己的逻辑不都清晰，然后思维很混乱导致的，所以我觉得要理清他的限制条件，可以把每个限制条件写成以一个函数来调用，然后选择合适的容器来储存，所以STL得运用也要加强。

L2-2 分发口罩—大模拟



样例输入：

4 2
5 3
A 123456789012345670 1 13:58
B 123456789012345671 0 13:58
C 12345678901234567 0 13:22
D 123456789012345672 0 03:24
C 123456789012345673 0 13:59
4 3
A 123456789012345670 1 13:58
E 123456789012345674 0 13:59
C 123456789012345673 0 13:59
F F 0 14:00
1 3
E 123456789012345674 1 13:58
1 1
A 123456789012345670 0 14:11

样例输出：

D 123456789012345672
A 123456789012345670
B 123456789012345671
E 123456789012345674
C 123456789012345673
A 123456789012345670
A 123456789012345670
E 123456789012345674

写法一：

#include
using namespace std;
map<string,int>mp,mp2;

struct node
{
	string name;
	string id;
	int num,hh,mm,t,idx;
	char time[15];	
}a[55555],b[55555];

int cmp(node a,node b)  // 排序 
{	
	if(a.t!=b.t)  // 如果时间不相同，根据时间排序，否则根据输入顺序排序 
	return a.t<b.t;   
	else
	return a.idx<b.idx;
}

int check(string n)  // 检查身份z号是否合格 
{	
	if(n.length()!=18)
	return 0;
	
	for(int i=0;i<n.length();i++)
	{
		if(!isdigit(n[i]))
		return 0;
	}
	return 1;
}

int main()
{
	int D,P,g=0;
	cin>>D>>P;
	for(int i=1;i<=D;i++)
	{
		int T,S;
		cin>>T>>S;	
		for(int j=0;j<T;j++)
		{	
		
			cin>>a[j].name>>a[j].id>>a[j].num>>a[j].time;
			a[j].idx=j;  // 记录输入顺序 
			
			if(mp.find(a[i].id)==mp.end())
			mp[a[i].id]=0;
			
			if(a[j].num==1&&mp2.find(a[j].id)==mp2.end()&&check(a[j].id))
			{
				mp2[a[j].id]=0;
				b[g++]=a[j];
			}	
			
			sscanf(a[j].time,"%d:%d",&a[j].hh,&a[j].mm); 
			a[j].t=a[j].hh*60+a[j].mm;//这个转换时间的方法是真的不错！
		
		}
		sort(a,a+T,cmp);
		int cnt=0;
		for(int j=0;j<T&&cnt<S;j++)  // S有可能为0，所以要将cnt和S的比较写在for后面的括号里面 
		{
	
				if(check(a[j].id)&&((mp[a[j].id]+P+1<=i)||mp[a[j].id]==0))
				{
					cout<<a[j].name<<" "<<a[j].id<<endl;
					cnt++;
					mp[a[j].id]=i;
				}	
		}
	}
	for(int i=0;i<g;i++)
	cout<<b[i].name<<" "<<b[i].id<<endl;
	return 0;
}

写法二：
简单模拟
首先确定结构体：输入的五个值，还要加一个优先级，为什么，因为题目说了，当两个人申请时间一样时，按列表中出现的先后顺序来，这就是隐藏的一个优先级~
可以开两个vector 分别存拿到口罩的人和身体有状况的人，相应的要用两个 map 辅助，map1 记录最近申请的天数，map2 去重即可~

#include

using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int d, p, t, s;
struct node {
    char name[15];
    char id[25];
    int h, m;
    int status;
    int priority;
};
map<string, int> m1, m2;
vector<node> ans1, ans2;

bool checkid(char s[]) {
    if (strlen(s) != 18) return 0;
    for (int i = 0; i < strlen(s); i++) {
        if (!isdigit(s[i])) return 0;
    }
    return 1;
}

bool checkday(int x, int y) {
    return (y - x - 1 >= p);
}

bool cmp(node a, node b) {
    if (a.h != b.h) return a.h < b.h;
    else if (a.m != b.m) return a.m < b.m;
    else return a.priority > b.priority;
}

string chartostring(char s[]) {
    string ans = "";
    for (int i = 0; i < strlen(s); i++) ans += s[i];
    return ans;
}

int main() {
    scanf("%d%d", &d, &p);
    for (int u = 1; u <= d; u++) {
        scanf("%d%d", &t, &s);
        vector<node> v;
        node a;
        while (t--) {
            scanf("%s %s %d %d:%d", a.name, a.id, &a.status, &a.h, &a.m);
            a.priority = t;
            if (checkid(a.id) && a.status && !m2[chartostring(a.id)]) {
                m2[chartostring(a.id)] = 1;
                ans2.push_back(a);
            }
            v.push_back(a);
        }
        sort(v.begin(), v.end(), cmp);
        for (auto i:v) {
            if (checkid(i.id) && s) {
                if (!m1[chartostring(i.id)]) {
                    s--;
                    m1[chartostring(i.id)] = u;
                    ans1.push_back(i);
                } else {
                    if (checkday(m1[chartostring(i.id)], u)) s--, ans1.push_back(i), m1[chartostring(i.id)] = u;
                }
            }
        }
    }
    for (auto i:ans1) printf("%s %s\n", i.name, i.id);
    for (auto i:ans2) printf("%s %s\n", i.name, i.id);
    return 0;
}

第二题是考察得二叉树，这个我自己写出来的，但是也是回顾了数据结构知识的前提下。

L2-3 完全二叉树的层序遍历 --后序转前序


这道题虽然是自己写出来的，但是还是还是查了一些知识点，才学完数据结构一个学期，啥都不记得了，全还给老师去了。
好了，首先是
前序遍历—根左右
中序遍历—左根右
后序遍历—左右根

前序转层序 
int idx = 0;
void dfs(int t) {  //实际上就是按后序遍历的顺序访问
    if(t > n) return ;
     ans[t] = hx[++ idx];
    dfs(t << 1);
    dfs(t << 1 | 1);
 
}
dfs(1);
中序转层序 
int idx = 0;
void dfs(int t) {  //实际上就是按中序遍历的顺序访问
    if(t > n) return ;
    dfs(t << 1);
    ans[t] = zx[++ idx];
    dfs(t << 1 | 1);
}
dfs(1);
后序转层序 
int idx = 0;
void dfs(int t) {  //实际上就是按后序遍历的顺序访问
    if(t > n) return ;
    dfs(t << 1);
    dfs(t << 1 | 1);
    ans[t] = hx[++ idx];
}
dfs(1);

这一道题一看数据范围，就知道可以用dfs、bfs、dp来做了。
这道题使用dfs

代码 
#include 

using namespace std;
int h[50];
int a[50];
int idx=1;
  int n;
void dfs(int u)
{
    if(u>n)return ;
    dfs(u*2);
    dfs(u*2+1);
    a[u]=h[idx];
    idx++;
}

int main()
{

    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>h[i];
    dfs(1);

    for(int i=1;i<=n;i++)
        cout<<a[i]<<" "[i==n];


    return 0;
}

第三题我读错题意，我觉得这方面就本来是我一个薄弱的地方，再加上读错题了，希望在明年的天体赛下面能够处理的游刃有余。

L2-4 网红点打卡攻略—简单模拟


输入样例：

6 13
0 5 2
6 2 2
6 0 1
3 4 2
1 5 2
2 5 1
3 1 1
4 1 2
1 6 1
6 3 2
1 2 1
4 5 3
2 0 2
7
6 5 1 4 3 6 2
6 5 2 1 6 3 4
8 6 2 1 6 3 4 5 2
3 2 1 5
6 6 1 3 4 5 2
7 6 2 1 3 4 5 2
6 5 2 1 4 3 6

输出样例：

3
5 11

给你一个路径，判断这条路径是否是一个NP完全问题的解，如果是找出路径最短的那个解，而且还得记录有多少个正确的解
这个题要判断给的点是否是n个不同的点就好了。1、p等于n。2、这p个点没有重复的点

首先判断攻略是否包含了所有网红点，即n是否等于N
判断0和攻略的第一个点和最后一个点是否有路
有路的话，判断每两个点之间是否有通路，判断是否走过即可AC。

写法一：

#include 
using namespace std;
const int maxn = 2005;
int g[maxn][maxn], a[maxn], vis[maxn];
int main() {
    int n, m, k;
    cin >> n >> m;
	while(m--) {
		int x, y, w;
		cin >> x >> y >> w;
		g[x][y] = g[y][x] = w;
	}
	cin >> k;
	int pos = 0, mx = 0x3f3f3f3f, mxn = 0, cnt = 0;
	while(pos++ < k) {
		int sum = 0, f = 0;
		cin >> m;
		for(int i = 1; i <= m; ++i) cin >> a[i];
		if(m == n) {//要求每个网红店仅只能访问一次，且都要访问到
			memset(vis, 0 ,sizeof vis);
			if(g[0][a[1]] && g[a[m]][0]) f = 1, sum = g[0][a[1]] + g[a[m]][0];
			vis[0] = vis[a[1]] = 0;
			for(int i = 1; i < m; ++i) {
				if(g[a[i]][a[i + 1]] && !vis[a[i + 1]]) {
					vis[a[i + 1]] = 1;
					sum += g[a[i]][a[i + 1]];
				}
				else {
					f = 0;
	 				break;
				}
			}
		}
		if(f) {
			cnt++;
			if(mx > sum) {
				mx = sum;
				mxn = pos;
			}
		}
	}
	cout << cnt << endl << mxn << " " << mx;
	return 0;
}

写法二：

#include  
using namespace std;

const int N = 210;

int g[N][N];
int n,m;
int k,p;

int road[N];
long long id,ans = 1e9;
long long sum;
bool check()
{
	sum = 0;
	sum += g[0][road[1]];
	
	for(int i = 1;i < p;i ++)
	{
		int x = road[i],y = road[i + 1];
		sum += g[x][y];	
	}
	sum += g[road[p]][0];
	
	if(sum >= 1e9){
		return false;
	}
	return true;
}
int main()
{
	cin >> n >> m;
	
	memset(g,0x3f,sizeof g);
	
	for(int i = 0;i < m;i ++)
	{
		int a,b,c;
		cin >> a >> b >> c;
		g[a][b] = g[b][a] = min(g[a][b],c);
	}
	
	cin >> k;
	int cnt = 0;
	
	for(int i = 1;i <= k;i ++)
	{
		cin >> p;
		set<int>ss; 
		for(int j = 1;j <= p;j ++)
		{
			cin >> road[j];
			ss.insert(road[j]);
		}
		
		if(p == n && ss.size() == n && check()){//这是用另外一种方式来保证所访问的能够满足条件，再来算最小值
			if(ans > sum){
				ans = sum;
				id = i;
			}
			cnt ++;
		}
	}
	
	cout << cnt << endl;
	cout << id << ' ' << ans << endl;
	
	return 0;
}

这类题目我就尽力做吧，真的是很弱，只能希望明年能够好起来吧！

L3-1 那就别担心了—dfs+记忆化搜索

下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题，其实都不用担心。


输入样例：

7 8
7 6
7 4
6 5
4 1
5 2
5 3
2 1
3 1
7 1

输出样例：

3 Yes

输入样例：

7 8
7 6
7 4
6 5
4 1
5 2
5 3
6 1
3 1
7 1

输出样例：

3 No

题目很容易理解，思路也很容易写出来。
从A开始用dfs来判断是否会到达B。但是要求A开始的任意一条边都要能到达B，终点可能是B能推出来的命题，但是我们不关心，只用到B就行了。
唯一需要注意的是dfs有很多重复的点，如果不记忆的话，会超时的。

写法一：

#include 
using namespace std;
const int N = 1e6 + 10;

int h[N],e[N],ne[N],idx;

int n,m;
int S,E;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

int ans[N];
bool st[N];
bool flag = true;
int dfs(int u)
{
    if(h[u] == -1 && u != E){//找到最后了都没找到
        flag = false;
    }
    st[u] = true;
    if(ans[u]) return ans[u];//找到最后就加一个答案
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        ans[u] += dfs(j);//找到一个点就加一个答案
    }
    
    return ans[u];
}


int main()
{
    memset(h,-1,sizeof h);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 0;i < m;i ++)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
    }
    cin >> S >> E;
    ans[E] = 1;
    dfs(S);
    
    if(flag){
        cout << ans[S] << ' ' << "Yes" << endl;
    }else{
        cout << ans[S] << ' ' << "No" << endl;
    }
    
    return 0;
}

写法二：

#include 
using namespace std;
const int maxn = 505;
vector<int> g[maxn];
int a, b, n, m, cnt = 0;
int vis[maxn];
pair<bool, int> dfs(int idx) {
	if(idx == b) {
		cnt++;
		return {1, 1};//有一条路可以到达
	}
	if(vis[idx]) {
		cnt += vis[idx];
		return {1, vis[idx]};//这条路下去有多少，有多少条路可以到达目标，实现记忆化
	}
	bool flag = 1, ent = 0;
	for(auto i : g[idx]) {
		auto t = dfs(i);
		flag &= t.first;//有一个1就可以了
		vis[idx] += t.second;
		ent = 1;
	}
	return {flag && ent, vis[idx]};
}
int main() {
	cin >> n >> m;
	while(m--) {
		scanf("%d %d", &a, &b);
		g[a].push_back(b);//用vector来存储就很妙
	}
	cin >> a >> b;
	if(dfs(a).first) {
		printf("%d Yes", cnt);
	}
	else {
		printf("%d No", cnt);
	}
	return 0;
}
与运算& 
1 & 1 = 1;
1 & 0 = 0;
0 & 1 = 0;
0 & 0 = 0;
或运算| 
0 | 0 = 0；
0 | 1 = 1；
1 | 0 = 1；
1 | 1 = 1；
 
0010 1011 | 0101 0100 = 0111 1111
异或运算 
0 ^ 0 = 0;
0 ^ 1 = 1;
1 ^ 0 = 1;
1 ^ 1 = 0;

写法三：拿部分分
拿了28分，最后一个测试点没过

#include 
using namespace std;
const int N = 1e6 + 10;

int h[N],e[N],ne[N],idx;

int n,m;
int S,E;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

int ans;
bool st[N];
bool flag = true;
void dfs(int u)
{
    if(u == E){
        ans ++;
        return;
    }
    if(u != E)
    {
        if(h[u] == -1){//说明找到最后都没有找到
            flag = false;
        }
    }
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        dfs(j);
    }
}


int main()
{
    memset(h,-1,sizeof h);
    
    cin >> n >> m;
    for(int i = 0;i < m;i ++)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
    }
    cin >> S >> E;
    dfs(S);
    
    if(flag){
        cout << ans << ' ' << "Yes" << endl;
    }else{
        cout << ans << ' ' << "No" << endl;
    }
    
    return 0;
}

剩下还有两道题，我觉得不是我能写的，所以我也就不掌握了！

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/717431.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-25
下一篇 2022-04-25

发表评论

登录后才能评论

评论列表（0条）

保存