国庆训练测试

已结束 OI 开始于: 2025-10-5 13:30 3.5 小时 主持人: 6

正式比赛要加文件读写，放到main函数开头，拿第一题举例，读写文件名为"val", 格式如下

#include <stdio.h> 
#include <iostream> 
int a[100050];
using namespace std; 
int main() { 
	freopen("val.in","r",stdin); //从文件中读取输入
	freopen("val.out","w",stdout); //输出答案到文件中
	int n;
	cin >> n;
	for (int i = 0; i < n; i ++) cin >> a[i];
    return 0; 
}

题解

B

我们可以使用二分答案的方法来求解最小宽度：

  1. 确定搜索范围： • 下界 l = max_length（最大单词长度）。

    • 上界 r = total_sum + (N - 1)（所有单词长度和加上 N-1 个空格）。

  2. 二分搜索： • 计算中间值 mid = (l + r) / 2。

    • 检查宽度 mid 是否可行（即是否能用不超过 M 行显示所有单词）。

    • 如果可行，则尝试更小的宽度（r = mid - 1）；否则，尝试更大的宽度（l = mid + 1）。

  3. 检查函数 check： • 从第一个单词开始，尽可能多地将单词放入当前行，直到添加下一个单词会导致行宽超过 mid（包括空格）。 • 如果当前行已有单词，添加新单词时需要加一个空格。 • 如果当前行放不下，则换行（行数加 1）。 • 如果行数超过 M 或某个单词本身长度超过 mid，则返回 False；否则，遍历完所有单词后返回 True。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
