526互联

「TAOI-2」核心共振,「NnOI R2-T3」Horizon Blue

发布时间 2023-08-21 00:32:53作者: o-Sakurajimamai-o

「TAOI-2」核心共振

# 「TAOI-2」核心共振

## 题目背景

⚡超越一切震慑凡人⚡

⚡带来终结机械降神⚡

⚡风暴之力充满全身⚡

⚡最后一击核心共振⚡

## 题目描述

给定正整数 $p$ 和 $n$。对于一个排列，我们称其中相邻两项产生「共振」当且仅当这两个数的和为 $p$ 的倍数。

请你构造一个 $1 \sim n$ 的排列，最大化其中产生「共振」的次数。如果有多种方案，输出任意一种即可。

## 输入格式

**本题有多组测试数据。**

输入的第一行包含一个正整数 $T$，代表数据的组数。

对于每组测试数据，输入包含一行，为由空格隔开的两个正整数 $n$ 和 $p$。

## 输出格式

对于每组测试数据，输出一行，包含由空格隔开的 $n$ 个正整数，代表你构造的排列。

## 样例 #1

### 样例输入 #1

```
3
9 1
5 2
1 12345
```

### 样例输出 #1

```
3 8 7 1 4 5 6 9 2
1 5 3 2 4
1
```

## 提示

**本题采用捆绑测试。**

+ Subtask 0（15 pts）：$n \leq 9$，$T \le 10$。
+ Subtask 1（10 pts）：$p = 2$。
+ Subtask 2（30 pts）：$p = 3$。
+ Subtask 3（45 pts）：无特殊限制。

对于所有数据，$1 \leq n \leq 10^5$，$1 \leq p \leq 10^8$，$1 \leq T \leq 10^4$，$1 \leq \sum n \leq 3\times 10^5$。

 

这道题目我在赛场上面没有想到,赛后查看博客之后才得到一丝启发

有这样一个规律,既然要求和为p,那么我们只需要让两个数对p取模之后,如果两个数的余数相加=p的话那就是p的倍数了

所以说先把p的倍数放在前面,然后将 余数和为p的两个数相间放就可以

