ai智工作室22级第三次训练赛

（1）进制转化  51Nod - 2130

https://www.51nod.com/Challenge/Problem.html#problemId=2130

输入一个十进制整数n，和一个进制b，输出b进制下的n。

0 <= n <= 10^9
2 <= b <= 16

Input

一行两个整数n，b。

Output

一行一个字符串，表示进制转换后的结果。 特别注意对于超过10进制的11至16进制。 如果一位数字是10 11 12 13 14 15，我们用ABCDEF来代替。

Sample

267242409 16

FEDCBA9

#include<stdio.h>
int main()
{
	int a,b,i,count=0;
	char arr[100];
	scanf("%d",&a);
	scanf("%d",&b);
	do{
		arr[count]=a%b;
		a=a/b;
		++count;
	}while(a!=0);
	
	for(i=count-1;i>=0;i--)
	{
		if(arr[i]>9)
		{
		printf("%c",arr[i]-10+'A');//这里解释一下arr[]数组里存储的是ASCII，
		//比如说第一位arr[0]存储的是13这个数字对应的ASCII值，计算机内部存在自动转换， 
		//arr[i]-10+'A'通过这个操作可以实现（2-36）进制的转换 
		}
		else
		printf("%d",arr[i]);
	}
	printf("\n");
}

（2）CodeForces - 734B 

Inose Mai 喜欢256和32这两个数字，他觉得这两个数字是他的幸运数字。
有一天Inose Mai从儿时的玩具里面发现了很多数字积木块，每个积木块上都只含有0-9这几个数字中的某个数。他把所有含2、3、5、6的数字积木块都找了出来，发现里面共有a1个2、a2个3、a3个5、a4个6。Inose Mai想用它们来组成自己的幸运数字，他希望组出来的幸运数字的总和最大。请你帮Inose Mai完成这个任务。
注意：每个数字最多只能使用1次，也就是2、3、5、6被使用的次数分别不能超过a1、a2、a3、a4次。当然，没有使用过的数字不能计算在总和之内。

输入

输入共包含多组测试数据。
每组测试数据的输入包含四个整数a1、a2、a3、a4 (1 ≤ a1、a2、a3、a4 ≤ 5×10^6)，分别表示 Inose Mai 拥有的2、3、5、6数字积木块的个数。

输出

对于每组测试数据，输出一个整数，表示这些数字积木块组出来的幸运数字总和的最大值。

样例

输入样例1    输出样例1                                       输入样例2    输出样例2

10 2 1 5    320                              4 2 7 2     576

输入样例3                 输出样例3                     输入样例4              输出样例4

489 292 127 263    41856                0 0 0 0            0

输入样例5                输出样例5

2 1 1 1              288

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a1,a2,a3,a4,min1,min2,res=0;//2,3,5,6
	scanf("%d%d%d%d",&a1,&a2,&a3,&a4);
	min1=min(min(a1,a3),a4);
	a1-=min1;
	min2=min(a1,a2);
	res=min1*256+min2*32;
	printf("%d\n",res);
 } 
 //题目要求输入4个数字a1,a2,a3,a4 
 //分别表示2 3 5 6积木块数量的个数
 //题目要求输出这些积木块组成的幸运数字所组成的最大值之和 
 //我们先找256，因为他最大,决定 能组成几个256的是2,5,6积木块中最少的数量 
 //用min1记录积木2,3,5中积木数量最少的块数 
 // 拼完256的积木块，2的数量就减少
 //接下来找组成32的积木块数，同理，由3，或修改的2中最小的数量决定
 //说一句谚语，决定水桶能承多少水的不取决于最长的挡板，取决于最小的挡板。 

（3）AtCoder - arc068_b 

D - Card Eater

C - 思维/模拟题-1

为了离成功更进一步

你需要向秦始皇献上种类不同的思维宝石，数量越多越好

而思维宝石只能从宇宙机协会拿取，只能拿一次，一次拿N个

每个思维宝石上都有对应种类序列号

