首页 > 其他分享 >241111 noip 题解

241111 noip 题解

时间:2024-11-11 17:41:43浏览次数:1  
标签:格子 noip int 题解 inv 241111 leq ans 序列

省流:\(100+50+10+30\)。还是不稳定啊,noip上不了270就真的要退役了。

T1

题意:给定一个长度为 \(n\) 的序列 \(a\),每次你可以交换相邻两个位置,求出最小交换次数以及字典序最小的交换方案使得 \(a\) 的每个不是本身的前缀都不是排列。

\(n \leq 10^5\)。

注意到每次交换至多会减少一个是排列的前缀。因此最少操作次数就是这样的前缀个数。

至于最小字典序,直接从前往后操作即可。

时间复杂度 \(\Theta(n)\)。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N];
vector<int> ve;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	int mx=0,mn=n+1;
	for(int i=1; i<n; i++) {
		if(min(mn,a[i])==1&&max(mx,a[i])==i) ve.push_back(i),swap(a[i],a[i+1]);
		mn=min(mn,a[i]),mx=max(mx,a[i]);
	}
	cout<<ve.size()<<'\n';
	for(int i=0; i<ve.size(); i++) cout<<ve[i]<<" ";
	return 0;
}

T2

题意:给定一个 \(n \times m\) 的网格,你需要操作一个角色走出网格。每个格子上有一个给定的方向,当角色站在这个格子上时,可以向格子给定的方向走不超过 \(k\) 步,求有多少个格子可以作为出发点让角色走出网格。

\(k \leq n,m \leq 3000\)。

考虑倒着做,如果一个格子可以走出网格,那么其余能够通过走一步到达这个格子的格子也能走出。于是我们可以对于每个格子与它上面第一个 D,下面第一个 U,左边第一个 R,右边第一个 L 连边,前提是距离这个格子不超过 \(k\),然后把可以一步走出网格的格子扔进队列跑多源 bfs 即可。容易证明这样一定能遍历到所有能够走出网格的格子。

时间复杂度 \(\Theta(nm)\)。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
char ch[N][N];
int n,m,k,vis[N][N],head[N][N],ecnt=0;
struct edge {int tox,toy,nxt;}e[N*N<<2];
inline void add(int x,int y,int xx,int yy) {e[++ecnt]=(edge){xx,yy,head[x][y]};head[x][y]=ecnt;}
inline bool check(int x,int y) {
	if(ch[x][y]=='D') if(x+k>n) return true;
	if(ch[x][y]=='U') if(x-k<1) return true;
	if(ch[x][y]=='L') if(y-k<1) return true;
	if(ch[x][y]=='R') if(y+k>m) return true;
	return false;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m>>k;
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>ch[i][j];
	for(int i=1; i<=n; i++) {
		int lst=0;
		for(int j=1; j<=m; j++) {
			if(lst&&j-lst<=k) add(i,j,i,lst);
			if(ch[i][j]=='R') lst=j;
		}
	}
	for(int i=1; i<=n; i++) {
		int lst=0;
		for(int j=m; j>=1; j--) {
			if(lst&&lst-j<=k) add(i,j,i,lst);
			if(ch[i][j]=='L') lst=j;
		}
	}
	for(int i=1; i<=m; i++) {
		int lst=0;
		for(int j=1; j<=n; j++) {
			if(lst&&j-lst<=k) add(j,i,lst,i);
			if(ch[j][i]=='D') lst=j;
		}
	}
	for(int i=1; i<=m; i++) {
		int lst=0;
		for(int j=n; j>=1; j--) {
			if(lst&&lst-j<=k) add(j,i,lst,i);
			if(ch[j][i]=='U') lst=j;
		}
	}
	queue<pair<int,int>> q;
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(check(i,j)) q.push(make_pair(i,j)),vis[i][j]=true;
	while(!q.empty()) {
		int x=q.front().first,y=q.front().second;
		q.pop();
		for(int i=head[x][y]; i; i=e[i].nxt) {
			int vx=e[i].tox,vy=e[i].toy;
			if(vis[vx][vy]) continue;
			vis[vx][vy]=true;
			q.push(make_pair(vx,vy));
		}
	}
	int ans=0;
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) ans+=vis[i][j];
	cout<<ans;
	return 0;
}

