首页 > 其他分享 >230722校内赛

230722校内赛

时间：2023-08-28 18:33:04浏览次数：35  
标签：ch 校内 int top 230722 freopen ans return

T1 CF576D

题解

我们根据边的出现时间分成 \(m\) 段

对于每一段，设 \(f_{T,i}\) 表示 \(T\) 时刻， \(i\) 节点能否走到，那么走一步就是个矩阵乘法

对于某一段，我们从终点开始 bfs 可以就可以求出答案，矩阵乘法用 bitset 优化

复杂度 \(\mathcal{O}(m^2+\frac {ω}{mn^3}logT)\)

#include<bits/stdc++.h>
using namespace std;
const int INF = 2e9,N = 155;
int n,m,ans = INF;
struct edge{
	int u,v,w;
}e[N];
struct mat{ 
	bitset<N>a[N];
	mat(){
		for(int i = 0;i<n;i++) a[i].reset();
	}
	void I(){
		for(int i = 0;i<n;i++) a[i][i] = 1;
	}
	mat operator *(mat &A){
		mat B;
		for(int i = 0;i<n;i++)
		for(int j = 0;j<n;j++) if(a[i][j]) B.a[i]|=A.a[j];
		return B;
	}
};
void work(mat &A,mat &E,int t){
	queue<int>q;int d[N];
	memset(d,-1,sizeof(d));
	for(int i=0;i<n;i++)
		if(A.a[0][i]){
			q.push(i);
			d[i] = 0;
		}
	while(q.size()){
		int x = q.front();q.pop();
		for(int i = 0;i<n;i++) 
			if(d[i]==-1&&E.a[x][i]){
				d[i] = d[x]+1;
				q.push(i);
			}
	}
	if(~d[n-1]) ans = min(ans,d[n-1]+t);
}
mat ksm(mat A,mat B,int b){
	while(b){
		if(b&1) A = A*B;
		B = B*B;
		b>>=1;
	}
	return A;
}
int main(){
	freopen("f.in","r",stdin);
	freopen("f.out","w",stdout);
	scanf("%d%d",&n,&m);
	mat A,E;
	A.a[0][0] = 1;
	for(int i = 1;i<=m;i++){
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
		--e[i].u,--e[i].v;
	}
	sort(e+1,e+m+1,[](edge a,edge b){
		return a.w<b.w;
	});
	for(int t = 1,lans = 0,now;t<=m;t++){
		if(e[t].w>=ans) break;
		now = e[t].w;
		if(now^lans) A = ksm(A,E,now-lans);
		E.a[e[t].u][e[t].v] = 1;
		work(A,E,now);
		lans = now;
	}
	if(ans==INF){
		puts("Impossible");
		return 0;
	} 
	printf("%d",ans);
	return 0;
}

T2 平均数

题解

很容易知道这是一道构造题

但是呢，这个构造极度难想，笔者考试时本以为自己可以A了，结果直接被某金牌选手的数据搞到了 60 分

感谢冯施源大佬的这套题，做得太nm开心了

n 为奇数的时候构造十分的容易，但是为偶数时就不同了

我们从一个 \(2 \times 2\) 的矩阵想起，其中的每一个位置上可以是一个元素或是一个矩阵

那么很明显的是对角线上的相等

但对于 $ n \equiv 2 \mod 4$ ，情况仍然有所不同

我们要构造一个 $ 4 \times 4$ 的大矩阵

算了直接放fsy的题解吧

#include<bits/stdc++.h>
#define N 2010
using namespace std;
int n,ans[N][N],b[N];
int main(){
	freopen("s.in","r",stdin);
	freopen("s.out","w",stdout);
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin>>n;
	if(n==2){
		puts("-1");
		return 0;
	}
	if(n%2==1){
		for(int i = 1;i<=n;i++){
			for(int j = 1;j<=n;j++)
				cout<<(i-1)*n+j<<" ";
			cout<<endl;
		}
		return 0;
	}
	if(n%4==0){
		for(int i = 1;i<=n;i+=2)
			for(int j = 1;j<=n;j+=2){
				ans[i][j] = ans[i+1][j+1] = i/2+1;
				ans[i+1][j] = ans[i][j+1] = n-ans[i][j];
			}
		for(int i = 1;i<=n/2;i++)
			ans[n][i] = ans[n-1][i] = 0;
	}
	if(n%4==2){
		ans[1][1] = n/2-1,ans[1][2] = n/2+1;
		ans[2][1] = 1,ans[2][2] = n-1;
		ans[3][1] = n/2,ans[3][3] = n-1,ans[3][4] = n/2+1;
		ans[4][2] = n/2,ans[4][3] = 1,ans[4][4] = n/2-1;
		for(int i = 5;i<=n/2+3;i++)
			ans[1][i] = ans[2][i] = n/2;
		for(int i = 5;i<=n;i+=2){
			ans[3][i] = ans[4][i+1] = 1;
			ans[3][i+1] = ans[4][i] = n-1;
		}
		ans[5][1] = ans[6][2] = 1;
		ans[5][2] = ans[6][1] = n-1;
		for(int i = 3;i<=n;i+=2){
			ans[5][i] = ans[6][i+1] = n/2-1;
			ans[5][i+1] = ans[6][i] = n/2+1;
		}
		for(int i = 7;i<=n;i+=2){
			for(int j = 1;j<=n;j+=2){
				ans[i][j] = ans[i+1][j+1] = i/2-1;
				ans[i][j+1] = ans[i+1][j] = n-ans[i][j];
			}
		}
	}
	b[0] = 1;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++)
			cout<<ans[i][j]+n*(b[ans[i][j]]++)<<" ";
		cout<<endl;
	}
	return 0;
}

