现在的位置: 首页 > 综合 > 正文

ZOJ Monthly, August 2014

2018年12月25日 ⁄ 综合 ⁄ 共 6247字 ⁄ 字号 评论关闭

ZOJ Monthly, August 2014

官方题解:http://wzimpha.sinaapp.com/archives/670

太弱了,简直不忍直视!!


ZOJ MONTHLY, AUGUST 2014

A

Abs Problem

39.87% (321/805)

B

Bike in ZJU

4.06% (5/123)

C

Calculation

8.23% (7/85)

D

Determinant and Matrix

7.14% (1/14)

E

Easy 2048 Again

18.12% (62/342)

F

Function

19.04% (8/42)

G

YY's Minions

52.73% (183/347)

H

Machine

25.91% (234/903)

I

Incircle and Circumcircle

18.08% (87/481)

J

Just a Palindrome

5.88% (2/34)

K

The Sum of Unitary Totient

28.57% (2/7)


ZOJ 3798 Abs Problem

给你一个数 n ,要求构造一个 n 的排列 a1,a2,…,an ,令 bi=|ai−bi−1|,b1=a1 ,满足 bn 最大,同样构造一个满足 bn 最大。

打表找规律,就A了。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<functional>
#include<vector>

using namespace std;
int ansmin, ansmax;
void calc(int n) {
    if(n%4==0) {
        ansmin = 0;
        ansmax = n/2*2;
    } else if(n%4==1) {
        ansmin = 1;
        ansmax = (n+2)/2*2 - 1;
    } else if(n%4==2) {
        ansmin = 1;
        ansmax = (n+1)/2*2 - 1;
    } else if(n%4==3) {
        ansmax = n/2*2;
        ansmin = 0;
    }
}
const int maxn = 50000 + 1000;
int a[maxn], b[maxn];
int main() {
    int n;
    while(~scanf("%d", &n)) {
        //calc(n);
        //printf("%d %d\n", ansmin, ansmax);
        int mn = 0 , mx = 0;
        for(int i=n; i>=1; --i) {
            a[n-i+1] = i;
            mn = abs(a[n-i+1] - mn);
        }

        for(int i=n-1; i>=1; --i) {
            b[n-i] = i;
            mx = abs(b[n-i] - mx);
        }
        b[n] = n;
        mx = abs(b[n] - mx);
        printf("%d %d\n", mn, mx);
        for(int i=1; i<=n; ++i) {
            printf("%d ", a[i]);
            if(i<n) printf(" ");
            else printf("\n");
        }
        for(int i=1; i<=n; ++i) {
            printf("%d ", b[i]);
            if(i<n) printf(" ");
            else printf("\n");
        }
    }
    return 0;
}

-------------------------------------------------------------------------------


ZOJ 3799 Bike in ZJU
给你一排宽度不同的车,车之间有空挡,能拿出一辆车的条件是左右空挡之和>=车身。那么搬出一辆车之前,需要搬出这辆车附近几辆车,腾出空间才能搬这辆车。让你求拿出指定车的最小搬车数。


-------------------------------------------------------------------------------


ZOJ 3800 Calculation
给你一个数组 a0,a1,a2,…,an−1 和一个集合 GS ,定义 G(L,R)=gcd(ai),L≤i<R 。
然后有若干个询问,每个询问给你三个数 L,R,M ,计算函数
F(L,R,M)=∑L≤i<j≤R[G(i,j)=M]
 数据保证 M∈GS ,并且 |GS|≤50


-------------------------------------------------------------------------------


ZOJ 3801 Determinant and Matrix
给你一个 n×n 的矩阵 Mn×n(ai,j) ,然后定义 add(Mn×n(ai,j))=Mn×n(ai,j+1),sub(Mn×n(ai,j))=Mn×n(ai,j+1) ,还定义了一个 perm(M) ,这个定义看题目吧。求
|det(sub(M))|⊕(⊕Mi∈perm(M)det(Mi))⊕|det(add(M))|