闲话:赛时不知道怎么了竟然天真的觉得带log能过。

T3

题意:你需要求出满足以下条件的长度为 \(n + 2\) 的 \(a\) 序列的数量。

  • \(a_0 = a_{n + 1} = 0\)
  • \(\forall i \in [1,n],a_i \geq 0\)
  • \(\sum_{i = 0}^n \max(a_{i + 1} - a_i,0) = m\)

\(1 \leq n,m \leq 2 \times 10^5\)。

解法一:

注意到答案相当于:对每个长度为 \(2m\) 的合法括号序列,将其分为 \(n + 1\) 段(每段可以为空),要求每段内不能同时含有左右括号,求方案数之和。

发现一个括号序列的划分方案数只和其中 () 子串的个数有关,对于左括号相当于从 \((x,y)\) 走到 \((x,y+1)\),右括号相当于 \((x,y)\) 走到 \((x+1,y)\),画出格路,就是只和拐弯次数有关(注意这个拐弯是先向上再向右的拐弯)。不妨称 () 子串在格路中对应一个“拐点”,则要对每个 \(k\) 求从 \((0,0)\) 到 \((m,m)\),恰好有 \(k\) 个拐点,且始终有 \(x \leq y\) 的格路个数。为什么是对的呢?因为我们知道了拐点数为 \(2k - 1\),这些拐点是已经钦定的 \(a_i\),所以还剩下 \(n - 2k + 1\) 个点没有钦定,因为是从 \((0,0)\) 到 \((m,m)\),所以这些没钦定的点有 \(2m + 1\) 种选择,由于可重且点是相同的,所以钦定未钦定的点的方案是 \(C_{2m + n - 2k + 1}^{n - 2k + 1}\) 的。这是一个固定的值。

先考虑如果没有 \(x \leq y\) 的限制怎么做。只要在两个坐标上分别选 \(k\) 个拐点的位置,就唯一对应一条格路。显然方案数是 \((C_n^k)^2\)。这启发我们对“拐点坐标”构成的序列进行计数,而非对格路进行计数。

设拐点坐标为 \((x_1,y_1),(x_2,y_2),\cdots,(x_k,y_k)\)。于是我们要减去存在某个拐点满足 \(y_i < x_{i + 1}\) 的格路数,表示在第 \(i\) 个位置走到第 \(i + 1\) 个位置后不合法了。不妨假设 \(i\) 是第一个 \(y_i < x_{i + 1}\) 的拐点。那么这样的路径满足的充要条件是:

\[0 \leq x_1 < x_2 < \cdots < x_i < y_{i + 1} < y_{i + 2} < \cdots < y_k \leq n \]

\[0 < y_1 < y_2 < \cdots < y_i < x_{i + 1} < x_{i + 2} < \cdots < x_k < n \]

由于是格点,所以是小于。两维独立,所以对上述两个柿子分别计算方案数就行,这样的两个序列包含了所有 \(i\) 的情况。容易证明。

所以有 \(k\) 个拐点的方案数为:

\[(C_n^k \times C_n^k - C_{n + 1}^k \times C_{n - 1}^k) \times C_{2m + n - 2k + 1}^{n - 2k + 1} \]

