比赛地址

VJudge

原2015长春现场赛题目

[A]Too Rich

题意

给出一个整数p.现在有面值分别为1,5,10,20,50,100,200,500,1000,2000的硬币若干枚.求最多用多少枚硬币可以表示出p.

题解

首先假如没有50和500面值的硬币,那么每一种硬币的面值都是前面硬币面值的倍数,可以相互转化进而求出最少和最多的方案数.然后考虑逆向求答案,用硬币总价值减去p,然后尝试用尽可能少的硬币去表示这一面值.枚举选取的50和500面值的情况,接下来贪心选取即可.

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>

#define LL long long
#define max(a, b) ((a)>(b)?(a):(b))
#define min(a, b) ((a)<(b)?(a):(b))

constexpr int PRICE[10]{1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000};
constexpr int M_50(4), M_500(7);

LL count[11];
LL ans, all_cnt, all_sum, goal;
void solve(int res, int cnt, int s100, int s1000)
{
    if (res < 0)
        return;
    for (int i = 9; i >= 0; i--)
    {
        //printf("%d %d %d %d %d %d\n",res,count[i],PRICE[i],cnt,s100,s1000);
        if (i == 4)
        {
            if (res >= 100 * s100)
            {
                res -= 100 * s100;
                cnt -= s100 * 2;
            }
            else
            {
                cnt -= res / 100 * 2;
                res %= 100;
            }
            continue;
        }
        if (i == 7)
        {
            if (res >= 1000 * s1000)
            {
                res -= 1000 * s1000;
                cnt -= s1000 * 2;
            }
            else
            {
                cnt -= res / 1000 * 2;
                res %= 1000;
            }
            continue;
        }

        if (res >= count[i] * PRICE[i])
        {
            res -= count[i] * PRICE[i];
            cnt -= count[i];
        }
        else
        {
            cnt -= res / PRICE[i];
            res %= PRICE[i];
        }
    }
    //  printf("%d %d\n",res,cnt);
    if (res == 0)
        ans = max(cnt, ans);
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        ans = -1;
        all_cnt = all_sum = 0;
        scanf("%lld", &goal);
        for (int i=0; i<10; ++i)
        {
            scanf("%lld", count+i);
            all_cnt += PRICE[i] * count[i];
            all_sum += count[i];
        }
        if (all_cnt < goal)
        {
            puts("-1");
            continue;
        }
        if (all_cnt == goal)
        {
            printf("%lld\n", all_sum);
            continue;
        }

        solve(all_cnt - goal, all_sum, count[4] / 2, count[7] / 2);
        if (count[4] && count[7])
            solve(all_cnt - goal - 50 - 500, all_sum - 2, (count[4] - 1) / 2, (count[7] - 1) / 2);
        if (count[4])
            solve(all_cnt - goal - 50, all_sum - 1, (count[4] - 1) / 2, count[7] / 2);
        if (count[7])
            solve(all_cnt - goal - 500, all_sum - 1, count[4] / 2, (count[7] - 1) / 2);
        printf("%lld\n", ans);
    }

#ifdef _KEVIN
    system("pause");
#endif
    return 0;
}

[B]Count a×b

题意

给定m,然后定义

f(m)=\sum_{a=0}^{m-1}\sum_{b=0}^{m-1} ab \ \ mod \ \ m \neq 0

g(n)=\sum_{d|n}f(d)

题解

首先打表找规律,定义如下辅助函数:

h(d)=d^2-f(d)

观察可知,该函数为积性函数.而且当d是质数的整数次幂时,有如下递推关系:

h(p^{r+1})=ph(p^r)+(p-1)^{r+1}

其中

h(p)=2p-1

因此,可以在log(n)的时间复杂度内计算单个f(d)的值.然后,对n进行质因数分解,然后分别计算f(d),最后再累加得到g(n).总的时间复杂度为

O(T\log n\log n)

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

int cnt[100005], val[100005], tot, n;
int noprime[100005], cnt_p;
unsigned long long int prime[100005];
unsigned long long int ans;

void shai(int top) {
    int i, j;
    for (int i = 2; i <= top; i++) {
        if (!noprime[i])
            prime[++cnt_p] = i;
        for (j = 1; j <= cnt_p && prime[j]*i <= top; j++) {
            noprime[prime[j]*i] = 1;
            if (i%prime[j] == 0) break;
        }
    }
}

unsigned long long int mi(unsigned long long int a, int n) {
    //printf("mi %llu %d\n", a, n);
    if (n == 0) return 1;
    if (n == 1) return a;
    unsigned long long int m = mi(a, n/2);
    m = m * m;
    if (n%2) m *= a;
    return m;
}

