2021年浙江理工大学新生赛同步赛

Problem K: nudun故事集之约会

Description

题目背景
时隔多年,赚了不少达不溜的zmw想要来一场甜甜的恋爱,于是乎他找到了万能的nudun。在情场高手mk23ez66的介绍下,挑选出了n个具有一定魅力值的小姐姐。虽然zmw都非常喜欢,但是并不是所有的小姐姐都想要与zmw进行约会。简而言之,对于第i个小姐姐,她同意与zmw进行约会的条件是从1到i-1中存在任意三个小姐姐的魅力值异或起来为第i个姐姐的魅力值。(可重复选择),现在,满脑子都是小姐姐的zmw想要你帮他计算他到底能和多少个小姐姐共度良宵。QwQQwQQwQ

题目描述
已知一个长为n的序列,序列的第i个数是a[i]。 如果a[i] (i>1)可以表示成a[1],a[2],...,a[i-1]中的任意三个数(同一个数可重复选择)的异或和,则称第i个数为“QwQ数”。现在让你求这个序列中有多少个数是“QwQ数”。
异或(xor)运算规则:在二进制下按位异或,对于每一位 0 xor 0 = 1 xor 1 = 0,1 xor 0 = 0 xor 1 = 1
例如:2 xor 3 xor 5 = (010) xor (011) xor (101) = (100) =4

Input

第一行输入两个正整数n(1<=n<=5000)
第二行输入n个正整数a[i] (0<=a[i]<2^20)

Output

第一行输出“QwQ数”的个数

Sample Input

5
1 2 3 0 3

Sample Output

2

HINT

说明/提示

对于第一组样例:

2不能表示成三个1的异或和,所以a[2]不是“QwQ数”

3不能表示成三个1或2的异或和,所以a[3]不是“QwQ数”

0 = 1 xor 2 xor 3,所以a[4]是“QwQ数”

3 = 1 xor 1 xor 3 , 2 xor 2 xor 3 , 1 xor 2 xor 0 , 3 xor 3 xor 3 , 3 xor 0 xor 0,所以a[5]是“QwQ数”

直接循环 

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
	int n,num=0;
	cin>>n;
	int a[10000];
	int dis[10000]={0};
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<n;i++)
	{
		for(int j=0;j<i;j++)
		{
			for(int k=0;k<i;k++)
			{
				for(int m=0;m<i;m++)
				{
					if(!dis[i]&&a[i]==(a[j]^a[k]^a[m]))
					{
						dis[i]=1;
						num++;
						//cout<<(a[j]^a[k]^a[m])<<" "<<a[i]<<endl;
					}
				}
			}
		}
	}
	cout<<num;
	return 0;
}

Problem B: nudun故事集之ATM发现了”st”

Description

题目背景
一天,群友说到:“st!”。ATM很疑惑,“到底啥是st呢?”。于是ATM找到了万能的nudun。由于懂得都懂的原因,nudun不能直接告诉ATM什么是“st”,但是nudun在1秒钟之内产生了13个st,并用了一种神奇的加密方式表示。

题目描述
首先nudun产生了一个数组长度为n的a,并给了m次操作,每次操作给出一个区间[l,r],并将区间内的所有数与运算上w。最后的数组a就是解压的密码。
与运算规则:对于二进制下第i位的a与b进行与操作。
例如,3&2=1,(11)2&(10)2=1 请帮在1秒钟内帮助ATM解决这个问题,作为答谢他会给你一份“st!”。

Input

第一行输入n,m,表示长度为n的数组,和m次操作(1<=n,m<=1e5)
第二行有n个数,第i个数表示a[i](a[i]<=1e18)
接下来的m行每行三个整数,l,r,w(1<=l<=r<=n,w<=1e18)

Output

输出n个数,表示最后的数组a

Sample Input

2 4
3 0 
1 1 5
2 2 2
1 2 2
1 2 5

Sample Output

0 0

HINT

样例解释: 3&5=1,0&2=0,1&2=0,而之后0无论如何操作结果都是0,所以答案是0 0

这是破解样例后产生的“st”。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a[100000];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	while(m--)
	{
		int l,r;
		ll w;
		cin>>l>>r>>w;
		for(int i=l;i<=r;i++)
		{
			if(a[i])
				a[i]&=w;
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<a[i]<<" ";
	}
	return 0;
}

 

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码

)">
< <上一篇
下一篇>>