T3 函数值

题解

好吧剩下两道题我没改，直接放题解吧

#include<bits/stdc++.h>
#define cs const
using namespace std;
cs int N = 1e6 + 5;
int read(){
	int cnt = 0, f = 1; char ch = 0;
	while(!isdigit(ch)){ ch = getchar(); if(ch == '-')f = -1; }
	while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();
	return cnt * f;
}
typedef long long ll;
int n, y[N], q; ll a[N], sum[N], ans[N];
#define mp make_pair
typedef pair<int, int> pi;
vector<pi> v[N];
int top, sta[N], L[N];
ll calc(int y, int x, int u){
	return sum[y] - sum[u] + 1ll * (x + u) * a[u];
}
int main(){
	freopen("y.in", "r", stdin);
	freopen("y.out", "w", stdout);
	n = read(), q = read(); 
	for(int i = 1; i <= n; i++) a[i] = read(), sum[i] = sum[i-1] + a[i];
	for(int i = 1; i <= q; i++){
		int x = read(), y = read();
		v[y].push_back(mp(x, i));
	}
	L[0] = 1e9;
	for(int i = 1; i <= n; i++){
		while(top && calc(i, L[top - 1] - 1, sta[top]) >= calc(i, L[top - 1] - 1, i)) --top;
		if(top){
			int l = L[top], r = L[top - 1] - 1;
			while(l < r){
				int mid = (l+r) >> 1;
				if(calc(i, mid, sta[top]) < calc(i, mid, i)) r = mid;
				else l = mid + 1;
			} L[top] = l;
		} sta[++top] = i; L[top] = - i;
		for(int j = 0; j < v[i].size(); j++){
			int x = v[i][j].first, id = v[i][j].second;
			int l = 1, r = top;
			while(l < r){
				int mid = (l+r) >> 1;
				if(L[mid] <= x - i) r = mid;
				else l = mid + 1;
			} ans[id] = calc(i, x - i, sta[l]);
		}
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
	return 0;
}

T4 宝石

题解

#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
cs int Mod = 998244353;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }
int mul(int a, int b){ return 1ll * a * b % Mod; }
void Add(int &a, int b){ a = add(a, b); }
void Dec(int &a, int b){ a = dec(a, b); }
void Mul(int &a, int b){ a = mul(a, b); }
int ksm(int a, int b){
	int ans = 1; for(; b; b >>= 1, Mul(a, a))
	if(b & 1) Mul(ans, a); return ans;
} int sgn(int x){ return x & 1 ? Mod - 1 : 1; }
cs int N = 3e7 + 50, M = N >> 1;
int n, d, r;
int fc[M], ifc[M];
int f[M], g[M];
int inv(int x){ return mul(ifc[x], fc[x - 1]); }
void fc_init(int n){
	fc[0] = fc[1] = ifc[0] = ifc[1] = 1; 
	for(int i = 2; i <= n; i++)
	fc[i] = mul(fc[i - 1], i);
	ifc[n] = ksm(fc[n], Mod - 2);
	for(int i = n - 1; i; i--)
	ifc[i] = mul(ifc[i + 1], i + 1);
}
vector<int> prm;
bool ex[M];
void sieve(int n){
	for(int i = 2; i <= n; i++){
		if(!ex[i]) prm.pb(i);
		for(int p : prm){
			if(p * i > n) break;
			ex[p * i] = true;
			if(i % p == 0) break;
		}
	}
}
int main(){
	freopen("o.in", "r", stdin);
	freopen("o.out", "w", stdout);
	cin >> n >> d >> r; 
	fc_init(max(n, d));
	for(int i = 0; i + r <= n; i++)
	if(i & 1) f[i + r] = mul(ifc[i], ifc[r]);
	else f[i + r] = dec(0, mul(ifc[i], ifc[r]));
	for(int i = n; i; i--)
	f[i] = mul(f[i - 1], inv(i)); 
	f[0] = 1;
	for(int i = 0, mt = 1; i <= n; i++)
	Mul(f[i], mt), Mul(mt, n - i);
	for(int i = 0; i <= n; i++)
	f[i] = dec(0, mul(r, f[i]));
	Add(f[0], r);
	for(int i = 0; i + r <= n; i++)
	if(i & 1) g[i + r - 1] = mul(ifc[i], ifc[r - 1]);
	else g[i + r - 1] = dec(0, mul(ifc[i], ifc[r - 1]));
	for(int i = n; i; i--)
	g[i] = mul(g[i - 1], inv(i)); g[0] = 1;  
	for(int i = 0, mt = 1; i < n; i++)
	Mul(g[i], mt), Mul(mt, n - i - 1);
	for(int i = n; i; i--)
	g[i] = mul(n, g[i - 1]); g[0] = 0;
	for(int i = 0; i <= n; i++)
	Add(f[i], g[i]);
	sieve(d);
	for(int z : prm)
	for(int i = 1; i * z <= d; i++)
	Add(f[i * z], f[i]);
	int ans = 0, mt = 1; 
	for(int i = 0; i <= d; i++){
		Add(ans, mul(f[d - i], mul(ifc[i], mt)));
		if(i < d) Mul(mt, n + i);
	} Mul(mt, ifc[d]);
	mt = ksm(mt, Mod - 2);
	cout << add(r, mul(mt, ans)); return 0;
}

