NOIP2024前做题记录

· · 个人记录

1.题目大意：给定两个长度均为n的数组a,b，每次操作可以从a,b中各选择一个数删除，最后使得两个数组合并后得到的新数组c中没有重复元素，最小化操作数 (n \le 10^5)。

题解：先分别对两个数组进行去重操作，分别独立计算各自的消除次数，计为ans1和ans2，得到两个无重集p,q，现在要消除p，q合体之后的新集合内的重复元素，当存在相同元素时，可以跟ans1和ans2中较少的部分一起消，若ans1 = ans2，则得进行额外的操作数，计为ans，由于有可能只存在奇数个相同元素，所以ans要加1再除2，最后的答案对于ans1+ans和ans2+ans取max即可。时间复杂度O(n)。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n,ans1,ans2,ans;
vector <int> p,q;
map <int,int> cnt;
int main(int argc,char *argv[])
{
    cin>>n;
    for(int i = 1,a;i <= n;++i)
    {
        cin>>a;
        if(!cnt[a]) p.push_back(a);
        else ans1++;
        cnt[a]++;
    }
    cnt.clear();
    for(int i = 1,b;i <= n;++i)
    {
        cin>>b;
        if(!cnt[b]) q.push_back(b);
        else ans2++;
        cnt[b]++; 
    }
    cnt.clear();
    for(auto i:p) cnt[i]++;
    for(auto i:q) cnt[i]++;
    for(auto i:cnt)
        if(i.second == 2)
        {
            if(ans1 == ans2) {ans++;continue;}
            if(ans1 > ans2) swap(ans1,ans2);
            ans1++;
        }
    ans = (ans+1)/2;
    cout<<max(ans1+ans,ans2+ans);
    return 0;
}

2.题目大意：给定n个栈，初始都为空。

有q次操作，每次操作为以下三种之一：

push$ $x$ $y$ $z$：在编号为$z

的栈中加入x 个数字 y 。

pop$ $x$ $z$：从第 $z

个栈中弹出 x 个数，并输出最后一个数。保证操作合法。

put$ $u$ $v$：依次把第 $u

个栈中的数弹出并加入到第 v 个栈中。

请维护以上操作。

n,m\le 2 \times 10^5 x \le 10^9

题解：由数据范围可知，直接模拟显然会T飞，考虑对于每个操作维护一个Pair记录连续的数量和数字种类，然后每个Pair记录两个连接，一个往前一个往后，类似于双向链表的操作，对于每个put操作直接记录哪个连接是现在在用的即可。注意：由于反复的翻转，所以舍去传统的记录前继和后继的做法，直接打标记记录哪个连接在用。这是一个技巧。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5+5;
struct node {int a,b,id,num;}e[maxn];
int n,m,l[maxn],r[maxn],cnt,x,y,z,u,v;
string s;
int main(int argc,char *argv[])
{
    //freopen("magic.in","r",stdin);
    //freopen("1.txt","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    while(m--)
    {
        cin>>s;
        if(s == "push")
        {
            cin>>x>>y>>z;
            e[++cnt] = (node){0,0,y,x};
            if(!r[z]) l[z] = r[z] = cnt;
            else
            {
                if(!e[r[z]].a)
                {
                    e[r[z]].a = cnt;
                    e[cnt].a = r[z];
                }
                else
                {
                    e[r[z]].b = cnt;
                    e[cnt].b = r[z];
                }
                r[z] = cnt;
            } 
        }
        else if(s == "pop")
        {
            cin>>x>>z;
            while(x > e[r[z]].num)
            {
                //if(!e[r[z]].num) continue;
                x -= e[r[z]].num;
                u = 0;
                if(e[r[z]].a) u = e[r[z]].a;
                if(e[r[z]].b) u = e[r[z]].b;
                if(e[u].a == r[z]) e[u].a = 0;
                if(e[u].b == r[z]) e[u].b = 0;
                if(e[r[z]].a == u) e[r[z]].a = 0;
                if(e[r[z]].b == u) e[r[z]].b = 0;
                r[z] = u;
            }
            e[r[z]].num -= x;
            cout<<e[r[z]].id<<'\n';
        }
        else
        {
            cin>>u>>v;
            if(!r[u]) continue;
            if(!r[v]) l[v] = r[u];
            else
            {
                if(!e[r[u]].a) e[r[u]].a = r[v];
                else e[r[u]].b = r[v];
                if(!e[r[v]].a) e[r[v]].a = r[u];
                else e[r[v]].b = r[u];
            }
            r[v] = l[u];
            l[u] = r[u] = 0;
        }
    }
    return 0;
}

3.题目大意：给定一个数N和N3，请问有多少组小于P的非负整数a b c ，满足：

记 N0 = N^2+1

N1 = N0 \mod a N2 = N1+b N3 = N2 \mod c

其中，1 \le a,c \le P,0 \le b \le P,P \le 10^5

题解：考虑枚举a 和 c，我们就可以得到一系列N1和N2的取值，由于b是非负数，所以每个大于N1的N2,都是一组可行解，二分即可。时间复杂度 O(PlgP)。

4.题目大意: 求将给定字符串变成回文词所需要插入的最少字符数。

题解：将原字符串颠倒，问题的答案即为原字符串长度减掉原字符串与其颠倒后的字符串的最长子序列的长度。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
string s,t;
int dp[5005][5005];
int main(int argc,char *argv[])
{
    cin>>s;
    t = s;
    reverse(s.begin(),s.end());
    int n = s.size();
    for(int i = 0;i < n;++i)
        for(int j = 0;j < n;++j)
        {
            if(s[i] == t[j]) 
                i==0||j==0?dp[i][j]=1:dp[i][j]=dp[i-1][j-1]+1;
            else
            {
                if(i == 0 && j == 0) dp[i][j] = 0;
                else if(i == 0) dp[i][j] = dp[i][j-1];
                else if(j == 0) dp[i][j] = dp[i-1][j];
                else dp[i][j] = max(dp[i-1][j],dp[i][j-1]); 
            } 
        }
    printf("%d\n",n-dp[n-1][n-1]);
    return 0;
}