你每次可以取出其中3个，丢掉序列号最大的和序列号最小的宝石，把中间那个再放回宝石堆

要求最后所有剩余宝石堆里的宝石序列号互不相同，求最多能剩几个宝石

Constraints

• 3 ≦ N ≦ 10^{5}3≦N≦105
• 1 ≦ A_i ≦ 10^{5}1≦Ai​≦105

Input

标准输入，格式如下:

NN
A_1A1​ A_2A2​ A_3A3​ ... A_{N}AN​

Output

输出答案

Sample 1

5
1 2 1 3 7

3

一个最佳解决方案是执行一次操作，取出两个1的宝石和一个2的宝石

一个带1的和另一个带2的将被丢掉，剩下的带1的将被送回宝石堆

然后，剩余的宝石所带序列各不相同为1，3，7，结束，最多还剩3个

Sample 2

15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1

7

#include<iostream>
using namespace std;
//题目大意是将先输入n表示有n个宝石，然后输入每个宝石的序号
//分析一下，每次取出三个宝石并且将2个宝石扔掉，另外一个宝石放回，
//既然宝石放回，可以等价于每次从宝石堆中取出2个宝石并且扔掉
//存在2种情况
//1,扔掉的2个宝石是同一序号的  
//2,扔掉的2个宝石是不同序号的  
//题目要求最后所有剩余宝石堆里的宝石序列号互不相同，求最多能剩几个宝石
//想一下，最多能剩 ，最好的情况是扔掉的2个宝石序号的相同的，扔到最后
//存在2种情况 
//1，恰巧把所有相同的宝石都扔完,剩下宝石中没有重复序号的宝石 
//2, 把所有相同的宝石都扔完后，发现抽出的堆中有1个宝石剩余，
//那就将这个宝石扔掉，再从原本堆中任意抽取扔掉一个 
//以下代码来模拟一下 
// 先用数组a全部存储0，用于做标记,用t来记录出现重复数的数量,
//  如果输入的数字在之前未出现过，则标记为1，当下次出现时候就会识别不等于0，记录为重复的数字，t++ 
//最后遍历完后，t记录的是重复的数量
//t有2种情况，当t能被2整除时,是第一种情况，t个宝石都是成对出现的，扔完后，n-t就是剩下的宝石数量 
//当t不能被整除，这时候需要从剩下牌堆中多抽取一张丢弃，这时候就是丢掉t+1张牌，剩下牌数量就是n-（t+1） 
int main()
{
	int n,a[100005]={0},b,t=0;
	scanf("%d",&n);//先输入宝石数量n 
	for(int i=0;i<n;i++)// 
	{
		scanf("%d",&b);//用 
		if(a[b]!=0) t++;
		else if(a[b]==0) a[b]=1;
	}
	if(t%2==0) printf("%d\n",n-t);
	else if(t%2==1) printf("%d\n",n-t-1);
	
 } 

（4）AtCoder - arc070_a 

Atcoder 

C - Go Home

当香槟装瓶，进行二次发酵时，汽泡就留在瓶内跑不掉了。但是瓶内的压力逐渐增强，沉淀物也逐渐发现

为了能把沉淀物取出而不使二氧化碳外泄

要把所有的瓶子以口朝下倒过来放置，每天派人轻轻摇晃酒瓶，好让沉淀残渣朝着瓶口方向集中；这项精细筛分工作必须极有耐心，粗鲁不得

假设进度为0开始，秒数开始为1

在第i秒，只能进行以下3种操作中的1种

向左摇会使进度-i

向右摇会使进度+i

也可以不摇，进度不发生变化

问进度为x的最小时间，超过x的不算是

如要求进度x为7，而你预想步骤得到的x为8，这是失败的

Constraints

• XX is an integer.
• 1≤X≤10^91≤X≤109

Input

标准输入，格式如下:

XX

Output

输出最小时间 XX.

Sample 1

6

3

Sample 2

2

2

Sample 3

11

