2018年全国多校算法寒假训练营练习比赛（第一场）

港控/mmm° 2022-06-01 06:08 171阅读 0赞

这是一场拼手速和细节的比赛，难题并不多，我做的七道题里没有一道涉及算法。我虽然做的有点慢，但是七道题全部1A，其中J题的规律想半天想不出来，感谢Winzard大神出手相助告诉了我hhhhh，最后拿了第26名，还算可以吧。

![SouthEast][]

A题：[大吉大利，今晚吃鸡——枪械篇][Link 1]

首先把n把枪的属性全部记录下来，然后对m个配件进行处理，处理出每一类配件的最高属性值，代回n把枪中，再对n把枪遍历一遍，就处理出了威力最高的枪，也就是答案。

#include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <string>  
    #include <cstdlib>  
    #include <cmath>  
    #include <vector>  
    #include <queue>  
    #include <iterator>  
    #include <map>  
    #include <algorithm>  
    #include <set>  
    #include <functional>  
    #include <time.h>  
    #define lson rt<<1  
    #define rson rt<<1|1  
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100005;
    const LL MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
    LL ppow(LL a, LL b) { LL res = 1; for (int i = 1; i <= b; i++)   res *= a; return res; }
    LL quick_mod(LL a, LL b, LL c) { LL ans = 1; while (b) { if (b % 2 == 1)ans = (ans*a) % c; b /= 2; a = (a*a) % c; }return ans; }
    
    struct gun
    {
    	double power;
    	int num;
    	int add[1005];
    };
    
    gun G[1005];
    double add[1005];
    
    int main()
    {
    	double res,ans,b;
    	int q;
    	int n, m;
    	while (scanf("%d%d", &n, &m) != EOF)
    	{
    		ans = 0;
    		memset(add, 0, sizeof add);
    		for (int i = 1; i <= n; i++)
    		{
    			scanf("%lf", &G[i].power);
    			scanf("%d", &G[i].num);
    			for (int j = 1; j <= G[i].num; j++)
    				scanf("%d", &G[i].add[j]);
    		}
    		for (int i = 1; i <= m; i++)
    		{
    			scanf("%d%lf", &q, &b);
    			if (add[q] - b < -eps)
    				add[q] = b;
    		}
    		for (int i = 1; i <= n; i++)
    		{
    			res = 1;
    			for (int j = 1; j <= G[i].num; j++)
    				res += add[G[i].add[j]];
    			res *= G[i].power;
    			if (res - ans > eps)
    				ans = res;
    		}
    		printf("%.4lf\n", ans);
    	}
    }

B题： [最强的决斗者一切都是必然的！][Link 2]

首先按顺序处理出每一次连锁的范围，对于样例来说，一共有三次连锁，分别是1~4,5~6,7~9。对于每一次连锁，我们从后往前循环分析，因为后连锁的先发动，如果是type1就直接ans+=x，如果是type2就ans+=x\*p，如果是type3我们就可以直接跳出该连锁，处理下一个连锁，如果是type4我们就跳过一张卡。最后处理完所有连锁后，ans就是总伤害。

#include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <string>  
    #include <cstdlib>  
    #include <cmath>  
    #include <vector>  
    #include <queue>  
    #include <iterator>  
    #include <map>  
    #include <algorithm>  
    #include <set>  
    #include <functional>  
    #include <time.h>  
    #define lson rt<<1  
    #define rson rt<<1|1  
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100005;
    const LL MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
    LL ppow(LL a, LL b) { LL res = 1; for (int i = 1; i <= b; i++)   res *= a; return res; }
    LL quick_mod(LL a, LL b, LL c) { LL ans = 1; while (b) { if (b % 2 == 1)ans = (ans*a) % c; b /= 2; a = (a*a) % c; }return ans; }
    
    struct card
    {
    	int speed;
    	int type;
    	int x;
    };
    
    LL ans;
    card C[1005];
    int l, r;
    
    void solve()
    {
    	for (int i = r; i >= l; i--)
    		if (C[i].type == 1)
    			ans += C[i].x;
    		else if (C[i].type == 2)
    			ans += C[i].x*(i - l + 1);
    		else if (C[i].type == 3)
    			return;
    		else if (C[i].type == 4)
    			i--;
    }
    
    int main()
    {
    	int n, p;
    	while (scanf("%d", &n) != EOF)
    	{
    		ans = 0;
    		l = 1;
    		r = 1;
    		for (int i = 1; i <= n; i++)
    		{
    			scanf("%d%d", &C[i].speed, &C[i].type);
    			if (C[i].type == 1 || C[i].type == 2)
    				scanf("%d", &C[i].x);
    		}
    		while (l <= n&&r <= n)
    		{
    			p = C[l].speed;
    			while (r + 1 <= n&&C[r + 1].speed >= p)
    				p = C[++r].speed;
    			solve();
    			l = r + 1;
    			r = l;
    		}
    		printf("%lld\n", ans);
    	}
    }

