模拟赛小结:2015-2016 ACM-ICPC, NEERC, Northern Subregional Contest

2015-2016 ACM-ICPC, NEERC, Northern Subregional Contest

2019年10月11日 15:35-20:35(Solved 8,Penalty 675)

这两天好像回寝室太早了,导致早早地就躺在床上吸引蚊子。到睡觉的点的时候,蚊子们就已经嗷嗷待哺地聚集到了我的床边。凌晨2:00~4:00的时候被烦得,只能下床喷个六神+开个空调QwQ。早上起不来导致很多东西都咕咕咕了(比如今日中午的市中心觅食计划)。

以后不出意外的话,我们队应该每周三&周六的这个时间打一场模拟赛吧。虽然没有传闻中咖啡鸡一天一套题那么恐怖,不过强度感觉差不多。有没有小伙伴要一起打的呀?(就是你,我的僵尸粉)

昨天这场感觉离金只差一口气了。不过最后还是落在银首。

Problem A. Alex Origami Squares:00:06(+)Solved by Dancepted

开场翻翻题册看到A题题面很短,读了一下发现是个签到。

代码:

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 100005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)

using namespace std;
typedef long long ll;
typedef double db;

/** fast read **/
template <typename T>
inline void read(T &x) {
    x = 0; T fg = 1; char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') fg = -1;
        ch = getchar();
    }
    while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }

int main()
{
    freopen("alex.in", "r", stdin);
    freopen("alex.out", "w", stdout);
    db h, w;
    cin >> h >> w;
    db ans1 = min(h/3, w);
    db ans2 = min(h, w/3);
    db ans3 = min(h/2, w/2);
    db ans = max(ans1, max(ans2, ans3));
    printf("%.6f
", ans);
    return 0;
}
/*
210 297
250 100
*/
View Code

 

Problem H. Hash Code Hacker:00:27(+)Solved by Dancepted & xk

我过了A之后,lh上去敲E。期间我去看了下L,发现预处理一下暴力可做;xk去看了下H和B,B可做;

题解:我问了一下xkH的题意,看了一下样例的哈希值,发现在本题中的哈希函数下,“Hs”和“IT”是相同的(样例的1和4)。那就不用想很多了:相同长度的情况下,其他字符都一样,把“Hs”换成“IT”就是一个新的字符串。枚举[0, k-1]之间的数,把“Hs”当作二进制表示中的0,“IT”当作1,打印出来就好了。

想好思路的时候lh那边也正好传来一声wa(00:23),我和xk商量着哪题写得比较快,就让我先上去敲H。

代码:O(k*logk)

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 100005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)

using namespace std;
typedef long long ll;
typedef double db;

/** fast read **/
template <typename T>
inline void read(T &x) {
    x = 0; T fg = 1; char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') fg = -1;
        ch = getchar();
    }
    while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }


int main()
{
    fast;
    freopen("hash.in", "r", stdin);
    freopen("hash.out", "w", stdout);
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        string res; int tmp = i;
        for (int j = 0; j < 20; j++, tmp>>=1) {
            if (tmp & 1) {
                res += "IT";
            }
            else {
                res += "Hs";
            }
        }
        cout << res << endl;
    }
    return 0;
}
View Code

 

Problem E. Easy Arithmetic:00:42(-1)Solved by lh

昨天这场lh同学过的题我好像都没怎么思考过qwq。我H写完之后xk上去敲B,又传来一声wa(00:35)。我看好久没过题了,忍不住抢键盘写L。敲到一半lh找到了E的bug,改了一发就过了。

