本来没有写博客的打算，可是看完了题解感觉这三道题这么水，我却只做出来一道，实在不应该，还是写点东西吧……
A.sum
问题描述
给定一个数列，求是否存在连续子列和为m的倍数，存在输出YES，否则输出NO
输入描述
输入文件的第一行有一个正整数T(1≤T≤101\leq T \leq 101≤T≤10)，表示数据组数。 接下去有T组数据，每组数据的第一行有两个正整数n,m (1≤n≤100000 1\leq n\leq 1000001≤n≤100000 ,1≤m≤5000 1\leq m\leq5000 1≤m≤5000). 第二行有n个正整数x （1≤x≤1001\leq x\leq 1001≤x≤100）表示这个数列。
输出描述
输出T行，每行一个YES或NO。
输入样例
2
3 3
1 2 3
5 7
6 6 6 6 6
输出样例
YES
NO 分析：
就做出来这一道题-_-||
思路很清晰 输入一个数加一个数进sum 然后取模 如果有两个sum%m相等 那么这两个数之间的序列和%m一定==0 当然 如果有序列和%m==0就不用算差了……
#include<stdio.h>
#include<string.h>
#define M(a,b) memset(a,b,sizeof(a))
int num[];
int sum[];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
M(num,);
int a;
for(int i=;i<n;i++){
scanf("%d",&a);
sum[i]=(sum[i-]+a)%m;
num[sum[i]]++;
}
if(n>=m||num[]!=){ //n>=m是题解抽屉原理的优化
puts("YES");
continue;
}
bool ok=;
for(int i=;i<m;i++)
if(num[i]>) ok=;
printf("%s\n",ok?"YES":"NO");
}
return ;
}
B.domino
问题描述
小白在玩一个游戏。桌子上有n张多米诺骨牌排成一列。它有k次机会，每次可以选一个还没有倒的骨牌，向左或者向右推倒。每个骨
牌倒下的时候，若碰到了未倒下的骨牌，可以把它推倒。小白现在可以随意设置骨牌的高度，但是骨牌高度为整数，且至少为1，并且
小白希望在能够推倒所有骨牌的前提下，使所有骨牌高度的和最小。
输入描述
第一行输入一个整数T(1≤T≤101\leq T \leq 101≤T≤10)
每组数据有两行
第一行有两个整数n和k，分别表示骨牌张数和机会次数。(2≤k,n≤1000002\leq k,n\leq 1000002≤k,n≤100000)
第二行有n-1个整数，分别表示相邻骨牌的距离d，1≤d≤1000001\leq d \leq 1000001≤d≤100000
输出描述
对于每组数据，输出一行，最小的高度和
输入样例
1
4 2
2 3 4
输出样例
9
分析：
一开始把这道题想复杂了 打了好长好长的代码 看了题解感觉真是想多了……
其实就是先把牌的高度存下来 然后贪心 即排序后只取前n-k个值
因为每张牌至少高度是1 所以初始化ans=n 就相当于每张牌一开始都是1 只要往上加间距就好了
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#define M(a,b) memset(a,b,sizeof(a))
using namespace std;
int card[];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,k;
M(card,);
scanf("%d%d",&n,&k);
for(int i=;i<n-;i++)
scanf("%d",&card[i]);
if(k>=n){
printf("%d\n",n);
continue;
}
sort(card,card+n);
long long ans=n;
for(int i=;i<=n-k;i++)
ans+=card[i];
printf("%I64d\n",ans);
}
return ;
}
c.abs
问题描述
给定一个数x，求正整数y≥2y\geq 2y≥2，使得满足以下条件：
1.y-x的绝对值最小
2.y的质因数分解式中每个质因数均恰好出现2次。
输入描述
第一行输入一个整数T（1≤T≤501\leq T\leq 501≤T≤50)
每组数据有一行，一个整数x（1≤x≤10181\leq x\leq {10}^{18}1≤x≤1018)
输出描述
对于每组数据，输出一行y-x的最小绝对值
输入样例
5
1112
4290
8716
9957
9095
输出样例
23
65
67
244
70 分析：
这道题的数据范围是最唬人的了 1e18 解法却是暴力……
因为素数定理（我也是百度才知道）可以将时间复杂度降到允许暴力的范围内……
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#define M(a,b) memset(a,b,sizeof(a))
using namespace std;
long long ans,y;
bool solve(long long a){
long long aa=a;
if(a<) return false;
for(long long i=;i*i<=aa;i++){
if(aa%i==){
if(aa%(i*i)==) //i出现不止一次
return false;
aa/=i;
}
}
ans=min(ans,abs(y-a*a)); //判断solve(x+i)和solve(x-i)一大一小
return true;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%I64d",&y);
long long x=(long long)(sqrt(y)+0.5);//这0.5的精度也会WA
long long i=;
ans=;
bool ok=false;
if(solve(x)){
printf("%I64d\n",abs(y-x*x));
continue;
}
while(true&&!ok){
if(solve(x+i)) ok=true;
if(solve(x-i)) ok=true;
i++;
}
printf("%I64d\n",ans);
}
return ;
}