2022睿抗CAIP赛道本科组省赛题解

RC-u1 不要浪费金币

思路：简单模拟题，送分的拼手速。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
using namespace std;

int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int n,m;
	cin>>n>>m;
	int sum=0;
	int cnt=0;
	for(int i=1;i<=n;i++){
		int val;
		cin>>val;
		if(sum+val>m){
			sum=val;
			cnt++; 
			continue;
		}
		else sum+=val;
	}
	cout<<cnt;
	return 0;
}

RC-u2 智能服药助手

思路：简单的模拟题，送分的拼手速。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
using namespace std;
const int N=1e3+7;
int last[N]; //第i种药上次吃的时间
int gap[N];//间隔
int n,m;
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>gap[i];
		last[i]=-gap[i]-500;
	}
	for(int i=1;i<=m;i++){
		int t,k;
		cin>>t>>k;
		while(k--){
			int v;
			cin>>v;
			if(gap[v]!=-1&&t-last[v]<gap[v]){
				printf("Don't take %d at %d!\n",v,t);//注意格式化输出
			}
			else last[v]=t;
		}
	}
	return 0;
}

RC-u3 跑团机器人

思路：很恶心的PAT风格字符串处理题，将字符串按\(+1|+2d3|-3\) 这样分，然后处理一下就可以了，注意到为了使最小值尽量的小，遇到见\(-2d3\) 这种，就要选\(2*3\) ，遇到\(2d3\) ，就让最大值加\(2*3\) ，反正尽可能的贪就可以了。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int N=2e4+7;
ll use[N];
ll maxval,minval;
vector<string> t;
string s;
void split(){
	string tt;
	int j=0;
	while(j<s.size()){
		if(s[j]=='-'||s[j]=='+'){
			t.push_back(tt);
			tt=s[j];
			j++;
			continue;
		}
		tt+=s[j];
		j++;
	}
	if(tt!="")t.push_back(tt);
	return;
} 

ll tol(const string& k,int l,int r){
	ll sum=0;
	ll base=1;
	for(int i=r;i>=l;i--){
		sum+=base*(k[i]-'0');
		base*=10;
	}
	return sum;
}
int main(){
	cin>>s;
	split();
	if(t[0][0]!='-'){
		t[0].insert(0,"+");
	}
	for(auto v:t){
		int dpos=v.find('d');
		int flag=v[0];
		if(dpos==-1){
			if(flag=='-'){
				maxval+=tol(v,1,v.size()-1)*-1;
				minval+=tol(v,1,v.size()-1)*-1;	
			}
			else{
				maxval+=tol(v,1,v.size()-1);
				minval+=tol(v,1,v.size()-1);
			}
		}
		else{
			ll left,right;
			if(dpos==0||dpos==1)left=1;
			else left=tol(v,1,dpos-1);
			right=tol(v,dpos+1,v.size()-1);
			use[right]+=left;
			if(flag=='-'){
				maxval-=left;
				minval-=right*left;
			}
			else{
				maxval+=right*left;
				minval+=left;
			}		
		}
	}
	for(int i=2;i<=1000;i++){
		if(use[i])cout<<i<<" "<<use[i]<<"\n";
	}
	cout<<minval<<" "<<maxval;
    return 0;
}

RC-u4 攻略分队

思路：贪心很麻烦，如果模拟处理更麻烦，考虑队伍数只有\(6\) 个，每个队要么是讨伐欧文要么是讨伐亚特的，只有两种状态，所以只有\(2^6=64\) 种排列方式。只需要二进制枚举然后不断检测即可。我们规定\(0\) 是欧文，\(1\) 是亚特，

​ 我们令\((MT,工兵,指挥)\) 也为一个二进制表达方式，记其十进制表达式为一个队伍的「特殊值」。

\((1)\)要将所有队伍分成 2 组，每支队伍必须且仅属于其中一组\(→\) 全\(0\) 和全\(1\) 不行

\((2)\)每组必须有至少一个 MT（主坦克）→ 每组至少要有一个特殊值大于\(\ge100=4\) 的

\((3)\)优先选择每组有至少一个指挥和至少一个工兵的方案→每组至少有一个特殊值\(011(3)/111(7)\) 的

\((4)\)如果规则 1 无法满足，则优先选择每组至少有一个指挥的方案→每组至少有一个特殊值为奇数 的

\((5)\)如果所有方案都不满足规则 2，或经过前 2 个规则筛选后，分组方案仍不唯一，则选择两边人数尽可能接近（即两边人数差尽可能小）的方案→枚举的二进制方案\(0\) 和\(1\) 的队伍人数数量尽可能相等

\((6)\)如果满足规则 3 的方案不唯一，选讨伐欧文的人数大于等于讨伐亚特的方案→\(0\) 的队伍人数比\(1\) 的多。

\((7)\)如果满足规则 4 的方案不唯一，选讨伐“欧文”的队伍编号方案中最小的一个→转字符串比对即可

因此，我们对着一步一步来有以下操作：

\((1)\) 枚举的时候不再枚举\(0,2^6-1\) ，但设置答案的时候先初始化为\(0\)

\((2)\) 统计\(0,1\) 的队伍对应有没有特殊值大于\(4\) 的， 如果这点不满足返回。