void dfs(int n, unsigned long long int m, unsigned long long int f) {
    //printf("%d %llu %llu\n", n, m, f);
    if (n == tot+1) { ans += (m*m-f); return ;}
    unsigned long long now = 1;
    for (int i = 0; i <= cnt[n]; i++) {
        if (i == 0) dfs(n+1, m, f);
        else if (i == 1) {
            now = val[n]*2-1;
            dfs(n+1, m*val[n], f*now);
        } else {
            now = val[n]*now + (val[n]-1)*mi(val[n], i-1);
            dfs(n+1, m*mi(val[n], i), f*now);
        }
    }
    return ;
}

int main(){
    int T; cin >> T;
    shai(100000);
    while(T--) {
        cin >> n;
        tot = 0;
        memset(cnt, 0, sizeof(cnt));
        memset(val, 0, sizeof(val));
        while(n != 1) {
            int flag = 0;
            for (int i = 1; i <= cnt_p; i++)
                if (n%prime[i] == 0) {
                    val[++tot] = prime[i];
                    flag = 1;
                    while(n%prime[i] == 0) {
                        cnt[tot]++;
                        n/=prime[i];
                    } 
                    break;
                }
            if (flag == 0) break;
        }
        if (n != 1) { val[++tot] = n; cnt[tot] = 1; }
        ans = 0;
        dfs(1, 1, 1);
        cout << ans << endl;
    }
    return 0;
}

[E]Rebuild

题意

给出一个多边形各个点的坐标,然后要求以每个顶点为圆心作圆.要求相邻两个顶点的圆要相切.问是否存在这样 的作圆方案.如果存在,输出圆的面积的最小值.

题解

设第一个圆的半径为r.因为已知点的坐标,也就知道了边长.而且题目要求圆要相切,所以可以用r表示出其他所有圆的半径.然后单个圆的面积是关于r的二次函数,总面积也是关于r的二次函数,则一定存在极值.之后三分答案即可.

代码

#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define sc(x) {register char _c=getchar(),_v=1;for(x=0;_c<48||_c>57;_c=getchar())if(_c==45)_v=-1;for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=getchar());x*=_v;}

#define PI 3.14159265358979323846

constexpr int MN(1e4+5);

#define IL inline
#define EPS 1e-6
IL double ABS(double x) {return x>0 ? (x>EPS ? x:0) : (x<-EPS ? -x:0);}
IL double MIN(double a, double b) {return a<b ? a:b;}
IL double MAX(double a, double b) {return a>b ? a:b;}
IL bool eq(double a, double b) {return a>b ? a-b<EPS : b-a<EPS;}
IL bool zero(double x) {return x>0 ? x<EPS : x>-EPS;}
IL int  sign(double x) {return x>0 ? (x>EPS ? 1:0) : (x<-EPS ? -1:0);}
IL double norm(double x) {return x>0 ? (x>EPS ? x+EPS:0) : (x<-EPS ? x-EPS:0);}


