UOJ Logo kb的博客

博客

成绩问题

2019-08-25 17:35:12 By kb

由于操作失误,在公布成绩时没有把程序评测完,现在已经在题库中为大家重测,请大家自行查看

0302Week01t1测试

2019-03-09 08:15:35 By kb

数学方法高于一切暴力

众所周知考试的时候数学方法太强了,虽然当时先搞了优先队列,但是我计算了一下时间复杂度,发现可能会T!!因此,果断抛弃这个方法,那就模拟吧!

#include<cstdio>
#include<algorithm>
using namespace std;
#define kb 1000005
#define ll long long

inline ll read()
{
    ll ans=0, w=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')    w=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans*w;
}

ll a[kb], tmax, tmin, js;
int main()
{
    int n=read();
    int k=read();
    for(int i=1; i<=n; i++)    a[i]=read();
    sort(a+1, a+n+1);
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<a[i]; j++)
        {
            tmin+=a[i]-j;
            js++;
            if(js==k)    break;
        }
        if(js==k)        break;
    }
    for(int i=n; i>=1; i--)
    {
        for(int j=0; j<a[i]-a[i-1]; j++)
        {
            if(k>=n-i+1)
            {    
                tmax+=(a[i]-j)*(n-i+1);
                k-=n-i+1;
            }
            else
            {
                tmax+=(a[i]-j)*k;
                printf("%lld %lld", tmax, tmin);
                return 0;
            }
            if(k<=0)    break;
        }
        if(k<=0)        break;
    }
    printf("%lld %lld", tmax, tmin);
    return 0;
}

唯一需要注意的一点就是一定要记得在第一大的数减到第二个数一般大的时候,要把两个数一块减(就因为忘记写这个乘法,满分变零分)。再加一个特判够不够一块减,不够的话只能加一部分。

364水题题解

2019-02-12 08:06:19 By kb

364水题题解

这道题是考试时候最水的一道题。

30分做法

n是小于等于5的,因此可以手动模拟啊qwq。暴力三十分到手。

另外30分做法

#include<cstdio>
using namespace std;
int main()
{
    printf("0");
}

好的,这三十分也到手了,是不是感觉很水。这时候你应该发现了,只要图是联通的,就不需要建立神圣城。

因此,只需要统计一下单点的数量,相信你们都会......

满分做法

#include<cstdio>
using namespace std;
#define kb 100010
bool bj[kb]; 
int main()
{
    int n, m, u, v, ans=0;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d", &u, &v);
        bj[u]=bj[v]=1;
    }
    for(int i=1; i<=n; i++)
        if(!bj[i])    ans++;
    printf("%d", ans);
    return 0;
}

话说这道题考试的时候代码被卡掉了,只拿了四十分,但是这个思路确实很简单吧。

友好城市题解

2018-12-07 18:02:30 By kb

这道题不就是最长不下降子序列,建议回去看看

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    using namespace std;
    #define kb 5010

    struct Edge{
        int from, to;
    }E[kb];
    int dp[kb];
    bool map[kb][kb];

    bool cmp(Edge a, Edge b)
    {
        if(a.from>b.from)
            return false;
        else
            return true;
    }

    int main()
    {
        int n, u, v;
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d", &E[i].from, &E[i].to);
            dp[i]=1;
        }
        sort(E+1, E+n+1, cmp);
        for(int i=2; i<=n; i++)
            for(int j=1; j<i; j++)
                if(E[j].to<=E[i].to)
                    dp[i]=max(dp[i], dp[j]+1);
        int max=0;
        for(int i=1; i<=n; i++)
            if(dp[i]>dp[max])
                max=i;
        printf("%d", dp[max]);
        return 0;
    }

emm,就是这个,我之前打的是sort不对好吧,不要复制

sort用法,kb出品

2018-12-07 16:15:48 By kb

作为一个最菜的人还要打这个东西.....如果没看懂来问我算了....

    #include<iostream>
    #include<algorithm>                        //这个是sort的头文件,编译不解释。
    #define kb 5010                            //宏定义,作用和const int差不多。
    struct Edge
    {
        int from, to;                        //自定义结构体from存边的起始点,to存边的重点。
    };
    bool cmp(Edge a, Edge b)
    {
        if(a.from>b.from)
            return false;
        else
            return true;                    //sort函数的判断函数,false表示交换,true表示不变。
    }
    Edge E[kb];                                
    int main()
    {
        sort(E+1, E+n+1, cmp);                //第一个参数是数组起始坐标(这里从1开始使用的), 第二个参数是结束坐标,然后是判断函数。
    }

emm就这样,代码肯定过不去了,大概就这个意思,自己打吧。

kb Avatar