代码:(今天看有没有时间补吧,先偷偷贴一发队友的代码

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define lowbit(x) ((-x) & x)
#define ffor(i, d, u) for (int i = (d); i <= (u); ++i)
#define _ffor(i, u, d) for (int i = (u); i >= (d); --i)
#define mst(array, Num, Kind, Count) memset(array, Num, sizeof(Kind) * (Count))
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define MAXV 2005
#define MAXE 3000005
typedef long long ll;
typedef double db;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<db, db> pdd;
const db PI = acos(-1);
const ll MO = 1e9 + 7;
const ll Inv2 = (MO + 1) / 2;
const bool debug = true;
template <typename T>
inline void read(T &x)
{
    x=0;char c;T t=1;while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-'){t=-1;c=getchar();}do(x*=10)+=(c-'0');while((c=getchar())>='0'&&c<='9');x*=t;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args)
{
    read(x), read(args...);
}
template <typename T>
inline void write(T x)
{
    int len=0;char c[21];if(x<0)putchar('-'),x*=(-1);
    do{++len;c[len]=(x%10)+'0';}while(x/=10);_ffor(i,len,1)putchar(c[i]);
}
string s;
int tot = 0;
char ans[MAXV << 2];
inline int ac()
{
    cin >> s;
    int i = 0, len = s.size();
    if (s[i] != '+' && s[i] != '-')
    {
        while (i < len && s[i] != '+' && s[i] != '-')
            ans[++tot] = s[i], ++i;
    }
    while (i < len)
    {
        ans[++tot] = s[i], ++i;
        if (ans[tot] == '+')
        {
            while (i < len && s[i] != '+' && s[i] != '-')
                ans[++tot] = s[i], ++i;
            continue;
        }
        ans[++tot] = s[i], ++i;
        while (i < len && s[i] != '+' && s[i] != '-' && s[i] == '0')
        {
            ans[++tot] = '+', ans[++tot] = s[i];
            ++i;
        }
        if (i < len && s[i] >= '1' && s[i] <= '9')
            ans[++tot] = '+';
        while (i < len && s[i] != '+' && s[i] != '-')
            ans[++tot] = s[i], ++i;
    }
    ffor(i, 1, tot) putchar(ans[i]);
    return 0;
}
int main()
{
    freopen("easy.in", "r", stdin), freopen("easy.out", "w", stdout);
    ac();
    fclose(stdin);
    fclose(stdout);
    return 0;
}
View Code

 

Problem B. Black and White:00:44(-1)Solved by xk

xk想了一会也找到bug了,上去改了一发过了。

代码:偷贴友码

#include<bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < (n); i++)
#define forab(i, a, b) for (int i = (a); i <= (b); i++)
#define forba(i, b, a) for (int i = (b); i >= (a); i--)
#define mset(a, n) memset(a, n, sizeof(a))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) ((int)x.size())
#define endl '
'
#ifdef hat
#define fast
#define de(x) cout  << #x << '=' << x << ' '
#define dee(x) cout  << #x << '=' << x << endl
#else
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define de(x) ((void) 0)
#define dee(x) ((void) 0)
#endif
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int, int> pii;
 
char s[101][101];
 
int main()
{
    freopen("black.in", "r", stdin);
    freopen("black.out", "w", stdout);
    int b, w;
    cin >> b >> w;
    b--, w--;
    cout << 100 << ' ' << 100 << endl;
    forn(i, 50)
    {
        forn(j, 100)
        {
            s[i][j] = '@';
        }
    }
    forab(i, 50, 99)
    {
        forn(j, 100)
        {
            s[i][j] = '.';
        }
    }
    int r = 0, c = 0;
    while(w)
    {
        s[r][c] = '.';
        c += 2;
        if(c >= 100)
        {
            r += 2;
            c = 0;
        }
        w--;
    }
 
    r = 51, c = 1;
    while(b)
    {
        s[r][c] = '@';
        c += 2;
        if(c >= 100)
        {
            r += 2;
            c = 1;
        }
        b--;
    }
    forn(i, 100)
    {
        printf("%s
", s[i]);
    }
}
View Code

 

Problem L. Lucky Chances:00:51(+)Solved by Dancepted

开场就看到有人做L了,结果到三十多分钟的时候才拿到键盘很心痛。

题解:预处理一下每个点往左(右、上、下)看,能看到的最大值,如果在边界上,那就是-1。然后暴力跑一边把每个点的答案加起来就好了。

代码:O(rc)

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 105
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)

using namespace std;
typedef long long ll;
typedef double db;

/** fast read **/
template <typename T>
inline void read(T &x) {
    x = 0; T fg = 1; char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') fg = -1;
        ch = getchar();
    }
    while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }

int a[N][N];
int L[N][N], R[N][N], U[N][N], D[N][N];
int main()
{
    freopen("lucky.in", "r", stdin);
    freopen("lucky.out", "w", stdout);
    int r, c;
    cin >> r >> c;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            read(a[i][j]);
    memset(L, -1, sizeof L);
    memset(R, -1, sizeof R);
    memset(U, -1, sizeof U);
    memset(D, -1, sizeof D);
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++) {
            L[i][j+1] = max(L[i][j+1], max(L[i][j], a[i][j]));
            U[i+1][j] = max(U[i+1][j], max(U[i][j], a[i][j]));
        }
    for (int i = r; i >= 1; i--)
        for (int j = c; j >= 1; j--) {
            R[i][j-1] = max(R[i][j-1], max(R[i][j], a[i][j]));
            D[i-1][j] = max(D[i-1][j], max(D[i][j], a[i][j]));
        }
    int ans = 0;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++) {
            if (a[i][j] > L[i][j])
                ans++;
            if (a[i][j] > R[i][j])
                ans++;
            if (a[i][j] > U[i][j])
                ans++;
            if (a[i][j] > D[i][j])
                ans++;
        }
    cout << ans << endl;
    return 0;
}
/*
3 4
5 3 9 10
1 8 8 2
4 3 4 3
*/
View Code

 

