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