BestCoder Round #85

sum

Accepts: 640

Submissions: 1744

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

YES
NO

题意：求字符串中是否存在连续子串和为m的倍数，是则输出"YES“，否则输出”NO“

分析：
维护前缀和，当时没想到，太弱，如果当前模得到0或者两个莫数据相同则YES，否则NO，可以用抽屉原理，(N>=M)->YES

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;
const int maxn = 1e5+10;

bool used[maxn];

int main()
{
    int n, m;
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        memset(used, 0, sizeof(used));
        used[0] = true;
        int sum = 0,x;
        bool flag = false;
        if(n>=m)
        {
            flag=1;
            for(int i=0;i<n;i++) scanf("%d",&x);
        }
        else
        {
            for(int i = 0; i < n; ++ i)
            {
                scanf("%d", &x);
                sum += x;
                sum %= m;
                if(used[sum]) {
                    flag=true;
                }
                else used[sum] = true;
            }
        }
        printf("%s
", flag ? "YES" : "NO");
    }
    return 0;
}
/*
2
3 3
3 1 1
3 7 
6 6 9
*/

domino

Accepts: 462

Submissions: 1498

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

题意：
给出一列扑克牌的距离，有k次机会，n张扑克牌，问全部推倒扑克牌，扑克牌的最小高度。

分析：
贪心排序，找到前n-k个数相加即可。（详情见bc的题解）

//贪心，将位置距离重排，取前n-k个，奥妙重重
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
int t,k,n,a[100100];LL sum;
int main()
{
    for(scanf("%d",&t);t--;)
    {
        scanf("%d%d",&n,&k);
        for(int i=0;i<n-1;i++) scanf("%d",a+i);
        if(n<=k) printf("%d
",n);
        else
        {
            sort(a,a+n-1);sum=n;
            for(int i=0;i<n-k;i++) sum+=a[i];
            printf("%I64d
",sum);
        }
    }
}

abs

Accepts: 136

Submissions: 927

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

题意：
给出一个数，找到距离该数最小的数（满足题目要求）。

分析：
明显要对x开方，然后枚举35000以内的素数，如果能够连除某个素数两次及以上，则重新进入循环，否则输出，记住是对开根号后的x加减，int乘以int要加LL，应对爆int的情况出现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
using namespace std;

#define LL long long
#define F(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define rep(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define rek(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define Cpy(a,b) memcpy(a,b,sizeof(b))

const int P=sqrt(1e9);
int prime[P];
bool is_prm[P+5];

bool check(LL x){
    for(int i=1;i<=prime[0]&&prime[i]*prime[i]<=x;++i)
        if(x%prime[i]==0&&(x/=prime[i])%prime[i]==0)
            return 0;
    return 1;
}
inline LL ab(LL x)
{
    return x<0?-x:x;
}
int t;
LL x;
const int eps=1e-8;
int main()
{
    //欧拉筛
    for(int i=2;i<=P;++i){
        if(!is_prm[i])prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&i*prime[j]<=P;++j){
            is_prm[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }

    //freopen("in.txt","r",stdin);
    for(scanf("%d",&t);t--;)
    {
        scanf("%I64d",&x);
        for(int yy1=sqrt(x),yy2=yy1+1;;)
        {
            //printf("%lf
",sqrt(x));
            //printf("yy1=%I64d y1=%I64d
",yy1,y1);
            //printf("%I64d
",yy1);
            if(yy1>1&&(x-(LL)yy1*yy1<(LL)yy2*yy2-x))
            {
                if(!check(yy1)) goto f;else {
                printf("%I64d
",(x-(LL)yy1*yy1));goto flag;
                }
                f:yy1--;
            }
            ///yy2=(LL)sqrt(y2);//printf("yy2=%I64d y2=%I64d
",yy2,y2);
            else
            {
                if(!check(yy2)) goto g;else {
                printf("%I64d
",((LL)yy2*yy2-x));goto flag;
                }
                g:yy2++;
            }
        }
        flag:;
    }
    return 0;
}