列表

详情

NC207456. Strangemultiset

描述

There was a strange person who gave you a strange multiset which had a chip in it.

Initially, the multiset is empty. just like what it was called, for sure you can add some integers into it , delete intergers or ask its size.But the chip inside the multiset will convert the value you give  by running a function and getting return value.
funtion shows in the picture below.

Now, you have to deal with q queries .A query has three types of operations.

operation 1 :  ask the size of the multiset.

operation 2:  add an integer X into the multiset

operation 3:  delete all integers that equal to the integer X from the multiset

Note that the multiset will always run the function through its chip and use the value of the function as final integer when you implement operation 2 or operation 3.

输入描述

First line contains a integer q --- number of queries.()
The following q lines contain operations.
There are three types of operations,()
The ask operations given as "1".
The add operations given as "2 X".
The delete operations given as "3 X".

输出描述

For every ask operations , you should output an integer representing the size of the current multiset

示例1

输入: 

5
2 9
2 15
1
3 21
1

输出: 

2
0

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 316ms, 内存消耗: 40940K, 提交时间: 2020-06-14 19:28:44 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e6+10;
int prime[N],vs[N],len;
inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}
void init()
{
    for(int i=2;i<N;++i){
        if(!vs[i]) prime[++len]=i;
        for(int j=1;j<=len&&i*prime[j]<N;++j){
            vs[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    }
}
int st[N];
int main()
{
    init();
    int _;scanf("%d",&_);

    int sum=0;
    while(_--)
    {
        int ty=read();
        if(ty==1){
            printf("%d\n",sum);
        }
        else{
            int x=read();
            if(vs[x]) x=vs[x];
            if(ty==2){
                st[x]++;
                sum++;
            }
            else {
                sum-=st[x];
                st[x]=0;
            }

        }
    }



}

C++(clang++11) 解法, 执行用时: 909ms, 内存消耗: 41208K, 提交时间: 2021-05-12 20:33:25 

#include<iostream>
using namespace std;
const int N=5e6+10;
int pri[N];
int a[N];
void init()
{
	int num = 0;
	for (int i = 2;i < N;i++)
	{
		if (a[i] == 0) pri[num++] = i;
		for (int j = 0;j < num && i * pri[j] < N;j++)
		{
			a[i * pri[j]] = pri[j];
			if (i % pri[j] == 0) break;
		}
	}
}
int main()
{
	init();
	int n;
	int st[N] = { 0 };
	int sum=0;
	cin >> n;
	while (n--)
	{
		int ty;
		int x;
		cin >> ty;
		if (ty == 1)
		{
			cout << sum <<endl;
		}
		else
		{
			cin >> x;
			if (a[x] != 0) x = a[x];
			if (ty == 2)
			{
				st[x]++;
				sum++;
			}
			else
			{
				sum -= st[x];
				st[x] = 0;
			}
		}
	}
}

上一题

© 2024 nowcoder.com