F题： [大吉大利，今晚吃鸡——跑毒篇][Link 3]

这道题数据范围很小，我们直接用最暴力的模拟即可，也就是每一秒每一秒的模拟，每一秒都判断一下下一回合不用急救包会不会死，如果会死就用急救包，否则就前进，如果要用急救包的时候再判断一下当前状态不用急救包能否走到终点和急救包是否够用，反正就是题目是什么要求我们就怎么写。

#include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <string>  
    #include <cstdlib>  
    #include <cmath>  
    #include <vector>  
    #include <queue>  
    #include <iterator>  
    #include <map>  
    #include <algorithm>  
    #include <set>  
    #include <functional>  
    #include <time.h>  
    #define lson rt<<1  
    #define rson rt<<1|1  
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100005;
    const LL MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
    LL ppow(LL a, LL b) { LL res = 1; for (int i = 1; i <= b; i++)   res *= a; return res; }
    LL quick_mod(LL a, LL b, LL c) { LL ans = 1; while (b) { if (b % 2 == 1)ans = (ans*a) % c; b /= 2; a = (a*a) % c; }return ans; }
    
    int a, b, c;
    int hp;
    
    bool solve()
    {
    	hp = 100;
    	for (int t = 1; t <= b; t++)
    	{
    		hp -= a;
    		if (hp - a * 7 <= 0)
    			if (hp - a*(b - t - 1) > 0)
    				return true;
    			else
    				if (c > 0 && a * 6 < 100)
    				{
    					hp = 80; c--;
    				}
    				else 
    					return false;
    	}
    	return true;
    }
    
    int main()
    {
    	bool ans;
    	int T;
    	scanf("%d", &T);
    	while (T--)
    	{
    		scanf("%d%d%d", &a, &b, &c);
    		ans = solve();
    		if (ans)
    			printf("YES\n");
    		else
    			printf("NO\n");
    	}
    }

G题： [圆圈][Link 4]

一道标准的递归图形输出问题，这类问题有通解：[递归图形输出问题通解][Link 5]

#include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <string>  
    #include <cstdlib>  
    #include <cmath>  
    #include <vector>  
    #include <queue>  
    #include <iterator>  
    #include <map>  
    #include <algorithm>  
    #include <set>  
    #include <functional>  
    #include <time.h>  
    #define lson rt<<1  
    #define rson rt<<1|1  
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100005;
    const LL MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
    LL ppow(LL a, LL b) { LL res = 1; for (int i = 1; i <= b; i++)   res *= a; return res; }
    LL quick_mod(LL a, LL b, LL c) { LL ans = 1; while (b) { if (b % 2 == 1)ans = (ans*a) % c; b /= 2; a = (a*a) % c; }return ans; }
    
    bool a[3000][3000];
    
    void draw(int x, int y, int n)
    {
    	int temp = ppow(3, n - 1);
    	if (n == 0) {
    		a[x][y] = true;
    	}
    	else {
    		draw(x - temp, y, n - 1);
    		draw(x + temp, y, n - 1);
    		draw(x, y - temp, n - 1);
    		draw(x, y + temp, n - 1);
    	}
    }
    
    int main()
    {
    	int T,n,x;
    	int len;
    	bool space;
    	scanf("%d", &T);
    	while (T--)
    	{
    		memset(a, 0, sizeof a);
    		scanf("%d", &n);
    		len = ppow(3, n);
    		x = (len + 1) / 2;
    		draw(x, x, n);
    		for (int i = 1; i <= len; i++)
    		{
    			space = true;
    			for (int j = 1; j <= len; j++)
    				if (a[i][j])
    				{
    					printf("O");
    					space = false;
    					for (int t = j + 1; t <= len; t++)
    						if (a[i][t])
    							space = true;
    				}
    				else
    					if (space)
    						printf(" ");
    					else
    						break;
    			printf("\n");
    		}
    	}
    }

H题： [方块与收纳盒][Link 6]

斐波那契数列

I题：[找数字个数][Link 7]

数据范围很小，把他给你的数字进行数位处理，不能选的数打上标记，然后直接1到1000的循环，答案就出来了。