Problem D. Distribution in Metagonia:01:12(+)Solve by xk & Dancepted

我在开L的时候xk读了D题,看我过了L就拿过来跟我讨论了一番。

题解:如果给出的n是偶数,则不断提出2,n /= 2,直到变成n奇数;如果n是奇数,则找最大的x,使得3x<当前的n,n -= 3x。最后比如121就可以表示成121 = 34+23(31+21(1))= 34+2331+24

相邻两次-3x必定会差1个系数2,并且反证法可以证明最后一定会得到1或0,所以是可行的。时间复杂度为O(tlogn),每次最多logn个数,是小于100个的。

代码:O(tlogn)(偷贴友码)

#include<bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < (n); i++)
#define forab(i, a, b) for (int i = (a); i <= (b); i++)
#define forba(i, b, a) for (int i = (b); i >= (a); i--)
#define mset(a, n) memset(a, n, sizeof(a))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) ((int)x.size())
#define endl '
'
#ifdef hat
#define fast
#define de(x) cout  << #x << '=' << x << ' '
#define dee(x) cout  << #x << '=' << x << endl
#else
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define de(x) ((void) 0)
#define dee(x) ((void) 0)
#endif
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int, int> pii;
 
ll p3[100];
ll ans[100];
 
int main()
{
    // #ifndef hat
    freopen("distribution.in", "r", stdin);
    freopen("distribution.out", "w", stdout);
    // #endif
    int T;
    fast;
    cin >> T;
    p3[0] = 1;
    int cur = 1;
    for(;; cur++)
    {
        p3[cur] = p3[cur-1] * 3;
        if(p3[cur] >= 1e18) break;
    }
    while(T--)
    {
        ll n;
        cin >> n;
        int cnt = 0;
        int p = cur, ansp = 0;
        while(n)
        {
            if(n % 2 == 0) {
                cnt++;
                n /= 2;
            } else {
                while(p3[p] > n) {
                    p--;
                }
                ans[ansp++] = (1LL << cnt) * p3[p];
                n -= p3[p--];
            }
        }
        cout << ansp << endl;
        forn(i, ansp)
        {
            cout << ans[i] << ' ';
        }
        cout << endl;
    }
}
View Code

 