对于每个 \(k\) 求和即可。

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=7e5+5,p=1e9+7;
int n,m,ans=0,fac[N],inv[N];
int qpow(int a,int b) {
	int ans=1;
	while(b) {
		if(b&1) ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}
void init(int lim) {
	fac[0]=inv[0]=1;
	for(int i=1; i<=lim; i++) fac[i]=fac[i-1]*i%p;
	inv[lim]=qpow(fac[lim],p-2);
	for(int i=lim-1; i>=1; i--) inv[i]=inv[i+1]*(i+1)%p;
}
int C(int n,int m) {
	if(n<0||m<0||n<m) return 0;
	return fac[n]*inv[m]%p*inv[n-m]%p;
}
signed main() {
	cin>>n>>m;
	init(600005);
	for(int k=0; k<=n; k++) ans=(ans+(C(m,k)*C(m,k)%p-C(m+1,k)*C(m-1,k)%p+p)%p*C(2*m+n-2*k+1,n-2*k+1)%p)%p;
	cout<<ans;
	return 0;
}

解法二

对 \(a\) 序列进行差分,得到长度为 \(n + 1\) 的序列 \(b\)。限制变为 \(b\) 的任意前缀和都 \(\geq 0\),且 \(b\) 中所有数之和 \(= 0\),绝对值之和 \(= 2m + 1\)。

将 \(b_1\) 改为 \(b_1 + 1\),限制变为 \(b\) 的任意前缀和都 \(> 0\),且 \(b\) 中所有数之和 \(= 1\),绝对值之和 \(= 2m + 1\)。

  • Raney 引理:如果 \(x_1,x_2,\cdots,x_k\) 是一个和为 \(1\) 的整数序列,则其所有循环位移中恰好有一个满足所有的前缀和都是正数。

  • 证明:考虑重复这个序列,生成一个无限数列。这个数列的“平均斜率”是 \(\frac{1}{k}\),并且整个图象会被夹在两条斜率为 \(\frac{1}{k}\) 的直线之间,并且每条直线与图象恰好有一个切点(因为直线在每个周期内与整点只接触一次)。循环位移的起始点能且只能取下界直线的切点。

因此只需统计和为 \(1\) 且绝对值之和为 \(2m + 1\) 的序列个数,最后除以 \(n + 1\) 即可。枚举负数的个数 \(i\),方案数是:

\[C_{m - 1}^{i - 1} C_{m + 1 + n - i}^{n - i} C_{n + 1}^{i} \]

神奇的是,两种做法推出来的式子完全不一样,但却是相等的。

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+5,p=1e9+7;
int n,m,ans=0,fac[N],inv[N];
int qpow(int a,int b) {
	int ans=1;
	while(b) {
		if(b&1) ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}
void init(int lim) {
	fac[0]=inv[0]=1;
	for(int i=1; i<=lim; i++) fac[i]=fac[i-1]*i%p;
	inv[lim]=qpow(fac[lim],p-2);
	for(int i=lim-1; i>=1; i--) inv[i]=inv[i+1]*(i+1)%p;
}
int C(int n,int m) {
	if(n<0||m<0||n<m) return 0;
	return fac[n]*inv[m]%p*inv[n-m]%p;
}
signed main() {
	cin>>n>>m;
	init(m+n+1);
	for(int i=0; i<=n+1; i++) ans=(ans+C(m-1,i-1)*C(m+1+n-i,n-i)%p*C(n+1,i)%p)%p;
	cout<<ans*qpow(n+1,p-2)%p;
	return 0;
}

闲话:感觉解法一更加值得学习一点,解法二的引理真的会考吗/oh/oh

T4

原题:P8415。

还不会。

标签:格子,noip,int,题解,inv,241111,leq,ans,序列
From: https://www.cnblogs.com/System-Error/p/18540229

相关文章

  • 11.11 NOIP模拟赛
    T1字符串,两个相同的串一个从前往后,一个从后往前,选完后正着看都一样的话,就能拼成一个回文串,考虑两倍字符串,用kmp找到n~2n中间的一个i,如果i-n+1到i和1到n组成的字符相同的话,答案就为(m-1)*n+(2n-i)。m=1时直接输出nxt[n]。T2找规律,能\(O(1)\)求出任意位置的价值的......
  • NOIP 2024 游记 & 赛前训练(未完待续)
    NOIP2024游记&赛前训练day-18(11.11)今天做信友错的模拟赛。第一题是和最短路有关的,看到\(n\le500\)就想到了\(n^3\logn\),然而看了很久都不会做,于是果断火速打了\(O(n^4)\)的暴力走人,get50pts。然后看第二题,发现是最大异或路径,正好最近刚学了线性基,于是想到之前做......
  • [题解]P11233 [CSP-S 2024] 染色
    P11233[CSP-S2024]染色设\(f[i][j=0/1]\)表示涂到第\(i\)位,且第\(i\)为颜色为\(j\),则考虑用\(i\)之前能和\(i\)匹配的位置\(p\)进行转移。\(p\)需要满足下面的条件:\(a[p]=a[i]\)。\(p\)的颜色为\(j\)。\([p+1,i-1]\)之间的颜色全不为\(j\)。显然,我们只需要找满足条件的......
  • [2024.11.11]NOIP模拟赛T2
    赛时T1提议看懂以后立马意识到就是让求最长Border。对于\(n\timesm\le10^6\)可以暴力建串然后直接KMP。容易发现如果\(s\)循环元为\(n\),那么答案就是\(n\times(m-1)\)。否则加上最长循环元长度即可。循环元还是用KMP求。T2让我想起了之前一道硬控我3h的题目......
  • AT_agc012_f [AGC012F] Prefix Median 题解
    首先将序列排序,这是显然的。考虑倒着确定\(b\)序列中的每个数。即从完整的\(a\)序列开始,每次删掉两个数,记录中位数。先找出\(b\)序列合法的条件。容易发现对于所有\(i\),在\(b_{p_i}\)成为中位数时,\(p_i,p_{i+1}\)之间的所有数都已经被删除了,且\(i\lep_i\le2n-i\)。......
  • NOIP2024加赛4
    NOIP2024加赛4\(T1\)luoguP11267【MX-S5-T1】王国边缘\(85pts\)预处理前缀中最后一个\(1\)出现的位置然后就可以倍增跳了。点击查看代码constllp=1000000007;intnxt[200010][62],f[200010][62],last[200010];chart[200010];lldivide(lls,llk){llan......
  • Eplan2022卡顿问题解决
    EPLAN2022卡顿崩溃怎么解决 第一步:可以检查下用户设置。打开菜单"选项→设置:用户→翻译→字典":不勾选"自动完成"和"自动更正"。在选项设置框中输入"自动",快速找到用户设置,取消勾选,如下图。 第二步:可以检查下电脑语言设置。设置:常规→兼容性"。如下图。 ......
  • CF 1257 题解
    CF1257题解ATwoRivalStudents每次交换都可以让距离增加\(1\),上界是\(n-1\).题目说至多而不是恰好交换\(x\)次,于是不需要考虑边界.BMagicStick一个重要的观察是:如果能够得到\(x\),那么就能得到任意小于等于\(x\)的数,这是操作二保证的.考虑操作\(1\)......
  • 2024中高级前端面试真题解析
    我是一名本科毕业的前端程序媛,工作5年了,周末双休待遇还不错。公司最近要搬迁新地址,业务要整合到一起,所以最近比较清闲,天天上班摸鱼,闲着没事,整理了以前面试时用的资料文档有945道:JavaScript(323题)CSS(61题)HTML(57题)React(83题)Vue(80题)算法(19题)计算机网络(71题)Node.js(2......
  • 【题解】CF1993【EF】
    A注意到一种选项最多填对\(n\)个题所以答案是\(\min(n,cnt_a)+\min(n,cnt_b)+\min(n,cnt_c)+\min(n,cnt_d)\)B注意到操作只能让奇数变多,偶数变少,所以我们只能把偶数全变成奇数特判掉全是偶数的情况,容易得到答案下界:偶数个数容易想到一个naive贪心做法:每次都拿出奇数......