int a[MAXN];
int n, m;
long long sum;
bool check(long long mid)
{
    long long num = 1;
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (ans + a[i] <= mid)
        {
            ans += a[i];
            if (i < n - 1)
            {
                ans++;
            }
        }
        else
        {
            num++;
            ans = a[i];
            if (i < n - 1) ans++; 
        }
    }
    if (num <= m)return true;
    return false;
}
int main() 
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) 
    {
        cin >> a[i];
        sum += a[i];
    }
    long long l = sum / m, r = sum + n - 1;
    long long ans = r;
    while (l <= r) 
    {
        long long mid = (l + r) / 2;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else 
        {
            l = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

C

考虑计算每个中位数 (p_i) 的贡献：

  • 对于 (pj>pi)(p_j > p_i) 令 (aj=1)(a_j=1)，对于 (pj<pi)(p_j<p_i) 令 (aj=−1)(a_j=-1)。问题转化为统计满足 (l≤i≤r)(l\le i\le r) 且[∑j=lraj=0] [ \sum_{j=l}^{r} a_j = 0 ]的区间 ([l,r]) 的个数。
  • 从(i) (i) 往左扫描并累计和 sj=∑k=jiak, s_j=\sum_{k=j}^{i} a_k, 用一个计数数组记录各个取值的出现次数。
  • 类似地，从 (i)(i) 往右扫描并累计和tj=∑k=ijak, t_j=\sum_{k=i}^{j} a_k,询问取值为(−tj)的(s) (-t_j) 的 (s) 的数量并累加。
  • 时间复杂度(O(n2)) (O(n^2))。
#include <bits/stdc++.h>
#define int long long
using namespace std;
#pragma GCC optimize("O1,O2,O3,O4,O5,Og,Os,Ofast,inline,-ffast-math")
int n,ans,cnt,k;
int a[10020],s[10020];
signed main(){
	freopen("book.in","r",stdin);
	freopen("book.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			s[j]=0;
		}
		cnt=a[i];
		s[cnt]=1;
		ans+=i*i*cnt;
		for(int j=i+2;j<=n;j+=2){
			s[a[j-1]]=1,s[a[j]]=1;
			if(a[j-1]>cnt){
				if(a[j]>cnt){
					for(int k=cnt+1;k<=n;k++){
						if(s[k]){
							cnt=k;
							break;
						}
					}

				}
				ans+=i*j*cnt;
			}else{
				if(a[j]<cnt){
					for(int k=cnt-1;k>=1;k--){
						if(s[k]){
							cnt=k;
							break;
						}
				
				}
				ans+=i*j*cnt;
			}
		}
	}
	cout<<ans;
	return 0;
}

D

注意到两类操作并不会改变单调性：对于任意 x≤yx \le y，在操作后仍然满足 x′≤y′x' \le y'。

将原序列升序排序，可以分别二分出最小和最大的下标。

时间复杂度 O!(n⋅log⁡max⁡∣Ai∣)O!\left(n \cdot \log \max |A_i|\right)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int a[N];
int la[N];
bool is[N];
int query[N];
int x[N];
int s[N];
int t[N];
int n,q,L,R;
int cal(int i){
//	cout<<"\ncal "<<a[i]<<"-------\n";
	if(is[i]) return la[i];
	int now=a[i];
	for(int j=1;j<=q;j++){
		if(query[j]==1){
			if(now>=x[j]){
				now=(now+s[j])*t[j];
//				cout<<"op="<<query[j]<<" "<<now<<"\n";
			}
		}else{
			if(now<=x[j]){
				now=(int)((now-s[j])/t[j]);
//				cout<<"op="<<query[j]<<" "<<now<<"\n";
			}
		}
	}
	la[i]=now;
	is[i]=true;
//	cout<<"\n\n";
	return now;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q>>L>>R;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
//	for(int i=1;i<=n;i++){
//		cout<<a[i]<<" ";
//	}
//	cout<<"\n";
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		cin>>query[i]>>x[i]>>s[i]>>t[i];
	}
//	for(int i=1;i<=n;i++){
//		cout<<cal(i)<<" ";
//	}
//	cout<<"\n\n";
	int pos_L;
	int pos_R;
	int l=0,r=n+1;
	while(l<r){
		int mid=(l+r)>>1;
		int ne=cal(mid);
//		cout<<l<<" "<<r<<" : "<<mid<<" "<<ne<<"\n";
		if(ne>=L){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	pos_L=l;
	//  cout<<pos_L<<"\n";
	if(l==0){
		pos_L=1;
	}
	
	l=0,r=n+1;
	while(l<=r){
		int mid=(l+r)>>1;
		int ne=cal(mid);
//		cout<<l<<" "<<r<<" : "<<mid<<" "<<ne<<"\n";
		if(ne>R){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	pos_R=r;
	if(r==n+1){
		pos_R=n;
	}
	// cout<<pos_R<<"\n";
	
	cout<<pos_R-pos_L+1<<"\n";
}
/*
1 -2 3

*/

E

  • 首先求出最短路，并构造最短路 DAG。
  • 按照 dist\text{dist}排序，保留满足du+wu,v=dvd_u+w_{u,v}=d_v 的边 u→vu\to v，成为 DAG。
  • DAG 上 11 到 xx 的路径，与原图 11 到 xx 的最短路一一对应，转化为 DAG 上的问题。
  • 恒等式：$$\sum_{j=1}^{n_i}\sum_{k=j+1}^{n_i}|d_{i,j}|\cdot|d_{i,k}| =\frac12\Bigg[\Big(\sum_{j=1}^{n_i}|d_{i,j}|\Big)^2-\sum_{j=1}^{n_i}|d_{i,j}|^2\Bigg]. $$
  • 问题转化为求所有路径的长度和，以及路径长度平方和。
  • 设 (fx,gx,hx)(f_x,g_x,h_x) 分别表示所有从 11 到 xx 的路径长度 (0,1,2)(0,1,2) 次方之和。则对边 (y→x)(y\to x)：

$ f_x \mathrel{+}= f_y,\qquad g_x \mathrel{+}= g_y+f_y,\qquad h_x \mathrel{+}= h_y+2g_y+f_y.

#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define N 300005
#define PII pair <int, int>
#define int long long
const int INF = 1e18;
const int mod = 1e9 + 7;
using namespace std;

int qpow(int a, int b){
	int ans = 1;
	while(b){
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

int n, m;
vector <PII> g[N];
vector <int> from[N];
int dis[N];
bool vis[N];

void Get_dis(){
	memset(dis, 127, sizeof dis);
	priority_queue < PII, vector<PII>, greater<PII> > q;
	q.push({0, 1});
	dis[1] = 0;
	while(!q.empty()){
		int u = q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(PII p : g[u]){
			int v = p.first, w = p.second;
			if(dis[v] > dis[u] + w){
				from[v].clear(); from[v].push_back(u);
				dis[v] = dis[u] + w;
				q.push({dis[v], v});
			} else if(dis[v] == dis[u] + w)
				from[v].push_back(u);
		}
	}
}

vector <int> e[N];
int r[N], cnt[N];
int d1[N], d2[N];
void topo(){
	queue <int> q;
	for(int i = 1; i <= n; i++)
		if(r[i] == 0){
			q.push(i);
			cnt[i]++;
		}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int v : e[u]){
			r[v]--;
			cnt[v] = (cnt[v] + cnt[u]) % mod;
			d1[v] = (d1[v] + d1[u] + cnt[u]) % mod;
			d2[v] = (d2[v] + d2[u] + cnt[u] + 2 * d1[u]) % mod;
			if(r[v] == 0) q.push(v);
		}
	}
}

void solve(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int u, v, w; cin >> u >> v >> w;
		g[u].push_back({v, w});
	}
	Get_dis();
	for(int u = 1; u <= n; u++)
		for(int fa : from[u]){
			e[fa].push_back(u);
			r[u]++;
		}
	topo();
	int ans = 0;
	for(int i = 1; i <= n; i++){
		int tmp = (d1[i] * d1[i] % mod - d2[i] + mod) % mod;
		ans += tmp * qpow(2, mod - 2) % mod;
	}
	cout << ans;
}

signed main(){
    freopen("Bob.in", "r", stdin);
    freopen("Bob.out", "w", stdout);
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	int T = 1;
//	cin >> T;
	while(T--)
		solve();
	return 0;
}

本场比赛采用灵活时间模式，你需要在参加后的指定时间内完成比赛。

文件

文件名 大小
down.zip 84.2 KiB
状态
已结束
规则
OI
题目
5
开始于
2025-10-5 13:30
结束于
2025-10-5 17:00
持续时间
3.5 小时
主持人
参赛人数
6
  1. Language
  2. 兼容模式
  3. 主题
  3. 鲁ICP备2023031993号-1
  6. Worker 0, 33ms
  7. Powered by Hydro v5.0.0-beta.6 Community