首页 > 其他分享 >2022.09.16 模拟赛小结（互测）

2022.09.16 模拟赛小结（互测）

时间：2022-09-20 11:00:56浏览次数：87  
标签：16 int deq sum long ret 2022.09 互测 define

2022.09.16 模拟赛小结（互测）

目录

题面

PDF链接

(这个链接只是为了自己方便找，页面设置权限了，不要尝试访问)

更好的阅读体验戳此进入

（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）

赛时思路

T1

赛时写了个暴力 + 卡时 + 随机化 + 贪心的纯纯乱搞，Luogu 能过一大半的点，不过数据被 zpair 加强之后直接除了暴力分全部寄掉了。

Code

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

namespace input{
    int seed,lst=1;
    const int prime1=163337,prime2=998244353;
    void init(){
        scanf("%d",&seed);
    }
    int read(){
        //return lst=((lst*prime1+seed)%prime2+prime2)%prime2;
    }
}

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to

/******************************
abbr

******************************/

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;



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

int a[6100000];
int N, D;
ll P;
namespace BL{
    int ans(0);
    int len(0);
    ll sum(0);
    deque < int > deq;
    int Make(void){
        for(int i = 1; i <= N - D + 1; ++i){
            len = 0;
            sum = 0;
            deq.clear();
            for(int j = 1; j <= N; ++j){
                ll val = (j >= i && j <= i + D - 1) ? 0 : a[j];
                while(!deq.empty() && sum + val > P)--len, sum -= deq.front(), deq.pop_front();
                if(sum + val <= P)deq.push_back(val), sum += val, ++len, ans = max(ans, len);
                // printf("%d ", len);
            }
            // printf("%d\n", ans);
        }
        return ans;
    }
}


