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