HZNU Training 1 for Zhejiang Provincial Competition 2020 Xeon第三场训练赛

A. People Couting

给出一个人的固定形状(3*3)的方框内，有许多人合影，最后拍的照不一定完整但每个人至少会出现一部分，问图中有几人

有点思维题的意思，最后发现只要遍历整个图判断满足条件的坐标有任何一个人的“部件”答案就能++，果然这种题一般都有比较巧妙的方法

反思：有时候不要把问题想复杂，很费时这里注意为了方便判断，把图延展

#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#define INF 0x3f3f3f3f
const int maxn = 2e5 + 10;
const double PI = acos(-1.0);
typedef long long ll;
using namespace std;

int vis[110][110];
char s[110][110];

int main() {
    int T, n, m;
    scanf("%d", &T);
    getchar();
    while (T--) {
        int ans = 0;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) scanf("%s", &s[i + 3][3]);
        for (int i = 0; i < n+3; i++) {
            for (int j = 0; j < m+3 ; j++) {
                if (s[i][j + 1] == 'O' || s[i + 1][j + 1] == '|' || s[i + 1][j] == '/' || s[i + 1][j + 2] == '\\' || s[i + 2][j] == '(' || s[i + 2][j + 2] == ')') ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

View Code

B. 大模拟

用C/C++的输出写出一段Cheken Language ，该程序能从标准输入中得到一个栈顶元素为fibo(n)的栈给出7个操作

不得不说挺难想的，相当于用7个底层操作实现循环，判断，递推三个操作等自学一些汇编来填坑

C.多项式题先跳

D.水题

E.字符串题只要有耐心和仔细就能A

G.H.L三个计算几何题没学过属实无奈

K. 贪心+三分+数学给出一段序列，找到一个子集（可重复），有最大的平均数-中位数。

基于如下事实：答案一定是奇数个子集（贪心），可以证明偶数一定不必奇数个更优枚举中位数时，每次贪心地选择中位数左边最右边的数和中位数右边最右边的数，这样选下去后会有峰值

因此可三分答案

亲身实践后三分感觉被精度卡成翔。。遂决定用二分求峰值亲身实践后 CF上用Microsoft VS2017过不了，用GNU G++11 过了。。神奇做这类数字大的题，涉及到除法的题一定要注意精度

#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#define INF 0x3f3f3f3f
#define pii pair<int,int>
const int maxn = 200000 + 10;
const double PI = acos(-1.0);
typedef long long ll;
using namespace std;

int n;
ll a[maxn];
ll sum[maxn];
double maxv;

ll f(int mid,int i) {
    return sum[i] - sum[i-mid-1] + sum[n] - sum[n-mid];
}

int main() {
    scanf("%d", &n);
    pii ans;
    ans.first = 1;

    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    sort(a+1, a + n + 1);

    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
    for (int i = 2; i < n; i++) {
        int l = 1, r = min(i - 1, n - i);
        int mid;
        long long f1, f2;
        while (l < r) {
            mid = l + r >> 1;
            f1 = f(mid, i) * (2 * mid + 3);
            f2 = f(mid + 1, i) * (2 * mid + 1);
            if (f1 > f2) r = mid;
            else {
                l = mid + 1;
                if (f1 == f2) break;
            }
        }
        if (1.0*f(l,i)/(2*l+1)-a[i]>maxv) {
            maxv = 1.0*f(l, i) / (2 * l + 1) - a[i];
            ans.first = i;
            ans.second = l;
        }
    }
    printf("%d\n%lld", ans.second * 2 + 1, a[ans.first]);
    for (int i = 1; i <= ans.second; i++) printf(" %lld %lld", a[ans.first - i], a[n - i + 1]);
    return 0;
}

View Code