10.05FZSZ Day2模拟总结

今天的题目难度比昨天小一些，但是太菜的我还是啥也不会。

今天的出题大佬是Heaplex，他的题目中倒是出现了ZZQ，不知道是否是本人？

T1.a

期望得分30，实际得分30

这道题开场发现好像有什么小小的规律，而且既然数据范围都到2*10^6了，这基本就是明示你要是用O（n）的算法了。

一开始我想了暴力30，就是n^2的算法，这样肯定不行。考虑一下当前每个s[i] > i的数，它在下一次旋转之后的贡献是当前的值-1，而s[i] < i的数，它在下一次旋转之后的贡献是当前值+1. 而当前第一个元素不大一样，他的贡献可以直接每次计算出来。

然后我就卡壳了，卡在怎么维护每次旋转之后s[i] > i的个数。

后来听了Dukelv的讲解才知道，其实无需维护！我们把答案看成一长序列，我们完全可以记录在旋转第i次的时候有多少值会从小变大！这个只要一开始的时候预处理一下，维护s[i]-i = -x的数，那么在旋转x次之后就会变正。之后直接线性计算就可以了！（我自己咋就想不出来我太菜了）

然后还有一种做法（题解），其实一个数对于答案序列的贡献是好几段不连续的等差数列，这个可以用二阶差分维护，但是代码长不想写……

看一下老詹的正解代码。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define rg register

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-;

const int maxn = 2e6 + ;

inline ll read()

{

    ll ans = ;

    char ch = getchar(), last = ' ';

    while(!isdigit(ch)) {last = ch; ch = getchar();}

    while(isdigit(ch)) {ans = ans *  + ch - ''; ch = getchar();}

    if(last == '-') ans = -ans;

    return ans;

}

inline void write(ll x)

{

    if(x < ) x = -x, putchar('-');

    if(x >= ) write(x / );

    putchar(x %  + '');

}

void MYFILE()

{

#ifndef mrclr

    freopen("a.in", "r", stdin);

    freopen("a.out", "w", stdout);

#endif

}

int n, a[maxn];

int big = , sma = , num[maxn << ];

ll ans, Min = ;

int main()

{

    MYFILE();

    n = read();

    for(int i = ; i <= n; ++i)

    {

        a[i] = read();

        int x = a[i] - i;

        if(x >= ) ++big, Min += x;

        else ++sma, Min -= x, num[-x]++;

    }

    ans = Min;

    for(int i = ; i <= n; ++i)

    {

        int x = a[i] - , y = n - a[i];

        big--; Min -= x;

        sma++; Min += y; num[i + y]++;

        Min += big - sma + ;

        if(num[i]) big += num[i], sma -= num[i];

        ans = min(ans, Min);

    }

    write(ans); enter;

    return ;

}

T2.maze

期望得分30，实际得分10.

这题一开始没啥思路，直接暴力bfs。然后还有一种神奇的起点不合法的情况没有特判，卡了我20.

之后据说正解是线段树……反正这个矩阵它非常的窄，我们可以把它看成一个序列。对于一个区间[l,r]，我们直接维护第l列所有点到第r列所有点的最短距离。

用线段树上的每一个点代表一个邻接矩阵，直接维护距离。

在修改的时候直接单点修改，然后暴力重构所有涉及到的矩阵，查询的时候合并直接用floyd合并，返回一个结构体（借鉴了老詹的代码，老詹重载了运算符）

我们看一下mrclr大神的代码。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define rg register

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-;

const int maxm = 2e5 + ;

inline ll read()

{

    ll ans = ;

    char ch = getchar(), last = ' ';

    while(!isdigit(ch)) {last = ch; ch = getchar();}

    while(isdigit(ch)) {ans = ans *  + ch - ''; ch = getchar();}

    if(last == '-') ans = -ans;

    return ans;

}

inline void write(ll x)

{

    if(x < ) x = -x, putchar('-');

    if(x >= ) write(x / );

    putchar(x %  + '');

}

void MYFILE()

{

#ifndef mrclr

    freopen("maze.in", "r", stdin);

    freopen("maze.out", "w", stdout);

#endif

}

int n, m, q, a[][maxm];

struct Tree

{

    int l, r;

    int dis[][];

    Tree operator + (const Tree &oth)const

    {

        Tree ret;

        Mem(ret.dis, 0x3f);

        ret.l = l; ret.r = oth.r;

        for(int k = ; k <= n; ++k)

            for(int i = ; i <= n; ++i)

                for(int j = ; j <= n; ++j)

                    ret.dis[i][j] = min(ret.dis[i][j], dis[i][k] +  + oth.dis[k][j]);

        return ret;

    }

}t[maxm << ];

void build(int L, int R, int now)

{

    t[now].l = L; t[now].r = R;

    if(L == R)

    {

        Mem(t[now].dis, 0x3f);

        for(int i = ; i <= n; ++i)

            for(int j = i; j <= n; ++j)

                if(a[j][L]) t[now].dis[i][j] = t[now].dis[j][i] = j - i;

                else break;

        return;

    }

    int mid = (L + R) >> ;

    build(L, mid, now << );

    build(mid + , R, now <<  | );

    t[now] = t[now << ] + t[now <<  | ];

}

void update(int now, int d)