在D做完之后,本场的水题应该都已经切完了(6个水题对我们思维题选手&手速队来说,真的很友好!),进入度日如年的挂机时间。

 

Problem C. Concatenation:02:08(+)Solved by lh

lh做完E之后就一个人开C去了。据说是个exkmp,但是我没细想。

代码:(偷贴友码)

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define lowbit(x) ((-x) & x)
#define ffor(i, d, u) for (int i = (d); i <= (u); ++i)
#define _ffor(i, u, d) for (int i = (u); i >= (d); --i)
#define mst(array, Num, Kind, Count) memset(array, Num, sizeof(Kind) * (Count))
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define MAXV 100050
#define MAXE 3000005
typedef long long ll;
typedef double db;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<db, db> pdd;
const db PI = acos(-1);
const ll MO = 1e9 + 7;
const ll Inv2 = (MO + 1) / 2;
const bool debug = true;
template <typename T>
inline void read(T &x)
{
    x=0;char c;T t=1;while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-'){t=-1;c=getchar();}do(x*=10)+=(c-'0');while((c=getchar())>='0'&&c<='9');x*=t;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args)
{
    read(x), read(args...);
}
template <typename T>
inline void write(T x)
{
    int len=0;char c[21];if(x<0)putchar('-'),x*=(-1);
    do{++len;c[len]=(x%10)+'0';}while(x/=10);_ffor(i,len,1)putchar(c[i]);
}
char s[MAXV], t[MAXV];
int cnt[30] = {};
inline int ac()
{
    scanf("%s%s", s, t);
    int lens = strlen(s), lent = strlen(t);
    ll ans = 1ll * lens * lent;
    --lens, lent -= 2;
    ffor(i, 1, lens) ++cnt[s[i] - 'a'];
    ffor(i, 0, lent) ans -= (ll)cnt[t[i] - 'a'];
    cout << ans;
}
int main()
{
    freopen("concatenation.in", "r", stdin), freopen("concatenation.out", "w", stdout);
    ac();
    fclose(stdin);
    fclose(stdout);
    return 0;
}
View Code

 

Problem J. Journey to the “The World’s Start”:03:25(-3)Solved by Dancepted & xk

这两天在看分块,逮着一道题就想用分块做。结果被xk:“这个不是二分就好了吗?”

题解:如果存在i < j && pi > pj,那么显然选择pj比较优秀。所以可以预处理一下所有的p,使得p是一个严格递增的序列。

然后考虑在这个序列上二分下标,对每个下标check能否在t时间内到达n号地铁站。

check的部分用单调队列优化的dp跑一跑就出来了。(应该是个单调队列的经典用法)

背锅:第一发提交的时候,没有考虑爆int的情况,wa3是因为check的时候把pr当作r放进去跑dp了,幸好xk找bug能力拉满,给我找出来了QwQ。

代码:O(nlogn)

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 50005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)

using namespace std;
typedef long long ll;
typedef double db;

/** fast read **/
template <typename T>
inline void read(T &x) {
    x = 0; T fg = 1; char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') fg = -1;
        ch = getchar();
    }
    while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }

int n;
ll t;
struct Node{
    int p; ll v;
};
vector <Node> ps;
ll d[N];

