头像

dadidididi

珂学院




离线:11分钟前


最近来访(20)
用户头像
Cold_heartless
用户头像
一万小时定律
用户头像
铃兰の顶点
用户头像
ambie
用户头像
acwing_7869
用户头像
wzx110404
用户头像
max2021
用户头像
福宝j
用户头像
AcWing2AK
用户头像
ZacharyG
用户头像
胡xx
用户头像
来时山有雪
用户头像
xhgua
用户头像
游弋人生小号

新鲜事 原文

图片


新鲜事 原文

图片



更好的阅读体验

异或的一个性质:如果对一个数异或了两次就相当于不异或。

所以我们可以用前缀和预处理 $a[i]\oplus =a[i-1]$

$i$ 至 $j$ 的异或和为 $a[j]\oplus a[i-1]$

该连续子数组的前一半元素的异或和等于其后一半元素的异或和。

即该连续子数组的异或和为 $0$ 。

暴力的解法:

#include<bits/stdc++.h>
using namespace std;
int n,tot,b;
int a[300001];
int f[300001];
int main()
{
  cin>>n;
  for(int i=1; i<=n; i++)
  {
    cin>>b;
    a[i]=a[i-1]^b;
    for(int j=i-1; j>=1; j-=2)
    {
      if(a[i]==a[j-1])
      {
        tot+=f[j-1];
        tot++;
        f[i]=f[j-1]+1;
        break;
      }
    }
  }
  cout<<tot<<endl;
}

优化:

观察数据范围, $1<<20$ ,可以接受。

于是我们开一个数组 $mp[2][(1<<20)+1]$ ,第一维是长度为奇数(1)或偶数(0),第二维是前缀和为 $x$ 的个数。

开第一维的原因是满足该连续子数组的长度为偶数(奇奇为偶)。

所以每对一个前缀和就判断和它相同值的个数,并计入答案。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,tot,b;
int a[300001];
int mp[2][(1<<20)+1];
signed main()
{
  cin>>n;
  mp[0][0]=1;
  for(int i=1; i<=n; i++)
  {
    cin>>b;
    a[i]=a[i-1]^b;
    tot+=mp[i&1][a[i]];
    mp[i&1][a[i]]++;
  }
  cout<<tot<<endl;
}


新鲜事 原文

图片



时间: $ O(a) $ 。

直接枚举 $ x $ 并判断即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b;
int cnt,n;
signed main()
{
  cin>>a>>b;
  cin>>n;
  for(int i=0; i<=a; i++)
  {
    if(n-i<=b&&n-i>=0)
    {
      cnt++;
    }
  }
  cout<<cnt<<endl;
}



时间: $ O(a.size()) $ 。

直接用栈模拟即可。

#include<bits/stdc++.h>
using namespace std;
string a,b,c;
int op=0,tot;
char ch[11111111];
int top;
int main()
{
  cin>>a;
  for(int i=0; i<a.size(); i++)
  {
    if(ch[top]==a[i])
    {
      top--;
      op^=1;
    }
    else
    {
      ch[++top]=a[i];
    }
  }
  cout<<(op==0?"No":"Yes")<<endl;
}



4502. 集合操作

题目

给定一个由正整数(最初为空)组成的多重集 $ S $。多重集表示可能存在重复元素的集合。

请你对该集合执行 $ Q $ 次操作,操作分为两种:

  • 增加操作,格式为 1 x,将一个正整数 $ x $ 加入到集合 $ S $ 中。数据保证,$ x $ 不小于当前 $ S $ 中的任何元素。
  • 询问操作,格式为 2,找到一个当前 $ S $ 的子集 $ s $,要求 $ max(s)-mean(s) $ 的值应尽可能大,输出 $ max(s)-mean(s) $ 的最大可能值。$ max(s) $ 表示 $ s $ 中最大元素的值,$ mean(s) $ 表示 $ s $ 中所有元素的平均值。

输入格式

第一行包含整数 $ Q $,表示操作次数。

接下来 $ Q $ 行,每行描述一个操作,格式如题面所述。

保证第一个操作一定是增加操作。

输出格式

每个询问操作输出一行结果,一个实数,表示 $ max(s)-mean(s) $ 的最大可能值。

输出结果与标准答案之间的绝对或相对误差不超过 $ 10^{-6} $ 即视为正确。

数据范围

前 $ 5 $ 个测试点满足 $ 1 \le Q \le 15 $。
所有测试点满足 $ 1 \le Q \le 5 \times 10^5 $,$ 1 \le x \le 10^9 $。

输入样例1:

6
1 3
2
1 4
2
1 8
2

输出样例1:

0.000000
0.500000
3.000000

输入样例2:

4
1 1
1 4
1 5
2

输出样例2:

2.000000

思路

数据保证,$ x $ 不小于当前 $ S $ 中的任何元素。

其实自己在比赛的思路是正确的,但是没看到题目的数据保证就没写这一题,然后窝就去写另外两题的题解了(在比赛结束后才提交题解)。

大小为 $ now $ 的子集一定为 前 $ now-1 $ 个元素(使平均值最小)和第 $ n $ 个元素(使子集的最大值最大)。

前 $ x $ 个数字的平均值可以用前缀和预处理。

$ Code $

