第二届中国计量大学ACM程序设计竞赛个人赛(同步赛)

本文详细解析了第二届中国计量大学ACM程序设计竞赛中的部分题目,包括A题的快读快写及排序应用,B题利用等差数列求解,I题通过斐波那契数列解决木棍摆放问题,以及G题通过排序和双指针策略计算磁盘调度的总距离。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

A题

快读快写函数 + sort() ;

B题 Little Gyro and Sets

题意:给出n和m,将1~m中为n的倍数的放到a中,否则放到b中,求sum(b)-sum(a).
题解:用等差求和求出1~m 记为sum , n的倍数也可以看做是一个等差数列求和并记为t,然后用sum(b)= sum-t , sum(a) = t , 所以结果为sum-2*t ;

#include <cstdio>
#include <algorithm>
using namespace std ;
typedef long long ll ;
inline int read(){    //快读函数
    int x = 0 , f = 1 ; 
    char ch = getchar();
    while(ch < '0' || ch > '9')    {
        if (ch == '-')
            f = -1 ;
        ch = getchar() ;    
    }
    while(ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + (ch^48) ;
        ch = getchar() ;
    }
    return x*f ;
}
inline void print(int x){    //快写函数
    char f[200] ;
    int t = x>0?x:-x ;
    if (x < 0)    putchar('-') ; 
    int len = 0 ;
    while(t > 0){
        f[len++] = t%10 + '0' ;
        t /= 10 ;
    }
    while(len > 0)    putchar(f[--len]) ;
}
int main(){
    int t ;
    scanf ("%d",&t) ;
    while(t --){
        ll n , m ;
        scanf ("%lld%lld",&n,&m) ;
        ll sum = ((1+m)*m)/2 ;
        ll a = m-m%n ;
        ll b = ((n+a)*a/n)/2 ;
        printf ("%lld\n",sum-2*b) ;
    }
    return 0 ;
}
I题 Logs Stacking

题意:给出n根木棍,问有几种摆放方式(只能摆一层或两层)
题解:写出前几项之后很高兴地发现是一个斐波那契数列,然后看到n的范围就绝望了,经大佬解说发现可以先跑一下程序看看到哪个数开始a[i] > 10000(跑完是15000) ,然后输入n的时候模掉i就可以。

#include <cstdio>
using namespace std ;
const int MOD = 10000 ; 
const int N = 15000 +10 ; 
int a[N] ; 
int main(){
	int t ; 
    scanf ("%d",&t) ; 
    a[1] = 1 , a[2] = 1 ;
	for (int i = 3 ; i <= N ; ++ i){
		a[i] = a[i-1] + a[i-2] ; 
		a[i] %= MOD ; 
	} 
	while(t --){
		int n ;
        scanf ("%d",&n) ;
        printf ("%d\n",a[n%15000]) ;
	}
	return 0  ;
}

G – Disk Scheduling

题意:给出长度为n的数组和m,m每次会移动到最近的点,问移动的总距离。
题解:先排序然后用左右指针模拟移动即可。

#include <iostream>
#include <algorithm>
using namespace std ;
const int N = 1e6 + 10 ;
int a[N] ;  
int main(){
	int n , m ; 
	cin >> n >> m ;
	for (int i = 0 ; i < n ; ++ i)
		cin >> a[i] ;
	sort(a,a+n) ;
	int i = n-1 ; 
    while(i >= 0 && a[i] > m)   -- i ; 
	int l = i , r = i+1 ;
	long long sum = 0 ;  
	while(l >= 0 || r < n){
		if ((l >= 0 && m-a[l] <= a[r]-m) || r == n){	
	//这里m-a[l] <= a[r]-m 要<= 只有< 的话会卡测试点,我也不知道为啥,可能是。。。玄学吧
			sum += m-a[l] ; 
			m = a[l] , -- l ;
		}
		else{
			sum += a[r]-m ;
			m = a[r] , ++ r ;
		}
	} 
	cout << sum << endl ; 
	return 0 ;
}
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值