-------------------------------------------------------------------------------


ZOJ 3802 Easy 2048 Again
某人在一条线上挖宝藏,每个宝藏可以选择要或者不要,不能回头再拿。 宝藏的积分规则和2048的加分规则一致。宝藏会在背包里自动合并。求最高的得分。


PS:计分规则还是挺麻烦的,需要好好理解
这是是一个简单的dp,首先我们发现背包里面有用的状态就是最后递减的部分,前面部分再也没用,因为不能和其他东西合并产生分数。
例如假设背包里面有{32, 4, 8, 4, 2},那么显然32和4就没用了,我们可以直接把这些东西删掉。这样背包里面剩下{8, 4, 2},显然这个可以用二进制表示,于是这道题目就可以搞成一个状态压缩dp,于是随便写写就能过了。

#include<bits/stdc++.h>
using namespace std;
const int maxs = 8192;
const int maxl = 500;
int f[2][maxs+10], a[maxl+10];
int n;

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i=1; i<=n; ++i) scanf("%d", &a[i]);

        memset(f, -1, sizeof f );
        f[0][0] = 0;
        int cur, pre = 0;
        for(int i=1; i<=n; ++i, pre = cur)
            for(int j=0; j<=maxs; ++j)
                if(f[pre][j]>=0) {
                    cur = 1-pre;
                    f[cur][j] = max(f[pre][j], f[cur][j]);
                    if((j&-j)<a[i])
                        f[cur][a[i]] = max(f[pre][j] + a[i], f[cur][a[i]] );
                    else {
                        int add = a[i];
                        int x = j, y = a[i];
                        while(x&y) {
                            x ^= y;
                            y <<= 1;
                            add += y;
                        }
                        x |= y;
                        f[cur][x] = max(f[pre][j] + add, f[cur][x]);
                    }
                }
        int ans = 0;
        for(int i=0; i<=maxs; ++i) ans = max(f[cur][i], ans);
        printf("%d\n", ans);
    }
    return 0;
}

-------------------------------------------------------------------------------


ZOJ 3803 Function
给你一个 n 位二进制数 x=(AnAn−1An−2…A2A1)2 ,给你两个加密方法
 G(x) = x ⊕ ⌊x / 2⌋
C(x)=2n−x,C(0)=0
现在告诉你 G(x),C(x) 的值,但是有些位置未知,求满足条件的 x 有多少个。


-------------------------------------------------------------------------------


ZOJ 3804 YY's Minions
给你一个奇怪的模拟规则,输出最后结果,自己看题吧,反正很简单。


简单模拟题。。。

<pre style="word-wrap: break-word; white-space: pre-wrap;">#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>

using namespace std;
const int maxn = 60;
char g[maxn][maxn], gt[maxn][maxn];
int t[maxn][maxn];
int dir[8][2] = {1, 0, -1, 0, 0, 1, 0, -1, 1, 1, 1, -1, -1, 1, -1, -1};
int n, m, f, k;

void work()
{
    for(int p =0; p<f; ++p) {
        for(int i=0; i<n; ++i) {
            for(int j=0; j<m; ++j) {
                if(g[i][j]=='X'){
                        gt[i][j] = g[i][j];
                        continue;
                }
                int Cnt = 0;
                for(int c=0; c<8; ++c){
                    int x = i+ dir[c][0];
                    int y = j + dir[c][1];
                    if(x<0||x>=n || y<0||y>=m||g[x][y]=='X') continue;
                    if(g[x][y]=='1') Cnt++;
                }

                if(g[i][j]=='1'){
                    if(Cnt<2 || Cnt>3){ gt[i][j] = '0';}
                    else if(Cnt==2 || Cnt==3) {gt[i][j]='1';}
                }else if(g[i][j]=='0'){
                    if(Cnt==3) {gt[i][j] = '1';}
                    else gt[i][j] = '0';
                }
            }
        }
        for(int i=0; i<n; ++i)
        for(int j=0; j<m; ++j) {
            if(t[i][j]!=-1 && t[i][j] == p+1) {
                    gt[i][j] = 'X';
            }
            g[i][j] = gt[i][j];
        }
    }
}