#include<bits/stdc++.h>
using namespace std;
double sum[500001],a[500001];
int Q,now=1,n;
int main()
{
  cin>>Q;
  while(Q--)
  {
    int op;
    cin>>op;
    if(op==1)
    {
      cin>>a[++n];
      sum[n]=a[n]+sum[n-1];
    }
    else
    {
      while(now<n&&a[n]-((sum[now]+a[n])/(now+1))>a[n]-((sum[now-1]+a[n])/now))now++;
      printf("%.6lf\n",a[n]-((sum[now-1]+a[n])/now));
    }
  }
}



4501. 收集卡牌

题目

某干脆面厂商在每包面中都放置有一张武将卡。

武将卡共分为 $ n $ 种,编号 $ 1 \sim n $。

当集齐 $ 1 \sim n $ 号武将卡各一张时,就可以拿它们去换大奖。

为了换大奖,李华先后购买了 $ m $ 包该品牌的干脆面。

其中第 $ i $ 包面中包含的武将卡的编号为 $ a_i $。

每当买完一包面,得到该面赠送的武将卡后,李华都会审视一遍自己手中的全部卡牌。

如果此时自己现有的卡牌能够凑齐全部武将卡,那么他就会立即将每种武将卡都拿出一张,并将拿出的卡牌寄给厂商,用来换奖。

请你分析李华购买干脆面的整个过程并计算购买完每一包面后,李华能否凑齐全部武将卡用来换奖。

注意,每次换奖都需要消耗卡牌,消耗掉的卡牌就不属于他了。

输入格式

第一行包含两个整数 $ n,m $。

第二行包含 $ m $ 个整数 $ a_1,a_2,…,a_m $。

输出格式

输出一个长度为 $ m $ 的 $ 01 $ 字符串,如果买完第 $ i $ 包面后,李华能够凑齐全部武将卡用来换奖,则第 $ i $ 位字符为 $ 1 $,否则为 $ 0 $。

数据范围

前 $ 5 $ 个测试点满足 $ 1 \le n,m \le 20 $。
所有测试点满足 $ 1 \le n,m \le 10^5 $,$ 1 \le a_i \le n $。

输入样例1:

3 11
2 3 1 2 2 2 3 2 2 3 1

输出样例1:

00100000001

输入样例2:

4 8
4 1 3 3 2 3 3 3

输出样例2:

00001000

思路

设换了 $ now $ 次奖, $ s_x $ 为卡牌数量大于等于 $ x $ 的卡牌种类的个数(不换一次奖)。

每收集一张卡牌 $ a_i $ ,卡牌 $ a_i $ 的数量 $ t[a_i] $ 加一,卡牌数量大于等于 $ t[a_i] $ 的卡牌种类 $ s[t[a_i]] $ 加 $ 1 $ ( $ t[a_i] $ 已经加过一)。

若 $ s_{now+1} == n $ ,则表示可以换第 $ now + 1 $ 次奖,输出 $ 1 $ , $ now $ 加一。

否则输出 $ 0 $ 。

$ Code $

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100001];
int s[100001];
int now,t[100001];
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>a[i];
        t[a[i]]++;
        s[t[a[i]]]++;
        if(s[now+1]==n)
        {
            cout<<1;now++;
        }
        else cout<<0;
    }
}



4500. 三个元素

题目

给定一个长度为 $ n $ 的数组 $ r_1,r_2,…,r_n $。

请你找到其中的三个元素 $ r_a,r_b,r_c $,使得 $ r_a < r_b < r_c $ 成立。

输入格式

第一行包含整数 $ n $。

第二行包含 $ n $ 个整数 $ r_1,r_2,…,r_n $。

输出格式

共一行,输出 $ a,b,c $。

注意,题目要求输出的是元素的下标。

如果方案不唯一,输出任意合理方案均可。

如果无解,则输出 -1 -1 -1

数据范围

前三个测试点满足 $ 3 \le n \le 10 $。
所有测试点满足 $ 3 \le n \le 3000 $,$ 1 \le r_i \le 10^9 $。

输入样例1:

6
3 1 4 1 5 9

输出样例1:

4 1 3

输入样例2:

5
1 1000000000 1 1000000000 1

输出样例2:

-1 -1 -1

输入样例3:

9
10 10 11 10 10 10 10 10 1

输出样例3:

9 8 3

思路

先记录一个结构体数组 $ a $ ,包含元素的值和下标。

然后按元素的值 $ sort $ 排序一下,使得 $ r_a \le r_b \le r_c $ 成立。

最后记录元素值只出现一次的元素,使得 $ r_a < r_b < r_c $ 成立。

判断非重复的元素的个数是否大于等于 $ 3 $ , 是则输出前三个记录的元素的下标,否则输出 $ -1 -1 -1 $ 。

$ Code $

#include<bits/stdc++.h>
using namespace std;
int n;
struct node
{
    int id,num;
}a[3001];
bool cmp(node a,node b)
{
    return a.num<b.num;
}
int s[3001],len;
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].num;a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1; i<=n; i++)
    {
        if(a[i].num!=a[i-1].num)
        {
            s[++len]=a[i].id;
        }
    }
    if(len<3)cout<<"-1 -1 -1"<<endl;
    else 
    cout<<s[1]<<" "<<s[2]<<" "<<s[3]<<endl;
}