deque <int> dq;
ll f[N];
bool check(ll r) {
    memset(f, 0, sizeof f);
    while (!dq.empty()) dq.pop_back();
    dq.push_back(1);
    for (int i = 2; i <= n; i++) {
//        int tmp = dq.front();
        while (i - dq.front() > r)
            dq.pop_front();
        int p = dq.front();
        f[i] = f[p] + d[i];
        while (!dq.empty() && f[dq.back()] >= f[i])
            dq.pop_back();
        dq.push_back(i);
    }
    return f[n] + n-1 <= t;
}
int main()
{
    freopen("journey.in", "r", stdin);
    freopen("journey.out", "w", stdout);
    read(n, t);
    for (int i = 1; i <= n-1; i++) {
        ll v; read(v);
        while (sz(ps) && ps.back().v >= v)
            ps.pop_back();
        ps.push_back(Node{i, v});
    }
    for (int i = 2; i <= n-1; i++)
        read(d[i]);
    int l = 0, r = sz(ps)-1;
    ll ans = ps[r].v;
    while (l <= r) {
        int mid = (l+r) >> 1;
        if (check(ps[mid].p)) {
            ans = min(ans, ps[mid].v);
            r = mid-1;
        }
        else
            l = mid+1;
    }
    cout << ans << endl;
    return 0;
}
/*
4 4
1 2 3
1 4
*/
View Code

 

UPD:

补题:Problem F. Fygon(dfs模拟+高斯消元)

思路:

答案的式子肯定是n的多项式,并且因为循环的个数不超过6,所以最高项只能是n6

因此直接用dfs模拟出n=0~6时lag执行的次数,然后跑一下高斯消元得到答案。

为了防止误差,高斯消元的时候要用分数类。

dfs的复杂度为O(6^6),高斯消元的时间复杂度为O(7^3*分数类gcd的log)。

代码:O(66+73log)

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 25
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)

using namespace std;
typedef long long ll;
typedef double db;

/** fast read **/
template <typename T>
inline void read(T &x) {
    x = 0; T fg = 1; char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') fg = -1;
        ch = getchar();
    }
    while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }


int tot = 0;
string s[N];

struct Node{
    bool is_lag;
    int dep;
    char nama;
    char limit;
};
vector <Node> v;
stack <Node> sn;
unordered_map <char, int> val;
int getsum(int pos) {
    Node tmp = v[pos];
    if (tmp.is_lag) return 1;

    int limit;
    if (isdigit(tmp.limit))
        limit = tmp.limit - '0';
    else
        limit = val[tmp.limit];
    ll sum = 0;
    for (int i = 0; i < limit; i++) {
        val[tmp.nama] = i;
        for (int j = pos+1; j < sz(v); j++) {
            if (v[j].dep == tmp.dep+1)
                sum += getsum(j);
            if (v[j].dep <= tmp.dep)
                break;
        }
    }
    return sum;
}
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a%b);
}
struct fraction{
    ll a, b; // a/b
    void upd() {
        if (b < 0) a = -a, b = -b;
        ll g = abs(gcd(a, b));
        a /= g;
        b /= g;
    }
    fraction(ll _a = 0, ll _b = 1) : a(_a), b(_b) {}
    fraction operator + (const fraction& x) const {
        fraction res = {a*x.b + x.a*b, b*x.b};
        res.upd();
        return res;
    }
    fraction operator - (const fraction& x) const {
        fraction res = {a*x.b - x.a*b, b*x.b};
        res.upd();
        return res;
    }
    fraction operator * (const fraction& x) const {
        fraction res = {a*x.a, b*x.b};
        res.upd();
        return res;
    }
    fraction operator / (const fraction& x) const {
        fraction res = {a*x.b, b*x.a};
        res.upd();
        return res;
    }
    void print() {
        if (b == 1)
            printf("%I64d", a);
        else
            printf("%I64d/%I64d", a, b);
    }
};
fraction gaoa[10][10], gaob[10];
fraction res[10];
void Gauss(int n) {
    int tmpr = 0;
    for (int c = 0; c < n; c++) {//c-th column
        for (int r = tmpr; r < n; r++) {//r-th row
            if (gaoa[r][c].a > 0) {
                for (int ci = 0; ci < n; ci++) {
                    swap(gaoa[r][ci], gaoa[tmpr][ci]);
                }
                swap(gaob[r], gaob[tmpr]);
                break;
            }
        }
        if (gaoa[tmpr][c].a == 0)
            continue;
        for (int r = 0; r < n; r++) if (r != tmpr) {
            if (gaoa[r][c].a != 0) {
                fraction mul = gaoa[r][c] / gaoa[tmpr][c];
                for (int ci = 0; ci < n; ci++) {
                    gaoa[r][ci] = gaoa[r][ci] - gaoa[tmpr][ci] * mul;
                }
                gaob[r] = gaob[r] - gaob[tmpr] * mul;
            }
        }
        tmpr++;
    }
    for (int c = 0; c < n; c++) {
        res[c] = gaob[c] / gaoa[c][c];
    }
}
void input() {
    freopen("fygon.in", "r", stdin);
    freopen("fygon.out", "w", stdout);
    while (getline(cin, s[tot++]));
    for (int i = 0; i < tot; i++) {
        int dep = 0;
        for (int j = 0; s[i][j] != '';) {
            switch (s[i][j]) {
                case ' ':
                    j += 4;
                    dep++;
                    break;
                case 'l':
                    v.push_back(Node{true, dep, ' ', ' '});
                    j += 3;
                    break;
                case 'f':
                    v.push_back(Node{false, dep, s[i][j+4], s[i][j+15]});
//                    cout << s[i][j+4] << ' ' << s[i][j+15] << endl;
                    j += 18;
                    break;
            }
        }
    }
}