\((3)\) 说明这个方案合法，然后再枚举这个方案和最优解方案是否都有特殊值大于\(3\) 的，如果只有这个方案有，这将这个方案设为最优解，返回。

\((4)\) 如果\((3)\) 两个解都没有或者都有（即相等），判断是否都有大于\(1\) 的，如果只有这个方案有，设为最优解并返回

\((5)\) 如果\((4)\) 两个解都没有或者都有（即相等），枚举两边\(0,1\) 对应队伍人数数量差，选择较小的一个

\((6)\) 如果\((5)\) 两个解都一样的话，选择\(0\) 的数量比\(1\) 多的。

\((7)\) 同理，说明两个解都是攻打欧文人数比较多的，取两者\(0\)队字符串，选字典序较小的一个。

​ 这么分析下来，变转为简单的判断题，这就是思维的魅力。然后我们发现其实我们只需要知道一个方案两个分组的信息，一个分组某个兵种只要有一个队伍有就是有，所以容易想到或操作。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#include <iostream>
#include <bitset>
using namespace std;
const int N = 15;
int cnt[N];//第i个队伍的人数 
int s[N];//第i个队伍的特殊值 
bitset<6> ans;
int tj[N];//第i个条件是否满足或者具体值
string vrank;
string ansrank = "11111111111111111";
void turn(bitset<6>v, int vtj[]) { //改变为最优解
	ans = v;
	for (int i = 0;i < 8;i++) { //这个方案是一个最优解 
		tj[i] = vtj[i];
	}
	ansrank = vrank;
	return;
}
void judge(bitset<6> v) {
	int vtj[8] = { 0,0,0,0,0,0,0,0 };
	int sp[2] = { 0,0 };
	int c[2] = { 0,0 };//0 /1 队伍人数
	vrank = "";
	string vv = v.to_string();
	for (int i = 0;i < vv.size();i++) {
		int id = vv[i] - '0';
		sp[id] |= s[i + 1];
		c[id] += cnt[i + 1];
		if (id == 0)vrank += (i + 1 + '0');
	}
	vtj[2] = (sp[0] >= 4) && (sp[1] >= 4);
	vtj[3] = (sp[0] == 3 || sp[0] == 7) && (sp[1] == 3 || sp[1] == 7);
	vtj[4] = (sp[0] & 1) && (sp[1] & 1);
	vtj[5] = -1 * abs(c[0] - c[1]);
	vtj[6] = (c[0] >= c[1]);
	for (int i = 2;i <= 6;i++) {
		if (tj[i] == vtj[i])continue;
		if (vtj[i] > tj[i])turn(v, vtj);
		else return;
	}
	if (vrank < ansrank) { //比较0队的字典序
		turn(v, vtj);
	}
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n = 6;
	for (int i = 1;i <= n;i++)cin >> cnt[i];
	for (int i = 1;i <= n;i++) {
		char x, y, z;
		cin >> x >> y >> z;
		s[i] += z - '0';
		s[i] += (y - '0') * 2;
		s[i] += (x - '0') * 4;
	}
	for (int i = 1;i < 63;i++) {
		bitset<6> v(i);
		judge(v);
	}
	if (!tj[2])  //当第2个条件不满足时，不行。
		cout << "GG\n";
		return 0;
	}
	string posans = ans.to_string();//用于定位
	int ok = 0;
	for (int i = 0;i < posans.size();i++) {
		if (posans[i] == '0' && cnt[i + 1] > 0) {
			if (ok)cout << " ";
			ok = 1;
			cout << i + 1;
		}
	}
	cout << "\n";
	ok = 0;
	for (int i = 0;i < posans.size();i++) {
		if (posans[i] == '1'&&cnt[i+1]>0) {
			if (ok)cout << " ";
			ok = 1;
			cout << i + 1;
		}
	}
	return 0;
}

RC-u5 树与二分图

思路：一颗树必定是二分图（一个节点和他父亲所相连，而一个节点仅被其父亲连接），设两个集合的点数分别为\(m,(n-m)\) ，则二分图的最大边数是\(n*(n-m)\) ，又根据容斥原理，我们可以先算出最大边数，然后容斥掉已经有了的边即可。

​ 那如何求出\(m\) 呢，我们已经知道求二分图就将一张图染色，我们不妨求出\(1\) 的颜色数量为\(m\) ，这样就能得到了，总数量为\(n*(n-m)\) ，然后由于已经有了\(n-1\) 条边，所以就可以得出答案。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <iostream>
using namespace std;
typedef long long ll;
const int N=1e6+7;
struct node{
	int to,next;
}edge[2*N];
int head[2*N];
int cnt;
void add(int x,int y){
	edge[++cnt].to=y;
	edge[cnt].next=head[x];
	head[x]=cnt;
}
ll n,m;
int color[N];
void dfs(int u,int c){ //二分图模板
	color[u]=c;
	if(c==1)m++;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(color[v]==0)dfs(v,3-c);
	}
} 

int main(){
	ios::sync_with_stdio(false),cin.tie(0); 
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x); 
	}
	dfs(1,1);
	cout<<m*(n-m)-(n-1);
	return 0;
}
comments powered by Disqus
© 2022 - 2023 羽肿的个人博客
Built with Hugo
主题 Stack 由 Jimmy 设计