int main()
{
    int tt;
    scanf("%d", &tt);
    while(tt--) {
        scanf("%d%d%d%d", &n, &m, &f, &k);
        for(int i=0; i<n; ++i) {
            scanf("%s", g[i]);
        }
        memset(t, -1, sizeof t );
        while(k--) {
            int T, X, Y;
            scanf("%d%d%d", &T, &X, &Y);
            t[--X][--Y] = T;
        }

        work();

        for(int i=0; i<n; ++i){
            printf("%s\n", g[i]);
        }
    }
    return 0;
}

-------------------------------------------------------------------------------

ZOJ 3805 Machine
有 n 个不同的机器,他们之间的生产关系构成一棵二叉树,要求使用管道把它们连接起来完成这个生产线,并使得整体的宽度最小 ,管道只有两种(具体形状参考题目),不能旋转管道。机器的输入和输出口  只有固定的3个位置。


简单二叉树遍历

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>

using namespace std;
const int maxn = 10000 + 1000;
vector<int> g[maxn];
int n;

int dfs(int u)
{
    int res = 0;
    if(g[u].size()>=1){
        res = dfs(g[u][0]);
    }
    if(g[u].size()>=2)
    {
        int tmp = dfs(g[u][1]);
        if(res == tmp) res = res + 1;
        else res = max(res, tmp);
    }
    return res;
}

int main()
{
    int i, x;
    while(~scanf("%d", &n)) {
        for(int i=0; i<=n; ++i) g[i].clear();
        for(int i=2; i<=n; ++i) {
            scanf("%d", &x);
            g[x].push_back(i);
        }

        int ans = dfs(1) + 1;
        printf("%d\n", ans);
    }
    return 0;
}

-------------------------------------------------------------------------------

ZOJ 3806 Incircle and Circumcircle
给你三角形外接圆和内切圆的半径(R,r),求出一个可行的三角形。
无解的情况(r>R/2)
然后我们能发现等腰三角形就能构造出所有的情况,于是只要算出等腰三角形的情况就好了。
然后二分三角形底边d,比较算出来的内切圆半径r’与r。

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

double r, R;

double h, x;

double cal(double a) {
    double d = a / 2;
    h = sqrt(R * R - d * d) + R;
    x = sqrt(h * h + d * d);
    return a * x * x / (2 * R * (a + x + x));
}

void solve() {
    double lx = 0, rx = sqrt(3.0) * R;
    double mid;
    for (int i = 0; i < 100; i++) {
	mid = (lx + rx) / 2;
	double tmp = cal(mid);
	if (tmp > r) rx = mid;
	else lx = mid;
    }
    cal((lx + rx) / 2);
    printf("%.10lf %.10lf %.10lf\n", mid, x, x);
}

int main() {
    while (~scanf("%lf%lf", &r, &R)) {
	if (r * 2 > R) printf("NO Solution!\n");
	else solve();
    }
    return 0;
}

用下面的定理也能解出来。。。
欧拉定理(几何):设三角形的外接圆半径为R,内切圆半径为r,外心与内心的距离为d,则d^2=R^2-2Rr. 

-------------------------------------------------------------------------------


ZOJ 3807 Just a Palindrome
给你一个长度最大为 105 的字符串,你可以选择两个位置,然后交换他们,求最长回文子串。

hash & SA  不会。。。。
-------------------------------------------------------------------------------

ZOJ 3808 The Sum of Unitary Totient
已知 Φ∗(n)=(p1a1−1)(p2a2−1)⋯(prar−1),n=p1a1p2a2⋯pkak 。求 ∑Ni=1Φ∗(i).  n≤ 109


题意简单,可是想不出2s时限内的算法。 呵呵。。。

抱歉!评论已关闭.