## ZOJ Monthly, August 2014

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

ZOJ Monthly, August 2014

 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

```#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

F(L,R,M)=∑L≤i<j≤R[G(i,j)=M]
数据保证 M∈GS ，并且 |GS|≤50

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

ZOJ 3801 Determinant and Matrix

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

ZOJ 3802 Easy 2048 Again

PS：计分规则还是挺麻烦的，需要好好理解

```#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;
}
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

G(x) = x ⊕ ⌊x / 2⌋
C(x)=2n−x,C(0)=0

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

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

```#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

```#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;
}
```

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

ZOJ 3807 Just a Palindrome

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

ZOJ 3808 The Sum of Unitary Totient