int main(){
    // freopen("T1.in", "r", stdin);
    // freopen("T1.out", "w", stdout);
    N = read(); P = read<ll>(); D = read(); //input::init();
    for(int i = 1; i <= N; ++i)a[i] = read();
    if(N <= 1000){printf("%d\n", BL::Make()); return 0;}
    // printf("%d\n", BL::Make());
    int ans(0);
    ll cur(0);
    for(int i = 1; i <= D - 1; ++i)cur += a[i];
    ll maxx(-1), maxp;
    for(int i = 1; i <= N - D + 1; ++i){
        cur -= a[i - 1], cur += a[i + D - 1];
        if(cur > maxx){
            maxx = cur;
            maxp = i;
        }
    }
    // printf("%d\n", maxp);
    // for(int i = maxp; i <= maxp + D - 1; ++i)
    deque < int > deq;
    int len = 0;
    int sum = 0;
    deq.clear();
    for(int j = 1; j <= N; ++j){
        // printf("Caling p = %d\n", maxp);
        ll val = (j >= maxp && j <= maxp + D - 1) ? 0 : a[j];
        while(!deq.empty() && sum + val > P)--len, sum -= deq.front(), deq.pop_front();
        if(sum + val <= P)deq.push_back(val), sum += val, ++len, ans = max(ans, len);
        // printf("%d ", len);
    }
        int pos(0);
    while((double)clock() / CLOCKS_PER_SEC < 0.3){
        pos = 0;
        while(pos < 1 || pos > N - D + 1)pos = maxp - rndd(1, D - 1);
        // printf("Caling p = %d\n", pos);
        len = 0;
        sum = 0;
        deq.clear();
        for(int j = 1; j <= N; ++j){
            ll val = (j >= pos && j <= pos + D - 1) ? 0 : a[j];
            while(!deq.empty() && sum + val > P)--len, sum -= deq.front(), deq.pop_front();
            if(sum + val <= P)deq.push_back(val), sum += val, ++len, ans = max(ans, len);
            // printf("%d ", len);
        }
    }
    while((double)clock() / CLOCKS_PER_SEC < 0.5){
        pos = 0;
        while(pos < 1 || pos > N - D + 1)pos = int((double)maxp * ((double)rndd(1, 100) / 100) * (rnddd(50) ? 1 : -1));
        // printf("Caling p = %d\n", pos);
        len = 0;
        sum = 0;
        deq.clear();
        for(int j = 1; j <= N; ++j){
            ll val = (j >= pos && j <= pos + D - 1) ? 0 : a[j];
            while(!deq.empty() && sum + val > P)--len, sum -= deq.front(), deq.pop_front();
            if(sum + val <= P)deq.push_back(val), sum += val, ++len, ans = max(ans, len);
        }
    }
    while((double)clock() / CLOCKS_PER_SEC < 0.7){
        pos = rndd(1, N - D + 1);
        // printf("Caling p = %d\n", pos);
        len = 0;
        sum = 0;
        deq.clear();
        for(int j = 1; j <= N; ++j){
            ll val = (j >= pos && j <= pos + D - 1) ? 0 : a[j];
            while(!deq.empty() && sum + val > P)--len, sum -= deq.front(), deq.pop_front();
            if(sum + val <= P)deq.push_back(val), sum += val, ++len, ans = max(ans, len);
            // printf("%d ", len);
        }
    }
    printf("%d\n", ans);

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



template<typename T>
inline T read(void){
    T ret(0);
    short 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

写了个奇怪的暴力，写挂了，爆零。

Code

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

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to

/******************************
abbr

******************************/

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}

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


#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char buf[1<<20],*p1=buf,*p2=buf;
inline void read(int &r){
    r=0;bool w=0;char ch=getchar();
    while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
    while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
    r=w?-r:r;
}
int N, Q;
int a[51000];
namespace BL{
    int lbuc[51000], rbuc[51000];
    int sum[51000];
    void Init(void){
        memset(sum, 0, sizeof(sum));
        for(int i = 1; i <= N; ++i)sum[i] = sum[i - 1] + a[i];
        for(int i = 1; i <= N; ++i){
            for(int j = i; j <= N; ++j){
                int val = sum[j] - sum[i - 1];
                lbuc[val] = i, rbuc[val] = j;
            }
        }
    }
    void Make(void){
        for(int i = 1; i <= Q; ++i){
            int q;
            read(q);
            // scanf("%d", &q);
            printf("%d %d\n", lbuc[q] ? lbuc[q] : -1, rbuc[q] ? rbuc[q] : -1);
        }
    }
}

int main(){
    freopen("T2.in", "r", stdin);
    freopen("T2.out", "w", stdout);
    read(N), read(Q);
    // scanf("%d%d", &N, &Q);
    for(int i = 1; i <= N; ++i)read(a[i]), --a[i];
    if(N <= 20000){BL::Init(); BL::Make(); return 0;}
    

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

T3

很乱搞的一个暴力，我以为能过不少点，结果全被卡掉了，拿了暴力分跑路。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <unordered_map>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to

#define MOD (1000000007ll)

/******************************
abbr

******************************/

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}

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



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

map < pair < int, int >, ll > add;

int N, M;
ll a[210000];
ll sum[210000];
int main(){
    freopen("T3.in", "r", stdin);
    freopen("T3.out", "w", stdout);
    N = read(), M = read();
    for(int i = 1; i <= N; ++i)a[i] = read() % MOD, sum[i] = (sum[i - 1] + a[i]) % MOD;

    while(M--){
        int opt = read();
        if(opt == 1){
            int x = read(), y = read(), val = read() % MOD;
            auto tmp = add.find(make_pair(x, y));
            if(tmp == add.end())add.insert(make_pair(make_pair(x, y), val));
            else tmp->second = (tmp->second + val) % MOD;
        }else{
            int l = read(), r = read();
            ll ans = (sum[r] - sum[l - 1] + MOD) % MOD;
            for(auto i : add){
                int tl = l - i.first.second, tr = r - i.first.second;
                if(tr < 0)continue;
                int by = max(tl / i.first.first, 0);
                tl -= by * i.first.first;
                tr -= by * i.first.first;
                if(tl <= 0)ans = (ans + i.second) % MOD;
                ans = (ans + int(tr / i.first.first) * i.second % MOD) % MOD;
            }
            printf("%lld\n", ans % MOD);
        }
    }

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



template<typename T>
inline T read(void){
    T ret(0);
    short 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;
}

T4

暴力跑路。

Code

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

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to

/******************************
abbr

******************************/

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}

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



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

int N;
//x < y => -1, x > y => 1
vector < tuple < int, int, int > > relations;
int ans(0);
int a[110];
int main(){
    freopen("T4.in", "r", stdin);
    freopen("T4.out", "w", stdout);
    N = read();
    for(int i = 1; i <= N - 1; ++i){
        int x = read(), y = read(), op = read();
        relations.push_back(make_tuple(x, y, op));
    }
    int frac(1);
    for(int i = 1; i <= N; ++i)frac *= i, a[i] = i;
    --frac;
    for(int i = 1; i <= frac; ++i){
        bool flag(true);
        for(auto j : relations){
            int x, y, op; tie(x, y, op) = j;
            if((op && a[x] <= a[y]) || (!op && a[x] >= a[y])){
                flag = false;
                break;
            }
        }
        if(flag)++ans;
        next_permutation(a + 1, a + N + 1);
    }
    printf("%d\n", ans);

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



template<typename T>
inline T read(void){
    T ret(0);
    short 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 还是哪道来着想了半天感觉很接近正解，不过依然寄

正解

T1

LG-P3594 [POI2015] WIL

咕咕咕

UPD

update-2022_09_16 初稿

标签：16,int,deq,sum,long,ret,2022.09,互测,define
From： https://www.cnblogs.com/tsawke/p/16710280.html

相关文章

  • mismatched tag: line 16, column 2：解决办法
    报错：    经排查少了个结束标签，所以加上即可运行报错：listindexoutofrange  经排查是标签名不对 ......
  • redis集群槽位16384
    单机模式主从模式哨兵模式(sentinel)集群模式(cluster)RedisCluster采用虚拟槽分区，所有的键根据哈希函数映射到0～16383个整数槽内，每个节点负责维护一部分槽以及槽......
  • CF1694E Keshi in Search of AmShZ#800(div.2)
    题目链接https://codeforces.com/contest/1694/problem/E题意简述\(Keshi\)准备从城市\(1\)出发,前往\(AmShZ\)所在的城市\(n\).这里一共有\(n\)个城市,编号......
  • 2022.9.16课后博客
    static关键字在类中，用static声明的成员变量为静态成员变量，也成为类变量。类变量的生命周期和类相同，在整个应用程序执行期间都有效。这里要强调一下：static修饰的成员变量......
  • 0-4 测试面试题_16合并两个排序数组_17tcp和udp_18单元集成系统验收回归_19测试和开发
    面试题（除个别外）及部分解析答案来自牛客网https://www.nowcoder.com/exam/interview/以下所述内容并不是百分之百正确，仅供参考。16手写代码：合并两个排序数组Merge1......
  • 1636. 按照频率将数组升序排序【模拟】
    题目给你一个整数数组nums，请你将数组按照每个值的频率升序排序。如果有多个值的频率相同，请你按照数值本身将它们降序排序。请你返回排序后的数组。难度：简单提示：......
  • 全志H616基于官方外设开发-蜂鸣器
    #include<stdio.h>#include<wiringPi.h>#include<unistd.h>#defineBEEP0//设置针脚0为蜂鸣器的控制引脚intmain(void){wiringPiSetup();//初......
  • 1636. 按照频率将数组升序排序
    1636.按照频率将数组升序排序给你一个整数数组 nums ，请你将数组按照每个值的频率升序排序。如果有多个值的频率相同，请你按照数值本身将它们降序排序。 请你返......
  • Codeforces Round #316 (Div. 2) D Tree Requests
    TreeRequests判断\(V_i\)的子树中，深度为\(h_i\)的结点上所带有的字符，能否组成一个回文串启发式合并维护所有深度上不同字符的数量，并且维护其奇数字符出现的次数如......
  • 6000 字 | 16 图，吃透 Spring Cloud Gateway 原理
    大家好，我是小富～本篇给大家带来的是微服务框架中非常重要的一个组件：API网关。前言在PassJava项目中，我用到了SpringCloudGateway作为API网关，客户端的所有的请......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99