首页 > 其他分享 >2023.01.06 模拟赛小结

2023.01.06 模拟赛小结

时间：2023-01-07 16:14:54浏览次数：66  
标签：06 int 2023.01 ll ret return 小结 void define

2023.01.06 模拟赛小结

目录

更好的阅读体验戳此进入

今天的题是 sssmzy 组的，他的题居然有一道签到，真的，我哭死。

这次模拟赛没有太寄。

赛时思路

T1

CF359B Permutation。

要求你构造一个序列，满足对应条件。具体条件略。

比较简单，构造方案很多且均不难想到，总之简单想一下就知道了，妥妥的签到题。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;



template < typename T = int >
inline T read(void);

int N, K;
basic_string < int > ans;
deque < int > values;

int main(){
    freopen("structure.in", "r", stdin);
    freopen("structure.out", "w", stdout);
    N = read(), K = read();
    if(!K){
        for(int i = 1; i <= N * 2; ++i)printf("%d%c", i, i == N * 2 ? '\n' : ' ');
        exit(0);
    }
    ans += {K + 1, 1};
    for(int i = 1; i <= N * 2; ++i)if(i != K + 1 && i != 1)values.emplace_back(i);
    while(!values.empty())ans += {values.front(), values.back()}, values.pop_front(), values.pop_back();
    for(auto it = ans.begin(); it != ans.end(); ++it)printf("%d%c", *it, it == prev(ans.end()) ? '\n' : ' ');
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

checker

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;



template < typename T = int >
inline T read(void);

int a[111000];

int main(){
    while(true){
        FILE* input = fopen("in.txt", "w");
        int N = rndd(1, 50000), K = rndd(0, N >> 1);
        fprintf(input, "%d %d\n", N, K);
        fcloseall();
        system("./std < in.txt > my.out");
        FILE* output = fopen("my.out", "r");
        for(int i = 1; i <= N * 2; ++i)fscanf(output, "%d", &a[i]);
        fcloseall();
        ll sum1(0), sum2(0);
        for(int i = 1; i <= N * 2; i += 2)sum1 += abs(a[i + 1] - a[i]), sum2 += a[i + 1] - a[i];
        sum2 = abs(sum2);
        if(sum1 - sum2 == K << 1)printf("Accept!\n");
        else printf("Wrong!\n"), exit(0);
    }

    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

T2

LG-P4884 多少个 1？。

给定 $ m, k $，求满足 $ 111 \cdots 111 \equiv k \pmod{m} $（共 $ n $ 个 $ 1 $）的最小 $ n $。

读完题之后想到的思路是把所有 $ 1 $ 拆分为 $ 10^{n - 1} + 10^{n - 2} + \cdots + 10^0 $，于是问题就转换为了对每个数取模之后加起来再取模，然后通过欧拉定理将幂次对 $ \varphi(m) = m - 1 $ 取模即可，这样的话就是 $ [0, m - 2] $ 循环，循环长度为 $ m - 1 $，然后记录一下 $ 10^i \bmod{m}(i \in [0, m - 2]) $ 的值即可，这样时空复杂度都是 $ O(n) $ 的，唯一有一个问题就是不知道会循环多少次，虽然结论似乎是 $ n \le m $ 的，不过总之赛时我用了一个类似卡时的思路去限定了一下。无论如何最后 $ m \le 5 \times 10^7 $ 的部分分过了，最终 $ 60\texttt{pts} $。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template < typename T = int >
inline T read(void);

ll K, MOD;
ll pow10[51000000];
ll sum(1);
ll ans(LONG_LONG_MAX);
const ll mxCnt = (ll)(1e8 + 114514);

int main(){
    freopen("date_struct.in", "r", stdin);
    freopen("date_struct.out", "w", stdout);
    K = read < ll >(), MOD = read < ll >();
    ll lim = mxCnt / (MOD - 1);
    pow10[0] = 1;
    for(int i = 1; i <= MOD - 2; ++i)pow10[i] = pow10[i - 1] * 10 % MOD, (sum += pow10[i]) %= MOD;
    ll cur(0);
    for(int i = 0; i <= MOD - 2; ++i){
        (cur += pow10[i]) %= MOD;
        if(cur == K)printf("%d\n", i + 1), exit(0);
    }cur = 0;
    for(int i = 0; i <= MOD - 2; ++i){
        (cur += pow10[i]) %= MOD;
        for(int j = 1; j <= lim; ++j)
            if((cur + sum * j % MOD) % MOD == K)ans = min(ans, (ll)i + 1 + (MOD - 1) * j);
    }
    printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

把 BSGS 的题刷一圈之后再回来继续补。

T3

CF494C Helping People。

Code

T4

COT3 - Combat on a tree。

Code

正解

T2

尝试进行转化，对 $ \texttt{LHS} \leftarrow \texttt{LHS} \times 9 + 1 $ 即可转换为 $ 10 $ 的幂，即：

\[10^n \equiv 9k + 1 \pmod{m} \]

然后套一下 BSGS 模板即可。

依然可以不使用光速幂，最终复杂度 $ O(\sqrt{m} \log m) $。

注意过程中部分需要使用 __int128_t。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template < typename T = int >
inline T read(void);

ll K, M;
unordered_map < ll, ll > mp;

ll qpow(ll a, ll b){
    ll ret(1), mul(a);
    while(b){
        if(b & 1)ret = (__int128_t)ret * mul % M;
        b >>= 1;
        mul = (__int128_t)mul * mul % M;
    }return ret;
}

int main(){
    K = read < ll >(), M = read < ll >();
    ll lim = (ll)ceil(sqrt(M));
    for(int i = 1; i <= lim; ++i)mp.insert({(__int128_t)(9 * K + 1) % M * qpow(10, i) % M, i});
    for(int i = 1; i <= lim; ++i){
        ll val = qpow(10, (ll)i * lim);
        if(mp.find(val) != mp.end())printf("%lld\n", (ll)i * lim - mp[val]), exit(0);
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

T3

Code

T4

Code

UPD

update-2022__ 初稿

标签：06,int,2023.01,ll,ret,return,小结,void,define
From： https://www.cnblogs.com/tsawke/p/17032818.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99