typedef struct Po
{
    double x, y;
    Po(void) {}
    Po(double xx, double yy) : x(xx), y(yy) {}
} Vec;
IL double DIST(const Po &p1, const Po &p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

Po a[MN];
double r[MN], len[MN];

double get_ans(double x, int n)
{
    double S = x * x;
    r[0] = x;
    for (int i=1; i<n; ++i)
    {
        r[i] = len[i-1] - r[i-1];
        S += r[i] * r[i];
    }
    return S;
}

double check(int n)
{
    for (int i=0; i<n; ++i)
        if (sign(r[i]) == -1)
            return false;
    return true;
}

int main()
{
    int T;
    sc(T)
    while (T--)
    {
        int n;
        sc(n)
        for (int i=0; i<n; ++i)
            scanf("%lf %lf", &a[i].x, &a[i].y);
        double C = 0, ling_sum = 0, jian_sum = 0;
        for (int i=0; i<n; ++i)
        {
            len[i] = DIST(a[i], a[(i+1)%n]);
            C += len[i];
            if (i&1)
                jian_sum += len[i];
            else
                ling_sum += len[i];
        }

        double L = 0, R = 2e9;
        get_ans(0, n);
        for (int i=0; i<n; ++i)
        {
            if (i&1)
                R = MIN(R, r[i]);
            else
                L = MAX(L, -r[i]);
        }
        if (n&1)    // 唯一解,或无解
        {
            double ans = get_ans(ling_sum - C/2, n);
            if (check(n))
            {
                printf("%.2f\n", ans * PI);
                for (int i=0; i<n; ++i)
                    printf("%.2f\n", r[i]);
            }
            else
                puts("IMPOSSIBLE");
        }
        else    // 三分
        {
            if (not eq(ling_sum, jian_sum) || sign(L-R)>0)
            {
                puts("IMPOSSIBLE");
            }
            else
            {
                while (R-L >= EPS)
                {
                    double ml = (L+L+R) / 3, mr = (L+R+R) / 3;
                    if (sign(get_ans(ml, n) - get_ans(mr, n)) >= 0)
                        L = ml;
                    else
                        R = mr;
                }
                double ans = get_ans((L + R) / 2, n);
                printf("%.2f\n", ans * PI);
                for (int j = 0; j < n; j++)
                    printf("%.2f\n", r[j]);
            }
        }
    }

#ifdef _KEVIN
    system("pause");
#endif

    return 0;
}

[F]Almost Sorted Array

题意

给出一个整数序列.当且仅当这个序列满足删去一个数可以变成单调不增或者单调不减序列,则称这个序列是几乎有序的.求给出的序列是否是几乎有序序列.

题解

设该序列长度为n.求这个序列的最长不增和不降子序列.当且仅当二者中有一个的长度大于等于n-1时是几乎有序的.

代码

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <list>
#include <iostream>
#include <map>
#include <set>

#define GC getchar()
#define _Q_(x) {register char _c=GC,_v=1;for(x=0;_c<48||_c>57;_c=GC)if(_c==45)_v=-1;
#define _H_(x) for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=GC);if(_v==-1)x=-x;}
#define sc(x) _Q_(x)_H_(x)
constexpr int MN(1e6+7);

int a[MN];
int sta[MN];
int LIS(const int n)
{
    int top = 0;
    sta[top++] = a[0];
    for (int i=1; i<n; ++i)
    {
        if (a[i] >= sta[top-1])
            sta[top++] = a[i];
        else
            *std::upper_bound(sta, sta+top, a[i]) = a[i];
    }
    return top;
}
int LDS(const int n)
{
    int top = 0;
    sta[top++] = a[0];
    for (int i=1; i<n; ++i)
    {
        if (a[i] <= sta[top-1])
            sta[top++] = a[i];
        else
            *std::upper_bound(sta, sta+top, a[i], std::greater<int>()) = a[i];
    }
    return top;
}


int main()
{
    int T;
    sc(T)
    while (T--)
    {
        int n;
        sc(n)
        for (int i=0; i<n; ++i)
            sc(a[i])
        int n1 = LIS(n);
        if (n1 < n-1)
        {
            int tp = LDS(n);
            if (tp > n1)
                n1 = tp;
        }
        puts(n1 >= n-1 ? "YES" : "NO");
    }

    return 0;
}

[G]Dancing Stars on Me

题意

给出n个二维平面上的整点,求是否可以构成正n边形.

题解

解法一:

求出这n个点的重心,然后把重心平移到原点.之后对n个点进行直角排序,判断相邻两点的边长以及夹角是否相等.如果相等,则不能构成.

解法二:

有如下定理:

二维坐标平面有且仅有边数为4的整点正多边形.只需要对正方形进行特判即可.n不为4时一定无解.

粗略的证明:

取多边形任意相邻的三点,将外侧的两个点连边,得到一个整点三角形.已知二维空间三角形面积公式:

S=\left| \frac{1}{2}\left| \begin{array}{ccc}\
1&x_1&y_1\\1&x_2&y_2\\1&x_3&y_3 \end{array} \right| \right|

显然,整点三角形面积必为有理数.(更严格地说,是一个整数的二分之一).同时,有

S=\frac{1}{2}ab \sin\alpha

前面三项会得到一个有理数.而当n不为4时,后面的sin一定不是有理数(严格证明并不会),所以产生了矛盾.故不存在边数不为4的整点正多边形.

代码

解法一:

#include <stdio.h>
#include <string.h>
#define sc(x) {register char _c=getchar(),_v=1;for(x=0;_c<48||_c>57;_c=getchar())if(_c==45)_v=-1;for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=getchar());x*=_v;}
#include <cmath>
#include <algorithm>

#define PI 3.14159265358979323846
#define DIST(p1, p2) sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y))

constexpr int MN(1e5);

#define IL inline
#define EPS 1e-5
IL double ABS(double x) {return x>0 ? (x>EPS ? x:0) : (x<-EPS ? -x:0);}
IL double MIN(double a, double b) {return a<b ? a:b;}
IL double MAX(double a, double b) {return a>b ? a:b;}
IL bool eq(double a, double b) {return a>b ? a-b<EPS : b-a<EPS;}
IL bool zero(double x) {return x>0 ? x<EPS : x>-EPS;}
IL int  sign(double x) {return x>0 ? (x>EPS ? 1:0) : (x<-EPS ? -1:0);}
IL double norm(double x) {return x>0 ? (x>EPS ? x+EPS:0) : (x<-EPS ? x-EPS:0);}

struct Point
{
    double x, y;
    double at;

    double operator ^(const Point &o) const
    {
        return x*o.y - y*o.x;
    }

    bool operator <(const Point &o) const
    {
        return at < o.at || at == o.at && x < o.x;
    }
} a[MN];
double mul(const Point &a, const Point &b, const Point &c)
{
    return (b.x-a.x)*(c.y-b.y) - (b.y-a.y)*(c.x-b.x);
}

int stack[MN];

int main()
{
    int T;
    sc(T)
    double avrx, avry;
    while (T--)
    {
        int n;
        sc(n)
        avrx = avry = 0;
        for (int i=0; i<n; ++i)
        {
            scanf("%lf %lf", &a[i].x, &a[i].y);
            avrx += a[i].x;
            avry += a[i].y;
        }
        avrx /= n, avry /= n;
        for (int i=0; i<n; ++i)
        {
            a[i].x -= avrx;
            a[i].y -= avry;
            a[i].at = atan2(a[i].x, a[i].y);
        }
        std::sort(a, a+n);

        bool convex = true;
        int sg = sign(mul(a[0], a[1], a[2]));
        for (int i=1; i<n; ++i)
        {
            if (sg != sign(mul(a[i], a[(i+1)%n], a[(i+2)%n])))
            {
                convex = false;
                break;
            }
        }

        bool ok = convex;
        if (ok)
        {
            double dd = DIST(a[0], a[n-1]);
            for (int i=1; i<n; ++i)
            {
                if (!eq(dd, DIST(a[i], a[i-1])))
                {
                    ok = false;
                    break;
                }
            }
        }

        puts(ok ? "YES" : "NO");
    }
}

解法二:

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 110
#define EPS 1e-5
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int T,i,j,n;
double x[N],y[N],a[N];

inline bool cmp(double x,double y){return x<y;}
inline double Abs(double x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline LL Max(LL a,LL b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline double Dis(int a,int b){
    return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
}

inline void Solve(){
    int i=0,j=0,s=0;
    double X=0,Y=0;
    X=x[1]+x[2]+x[3]+x[4];
    Y=y[1]+y[2]+y[3]+y[4];
    x[5]=1.0*X/4;   y[5]=1.0*Y/4;
    for (i=1;i<=4;i++)  a[++s]=Dis(5,i);
    sort(a+1,a+1+s,cmp);
    if (Abs(a[1]-a[4])<EPS) printf("YES\n");
    else printf("NO\n");
}


int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        for (i=1;i<=n;i++)  scanf("%lf%lf",&x[i],&y[i]);
        if (n!=4){
            printf("NO\n");
            continue;
        }
        Solve();
    }
    return 0;
}

[H]Partial Tree

题意

给出一个节点数为n的树.树上所有边还没有添加.现在给出一个节点的度数为d时所获得的价值f(d).求怎样连边,使得所有节点的价值总和最大.

题解

首先,一棵树的节点度数总和为2n-2.根据Prufer数列可以得知,一棵节点为n的树和一个长度为n-2的整数序列一一对应.而且无论怎么分配这2n-2个度数,只要每个节点的度数都合法,就一定能根据Prufer数列构造出一棵树.因此,该问题转化为了一个背包问题.背包容量为2n-2,而且要正好装满n个物品.物品的价值和体积分别是节点的价值与度数.考虑到有物品数量的限制,所以可以先假设给每个节点分配了一个度数,然后背包容量变成了n-2.此时,度数带来的价值会发生变化.f(d)变为了f(d)-f(1).这时相当于已经没有了物品数量的限制了,直接按照下面的DP方程DP即可.

f[i]=Max(f[i],f[j]+a[i-j+1])

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define N 200010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f3f3f3f3fLL
using namespace std;

int n,i,j,T;
LL Ans;
LL f[N],a[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline LL Max(LL a,LL b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        for (i=1;i<n;i++)
            scanf("%lld",&a[i]);
        if (n==2){
            printf("%lld\n",a[1]*2);
            continue;
        }
        Ans=(LL)n*a[1];
        for (i=2;i<n;i++)   a[i]-=a[1];
        memset(f,-INF,sizeof(f));
        f[0]=0;
        for (i=1;i<=n-2;i++)
            for (j=0;j<i;j++)
                if (f[j]>-INF)
                    f[i]=Max(f[i],f[j]+a[i-j+1]); 
        printf("%lld\n",Ans+f[n-2]);
    }
    return 0;
}

[J]Chip Factory

题意

给定一个序列a,求下式的最大值.

(a_i+a_j)xor \ a_k \ \ i \neq j \neq k

题解

正解是建一棵Trie树,利用Trie树求最大值.但是时限有15s.而且数据范围极小.所以就直接上暴力了.

代码

#include <cstdio>
#include <iostream>

#define IL inline
#define LL long long
#define ULL unsigned LL
#define _BS 1048576
char _bf[_BS];
char *__p1=_bf,*__p2=_bf;
#define _IO char *_p1=__p1,*_p2=__p2;
#define _OI __p1=_p1,__p2=_p2;

#ifdef _KEVIN
#define GC getchar()
#else
#define GC (_p1==_p2&&(_p2=(_p1=_bf)+fread(_bf,1,_BS,stdin),_p1==_p2)?EOF:*_p1++)
#endif

#define PC putchar
#define _Q_(x) {register char _c=GC,_v=1;for(x=0;_c<48||_c>57;_c=GC)if(_c==45)_v=-1;
#define _H_(x) for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=GC);if(_v==-1)x=-x;}
#define sc(x) _Q_(x)_H_(x)
#define se(x) _Q_(x)else if(_c==EOF)return 0;_H_(x)
#define _G1(_1) int _1;sc(_1)
#define _G2(_1,_2) int _1,_2;sc(_1)sc(_2)
#define _G3(_1,_2,_3) int _1,_2,_3;sc(_1)sc(_2)sc(_3)
#define _gG(_1,_2,_3,_get, ...) _get
#define get(...) _gG(__VA_ARGS__,_G3,_G2,_G1, ...)(__VA_ARGS__)
#define F(i,l,r) for(int i=(l);i<(r);++i)

template<class T>
void UPRT(const T _){if(_>=10)UPRT(_/10);PC(_%10+48);}
#define UPL(_) UPRT(_),PC(10)  
template<class T>
void PRT(const T _){if(_<0){PC(45),UPRT<ULL>(-(ULL)_);return;}if(_>=10)PRT(_/10);PC(_%10+48);}
#define PL(_) PRT(_),PC(10)

constexpr int MN(1e6+7);

int main()
{
    _IO
    int a[1234];
    get(T)
    while (T--)
    {
        get(n)
        register int i, j, k, tp;

        for (i=0; i<n; ++i)
            sc(a[i])

        int maxx = 0;
        for (i=0; i<n; ++i)
            for (j=i+1; j<n; ++j)
                for (k=j+1; k<n; ++k)
                {
                    if ((tp=a[i]+a[j]^a[k]) > maxx)
                        maxx = tp;
                    if ((tp=a[i]+a[k]^a[j]) > maxx)
                        maxx = tp;
                    if ((tp=a[j]+a[k]^a[i]) > maxx)
                        maxx = tp;
                }
        PL(maxx);
    }

    return 0;
}

[L]House Building

题意

给出Mincraft世界的一个n*m的二维区域,再给出每个位置的建筑高度.然后要求给裸露在空气中的建筑的表面全部贴上玻璃,求需要多少玻璃.不算和地面接触的部分.

题解

签到题

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,j,T;
int a[110][110];
LL Ans;

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline LL Work(int x,int y){
    LL cnt=0;
    if (a[x][y]>a[x-1][y])  cnt+=a[x][y]-a[x-1][y];
    if (a[x][y]>a[x+1][y])  cnt+=a[x][y]-a[x+1][y];
    if (a[x][y]>a[x][y-1])  cnt+=a[x][y]-a[x][y-1];
    if (a[x][y]>a[x][y+1])  cnt+=a[x][y]-a[x][y+1];
    return cnt;
}

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d%d",&n,&m);
        memset(a,0,sizeof(a));
        Ans=0;
        for (i=1;i<=n;i++)
            for (j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
        for (i=1;i<=n;i++)
            for (j=1;j<=m;j++){
                if (a[i][j]==0) continue;
                Ans++;
                Ans+=Work(i,j);
            }
        cout<<Ans<<endl;
    }
    return 0;
}

总结

这场比赛发挥还算不错.中期做思维题明显感觉要顺利了很多.不过前期发现H题很水之后没有立刻切掉,导致吃了两发暴力罚时和耽误的两个小时时间,导致罚时在同过题数垫底.好在做其他题的时候罚时是远小于其他队伍的.希望下次可以吸取教训,不轻易交暴力,能够更快的把大众题做完,提升敲代码的速度.

说点什么
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...