最后，对冯施源大佬万分感谢，出了这么一套题，让我做的十一分开心（此人已疯

标签：ch,校内,int,top,230722,freopen,ans,return
From： https://www.cnblogs.com/cztq/p/17663134.html

相关文章

  • 230719校内赛
    T1usaco20febEquilateralTrianglesP题面我就不描述了题解首先我们是不可能暴力计算每一对点距离的我们可以想一想如何将斜着的数个点转换为横着或竖着的数个点，这样会使我们的计算方便许多不难想到的是切比雪夫距离，当然考场上也容易推出这玩意（我就是考场现推的）然后就是如......
  • [校内]极端题
    0811T1计数练习题意作为一名普及组选手，小\(A\)喜欢数数。一天，小\(A\)学习了排列相关的知识。定义一个长度为\(n\)的序列\(p_{1...n}\)是一个\(n\)阶排列，当且仅当\(p_{1...n}\)都是\([1,n]\)中的正整数且它们两两不同。小\(A\)想数排列。为了让数排列更有趣，......
  • [校内] 计数练习
    0811T1计数练习题意作为一名普及组选手，小\(A\)喜欢数数。一天，小\(A\)学习了排列相关的知识。定义一个长度为\(n\)的序列\(p_{1...n}\)是一个\(n\)阶排列，当且仅当\(p_{1...n}\)都是\([1,n]\)中的正整数且它们两两不同。小\(A\)想数排列。为了让数排列更有趣，......
  • YTEZ校内数学集训笔记
    计数原理例题1：用一个大写的英文字母或一个阿拉伯数字给教室里的一个座位编号，总共能编出多少种不同的号码？或：\(a\wedgeb\)有\(a\)无\(b\)有\(b\)无\(a\)有\(a\)有\(b\)且：\(a\veeb\)有\(a\)有\(b\)非：\(┐a\)无\(a\)答案：英文字母共有26个，阿拉伯数......
  • 7.23 校内 test
    T1题面：给一个由A,B组成的操作序列，A代表全部取反，B代表+1，每次给出操作区间l,r和一个01串，问经过操作序列中\([l,r]\)的操作后的01串，强制在线。观察性质，发现一次取反会使后面的所有+1变成-1，随便用前缀和维护即可。T2给一个网格图，每个格子有权值，切割一次的代价是被......
  • 「赛后总结」20230722 CSP 模拟赛
    「赛后总结」20230722CSP模拟赛点击查看目录目录「赛后总结」20230722CSP模拟赛反思题解T1回文思路代码T2快速排序思路代码T3混乱邪恶思路代码T4校门外歪脖树上的鸽子思路吓死我了我还以为K8He不更博了。为啥前天模拟赛不写啊？打过，没参加。为啥昨天模拟赛不......
  • 230722 做题记录 // 网络流二十四题 (1/24)
    知耻而后勇，物极必反。A.星际转移问题http://222.180.160.110:1024/contest/3952/problem/1如果就按照题目给的路线图，我们显然无法考虑到飞船到达的时刻。同时\(n\)和\(m\)又很小，我们就知道了，「人不能两次踏进同一条河流」，1时刻的站\(p\)和2时刻的站\(p\)也不能是......
  • 230715校内赛
    T1串背景形貌昳丽的西克是風子国王嫡系军队的general,同时也兼任風子王国驻绿鸟国的外交官。西克喜欢在蕉含流群里与其它王国的使者蕉含流,但前段时间由于说怪话被来自绿鸟国意识形态不完全的国王驱含逐出境。西克非常愤怒,想要说出一句最怪的话,但他却忙于敢览求社的......
  • 230713校内赛
    MC党狂喜系列比赛T1命令方块题目描述实际上这道题与命令方块没有什么关系。给定\(n\)个字符串\(s_i\),将它们按给出的顺序排开。你每次可以交换任意两个字符串的位置。通过交换,这些字符串最终需要满足如下的性质:对于任意的\(i<j<k\),必须有:\(lcp(s_i,s_j)\gel......
  • 230712校内赛
    T1前缀和题目描述给你一个字符串，求所有长度为偶数的前缀在整个字符串中出现的次数和。输入格式共一行，一个字符串S输出格式共一行，输出一个整数，代表长度为偶数的前缀在整个字符串中出现的次数和样例输入数据1abababc输出数据16输入数据2isdashagayisdashagaydas......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99