专栏文章

NOIP2024前做题记录

OOnana_in_XMFLS
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir137r1
此快照首次捕获于
2025/12/04 14:01
3 个月前
此快照最后确认于
2025/12/04 14:01
3 个月前
查看原文
1.题目大意：给定两个长度均为nn的数组aa,bb，每次操作可以从aa,bb中各选择一个数删除，最后使得两个数组合并后得到的新数组cc中没有重复元素，最小化操作数 (n≤105n \le 10^5)。
题解：先分别对两个数组进行去重操作，分别独立计算各自的消除次数，计为ans1ans1和ans2ans2，得到两个无重集pp,qq，现在要消除pp，qq合体之后的新集合内的重复元素，当存在相同元素时，可以跟ans1ans1和ans2ans2中较少的部分一起消，若ans1=ans2ans1 = ans2，则得进行额外的操作数，计为ansans，由于有可能只存在奇数个相同元素，所以ansans要加1再除2，最后的答案对于ans1+ansans1+ans和ans2+ansans2+ans取maxmax即可。时间复杂度O(n)O(n)。
CPP
#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.题目大意：给定nn个栈，初始都为空。
有qq次操作，每次操作为以下三种之一：
pushpush xx yy zz：在编号为zz 的栈中加入xx 个数字 yy 。
poppop xx zz：从第 zz 个栈中弹出 xx 个数，并输出最后一个数。保证操作合法。
putput uu vv：依次把第 uu 个栈中的数弹出并加入到第 vv 个栈中。
请维护以上操作。
n,m≤2×105n,m\le 2 \times 10^5
x≤109x \le 10^9
题解：由数据范围可知，直接模拟显然会T飞，考虑对于每个操作维护一个Pair记录连续的数量和数字种类，然后每个Pair记录两个连接，一个往前一个往后，类似于双向链表的操作，对于每个putput操作直接记录哪个连接是现在在用的即可。注意：由于反复的翻转，所以舍去传统的记录前继和后继的做法，直接打标记记录哪个连接在用。这是一个技巧。
CPP
#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.题目大意：给定一个数NN和N3N3，请问有多少组小于PP的非负整数aa bb cc ，满足：
记 N0=N2+1N0 = N^2+1
N1=N0mod  aN1 = N0 \mod a
N2=N1+bN2 = N1+b
N3=N2mod  cN3 = N2 \mod c
其中，1≤a,c≤P,0≤b≤P,P≤1051 \le a,c \le P,0 \le b \le P,P \le 10^5
题解：考虑枚举aa 和 cc，我们就可以得到一系列N1N1和N2N2的取值，由于bb是非负数，所以每个大于N1N1的N2N2,都是一组可行解，二分即可。时间复杂度 O(PlgP)O(PlgP)。
4.题目大意: 求将给定字符串变成回文词所需要插入的最少字符数。
题解：将原字符串颠倒，问题的答案即为原字符串长度减掉原字符串与其颠倒后的字符串的最长子序列的长度。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...