2022暑期个人训练赛第02场解题体会_欢迎来到异或王国,这是一个特殊的王国,对于一个数组它的价值并非所有数相加,而是

问题 B: 异或

题目描述

鸡尾酒获得了一个数组，他定义数组的价值为每个相邻元素异或之和。例如数组[3,5,9]的价值为(3^5)+(5^9)=18，其中^为二进制中的异或运算。
现在他将数组向右进行m次向右循环移动，每次移动bi位，循环移动都建立在上一次移动的基础上进行。现在他想考考你，每次循环移动过后，这个数组的价值为多少？
向右循环移动的定义：向右循环移动一位，数组中最右边的元素变成最左边的元素，其余元素全部向右移动一位。
例如数组[1,2,3,4,5]向右循环移动两位的结果是[4,5,1,2,3]。

输入

输入第一行包含两个正整数n和m，分别代表数组的长度和循环移动的次数。
接下来一行包含n个由空格隔开的正整数，分别表示数组中每个数字的长度。
接下来一行包含m个正整数，分别表示每次循环移动要移动的位数bi。

输出

先输出一个答案表示原来数组的价值，然后输出m个整数，表示对于每一次循环移位后，数组当前的价值。所有输出的整数用空格隔开。

思路：

先算出原数组异或和ans.用数组 l[ ] 维护数与其前驱的异或，用一个指针c标记数组首位的数，数组右移相当于指针左移，每次移动ans+=l[c],指针变换后，ans-=l[c]

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],l[N],r[N];
int main()
{
    int n,m,c,d;
    long long ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<n;i++) r[i]=a[i]^a[i+1];
    for(int i=2;i<=n;i++) l[i]=a[i]^a[i-1];
    l[1]=a[1]^a[n];r[n]=a[n]^a[1];
    for(int i=1;i<n;i++) ans+=r[i];
    c=1,d=n;
    printf("%lld ",ans);
    while(m--)
    {
        int x;
        scanf("%d",&x);
        ans+=l[c];
        c=(c-x+n*10000)%n;  //用10000处理x过大的情况
        if(!c) c=n;
        ans-=l[c];
        printf("%lld ",ans);
    }
    return 0;
}

tip:

注意用long long 否则会爆int

问题 C: 最大公约数

题目描述

鸡尾酒的数学很差，他学了很长时间的最大公约数，终于有一天他会求最大公约数了。
于是他迫不及待地向你提问——给定数轴上的区间[l,r]，你可以从中任选两个不相同的整数，求它们的最大公约数。请问它们的最大公约数最大为多少？

输入

输入两个正整数l，r，意义如题面所示。

输出

输出一行一个正整数表示答案。

思路：

想让公约数尽可能大，从i=2开始枚举，a=r/i,若(i-1)*a在区间[l，r]中，则a为最大公约数

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int l,r;
    scanf("%d%d",&l,&r);
    for(int i=2;;i++)
    {
        int a=r/i;
        if((i-1)*a>=l) {cout<<a;break;}
    }
    return 0;
}

问题 J: Recording the Moolympics

题目描述

Being a fan of all cold-weather sports (especially those involving cows),Farmer John wants to record as much of the upcoming winter Moolympics as possible.

The television schedule for the Moolympics consists of N different programs (1 <= N <= 150), each with a designated starting time and ending time.  FJ has a dual-tuner recorder that can record two programs simultaneously.
Please help him determine the maximum number of programs he can record in total. 

输入

* Line 1: The integer N.
* Lines 2..1+N: Each line contains the start and end time of a single  program (integers in the range 0..1,000,000,000).

输出

* Line 1: The maximum number of programs FJ can record.

题目大意：

有n个节目从时间从a-b，然后你有俩个录像器，求最多可以录几个节目

思路：一道贪心的题目。按结束时间升序排序。将录像器想象为从零开始的两条时间线。指针r1,r2记录第一,二条线的结束时间。将r1，r2初始化为0，然后按顺序对每一个节目进行判断。优先填到两条线中结束时间大的那一条(贪心核心思路)，都无法填入则舍弃。

代码：

#include <bits/stdc++.h>
using namespace std;
struct lx
{
    int s,e;
}a[155];
bool cmp(lx n,lx m)
{
    return n.e<m.e;
}
int main()
{
    int n,cnt=1;
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].s,&a[i].e);
    sort(a+1,a+n+1,cmp);
    int r1=a[1].e,r2=0;  //我写的时候先放入了第一个
    for(int i=2;i<=n;i++)  
    {
        if(r1>=r2&&a[i].s>=r1) {r1=a[i].e;cnt++;}
        else if(r1>=r2&&a[i].s<r1&&a[i].s>=r2) {r2=a[i].e;cnt++;}
        else if(r1<r2&&a[i].s>=r2) {r2=a[i].e;cnt++;}
         else if(r1<r2&&a[i].s<r2&&a[i].s>=r1) {r1=a[i].e;cnt++;}
    }
   cout<<cnt;
    return 0;
}

tip:

一开始我用的几个if来判断导致程序错误，因为每次判断后对r1,r2的值会改变，从而影响后面的if语句。以后记得用if else if语句

问题 N: Index Trio

题目描述

You are given an integer sequence A = (A1, ..., AN) of length N.Find the number of triplets of integers (i, j, k) satisfying all of the conditions below.
1 ≤ i, j, k ≤ N
Ai/Aj = Ak
Constraints
1 ≤ N ≤ 2 × 105
1 ≤ Ai ≤ 2 × 105 , (1 ≤ i ≤ N)
All values in input are integers.
 

输入

Input is given from Standard Input in the following format:
N
A1 ... AN
 

输出

Print the answer.

题目大意：

有长度为n的序列，求出数对(i, j, k)的数量，其中满足ai/aj=ak

思路：

用一个桶b[ ]记录每个数出现的次数，枚举所有的ai，求ai所有的分解x*y，ans+=b[x]*b[y]*2.对于x=y时要特判，因为此时(i,j,k)有j=k的情况。时间复杂度O(n*sqrt(n))

代码：

#include <iostream>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int a[N],b[N];
int main()
{
    int n;
    ll ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {scanf("%d",&a[i]);b[a[i]]++;}
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j*j<=a[i];j++)
        {
 
            if(a[i]%j==0&&j*j==a[i])
            ans+=(1ll*b[j]*(b[j]-1)+b[j])*1ll;
            if(a[i]%j==0&&j*j!=a[i])
            ans+=1ll*b[j]*b[a[i]/j]*2;
        }
    }
    printf("%lld",ans);
    return 0;
}

tip:1ll要乘在前面