5

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
//题目跳出条件是当这个人向右走恰好走到s就结束
//而他走的位移和时间呈现 x=t，他可以选择不走，向右走，向左走，我们要想在最短时间内走到制定位移
//最好是向右走，或者不走，向左走，时间肯定就长了，那么我们可以选择向右走或者不走
//在for中，sum表示累加走过的位移，如果sum大于或者等于s，就终止，输出当前的时间 
//想一下，当时我们此时走的路程是超出需要的这个范围的呀!
//实际上，超出的这部分差值，在前面是走过的，因为时间是每一秒每一秒的增长的，每秒走的路程是成x=t的函数的。
//举个例子，比如说你要输入的数字是11，输出的数字是5秒
//正常来说，如果一直往右走，第一秒走1m，第二秒走2m，第三秒走3m，第4秒走4m，第5秒走5m
//1+2+3+4+5=15,如果你一直往右走，第5秒时候是走15m的，但题目要求是走11m，这时候，你转换一下思路，
//15-11=4,如果你第四秒不走，选择停止，那么你时间还是5秒，只不过你第四秒不走。 你走的路程是11米 
int main()
{
	int s=0,sum=0,d,a[9999]={0},k=0;
	scanf("%d",&s);//输入这个人想要走的路程 
	for(int t=1;t<=s;t++)
	{ 
        sum+=t;k++;
        if(sum>=s) 
		{
			
		break;
		} 
		
	}
	printf("%d\n",k);
}

（5）并查集 北京大学-2524

2524 -- Ubiquitous Religions

当今世界上有许多不同的明星，你想知道你们学校的学生总共喜欢多少个不同的明星。
你知道你的大学里有n个学生(0 < n ≤ 50000)，你问每个学生他们喜欢的明星是不可能的。此外，许多学生不好意思说出他们喜欢哪个明星。避免这些问题的一种方法是问m (0≤ m ≤ n(n-1)/2)对学生，问他们是否喜欢相同的明星(例如，他们可能知道他们是否观看同一场演出)。从这些数据中，你可能不知道每个人具体喜欢哪个明星，但你可以知道校园里最多有多少个不同的被喜欢的明星。你可以假设每个学生最喜欢的只有一个明星。

输入

输入由多组用例组成。每一种情况都以整数n和m作为的一行开始，接下来的m行分别由两个整数i和j组成，表示学生i和j喜欢相同的明星。学生被编号为1到n。输入的结束由一行指定，其中n = m = 0。

输出

对于每个测试用例，在单行上打印案例号(以1开头)，后面跟着该大学学生所喜欢的不同明星的最大数量。

样例输入

10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0

样例输出

Case 1: 1
Case 2: 7

#include<iostream>
using namespace std;
int fa[50004];
int find(int x)
{
	int x_fa;
	if (fa[x] == x) return x;
	else
	{
		x_fa = find(fa[x]);
		fa[x] = x_fa;
		return fa[x];
	}
 
}
void join(int a, int b)
{
	int a_fa, b_fa;
	a_fa = find(a);
	b_fa = find(b);
	fa[a_fa] = b_fa;
}
 
int main()
{
	int n, m, k = 0, j = 0;
	scanf("%d%d",&n,&m);
	while (n && m)
	{
		k = 0;
		for (int i = 1; i <= n; i++)
			fa[i] = i;
 
		for (int i = 1; i <= m; i++)
		{
			int a, b;
				scanf("%d%d",&a,&b); join(a, b);
 
		}
		for (int i = 1; i <= n; i++)//n个人最多有n个不同的祖先，每个祖先代表一个种类的棒冰，如果a[2]=3，a[3]=3,那么2和3就算1个祖先，是3，从第一个祖先开始遍历
			if (fa[i] == i)k++;
		printf("Case %d: %d\n", ++j, k);
		cin >> n >> m;
	}
	return 0;
}

并查集的模板我讲过了，我放链接在这下面

教授先生带你学习并查集_教授先生的博客-CSDN博客

这个是汤学长为我们同学准备的代码和题解：

https://www.yuque.com/docs/share/c2df161b-d4c2-4a8a-8545-0e01c5894a4e?#

《讲题-2》