huas2021届圣诞杯题解
b用来标记第i个朋友是否知道；
易错点：朋友都是1到n，而数组是从0开始的，所以数组要开b[100001]以上才能访问b[100000]；
很多同学只开了b[100000]就只有b[0~99999]，找就会b[100000]报错;
int a[100005];
int b[100005];
//数组定义在全局时 默认全部是0；
int main()
{
int n,x;
scanf("%d%d",&n,&x);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);//储存第i个朋友最好的朋友。
int sum=0;
while(b[x]==0)//判断x是不是知道了，已经知道就结束循环了。
{
b[x]++;//标记已经知道了。
x=a[x];//准备访问x的好朋友。
sum++;//计数
}
printf("%d",sum);
return 0;
}B.超级减肥药
题解：
异或运算：在二进制下，0^0=1,1^1=0,0^1=1,1^0=1.
不难发现，当一个数的最高位1与同位置的1异或后，得到的数一定小于本身。所以只需要反复找N中的1位然后与该位置为1的数异或，结果一定小于本身。最后需要注意数在区间l-r即可。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a,b,k;
int main()
{
cin>>n>>a>>b;
for (int i=60; i>=0; i--)
if((n>>i)&1) //位运算 按位取 如果第i位为1的话
k+=max(0ll,min(b+1,1ll<<i+1)-max(a,1ll<<i));//判断2的i+1次方与右边界
//判断2的i次方与左边界
//相减即为答案
cout<<k<<endl;
}C.字符串的小匹配
此题的关键就是字符串必须要交换一次
所以我们先遍历一下字符串把与目标字符串不相同的字符都取出来
1.如果不相同的位置不等于2个 直接输出NO
2.如果不相同的位置等于2 判断一下 四个位置交换匹配一下是否相等
详情见代码注释。
#include <iostream>
#include <cstring>
using namespace std;
int c[30]; /// 用于记录每种字符出现的次数（当没有位置字符不相等的时候判断是否存在某一个字符出现过多次）
int main(){
string s1, s2; /// C++ 提供的字符串对象
int t; cin >> t;
while(t --) { /// t 组案例
cin >> s1 >> s2; /// 读入字符串
if(s1.length() != s2.length()) { /// 长度不同必不相等
cout << "No" << endl;
continue;
}
memset(c, 0, sizeof(c)); /// 重置 c 数组为 0
char a1, a2, b1, b2; /// 记录两个不同位置的 s1 s2 字符串中字符
int sum = 0; /// 记录不同的位置的个数
for(int i = 0; i < s1.length(); i ++) {
c[s1[i] - 'a'] ++; /// 对 s1 进行字符计数
if(s1[i] == s2[i]) continue;
sum ++; /// 不相同字符位置数 +1
if(sum > 2) break; /// 超过两个位置不同
else if(sum == 1) a1 = s1[i], a2 = s2[i]; /// 记录第一个不同位置
else b1 = s1[i], b2 = s2[i]; /// 记录第二个不同位置
}
int p = 1; /// 标记答案，默认为正确
if(sum == 0) { /// 如果两个字符串相等
p = 0;
for(int i = 0; i < 26; i ++)
if(c[i] >= 2) p = 1; /// 存在两个字符相同
} else if(sum != 2) p = 0; /// 没有刚好两个位置不同
else if(a1 != b2 || b1 != a2) p = 0; /// 刚好有两个位置不同但交换后还是不同
if(p) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}D.爱数学的阿威学长
杨会长出的。
题解：主要考察了如何去进行差分来优化3个for嵌套枚举的时间复杂度
考察了算法：差分+前缀和
#include <cstring>
#include <bitset>
#include <iostream>
#include <algorithm>
#define pb push_back
#include<bits/stdc++.h>
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define X first
#define Y second
#define inf 0x3f3f3f3f
//The desire of his soul is the prophecy of his fate.
// 灵 魂 的 渴 望 是 你 命 运 的 先 知 。
using namespace std;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
typedef long long ll;
typedef pair<int, int>PII;
typedef pair<ll, ll>PLL;
ll f[N];
vector<char>ans;
int main() {
SIS;
int a, b, c, d;
cin >> a >> b >> c >> d;
for (int i = a; i <= b ; i ++)//对区间进行差分
{
f[i + b]++;
f[i + c + 1]--;
}
for (int i = 1 ; i <= 2e6 + 2 ; i ++ )f[i] += f[i - 1];
//先进行一遍前缀和 此时f[i]表示由a，b组成的i的方案数
for (int i = 1 ; i <= 2e6 + 2 ; i ++ )f[i] += f[i - 1];
//第二次前缀和，处理处f[i]前面所有的方案数
ll ans = 0;
//由2条小边要组成三角形可知 ：a + b >= c
//所以这里的for 遍历一遍所有的大于c边的方案数
for (int i = c ; i <= d; i ++ ) ans += f[2000000] - f[i];//把答案累加起来
cout << ans << endl;//输出答案
return 0;
}题解：大家在高中学过的椭圆的性质：
在椭圆上任意一点到左右端点的斜率乘积为
#include <stdio.h>
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int T;
scanf("%d", &T);
while (T --)
{
int A, B; scanf("%d %d", &A, &B);
int y, x; scanf("%d/%d", &y, &x);
int Up = B * B * x;
int Down = A * A * y;
int Redu = gcd(Up, Down);
Up /= Redu;
Down /= Redu;
printf("-%d/%dn", Up, Down);
}
return 0;
}F.秦始皇の诺言
题解：纯数学，利用海伦公式或者其他cos、sin都可以。
G.阿威的心情
差分+前缀和算法模板
算法详情自己去百度~~~
#include <cstring>
#include <bitset>
#include <iostream>
#include <algorithm>
#define pb push_back
#include<bits/stdc++.h>
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define X first
#define Y second
#define inf 0x3f3f3f3f
//The desire of his soul is the prophecy of his fate.
// 灵 魂 的 渴 望 是 你 命 运 的 先 知 。
using namespace std;
const int N = 3e6 + 7;
const int mod = 1e9 + 7;
int a[N];
int main() {
SIS;
int n, m;
cin >> n >> m;
for (int i = 1; i <= m ; i ++ ) {
int x, y;
cin >> x >> y;//c++输入流方式
if (x > y)swap(x, y); //输出不一定是严格x<y的需要特判一下
a[x] ++; //差分对[x,y]区间
a[y + 1]--;
}
for (int i = 1; i <= n ; i ++ ) {
a[i] = a[i] + a[i - 1]; //前缀和 统计所有被涂黑的格子
}
int flag = 0;//用来判断左右区间的端点
int i;
for (i = 1; i <= n ; i ++ ) {
if (flag == 0 && a[i] == 0)//如果flag为0并且遇到了一个没被涂黑的点 则为左端点
{
flag = 1;//标记下一次寻找右端点
cout << i << " "; //输出左端点
} else if (flag == 1 && a[i] != 0)//如果遇到了涂黑的点并且找的是右端点 则输出前一个点
{
cout << i - 1 << endl; //输出
flag = 0; //标记下一次寻找左端点
}
}
if (flag == 1) cout << i - 1 << endl;//最后要判断一下是否左右端点匹配 否则再输出一次左端点
return 0;
}
/*
*/H.我猜我是个签到题
签到题 卡了c++的输入
因为：
c语言的读入输出一般是最快的（scanf printf）
c++语言的读入输出相对较慢（cin cout）
其时间差在十倍左右，我们认为测评机一秒仅能使用 C++ 的读入输出的级别在 1e6 以下。
所以大家写题目超时时要检查是不是输入太大用了cin
I.要微信？
题解：博弈论（思维）
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,n,m,k;
scanf("%d",&t);//输入T组样例
while(t--)
{
scanf("%d%d%d",&n,&m,&k);//输入n,m,k 分别表示孙会长和阿威的点券和能最多一次用的点券
//因为每次孙会长和阿威用点券的范围都在[1,k],故第一个人不管怎么取第二个人都可以凑成
//(k+1)个点券，例如孙会长取x个点券则阿威可以取(k+1-x)个点券使和凑成k+1。
//所以我们不难发现如果总数（n+m）是k的整数倍我们可以拆成若干个（k+1）每次都由阿威凑
//此时无论如何都是阿威取到第k+1个（因为是整数倍，不影响结果），故（n+m）%（k+1）==0
//时，阿威必胜。设p=(n+m)%(k+1),否则孙会长就会取p个点券使游戏结果和前面相反（此时为
//阿威取，不过此时总点券数量为（k+1）整数倍所以孙会长必胜。
if((n+m)%(k+1)==0)//总数为(k+1)倍数，阿威必胜
printf("sunn");
else
printf("wein");
}
return 0;
}J.原来你也玩原神
题解：博弈论（思维）
思路：由于9 99 999......互相转化都是奇数次操作，所以无论怎么操作结果均不会改变，
所以只要求出每个数除9的值x，如果这个数是9的倍数，则为x-1，在把这些值相加，最后判断奇偶即可。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--){
long long m=0;
int n;
cin>>n;
for(int i=0,x;i<n;i++){
cin>>x;
m+=x/9; //每次把9的倍数取出来 代表最多能取多少次
if(x%9==0)m--;//又因为不能一次取完，所以判断如果是9的倍数我就少取一次
}
if(m%2!=0)puts("b");
else puts("a");
}
return 0;
}大家有啥不懂的在群里@孙会长！！！
这次比赛比预期的难，没发挥好的也不要泄气，毕竟大家都才开始学。
大家好好加油，之后还有月赛，校赛等。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
二维码