先上一段部分TLE的代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m,k;
bool vis[N];
void solve()
{
    cin>>n>>k;
    map<int,vector<int>>mp;
    for(int i=1;i<=n;i++) mp[i%k].push_back(i);
    for(auto i:mp[0]) cout<<i<<" ";
    for(int i=1;i<=k/2;i++){
        int p=k-i,num=0;
        if(p==i) for(auto j:mp[p]) cout<<j<<" ";
        else{
            for(auto j:mp[i]){
                cout<<j<<" ";
                if(num+1<=mp[p].size()) cout<<mp[p][num++]<<" ";
            }
        }
    }
    cout<<endl;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

为什么会超时呢?通过分析得知我们的复杂度只能是O(n*m/2),所以说可能出现一种m过于大的情况,而又没有n与之匹配

所以说我们在开头特判一下即可,如果m>=2*n的话,那就直接输出原序列就可以

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m,k;
bool vis[N];
void solve()
{
    cin>>n>>k;
    map<int,vector<int>>mp;
    if(k>=n*2){
        for(int i=1;i<=n;i++) cout<<i<<" ";
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++) mp[i%k].push_back(i);
    for(auto i:mp[0]) cout<<i<<" ";
    for(int i=1;i<=k/2;i++){
        int p=k-i,num=0;
        if(p==i) for(auto j:mp[p]) cout<<j<<" ";
        else{
            for(auto j:mp[i]){
                cout<<j<<" ";
                if(num+1<=mp[p].size()) cout<<mp[p][num++]<<" ";
            }
        }
    }
    cout<<endl;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

　　　　　　　　　「NnOI R2-T3」Horizon Blue

# 「NnOI R2-T3」Horizon Blue

## 题目描述

小 C 喜欢在画板上画画。他进行了 $ n $ 次操作，每次操作有如下三种可能：

- ```1 k b``` 代表小 C 绘制了一条解析式为 $ y=kx+b $ 的直线。
- ```2 k b``` 代表小 C 询问你直线 $ y=kx+b $ 与多少条被绘制的直线有**恰好**一个公共点。
- ```3 k b``` 代表小 C 擦除所有与直线 $ y=kx+b $ 有**至少**一个公共点的直线。

**注意：两条重合的直线有无数个交点。**

**注意：询问时重合的直线应分别计算。**

## 输入格式

第一行一个整数 $ n $。

接下来 $n$ 行，每行三个整数 $ 1/2/3,k,b $，代表一次操作。

## 输出格式

对每次 ```2 k b``` 操作，输出满足要求的直线数量。

## 样例 #1

### 样例输入 #1

```
6
1 1 0
1 -1 0
2 2 1
3 1 3
2 2 1
2 1 1
```

### 样例输出 #1

```
2
1
0
```

## 样例 #2

### 样例输入 #2

```
10
1 1 0
1 1 0
2 1 1
2 1 0
2 2 5
3 1 0
2 2 5
1 2 3
1 3 4
2 3 5
```

### 样例输出 #2

```
0
0
2
0
1
```

## 提示

**【样例 1 解释】**

第 1 次操作，绘制直线 $ y=x $。

第 2 次操作，绘制直线 $ y=-x $。

第 3 次操作，可以发现直线 $ y=2x+1 $ 与前两条线相交。

第 4 次操作，擦掉所有 $ y=x+3 $ 相交的线，直线 $ y=-x $ 被擦掉。

第 5 次操作，$ y=2x+1 $ 显然与 $ y=x $ 相交。

第 6 次操作，$ y=x+1 $ 与 $ y=x $ 斜率相等，是平行线，不相交。

**【数据范围】**

对于 $ 100\% $ 的数据，$ 1 \le n \le 10^5 $，$ 1 \le |k| \le 10^5 $，$ 0 \le |b| \le 10^5 $。

**提示：本题开启捆绑测试。**

$$
\def\r{\cr\hline}
\def\None{\text{None}}
\def\arraystretch{1.5}
\begin{array}{c|c|c}
\textbf{Subtask} & \textbf{Sp. Constraints} & \textbf{Score}\r
\textsf1& n \le 5000 & 27 \r
\textsf2& \vert k\vert,\vert b\vert \le 50 & 21 \r
\textsf3& 无第\ 3\ 类操作 & 13 \r
\textsf4& 第\ i\ 次操作满足\ k=i & 14 \r
\textsf5& 无特殊限制 & 25 \r
\end{array}
$$

 61分超时代码:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,num;
int vis[N],res[N],cnt;
map<int,int>mp;
map<pair<int,int>,int>mp_;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        int a,k,b;
        scanf("%d%d%d",&a,&k,&b);
        if(a==1) num++,mp[k]++,mp_[{k,b}]++;
        if(a==2) printf("%d\n",num-mp[k]);
        if(a==3){
            for(auto &i:mp) if(i.first!=k) num-=i.second,i.second=0;
            for(auto &i:mp_){
                if(i.first==make_pair(k,b))
                    {if(i.second!=0) num-=i.second,mp[k]-=i.second,i.second=0;}
                else if(i.first.first!=k) i.second=0;
            }
        }
    }
    return 0;
}

考虑优化,使用二维map,然后使用clear()清楚,时间复杂度O(nlogn)

这里要注意,能不在循环里清除就不清楚,用clear的效率要比单提一个map的时间快得多

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,num;
int vis[N],res[N],cnt;
map<int,int>mp;
map<int,unordered_map<int,int>>mp_;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        int a,k,b;
        scanf("%d%d%d",&a,&k,&b);
        if(a==1) num++,mp[k]++,mp_[k][b]++;
        if(a==2) printf("%d\n",num-mp[k]);
        if(a==3){
            for(auto &i:mp) if(i.first!=k) num-=i.second,mp_.erase(i.first);
            mp.clear();
            num-=mp_[k][b],mp_[k][b]=0,mp[k]=num;
        }
    }
    return 0;
}

这是超时的,原因就是每次都单提一个map导致时间复杂度变高:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,num;
int vis[N],res[N],cnt;
map<int,int>mp;
map<int,unordered_map<int,int>>mp_;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        int a,k,b;
        scanf("%d%d%d",&a,&k,&b);
        if(a==1) num++,mp[k]++,mp_[k][b]++;
        if(a==2) printf("%d\n",num-mp[k]);
        if(a==3){
            for(auto &i:mp) if(i.first!=k) num-=i.second,i.second=0,mp_.erase(i.first);
           mp[k]-=mp_[k][b],num-=mp_[k][b],mp_[k][b]=0;
        }
    }
    return 0;
}