{

    if(t[now].l == t[now].r)

    {

        Mem(t[now].dis, 0x3f);

        for(int i = ; i <= n; ++i)

            for(int j = i; j <= n; ++j)

                if(a[j][t[now].l]) t[now].dis[i][j] = t[now].dis[j][i] = j - i;

                else break;

        return;

    }

    int mid = (t[now].l + t[now].r) >> ;

    if(d <= mid) update(now << , d);

    else update(now <<  | , d);

    t[now] = t[now << ] + t[now <<  | ];

}

Tree query(int L, int R, int now)

{

    if(L == t[now].l && R == t[now].r) return t[now];

    int mid = (t[now].l + t[now].r) >> ;

    if(R <= mid) return query(L, R, now << );

    else if(L > mid) return query(L, R, now <<  | );

    else return query(L, mid, now << ) + query(mid + , R, now <<  | );

}

int main()

{

    MYFILE();

    n = read(); m = read(); q = read();

    for(int i = ; i <= n; ++i)

        for(int j = ; j <= m; ++j) a[i][j] = read();

    build(, m, );

    for(int i = ; i <= q; ++i)

    {

        int op = read();

        if(op == )

        {

            int x = read(), y = read();

            a[x][y] ^= ; update(, y);

        }

        else

        {

            int sx = read(), sy = read(), ex = read(), ey = read();

            int ans = query(sy, ey, ).dis[sx][ex];

            write(ans == INF ? - : ans); enter;

        }

    }

    return ;

}

T3.point

期望得分60，实际得分95.

本题一开场最暴力思路想到30分。然后发现这个k必然是区间最小值，可以用st表维护，然后又发现这样无法解决判断的问题……还是O（n^3）。又发现，我们反正要求最大的区间，那不如直接从每个点往两边暴力拓展，维护与之最近的不是其倍数的点，然后这样再扫一遍，复杂度是O（n^2）的，但是实际上因为数据特别随机它卡过了95pts，而且比正解跑的快。大哥用暴力+特判直接把这题A了。

正解是，我们可以先预处理每个区间的最小值和区间gcd，如果二者相等说明此区间合法。（这个就是我没想到的了）

这样我们可以O（1）判断一个区间，预处理是O（nlog^2n），然后又因为我们要求最大区间长，所以可以直接二分答案，那么计算的复杂度就是O（nlogn），直接A题。

题外话，其实这题暴力跑的贼快，比正解快5倍，除了那个被卡掉的点。

不上95分代码啦……直接看一下老詹的A题代码（%%%%%）

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define rg register

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-;

const int maxn = 5e5 + ;

inline ll read()

{

    ll ans = ;

    char ch = getchar(), last = ' ';

    while(!isdigit(ch)) {last = ch; ch = getchar();}

    while(isdigit(ch)) {ans = ans *  + ch - ''; ch = getchar();}

    if(last == '-') ans = -ans;

    return ans;

}

inline void write(ll x)

{

    if(x < ) x = -x, putchar('-');

    if(x >= ) write(x / );

    putchar(x %  + '');

}

void MYFILE()

{

#ifndef mrclr

    freopen("point.in", "r", stdin);

    freopen("point.out", "w", stdout);

#endif

}

int n;

inline int gcd(int x, int y)

{

    return y ? gcd(y, x % y) : x;

}

int dp[maxn][][], ha[maxn];

void rmq()

{

    for(rg int i = ; i <= n; ++i) dp[i][][] = dp[i][][] = read();

    for(rg int j = ; ( << j) <= n; ++j)

        for(rg int i = ; i + ( << j) -  <= n; ++i)

        {

            dp[i][j][] = min(dp[i][j - ][], dp[i + ( << (j - ))][j - ][]);

            dp[i][j][] = gcd(dp[i][j - ][], dp[i + ( << (j - ))][j - ][]);

        }

    int x = ;

    for(rg int i = ; i <= n; ++i)

    {

        ha[i] = x;

        if(( << (x + )) <= i + ) x++;

    }

}

inline int query_Min(const int &L, const int &R)    //卡常……

{

    int k = ha[R - L + ];

    return min(dp[L][k][], dp[R - ( << k) + ][k][]);

}

inline int query_Gcd(const int &L, const int &R)

{

    int k = ha[R - L + ];

    return gcd(dp[L][k][], dp[R - ( << k) + ][k][]);

}

bool judge(const int &len)

{

    for(rg int i = ; i + len -  <= n; ++i)

    {

        int L = i, R = i + len - ;

        int Min = query_Min(L, R), Gcd = query_Gcd(L, R);

        if(!(Gcd % Min)) return true;

    }

    return false;

}

int num = ;

vector<int> ans;

int main()

{

    MYFILE();

    n = read();

    rmq();

    int L = , R = n;

    while(L < R)

    {

        int mid = (L + R + ) >> ;

        if(judge(mid)) L = mid;

        else R = mid - ;

    }

    for(rg int i = ; i + L -  <= n; ++i)

    {

        int l = i, r = i + L - ;

        int Min = query_Min(l, r), Gcd = query_Gcd(l, r);

        if(!(Gcd % Min)) num++, ans.push_back(i);

    }

    write(num); space; write(L - ); enter;

    for(rg int i = ; i < (int)ans.size(); ++i) write(ans[i]), space;

    enter;

    return ;

}

两天分数合计215可还行……菜到连本省省一线都没到。

还是撸起袖子继续干吧orz。

巴特西

10.05FZSZ Day2模拟总结

最新文章

热门文章