#define st 0
int main()
{
    input();
    for (int i = 0; i <= 6; i++) {
        val.clear(); val['n'] = i+st;
        ll sum = 0;
        for (int j = 0; j < sz(v); j++) if (v[j].dep == 0)
            sum += getsum(j);
        gaob[i] = fraction{sum, 1};
        gaoa[i][0] = fraction{1, 1};
        for (int j = 1; j <= 6; j++) {
            gaoa[i][j] = fraction{gaoa[i][j-1].a * (i+st), 1};
        }
    }
    Gauss(7);
    bool firstprint = true;
    for (int i = 0; i <= 6; i++) {
        if (res[i].a) {
            if (firstprint)
                firstprint = false;
            else {
                if (res[i].a < 0) {
                    printf("-");
                    res[i].a = -res[i].a;
                }
                else {
                    printf("+");
                }
            }

            if (res[i].a == 1 && res[i].b == 1 && i >= 1) {
                printf("n");
                for (int j = 2; j <= i; j++)
                    printf("*n");
            }
            else {
                res[i].print();
                for (int j = 1; j <= i; j++)
                    printf("*n");
            }
//            res[i].print();
//            for (int j = 1; j <= i; j++)
//                printf("*n");
        }
    }
    puts("");
    return 0;
}
/*
for i in range(n):
    for j in range(i):
        lag
for x in range(5):
    for y in range(n):
        for z in range(n):
            lag
    lag

for d in range(n):
    for e in range(d):
        for k in range(e):
            lag
*/
View Code

总结:

本场的前期题比较多,而我们队切水题又比较厉害,所以做起来很舒服。没有出太多的差错。

中期题中的J给我和xk跌跌撞撞地搞过去了,lh也很给力,过了我和xk都几乎没法下手的C。

本场算是发挥得已经算比较好的一场了,不过写J的时候,我其实有点飘了,导致死都找不出来bug,幸好有xk帮我找bug。

如果没有飘,可以少差不多200的罚时,差不多银区1、2的位置,也会多一些时间去开后面的F、G,如果能开出一道,差不多就金了。

不过虽然想起来容易,差一题就是差一题,离金还是有差距的。

最近打下来的感觉:打崩了差不多靠手速苟个银,打得好的话,距金还差一口气,冲金之路很坎坷啊!这段时间还是要提升一下细节,新入手的算法也要巩固一下。还有希望南京站发挥得好一点,少几个神仙队,给我们留个金吧QwQ。

 

原文地址:https://www.cnblogs.com/Lubixiaosi-Zhaocao/p/11666067.html