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;
}

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