—— Summon, Light!
0%

FJNU 低年级程序设计竞赛

发表于 更新于 Valine：

B-捧杯

受力分析。。。贴这题主要是因为看到了向量化简有一个很简洁的作法~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int gcd(int a,int b)
{
    if (a==0||b==0) {
        return max(a+b,1);//cool~
    }
    while (b) {
        int t=b;
        b=a%b;
        a=t;
    }
    return a;
}

void spfy(int &a,int &b)
{
    int g=gcd(abs(a),abs(b));
    a/=g;b/=g;
}

int main()
{
    int T;
    scanf("%d",&T);
    while (T--) {
        int x0,y0,n;
        int ansx=0,ansy=0;
        scanf("%d%d",&x0,&y0);
        scanf("%d",&n);
        for (int i=1;i<=n;i++) {
            int x,y;
            scanf("%d%d",&x,&y);
            ansx+=x-x0;
            ansy+=y-y0;
        }
        spfy(ansx,ansy);
        printf("%d %d\n",ansx,ansy);
    }
    return 0;
}

C-汪老司机

交错dp。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N=10010;
const ll INF=1LL<<60;
ll a[N],b[N];
ll f[N][20],g[N][20];

int main()
{
    int T,n,k;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&k);
        for (int i=1;i<=n;i++) {
            scanf("%lld",&a[i]);
        }
        for (int i=1;i<=n;i++) {
            scanf("%lld",&b[i]);
        }
        for (int i=1;i<=n;i++) {
            f[i][0]=f[i-1][0]+a[i];
            g[i][0]=g[i-1][0]+b[i];
        }
        for (int j=1;j<=k;j++) {
            for (int i=1;i<=n;i++) {
                f[i][j]=min(f[i-1][j]+a[i],g[i-1][j-1]+a[i]);
                g[i][j]=min(g[i-1][j]+b[i],f[i-1][j-1]+b[i]);
            }
        }
        printf("%lld\n",min(f[n][k],g[n][k]));
    }
    return 0;
}

D-蒟蒻的任务分配

这题是比赛的时候唯一没什么想法的。先贴一下通过某种py搞到的出题人的题解：

首先考虑到，没有可容性的事件一定是不能同时进行的，也就是说，最短也要花费这些事件长度的总和，如果这些事件长度的总和是大于有可容性的事件的长度的总和，那么最少耗费时间就是没有可容性事件的长度总和

首先因为最多同时开两件事，那么自然尽量把所有事分为尽量相等的两段，如果能够安排出合理的方案，那么该解一定是最优的。

接下来证明在这种条件下若分成尽量相等的两段，总能够安排出合理的序列使得任务能够正常进行

假设分为两段第一段里没有可容性的事件总长为x1,有可容性的事件的总长为y1。第二段里没有可容性的事件总长为x2,有可容性的事件的总长为y2。那么有x1+x2<=y1+y2不妨设x1+y1<=x2+y2那么有如下安排方案先做第一段里没有可容性的事件，同时开始做第二段里有可容性的事件如果y2 < x1,那么根据x1+y1<=x2+y2,一定有x2>y1,那么有x1+x2>y1+y2，与该情况相悖,所以y2>=x1。那么在第一段没有可容性的事件全部做完后，开始做第一段有可容性的事件然后在第二段有可容性的事件全部做完后，开始做第二段没有可容性的事件随后任务肯定能够没有冲突的顺利进行，证毕。

接下来只需要把所有任务分为时间尽量相等的两半就可以了，这一部分可以背包暴力跑01背包时间复杂度是 $O(t*n^2*costi)$ 但是考虑到costi很小，可以记录costi相等的事件的数量，然后做二进制优化优化后的时间复杂度为 $O(t*cost^2*nlogn)$

本题放过了暴力01背包的解法

不得不说这个想法很巧妙，反正我肯定是想不到的。
虽然出题人说01背包能过但是我并没有过。。。于是我还是写了多重背包。。。结果因为没清f[] WA了好几次。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=1005;
int cnt[20],f[N*10],s[2];

int main()
{
    int T,n;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        s[0]=s[1]=0;
        memset(f,0,sizeof(f));
        memset(cnt,0,sizeof(cnt));
        for (int i=1;i<=n;i++) {
            int ci,fi;
            scanf("%d%d",&ci,&fi);
            s[fi]+=ci;
            cnt[ci]++;
        }
        if (s[0]>s[1]) {
            printf("%d\n",s[0]);
            continue;
        }
        s[0]+=s[1];
        int lim=s[0]/2;
        for (int i=1;i<=10;i++) {
            for (int k=1;k<=cnt[i];k<<=1) {
                for (int j=lim;j>=k*i;j--) {
                    f[j]=max(f[j],f[j-k*i]+k*i);
                }
                cnt[i]-=k;
            }
            for (int j=lim;j>=cnt[i]*i;j--) {
                f[j]=max(f[j],f[j-cnt[i]*i]+cnt[i]*i);
            }
        }
        printf("%d\n",s[0]-f[lim]);
    }
    return 0;
}

还找到了一个理解起来难度可能小一点的方法：Problem D: 蒟蒻的任务分配 自行查阅

F-火柴棒

这题比赛的时候想的差不多了但是就是有一点没想到。。。
首先总火柴数是偶数的话肯定都是1。
总火柴数是奇数的话：

  1. 如果其余拼成奇数个1，把中间一个1变成7即可
  2. 如果其余拼成偶数个1，把四个1和多余的1根变为三个7，放在首尾和中间；如果不到四个1，用两个1和多余的1根变为一个5，可以发现这时总火柴数一定是5。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int w[10]={6,2,5,5,4,5,6,3,7,6};
char s[10010];

int main()
{
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%s",s);
        int l=strlen(s),sts=0;
        for (int i=0;i<l;i++) {
            sts+=w[s[i]-'0'];
        }
//        printf("%d\n",sts);
        if (sts%2==0) {
            int k=sts/2;
            while (k--) {
                putchar('1');
            }
            puts("");
            continue;
        }
        int k=sts/2;
        if (k&1) {
            k/=2;
            for (int i=1;i<=k;i++) {
                putchar('1');
            }
            putchar('7');
            for (int i=1;i<=k;i++) {
                putchar('1');
            }
            puts("");
        } else {
            if (sts==5) {
                puts("5");
                continue;
            }
            k=k/2-1;
            putchar('7');
            for (int i=1;i<k;i++) {
                putchar('1');
            }
            putchar('7');
            for (int i=1;i<k;i++) {
                putchar('1');
            }
            putchar('7');
            puts("");
        }
    }
    return 0;
}

G-PY

若有 $i < j$，则 $F(i, j) = ai + ( aj + j ) - i$ ，倒着枚举 $i$ ，边更新最优的 $j$ 边更新答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N=100010;
long long a[N];

int main()
{
    int T,n;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        for (int i=1;i<=n;i++) {
            scanf("%lld",&a[i]);
        }
        ll ans=-1;
        int pre=n;
        for (int i=n-1;i>0;i--) {
            ans=max(ans,a[i]+a[pre]+pre-i);
            if (a[i]+i>a[pre]+pre) pre=i;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

终于可以假装自己AK了，over~

Coda

看到其他学校搞的比赛，不得不说比我们正式正规的多。。。
不过有底气邀请全国的我们也不说了 =。= 话说那天给的网址是日本的服务器然后现在已经登不了了。。。FJNU 可以的，很66666

咖啡，亦我所需也