#include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <string>  
    #include <cstdlib>  
    #include <cmath>  
    #include <vector>  
    #include <queue>  
    #include <iterator>  
    #include <map>  
    #include <algorithm>  
    #include <set>  
    #include <functional>  
    #include <time.h>  
    #define lson rt<<1  
    #define rson rt<<1|1  
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100005;
    const LL MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
    LL ppow(LL a, LL b) { LL res = 1; for (int i = 1; i <= b; i++)   res *= a; return res; }
    LL quick_mod(LL a, LL b, LL c) { LL ans = 1; while (b) { if (b % 2 == 1)ans = (ans*a) % c; b /= 2; a = (a*a) % c; }return ans; }
    
    bool numok[10];
    int a, b;
    
    void solve(int x)
    {
    	int res;
    	while (x)
    	{
    		res = x % 10;
    		x /= 10;
    		numok[res] = false;
    	}
    }
    
    bool check(int x)
    {
    	if (x%a == 0 || x%b == 0)
    		return false;
    	int res;
    	while (x)
    	{
    		res = x % 10;
    		x /= 10;
    		if (numok[res] == false)
    			return false;
    	}
    	return true;
    }
    
    int main()
    {
    	int T;
    	int ans;
    	scanf("%d", &T);
    	while (T--)
    	{
    		ans = 0;
    		for (int i = 0; i < 10; i++)
    			numok[i] = true;
    		scanf("%d%d", &a, &b);
    		solve(a);
    		solve(b);
    		for (int i = 1; i <= 1000; i++)
    			if (check(i))
    				ans++;
    		printf("%d\n", ans);
    	}
    }

J题： [闯关的lulu][lulu]

这题题目里没告诉你规律，要自己找，找到了就很简单。奇数层会给你一个0，偶数层会给你一个1和一个0。

2个0->1个1，3个1->1个2，4个2->1个3，5个3->1个4，以此类推。

那么第n层一共会给你n个0和n/2个1，我们用一个数组记录这些数字的个数，比如说num\[p\]就是指p的个数，那我们就可以得到一个递推操作，num\[p\]=num\[p-1\]/(p+1),num\[p-1\]%=(p+1)，这就是把p-1转化成p的操作。我们从p=1开始执行这个操作，直到num\[p-1\]/(p+1)=0为止，即无法继续转化成更大的数了。然后我们从p到0循环一遍，对于每一个i输出num\[i\]次就是答案。

#include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <string>  
    #include <cstdlib>  
    #include <cmath>  
    #include <vector>  
    #include <queue>  
    #include <iterator>  
    #include <map>  
    #include <algorithm>  
    #include <set>  
    #include <functional>  
    #include <time.h>  
    #define lson rt<<1  
    #define rson rt<<1|1  
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100005;
    const LL MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
    LL ppow(LL a, LL b) { LL res = 1; for (int i = 1; i <= b; i++)   res *= a; return res; }
    LL quick_mod(LL a, LL b, LL c) { LL ans = 1; while (b) { if (b % 2 == 1)ans = (ans*a) % c; b /= 2; a = (a*a) % c; }return ans; }
    
    int num[1005];
    
    int main()
    {
    	int T, n, p;
    	scanf("%d", &T);
    	while (T--)
    	{
    		memset(num, 0, sizeof num);
    		scanf("%d", &n);
    		num[0] = n;
    		num[1] = n / 2;
    		p = 1;
    		while (num[p - 1] / (p + 1)>0)
    		{
    			num[p] += num[p - 1] / (p + 1);
    			num[p - 1] %= (p + 1);
    			p++;
    		}
    		for (int i = p - 1; i >= 0; i--)
    			for (int j = 0; j < num[i]; j++)
    				printf("%d", i);
    		printf("\n");
    	}
    }

[SouthEast]: /images/20220601/35b7b2de84584ba1bd50bb963951d04e.png
[Link 1]: https://www.nowcoder.com/acm/contest/67/A
[Link 2]: https://www.nowcoder.com/acm/contest/67/B
[Link 3]: https://www.nowcoder.com/acm/contest/67/F
[Link 4]: https://www.nowcoder.com/acm/contest/67/G
[Link 5]: http://blog.csdn.net/kele52he/article/details/79129111
[Link 6]: https://www.nowcoder.com/acm/contest/67/H
[Link 7]: https://www.nowcoder.com/acm/contest/67/I
[lulu]: https://www.nowcoder.com/acm/contest/67/J