2017 Multi-University Training Contest - Team 6

时间:2022-01-31 15:42:01

1003

题意:Bi=maxijAj , i2. 给出Ai,求出所有Bi

思路:直接暴力了,存储Ai和i,然后按Ai从小到大排序,然后从求出每个位置不整除i对应的最大数,在1e5的范围内最多会找100次(这个可以去看看反素数表,1e5的范围内一个数因子最多的个数就是100个,好像是这么多,根据鸽笼原理就是这样咯),最后的复杂度就是O(100 * n)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define mst(a, b)	memset(a, b, sizeof a)
#define REP(i, x, n)	for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
struct Node {
	int val, id;
	bool operator < (const Node &a) {
		return val > a.val;
	}
}node[qq];
int n;

int main(){
	int t;	scanf("%d", &t);
	while(t--) {
		scanf("%d", &n);
		for(int i = 0; i < n; ++i) {
			scanf("%d", &node[i].val);
			node[i].id = i + 1;
		}
		sort(node, node + n);
		for(int i = 2; i <= n; ++i) {
			for(int j = 0; j < n; ++j) {
				if(node[j].id % i != 0) {
					printf("%d", node[j].val);
					printf(i == n ? "\n" : " ");
					break;
				}
			}
		}
	}
	return 0;
}




1008

题意:给出一个m,一个串,在其中选择两个不相交的字串使得disA,B=i=0n1|AiBn1i| 小于等于m,问字串最长是多大

思路:想了很久猜想出来这个题的解法,假设两个串A、B,A串对应的位置是a c, B串对应的位置是b d,假设a < b,可以发现在范围a - d中,两个串是关于中间对称的,所以我想到了枚举对称轴,然后使用尺取法来维护串最大的长度

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define mst(a, b)	memset(a, b, sizeof a)
#define REP(i, x, n)	for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 2e5 + 10;
const int INF = 1e9 + 10;
char st[5005];
int n, m, res;

int main(){
	int t;	scanf("%d", &t);
	while(t--) {
		scanf("%d", &m);
		scanf("%s", st + 1);
		n = strlen(st + 1);
		res = 0;
		for(int k = 1; k < n; ++k) {
			int a = k, b = k + 1;
			int c = k, d = k + 1;
			int sum = 0;
			while(a != 0 && b != n + 1) {
				sum += abs(st[a] - st[b]);
				while(sum > m) {
					sum -= abs(st[c] - st[d]);
					c--, d++;
				}
				res = max(res, c - a + 1);
				--a, ++b;
			}
			a = k, b = k + 2;
			c = k, d = k + 2;
			sum = 0;
			while(a != 0 && b != n + 1) {
				sum += abs(st[a] - st[b]);
				while(sum > m) {
					sum -= abs(st[c] - st[d]);
					c--, d++;
				}
				res = max(res, c - a + 1);
				--a, ++b;
			}
		}
		printf("%d\n", res);
	}
	return 0;
}


1010

题意:给出n个点,n - 1条边, pi的父结点是i + 1,现在两个人玩游戏Alice先手,Bob后手,最初结点都是没有颜色的, 玩家Alice只可以选择一个没有颜色的点将它涂为白色,玩家Bob可以选择一个没有颜色的点将它涂为黑色,并且与这个点有边的点都会被涂为黑色(无论它之前是白色还是没有颜色), 玩家Bob由于冲了VIP,所以他有k次机会,可以在游戏中任意时刻去消除一条边,给出这个图,问最终谁会赢

思路:其实首先要明白一点这个k在什么情况下会使用,最开始推整个图是一条链的情况,发现只有n = 2时Bob才会赢,之后就画了几颗奇怪的图发现确实是这样,就猜了猜是不是把图都变成多个结点树为2的子图Bob就能赢,然后就试了试直接Dfs进行标记,搜到底的时候判断一些这点和它的父结点是否被标记,首先判断能不能变成多个结点数为2的子图,然后再判断需要消边的次数是不是小于等于k

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define mst(a, b)	memset(a, b, sizeof a)
#define REP(i, x, n)	for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 2e5 + 10;
const int INF = 1e9 + 10;
vector<int> G[505];
int n, k;
int cnt;
bool vis[505];
void Init() {
	for(int i = 0; i <= n; ++i) {
		G[i].clear();
	}
	mst(vis, false);
}

bool f;
void Dfs(int u, int fa) {
	for(int i = 0; i < (int)G[u].size(); ++i) {
		int v = G[u][i];
		if(v == fa)	continue;
		Dfs(v, u);
	}
	if(!vis[u] && u != 1 && !vis[fa])	vis[u] = vis[fa] = true;
}

int main(){
	int t;	scanf("%d", &t);
	while(t--) {
		scanf("%d%d", &n, &k);
		Init();
		for(int i = 2; i <= n; ++i) {
			int x;	scanf("%d", &x);
			G[x].pb(i), G[i].pb(x);
		}
		f = true, cnt = 0;
		Dfs(1, -1);
		for(int i = 1; i <= n; ++i) {
			if(!vis[i])	f = false;
		}
		if(f && n / 2 - 1 <= k) {
			puts("Bob");
		} else {
			puts("Alice");
		}
	}
	return 0;
}


1011

trick 有点疯狂阿、

自己写了两发WA掉了,队友一改就tm对了

题意:有三门课程,给出n个班级选择A课程人数,B课程人数,C课程人数,AB课程人数,BC课程人数,AC课程人数以及ABC课程人数,让你求一个所有班级中参加课程的人数最多的是多少,其中某些班级的数据有错误,可以忽略掉这个班级,保证至少有意组数据正确

思路:先判一下,求出答案后反判一下可以看下这组数据

5 5 5 5 5 5 0

这肯定是不对的

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define mst(a, b)	memset(a, b, sizeof a)
#define REP(i, x, n)	for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 2e5 + 10;
const int INF = 1e9 + 10;
int num[105][10];

int main(){
	int t;	scanf("%d", &t);
	while(t--) {
		int n;	scanf("%d", &n);
		int maxn = 0;
		for(int i = 1; i <= n; ++i) {
			for(int j = 1; j <= 7; ++j) {
				scanf("%d", &num[i][j]);
			}
			if(num[i][4] > min(num[i][1], num[i][2]))	continue;
			if(num[i][5] > min(num[i][2], num[i][3]))	continue;
			if(num[i][6] > min(num[i][1], num[i][3]))	continue;
			if(num[i][7] > min(num[i][4], min(num[i][5], num[i][6])))	continue;
			int ans = 0;
			for(int j = 1; j <= 7; ++j) {
				if(j >= 4 && j <= 6)	ans = ans - num[i][j];
				else	ans = ans + num[i][j];
			}
			if(ans - num[i][1] - num[i][2] + num[i][4] < 0)	continue;
			if(ans - num[i][2] - num[i][3] + num[i][5] < 0)	continue;
			if(ans - num[i][1] - num[i][3] + num[i][6] < 0)	continue;
			if(ans - num[i][4] - num[i][5] - num[i][6] + num[i][7] * 2 < 0)	continue;
			maxn = max(maxn, ans);
		}
		printf("%d\n", maxn);
	}
	return 0;
}